《数据结构》试题汇编(带答案)

《数据结构》习题汇编

一、单项选择题

1. 在数据结构中，从逻辑上可以把数据结构分成（ ）。

A. 动态结构和静态结构 C. 线性结构和非线性结构

2. 数据结构在计算机内存中的表示是指（ ）。

A. 数据的存储结构 C. 数据的逻辑结构

3. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。

A. 逻辑

4. 计算机算法指的是（ ① ），它必须具备输入、输出和（ ② ）等5个特性。

①A. 计算方法

B. 排序方法 D. 调度方法

B. 可行性、确定性和有穷性 D. 易读性、稳定性和安全性

C. 解决问题的有限运算序列 C. 确定性、有穷性和稳定性

5. 在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后

移（ ）个元素。

A. n-i

6. 在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需要从前向后依次前移（ ）个元素。

A. n-i

7. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。

A. O(n)

8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。

A. O(n)

9. 不带头结点的单链表first为空的判定条件是：（ ）

A. first == NULL;

B. first->next == NULL; D. first != NULL;

C. first->next == first;

B. O(n/2)

C. O(1)

D. O(n2)

B. O(1)

C. O(n2)

D. O(log2n)

B. n-i+1

C. n-i-1

D. i

B. n-i+1

C. n-i-1

D. i

B. 存储

C. 逻辑和存储

D. 物理

B. 数据结构

D. 数据元素之间的关系

B. 紧凑结构和非紧凑结构 D. 内部结构和外部结构

②A. 可行性、可移植性和可扩充性

10. 带头结点的单链表first为空的判定条件是：（ ）

A. first == NULL;

B. first->next == NULL; D. first != NULL;

C. first->next == first;

11. 设单链表中结点的结构为（data, next）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，

则应执行下列哪一个操作？（ ）

A. s->next = p; p->next = s; C. s->next = p->next; p = s;

1

B. p->next = s; s->next = p; D. s->next = p->next; p->next = s;

12. 设单链表中结点的结构为（data, next）。若想摘除结点*p(*p既不是第一个也不是最后一个结点)

的直接后继，则应执行下列哪一个操作？（ ）

A. p->next = p->next->next; B. p = p->next; p->next = p->next->next; C. p->next = p->next;

D. p = p->next->next;

13. 非空的循环单链表first的尾结点（由p所指向）满足：（ ）

A. p->next == NULL;

B. p == NULL; D. p == first;

C. p->next == first;

14. 若让元素1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。

A. 3, 2, 1

15. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。

A. n-2

16. 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。

A. 队头指针加一

17. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。

A. front+1 == rear C. front == 0

18. 树中所有结点的度等于所有结点数加（ ）。

A. 0

19. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。

A. 2

20. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。

A. n

21. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第1层，i大于等于1而小于等于树的高度），

最多具有（ ）个结点。

A. 2i

22. 在一棵高度为h（假定根结点的层号为1）的完全二叉树中，所含结点个数不小于（ ）。

A. 2h-1

23. 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。假定空树的高度为0。

A. 5

24. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。假定树根结点的编号为1。

A. ?(n-1)/2?

2

B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2

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

B. 队头指针减一

D. 取出队尾指针所指的元素

C. 取出队头指针所指的元素

B. rear+1 == front D. front == rear

B. 1 C. -1 D. 2

B. 1 C. 0 D. -1

B. n-1 C. n+1 D. 2*n

B. 2i+1

C. 2i-1

D. 2n

B. 2h+1

C. 2h-1

D. 2h

B. 6 C. 7 D. 8

B. ?n/2? C. ?n/2? D. ?n/2? -1

25. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（ ）。假定根结点

的编号为1

A. 2i

26. 在一棵完全二叉树中，假定根结点的编号为1，则对于编号为i（i＞1）的结点，其双亲结点的编号为

（ ）。

A. ?(i+1)/2?

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

A. n-1

28. n个顶点的连通图至少有（ ）条边。

A. n-1

B. n

C. n+1

D. 0

29. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。

A. 3

30. 图的深度优先搜索类似于树的（ ）次序遍历。

A. 先根 A. 先根

32. n (n＞1) 个顶点的强连通图中至少含有（ ）条有向边。

A. n-1

33. 具有n个顶点的有向无环图最多可包含（ ）条有向边。

A. n-1

34. 一个有n个顶点和n条边的无向图一定是（ ）。

A. 连通的

35. 在n个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。

A. n

36. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（ ）。

A. 栈

37. 若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为（ ）。

A. n

38. 对长度为10的顺序表进行搜索(从表头开始搜索)，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ）。

A. 5.5

3

B. 2i-1 C. 2i+1 D. 2i+2

B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1

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

B. 2 C. 1 D. 1/2

B. 中根 C. 后根 D. 层次

31. 图的广度优先搜索类似于树的（ ）次序遍历。

B. 中根

C. 后根

D. 层次

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

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

B. 不连通的 C. 无环的 D. 有环的

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

B. 队列 C. 二叉树 D. 树

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

B. 5 C. 39/8 D. 19/4

39. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的

向上取整。

A. log2(n+1)

B. log2n

C. n/2

D. (n+1)/2

40. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的

向下取整加一。

A. log2(n+1)

41. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）

的值除以9。

A. 20

42. 对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（ ）。

A. 3

43. 对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（ ）。

A. O(n)

44. 对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较？

A. 8

45. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？

A. 起泡排序

46. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最慢结束？

A. 起泡排序

二、填空题

1. 算法的五个重要特性是 有穷性 、确定性、可行性、输入和输出。

2. 设单链表中结点的结构为（data, next）。若想摘除结点*p本身，则应执行操作：

q=p->next; p->data=q->data; p->next=q->next ; free(q) ;

3. 设循环队列Q的队头和队尾指针分别为front和rear，队列的最大容量为MaxSize，且规定判断队

空的条件为Q.front == Q.rear，则判断队满的条件为 (Q.rear+1)%MaxSize==Q.front ，而计算队列长度的表达式为(Q.rear-Q.front+MaxSize)%MaxSize 。

4. 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3,

s4, s6, s5, s1，则顺序栈的容量至少应为 3 。

5. 如果进栈序列是1, 2, 3, 4, 5, 6, 7, 8。则可能的出栈序列有 1430 种。

6. 用简单的模式匹配算法在主串\中检索子串”aab”，则总的比较次数为

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

B. 18 C. 25 D. 22

B. 4 C. 5 D. 6

B. O(n2)

C. O(1) D. O(log2n)

B. 10 C. 15 D. 25

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

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

15 。

4

7. 用简单的模式匹配算法在主串\中检索子串”string”，总的比较次数为 12 。

8. 假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为

为1。

9. 在一棵高度为3的四叉树中，最多含有 21 结点。

10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度

为0的结点数有 6 个。

11. 一棵高度为5的完全二叉树中，最多包含有 31个结点。假定根结点的高度为1。

12. 在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，则叶结点数

为 6个。

13. 假定一棵二叉树的结点个数为18，则它的最小高度为

14. 按照二叉树的定义，具有5个结点的二叉树有

5 。假定根结点的高度为1。

5 。假定根结点的高度

42 种形态。

15. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为 O(n) 。

16. 对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi，搜索长度（即在搜索过程中依次

同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为

n 。

ASL?pici i?1?17. 假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长

度为 20.5 。

18. 以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为

O(log2n) 。

3 。

19. 从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为

20. 假定对长度n = 50的有序表进行折半搜索，则对应的判定树中最后一层的结点数为 19 个。

21. 直接插入排序在最好情况下的比较次数为 ，最坏情况下为

（正序最好C=n-1，逆序最坏C=n*(n-1)/2）

22. 直接插入排序在最好情况下的移动次数为

（最好M=0，最坏M=(n+4)*(n-1)/2）

23. 简单选择法排序时比较数据的次数为

，最坏情况下为

。

。

。（任何情况下C=n*(n-1)/2）

。

24. 简单选择法排序在最好情况下的移动次数为 ，最坏情况下为

（最好正序M=0，最坏（非逆序，如6,1,2,3,4,5）M=3*(n-1)）

5

25. 起泡排序在最好情况下的比较次数为 ，最坏情况下为

。

（最好正序C=n-1，最坏逆序C=n*(n-1)/2）

26. 起泡排序在最好情况下的移动次数为 ，最坏情况下为

。

（最好正序M=0，最坏（逆序）M=3*n*(n-1)/2）

27. 在直接选择排序中，排序码比较次数的时间复杂度为O( n^2 )。

28. 在直接选择排序中，数据对象移动次数的时间复杂度为O( n )。

29. 快速排序在平均情况下的时间复杂度为O( nlog2n )。

30. 快速排序在最坏情况下的时间复杂度为O( n2 )。

三、简答题

1. 下面程序段的时间复杂度是 O(n*m) 。

for(i=0;i

2. 下面程序段的时间复杂度是 O(n^0.5) 。

i=s=0; while(s

3. 下面程序段的时间复杂度是O(n^2) 。

s=0;

for(i=0;i

4. 下面程序段的时间复杂度是O(log3n) 。

i=1; while(i<=n) i=i*3;

5. 写出下列程序段的输出结果: 514263 。

void main( ) {

SqStack S; SqQueue Q; int i,j,n=6,e; for(i=1;i<=n;++i)Push(&S,i); for(i=1;i<=n;++i){

Pop(&S,&e); EnQueue(&Q,e); DeQueue(&Q,&e); EnQueue(&Q,e); } for(i=1;i<=n;++i){ DeQueue(&Q,&e); Push(&S,e); } for(i=1;i<=n;++i){ Pop(&S,&e); printf(\}

6

6. 已知一棵二叉树的前序和中序序列，画图并求该二叉树的后序序列。

前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列：

7. 已知一棵二叉树的中序和后序序列如下，画图并求该二叉树的前序序列。

中序序列：c, b, d, e, a, g, i, h, j, f 后序序列：c, e, d, b, i, j, h, g, f, a 前序序列：

8. 有7个带权结点，其权值分别为3, 7, 8, 2, 6, 10, 14，试以它们为叶结点生成一棵赫夫曼树，

求出该树的带权路径长度：

9. 设连通图G如图所示。试给出对它执行从顶点V0开始的广度优先遍历和深度优先遍历的结果。

广度优先遍历：012345678 深度优先遍历：013256784

V0 V2 V5 V3 V8 V6 V1 V4

V7 10. 设有一个连通网络如图所示。试采用prim算法从顶点0开始构造最小生成树。（写出加入生成树顶点

集合S和选择边Edge的顺序） 0 9 10 边(顶点，顶点，权值) 顶点集合 7 0 1 2 ( 0 ， 1 ， 9 ) 5 7 6 01 ( 1 ， 3 ， 5 ) 11 8 3 4 5 013 ( 1 ， 2 ， 7 ) 0132 01324 013245

11. 设带权有向图如图所示。试采用Dijkstra算法求从顶点0到其他各顶点的最短路径和最短路径长度。 8 顶点号 1 3 2 4

( 2 ， 4 ， 6 ) ( 2 ， 5 ， 7 ) 路径长度 4 7 8 10 路径 01 03 012 0124 0 4 1 7 9 3 5 2 2 4 1 4 7

12. 试对下图所示的AOE网络 2 (1) 这个工程最早可能在什么时间结束。

1 4 (2) 确定哪些活动是关键活动。画出由所有关键活动构15 成的图，指出哪些活动加速可使整个工程提前完成。 3 拓扑序列132456

每个顶点的最早发生时间、最迟发生时间：

1(0,0),3(15,15),2(19,19),4(29,37),5(38,38),6(43,43)

2 10 19 4 6 6 11 5 5 工期：43天

每个活动的最早开始时间、最迟开始时间：

1-2(0,17),1-3(0,0),3-2(15,15),3-5(15,27),2-5(19,19),2-4(19,27) 5-6(38,38),4-6(29,37)

13. 一个一维数组a[10]中存储着一个有序表，该有序表为：(15, 26, 34, 39, 45, 56, 58, 63, 74,

76 )，画出折半搜索所对应的判定树，并求出在等概率情况下搜索成功的平均搜索长度。 平均搜索长度： 2.9

14. 给定一组数据对象的排序码为 {46, 79, 56, 38, 40, 84}，对其进行一趟快速排序，

结果为 40,38,46,56,79,84 。

四、算法设计题

1. 设有一个顺序表 (e0, e1, …, en-2, en-1)。请编写一个函数将这个顺序表原地逆置，即顺序表的内

容置换为 (en-1, en-2, …, e1, e0)。 void Reverse(SqList *L){ int i=0,j=L->length-1; ElemType t;

for(;ielem[i]; L->elem[i]=L->elem[j]; L->elem[j]=t; } }

2. 试编写一个函数，用以删除顺序表L中所有值为x的元素（要求就地工作）。 void DeleteX(SqList *L, ElemType x){ int j=0;

for(i=0;ilength;++i){ if(L->elem[i]!=x){

if(i>j) L->elem[j]=L->elem[i]; ++j; } }

L->length =j; }

8

3. 试编写一个函数，在数组R（已正序排列）中进行折半查找某个值k，找到则返回其位置，否则返回0。 int SearchBin(int R[], int n, int k){ //有序（正序）的顺序表的二分查找，n为数组元素个数，k为待查找的值 int low=0,high=n-1,mid; while(low<=high){ mid=(low+high)/2;

if(R[mid]==k)return mid+1; else if(R[mid]>k) high=mid-1; else low=mid+1; }

return 0;

}

4. 试编写一个函数，对数组r进行选择法排序（结果为正序）。 void SelectSort(ElemType r[],int n){ //对顺序表r作简单选择排序，n为数组元素个数 int i,j,k; ElemType tmp;

for(i=0;i

for(j=i+1;j

tmp=r[i]; r[i]=r[k]; r[k]=tmp; }

}

}

9

本文来源：https://www.bwwdw.com/article/fz9.html