《数据结构》期末复习题 答案

内容发布更新时间 : 2024/12/23 11:59:07星期一 下面是文章的全部内容请认真阅读。

1. 以下与数据的存储结构无关的术语是( c ) C、哈希表

2. 一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( B ) B、108

3. 假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是( C ) C、head–>next= =head

4. 若进栈序列为1,2,3,4,5,6,且进栈和出栈可以穿插进行,则不可能出现的出栈序列是( D )

D、2,3,5,1,6,4

5. 下列关键字序列中,构成小根堆的是( A ) A、{12,21,49,33,81,56,69,41}

6. 下列数据结构中,不属于二叉树的是( A ) A、B树

7. 用顺序存储的方法来存储一棵二叉树,存放在一维数组A[1..N]中,若结点A[i]有右孩子,则其右孩子是( C )。 C、A[2i+1]

8. 设树T的高度为4,其中度为1、2、3、4的结点个数分别为4、2、1、1,则T中叶子数为( D ) D、 8

9. 有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,则应选择下面哪个序列输入( B ) B、37,24,12,30,53,45,96

10. 对下面有向图给出了四种可能的拓扑序列,其中错误的是( C ) C、5,1,6,3,4,2

11. m阶B-树中所有非终端(除根之外)结点中的关键字个数必须大于或等于( B ) B、[m/2]-1

12. 散列文件也称为( C ) B 、索引文件

13. 数据结构是( D )

D、相互之间存在一种或多种特定关系的数据元素的集合

14. 从逻辑关系来看,数据元素的直接前驱为0个或1个的数据结构只能是( C ) C、线性结构和树型结构

15. 设p为指向双向循环链表中某个结点的指针,p所指向的结点的两个链域分别用p→llink和p→rlink表示,则同样表示

1

p指针所指向结点的表达式是( D ) D、p→llink→rlink 16.

若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈( i =1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是( B ) B、 top[1]+1=top[2] 17.

若一棵二叉树有11个叶子结点,则该二叉树中度为2的结点个数是( A ) A、10 18.

树的先根序列等同于与该树对应的二叉树的( A ) A、先序序列 19.

下面关于哈希(Hash,杂凑)查找的说法正确的是( C ) C、不存在特别好与坏的哈希函数,要视情况而定 20.

下列序列中,( D )是执行第一趟快速排序后所得的序列。

D、 [68,11,69,23,18] [93,73] 21.

下列关键字序列中,构成小根堆的是( D ) D、 (15,28,46,37,84,58,62,41) 22.

ISAM文件和VASM文件属于( C ) C、索引顺序文件 23.

下面程序段的时间复杂度为( C )

for (i=0; i

for (j=0; j

A[i][j]=i*j;

C、O(m*n) 24.

已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为( A ) A、q->next=s->next;s->next=p; 25.

为便于判别有向图中是否存在回路,可借助于( D ) D、拓扑排序算法 26.

若以S和X分别表示进栈和退栈操作,则对初始状态为空的栈可以进行的栈操作系列是( D ) D、SSSXXSXX 27.

设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应

2

该是( B ) B、3 28.

假设以数组A[m]存放循环队列的元素。已知队列的长度为length,指针rear指向队尾元素的下一个存储位置,则队头元素所在的存储位 置为( B )。 B、(rear-length+m)%m 29.

在一个链队列中,front和rear分别为头指针和尾指针,则插入一个结点s的操作为( D )。 D、rear->next=s;rear=s; 30.

对于哈希函数H(key)=key,被称为同义词的关键字是( D )

D、25和51 31.

采用二叉链表存储的n个结点的二叉树,共有空指针( A )个。 A、n+1 32.

连通网的最小生成树是其所有生成树中( D )

D、边的权值之和最小的生成树 33.

对记录序列(314,298,508,123,486,145)依次按个位和十位进行两趟基数排序之后所得结果为( B )

B、508,314,123,145,486,298 34.

任何一个无向连通图的最小生成树( C )。 C、一棵或多棵 35.

无向图的邻接矩阵是一个( C ) C、对称矩阵 36. 37.

设无向图G-=(V,E)和G’=(V’,E’),如G’为G的生成树,则下列说法中不正确的是( B )。B、G’为G 连通分量 以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是( D ) D、 v1,v2,v5,v6,v7,v3,v4 38.

下面几个符号串编码集合中,不是前缀编码的是( B ) B、{0,1,00,11} 39.

希尔排序的增量序列必须是(B )。 B、递减的 40.

采用起泡排序法对n个关键字进行升序排序,若要使排序过程中比较关键字的次数最多,则初始时的序列应满足条件( D )

D、关键字从大到小排列 41.

在下列内部排序中( A )是不稳定的。

3

A、希尔排序 42.

分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( C )。 A、(100,80, 90, 60, 120,110,130) 43.

在查找过程中,冲突指的是( C )。 C、不同键值对应相同的存储地址 44.

对有14个元素的有序表A[1..14]作二分查找,查找元素A[4]时的被比较元素依次为( D )。 D、A[7],A[3],A[5],A[4] 45.

以v1为起始结点对下图进行广度度优先遍历,正确的遍历序列是( A ) A、 v1,v2,v3,v4,v5,v6,v7

二、填空题(本大题共10小题,每小题2分,若有两个空格,每个空格1分,共20分) 1. 2. 3.

数据的物理结构包括 数据元素 的存储和 数据之间关系 的存储。

若一个算法中的语句频度之和为T(n)=1921n+4nlogn,则算法的时间复杂度为 nlogn 。 下面程序段的时间复杂度是 log3n 。

i=1;

while (i<=n) i=i*3; 4.

循环队列用数组A[0..m-1]存放其元素值,已知其头尾指针分别是front和rear ,则当前队列的元素个数是 ( rear-front+m )% m 5. 6. 7. 8.

主要是使插入和删除等操作统一 (n-1)/2 。

在单链表中设置头结点的作用是 深度优先 。

线性表L=(a1,a2,?,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是 相同值关键字 。 9.

已知一无向图G=(V,E),其中V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点a开始遍历图,得到的序列为abecd,则采用的是 前移 遍历方法。 10. 11. 12. 13.

如果排序过程不改变 时间复杂度 之间的相对次序,则称该排序方法是稳定的。 从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需 出度 一个位置。 当问题的规模n趋向无穷大时,算法执行时间T(n)的数量级被称为算法的 10 。

若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数即为顶点vi的 sxssxxssxssxxx 。

4

14. 15.

一棵含999个结点的完全二叉树的深度为 12 。

假设S和X分别表示进栈和出栈操作,由输入序列“ABC”得到输出序列“BCA”的操作序列为SSXSXX,则由“a*b+c/d”得到“ab*cd/+”的操作序列为 4 。

16. 17.

.如图所示的有向无环图可以排出 L->next->next==L 边 种不同的拓扑序列。

18. 从空树起,依次插入关键字1l,27,35,48,52,66和73构造所得的二叉排序树,在等概率查找的假设下,查找成功时的平均查找长度为 384 。

19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30.

带头结点的双循环链表L中只有一个元素结点的条件是 队列 。

求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中 边稠密 、边稀疏 的数目正相关。 已知一棵完全二叉树中共有768结点,则该树中共有 5 个叶子结点。

实现图的广度优先搜索,除了一个标志数组标志已访问的图的结点外,还需要 8、64 存放被访问的结点以实现遍历。 Prim(普里姆)算法适用于求 2h-1 的网的最小生成树;kruskal(克鲁斯卡尔)算法适用于求 2h-1 的网的最小生成树。 对长度为20的有序表进行二分查找的判定树的高度为 n-1 。

设一棵完全二叉树有128个结点,则该完全二叉树的深度为 n ,有_ 个叶子结点。 高度为h的完全二叉树中最少有 栈 个结点,最多有 个结点。 设连通图G中有n个顶点e条边,则对应的最小生成树上有 3 条边。 构造n个结点的强连通图,至少有 O(n) 条弧。

表达式求值是 (42,13,94,55,05,46,17) 应用的一个典型例子。

设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5,e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈的容量至少应该是 。

2

31. 32.

快速排序算法在最差的情况下其时间复杂度是 。

对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是 。

三、应用题(本大题共5小题,每小题6分,共30分) 1.

已知二叉树的先序遍历序列ABCDEFGH,中序遍历序列为CBEDFAGH,画出二叉树。

5

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi