数据结构精选习题及参考答案

习题1

一、单项选择题

1. 数据结构是指（ C ）。

A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义

2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ C ）。

A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3. 树形结构是数据元素之间存在一种（ C ）。

A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系

4. 设语句x++的时间是单位时间，则以下语句的时间复杂度为（ C ）。

for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++;

A.O(1)

B.O(n)

2 C.O(n)

D.O(n)

35. 算法分析的目的是（C），算法分析的两个主要方面是（B）。

（1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系

C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性

C.可读性和文档性 D.数据复杂性和程序复杂性 6. 计算机算法指的是（C），它具备输入，输出和（B）等五个特性。 （1） A.计算方法 B.排序方法

C.解决问题的有限运算序列 D.调度方法

（2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性

C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性

7. 数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（ B ）。

A.低 B.高 C.相同 D.不好说 8. 数据结构作为一门独立的课程出现是在（ ）年。

A.1946 B.1953 C.1964 D.1968 9. 数据结构只是研究数据的逻辑结构和物理结构，这种观点（ B ）。

A.正确 B.错误

C.前半句对，后半句错 D.前半句错，后半句对 10. 计算机内部数据处理的基本单位是（ B ）。

A.数据 B.数据元素 C.数据项 D.数据库 二、填空题

1. 数据结构按逻辑结构可分为两大类，分别是 线性结构 和 非线性结构 。 2. 数据的逻辑结构有四种基本形态，分别是___集合____、_____线性____、____树_____和_____图_____。 3. 线性结构反映结点间的逻辑关系是____一对一____的，非线性结构反映结点间的逻辑关系是____一对多或多对多____的。

4. 一个算法的效率可分为___时间___效率和____空间_____效率。

5. 在树型结构中，树根结点没有 前驱 结点，其余每个结点的有且只有________1__________个前趋驱结点；叶子结点没有_____后继_____结点；其余每个结点的后续结点可以________不止1个__________。

6. 在图型结构中，每个结点的前趋结点数和后续结点数可以_____有多个____。 7. 线性结构中元素之间存在_____一对一____关系；树型结构中元素之间存在_____一对多_____关系；图型结构中元素之间存在_____多对多_____关系。

8. 下面程序段的时间复杂度是____O(n^2)____。

for(i=0;i

A[i][j]=0;

9. 下面程序段的时间复杂度是__________________。

i=s=0; while(s

10. 下面程序段的时间复杂度是__________________。

s=0;

for(i=0;i

11. 下面程序段的时间复杂度是__________________。

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

12. 衡量算法正确性的标准通常是___程序对于精心设计的典型合法数据输入能得出符合要求的结果。___。

13. 算法时间复杂度的分析通常有两种方法，即__事后统计__和___事前估计__的方法，通常我们对算法求时间复杂度时，采用后一种方法。

三、求下列程序段的时间复杂度。

1. x=0;

for(i=1;i

2. x=0;

for(i=1;i

3. int i,j,k;

for(i=0;i

for(k=0;k

c[i][j]=a[i][k]*b[k][j]

}

4. i=n-1;

-2-

while((i>=0)&&A[i]!=k)) j--; return (i);

5. fact(n)

{ if(n<=1)

return (1);

else

return (n*fact(n-1)); }

习题1参考答案

一、单项选择题

1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B 二、填空题

1. 线性结构，非线性结构 2. 集合，线性，树，图 3. 一对一，一对多或多对多 4. 时间，空间

5. 前趋，一，后继，多 6. 有多个

7. 一对一，一对多，多对多 8. O(n2) 9. O(n) 10. O(n2) 11. O(log3n)

12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。 13. 事后统计，事前估计 三、算法设计题

1. O(n2) 2. O(n2) 3. O(n3) 4. O(n) 5. O(n)

-3-

习题2

一、单项选择题

1. 线性表是____A____。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空

2. 在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动 A 个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址____D____。

A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以

4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较____C____个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/2

5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是__D__。

A． p->next=s; s->prior=p;

p->next->prior=s; s->next=p->next; B． s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; C． p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; D． s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;

6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为____A____。

A．p->next=p->next->next; B．p=p->next; C．p=p->next->next; D．p->next=p;

7. 在一个长度为n的顺序表中向第i个元素(0< i

A．n-i B．n-i+l C．n-i-1 D．i

8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行 B A．s->next=p->next; p->next=s B．q->next=s; s->next=p

C．p->next=s->next; s->next=p D．p->next=s; s->next=q

9. 以下关于线性表的说法不正确的是___C___。

A．线性表中的数据元素可以是数字、字符、记录等不同类型。 B．线性表中包含的数据元素个数不是任意的。

C．线性表中的每个结点都有且只有一个直接前趋和直接后继。 D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。 10. 线性表的顺序存储结构是一种___B____的存储结构。

A．随机存取 B．顺序存取 C．索引存取 D．散列存取

11. 在顺序表中，只要知道___D____，就可在相同时间内求出任一结点的存储地址。 A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小

-4-

12. 在等概率情况下，顺序表的插入操作要移动___B___结点。 A．全部 B．一半 C．三分之一 D．四分之一 13. 在___C___运算中，使用顺序表比链表好。 A．插入 B．删除

C．根据序号查找 D．根据元素值查找

14. 在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。 A．O(1) B．O(n)

2

C．O(n) D．O(log2n)

15. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列____C______。 A．A, B, C, D, E B．B, C, D, E, A C．E, A, B, C, D D．E, D, C, B, A

16. 在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为___C___。

A．top不变 B．top=0 C．top-- D．top++ 17. 向一个栈顶指针为hs的链栈中插入一个s结点时，应执行___B___。 A．hs->next=s; B．s->next=hs; hs=s;

C．s->next=hs->next;hs->next=s; D．s->next=hs; hs=hs->next;

18. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为_______。

A．rear％n= = front B．（front+l）％n= = rear C．rear％n -1= = front D．(rear+l)％n= = front

19. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为____C____。

A．rear％n= = front B．front+l= rear

C．rear= = front D．(rear+l)％n= front

20. 在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为____A____。 A．front=front->next B．rear=rear->next C．rear=front->next D．front=rear->next 二、填空题

1. 线性表是一种典型的___线性___结构。

2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移__n-i+1__个元素。 3. 顺序表中逻辑上相邻的元素的物理位置____相邻____。

4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需____向前移动___一个位置，移动过程是从___前____向___后____依次移动每一个元素。

5. 在线性表的顺序存储中，元素之间的逻辑关系是通过___物理存储位置____决定的；在线性表的链接存储中，元素之间的逻辑关系是通过___链域的指针值____决定的。

6. 在双向链表中，每个结点含有两个指针域，一个指向____前驱___结点，另一个指向___后继____结点。

7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用__栈 （顺序）_____存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用___队列 （链接）____存储结构为宜。

8. 顺序表中逻辑上相邻的元素，物理位置___也____相邻，单链表中逻辑上相邻的元素，物理位置____不一定___相邻。 9. 线性表、栈和队列都是____线性___结构，可以在线性表的___任意___位置插入和删除元素；对于栈只能在___栈顶____位置插入和删除元素；对于队列只能在___队尾____位置插入元素和在____队首___位置删除元素。

10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为___单链表______和___双链表____；而根据

-5-

rear=p; } }

（2）删除（即出队）算法：

delete(LinkList *rear)

{ //设循环链队列的队尾指针为rear if (rear= =NULL) //空队 printf(\

if(rear->next= =rear) //队中只有一个结点 rear=NULL; else

rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点 }

8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) { int i;

if ( (*L).len>= maxlen) { printf(“overflow\ return(0); }

for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++; return(1); }

-11-

习题3

一、单项选择题

1. 空串与空格字符组成的串的区别在于（ B ）。

A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ D ）。

A.子串的最后那个字符在主串中的位置

B.子串的最后那个字符在主串中首次出现的位置 C.子串的第一个字符在主串中的位置

D.子串的第一个字符在主串中首次出现的位置 3. 下面的说法中，只有（ C ）是正确的。

A.字符串的长度是指串中包含的字母的个数 B.字符串的长度是指串中包含的不同字符的个数 C.若T包含在S中，则T一定是S的一个子串 D.一个字符串不能说是其自身的一个子串 4. 两个字符串相等的条件是（ D ）。

A.两串的长度相等 B.两串包含的字符相同

C.两串的长度相等，并且两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同 5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（ B ）。

A. “ijing” B. “jing＆” C. “ingNa” D. “ing＆N” 6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（ C ）。

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

7. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanjing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（ D ）。

A. “Nanjing＆Shanghai” B. “Nanjing＆Nanjing” C. “ShanghaiNanjing” D. “Shanghai＆Nanjing”

8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（ C ）。

A.i＞0 B. i≤n C.1≤i≤n D.1≤i≤n+1

9. 字符串采用结点大小为1的链表作为其存储结构，是指（ D ）。

A.链表的长度为1

B.链表中只存放1个字符 C.链表的每个链结点的数据域中不仅只存放了一个字符 D.链表的每个链结点的数据域中只存放了一个字符 二、填空题

1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___固定长度___，第二种是____设置长度指针____。 2. 两个字符串相等的充要条件是___字符串长度相等___和____对应位置上的字符相等_______________。

-12-

3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为____BCDEDE___。

4. 串是指____含n个字符的有限序列 （n≥0）____。

5. 空串是指____不含任何字符的字符串____，空格串是指____仅含空格字符的字符串_______________。 三、算法设计题

1. 设有一个长度为s的字符串，其字符顺序存放在一个一维数组的第1至第s个单元中（每个单元存放一个字符）。现要求从此串的第m个字符以后删除长度为t的子串，m

2. 设s和t是表示成单链表的两个串，试编写一个找出s中第1个不在t中出现的字符（假定每个结点只存放1个字符）的算法。

习题3参考答案

一、单项选择题 1．B

2．D

3．C

4．D

5．B

6．C

7．D

8．C

9．D

二、填空题

1. 固定长度，设置长度指针

2. 两个串的长度相等，对应位置的字符相等 3. “BCDEDE”

4. 含n个字符的有限序列 （n≥0）

5. 不含任何字符的串，仅含空格字符的字符串 三、算法设计题 1．算法描述为：

int delete(r,s,t,m) //从串的第m个字符以后删除长度为t的子串 char r[ ]; int s,t,m; { int i,j;

for(i=1;i<=m;i++)

r[s+i]=r[i]; for(j=m+t-i;j<=s;j++)

r[s-t+j]=r[j]; return (1); } //delete

2．算法思想为：

（1）链表s中取出一个字符；将该字符与单链表t中的字符依次比较；

（2）当t中有与从s中取出的这个字符相等的字符，则从t中取下一个字符重复以上比较； （3）当t中没有与从s中取出的这个字符相等的字符，则算法结束。

设单链表类型为LinkList；注意，此时类型 LinkList中的data成分为字符类型。

LinkString find(s,t) LinkString *s, *t; { LinkString *ps, *pt; ps=s;

while(ps!=NULL)

-13-

{ pt=t;

while((pt!=NULL)&&(ps->data!=pt->data)) pt=pt->next; if(pt= =NULL)

ps=NULL;

else

{ ps=ps->next;

s=ps;

} } return s; } //find

-14-

习题5

一、单项选择题

1. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ C ）个。

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

2. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ B ）个。 A. 15 B. 16 C. 17 D. 47 3. 假定一棵三叉树的结点数为50，则它的最小高度为（ C ）。 A. 3 B. 4 C. 5 D. 6 4. 在一棵二叉树上第4层的结点数最多为（ D ）。

A. 2 B. 4 C. 6 D. 8

5. 用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（ B ）。

A. R[2i+1] B. R[2i] C. R[i/2] D. R[2i-1]

6. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ D ）。 A. 24 B. 48 C. 72 D. 53 7. 线索二叉树是一种（ C ）结构。

A. 逻辑 B. 逻辑和存储 C. 物理 D. 线性 8. 线索二叉树中，结点p没有左子树的充要条件是（ B ）。 A. p->lc=NULL B. p->ltag=1 C. p->ltag=1 且p->lc=NULL D. 以上都不对

9. 设n , m 为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（ B ）。 A. n在m右方 B. n在m 左方 C. n是m的祖先 D. n是m的子孙

10. 如果F是由有序树T转换而来的二叉树，那么T中结点的前序就是F中结点的（ A ）。 A. 中序 B. 前序 C. 后序 D. 层次序

11. 欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（ A ）存储结构。 A. 三叉链表 B. 广义表 C. 二叉链表 D. 顺序 12. 下面叙述正确的是（ D ）。 A. 二叉树是特殊的树

B. 二叉树等价于度为2的树 C. 完全二叉树必为满二叉树 D. 二叉树的左右子树有次序之分

13. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（ A ）。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对

14. 已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（ C ）。 A. 1 B. 2 C. 3 D. 4

15. 根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（ AD ）。

A. 是完全二叉树 B. 不是完全二叉树 C. 是满二叉树 D. 不是满二叉树

-15-

二、判断题

1. 二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。 2. 二叉树的前序遍历中，任意结点均处在其子女结点之前。 3. 线索二叉树是一种逻辑结构。 4. 哈夫曼树的总结点个数（多于1时）不能为偶数。 5. 由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。 6. 树的后序遍历与其对应的二叉树的后序遍历序列相同。 7. 根据任意一种遍历序列即可唯一确定对应的二叉树。 8. 满二叉树也是完全二叉树。 9. 哈夫曼树一定是完全二叉树。 10. 树的子树是无序的。 三、填空题

1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为__3___，树的深度为___4__，终端结点的个数为___6___，单分支结点的个数为___1___，双分支结点的个数为__1____，三分支结点的个数为____2___，C结点的双亲结点为___A____，其孩子结点为___F____和____G___结点。

2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有___n+1____个。

3. 对于一个有n个结点的二叉树，当它为一棵____完全____二叉树时具有最小高度，即为___??log2(n?1)??____，当

（0 ）

（1 ） （× ） （1 ） （0 ） （0 ）√ （0 ）√ （1 ） （0 ） （1 ）×

它为一棵单支树具有____最大___高度，即为___n____。

4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___55。 5. 在一棵二叉排序树上按___中序____遍历得到的结点序列是一个有序序列。 6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为___n___个，其中___n-1____个用于链接孩子结点，___n+1____个空闲着。

7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=__n2+1____。

8. 一棵深度为k的满二叉树的结点总数为__2^k-1_____，一棵深度为k的完全二叉树的结点总数的最小值为__2^(k-1)___，最大值为__2^k-1____。

9. 由三个结点构成的二叉树，共有__6__种不同的形态。

10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为__2^(h-1)+1 2^h-1__。

11. 一棵含有n个结点的k叉树，___单支树___形态达到最大深度，__完全二叉树__形态达到最小深度。

12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。

13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。

14. 哈夫曼树是指_______带权路径长度最小______的二叉树。

15. 空树是指____结点数为0_____，最小的树是指_________只有一个根结点的树______________。 16. 二叉树的链式存储结构有____二叉链表_____和____三叉链表_____两种。 17. 三叉链表比二叉链表多一个指向____双亲结点____的指针域。 18. 线索是指____指向结点前驱和后继信息的指针______。

19. 线索链表中的rtag域值为__1___时，表示该结点无右孩子，此时___Rchild___域为指向该结点后继线索的指针。 20. 本节中我们学习的树的存储结构有_____________、___________和___________。 四、应用题

1. 已知一棵树边的集合为{，，，，，，，，，，

-16-

，，}，请画出这棵树，并回答下列问题：

（1）哪个是根结点？ （2）哪些是叶子结点？ （3）哪个是结点g的双亲？ （4）哪些是结点g的祖先？ （5）哪些是结点g的孩子？ （6）哪些是结点e的孩子？

（7）哪些是结点e的兄弟？哪些是结点f的兄弟？ （8）结点b和n的层次号分别是什么？ （9）树的深度是多少？

（10）以结点c为根的子树深度是多少？ 2. 一棵度为2的树与一棵二叉树有何区别。

3. 试分别画出具有3个结点的树和二叉树的所有不同形态？

4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。

5. 一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：

（1）各层的结点数目是多少？

（2）编号为n的结点的父结点如果存在，编号是多少？

（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？

（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？ 6. 找出所有满足下列条件的二叉树：

（1）它们在先序遍历和中序遍历时，得到的遍历序列相同； （2）它们在后序遍历和中序遍历时，得到的遍历序列相同； （3）它们在先序遍历和后序遍历时，得到的遍历序列相同；

7. 假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。 8. 假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。 9. 给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。 10．给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。 A G K L

C I B H M

D E F J O N

五、算法设计题

1. 一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。

2. 给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。

3. 写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。

4. 给定一棵二叉树，用二叉链表表示，其根指针为t，试写出求该二叉树中结点n的双亲结点的算法。若没有结点n或者该结点没有双亲结点，分别输出相应的信息；若结点n有双亲，输出其双亲的值。

图5-14

-17-

习题5参考答案

一、单项选择题

1. C 2. B 3. C 4. D 5. B 6. D 7. C 8. B 9. B 10. B 11. A 12. D 13. A 14. B 15. A 二、判断题

1.× 2.√ 3.× 4.√ 5.× 6.√ 7.√ 8.√ 9.× 10.× 三、填空题

1. 3，4，6，1，1，2，A，F，G 2. n+1

3. 完全，??log2(n?1)??，最大，n

4. 55 5. 中序

6. 2n，n-1，n+1 7. n2+1

8. 2k-1，2k-1，2k-1 9. 5 10. 2h-1

11. 单支树，完全二叉树

12. 2i，2i+1，i/2（或?i/2?） 13. 2n，n-1，n+1

14. 带权路径长度最小

15. 结点数为0，只有一个根结点的树 16. 二叉链表，三叉链表 17. 双亲结点

18. 指向结点前驱和后继信息的指针 19. 1，RChild

20. 孩子表示法，双亲表示法，长子兄弟表示法 四、应用题

1. 解答： 根据给定的边确定的树如图5-15所示。 a 其中根结点为a；

叶子结点有：d、m、n、j、k、f、l；

b c c是结点g的双亲；

a、c是结点g的祖先； d e

g f h j、k是结点g的孩子； i j k i m、n是结点e的子孙；

e是结点d的兄弟；

m n g、h是结点f的兄弟；

结点b和n的层次号分别是2和5； 图5-15

树的深度为5。 2. 解答： 度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。-18-

3. 解答： 略 4. 解答：

先序序列：ABDHIEJKCFLG 中序序列：HDIBJEKALFCG 后序序列：HIDJKEBLFGCA 5. 解答： （1）第i层上的结点数目是mi-1。

（2）编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。

（3）编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。

（4）编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。 6. 解答： （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。 7. 解答：后序序列：ACDBGJKIHFE 8. 解答：先序序列：ABCDGEIHFJK 9. 解答： 先根遍历：ABCDEFGHIJKLMNO 后根遍历：BDEFCAHJIGKNOML 森林转换成二叉树如图5-16所示。

10. 解答：构造而成的哈夫曼树如图5-17所示。

A

50 B G

30 20 C H K

五、算法设计题

1. 解答：这个问题可以用递归算法，也可用非递归算法，下面给出的为非递归算法。假设该完全二叉树的结点以层次为序，按照从上到下，同层从左到右顺序编号，存放在一个一维数组R[1..n]中，且用一个有足够大容量为maxlen的顺序栈作辅助存储，算法描述如下：

preorder (R) //先序遍历二叉树R int R[n]; { int root;

SqStack *s; //s为一个指针栈，类型为seqstack，其中包含top域和数组data s->top= -1; //s栈置空 root=1;

while ((root<=n) && (s->top>-1)) { while (root<=n) { printf(R[root]);

s->top++;

-19-

D E F J I M L 9 11 14 7 7 2 图5-17

16 N O 图5-16

5

} }

}

if (s->top>-1) //栈非空访问，遍历右子树 { root=s->data[s->top]*2+1; s->top--; }

s->data[s->top]=root; root=2*root;

2. 解答：考虑用一个顺序队que来保存遍历过程中的各个结点，由于二叉树以二叉链表存储，所以可设que为一个指向数据类型为bitree的指针数组，最大容量为maxnum，下标从1开始，同层结点从左到右存放。算法中的front为队头指针，rear为队尾指针。

levelorder (BiTree *t) //按层次遍历二叉树t { BiTree *que[maxnum]; int rear,front; if (t!=NULL)

{ front=0; //置空队列 rear=1; que[1]=t; do

{ front=front%maxsize+1; //出队 t=que[front]; printf(t->data);

if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1;

que[rear]=t->lchild; }

if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild;

}

}while (rear= =front); //队列为空时结束 } }

3. 解答：设该线索二叉树类型为bithptr，包含5个域：lchild，ltag，data，rchild，rtag。

insert(p, s) //将s结点作为p的右子树插入 BiThrNode *p,*s; { BiThrNode *q;

if (p->rtag= =1) //无右子树，则有右线索 { s->rchild=p->rchild; s->rtag=1; p->rchild=s; p->rtag=0; } else

{ q=p->rchild;

-20-

while(q->ltag= =0) //查找p所指结点中序后继，即为其右子树中最左下的结点

q=q->lchild; q->lchild=p->rchild; s->rtag=0; p->rchild=s; }

s->lchild=p; //将s结点的左线索指向p结点 s->ltag=1; }

4. 解答：利用一个队列来完成，设该队列类型为指针类型，最大容量为maxnum。算法中的front为队头指针，rear为队尾指针，若当前队头结点的左、右子树的根结点不是所求结点，则将两子树的根结点入队，否则，队头指针所指结点即为结点的双亲。

parentjudge(t,n) BiTree *t; int n;

{ BiTree *que[maxnum]; int front,rear; BiTree *parent; parent=NULL; if (t)

if (t->data= =n)

printf(“no parent!”); //n是根结点，无双亲 else

{ front=0; //初始化队列

rear=1;

que[1]=t; //根结点进队 do

{ front=front%maxsize+1; t=que[front];

if((t->lchild->data= =n)|| (t->rchild->data= =n)) //结点n有双亲 { parent=t; front=rear;

printf(“parent”,t->data); } else

{ if (t->lchild!=NULL) //左子树的根结点入队 { rear=rear%maxsize+1; }

}while(rear= =front); //队空时结束

if (parent = =NULL)

-21-

}

if (t->rchild!=NULL) //右子树的根结点入队 { rear=rear%maxsize+1; que[rear]=t->rchild; }

que[rear]=t->lchild;

} }

printf(“结点不存在”);

-22-

习题6

一、单项选择题

1. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为( A )。

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

2. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的度数之和为( D )。

A. s B. s-1 C. s+1 D. 2s

3. 在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数之和为( D )。

A. n B. e C. n+e D. 2e

4. 在一个具有n个顶点的无向完全图中，所含的边数为( C )。

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

5. 在一个具有n个顶点的有向完全图中，所含的边数为( )。

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

6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。

A. k B. k+1 C. k+2 D. 2k

7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为( )。

A. 0 B. 1 C. n D. n+1

8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须调用( )次深度优先搜索遍历的算法。

A. k B. 1 C. k-1 D. k+1

9. 若要把n个顶点连接为一个连通图，则至少需要( )条边。

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

10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为( )。

A. n B. n?e C. e D. 2?e

11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为( )。

A. n B. n?e C. e D. 2?e

12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为( )。

A. n B. n?e C. e D. 2?e

13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为( )。

A. n B. 2n C. e D. 2e

14. 在一个无权图的邻接表表示中，每个边结点至少包含( )域。

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

15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链表中的边结点数为( )。

A. k1 B. k2 C. k1-k2 D. k1+k2

16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单链表中的边结点数为( )。

A. k1 B. k2 C. k1-k2 D. k1+k2

17. 对于一个无向图，下面( )种说法是正确的。

A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和 C. 每个顶点的入度为0 D. 每个顶点的出度为0

18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的( )。

A. 出边数 B. 入边数 C. 度数 D. 度数减1

19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为( )。

-23-

A. A,B,C,F,D,E B. A,C,F,D,E,B C. A,B,D,C,F,E D. A,B,D,F,E,C

20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为( )。

A. A,B,C,D,E,F B. A,B,C,F,D,E C. A,B,D,C,E,F D. A,C,B,F,D,E

21. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行深度优先搜索，得到的顶点序列可能为( )。

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

22. 若一个图的边集为{<1,2>,<1,4>,<2,5>,<3,1>,<3,5>,<4,3>}，则从顶点1开始对该图进行广度优先搜索，得到的顶点序列可能为( )。

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

23. 由一个具有n个顶点的连通图生成的最小生成树中，具有( )条边。

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

24. 已知一个有向图的边集为{,,,,,}，则由该图产生的一种可能的拓扑序列为( )。

A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e 二、填空题

1. 在一个图中，所有顶点的度数之和等于所有边数的____2____倍。

2. 在一个具有n个顶点的无向完全图中，包含有____n(n-1)/2____条边，在一个具有n个顶点的有向完全图中，包含有____n(n-1)____条边。

3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{, , , , , }，则出度为0的顶点个数为________，入度为1的顶点个数为________。

4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要___n-1_____条边。 5. 表示图的两种存储结构为__________和__________。 6. 在一个连通图中存在着____1____个连通分量。

7. 图中的一条路径长度为k，该路径所含的顶点数为___k+1_____。

8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。 9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为____n____?____n____。

10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为____2e____和____e____。

11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。

12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。

13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。

14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。

15. 一个图的边集为{,,,,,}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。

16. 图的____深度____优先搜索遍历算法是一种递归算法，图的____广度____优先搜索遍历算法需要使用队列。 17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为____n____和___n-1_____。 18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是____唯一____（唯一/不唯一）的。 19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__唯一__的。

20. 假定一个有向图的边集为{,,,,,}，对该图进行拓扑排序得到的顶点序列为

-24-

____aeacfb____。 三、应用题

1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。

注：每一种序列都是唯一的，因为都是在存储结构上得到的。

2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。 注：每一种序列都是唯一的，因为都是在存储结构上得到的。 0 0 1 2 1 4 6 5 3 4 5 7 9

8

6 2 3 7 8 (a)

(b)

图6-11

3. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。

4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 (a) (b)

图6-12

5. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。 6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。

60 V1 V3 50 45 52

42 65 V4 V7 V2

50 30 40 V5 V6

70 图6-13

7. 图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用Dijkstra算法，求从V0 到其余各顶点的最短路径。

V5 100 -25- 60 30 V0 V4 ∞ ∞ 10 ∞ 30 100 ∞ ∞ 5 ∞ ∞ ∞ 10

8. 图6-15给出了一个具有15个活动、11个事件的工程的AOE网，求关键路径。 v4 a3=2 a7=6 v2 a1=3 a4=1 v7 a8=8 a11=7 v1 v5 a9=4 a2=4 a5=3 v3 v8 v11 a6=5 a13=10 a12=4 a15=6 v6 v10 a10=2 v9 a14=101

图6-15

四、算法设计题

1. 编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 int degree1(Graph & ga, int numb)

2. 编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数。 int degree2(Graph & ga, int numb)

3. 编写一个算法，求出邻接表表示的无向图中序号为numb的顶点的度数。 int degree3(GraphL & gl, int numb)

4. 编写一个算法，求出邻接表表示的有向图中序号为numb的顶点的度数。 int degree4(GraphL & gl, int numb)

习题6参考答案

一、单项选择题

1. A 2. D 3. D 4. C 5. B 6. B 7. B 8. A 9. C 10. D 11. C 12. D 13. A 14. B 15. B B 20. D 21. A 22. C 23. B 24. A 二、填空题

1. 2 2. n(n-1)/2，n(n-1) 3. 2，4 4. n-1

17. A 19.

-26-

16. C 18. A

5. 邻接矩阵，邻接表 6. 1 7. k+1 8. 3

9. n，n 10. 2e，e 11. 出边，入边 12. O（n），O（e/n）

13.O（n2

），O（n+e） 14. acdeb，acedb （答案不唯一） 15. acfebd，acefbd （答案不唯一） 16. 深度，广度 17. n，n-1 18. 唯一

19. 唯一 20. aebdcf（答案不唯一） 三、应用题

1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9 广度优先搜索序列：0,1,4,2,7,3,8,6,5,9 2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2 广度优先搜索序列：0,4,3,1,7,5,6,2,8 3. 深度优先搜索序列：0,2,3,5,6,1,4 广度优先搜索序列：0,2,3,5,6,1,4 4. 深度优先搜索序列：0,3,6,4,1,5,2 广度优先搜索序列：0,3,2,6,5,4,1 5. 过程如图6-16所示 60 V1 50 V1 V3 V1 V3 50 V3 52 45 65 42 V2 V2 V4 V7 50 V4 V7 V2 V4 V7 40 30 V5 70 V6 V5 V6 V5 V6 (a)

(b) (c) 50 V1 V3 50 V1 V3 50 V1 V3 V2 V4 V7 V2 V4 V7 V2 V4 V7 50 50 30 40 V5 V6 40 V5 V6 40 V5 V6

(d) (e)

(f) 50 V1 V3 V1 V3

V2 V4 42 50 45 V7 42 40 50 30 V2 V4 V7 50

V5 V6 40 30 V5 V6 (g) (h)

图6-16 6. 求解过程如图6-17所示。 V1 V3 V1 V3 V1 V3 V2 V4 V7 V2 V4 V7 V2 V4 42 V7

30

V5 30 V6 40 V5 V6 40 V5 30 V6 (a)

(b)

(c)

-27-

V1 V3 V3 45 50 V1 42 45 50 V1 V3 45 V2 V4 42 V7 V2 V4 V7 V2 40 30 40 50 V4 42 V7 V5 V6 V5 30 V6 40 V5 30 V6 (d) (e)

(f)

图6-17

7. 求解过程如下表所示。 终点 从v0到各终点的D值和最短路径的求解过程 i=1 i=2 i=3 i=4 i=5 V1 ∞ ∞ ∞ ∞ ∞ 无 V2 10 (v0,v2) V3 ∞ 60 50 (v0,v2,v3) (v0,v4,v3) V4 30 30 (v0,v4) (v0,v4) V5 100 100 90 60 (v0,v5) (v0,v5) (v0,v4,v5) (v0,v4,v3,v5) Vj V2 V4 V3 V5 S {v0,v2} {v0,v2,v4} {v0,v2,v3,v4} {v0,v2,v3,v4,v5} 8. 求解过程如下：

①事件的最早发生时间ve[k]。 ve (1)=0 ve (2)=3 ve (3)=4

ve (4)=ve(2)+2=5

ve (5)=max{ve(2)+1,ve(3)+3}=7 ve (6)=ve(3)+5=9

ve (7)=max{ve(4)+6,ve(5)+8}=15 ve (8)=ve(5)+4=11

ve (9)=max{ve(8)+10,ve(6)+2}=21 ve (10)=max{ve(8)+4,ve(9)+1}=22 ve (11)=max{ve(7)+7,ve(10)+6}=28

②事件的最迟发生时间vl[k]。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21

vl (8)=min{ vl (10)-4, vl (9)-10}=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19

vl (5)=min{ vl (7)-8,vl (8)-4}=7

-28-

vl (4)= vl (7)-6=15

vl (3)=min{ vl (5)-3, vl (6)-5}=4 vl (2)=min{ vl (4)-2, vl (5)-1}=6 vl (1)=min{vl (2)-3, vl (3)-4}=0

③活动ai的最早开始时间e[i]和最晚开始时间l[i]。

活动a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活动a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活动a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活动a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活动a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活动a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活动a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活动a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活动a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活动a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活动a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活动a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活动a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活动a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活动a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22

④最后，比较e[i]和l[i]的值可判断出a2,a5,a9,a13,a14,a15是关键活动，关键路径如图6-18所示。 v1 v5 a9=4 v11 a2=4 v3 a5=3 v8 a13=10 a15=6 v10 v9 a14=101

图6-18

四、算法设计题

1. int degree1(Graph & ga, int numb)

{ //根据无向图的邻接矩阵求出序号为numb的顶点的度数 int j,d=0;

for(j=0; j

if (ga.cost[numb][j]!=0 && ga.cost[numb][j]!=MAXINT)

d++;

return (d); }

2. int degree2(Graph & ga, int numb)

//根据有向图的邻接矩阵求出序号为numb的顶点的度数 { int i,j,d=0;

//求出顶点numb的出度

-29-

for(j=0; j

if(ga.cost[numb][j]!=0 && ga.cost[numb][j]!=MAXINT)

d++;

//求出顶点numb的入度 for(i=0; i

d++; //返回顶点numb的度 return (d); }

3. int degree3(GraphL & gl, int numb)

//根据无向图的邻接表求出序号为numb的顶点的度数 { int d=0;

vexnode * p=gl.adjlist[numb]; while(p!=NULL) { d++; p=p->next;

} return (d); }

4. int degree4(GraphL & gl, int numb)

//根据有向图的邻接表求出序号为numb的顶点的度数 { int d=0, i;

vexnode * p=gl.adjlist[numb]; while (p!=NULL) { d++; p=p->next;

} //求出顶点numb的出度 for(i=0; i

{ if(p->vertex= =numb) d++;

p=p->next; }

}//求出顶点numb的入度

return (d); //返回顶点numb的度数 }

-30-

习题7

一、单项选择题

1. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为( )。

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

2. 对于长度为9的顺序存储的有序表，若采用折半查找，在等概率情况下的平均查找长度为( )的9分之一。

A. 20 B. 18 C. 25 D. 22

3. 对于长度为18的顺序存储的有序表，若采用折半查找，则查找第15个元素的比较次数为( )。

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

4. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为( )。

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

5. 对具有n个元素的有序表采用折半查找，则算法的时间复杂度为( )。

2

A. O(n) B. O(n) C. O(1) D. O(log2n)

6. 在索引查找中，若用于保存数据元素的主表的长度为n，它被均分为k个子表，每个子表的长度均为n/k，则索引查找的平均查找长度为( )。

A. n+k B. k+n/k C. (k+n/k)/2 D. (k+n/k)/2+1

7. 在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。

A. 13 B. 24 C. 12 D. 79

8. 从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时间复杂度大致为( )。

2

A. O(n) B. O(1) C. O(log2n) D. O(n)

9. 从具有n个结点的二叉排序树中查找一个元素时，在最坏情况下的时间复杂度为( )。

2

A. O(n) B. O(1) C. O(log2n) D. O(n)

10. 在一棵平衡二叉排序树中，每个结点的平衡因子的取值范围是( )。

A. -1?1 B. -2?2 C. 1?2 D. 0?1

11. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K计算哈希地址，则元素64的哈希地址为( )。

A. 4 B. 8 C. 12 D. 13

12. 若根据查找表(23,44,36,48,52,73,64,58)建立哈希表，采用h(K)=K%7计算哈希地址，则哈希地址等于3的元素个数( )。

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

13. 若根据查找表建立长度为m的哈希表，采用线性探测法处理冲突，假定对一个元素第一次计算的哈希地址为d，则下一次的哈希地址为( )。

A. d B. d+1 C. (d+1)/m D. (d+1)%m 二、填空题

1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为__(n+1)/2__，时间复杂度为___O(n)___。

2. 对长度为n的查找表进行查找时，假定查找第i个元素的概率为pi,查找长度（即在查找过程中依次同有关元素比较的总次数）为ci，则在查找成功情况下的平均查找长度的计算公式为________。

3. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________，在查找不成功情况下的平均查找长度________。

4. 以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于__ ?log2(n+1)?__的向上取整减1，

-31-

时间复杂度为__O(log2n)__。

5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成__顺序__存储的__有序__表。

6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。 7. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为________，最后一层的结点数为________。 8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为____________。 9. 在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为________。 10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。

11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。 12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续向________查找。

13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的________插入，若元素的值大于根结点的值，则接着向根结点的________插入。

14. 根据n个元素建立一棵二叉排序树的时间复杂度大致为________。

15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。

16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。

17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。

18. 在线性表的哈希存储中，装填因子?又称为装填系数，若用m表示哈希表的长度，n表示线性表中的元素的个数，则?等于________。

19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有________个，哈希地址为5的元素有________个。 三、应用题

1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。

2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。

3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。

元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 最终哈希地址

0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表

4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。 四、算法设计题

1. 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。

2. 试将折半查找的算法改写成递归算法。

-32-

习题7参考答案

一、单项选择题

1. D 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. A 10. A 11. C 12. B 13. D 二、填空题

n1. (n+1)/2, O(n) 2.

?pici

i?13. 20.5, 41 4. ?log2(n+1)?，O(log2n) 5. 顺序 有序 6. 1，3

7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于

11. 有序序列 12. 查找成功，左子树，右子树 13. 左子树，右子树 14. O(nlog2n) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 三、应用题

1. 折半查找判定树如图7-3所示，平均查找长度等于29/10。图7-3中的结点与有序表中元素的对应关系如下表所示。

5 2 8 1 2 3 4 5 6 7 8 9 10 1 3 6 7 15 26 34 39 45 56 58 63 74 76 4 9 10 图7-3

2. 二叉排序树如图7-4所示，平均查找长度等于32/10。

38

25 52 16 30 74

68 90 54 72 图7-4

3. H(K)=K % 13平均查找长度为14/10，其余解答如下。

元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5 最终哈希地址 6 10 3 11 9 4 12 7 5 8

0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63 25

4. H(K)=K % 11，哈希表如图7-5所示，平均查找长度17/12。

-33-

0

∧

四、算法设计题

图7-5

1. 设计思路：进入判别算法之前，pre取初值为min(小于树中任一结点值)，fail=FALSE,即认为bt是二叉排序树。按中序遍历bt，并在沿向根结点，与前趋比较，若逆序，则fail为TRUE,则bt不是二叉排序树。

void bisorttree(bitree bt,keytype pre, bool &fail)

{ //fail初值为FALSE，若非二叉序树，则fail值TRUE if (!fail) { if (bt)

{ bisosrttree(bt->lchild,pre,fail); //判断左子树 if (bt->data_key

{ pre=bt->data_key;

bisorttree(bt->rchild,pre,fail); //判断右子树 } } }

} //bisorttree

说明：较为直观的方法，可套用中序遍历非递归算法。 2. int search_bin(SeqTable st , keytype k , int low , int high)

{ if (low

{ mid=(low+high)/2;

if (k= =st.elem[mid].key) return (mid) ; //成功 else

if (k

-34-

习题8

一、单项选择题

1. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（ ）。

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

2. 若对n个元素进行直接插入排序，则进行任一趟排序的过程中，为寻找插入位置而需要的时间复杂度为（ ）。

2

A. O(1) B. O(n) C. O(n) D. O(log2n)

3. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。

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

4. 对n个元素进行直接插入排序时间复杂度为（ ）。

2

A. O(1) B. O(n) C. O(n) D. O(log2n)

5. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换。 A. n B. n-1 C. n+1 D. n/2

6. 在对n个元素进行冒泡排序的过程中，最好情况下的时间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(n) 7. 在对n个元素进行冒泡排序的过程中，至少需要（ ）趟完成。 A. 1 B. n C. n-1 D. n/2

8. 在对n个元素进行快速排序的过程中，若每次划分得到的左、右两个子区间中元素的个数相等或只差一个，则整个排序过程得到的含两个或两个元素的区间个数大致为（ ）。

A. n B. n/2 C. log2n D. 2n

9. 在对n个元素进行快速排序的过程中，第一次划分最多需要移动（ ）次元素，包括开始把支点元素移动到临时变量的一次在内。

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

10. 在对n个元素进行快速排序的过程中，最好情况下需要进行（ ）躺。 A. n B. n/2 C. log2n D. 2n

11. 在对n个元素进行快速排序的过程中，最坏情况下需要进行（ ）躺。 A. n B. n-1 C. n/2 D. log2n

12. 在对n个元素进行快速排序的过程中，平均情况下的时间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)

13. 在对n个元素进行快速排序的过程中，最坏情况下的时间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)

14. 在对n个元素进行快速排序的过程中，平均情况下的空间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n) 15. 在对n个元素进行直接插入排序的过程中，算法的空间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)

16. 对下列四个序列进行快速排序，各以第一个元素为基准进行第一次划分，则在该次划分过程中需要移动元素次数最多的序列为（ ）。

A. 1, 3, 5, 7, 9 B. 9, 7, 5, 3, 1 C. 5, 3, 1, 7, 9 D. 5, 7, 9, 1, 3 17. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。 A. 2 B. 3 C. 4 D. 5

18. 在对n个元素进行简单选择排序的过程中，需要进行（ ）趟选择和交换。

-35-

A. n B. n+1 C. n-1 D. n/2 19. 在对n个元素进行堆排序的过程中，时间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n) 20. 在对n个元素进行堆排序的过程中，空间复杂度为（ ）。

2

A. O(1) B. O(log2n) C. O(n) D. O(nlog2n)

21. 假定对元素序列（7, 3, 5, 9, 1, 12）进行堆排序，并且采用小根堆，则由初始数据构成的初始堆为（ ）。 A. 1, 3, 5, 7, 9, 12 B. 1, 3, 5, 9, 7, 12 C. 1, 5, 3, 7, 9, 12 D. 1, 5, 3, 9, 12, 7

22. 假定一个初始堆为(1, 5, 3, 9, 12, 7, 15, 10)，则进行第一趟堆排序后得到的结果为（ ）。 A. 3, 5, 7, 9, 12, 10, 15, 1 B. 3, 5, 9, 7, 12, 10, 15, 1 C. 3, 7, 5, 9, 12, 10, 15, 1 D. 3, 5, 7, 12, 9, 10, 15, 1 23. 若对n个元素进行归并排序，则进行归并的趟数为（ ）。

A. n B. n-1 C. n/2 D. ?log2n? 24. 若一个元素序列基本有序，则选用（ ）方法较快。 A. 直接插入排序 B. 简单选择排序 C. 堆排序 D. 快速排序

25. 若要从1000个元素中得到10个最小值元素，最好采用（ ）方法。 A. 直接插入排序 B. 简单选择排序 C. 堆排序 D. 快速排序

26. 若要对1000个元素排序，要求既快又稳定，则最好采用（ ）方法。 A. 直接插入排序 B. 归并排序 C. 堆排序 D. 快速排序

27. 若要对1000个元素排序，要求既快又节省存储空间，则最好采用（ ）方法。 A. 直接插入排序 B. 归并排序 C. 堆排序 D. 快速排序 28. 在平均情况下速度最快的排序方法为（ ）。

A. 简单选择排序 B. 归并排序 C. 堆排序 D. 快速排序 二、填空题

1. 每次从无序子表中取出一个元素，把它插入到有序子表中的适当位置，此种排序方法叫做__插入__排序；每次从无序子表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__选择_排序。

2．每次直接或通过支点元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做__快速__排序；每次使两个相邻的有序表合并成一个有序表的排序方法叫做__归并__排序。

2

3．在简单选择排序中，记录比较次数的时间复杂度为__O(n) __，记录移动次数的时间复杂度为___O(n)__。 4. 对n个记录进行冒泡排序时，最少的比较次数为__n-1__，最少的趟数为__1__。

2

5. 快速排序在平均情况下的时间复杂度为__ O(nlog2n)__，在最坏情况下的时间复杂度为___O(n) __。

6. 若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较________次。

7. 假定一组记录为(46,79,56,38,40,84)，则利用堆排序方法建立的初始小根堆为____________________。

8. 假定一组记录为(46,79,56,38,40,84)，在冒泡排序的过程中进行第一趟排序后的结果为____________________。 9. 假定一组记录为(46,79,56,64,38,40,84,43)，在冒泡排序的过程中进行第一趟排序时，元素79将最终下沉到其后第_______个元素的位置。

10. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，共需要________趟排序。

11. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的过程中，含有两个或两个以上元素的排序区间的个数为________个。

12. 假定一组记录为(46,79,56,25,76,38,40,80)，对其进行快速排序的第一次划分后，右区间内元素的个数为__________。 13. 假定一组记录为(46,79,56,38,40,80)，对其进行快速排序的第一次划分后的结果为____________________。

14. 假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第二趟归并后的子表个数为________________。

-36-

15. 假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，第三趟归并后的第2个子表为________________。

16. 假定一组记录为(46,79,56,38,40,80,46,75,28,46)，对其进行归并排序的过程中，供需要__________趟完成。 17. 在时间复杂度为O(nlog2n)的所有排序方法中，________排序方法是稳定的。

18. 在时间复杂度为O(n2

)的所有排序方法中，________排序方法是不稳定的。 19. 在所有排序方法中，________排序方法采用的是二分法的思想。

20. 在所有排序方法中，________方法使数据的组织采用的是完全二叉树的结构。 21. 在所有排序方法中，________方法采用的是两两有序表合并的思想。 22. ________排序方法使键值大的记录逐渐下沉，使键值小的记录逐渐上浮。 23. ________排序方法能够每次使无序表中的第一个记录插入到有序表中。 24. ________排序方法能够每次从无序表中顺序查找出一个最小值。 三、应用题

1. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用直接插入排序法进行排序时每一趟的排序结果。 2. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用冒泡排序法进行排序时每一趟的排序结果。 3. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用快速排序法进行排序时每一趟的排序结果。 4. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用简单选择排序法进行排序时每一趟的排序结果。 5. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用堆排序法进行排序时每一趟的排序结果。

6. 已知一组记录为(46,74,53,14,26,38,86,65,27,34)，给出采用归并排序法进行排序时每一趟的排序结果。 四、算法设计题

1. 编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。 2. 试以单链表为存储结构实现简单选择排序的算法。

习题8参考答案

一、单项选择题

1. D 2. B 3. C 4. C 5. B 6. D 7. A 8. B 9. D 10. C 11. B 12. D 13. C 14. D 15. A 16. D 17. B 18. C 20. A 21. B 22. A 23. D 24. A 25. B 26. B 27. C 28. D 二、填空题

1. 插入，选择 2. 快速，归并 3. O(n2)，O(n) 4. n-1，1 5. O(nlog2n)，O(n2) 6. 4

7. (38,40,56,79,46,84) 8. (46,56,38,40,79,84) 9. 4 10. 3

11. 4 12. 4 13．[40 38] 46 [56 79 80] 14．3 15. [28 46] 16. 4 17. 归并 18. 直接选择 19. 快速 20. 堆排序 21. 归并排序 22. 冒泡 23. 直接插入 24. 直接选择 三、应用题 1.

D -37-

19.

(0) [46] 74 53 14 26 38 86 65 27 34 (1) [46 74] 53 14 26 38 86 65 27 34 (2) [46 53 74] 14 26 38 86 65 27 34 (3) [14 46 53 74] 26 38 86 65 27 34 (4) [14 26 46 53 74] 38 86 65 27 34 (5) [14 26 38 46 53 74] 86 65 27 34 (6) [14 26 38 46 53 74 86] 65 27 34 (7) [14 26 38 46 53 65 74 86] 27 34 (8) [14 26 27 38 46 53 65 74 86] 34 (9) [14 26 27 34 38 46 53 65 74 86] 2.

(0) [46 74 53 14 26 38 86 65 27 34] (1) [46 53 14 26 38 74 65 27 34] 86 (2) [46 14 26 38 53 65 27 34] 74 86 (3) [14 26 38 46 53 27 34] 65 74 86 (4) [14 26 38 46 27 34] 53 65 74 86 (5) [14 26 38 27 34] 46 53 65 74 86 (6) [14 26 27 34] 38 46 53 65 74 86 (7) [14 26 27 34] 38 46 53 65 74 86 3.

(0) [46 74 53 14 26 38 86 65 27 34] (1) [34 27 38 14 26] 46 [86 65 53 74] (2) [26 27 14] 34 38 46 [74 65 53] 86 (3) 14 26 27 34 38 46 [53 65] 74 86 (4) 14 26 27 34 38 46 53 65 74 86 4.

(0) [46 74 53 14 26 38 86 65 27 34] (1) 14 [74 53 46 26 38 86 65 27 34] (2) 14 26 [53 46 74 38 86 65 27 34] (3) 14 26 27 [46 74 38 86 65 53 34] (4) 14 26 27 34 [74 38 86 65 53 46] (5) 14 26 27 34 38 [74 86 65 53 46] (6) 14 26 27 34 38 46 [86 65 53 74] (7) 14 26 27 34 38 46 53 [65 86 74] (8) 14 26 27 34 38 46 53 65 [86 74] (9) 14 26 27 34 38 46 53 65 74 [86] 5. 构成初始堆（即建堆）的过程：

1 2 3 4 5 6 7 8 9 10 (0) 46 74 53 14 26 38 86 65 27 34 (1) 46 74 53 14 26 38 86 65 27 34 (2) 46 74 53 14 26 38 86 65 27 34 (3) 46 74 38 14 26 53 86 65 27 34 (4) 46 14 38 27 26 53 86 65 74 34 (5) 14 26 38 27 34 53 86 65 74 46 进行堆排序的过程：

(0) 14 26 38 27 34 53 86 65 74 46

-38-

(1) 26 27 38 46 34 53 86 65 74 [14] (2) 27 34 38 46 74 53 86 65 [26 14] (3) 34 46 38 65 74 53 86 [27 26 14] (4) 38 46 53 65 74 86 [34 27 26 14] (5) 46 65 53 86 74 [38 34 27 26 14] (6) 53 65 74 86 [46 38 34 27 26 14] (7) 65 86 74 [53 46 38 34 27 26 14] (8) 74 86 [65 53 46 38 34 27 26 14] (9) 86 [74 65 53 46 38 34 27 26 14] 6.

(0) [46] [74] [53] [14] [26] [38] [86] [65] [27] [34] (1) [46 74] [14 53] [26 38] [65 86] [27 34] (2) [14 46 53 74] [26 38 65 86] [27 34] (3) [14 26 38 46 53 65 74 86] [27 34] (3) [14 26 27 34 38 46 53 65 74 86] 四、算法设计题 1.

void Bubble_Sort2(int a[ ],int n) //相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1;

while (low

for(i=low;ia[i+1]) { a[i]<->a[i+1]; change=1; }

high--; //修改上界

for (i=high;i>low;i--) //从下向上起泡 if (a[i]a[i-1]; change=1; }

low++; //修改下界 }//while }//Bubble_Sort2

2.

void LinkList_Select_Sort(LinkList &L) //单链表上的简单选择排序算法 { for (p=L;p->next->next;p=p->next) { q=p->next; x=q->data;

for (r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点 if (r->next->datanext->data; s=r; }

if (s!=q) //找到了值比q->data更小的最小结点s->next

-39-

{ p->next=s->next; s->next=q; t=q->next; q->next=p->next->next; p->next->next=t;

} //交换q和s->next两个结点 }//for

}//LinkList_Select_Sort

-40-

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