《数据结构》课程习题集
一、单选题
1. 头结点为L的单循环链表为空的条件是（ ）
A、L==NULL B、L->next==NULL C、L->next==L D、L!==NULL
2. 与线性表的链式存储结构特点不符的是：（ ）
A、便于插入、删除运算 C、需要连续的地址空间 A、先序遍历 C、后序遍历
B、查找操作费时 D、空间动态分配
3. 采用邻接表存储的图，其深度优先遍历算法类似于二叉树的（ ）
B、中序遍历 D、按层遍历
4. 对序列{1,5,7,10,12,15,19}，采用折半查找1，需比较（ ）次。
A、1 B、2 C、3 D、4
5. 直接选择排序算法的时间复杂度为（ ）
A、O（n） B、O（n） C、 O（n*log（n）） D、 O（1）
2
6. 一个栈的入栈序列为1、2、3、4，则栈的不可能的输出序列是（ ）
A、1 2 3 4 B、 4 3 2 1 C、4 1 2 3 D、 3 4 2 1
7. 判定一个顺序栈S为空的条件为（ ）。
A、S.top=0 B、S.base=0
C、S.top=S.base D、S.top>S.stacksize
8. 设有两个串r和t，求r在t中首次出现位置的运算称作（ ）
A、求串长 B、连接 C、模式匹配 D、求子串
9. 按二叉树的定义，具有3个结点的二叉树共有（ ）种形态。
A、3 C、5
B、4 D、6
10. 一个有n个顶点的完全无向图共有（ ）条边。
A、n C、n*(n-1) A、1 C、3
B、2n
D、n*(n-1)/2
B、2 D、4
11. 对序列{5，7，12，19，20，30}，采用折半查找19，需比较（ ）次。
12. 直接插入排序算法的时间复杂度为：（ ）
第 1 页 共 21 页
A、O（n2） C、O（n*log（n）） 移（ ）个元素。 A、n-i C、n-i-1 （ ）。 A、 行号 C、 元素值 A、后一个 C、当前
B、O（n） D、O（1）
13. 在一个长度为n的顺序表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前
B、n-i+1 D、i
14. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的
B、 列号 D、 地址
15. 在一个循环顺序队列中，队头指针指向队头元素（ ）位置。
B、前一个 D、后面
B、front!=NULL D、front==NULL B、 O(1)
2
D、 O(n) B、 O(log2n ) D、 O(nlog2n) B、数据元素 D、数据结构 B、队列 D、树
B、部分地址必须是连续的 D、连续与否均可以
16. 假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是（ ）。
A、front==rear C、rear!=NULL A、 O(n)
n
C、 O(log2) A、 O(1) C、 O(n)
17. 从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
18. 向二叉搜索树中插入一个元素时，其时间复杂度大致为（ ）。
19. （ ）是数据的基本单位。
A、数据项 C、数据对象 A、堆栈 C、线性表
20. 以下不属于线性结构的是（ ）
21. 线性表采用链式存储时，其地址（ ）
A、必须是连续的 C、一定是不连续的 A、线性表 C、队列
22. 下面的不属于线性结构的有（ ）
B、栈
D、二叉树 B、C，B，A D、C，A，B
B、11
第 2 页 共 21 页
23. 设一个栈的输入序列为A，B，C，则借助一个栈所得的输出序列不可能是（ ）
A、A，B，C C、A，C，B A、9
24. 若一棵二叉树具有10个叶结点，则该二叉树的度为2的结点个数是（ ）
C、12
D、不确定
B、head->next=NULL D、head!=NULL
25. 不带头结点的单链表head为空的判定条件是（ ）
A、head=NULL C、head->next=head A、5 C、7 A、13 C、26
26. 具有6个顶点的无向图，至少要有（ ）条边，才能确保是一个连通图
B、6 D、8 B、12 D、25
27. 设有13个叶子结点，用它们组成一颗哈夫曼树，则该哈夫曼树共有（ ）个结点。
28. 在下列存储形式中，（ ）不是树的存储结构。
A、双亲表示法 B、孩子表示法
C、孩子兄弟表示法 D、顺序存储表示法
29. 在以HL为头结点的单链表中，若要向表头插入一个由指针P指向的结点，则执行
（ ）。
A、HL=P;P->next=HL C、P->next=HL ;HL=P
B、P->next=HL;HL->next=P
D、P->next=HL->next; HL->next=P
B、插入删除不需要移动元素
D、所需空间与线性表长度成正比
30. 链表不具有的特点是（ ）。
A、可随机访问任一元素 C、不必事先估计存储空间 A、1/2 C、2
31. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。
B、1 D、4
32. 对线性表进行二分查找时，要求线性表必须（ ）。
A、以顺序方式存储 B、以链接方式存储
C、以顺序方式存储，且结点按关键字有序排列 D、以链接方式存储，且结点按关键字有序排列
33. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是（ ）。
A、插入排序 C、快速排序
B、选择排序 D、归并排序
34. 下描述中正确的是( )
A、线性表的顺序存储结构优于链表存储结构 B、对栈的插入和删除元素的操作都可在栈底进行 C、栈的操作方式是先进先出 D、队列的操作方式是先进先出
35. 在一个单链表中，若删除*p 所指结点的后续结点，则执行( )
A、s=p->next;p->next=s->next; free(s) B、p=p->next; p->next=p->next->next
第 3 页 共 21 页
C、p->next=p->next D、p=p->next->next
36. 栈的插入和删除操作在（ ）进行。
A、栈顶 C、任意位置 A、247 C、249 A、n -1 C、n+1
B、栈底 D、指定位置 B、248 D、250
37. 一颗有124个叶子结点的完全二叉树，最多有（ ）个结点。
38. n个顶点的连通图至少有（ ）条边。
B、n D、0
39. 衡量查找算法效率的主要标准是（ ）。
A、元素个数 B、所需的存储量 C、平均查找长度 D、算法难易程度
40. 计算机算法指的是( )
A、计算方法 B、排序方法 C、解决问题的有限操作序列 D、调度方法
41. 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的有序序列。
A、前序 C、后序
B、中序 D、按层次
42. 顺序查找法适合于存储结构为（ ）的线性表。
A、散列存储 B、 顺序存储或链式存储 C、压缩存储 D、索引存储
43. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素
进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。 A、希尔排序 B、起泡排序 C、插入排序 D、选择排序
44. 计算机算法它必具备输入、输出和( )等五个特性。
A、可行性、可移植性和可扩充性 C、确定性、有穷性和稳定性
B、可行性、确定性和有穷性 D、易读性、稳定性和安全性
45. 假设队列的对头指示器为front，队尾指示器尾rear，队列的最大存储空间大小为
max，则顺序循环队列为空的标志是（ ）。
A、 rear==front B、rear!=front
C、rear=(front+1)%max D、front=(rear+1)%max
46. 在有n个叶子结点的哈夫曼树中，总的结点个数是（ ）。
A、n B、2n-1 C、2n+1 D、2n
47. 栈和队列的共同点是( )。
A、都是先进后出
B、只允许在端点处插入和删除
第 4 页 共 21 页
C、没有共同点 D、都是后进先出
48. 串是一种特殊的线性表，其特殊性体现在( )。
A、可以顺序存储 B、数据元素是字符
C、可以链接存储 D、数据元素可以是多个字符
49. 就平均性能而言，目前最好的内排序方法是( )排序法。
A、冒泡 C、交换
B、希尔 D、快速
50. N个结点的二叉树中，用二叉链表存储，非空指针数目为（ ）。
A、N B、2N C、N-1 D、N+1
二、简答题
51. 设散列表的长度m = 13，散列函数H（ K ）= K mod m，给定的关键码序列为19，
14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度。
52. 已知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入
生成的一棵二叉搜索树。
53. 请分别画出具有三个结点的树和二叉树的所有形态。
54. 用直接选择排序方法对下列关键字进行排序，请写出每一趟排序的结果。
55. 已知有序序列{3,12,24,37,45,53,61,78,90,100},请用二分查找法查找 元素37,并
写出每次查找比较的过程,用”↑”标示 查找过程的mid元素,分别用”[” 和 ”]”标示low和high元素。
56. 已知序列{17,18,60,40,7,32,73,65,85},请给出分别构建大根堆和小根堆后的顺序
序列.
57. 已知一组关键字为（Dec,Feb,Nov,Oct,June,Sept,Aug,Apr,May,July,Jan,Mar）,按
哈希函数H(key)= key mod 12和链地址法处理冲突构造长度为12的哈希表，并求平均查找长度。
58. 有七个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈
夫曼树，并计算出带权路径长度WPL。
59. 已知二元组C=（D，S），其中：D={1，2，3，4，5}， S={（1，2）、（1，3）、（2，4）、
（3，4）、（2，5）、（3，5）}（1，2）表示元素1和2之间有一条连接线，画出其逻辑图表示，并指出其属于何种数据结构。
60. 画出如下所示的有向图的邻接表。
第 5 页 共 21 页
61. 画出树的孩子兄弟表示法存储结构（每结点三个域）。
62. 已知序列{19，20，80，55，7，35，90，88，66}，给出采用起泡排序按升序排序时
每一趟的示意图。
63. 无向图进行如下操作：
（1）画出其邻接矩阵；
（2）根据普里姆算法求最小生成树。
64. 对于下图：
（1）写出从顶点0出发按度优先搜索遍历得到的顶点序列； （2）写出从顶点0出发按广度优先搜索遍历得到的顶点序列； （3）结点2的度是多少？ （4）画出其邻接矩阵。
第 6 页 共 21 页
65. 如下图所示的树,回答以下问题:
（1）该树的深度是 ； （2）该树的度是 ；
（3）该树的叶子结点有哪些 。
66. 由如图所示的二叉树,回答以下问题:
这棵二叉树的先序,中序和后序遍历序列分别是 , 和 。
67. 如下图所示,回答下列问题:
(1) 结点3的度为 。
(2) 给出该图的一个拓扑有序序列
。
68. 对于下图，分别画出用克鲁斯卡尔(Kruskal)算法构造最小生成树的过程。
第 7 页 共 21 页
69. 设数据元素关键字序列为{75，37，81，19，82，74，50，26，15，06}，分别写出采
用下列排序算法排序的第一趟排序结果。 （1）希尔排序（d=5）; （2）直接选择排序 （3）快速排序 （4）二路归并排序
70. 知一组关键字为（46,88,45,39,70,58,44,12,27,66），地址空间为0至12 按哈希函数
H(key)= key ％ 11。
（1）用开放地址法线性探测处理冲突构造该哈希表。 （2）求出等概率情况下查找成功的平均查找长度。 0 1 2 3 4 5 6 7 8 9 10 11 12
三、算法设计题
71. 有一个带头结点的单链表Head，在其数据域为a的结点后加入新元素一个新的结点s
（s为指向新插入结点的指针）。设计一个算法实现上述功能。
72. 顺序循环队列类型模块说明如下：
#define Max 100 //最大队列长度 Typedef struct{
QElemType *base; //初始化的动态分配存储空间 int front，rear; //头指针和尾指针 }SeQueue;
第 8 页 共 21 页
填写画线部分空白处，完成下列入队列函数。 Status EnQueue(SqQueue &Q,QElemType e) {
if( ) //队列满 return Error ; ; return OK; }
73. 针对带头结点的单链表，试编写统计函数count，统计单链表中给定值x的所有元素
个数。假设已经对单链表进行了结构体定义，数据域为data，指针域为next，头结点为head。
74. 阅读下面的算法,补上空格处的语句。
typedef struct {
Elemtype *elem; //数据元素存储空间基址,建表时按实际长度分配,0号单元留空 int length; //表长度
}SSTable; //静态查找表的顺序存储结构
int Search_Bin(SSTable St,KeyType key){//关键字从小到大排好 low=1;high=St.length; while(low<=high){ mid=(low+high)/2;
if EQ(key,St.elem[mid].key) return ;
else if LT(key,St.elem[mid.key]) ; // LT 表示第一个参数值比第二个小 else ; }
return 0; }//Search_Bin
75. 编写算法实现用递归方法对a[low]--a[high]进行快速排序。
四、 填空题
76. 一个对象序列的关键码为{ 46，79，56，38，40，84 }, 采用快速排序以位于最左位
置的对象为基准而得到的第一次划分结果为( )。
77. 设有一个10阶的对称矩阵Ａ[10][10]，采用压缩存储方式按行将矩阵中下三角部分
的元素存入一维数组Ｂ[ ]中，Ａ[0][0]存入Ｂ[0]中，则Ａ[8][5]在Ｂ[ ]中的位置是( )。
78. 具有65个结点的完全二叉树的高度为（） 。
79. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。 80. 数据元素从逻辑上分为线性结构和（ ）结构。
第 9 页 共 21 页
81. 将插入限定在表的一端，而删除限定在表的另一端进行的线性表是（ ） 。 82. 若规定空二叉树的深度为-1，则深度为k的二叉树的最大结点数是（ ）个。 83. 存储数据时，不仅要存储数据的值，还要存储元素之间的（ ）。 84. N个顶点的有向完全图具有（ ）条弧。 85. ( )是数据的基本单位。
86. 数据结构被形式的定义为(D,S)，其中D是（ ）的有限集合，S是D上关系的有限集
合。
87. 深度为3的二叉树至少有（ ）个结点。
88. 若二叉树中不含有度为1的结点，那么此二叉树中度为2的结点数n2与度为0的结
点数n0之间满足（ ）关系式。
89. 已知一棵二叉树中序遍历和后序遍历结果都是cba,它的先序遍历结果是（ ） 。 90. 两个串相等的充分必要条件是（ ）。
91. 对于长度为N的线性表进行顺序查找，则时间复杂度为（ ）。 92. 对于长度为N的线性表采用二分查找，则时间复杂度为（ ）。 93. 一棵有k层的满二叉树一共有（ ）个结点。（根结点为第1层） 94. 在一棵二叉树中，第5层上的结点数最多为（ ）。
95. 对序列（10，5，17，5*，1，9）排序时，若采用稳定的排序算法递增排序，其结果
为（ ）。
96. 有n个元素的数组a, Loc（a0）是a0的存储地址，每个元素需占用L个存储单元，
则第i个元素的存储地址为（ ）。
97. 采用哈希存储方法时，用于计算结点存储地址的是（ ）。
98. 在排序过程中，任何情况下都不比较关键字大小的排序算法是（ ）。
99. 有一组序列｛48，36，68，99，75，24，28，52｝进行快速排序，要求结果从小到大
排列，则进行一趟快速排序的结果是（ ）。
100. 若以｛4，5，6，7，8｝作为叶子结点的权值构造哈夫曼树，则其带权路径长度是（ ）。 五、判断题 （略）……
答案
一、单选题
第 10 页 共 21 页
1. C 2. C 3. A 4. C 5. B 6. C 7. A 8. C 9. C 10. D 11. C 12. A 13. A 14. A 15. B 16. A 17. C 18. B 19. B 20. D 21. D 22. D 23. D 24. A 25. A 26. A 27. D 28. D 29. D 30. A 31. B 32. C 33. A 34. D 35. A 36. A 37. B 38. A 39. C
第 11 页 共 21 页
40. C 41. B 42. B 43. C 44. B 45. A 46. B 47. B 48. B 49. D 50. D
二、简答题
51. 设散列表的长度m = 13 ；散列函数为H（ K ）= K mod m ,给定的关键码序列为19，
14，23，01，68，20，84，27，55，11，则有 H（19）= 6，成功；H（14）= 1，成功；H（23）= 10，成功；H（01）= 1 ，冲突， = 2 ，成功； H（68）=3，成功；H（20）= 7，成功；H（84）= 6，冲突， = 7, 冲突， = 8成功；H（27）=1，冲突， = 2 ，冲突， = 3 ，冲突， =4 ，成功；H（55）= 3 ，冲突， = 4 ，冲突， = 5 ，成功；H（11）= 11，成功； 0 1 2 3 4 5 6 7 8 9 10 11 12 14 01 68 27 55 19 20 84 23 11 在等概率的情况下，搜索成功时的平均搜索长度:ASLSUCC = 18/10 = 1.8 52.
第 12 页 共 21 页
53.
54. 初态： [68 45 20 90 15 10 50]
第一趟：10 [45 20 90 15 68 50] 第二趟：10 15 [20 90 45 68 50] 第三趟：10 15 20 [90 45 68 50] 第四趟：10 15 20 45[ 90 68 50] 第五趟：10 15 20 45 50 [68 90] 第六趟：10 15 20 45 50 68 [90] 第七趟：10 15 20 45 50 68 90
55. 原始:[3
12 24
37 45 53 ↑low ↑mid 第一次后[3 12 24 37] 45 53 ↑low ↑mid ↑high 第二次后3 12 [24 37] 45 53 ↑low ↑high 第三次后3 12 24 [37] 45 ↑low ↑high ↑mid 经过3次比较后，找到了元素37
56. 大根堆序列: 85，65，73，40，7，32，60，18，17
小根堆序列：7，17，32，40，18，60，73，65，85
57.
第 13 页 共 21 页
61 78 61 78 61 78 53 61
90 100] ↑high 90 100 90 100 78 90 100
ASL=(7*1+2*2+3*2+4*1)/12=21/12=7/4
第 14 页 共 21 页
58.
WPL=10×2+2×4＋3×4＋6×3＋14×2＋7×3＋8×3＝131
59.
图型数据结构
60.
第 15 页 共 21 页
61.
62. 初始 第一趟 第二趟 第三趟 第四趟 第五趟
19 19 19 19 7 结束 20 20 20 7 19 80 55 7 20 20 55 7 35 35 35 7 35 55 55 55 35 80 80 66 66 90 88 66 80 88 66 88 66 90
63. （1）邻接矩阵如下：
0 12 ∞
5 ∞
a
12 0 8 ∞ 10
b
∞ 8 0 ∞ ∞
c
5 ∞ ∞ 0 6
d
∞ 10 ∞ 6 0
e
∞ ∞ 3 ∞ 11
f
（2）最小生成树如下：
64. （1）0 1 4 2 5 3
（2）0 1 2 3 4 5 （3）3 （4）
0 1 1 1 1 0 1 0 0 0 1 0 1 0 0 0 1 1 第 16 页 共 21 页
1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 1 1 0
∞ ∞ 3 ∞ 11 0
65. （1）4，
（2）4， （3） C F G L I M K
66. abdgce dgbaec gdbeca 67. （1）3
（2）2 5 4 3 6 1
第 17 页 共 21 页
68.
69. （1）{75，37，81，19，82，74，50，26，15，06}
（2）{06，37，81，19，82，74，50，26，15，75 } （3）{75，37，81，19，82，74，50，26，15，06} （4）{75，37，81，19，82，74，50，26，15，06}
第 18 页 共 21 页
70.
88 45 46 58 70 44 39 12 27 66 0 1 2 3 4 5 6 7 8 9 10 11 12 ASL=(1*6+1*6+1*7+1*4+1*10)/10=33/10=3.3
三、算法设计题
71. void insert( ListNode *Head, int item)
{
ListNode *p; p=Head->next;
while(p!=Null&&p->data!=a) p=p->next; if(p==Null) printf(”不存在结点a”); else
{
s->next=p->next; p->next=s; }
}
72. （1）（Q.rear+1）%Max= =Q.front;
（2）Q.base[Q.rear=e;
（3）Q.rear=(Q.reaar+1)%Max
73. int count(struct node *head,char x)
{
int counter=0; if(head==NULL) return 0;
while(head!=NULL) {
if(head->data==x) counter++;
head=head->next; }
return counter; }
74. （1）return 1
第 19 页 共 21 页
（2）high=mid-1 （3）low=mid+1
75. void QuickSort(DataType a[],int low,int high)
{
int i =low,j = high; Datatype temp=a[low]; while(i while(i //从数组的左端扫描 while(i a[i]=temp; //对子对象数组进行递归快速排序 if(low 四、 填空题 76. 40,38,46,56,79,84 77. 41 78. 6 第 20 页 共 21 页 79. 2 80. 非线性 81. 队列 82. 2k+1-1 83. 关系 84. N(N-1) 85. 数据元素 86. 数据元素 87. 3 88. n0=n2+1 89. abc 90. 串长度和对应元素相等 91. （n+1）/2 92. log2（n+1） 93. 2k-1 94. 16 95. （1，5，5*，9，10，17 ） 96. Loc（a0）+i*L 97. 哈希函数 98. 基数排序 99. 28，36，24，48，75，99，68，52 100. 69 五、判断题 （略）…… 第 21 页 共 21 页 因篇幅问题不能全部显示，请点此查看更多更全内容