2024年4月30日发(作者：)

《数据结构与算法》期末练习

一 选择题

1．以下与数据的存储结构无关的术语是（ D ）。

A．循环队列 B. 链表 C. 哈希表

D.

栈

2. 算法的时间复杂度取决于（ A ）

A．问题的规模 B. 待处理数据的初态 C. A和B D.

计算机cpu

3. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输

出序列的是（ B ）。

A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5

4 3 2

4. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，又有

动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)

静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不

能增加。(3) 静态链表与动态链表在元素的插入、删除上类似，不需

做元素的移动。以上错误的是（ B ）

A．（1），（2） B．（1） C．（1），（2）,(3) D.

（2）

5．对于有n 个结点的二叉树, 其高度为（ D ）

A．nlog

2

n B．log

2

n C．ëlog

2

nû|+1 D．不

确定

6．从下列有关树的叙述中,选出正确的叙述（ C ）

A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当K≥1时高度为K的二叉树至多有2

k-1

个结点。

C．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。

D．在二叉树中插入结点,该二叉树便不再是二叉树。

7．设无向图的顶点个数为n，则该图最多有（ B ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0

E．n

2

8．已知有向图G=(V,E)，其中V={V

1

,V

2

,V

3

,V

4

,V

5

,V

6

,V

7

}，E={

1

,V

2

>,

1

,V

3

>,

1

,V

4

>,

2

,V

5

>,

3

,V

5

>,

3

,V

6

>,

4

,V

6

>,

5

,V

7

>,

6

,V

7

>},G的拓扑序列是（ A ）。

A．V

1

,V

3

,V

4

,V

6

,V

2

,V

5

,V

7

B．V

1

,V

3

,V

2

,V

6

,V

4

,V

5

,V

7

C．V

1

,V

3

,V

4

,V

5

,V

2

,V

6

,V

7

D．V

1

,V

2

,V

5

,V

3

,V

4

,V

6

,V

7

9．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序 B. 快速排序，堆排序

C. 希尔排序，归并排序 D. 归并排序，冒泡排序

10．对一组数据（84，47，25，15，21）排序，数据的排列次序在排

序的过程中的变化为

（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47

(4） 15 21 25 47 84

11. 则采用的排序是 ( A )。

A. 选择 B. 冒泡 C. 快速 D.

插入

12．以下数据结构中，哪一个是线性结构（ D ）

A．广义表 B. 二叉树 C. 稀疏矩阵 D.

串

13．下面关于线性表的叙述中，错误的是哪一个（ B ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

14. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的

合法输出序列的是（ D ）。

A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D.

3 2 1 5 4

15. 设n为正整数.下列程序段中前置以@的语句的频度为（ B ）。

i = 1; k = 0;

do{

@ k+= 10*i;

i++;

}While(i <= n-1);

A. n – 1 B. n C. n + 1 D. n - 2

16. 一棵具有 n个结点的完全二叉树的树高度（深度）是（ A ）

A．ëlognû+1 B．logn+1 C．ëlognû

D．logn-1

17．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输

出第i（1<=i<=n）个元素是（ B ）。

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

n-i

18．n个结点的完全有向图含有边的数目（ D ）。

A．n*n Ｂ．n（n＋１） C．n／2 D．n*

（n－l）

19．稳定的排序方法是（ B ）

A．直接插入排序和快速排序 B．折半插入排序和起泡排序

C．希尔排序和四路归并排序 D．树形选择排序和shell排

序

20．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分

方法进行一趟划分后数据的排序为 ( A )（按递增序）。

A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，

20

C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，

20

21．以下那一个术语与数据的存储结构无关（ A ）

A．栈 B. 哈希表 C. 线索树 D.

双向链表

22．下面关于串的的叙述中，哪一个是不正确的（ B ）

A．串是字符的有限序列 B．空串是由空格构成的串

C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，

也可以采用链式存储

23. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能

是它的输出序列的是（ D ）。

A. a，c，b，d B. b, c，d，a C. c, d，b, a D.

d, c，a，b

24. 关于二叉树的叙述：①只有一个结点的二叉树的度为0; ②二

叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完

全二叉树的结点个数小于或等于深度相同的满二叉树。正确的是

（ D ）

A．①②③ B．②③④ C．②④ D．①④

25．高度为 K的二叉树最大的结点数为（ C ）。

A．2

k

B．2

k-1

C．2

k

-1 D．2

k-1

-1

26．从下列有关树的叙述中,选出正确的叙述（ C ）

A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。

B．当K≥1时高度为K的二叉树至多有2

k-1

个结点。

C．用树的前序遍历和中序遍历可以导出树的后序遍历。

D．哈夫曼树是带权路径最长的树,路径上权值较大的结点离根较

近。

27. 关键路径是事件结点网络中（ A ）。

A．从源点到汇点的最长路径 B．从源点到汇点的最短路

径

C．最长回路 D．最短回路

28．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应

的顶点，则输出的顶点序列是( A )。

A．逆拓扑有序 B．拓扑有序 C．无序的

29．一组记录的关键码为（46，79，56，38，40，84），则利用快速

排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。

A．(38,40,46,56,79,84) B. (40,38,46,79,56,84)

C．(40,38,46,56,79,84) D. (40,38,46,84,56,79)

30. 一个向量的第一个元素的地址是begin，每个元素的长度是k ，

则第i个元素的地址是( D )

A. begin+(k-1)i B. begin+(k-2)i C. begin+ki D.

begin+(i-1)k

31. 有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，

100}，用折半查找法，若要找63，要经过( C )次与63比较。

A. 12 B. 6 C. 4 D. 5

32. 一个序列的初始状态为（46，77，82，53，31，70），今对其进

行冒泡排序，当进行两趟冒泡后，序列中的元素排列为( D )。

A.（31，46，70，53，77，82）

B.（46，77，53，31，70，82）

C.（46，31, 82，53，77，70）

D. (46 ，53，31，70，77，82)

33. 将一个长度为n的向量的第i 个元素删除时，需要前移( B )

个元素。

A. i B. n-i C. n+1 D. n-i+1

34. 不带表头的单链表，头指针为head ，判断其是否为空的条件是

( A )

A. head==0 B. head->next==null C. head==head D.

head->next==head

35. 在一个单链表中，已知*q是（*q表示指针q所指的结点，以下

同）*p的前驱结点，在*q之后插入结点*s，正确的操作步骤序列是

( A )。

A) q->next=s; s->next =p B) s->next=p->next; q->next=s;

C) p->nexr=s; s->next=p ; D) p->next=s; s->next=q;

36. 非空循环链表head 的尾结点 *p 满足下列( C )条件

A) head->next==p; B) head==p; C) p->next==head; D)

p->next==0

37. 一个栈的输入序列是a,b,c,d,e ，则可能的出栈序列是( D )。

A. ecdab B) cebda C) daecb D) abcde

38. 设栈s的类型为sqstack ，判定栈空的条件是( C )。

A. s==NULL B) s->top==0 C) ==0 D) ==NULL

39. 深度为5 的二叉树至多有个( B )结点。

A. 12 B. 31 C. 14 D. 15

40. 已知二叉树的后、中根序列分别是bedfca 和 badecf，则该二

叉树的前根遍历序列是( C )。

A) defbca B) fedbca C) abcdef D) fedcba

41. 一个有n个顶点的有向图最多有( B )弧 。

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

42. 具有n个顶点的无向图至少要有( B )条边才有可能是一个连

通图。

A) n(n+1) B) n-1 C) n+1 D) n(n-1)

43. 已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深

度优先遍历序列是( B )。

A) 1 2 3 4 B) 1 4 2 3 C) 1 3 2 4 D) 1 4 3 2

44. 一个向量的第一个元素的地址是100，每个元素的长度是2 ，则

第五个元素的地址是( C )

A) 102 B) 110 C) 108 D) 120

45. 一个循环顺序队列 ,队头、尾指针的值分别为front,rear ，

则队列中元素个数为( A )。（maxlen为循环顺序表的长度）

A. (rear-front+maxlen) % maxlen

B. (rear-front) % maxlen

C. rear-front+1

D. front-rear+1

46. 一个有n个顶点的图最少有( D )条边。

A) n(n+1) B) n(n-1) C) n(n+1)/2 D) 0

47. 具有5个顶点的无向图至少要有( A )条边才能确保是一个连

通图。

A) 4 B) 5 C) 6 D) 7

48. 设栈s的类型为sqstack ，最多可容纳maxlen个元素，则判定

栈满的条件是( B )。

A. s==maxlen-1 B) ==maxlen-1 C) s->top==maxlen-1 D) ==0

49. 一个顺序队列q的类型为sqqueue,队头、尾指针分别为

front,rear，最多可容纳maxlen个元素，则队空的条件是( C )。

A) front==rear B) rear==0 C) == D) rear==maxlen-1

50. 在具有n个结点的有序单链表中插入一个新结点并使链表仍然

有序的时间复杂度是( B )

(1) (n)

(nlogn) (n*n)

51. 链栈与顺序栈相比，比较明显的优点是( D )

A.插入操作更加方便 B.删除操作更加方

便

C.不会出现下溢的情况 D.不会出现上溢的情

况

52. 二叉树中第5层上的结点个数最多为( C )

53. 下列编码中属前缀码的是( A )

A.{1,01,000,001} B.{1,01,011,010}

C.{0,10,110,11} D.{0,1,00,11}

54. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采

用（ B ）

A．深度优先搜索算法 B．广度优先搜索算法

C．求最小生成树的prim算法 D．拓扑排序算法

55. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为

( B )

(1) (logn)

(n) (n logn)

56. 对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，

查找成功的平均查找长度为( C )

A. (n-1)/2 B. n/2

C. (n+1)/2 D. n

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

( D )

和41 和39

和44 和51

58. 关于线性表的说法,下面选项正确的是（ B ）

A 线性表的特点是每个元素都有一个前驱和一个后继

B 线性表是具有n(n>=0)个元素的一个有限序列

C 线性表就是顺序存储的表

D 线性表只能用顺序存储结构实现

59. 表长为n的顺序存储的线性表，当在任何一个位置上插入或者删

除一个元素的概率相等时，删除一个元素需要移动元素的平均个数为

（ A ）

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

60. 设双向循环链表中节点的结构为(data,LLink,RLink)，且不带头

节点。若想在指针p所指节点之后插入指针s所指节点，则应执行下

列哪一个操作（ D ）

A p->RLink=s; s->LLink=p;

p->RLink->LLink=s; s->RLink=p->RLink;

B p->RLink=s; p->RLink->LLink=s;

s->LLink=p; s->RLink=p->RLink;

C s->LLink=p; s->RLink=p->RLink;

p->RLink=s; p->RLink->LLink=s;

D s->LLink=p; s->RLink=p->RLink;

p->RLink->LLink=s; p->RLink=s;

61. 栈和队列都是（ A ）

A 限制存取位置的线性结构

B 链式存储的非线性结构

C 顺序存储的线性结构

D 限制存取位置的非线性结构

62. 单循环链表表示的队列长度为n，若只设头指针，则入队的时间

复杂度为（ A ）

A O(n) B O(1) C O(n*n) D O(n*logn)

63. 一棵含有n个节点的k叉树，可能达到的最小深度为多少（ C ）

A n-k B n-k+1 C |log

k

n|+1 D |log

k

n| 其中|k|表示下取

整

64. 下列序列中( B )不是堆。

A. 12 36 53 68 48 60 75 B. 12 48 53 68 36

60 75

C. 12 48 36 60 75 68 53 D. 12 36 60 53 48

68 75

65. 在下列内排序方法中，( C )的平均时间复杂性是O(nlogn)。

A. 直接插入排序 B. 简单选择排序 C. 快速排序 D.

希尔排序

66. 设顺序栈s非空，则语句段( C )可实现栈s的出栈操作，其

中为栈顶指针，为栈空间，出栈的元素存放在x中。

A. :=+1; B. x:=[];

x:=[]; :=+1;

C. :=; D. x:=[];

x:=[]; :=;

67. 已知L是带头结点的单链表，p指向表中某结点，则要删除p结

点的后继结点应执行操作( A )；要在p结点后插入s结点应执行

操作( D )。

A. pnext:=pnextnext; B. pnextnext:=

.next;

C. pnext:=s; s

snext:=pnext; p

next:=pnext; D.

next:=s;

68. 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上

所经过的结点序列按其关键字有序（ D ）。

A．二叉排序树 B．哈夫曼树 C．AVL树 D．堆

69. 下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并

D. 快速排序

70. 若需在O(nlog

2

n)的时间内完成对数组的排序，且要求排序是稳

定的，则可选择的排序方法是（ C ）。

A. 快速排序 B. 堆排序 C. 归并排序 D.

直接插入排序

二 填空题

1、在单链表L中，指针p所指结点有后继结点的条件是：

p->next!=null

2、表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是：

(请在表达式中用点(.)将数隔开)

23.12.3*2-4/*7/+++

3、有一个100*90的稀疏矩阵，非0元素有9个，设每个整型数占2

字节，则用三元组表示该矩阵时，所需的字节数是

60

4、深度为9的完全二叉树具有的 个结点

256

5、已知二叉树后序为DGEBFCA，中序为DBGEACF，则前序一定是

ABDEGCF

6、先根遍历树林正好等同于按__ _遍历对应的二叉树.

先序

7、构造n个结点的强连通图，至少有_______条弧。

n

8、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，

所比较的元素下标依次为

6,9,11,12

9、在单链表指针为p的结点之后插入指针为s的结点的操作是：

s->next=p->next;p->next=s;

10、有N个顶点的有向图，至少需要量_______条弧才能保证是连通

的。

N-1

11、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折

半）法查找关键码值12，需做的关键码比较次数为

4

13、下面是一个无向图的邻接矩阵，试将有关数据填入本题的空白处

（顶点号由1开始）

0 1 0 1 1

1 0 1 0 0

0 1 0 1 0

1 0 1 0 1

1 0 0 1 0

该图的顶点数为 该图的边数为 顶点3的度

为 。

5 6 2

14、后根遍历树林正好等同于按__(6) _遍历对应的二叉树。

中序

15、n个结点的完全有向图含有边的数目__(7)

n*（n－l）

16、当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被

称为算法的________。

时间复杂度

17、假设S和X分别表示进栈和出栈操作，由输入序列“ABC”得到

输出序列“BCA”的操作序列为SSXSXX，则由“a*b+c/d”得到“ab*cd/+”

的操作序列为___________。

SXSSXXSSXSSXXX

18、在一棵度为3的树中，度为2的结点个数是1，度为0的结点个

数是6，则度为3的结点个数是________。

2

19、如图所示的有向无环图可以排出________种不同的拓扑序列。

12

20、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根

堆为(____ ____)。

75, 66, 48, 29, 31, 37

21、对长度为20的有序表进行二分查找的判定树的高度为________。

5

22、n个顶点的连通无向图，其边的条数至少为

________________________。

n-1

23、排序(sorting)有哪几种方法_______________，_____________，

____________，_____________，____________。

直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排

序，堆排序等

24、下面程序段的时间复杂度为______________。（用O估计）

FOR i:=1 TO n DO

FOR j:=i TO n DO

s=s+j;

O（n*n）

25、非线性结构包括______________和_________________。

树，图

26、在线性表的___________存储结构上进行插入或删除操作要移动

元素。

顺序存储结构

27、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队

尾指针分别是front

和rear，且队头指针所指的单元闲置，则队满的条件是

______________________________

_____________________________。

Front=rear, rear+1=front

28、下面表达式树所对应的表达式的前缀表达式是

，队空的条件是

_____________________________

____________________________。

+*a-bc/de , abc-*de/+

，后缀表达式是

29、在AOE-网中，设e(i)和l(i)分别表示活动

a

i

的最早开始时间和

最晚开始时间，则当且仅当_________________时，

a

i

为关键活动。

e(i)==l(i)

30．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图

_________________。下面有向图的一个拓扑有序序列是

______________________________。

存在回路，8

31、二叉排序树的特点是其 序列是有序的。

中序遍历