数据结构习题集

第一章 绪论

一、填空题

1． 数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。____数据元素_____是数据的基本单位；____数据项_______是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为____结构____。

2． 数据结构进行形式化定义时，可以从逻辑上认为数据结构DS 是_____数据元素的有限集____的集合D 和D 上____关系的有限集_____的集合R 所构成的二元组：DS=（D ，R ）。

3．

4． 一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n 大小无关时，则表示为____O(1)______；成正比关系时，则表示为_____O(n)______；成对数关系时，则表示为____O(log2n)_______；成平方关系时，则表示为____O(n2)______。

5． 数据结构的逻辑结构包括_____线性结构________、树型结构和图型结构三种类型，其中树型结构和图型结构合称为______非线性结构_______；数据结构的存储结构主要包括____顺序________和______链式______两种类型。

6． 线性结构的特点是：第一个结点___无____前驱结点，其余结点有且仅有__一_____个前驱结点；最后一个结点__无_____后继结点，其余每个结点有且仅有___一____个后继结点。

7． 树型结构的特点是：根结点没有__前驱______结点，其余每个结点有且仅有_____一个___个前驱结点；叶子结点_____无____后继结点，其余结点可以有___任意______个后继结点。

8． 图型结构的特点是：每个结点可以有____任意_____个前驱结点和后继结点。

9． 程序段for （i=1，s=0；s

10． 常见的时间复杂度有常数阶O(1)、对数阶O(log2n) 、线性阶O(n)、平方阶O(n2) 、线性对数阶O(nlog2n) 、立方阶O(n3) 、指数阶O(2n ) 等等，这些数量阶之间的大小关系为___ O(1)

二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。

1. A=（K ，R ），其中：K={a，b ，c ，d ，e ，f ，g ，h}，R={r}，r={，，，，，

，}。

2. B=（K ，R ），其中：K={a，b ，c ，d ，e ，f ，g ，h}，R={r}，r={，，，，，

，}。

3. C=（K ，R ），其中：K={ a，b ，c ，d ，e }，R={r}，r={，，，，，，

}。

4. D=（K ，R ），其中：K={48，25，64，57，82，36，75}，R={r1，r2}，r1={，，

57>，，，}；r2={，，，，，}。

5. E=（K ，R ），其中：K={1，2，3，4，5，6，7}，R={r}，r={，，，，

3>，，，，，}。

三、指出下列各函数的功能并求出其时间复杂度。

1. void prime(int n)

{

int i;

for(i=2;i

if (i>sqrt(n)) printf(“yes”); else printf(“no”);

}

2. long sum1(int n)

{

long sum,w,i;

for(sum=0,i=1;i

return(sum);

}

3. long sum2(int n)

{

long sum,w,i;

for(sum=0, w=1,i=1;i

return(sum);

}

4. void sort(int r[ ],int n)

{

int i,j;

for(i=1; i

if(r[j]>r[j+1]) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;}

}

第二章 线性表

一、填空题

1． 设长度为n 的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动____n/2___个元素，删除一个元素时平均需要移动____(n-1)/2__个元素。

2． 在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要___向后_____移动一个位置。

3． 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要_____向前_____移动一个位置。

4． 线性表的链式存储结构中，元素之间的线性关系是通过结点中的____指针域____来实现的。

5． 线性表的顺序存储结构中逻辑上相邻的元素，物理位置____一定______相邻；线性表的链式存储结构中逻辑上相邻的元素，物理位置_____不一定_______相邻。

6． 已知单链表的长度为n ，则在给定值为x 的结点后插入一个新结点的时间复杂度为_____O(n)_____。

7． 已知单链表的长度为n ，则删除给定值为x 的结点的时间复杂度为______O(n)____。

8． 在单链表中设置头结点的作用是________________消除空表的特殊性，统一表示和处理空表和非空表的情形，简化删除和插入的操作细节________________。

9． 双向链表中每个结点含有两个指针域，其中一个指针域指向___前驱____结点，另一个指针域指向___后驱___结点。

10． 在长度为n 的线性表中顺序查找某个结点值为X 的时间复杂度为______O(n)________。

二、选择题

1．在长度为n 的顺序线性表中删除第i 个元素(1

2．建立一个长度为n 的单链表的时间复杂度为（ 1 ）。

⑴ O(n) ⑵ O(1) ⑶ O(n2) ⑷ ((log2n)

3．设指针p 指向单链表中的结点A ，结点A 的后继结点是结点B ，则删除结点B 的操作为（ 4 ）。 ⑴ p->next=p ⑵ p=p->next

⑶ p=p->next->next ⑷ p->next=p->next->next

4．设指针p 指向单链表中结点A ，指针q 指向单链表中结点A 的前驱结点B ，指针s 指向被插入的结点X ，则在结点A 和结点B 之间插入结点X 的操作为（ 2 ）。

⑴ s->next=p->next； p->next=s； ⑵ q->next=s； s->next=p；

⑶ p->next=s->next； s->next=p； ⑷ p->next=s； s->next=q；

5．在长度为n 的顺序线性表中的第i 个元素(1

⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i

6．在长度为n 的有序线性表中插入一个元素后仍然保持有序的平均时间复杂度为（ 4 ）。

⑴ O(log2n) ⑵ O(1) ⑶ O(n2) ⑷ O(n)

7．设指针p 指向双向链表中的结点A ，指针s 指向被插入的结点X ，则在结点A 之后插入结点X 的操作为（ 4 ）。 ⑴ p->rlink=s； s->llink=p； p->rlink->llink=s； s->rlink=p->rlink；

⑵ s->llink=p； s->rlink=p->rlink； p->rlink=s； p->rlink->llink=s；

⑶ p->rlink=s； p->rlink->llink=s； s->llink=p； s->rlink->p->rlink；

⑷ s->llink=p； s->rlink=p->rlink； p->rlink->llink=s； p->rlink=s；

8．指针p 指向双向链表中的结点A ，则删除结点A 的操作是（ 1 ）。

⑴ p->llink->rlink=p->rlink； p->rlink->llink=p->llink；

⑵ p->rlink->llink=p->rlink； p->llink->llink=p->llink；

⑶ p->llink->rlink=p->llink； p->rlink->llink=p->rlink；

⑷ p->rlink->rlink=p->rlink； p->rlink->rlink=p->rlink；

9．线性表采用链式存储结构时，要求存储单元的地址（ 4 ）。

⑴ 必须是连续的 ⑵ 部分地址必须是连续的

⑶ 一定是不连续的 ⑷ 连续不连续都可以

10．设head 为单链表的头指针，则不带头结点的单链表为空的判定条件是（ 1 ）。

⑴ head==NULL ⑵ head->next==NULL

⑶ head->next==head ⑷ head!=NULL

11．设head 为单链表的头指针，则带头结点的单链表为空的判定条件是（2 ）。

⑴ head==NULL ⑵ head->next==NULL

⑶ head->next==head ⑷ head!=NULL

12．设head 和tail 分别为单向循环链表的头指针和尾指针，则下列等式成立的是（ 3 ）。

⑴ head==tail ⑵ head->next==tail

⑶ tail->next==head ⑷ head->next==tail->next

三、算法设计题

顺序存储结构的类型定义：typedef struct {int a[m]; int n; } sqlist;

链式存储结构的类型定义：typedef struct node {int data; struct node *next;} lklist;

1. 建立一个有n 个结点的单链表，要求从尾部进行插入。

2. 建立一个有n 个结点的单链表，要求从头部进行插入。

3. 用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a 1，a 2，……，a n ）逆置为(an ，

a n-1，……，a 1) 。

4. 用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a 1，a 2，……，a n ）逆置为(an ，

a n-1，……，a 1) 。

5. 已知集合A 、B ，求集合C=A∩B 算法，要求集合A 、B 和C 均用采用顺序存储结构表示。

6. 已知集合A 、B ，求集合C=A∩B 算法，要求集合A 、B 和C 均用采用链式存储结构表示。

7. 设计在带有头结点的单向链表中删除值为X 的结点算法。

第三章 栈和队列

一、填空题

1. 线性表、栈和队列从逻辑上来说都是_____线性_______结构。可以在线性表的___任意____位置插入和删除元素；对于栈只能在____栈顶______插入和删除元素；对于队列只能在______队尾_____插入元素和在_____队头____删除元素。

2. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为____先进后出______表；队列的插入和删除运算分别在队列的两端进行，进行插入的一端叫做_____队尾_____，进行删除的一端叫做______队头_____，先进队的元素必定先出队，所以又把队列称为______先进先出______表。

3. 假设用向量S[1：m]来存储顺序栈，指针top 指向当前栈顶的位置。则当栈为空时满足的条件是_____top==0_______；当栈为满时满足的条件是____top==m_________。

4. 设有一个空栈，现有输入序列1、2、3、4、5，经过push 、push 、pop 、push 、pop 、push 、push 、pop 、pop 、 pop 后，输出序列为________23541__________。

5. 在一个顺序循环队列中为了方便入队列和出队列的操作通常约定头指针front 指向实际队头元素的______前一个位置______，尾指针rear 指向当前实际队尾元素的______所在位置______。若该顺序循环队列有m 个存储单元，则队列满时共有_____m-1_____个元素。

6. 设有一个顺序循环队列如上题中的约定，则该队列满的条件是____(rear+1)%m==front_____，队列空的条件是____rear==front_____。

7. 不论是顺序栈（队列）还是链式栈（队列），插入（删除）运算的时间复杂度均为____O(1)____。

8. 系统在函数调用前自动把调用后的______返回地址______压入堆栈；当函数调用结束后，系统又自动作退栈处理，并将程序执行流程无条件转移到所保存的______返回地址_______处继续执行。

二、选择题

1．设栈的输入序列是1、2、3、…、n ，输出序列的第一个元素是n ，则第i 个输出元素是（ 3 ）。 ① n-i ② n-i-1 ③ n-i+1 ④不确定

2．设元素进栈次序为A 、B 、C 、D 、E ，则下列不可能的出栈序列是（ 3 ）。

① ABCDE ② BCDEA ③ EABCD ④ EDCBA

3．设用一维数组s[m]表示栈的存储空间，用top 指向当前栈顶元素（其初始值为-1），则进行出栈时的操作序列是（ 3 ）。

① x=s[op]； ② x=s[top]；top=0；

③ x=s[top]；top==top-1； ④ x=s[top]；top==top+1；

4．设指针hs 指向栈顶，指针s 指向插入的结点A ，则插入结点A 时的操作为（ 2 ）。

① hs->next=s； ② s->next=hs； hs=s；

③ s->next=hs->next； hs->next=s； ④ s->next=hs； hs=hs->next；

5．设用一维数组s[m]表示栈的存储空间，用top 指向当前栈顶元素（其初始值为-1），则进行入栈时的操作序列是（ 2 ）。

① s[top] =x； ② top=top+1；s[top]=x；

③ top==top-1；s[top]=x； ④ s[top]=x；top==top+1；

6．设front 是链式队列的头指针，rear 是链式队列的尾指针，s 指向插入的结点A ，则插入结点A 的操作为（ 3 ）。 ① front->next=s； front=s； ② s->next=rear； rear=s；

③ rear->next=s； rear=s； ④ s->next=front； front=s；

7．设front 是链式队列的头指针，rear 是链式队列的尾指针，则删除队头元素的操作为（ 1 ）。 ① front=front->next； ② rear=rear->next ；

③ rear=front->next ； ④ front=rear->next；

8．对于一个具有m 个存储单元的顺序循环队列，设front 为队头指针，rear 为队尾指针，则该队列中队列元素的个数计算公式为（ 4 ）。

① rear-front ② front-rear

③ (rear-front)%m ④ (rear-front+m)%m

9． 设用一维数组q[m]作为顺序循环队列的存储空间，front 指向队头元素的前一个位置，rear 指向队尾元素的

当前位置，则入队列的操作序列为（ 3 ）。

① q[rear] =x；rear=rear+1； ② q[rear]=x；rear=rear-1；

③ rear=(rear+1)%m；q[rear] =x； ④ rear=(rear-1)%m；q[rear]=x；

10． 设用一维数组q[m]作为顺序循环队列的存储空间，front 指向队头元素的前一个位置，rear 指向队尾元素的

当前位置，则出队列的操作序列为（ 2 ）。

① x=q[front]；front=front+1； ② x=q[front]；front=(front+1)%m；

③ x=q[front]；front=front-1； ④ x=q[front]； front=(front-1)%m；

三、算法设计题

1． 设有两个顺序栈S1和S2共享一个存储区S[0：m-1]，为了尽量利用存储空间减少溢出的可能性，采用栈

顶相向、迎面增长的存储方式，要求分别设计两个栈的入栈和出栈操作。

2． 设计算法判断表达式中的圆括号是否配对出现。

3． 设用一个单向循环链表来表示队列（也称循环队列），该队列只设一个队尾指针rear ，不设队头指针front ，

要求设计出该队列的入队列和出队列操作。

4． 假设以一个一维向量q[0：m-1]作为顺序循环队列的存储空间，同时设变量rear 和len 分别指示顺序循环队

列中的队尾元素的位置和实际队列中的元素个数，要求设计出该队列的入队列和出队列操作。

5． 将数字1、2、……、n 按顺时针方向排列成环形，按顺时针方向从1开始计数，计满时则输出该位置上的

数字并从环中删除该数字，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止，要求设计一个算法完成此功能。

第四章 字符串和数组

一、填空题

1. 设字符串S1=“ABCDEF”，S2=“PQRS”，则运算S=CONCAT(SUB(S1，2，LEN(S2))，SUB(S1，LEN(S2)，

2) 的结果为S=_______BCDEDE__________。

2. 判断两个字符串相等的充要条件是____字符串的长度相等且对应位置的字符相等________________________。

3. 下列程序段实现子串t 在主串s 中位置的算法，要求在下划线处填上正确语句。

int index(char s[ ], char t[ ])

{

i=j=0;

while(i

if(s[i]==t[j]){i=i+l; j=j+l;}else{i=__i-j+1_____; j=___0___;}

if (j==strlen(t))return(i-strlen(t));else return (-1);

}

4. 设二维数组A 有m 行n 列，每个数组元素占L 个字节的存储单元，按行的顺序存放在m*n个连续的存储单元中。已知A[0][0]的地址为1000，则A[i][j]的地址为_______1000+(i*n+j)*L_______________________________。

5. 设三维数组A[3][4][5]中的每个元素占10个字节的存储单元，按行的顺序存放在一组连续的存储空间中。已知A[0][0][0]的首地址为1000，则数组元素A[1][2][3]的首地址为____________1330_______________。

6. 设对称矩阵A 有n 行n 列，每个数组元素占L 个字节的存储单元，按行的顺序将下三角矩阵中的元素（包括对角线上的元素）存放在n*(n+1)/2个存储单元中，已知A[0][0]的地址为1000，则A[i][j]（i>=j）的地址为______1000+(i*(i+1)/2+j)_____________________。

7. 设有n 行n 列的三对角矩阵A ，每个数组元素占L 个字节的存储单元，按照从上到下从左到右的顺序将三条对角线上的元素存放在3n-2个连续的存储单元中，已知A[0][0]的地址为1000，则三对角线上元素A[i][j]的地址为________(2*i+j)*L_________。

⎧0⎪3⎪8. 已知稀疏矩阵A=⎨⎪0

⎪⎩002000-1000⎫0⎪⎪⎬，则A 的三元组表为__________________。 5⎪0⎪⎭

二、算法设计题

1. 设用顺序存储结构存储字符串S1和S2，要求设计一个函数完成对两个字符串的比较。若S1>S2时则返回正数；若S1=S2时则返回0；若S1

2. 用顺序存储结构实现在字符串S 中删除所有其值等于ch 的字符的算法。

3. 设单链表中存放n 个字符，试设计算法判断字符串是否关于中心对称。

第五章 树

一、填空题

1. 设一棵树的二元组形式表示为T=（D ，R ），其中D={A，B ，C ，D ，E ，F ，G}，R={(A，B) ，(A，C) ，(A，

D) ，(B，E) ，(C，F) ，(C，G)}，则该树的度数为____3____，树的深度为___3_____，叶子结点的个数为_____4____，分支结点的个数为___4______，C 结点的双亲结点为____A______，C 结点的孩子结点为____F,G______。

2. 二叉树有____5_____种不同形态。

3. 对于一棵具有n 个结点的二叉树，当它为一棵____完全______二叉树时具有最小高度，其最小高度为________[logn+1]_______。 2

4.

5. 一棵深度为k 的满二叉树的结点总数为______2k -1_____；一棵深度为k 的完全二叉树的结点总数最少有______2k-1_____个，最多有______2k -1______个。 已知一棵二叉树中度数为0的结点个数为n 0，度数为1的结点数为n 1，则该树中度数为2的结点数为n 2，则n 0=_____1+n2______。

6. 一棵树中度数为1的结点数为n 1，度数为2的结点数为n 2，……，度数为m 的结点度为n m ，则该树中度数为0的结点数为_____n0=1+n2+2n3````(m-1)nm _______个。

7. 已知一棵二叉树的顺序存储结构表示为ABCDE ϕF （其中字符ϕ表示空结点），则其前序序列为______ABDECF_______，中序序列为____DBEACF_______，后序序列为_____DEBFCA________。

8. 按照从上到下、从左到右的顺序对有n 个结点的完全二叉树从1开始顺序编号，则编号为（i i!=1且2i+1

9. 对于一棵具有n 个结点的二叉树，当用二叉链表作为存储结构时，其二叉链表中的指针域的总数为___2n___个，其中___n-1___个用于链接孩子结点，__n+1_____个为空指针域。

10. 设某棵二叉树的前序遍历序列为ABCDEFGH ，中序遍历序列为BCAEDGHF ，则该二叉树的后序遍历序列为_________CBEHGFDA___________。

11. 如果按中序遍历某二叉树的遍历序列为abc ，问有___5_____种不同的二叉树可以得到这一遍历序列。

12. 设哈夫曼树中有n 个叶子结点，则该哈夫曼树中总共有____2n-1_______结点。

二、选择题

1．假设一棵二叉树中，双分支结点数为15个，单分支结点数为30个，则终端结点数为（ 2 ）。 ① 15 ② 16 ③ 17 ④ 47

2．假设一棵三叉树的结点数为50，则它的最小高度为（ 3 ）。

① 3 ② 4 ③ 5 ④ 6

3．一棵二叉树上第5层的结点数最多为（ 2 ）。

① 15 ② 16 ③ 8 ④ 32

4．将完全二叉树中的所有结点按照从上到下、从左到右的顺序存放在n 个连续的存储单元中，若结点R[i]有左孩子，则左孩子的结点是（ 2 ）。

① R[2i+1] ② R[2i] ③ R[i/2] ④ R[2i-1]

5. 设一棵具有n 个结点的满二叉树有m 个叶子结点和k 个分枝结点，则下列等成立的是（ 1 ）。 ① n=2k+1 ② m+k=2n ③ n=2m+1 ④ n=2k-1

6．设森林F 中有三棵树，第一、第二和第三棵树的结点树分别为m 1、m 2和m 3，则与森林F 对应的二叉树的根结点的右子树上的结点个数是（ 4 ）。

① m 1 ② m 1+m2 ③ m 3 ④ m 2+m3

7．设A 、B 为一棵二叉树上的两个结点，中序遍历时A 在B 前的条件是（ 2 ）。

① A 在B 的右方 ② A 在B 的左方 ③ A 是B 的祖先 ④ A 是B 的子孙

8．一棵具有k 层的满三叉树中共有（ 1 ）个结点数。

① (3 k -1)/2 ② 3 k -1 ③ (3 k -1)/3 ④ 3 k

9．设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少有（ 3）个。 ① 2h ② 2h-1 ③ 2h+1 ④ h+1

10．若采用顺序存储结构存储深度为h 且有n 个结点的二叉树，则最多将浪费（ 2）个存储单元。

① 0 ② 2 h -1-n ③ 2 h +1-n ④ 2 h -n

11．已知某二叉树的后序遍历序列是dabec ，中序遍历序列是debac ，则它的前序遍历序列是（ 4 ）。

① acbed ② decab ③ deabc ④ cedba

12．在一棵非空二叉树的中序遍历序列中，根结点的右边（ 1 ）。

① 只有右子树上的所有结点 ② 只有右子树上的部分结点

③ 只有左子树上的部分结点 ④ 只有左子树上的所有结点

三、应用题

1． 设一棵树的二元组形式表示为{(A，B) ，(A，C) ，(A，D) ，(B，E) ，(C，F) ，(C，G)}，要求用孩子兄弟表

示法表示出该树的存储结构并将该树转化为对应的二叉树。

2． 根据5个叶子结点的权值集合{3、6、9、2、5}构成一棵哈夫曼树并计算这棵哈夫曼树的带权路径长度。

四、算法设计题

typedef struct node {int data; struct node *lchild; struct node *rchild;} bitree;

1. 设计复制一棵二叉树的算法。

2. 设计判断两个二叉树是否等价的算法。

3. 设计层次遍历二叉树中所有结点的算法。

4. 设计统计二叉树中叶子结点总数的算法。

5. 设计交换二叉树中所有结点左右子树的算法。

6. 建立一棵二叉树的链式存储结构的算法。

第六章 图

一、填空题

1． 设无向图G 中的顶点数为n ，则图G 中最少有_____0___条边，最多有___n(n-1)/2_____条边；设有向图G

中的顶点数为n ，则图G 中最少有____0____条边，最多有___n(n-1)_____条边。

2． 设无向图G 中有n 个顶点和e 条边，用邻接矩阵作为存储结构时，则访问任何一个顶点的所有邻接点的时

间复杂度为_____O(n)_____；用邻接表作为存储结构时，则访问任何一个顶点的所有邻接点的平均时间复杂度为____O(e/n)______。

3． 设有向图G 有n 个顶点，采用邻接矩阵作为存储结构，则该矩阵中含有___n____个数组元素。

4． 设无向图G 中有e 条边且所有顶点的度数之和为m ，则m 与e 之间的关系为__m=2e___。

5． 设无向图G 中有n 个顶点和e 条边，则用邻接矩阵作为图的存储结构进行深度优先遍历或广度优先遍历的

时间复杂度为_____O(n)____；用邻接表作为图的存储结构进行深度优先遍历或广度优先遍历的时间复杂度为____O(n+e)_____；图的深度优先或广度优先遍历的空间复杂度为____O(n)________。

22

6． 设有向图G 有n 个顶点和e 条边且用邻接表作为存储结构，则进行拓补排序时的时间复杂度为

____O(n+e)______。

7． 在一个有向图G 中若有弧、和，则在图G 的拓扑序列中，顶点i ，j ，k 的相对次序为

___(i,j,k)_________。

8． 在有向图的邻接矩阵中，第i 行上非零元素个数之和等于顶点i 的_____出度____，第i 列上非零元素个数

之和等于顶点i 的_____入度____。

9． 设有向图G 的邻接表中第1条单链表中有结点2、5、4，第2条单链表中有结点3、5，第3条单链表中有

结点5，第4条单链表为空，第5条单链表中有结点4、3，则从该图中顶点1出发的深度优先遍历序列为_________1,2,3,5,4_________，广度优先遍历序列为____1,2,5,4,3________________。

10． 设用邻接矩阵作为图的存储结构，则用普里姆算法求连通图的最小生成树的时间复杂度为

____O(n)_________。

二、选择题

1．无向图的深度优先遍历算法类似于二叉树的（ 2 ）。

① 中序遍历 ② 先序遍历

③ 后序遍历 ④ 层次遍历

2．图的广度优先遍历算法类似于二叉树的（ 4 ）。

① 中序遍历 ② 先序遍历

③ 后序遍历 ④ 层次遍历

3．设无向图G 的二元组形式表示为G=（D ，R ），其中D={a，b ，c ，d ，e ，f}，R={(a，b) ，(a，e) ，(a，c) ，(b，e) ，(e，d) ，(d，f) ，(f，c)}，从顶点a 出发按深度优先遍历该图，则可以得到的一种顶点序列为（ 4 ）。 ① abecdf ② acfebd ③ aebcfd ④ aedfcb

4．设无向图G 中有e 条边且采用邻接表作为存储结构，则邻接表中有（ 3 ）表结点。

① e/2 ② e ③ 2e ④ n+e

5．连通具有n 个顶点的无向图至少需要（ 4 ）条边。

① n ② n+1 ③ n/2 ④ n-1

6．已知有向图G 的二元组形式表示为G=（D ，R ），其中D={1，2，3，4，5，6}，R={，，，，，，}，，则由图G1得到的一种拓扑排序序列为（ 1 ）。

① v1，v4，v6，v2，v5，v3 ② v1，v2，v3，v4，v5，v6

③ v1，v4，v2，v3，v6，v5 ④ v1，v2，v4，v6，v3，v5

7．设强连通图G 有n 个顶点，则该图至少有（ 1 ）条边。

① n ② n+1 ③ n(n-1) ④ n-1

8．关键路径是AOE 网中的（ 1 ）。

① 从源点到汇点的最长路径 ② 最长的回路

③ 从源点到汇点的最短路径 ④ 最短的回路

2

⎛∞4∞85⎫ ⎪4∞1∞1 ⎪

三、已知无向图G 的邻接矩阵 ∞1∞82⎪，按要求完成下列各题。 ⎪ 8∞8∞6⎪ ⎪5126∞⎝⎭

1． 给出无向图G 中各顶点的度数；

2． 给出无向图G 的邻接表；

3． 分别给出应用Kruskal 和Prim 算法构造最小生成树的过程。

四、算法设计题

1． 设计图的深度优先遍历算法（用邻接表作为存储结构）。

2． 设计图的广度优先遍历算法（用邻接矩阵作为存储结构）。

3． 设计将无向图的邻接矩阵转化成无向图的邻接表的算法。

第七章 排序

一、填空题

1. 对一组记录关键字（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，从后向前为寻找插入位置需要比较____3___次。

2. 在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取d 1=4，d 2=2，则第二趟排序后的结果为__(15,20,50,40,,60,45,80,70,95)__________________________。

3. 在对一组记录关键字（50，40，95，20，80，70，60，45，15）进行冒泡排序时，第一趟需要进行相邻记录的交换次数为______7_____，在整个排序过程中需要进行______8____趟才能完成。

4. 在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行快速排序时，若以第一个关键字50作为基准记录，则第一趟排序后的结果为___(45,40,15,20,50,70,60,95,80)________________。

5. 在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行简单选择排序时，第4趟排序后的结果为___(15,20,40,45,50,70,60,95,80)______________________。

6. 在直接插入和简单选择排序中，若初始记录关键字基本有序，则选用____直接插入排序_______排序，若初始记录关键字基本反序，则选用______简单选择排序______排序。

7. 在对一组记录关键字（50，40，95，20，15，70，60，45，80）进行堆排序时，则根据这组记录关键字构成的初始堆为____(15,20,60,45,40,70,95,50,80)_____________________。

8. 在堆排序过程中，由n 个待排序的记录关键字建成初始堆需要进行______n/2_____次筛选；由初始堆到堆排序结束需要进行______n-1_____次筛选，每次筛选时对记录关键字进行比较的数量级为__________；堆排序算法的时间复杂度为___O(nlog2n)_______。

9. 在堆排序和快速排序中，若原始记录关键字接近正序或反序，则最好选用___堆排序_____排序，若原始记录关键字无序，则最好选用_____快速排序____排序。

10. 在归并排序中，若待排序的记录关键字个数为20，则需要进行___5_______趟归并，在第三趟归并中是把长度为_____4_____的有序表归并成长度为____8______的有序表。

11. 在堆排序、快速排序和归并排序中，若从节省存储空间的角度考虑，则首先选取_____堆排序_______方法，其次选择_______快速排序______方法；若从平均情况下速度最快的角度考虑，则选择______快速排序______方法。

12. 从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列中的正确位置上，此方法称为_____插入排序______；从未排序序列中挑选元素，并将其放入已排序序列的一端，此方法称为_____选择排序______；依次将每两个相邻的有序表合并成一个有序表的排序方法叫做_____归并排序______；当两个元素比较出现反序时就相互交换位置的排序方法叫做______交换排序______。

13. 快速排序的平均时间复杂度为_____O(nlog2n)______，空间复杂度为_____O(log2n)_______；快速排序的最坏时间复杂度为____O(n2)______，空间复杂度为____O(n)_____。

14. 堆中的所有非叶子结点R i 与该结点的左右孩子结点R 2i 和R2i+1之间的关系是_____________________________。

15. 设初始记录关键字序列（502，87，513，64，902，170，897），则利用基数排序思想经过第一趟的分配和回收后的结果序列为________(170,502,902,513,64,87,897)_______________________。

二、选择题

1．直接插入排序和冒泡排序的时间复杂度为（ 2 ）。

2① O(n) ② O(n) ③ O(log2n) ④ O(nlog2n)

2．简单选择排序的时间复杂度为（ 2 ）。

① O(n) ② O(n2) ③ O(log2n) ④ O(nlog2n)

3．已知一组记录关键字（45，80，55，40，42，85），则利用快速排序的方法，以第一个记录关键字作为基准而得到的一次划分结果是（ 3 ）。

① （40，42，45，55，80，85） ② （42，40，45，80，85，55）

③ （42，40，45，55，80，85） ④ （42，40，45，85，55，80）

4．每次将待排序的元素划分为左右两个子区间，其中左区间中所有元素的关键字均小于基准元素的关键字，右区间中所有元素的关键字均大于等于基准元素的关键字，则此排序的方法叫做（ 2 ）。

① 堆排序 ② 快速排序 ③ 冒泡排序 ④ 希尔排序

5．设一组记录关键字为（25，50，15，35，80，85，20，40，36，70），其中含有5个长度为2的有序表，则用归并排序的方法对该序列进行一趟归并后的结果为（ 1 ）。

① 15，25，35，50，20，40，80，85，36，70

② 15，25，35，50，80，20，85，40，70，36

③ 15，25，35，50，80，85，20，36，40，70

④ 15，25，35，50，80，20，36，40，70，85

6．根据一组记录关键字（45，80，55，40，42，85）建立的初始堆为（ 2 ）。

① （80，45，55，40，42，85） ② （85，80，55，40，42，45）

③ （85，80，55，45，42，40） ④ （85，55，80，42，45，40）

7．下列（ 2 ）中比较关键字的次数与记录关键字的初始序列无关。

① 插入排序 ② 选择排序 ③ 冒泡排序 ④ 希尔排序

8．设待排序的记录关键字序列基本有序，则下列（ 1 ）的效率最高。

① 插入排序 ② 选择排序 ③ 快速排序 ④ 归半排序

三、判断下列初始序列是否为堆，若不是堆则将它们调整为堆。

1. 100，85，95，75，80，60，82，40，20，10，65

2. 100，95，85，82，80，75，65，60，40，20，10

3. 100，85，40，75，80，60，65，95，82，10，20

四、算法设计题

1． 设计直接插入排序算法在链式存储结构上的实现。

2． 设计双向冒泡排序算法在顺序存储结构上的实现。

3． 设关键字序列（k 1，k 2，…，k n-1）是堆，设计算法将关键字序列（k 1，k 2，…，k n-1，x ）调整为堆。

第八章 查找

一、填空题

1. 假设在有序表R[0：19]上进行二分查找，则比较一次查找成功的结点数有______个，比较两次查找成功的结点数有________个，比较三次查找成功的结点数有_______个，比较四次查找成功的结点数有________个，比较五次查找成功的结点数有_______个，平均查找长度为_______。

2. 假设查找表R[0：11]中每个元素的查找概率相等，则对该查找表进行顺序查找的平均查找长度为_________，对该查找表进行二分查找的平均查找长度为____________。

3. 假设对线性表R[0：59]进行分块查找，共分10块，每块长度为6，利用顺序查找方法查找索引表和块，则查找每一个元素的平均查找长度为__________。

4. 在分块查找中，首先在_________中查找，然后再在_________中查找。分块查找的平均查找长度等于查找索引表的平均长度与查找相应子块的平均查找长度的________。

5. 对于长度为n 的线性表，若利用顺序查找方法，则时间复杂度为__________，若利用二分查找方法，则时间复杂度为____________，若利用分块查找方法，则时间复杂度为____________。（假定总块数和每块长度均接近n 的值）。

6. 设HASH 表中实际存储的数据元素个数为n ，HASH 表的长度为m ，则m 应________n，装填因子

α=__________。装填因子α的值越大，则存取元素时发生冲突的可能性就越_________，否则存取元素时发生冲突的可能性就越__________。

7. HASH 查找技术处理冲突的方法有____________和_____________两种。

8. 将一组关键字记录（18，34，58，26，75，67，48，93，81）映射到长度为11的散列表中。设散列函数为H （k ）=k %11，采用线性探测法解决冲突，则平均查找长度为__________，采用链地址法解决冲突，则平均查找长度为__________。

9. 在二叉排序树上查找元素的时间复杂度为_________，删除元素的时间复杂度为__________。

10. 在一棵二叉排序树上按_________遍历得到的序列是一个有序序列。

11. 采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分___________个结点为最佳。

12. 假设N 个关键字均具有相同的Hash 函数值，则用线性探测方法将这N 个关键字映射存储到Hash 表中时，共需要作__________________次探测。

二、选择题

1． 对顺序表进行二分查找时，要求顺序表必须满足的条件是______________。

① 以顺序存储方式存储 ② 以链式方式存储

③ 以顺序存储方式存储且数据元素有序 ④ 以链式方式存储且数据元素有序

2． 已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当利用二分查找方法查找值为90的元素时，总共需要和关键字比较____________次。

① 1 ② 2 ③ 3 ④ 4

3． 如果要求一个线性表既能够进行较快的插入和删除又能够反映数据元素之间的逻辑关系，则应该_____________。

① 以顺序方式存储 ② 以链式方式存储

③ 以散列方式存储 ④ 以上均可以

4． 设散列表的地址空间为R[0：m-1]，散列函数为H(k)=k mod P ，为了减少发生冲突的可能性，通常情况下最好选择P 为___________。

① 小于等于m 的最大奇数 ② 小于等于m 的最大素数

③ 小于等于m 的最大偶数 ④ 小于等于m 的最大合数

5． 散列函数将记录的关键字值转化为记录的存储地址，则选择好的______________是散列查找的关键。 ① 散列函数 ② 除余法中的质数

③ 冲突处理 ④ 散列函数和冲突处理

三、算法设计题

1． . 若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率，若找到指定结点则将该结点和

其前驱结点（如果存在）交换。设计在顺序存储结构上实现上述策略的顺序查找算法。

2． . 设计在链式存储结构上建立二叉排序树的算法。

3． . 设计判断一棵二叉树是否为二叉排序树的算法。

4． . 设计指定结点在二叉排序树中所在层次的算法。

5． . 设散列表采用线性探测解决冲突，设计在散列表中查找指定关键字的算法。

6． . 设散列表采用链地址法解决冲突，设计在散列表中查找指定关键字的算法。