南京信息工程大学滨江学院数据结构期末试题及答案
更新时间:2024-06-11 10:41:01 阅读量: 综合文库 文档下载
一、单项选择题
1、在以下的叙述中,正确的是( A )。 A. 线性表的线性存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出
2、判定一个循环队列qu(最多元素为m0)为空的条件是( A )。 A. qu->front==qu->rear B. qu->front!=qu->rear C. qu->front=(qu->rear+1)%m0 D. qu->front!=(qu->rear+1)%m0
3、向一个栈顶指针为hs的链栈中插入一个s所指结点时,则执行( C )。 A. hs->next=s;
B. s->next=hs->next;hs->next=s; C. s->next=hs;hs=s; D. s->next=hs;hs=sh->next
4、串是一种特殊的线性表,其特殊性体现在( B )。 A. 可以顺序存储 B. 数据元素是一个字符 C. 可以链接存储 D. 数据元素可以是多个字符 5、设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i≥j),在一维数组B的下标位置k的值是( B )。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j
6、将递归算法转换成对应的非递归算法时,通常需要使用( A )。
第 1 页 (共 9 页)
A. 栈 B. 队列 C. 链表 D. 树
7、树的基本遍历策略可分为先根遍历和后根遍历叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里,我们把由树转化得到的二叉树叫做这棵树对应的二叉树。结论__A__是正确的。 A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D. 以下都不对
8、对一个满二叉树,m个树叶,n个结点,深度为h,则( D )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 9、具有7个顶点的无向图至少应有( A )条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8
10、判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用( D )。
A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 宽度优先遍历算法 D. 深度优先遍历算法
11、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,( C )次比较后查找成功。
A. 1 B. 2 C. 4 D. 8 12、如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用___A__查找方法。
A. 分块 B. 顺序 C. 二分 D. 散列
13、在所有排序方法中,关键字比较的次数与记录的初始排列次序无关的是____D_____。
A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
第 2 页 (共 9 页)
14、快速排序方法在( C )情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 15、索引无序文件是指( A )。 A. 主文件无序,索引表有序 B. 主文件有序,索引表无序 C. 主文件有序,索引表有序 D. 主文件无序,索引表无序 二、填空题(每空 2 分,共 30 分)
16、下面程序段的时间复杂度是___O(m*n)____。 for ( i=0;i 17、向栈中压入元素的操作是_p->next=s;p->data=x;s=p;_。 18、在hq的链队中,判定只有一个结点的条件是__hq->front=hq->rear__。 19、已知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),A[i][j]的地址是___LOC(A[0][0])+(n*i+j)*k___。 20、有如下递归方程: void print(int w) { int i; if (w!=0) 第 3 页 (共 9 页) { print(w-1); for (i=1;i<=w;i++) print(“=”,w); rpintf(“/n”); } } 调用语句print(4)结果是___1 2 2 3 3 3 4 4 4 4_____ 21、广义表(a,(a,b),d,e,((i,j),k)) 的长度是___5_____,深度是__3___。 22、以数据集{4,5,6,7,10,12,18}为结点权值所构造的哈夫曼树为_____,其带权路径长度为________。 23、已知图G的邻接表如下图所示,其从顶点v1出发的深度优先搜索序列为_v1->v2->v3->v6->v5->v4_,其从顶点v1出发的宽度优先搜索序列为_v1->v2->v5->v4->v3->v6_。 24、在各种查找中,平均查找长度与结点个数n无关的查法方法是_哈希___。 第 4 页 (共 9 页) 25、在对一组记录{54,38,96,23,15,72,60,45,83}进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较_3_次。 26、顺序查找法的平均查找长度为__n(n+1)/2_____;二分查找法的平均查找长度为___((n+1)*log2(n+1))/n-1____。 三、解答操作题(每小题 5 分,共 20 分) 27、已知序列{503,87,512,61,908,170,897,275,653,462},采用基数排序法对该序列作升序排序时的每趟的结果。 A[0]=170 A[1]=61 A[2]=512->462 A[3]=503->653 A[5]=275 A[7]=87->897 A[8]=908 28、设给定权集w={2,3,4,7,8,9},度构造关于w的一棵哈夫曼树,并求其加权路径长度wpl。 29、对下图所示的树: (1)转换成对应的二叉树形式,并且说明转换规则; (2)写出前序、中序、后序遍历的结果; 第 5 页 (共 9 页) 30.现有稀疏矩阵A如下图所示,要求画出以下几种表示法。 (1)三元组表示法 (2)带行指针向量的单链表表示法 (3)十字链表示法。 四、算法阅读题(每小题6分,共12分) 31、下列算法的功能是实S串的逆序 (串均采用顺序存储方式),请在空白处填入适当的内容。 SeqString *invert (SegString *s) { int i; char temp for (i=0; i s->ch[i]=s->ch[ s->length-i+1 ]; s->ch[s->length-i+1]= temp ; } return s ;} 32.下列算法的功能是实现链栈的进栈运算,请在空白处填入适当的内容。 链栈的类型定义如下: Typedef struct stacknode { DataType data; Struct stacknode *next; } StackNode; Typedef struct { StackNode *top; 第 6 页 (共 9 页) }LinkStack; Void Push(LinkStack *s,DataType x) { StackNode p; *p=(StackNode *)malloc(sizeof(StackNode)); p->data= x ; p->next= s->top ; s->top= p ; } 五、算法设计题 33、假设二叉树采用链接方法存储,编写一个函数复制一棵给定的二叉树。结点结构为: Copy(BiTree *T) { if(!T)return NULL; BiTree *S=new BiTree; if(T->Lchild) S->Lchild=T->Lchild; Copy(T->Lchild); if(T->Rchild) S->Rchild=T->Rchild; Copy(T->Rchild); } D 卷 一、单项选择题1. B 2. A 3. C 4. B 5. B 6. A 7. A 8. D 9. A 10. D 11. C 12. A 13. D 14. C 15. A 二、填空题(每小题2分,共30分) 16. O(m*n) 17. 先移动栈顶指针,后存入元素 18. hq->front==hq->rear 19. LOC(A[0][0])+(n*i+j)*k 20. 答 1 2 2 3 3 3 4 4 4 4 23、 v1,v2,v3,v6,v5,v4 v1,v2,v5,v4,v3,v6 24、哈希表查找法 25、3 26、(n+1)/2 ((n+1)*log2(n+1))/n-1 第 7 页 (共 9 页) 三、操作题(每小题5分,共20分) 27、初始:503,87,512,61,908,170,897,275,653,462 第1趟(按个位排序)170,61,462,512,503,653,475,87,897,908 第2趟(按十位排序)503,908,512,653,61,462,170,175,87,897 第3趟(按百位排序)61,87,170,275,462,503,512,653,897,908 28、加权路径长度wpl=7×2+8×2+4×3+2×4+3×4+9×2=80 29.(1) (2) 前序:abcejfdghki 中序:jefcgkhidba 后序:jfekihgdcba 30. 四、算法设计题(每小题 6 分,共 12 分) 参考答案 31.s-length-i+1 Temp Return(s) 32. p->data=x; p->next=s->top; s->top=p; 五、算法设计题(共8分) 参考答案 33. Btree *copy(btree *b) { Btree *p; If (b!=NULL) { P=(btree *)malloc(sizeof(btree)) p->data=b->data; p->left=copy(b->left); p->right=copy(b->right); return(p); } Else return(NULL); } 第 8 页 (共 9 页) 第 9 页 (共 9 页)
正在阅读:
主体施工方案11109-28
绍兴市市属中小学教学案例获奖名单04-25
Chapter 3财管习题06-10
浅谈电子技术在汽车上的应用论文08-24
教研工作总结范文大全07-30
【热门】小猫的故事作文汇总七篇03-23
无法访问局域网内IIS服务器的解决办法09-01
2017年广东省韶关市南雄市中考物理(四模)试卷含答案12-02
中行合规测试题目手册04-08
- 必修一物理寒假作业
- 2019-201X年5月大学生入党积极分子思想汇报-word范文模板(3页)
- 药物分析习题五
- 重拾应用意识 体会数学价值(沈建军)
- 2017全国高校辅导员结构化面试题集及参考答案
- 广东徐闻县实验中学2014届高三第二次月测地理试题
- 今天你共鸣了么?
- 2018-2019正能量读后感1000字-推荐word版(6页)
- 2018年中国截切型盖板针布行业专题研究分析报告目录
- 中国移动业务处理流程大全
- 公文写作常用词汇和句子集锦2016
- ARM课程设计说明书
- 教师资格证教育学论文
- 中考试卷分析
- 环境监测试卷(五)
- 党风廉政建设广播稿1
- 快速制作香香宫煮麻辣烫教程
- 《国际金融学》习题
- 文明施工保障措施方案
- 春兰维修资料故障代码
- 滨江
- 数据结构
- 南京
- 期末
- 试题
- 答案
- 学院
- 工程
- 大学
- 信息
- 内皮细胞的培养
- 中央电大《城市管理》试题及参考答案 - 图文
- 新仁爱版八年级英语上册《Unit 1 Playing Sports Topic 3 Sectio
- 大气压导学案
- 大学迎新晚会演讲稿4篇
- 农村葬礼习俗调查报告
- 其他高等教育机构的设立、分立、合并、变更名称、类别及章程修改
- 高中生物学教学中拓展性内容的运用与思考 - 图文
- 河南高等教育教学改革研究项目立项申请书
- 体育艺术2+1工作总结2014
- 画图解题有时也便捷
- 高压电工(1)
- 2015年四川省选调生行测真题及解析
- 万家学校教学奖惩制度
- 分布式电源对配电网保护影响的研究开题报告+文献综述+中期报告+
- 康腾杯案例分析大赛优秀作品
- 七年级语文第一学月考试试卷
- 五年级上小数乘除混合运算习题
- 微电影拍摄感想
- 人教版小学数学三年级上册:第五单元 倍的认识教案 - 图文