- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
2022年安徽农业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)
一、选择题
1、下述文件中适合于磁带存储的是( )。
A.顺序文件
B.索引文件
C.哈希文件
D.多关键字文件
2、无向图G=(V,E),其中:V={a,b,c,d,e,f},E={(a,b),(a, e),(a,c),(b,e),(c,f),(f,d),(e,d)},对该图进行深度优先遍历,得到的顶点序列正确的是( )。
A.a,b,e,c,d,f B.a,c,f,e,b,d
C.a,e,b,c,f, d D.a,e,d,f,c,b
3、链表不具有的特点是( )。
A.插入、删除不需要移动元素 B.可随机访问任一元素
C.不必事先估计存储空间 D.所需空间与线性长度成正比
4、已知串S=aaab,其next数组值为( )。
A.0123 B.1123 C.1231 D.1211
5、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}, E={V1,V2,V1,V3,V1,V4,V2,V5,V3,V5, V3,V6,V4,V6,V5,V7,V6,V7},G的拓扑序列是( )。
A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7
6、下列关于无向连通图特性的叙述中,正确的是( )。
Ⅰ.所有的顶点的度之和为偶数 Ⅱ.边数大于顶点个数减1 Ⅲ.至少有一个顶点的度为1
A.只有Ⅰ B.只有Ⅱ C.Ⅰ和Ⅱ D.Ⅰ和Ⅲ
7、下列选项中,不能构成折半查找中关键字比较序列的是( )。
A.500,200,450,180 B.500,450,200,180
C.180,500,200,450 D.180,200,500,450
8、已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历结果为( )。
A.CBEFDA B.FEDCBA C.CBEDFA D.不定
9、有关二叉树下列说法正确的是( )。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
10、对序列{15,9,7,8,20,-1,4}用希尔排序方法排序,经一趟后序列变为{15,-1,4,8,20,9,7}则该次采用的增量是( )。
A.1 B.4 C.3 D.2
二、填空题
11、有向图G=(V,E),其中V(G)={0,1,2,3,4,5},用a,b,d 三元组表示弧a,b及弧上的权d。E(G)为E(G)={0,5,100,0, 2,10,1,2,5,0,4,30,4,5,60,3,5,10,2, 3,50,4,3,20},则从源点0到顶点3的最短路径长度是______,经过的中间顶点是______。
12、分别采用堆排序,快速排序,起泡排序和归并排序,对初态为有序的表,则最省时间的是______算法,最费时间的是______算法。
13、建立索引文件的目的是______。
14、外排序的基本操作过程是______和______。
15、应用Prim算法求解连通网络的最小生成树问题。(1)针对如图所示的连通网络,试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
(2)下面是Prim算法的实现,中间有5个地方缺失,请阅读程序后将它们补上。
16、设有N个结点的完全二叉树顺序存放在向量A[1:N]中,其下标值最大的分支结点为______。
17、在顺序存储的二叉树中,编号为i和j的两个结点处在同一层的条件是______。
18、已知链队列的头尾指针分别是f和r,则将值x入队的操作序列是______。
三、判断题
19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。( )
20、倒排文件是对次关键字建立索引。( )
21、稀疏矩阵压缩存储后,必会失去随机存取功能。( )
22、设栈采用顺序存储结构。若已有i-1个元素入栈,则将第i个元素入栈时,入栈算法的时间复杂性为O(i)。( )
23、对于有n个结点的二叉树,其高度为log2n。( )
24、树形结构中元素之间存在一对多的关系。( )
25、外部排序是把外存文件调入内存,可利用内部排序的方法进行排序,因此排序所花的时间取决于内部排序的时间。( )
26、快速排序和归并排序在最坏情
文档评论(0)