《数据结构》期末考试复习题及参考答案

1 / 17

数据结构 复习题

（课程代码 252259）

一、填空题（本大题共40小题）

1. 队列中是按照______先进先出______的原则进行数据元素的增删。

2. ___栈__又称为LIFO表。

3. 在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。

4. 存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。

5. 在串S=“structure”中，以r为首字符的子串有_9_个。

6. 设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。

7. 在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。

8. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40） （ ） （74） （23,55，63）____。

9. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。

10. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。

11. 在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。

12. 一棵深度为5的满二叉树中的结点数为_______31_______个。

13. 在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。

14. 从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。

15. _____拓朴排序______可以判断出一个有向图中是否有环。

16. 栈又称为______后进先出__________的线性表。

17. 数据结构在计算机中的表示称为数据的__物理结构____。

18. 有4个结点的不同的二叉树有__9___棵。

19. 含有60个结点的树有____59____条分支。

20. 在图结构中，前驱元素和后继元素之间存在着_____多对多____的联系。

21. ____哈夫曼树____又称最优二叉树。 2 / 17

22. 一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有___33___个。

23. 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=______ p－＞next－＞next ____。

24. 栈顶的位置是随着_____进栈和出栈______操作而变化的。

25. 设一个散列表的容量为M，用线性探测法解决冲突.。若要查找一个键值，至少要进行1次比较，至多要进行_____M_____次比较。

26. 在n个结点的线索二叉链表中，有____ n-1___个线索指针。

27. 具有180个结点的二叉树，其深度至少为___8______。

28. 序列中有1000个元素基本按键值递增顺序排列，就算法的比较次数而言，应选择______

_____直接插入_____排序算法。

29. 若堆栈的入栈序列为1,2,3,…,n-1,n，输出元素i需要进行____ n-i+1______次出栈操作。

30. 对于队，只能在 队尾 插入元素，只能在 队头

删除元素。

31. 抽象数据类型ADT可以用三元组（D，S，P）表示，它们分别表示： 数据对象 、 数据关系 和 基本操作 。

32. 栈是一种受限制的线性表，也叫LIFO结构，LIFO的含义是 后进先出

33. 在单链表中，若要在指针p所指结点后插入指针s所指结点，则需要执行下列两条语句：s->next=p->next； p->next=s

34. 通常从四个方面评价算法的质量：___正确性 易读性 强壮性 高效率_____。

35. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为___ O(n)_____。

36. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为___9_______个，树的深度为_____3______，树的度为___3______。

37. 后缀算式9 2 3 +- 10 2 / -的值为____－1______。中缀算式（3+4X）-2Y/3对应的后缀算式为_______3 4 X * + 2 Y * 3 / -________________________。

38. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有___2n_____个指针域，其中有__n-1______个指针域是存放了地址，有_______n+1_________个指针是空指针。

39. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_____e__个和____2e____个。

40. AOV网是一种________有向无回路___________的图。

二、单项选择题（本大题共50小题）

1． 将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（D ） 3 / 17

A）O（1） B）O（n） C）O（m） D）O（m+n）

2． 如下所示的图的拓扑序列为（ D ）

A） C1，C2，C3，C4，C5，C6

B) C1，C2，C5，C3，C4，C5，C7

C) C1，C4，C2，C3，C5，C6

D) C1，C2，C5，C4，C3，C6

3． 在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( D )

A）e B）2e C）n2－e D）n2－2e

4． 设有6个结点的无向图，该图至少应该有(A)条边才能确保是一个连通图

A．5 B．6 C．7 D．8

5． 有N个结点的图的邻接矩阵存储法中，链表的表头结点有（ A ）个。

A、 N B、 2N C、N/2 D、N*N E、N-2

6． 具有4个顶点的无向完全图有（ A ）条边。

A、6 B、12 C、16 D、20

7． 邻接矩阵是对称矩阵的图为(D ）。

A、有向图 B、带权有向图 C、带权连通图 D、无向图

8． 在长度为n的线性表中查找值为x的数据元素的时间复杂度为（ C ）。

A）O(0) B）O(1) C）O(n) D）O(n2)

9． 若一个栈的输入序列是1，2，3，„„，n，输出序列的第一个元素是n，则第i个输出元素是（ D ）。

A）不确定 B）n-i C、n-i-1 D、n-i+1

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

A、6 B、4 C、3 D、2

11． 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的出栈序列是（ C ）。

A、5，4，3，2，1 B、4，5，3，2，1 C、4，3，5，1，2 D、1，2，3，4，5

12． 设计一个判别表达式中左右括号是否匹配的算法，采用（ B ）数据结构最佳。

A、顺序表 B、栈 C、队列 D、链表

13． 在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印缓冲区，该缓冲区应该是一个（ B ）结构。 C1

C2 C3

C4

C5 C6 4 / 17

A、栈 B、队列 C、数组 D、线性表

14． 线性表若采用链表存储结构，要求内存中可用存储单元地址( D )

A．必须连续 B．部分地址必须连续 C．一定不连续 D．连续不连续均可

15． 依次在初始为空的队列中插入元素X，Y，Z，W以后，紧接着作了两次删除操作，此时的队头元素是（ C ）

A）X B）Y C）Z D）W

16． 已知一个有向图如下图所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为（ A ）。

A) a d b e f c

B) a d c e f b

C) a d c b f e

D) a d e f c b

17． 若连通无向图G有n个顶点，则图G的生成树有（ B ）条边

A）n B）n-1 C）n(n-1)/2 D）n/2

18． 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ D ）

A）front=front+1 B）front=(front+1)%(m-1)

C）front=(front-1)%m D）front=(front+1)%m

19． 设某算法的问题规模函数f(n)=25n3+5000n2，则它的渐进时间复杂度为（ A ）。

A）O(n3) B）O(n2) C）O(n) D）O(1)

20． 假定一个顺序队列的队首和队尾指针分别为f和r，则判断队空的条件为( D )。

A）f+1==r B）r+1==f C）f==0 D）f==r

21． 线性表采用链式存储时，结点的存储地址（ B ）

A） 必须是不连续的 B） 连续与否均可