数据结构练习题
第一部分 绪 论
一、单选题
一个数组元素 a[i] 与________的表示等价。
A 、 *(a+i) B 、 a+i C 、 *a+i D 、 &a+i
对于两个函数，若函数名相同，但只是____________ 不同则不是重载函数。
A 、 参数类型 B 、 参数个数 C 、 函数类型
3. 若需要利用形参直接访问实参，则应把形参变量说明为 ________参数
A 、 指针 B 、 引用 C 、 值
下面程序段的时间复杂度为 ____________。
for(int i=0; i<m; i++)
for(int j=0; j<n; j++)
a[i][j]=i*j;
2
2
、 O(m*n)D
、 O(m+n)
A、 O(m )B
、 O(n )C
执行下面程序段时，执行 S 语句的次数为 ____________ 。
for(int i=1; i<=n; i++)
for(int j=1; j<=i; j++)
S;
A 、 n 2 B 、 n 2/2 C 、 n(n+1) D 、 n(n+1)/2
下面算法的时间复杂度为 ____________。
int
f( unsigned int
n ) {
if ( n==0 || n==1 ) return
1; else
return
n*f(n-1);
}
A
、 O(1)
B
、 O(n)
C
2
D
、 O(n!)
、 O(n )
二、填空题
数据的逻辑结构被分为 __________ 、 _________、__________ 和 __________ 四种。
数据的存储结构被分为 __________ 、 _________、__________ 和 __________ 四种。
在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、
________和________的联系。
一种抽象数据类型包括 __________ 和 __________两个部分。
当一个形参类型的长度较大时，应最好说明为 _________，以节省参数值的传输时间和存储参数的空间。
6. 当需要用一个形参访问对应的实参时，则该形参应说明为 __________。
在函数中对引用形参的修改就是对相应 __________ 的修改，对 __________ 形参的修改只局限在该函数的内部，不会反映到对应的实参上。
当需要进行标准 I/O 操作时，则应在程序文件中包含 ________________ 头文件，当需要进行文件 I/O 操作时，则应在程序文件中包含 ________________ 头文件。
在包含有 ________________ 头文件的程序文件中，使用 ________________ 能够产生
0～ 20 之间的一个随机整数。
10. 一个数组 a 所占有的存储空间的大小即数组长度为 ____________，下标为 i 的元素
a[i] 的存储地址为 __________，或者为 ______________________________ 。
函数重载要求 ____________ 、____________ 或 ____________有所不同。
对于 双 目操 作符 ， 其重 载 函数 带有 __________ 个 参数 ，其 中 至少 有 一个 为
____________的类型。
13. 若对象 ra 和 rb 中至少有一个是属于用户定义的类型，则执行 ra==rb 时，需要调
用__________ 重载函数， 该函数的第一个参数应与 __________的类型相同， 第二个参数应与
__________的类型相同。
14. 从一维数组 a[n] 中顺序查找出一个最大值元素的时间复杂度为
个二维数组 b[m][n] 中所有元素值的时间复杂度为 ________。
________，输出一
在下面程序段中， s=s+p 语句的执行次数为 ________， p*=j 语句的执行次数为
________，该程序段的时间复杂度为 ________。
int i=0,s=0;
while(++i<=n) {
int p=1;
for(int j=1;j<=i;j++) p*=j;
s=s+p;
}
一个算法的时间复杂度为 (3 n2+2nlog 2n+4n-7)/(5 n) ，其数量级表示为 ________。
第二部分 线性表
一、单选题
．在一个长度为 n 的顺序存储线性表中， 向第 i 个元素 (1 ≤ i ≤ n+1) 之前插入一个新元
素时，需要从后向前依次后移 个元素。
A 、 n-i B 、 n-i+1 C 、 n-i-1 D 、 i
．在一个长度为 n 的顺序存储线性表中， 删除第 i 个元素 (1 ≤ i ≤n+1) 时，需要从前向
后依次前移 个元素。
A 、 n-i B 、 n-i+1 C 、 n-i-1 D 、 i
3 ．在一个长度为 n 的线性表中顺序查找值为 x 的元素时，查找时的平均查找长度（即
x 同元素的平均比较次数，假定查找每个元素的概率都相等）为 。
A 、 n B 、 n/2 C 、 (n+1)/2 D 、 (n-1)/2
4 ．在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行 。
、 HL = p; p->next = HL;
、 p->next = HL; HL = p;
C 、 p->next = HL; p = HL;
D 、 p->next = HL->next; HL->next = p;
5 ．在一个单链表
HL 中，若要在指针
q 所指的结点的后面插入一个由指针
p 所指的结点，
则执行
。
、q->next = p->next ; p->next = q;
、p->next = q->next; q = p;
、q->next = p->next; p->next = q;
、p->next = q->next ; q->next = p;
6 ．在一个单链表 HL 中，若要删除由指针 q 所指向结点的后继结点，则执行 。
、p = q->next ; p->next = q->next;
、p = q->next ; q->next = p;
、p = q->next ; q->next = p->next;
、q->next = q->next->next; q->next = q;
二、填空题
1．在线性表的单链接存储结构中，每个结点包含有两个域，一个叫
一个叫 域。
2 ．在下面数组 a 中链接存储着一个线性表，表头指针为 a[0].next
。
域，另
，则该线性表为
3 ．对于一个长度为 n 的顺序存储的线性表，在表头插入元素的时间复杂度为 ，
在表尾插入元素的时间复杂度为 。
4 ．对于一个长度为 n 的单链接存储的线性表，在表头插入元素的时间复杂度为 ，
在表尾插入元素的时间复杂度为 。
5．在线性表的顺序存储中，若一个元素的下标为 i ，则它的前驱元素的下标为 ，
后继元素的下标为 。
6 ．在线性表的单链接存储中，若一个元素所在结点的地址为 p，则其后继结点的地址
为 ，若假定 p 为一个数组 a 中的下标，则其后继结点的下标为 。
7 ．在循环单链表中，最后一个结点的指针指向 结点。
8 ．在双向链表中每个结点包含有两个指针域， 一个指向其 结点，另一个指
向其 结点。
9 ．在循环双向链表中表头结点的左指针域指向 结点，最后一个结点的右指
针域指向 结点。
．在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件
分别为 和 。
三、应用题
1 ．在下面的每个程序段中，假定线性表
La
的类型为
List
，元素类型
ElemType 为 int
，
并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表 La。
(1) InitList(La);
int a[]={48,26,57,34,62,79};
for(i=0; i<6; i++) InsertFront(La,a[i]);
TraverseList(La);
(2) InitList(La);
for(i=0; i<6; i++) Insert(La,a[i]);
TraverseList(La);
(3) ClearList(La);
for(i=0; i<6; i++) InsertRear(La,a[i]);
Delete(La, a[5]);
Sort(La);
Insert(La,a[5]/2);
TraverseList(La);
2．写出下面函数被调用执行后，得到的以 HL 为表头指针的单链表中的数据元素序列。
void
AA(LNode * & HL)
{
InitList(HL);
InsertRear(HL,30);
InsertRear(HL,50);
int a[5] = {15,8,9,26,12};
for ( int i=0; i<5;
i++ )
InsertFront(HL,a[i]);
}
．对于 List 类型的线性表，编写出下列每个算法。
从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。
从线性表中删除第 i 个元素并由函数返回。
向线性表中第 i 个元素位置插入一个元素。
(4) 从线性表中删除具有给定值 x 的所有元素。
．对于结点类型为 LNode 的单链表，编写出下列每个算法。
删除单链表中的第 i 个结点。
(2) 在有序单链表中插入一个元素 x 的结点。
从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。
(4) 统计出单链表中结点的值等于给定值 x 的结点数。
第三部分
栈和队列
一、单选题
1 ．栈的插入与删除操作在 进行。
A 、栈顶 B 、栈底 C 、任意位置 D 、指定位置
2 ．当利用大小为 N 的一维数组顺序存储一个栈时， 假定用 top==N 表示栈空， 则向这个
栈插入一个元素时，首先应执行 语句修改 top 指针。
A 、top++ B 、 top-- C 、 top=0 D 、 top
3 ．若让元素 1， 2， 3 依次进栈，则出栈次序不可能出现 种情况。
A 、3， 2， 1 B 、 2， 1，3 C 、 3， 1， 2 D 、 1， 3， 2
4 ．在一个循环顺序队列中，队首指针指向队首元素的 位置。
A 、前一个 B 、后一个 C 、当前 D 、后面
5 ．当利用大小为 N 的一维数组顺序存储一个循环队列时，该队列的最大长度为 。
6
8
A 、N-2 B 、 N-1 C 、 N D 、 N+1
．从一个循环顺序队列删除元素时，首先需要 。
A 、前移一位队首指针 B 、后移一位队首指针
C 、取出队首指针所指位置上的元素 D 、取出队尾指针所指位置上的元素
7．假定一个循环顺序队列的队首和队尾指针分别为 f 和 r ，则判断队空的条件是
A 、f+1==r B 、 r+1==f C 、 f==0 D 、 f==r
．假定一个链队的队首和队尾指针分别为 front 和 rear ，则判断队空的条件是
A 、front==rear B 、 front!=NULL C 、 rear!=NULL D 、 front==NULL
。
。
二、填空题
1 ．队列的插入操作在 进行，删除操作在 进行。
2 ．栈又称为 表，队列又称为 表。
3 ．向一个顺序栈插入一个元素时，首先使 后移一个位置，然后把待插入元素
到这个位置上。
4 ．从一个栈中删除元素时，首先取出 ，然后再前移一位 。
5 ．在一个循环顺序队列 Q 中，判断队空的条件为 ，判断队满的条件
为 。
6 ．在一个顺序栈中，若栈顶指针等于 ，则为空栈；若栈顶指针等于 ，则
为满栈。
7 ．在一个链栈中，若栈顶指针等于 NULL，则为 ；在一个链队中，若队首指
针与队尾指针的值相同，则表示该队列为 或该队列为 。
8 ．向一个链栈插入一个新结点时， 首先把栈顶指针的值赋给 ，然后把新结点
的存储位置赋给 。
9 ．从一个链栈中删除一个结点时，需要把栈顶结点 的值赋给 。
10 ．向一个顺序队列插入元素时， 需要首先移动 ，然后再向所指位置 新
插入的元素。
11 、当用长度为 N 的一维数组顺序存储一个栈时，假定用 top==N 表示栈空，则表示栈
满的条件为 。
12 ．向一个栈顶指针为
HS的链栈中插入一个新结点
*P
果，应执行
和
操作。
．从一个栈顶指针为 HS的非空链栈中删除结点并不需要返回栈顶结点的值和回收结
点时，应执行 操作。
．假定 front 和 rear 分别为一个链队的队首和队尾指针，则该链队中只有一个结点
的条件为 。
15.
中缀算术表达式 3+4/(25-(6+15))*8
所对应的后缀算术表达式为
。
16.
后缀算术表达式 24 8 + 3 * 4 10 7 - * /
所对应的中缀算术表达式为
，
其值为
。
三、应用题
执行下面函数调用后得到的输出结果是什么？
void AF(Queue & Q)
{
InitQueue(Q);
int a[4] = { 5,8,12,15 };
for ( int i=0; i<4;
QInsert(Q,QDelete(Q));
QInsert(Q,30);
QInsert(Q,QDelete(Q)+10);
while ( ! QueueEmpty(Q) ) cout
i++ )
QInsert(Q,a[i]);
<<QDelete(Q)<<
’ ‘ ;
}
四、编程题
裴波那契 (Fibonacci) 数列的定义为：它的第 1 项和第 2 项均为
项之和。若裴波那契数列中的第 n 项用 Fib(n) 表示，则计算公式为：
1 (n=1 或 2)
1，以后各项为其前两
Fib(n)=
Fib(n-1)+Fib(n-2)
(n>=2)
试编写出计算
Fib(n)
的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂
度。
第四部分 稀疏矩阵和广义表
一、单选题
在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的
________。
A 、 行号 B 、 列号 C 、 元素值 D 、 地址
2. 设一个广义表中结点的个数为 n，则求广义表深度算法的时间复杂度为 _______。
2
A 、 O(1) B 、 O(n) C 、 O(n ) D 、 O(log 2n)
二、填空题
1. 在一个稀疏矩阵中， 每个非零元素所对应的三元组包括该元素的 ________、________
________三项。
在稀疏矩阵所对应的三元组线性表中， 每个三元组元素按 ________为主序、 ________
为辅序的次序排列。
3. 在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 ________参数。
在稀疏矩阵的顺序存储中， 利用一个数组来存储非零元素， 该数组的长度应 ________
对应三元组线性表的长度。
5 ．在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有 ________个域，在相应
的十字链接存储中，每个结点包含有 ________个域。
．在稀疏矩阵的十字链接存储中， 每个结点的 down 指针域指向 ________相同的下一个结点， right 指针域指向 ________相同的下一个结点。
．一个广义表中的元素分为 ________元素和 ________元素两类。
．一个广义表的深度等于 ________嵌套的最大层数。
．在广义表的存储结构中，每个结点均包含有________个域。
．在广义表的存储结构中， 单元素结点与表元素结点有一个域对应不同，各自分别为
________域和 ________域。
11 ．若把整个广义表也看为一个表结点，则该结点的
tag
域的值为
________， next
域
的值为 ________。
三、应用题
已知一个稀疏矩阵如下图所示：
0
4
0
0
0
0
0
0
0
0
-3
0
0
1
8
0
0
0
0
0
0
0
0
0
5
0
0
0
0
-7
0
0
0
2
0
0
0
0
6
0
0
0
具有 6 行× 7 列的一个稀疏矩阵
写出它的三元组线性表；
给出它的顺序存储表示；
给出它的转置矩阵的三元组线性表和顺序存储表示；
画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。
A=(())
B=(a,b,c)
C=(a,(b,(c)))
D=((a,b),(c,d))
E=(a,(b,(c,d)),(e))
F=((a,(b,(),c),((d),e)))
第五部分 树和二叉树
一、填空题
1 ．对于一棵具有 n 个结点的树，该树中所有结点的度数之和为 ______ 。
假定一棵三叉树的结点个数为50，则它的最小深度为 ________，最大深度为 _______。
．在一棵三叉树中，度为 3 的结点数有 2 个，度为 2 的结点数有 1 个，度为 1 的结点数为 2 个，那么度为 0 的结点数有 ________个。
4
．一棵深度为 5 的满二叉树中的结点数为
________个，一棵深度为
3 的满三叉树中的
结点数为 ________个。
5
．假定一棵树的广义表表示为
A(B(C,D(E,F,G),H(I,J)))
，则树中所含的结点数为
________个，树的深度为 ________，树的度为 ________。
6
．假定一棵树的广义表表示为
A(B(C,D(E,F,G),H(I,J)))
，则度为
3、 2、 1、 0 的结点
数分别为 ______、 ______、 ______和 ______个。
7.
假定一棵树的广义表表示为
A(B(C,D(E,F,G),H(I,J)))
，则结点
H 的双亲结点为
________，孩子结点为 ___________。
8
．在一棵二叉树中，假定双分支结点数为
5 个，单分支结点数为 6
个，则叶子结点数
________个。
9
．对于一棵二叉树，若一个结点的编号为i ，则它的左孩子结点的编号为
________，
右孩子结点的编号为 ________，双亲结点的编号为 ________。
10
．在一棵二叉树中，第 5 层上的结点数最多为 ______。
．假定一棵二叉树的结点数为18，则它的最小深度为 ________，最大深度为 ________。
12 ．一棵二叉树的广义表表示为 a(b(c,d),e(f(,g))) ，则 e 结点的双亲结点为 ______，
左孩子结点为 ________，右孩子结点为 ________。
13. 一棵二叉树的广义表表示为 a(b(c,d),e(f(,g))) ，它含有双亲结点 ______个，单
分支结点 ______个，叶子结点 ______个。
假定一棵二叉树顺序存储在一维数组a 中，则 a[i] 元素的左孩子元素为 ________，
右孩子元素为 ________，双亲元素 (i>1) 为 ________。
．假定一棵二叉树顺序存储在一维数组a 中，但让编号为 1 的结点存入 a[0] 元素中，
让编号为 2 的结点存入 a[1] 元素中，其余类推，则编号为 i 结点的左孩子结点对应的存储
位置为 ________，若编号为 i 结点的存储位置用 j 表示，则其左孩子结点对应的存储位置为
________。
16. 若对一棵二叉树从 0 开始进行结点编号， 并按此编号把它顺序存储到一维数组 a 中，
即编号为 0 的结点存储到 a[0] 中，其余类推，则 a[i] 元素的左孩子元素为 ________，右孩
子元素为 ________，双亲元素 (i>0) 为 ________。
17 ．对于一棵具有 n 个结点的二叉树，对应二叉链表中指针总数为 ________个，其中
________个用于指向孩子结点， ________个指针空闲着。
18. 一棵二叉树广义表表示为 a(b(d(,h)),c(e,f(g,i(k)))) ，该树的结点数为 ________
个，深度为 ________。
19. 假定一棵二叉树广义表表示为 a(b(c),d(e,f)) ，则对它进行的先序遍历结果为
____________，中序遍历结果为 ____________，后序遍历结果为 ____________ ，按层遍历结
果为 ____________ 。
20. 假定一棵普通树的广义表表示为 a(b(e),c(f(h,i,j),g),d) ，则先根遍历结果为
____________，按层遍历结果为 ___________ 。
二、应用题
1. 已知一棵具有 n 个结点的完全二叉树被顺序存储于一维数组的 A[1] A[n] 元素中，
试编写一个算法打印出编号为 i 的结点的双亲和所有孩子。
2. 编写一算法，求出一棵二叉树中所有结点数和叶子结点数，假定分别用变参 C1 和
C2 统计所有结点数和叶子结点数，初值均为 0。
对于右图所示的树：
写出先根遍历得到的结点序列；
写出按层遍历得到的结点序列；
画出转换后得到的二叉树和二叉链表。
二叉树的应用
一、单选题
1.
从二叉搜索树中查找一个元素时，其时间复杂度大致为
________。
A
、 O(n)
B
、 O(1)
C
、 O(log 2n)
D
、 O(n 2)
2.
向二叉搜索树中插入一个元素时，其时间复杂度大致为
________。
A
、 O(1)
B
、 O(log
2n )
C
、 O(n)
D
、 O( nlog 2n)
3.
根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为
________。
A
、 O(n)
B
、 O(log
2
C
2
D
2
n )
、 O(n )
、 O( nlog n)
从堆中删除一个元素的时间复杂度为________。
A 、 O(1) B 、 O(n) C 、 O(log 2n) D 、 O( nlog 2n)
向堆中插入一个元素的时间复杂度为________。
A 、 O(log 2n) B 、 O(n) C 、 O(1) D 、 O( nlog 2n)
6. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为
________。
A 、 24 B 、 48 C 、 72 D 、 53
二、填空题
1. 在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 ________该结点
的值，右子树上所有结点的值一定 ________该结点的值。
2 ．对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个 ________。
3 ．从一棵二叉搜索树中查找一个元素时， 若元素的值等于根结点的值， 则表明 _______，
若元素的值小于根结点的值， 则继续向 ________查找，若元素的大于根结点的值， 则继续向
________查找。
4 ．在一个堆的顺序存储中， 若一个元素的下标为
i ，则它的左孩子元素的下标为 ______，
右孩子元素的下标为 ________。
在一个小根堆中，堆顶结点的值是所有结点中的 ________，在一个大根堆中，堆顶结点的值是所有结点中的 ________。
6 ．当从一个小根堆中删除一个元素时，需要把
后再按条件把它逐层 ________调整。
________元素填补到 ________位置，然
三、应用题
1. 已知一组元素为 (46,25,78,62,12,37,70,29) ，画出按元素排列顺序输入生成的一棵二叉搜索树。
2. 空堆开始依次向堆中插入线性表 （ 38,64,52,15,73,40,48,55,26,12 请以线性表的形式给出每插入一个元素后堆的状态。
）中的每个元素，
3. 已知一个堆为（ 12,15,40,38,26,52,48,64
给出每删除一个元素后堆的状态。
），若需要从堆中依次删除四个元素，请
4. 有七个带权结点，其权值分别为 3,7,8,2,6,10,14 ，试以它们为叶子结点构造一棵
哈夫曼树，并计算出带权路径长度 WPL。
四、算法设计
1．编写在以
BST为树根指针的二叉搜索树上进行查找值为
item
的结点的非递归算法，
若查找成功则由 item 带回整个结点的值并返回 true ，否则返回 false 。
bool Find( BTreeNode * BST , ElemType & item )
2．下面的算法功能是向 HBT堆中插入一个值为 item 的元素，使得插入后仍是一个堆。
请在画有横线的地方填上合适的语句，完成其功能。
void
AH(Heap & HBT , const
ElemType
item)
在一个具有
n 个顶点的无向图中，要连通所有顶点则至少需要
________条边。
4
．表示图的三种存储结构为 ________、 ________和 ________。
5.
对于一个具有 n 个顶点的图，若采用邻接矩阵表示，则矩阵大小为________。
．对于一个具有 n 个顶点和 e 条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为 ________和 ________条。
在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有
________和________结点。
．对于一个具有 n 个顶点和 e 条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为 ________和 ________条。
．对于一个具有 n 个顶点和 e 条边的无向图，当分别采用邻接矩阵、邻接表和边集数
组表示时，求任一顶点度数的时间复杂度依次为________、 ________和 ________。
假定一个图具有 n 个顶点和 e 条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为 ________、 ________和 ________。
11. 对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为 ________，对用邻接表
表示的图进行任一种遍历时，其时间复杂度为 ________。
12．对于下面的无向图 G1，假定用邻接矩阵表示，则从顶点 v0 开始进行深度优先搜索
遍历得到的顶点序列为 ____________ ，从顶点 v0 开始进行广度优先搜索遍历得到的顶点序
列为 ____________ 。
对于下面的有向图 G2，假定用邻接矩阵表示，则从顶点 v0 开始进行深度优先搜索遍历得到的顶点序列为 ____________ ，从顶点 v0 开始进行广度优先搜索遍历得到的顶点序列为 ____________ 。
对于下面的带权图 G3，其最小生成树的权为 ________。
．对于下面的带权图 G3，若从顶点 v0 出发， 则按照普里姆算法生成的最小生成树中，依次得到的各条边为 _______________。
16. 对于下面的带权图 G3，若按照克鲁斯卡尔算法产生最小生成树，则得到的各条边依次为 _______________。
17 ．假定用一维数组
d[n]
存储一个
AOV网中用于拓扑排序的顶点入度，则值为
0 的元
素被链接成为一个
________。
对于一个具有 n 个顶点和 e 条边的连通图，其生成树中的顶点数和边数分别为
________和________。
二、应用题
1. 对于下图
G4 和
G5，按下列条件试分别写出从顶点
v0 出发按深度优先搜索遍历得到
的顶点序列和按广度优先搜索遍历得到的顶点序列。
(1) 假定它们均采用邻接矩阵表示 ;
假定它们均采用邻接表表示， 并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
对于下图 G6，试给出一种拓扑序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓扑序列。
第七部分
查找
一、填空题
1 ．以顺序查找方法从长度为 n 的线性表中查找一个元素时， 平均查找长度为 ________，
时间复杂度为 ________。
2 ．以二分查找方法从长度为 n 的线性有序表中查找一个元素时，平均查找长度小于等
________，时间复杂度为 ________。
3
．以二分查找方法从长度为 12 的有序表中查找一个元素时， 平均查找长度为 ________。
4
．以二分查找方法查找一个线性表时，此线性表必须是
________存储的 ________表。
5
．从有序表 (12,18,30,43,56,78,82,95)中依次二分查找
43 和 56 元素时，其查找长度
分别为 ________和 ________。
6
．对于二分查找所对应的判定树，它既是一棵_______，又是一棵 ________。
．假定对长度 n=50 的有序表进行二分查找， 则对应的判定树高度为 ________，判定树
中前 5 层的结点数为 ________，最后一层的结点数为 ________。
8
．在索引表中，每个索引项至少包含有
________域和 ________域这两项。
9
．假定一个线性表为
(12,23,74,55,63,40,82,36)
，若按 Key %3 条件进行划分，使得
同一余数的元素成为一个子表，则得到的三个子表分别为
________、________和 ________。
10.
假
定
一
个
线
性
表
为
( ”abcd”, ”baabd”, ”bcef ”, ”cfg ”, ”ahij ”, ”bkwte”, ”ccdt ”,
”aayb”) ，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的 a,b,c 三个子表的长度分别为 ________、 ________和 ________。
11 ．在线性表的 ________存储中，无法查找到一个元素的前驱或后继元素。
12 ．在线性表的 ________存储中，对每一个元素只能采用顺序查找。
13 ．假定对线性表 (38,25,74,52,48) 进行散列存储，采用 H(K)=K % 7 作为散列函数，若分别采用线性探查法和链接法处理冲突， 则对各自散列表进行查找的平均查找长度分别为_______和 ________。
14 ．假定要对长度 n=100 的线性表进行散列存储， 并采用链接法处理冲突， 则对于长度
m=20的散列表，每个散列地址的单链表的长度平均为 ________。
在线性表的散列存储中，处理冲突有________和 ________两种方法。
16 ．对于线性表 (18,25,63,50,42,32,90) 进行散列存储时，若选用 H(K)=K % 9 作为散
列函数，则散列地址为 0 的元素有 ________个，散列地址为 5 的元素有 ________个。
二、应用题
假定查找有序表 A[25] 中每一元素的概率相等，试分别求出进行顺序、二分查找每一元素时的平均查找长度。
2. 假定一个待散列存储的线性表为 (32,75,29,63,48,94,25,46,18,70) ，散列地址空间
HT[13] ，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
3. 假定一个待散列存储的线性表为 (32,75,29,63,48,94,25,46,18,70) ，散列地址空间
HT[11] ，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
三、算法设计
设计在有序表 A[n] 中按二分查找关键字为 K 的递归和非递归算法。
第八部分 排序
一、填空题
．每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫
________排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 ________排序。
．每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，
此种排序方法叫做 ________排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫
做________排序。
3 ．在直接选择排序中，记录比较次数的时间复杂度为
复杂度为 ________。
________，记录移动次数的时间
4. 在堆排序的过程中，对 n 个记录建立初始堆需要进行 ________次筛运算，由初始堆
到堆排序结束，需要对树根结点进行 _______次筛运算。
5 ．在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为 ________，整个堆
排序过程的时间复杂度为 ________。
6 ．假定一组记录的排序码为 (46,79,56,38,40,84) ，则利用堆排序方法建立的初始堆为
________________ 。
快速排序在平均情况下的时间复杂度为________，在最坏情况下的时间复杂度为
________。
8 ．快速排序在平均情况下的空间复杂度为
________。
________ ，在最坏情况下的空间复杂度为
9 ．在快速排序方法中，进行每次划分时，是从当前待排序区间的 ________向 ________
依次查找出处于逆序的元素并交换之， 最后将基准元素交换到一个确定位置， 从而以该位置
把当前区间划分为前后两个子区间。
10. 假定一组记录的排序码为 (46,79,56,38,40,80) ，对其进行快速排序的一次划分的
结果为 ________________ 。
11. 假定一组记录的排序码为 (46,79,56,38,40,80) ，对其进行快速排序的过程中，对
应二叉搜索树的深度为 ________，分支结点数为 ________。
．在二路归并排序中，对 n 个记录进行归并的趟数为 ________。
在归并排序中，进行每趟归并的时间复杂度为 ________，整个排序过程的时间复杂度为 ________，空间复杂度为 ________。
14 ．对 20 个记录进行归并排序时，共需要进行 ________趟归并，在第三趟归并时是把
长度为 ________的有序表两两归并为长度为 ________的有序表。
15 ．假定一组记录的排序码为 (46,79,56,38,40,80) ，对其进行归并排序的过程中，第
二趟归并后的结果为
________________ 。
二、应用题
已知一组元素的排序码为
(46 ， 74， 16， 53，14， 26，40， 38，86， 65， 27， 34)
利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。
利用直接选择排序方法写出每次选择和交换后的排列结果。
(3) 利用堆排序的方法写出在构成初始堆和利用堆排序的过程中， 每次筛运算后的排列
结果，并画出初始堆所对应的完全二叉树。
(4) 利用快速排序的方法写出每一层划分后的排列结果， 并画出由此快速排序得到的二
叉搜索树。
利用归并排序的方法写出每一趟二路归并排序后的结果。
三、算法设计
完成从一维数组 A[n] 上进行快速排序的递归算法。
void QuickSort( ElemType A[] , int
s , int
t )
{
int i = s,
ElemType
do {
j = t+1;
x = A[s];
do
i++;
while
(
) ;
tn >
);
if
( i<j )
{
ElemType
temp
= A[i]
;
A[i]
= A[j]
;
A[j]
=
temp; }
} while ( i<j );
A[s] = A[j];
A[j] = x;
if ( s<j-1 )
;
if ( j+1<t )
;
}
数据结构练习题参考答案
第一部分 绪 论
一、单选题
1. A 2. C 3. B 4. C 5. D 6. B
二、填空题
集合结构、线性结构、树型结构、图形结构
顺序、链接、索引、散列
1:1 、 1:N 、 M:N
数据定义、操作声明
引用形参 ( 或 指针形参 )
引用类型 ( 或 指针类型 )
实参、值
、
、 rand( ) %21
10. sizeof(a) 、 a+i*sizeof(a[0]) 、a+i
参数类型、数量、次序
2 、用户自定义
= = 、ra 、 rb
O(n) 、O(m*n)
n 、 n(n+1)/2 、 O(n2)
O(n)
第二部分 线性表
一、单选题
1. B 2. A 3. C 4. B 5. D 6. C
二、填空题
元素值、指针
( 38 , 56 , 25 , 60 , 42 , 74 )
O(n) 、O(1)
(1) 、 O(n)
i-1 、 i+1
6. p->next 、 a[p].next
表头
前驱、后继
表尾、表头
10． HL->next = = NULL 、 HL->next = = HL
三、应用题
(1) ( 79 , 62 , 34 , 57 , 26 , 48 )
( 26 , 34 , 48 , 57 , 62 , 79 )
( 26, 34 , 39 , 48 , 57 , 62 )
． （ 12， 26， 9， 8， 15，30， 50）
． (1) ElemType DMValue( List & L ) {
if ( ListEmpty(L) ) { A 2. B 3. C 4. A 5. B 6. B 7. D 8.
D
二、填空题
队尾、队首
后进先出 (LIFO) 、先进先出 (FIFO)
栈顶指针、存储
栈顶元素、栈顶指针
5. front = = rear 、 (rear+1)%QueueMaxSize = = front
–1 、 StackMaxSize-1
栈空、空队、队列只有一个元素
新结点的指针域、栈顶指针
指针域、栈顶指针
队尾指针、存储
top = = 0
12.
p->next = HS
、 HS = p
13.
HS = HS->next
( front = = rear ) && ( front <>NULL )
3 4 25 6 15 + - / 8 * +
16. (24+8)*3/(4*(10-7)) 、 8
三、应用题
12 15 5 30 18
四、编程题
递归算法：
long Fib( int n ) {
if ( n==1 || n=2 ) A 2. B
二、填空题
行号、列号、元素值
行号、列号
引用 ( 或指针 )
等于
4 、 5
列号、行号
单、表
括号
3
元素值、子表指针
true 、NULL
三、应用题
1． (1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) )
(2)
1
2
2
3
4
5
5
6
2
4
7
1
4
2
6
4
4
-3
1
8
5
-7
2
6
(3) ((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5), (4,6,6),(6,5, 2),(7,2,1))
1
2
2
4
4
4
6
7
3
1
5
2
4
6
5
2
8
4
-7
-3
5
6
2
1
2． (1) A
(2) B
：长度：
：长度：
1
3
深度：
深度：
2
1
C ：长度： 2 深度： 3
(4) D ：长度： 2 深度： 2
E ：长度： 3 深度： 3
F：长度： 1 深度： 4
第五部分 树和二叉树
一、填空题
n-1
5 、 50
6
31 、 21
10 、 4、 3
2 、 1、 1、 6
B 、 I 和 J
6
9. 2i 、 2i+1 、 i/2
16
5 、 18
a 、 f 、空结点 ( 即无右孩子结点 )
4 、 2、 3
14.
a[2*i]
、 a[2*i+1]
、 a[i/2]
15.
2i-1
、 2j+1
16.
A[2*i+1]
、 a[2*i+2]
、 a[i/2]
2n 、 n-1 、n+1
10 、 5
abcdef 、 cbaedf 、 cbefda 、abdcef
20. abecfhijgd 、 abcdefghij
二、应用题
1． void Request( int A[] , int n , int i ) {
if ( i>n ) {
cerr <<
”编号为”
<<i<< ”的结点不存在！”
<<endl;
exit(1);
}
cout <<
int j = i/2; C
”当前结点为” 2. B 3. D 4. C
<<A[i]<<endl;
5. A 6. D
二、填空题
小于、大于等于
按升序排列的有序序列
找到、左子树、右子树
2i+1 、 2i+2
最小值、最大值
堆尾、堆顶、向下
三、应用题
1.
初态：空堆 ( )
插入 38 后： ( 38 )
插入 64 后： ( 38 , 64 )
插入 52 后： ( 38 , 64 , 52 )
插入 15 后： ( 15 , 38 , 52 , 64 )
插入 73 后： ( 15 , 38 , 52 , 64 , 73 )
插入 40 后： ( 15 , 38 , 40 , 64 , 73 , 52 )
插入 48 后： ( 15 , 38 , 40 , 64 , 73 , 52 , 48 )
插入 55 后： ( 15 , 38 , 40 , 55 , 73 ,52 , 48 , 64 )
插入 26 后： ( 15 , 26 , 40 , 38 , 73 ,52 , 48 , 64 , 55 )
插入 12 后： ( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 , 55 ,73 )
初态堆： ( 12 , 15 , 40 , 38 , 26 ,52 , 48 , 64 )
删除第 1 个元素后堆： ( 15 , 26 , 40 , 38 , 64 , 52 , 48 )
删除第 2 个元素后堆： ( 26 , 38 , 40 , 48 , 64 , 52 )
删除第 3 个元素后堆： ( 38 , 48 , 40 , 52 , 64 )
删除第 4 个元素后堆： ( 40 , 48 , 64 , 52 )
哈夫曼树：
WPL = 3*4+7*3+8*3+2*4+6*3+10*2+14*2 = 131
四、算法设计
．bool Find( BTreeNode * BST , ElemType & item )
{
while ( BST != NULL )
{
if ( item == BT->data ) {
ey )
return mid; ey )
return Binsch( A , low , mid-1 , K ); ey )
return mid; ey )
high = mid-1; tn<
QuickSort( A,s,j-1)
QuickSort( A,j+1,t)