数据结构习题

习题2

2.1选择题

（1）线性表是具有n个 __________的有限序列（n!=0）。 A.表元素 B.字符 C.数据元素 D.数据项

（2）顺序表的存储结构是一种__________的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.HASH存取

（3）在一个长度为n的顺序表中，向第i个元素（1<=i<=n+1）之前插入一个新元素时，需要向后移动____________个元素。

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

(4)链表是一种采用____________存储结构存储的线性表。 A.顺序 B链式 C.星式 D.网状

（5）下面关于线性表的叙述错误的是_____________。 A.线性表采用顺序存储方式，必须占用一片连续的存储空间 B.线性表采用链式存储方式，不必占用一片连续的存储空间 C.线性表采用链式存储方式，便于插入和删除操作的实现 D.线性表采用顺序存储方式，便于插入和删除操作的实现

（6）设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用____________存储方式最节省运算时间。

A.单项链表 B.单向循环链表 C.双向链表 D.双向循环链表

(7)设指针q指向单链表中的结点A，指针p指向单链表中的结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为____________。 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;

(8)设指针变量p指向单链表结点A，则删除结点A的后继结点B的操作为___________。 A.p->next=p->next->next B.P=P->next C.p=p->next->next D.P->next=p

(9)在一个以h为头的单循环链表中，p指针指向链尾的条件是__________. A.P->next=h B.p->next=NULL C.p->next->next=h D.p->data=-1

(10)对于只在首尾两端进行插入操作的线性表，宜采用的存储结构为___________。 A.顺序表 B.用头指针表示的单循环链表 C.单链表 D.用尾指针表示的单循环链表 2.2填空题

（1）线性表是n个元素的_____________________________。 （2）线性表的存储结构有______________________________。

（3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________________，在链式存储结构上实现顺序查找的平均时间复杂度为___________________。

（4）设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___________个数据元素；删除第i个位置上的数据元素需要移动表中___________个元素。 （5）若频繁地对线性表进行插入与删除操作，该线性表应采用_________________存储结构。 （6）链式存储结构中的结点包含________________域和_________________域。

（7）在双链表中，每个结点有两个指针域，一个指向____________，另一个指向_______________。

（8）对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为______________，在表尾插入时间的复杂度为_________________。

（9）设指针变量p指向单链表中的结点A，指针s指向被插入结点B，则在结点A的后面插入结点B的操作序列为_________________________________________________。

（10）设指针变量p指向单链表中的结点A，则删除结点A的后继结点（假设存在）的语句序列我为：

S=p->next; p->next=___________________；free(s)；

习题2参考答案 2.1选择题

(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D. 2.2.填空题 (1). 有限序列

(2). 顺序存储和链式存储 (3). Ｏ(n) O(n) (4). n-i+1 n-i (5). 链式

(6). 数据 指针 (7). 前驱 后继 (8). Ο(1) Ο(n)

(9). s->next=p->next; p->next=s ; (10). s->next

习题三 3.1选择题

1）下列说法正确的是（）

A.堆栈是在两端操作、先进后出的线性表 B.堆栈是在一端操作、先进先出的线性表 C.队列是在一端操作、先进先出的线性表 D.队列是在两端操作、先进先出的线性表 2）栈和队列的共同点是（） A.都是先进先出 B.都是先进先出

C.只允许在端点出插入和删除元素 D.没有共同点

3）以下数据结构中（）是非线性结构。 A.队列 B.栈

C.线性表 D.二叉树

4）若一个栈的入栈序列是1，2,3，，n。其输出序列为p1,p2,p3,?pn,,,p1=n,则pi为（） ?A. I B. N-i C. N-i+1 D. 不确定

5）当利用大小为N的一位素组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A.top++ B.Top-- C.Top=0 D.Top

6）4个元素s栈的顺序是A,B,C,D,经运算，pop(s)后栈顶元素是（） A. A B. B C. C D.D

7)一个栈的输入序列是a，b，c，d，e，则栈的不可能的输出序列是（） A. adcba B. decba C. dceab D. abcde 8)设输入序列是1,2,3，?n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（） A.n-i B.n-1-i C.n+1-i D.不能确定

9）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串

A.15 B.14 C.16 D.21

10)递归函数f(n)=f(n-1)+n(n>1)的递归出口是（） A.f(1)=0 B.f(1)=1 C.f(0)=1 D.f(n)=n

11)设指针变量top指向当前链式栈的栈顶，则删除栈顶的元素的操作序列为（） A.top=top+1 B.top=top-1

C.top->next=top D.top = top->next 12)中缀表达式A-(B+C/D)*E的后缀表达式是（） A.ABC+D/*E- B.ABCD/+E*- C.AB-C+D/E* D.ABC-+D/E*

13)用front和rear分别表示顺序循环队列的队首和队尾指针，判断队空的条件是（） A.front+1==rear B.(rear+1)%maxsize == front C.front==0 D.front==rear

14)判定一个循环队列QU（最多元素为m0）为满队列的条件是（） A.QU->front==QU->rear B.QU->front!=QU->rear

C.QU->front==（QU->rear+1）%m0 D.QU->front!=（QU->rear+1）%m0

15）设栈s和队列Q的初始状态为空。元素E1，E2,E3,E4,E5和E6依次通过栈S，一个元素出栈后即进入队列Q。若6个元素出列的顺序为E2，E4，E3,E6，E5和E1。则栈S的容量至少应该是（）

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

16）用链接式存储的队列。在进行插入运算时，（） A.仅修改头指针

B.头、尾指针都要修改 C.仅修改尾指针

D.头、尾指针可能都要修改

17）若用一个大小为6的数组实现循环队列，且当前rear和front的值分别为0和3.当从队列中删除一个元素再加入两个元素后。Rear 和front 的值分别为（） A.1和5 B.2和4 C.4和2 D.5和1

18）设顺序循环队列Q[0;M-1]的头指针分别为F和R，头指针F总是指向头元素的前一位置。尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（） A.R-F B.F-R

C.(R-F+M)%M D.(F-R+M)%M

19)设指针变量front便是链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点x，则入队列的操作序列为（） A.front->next=s;front=s B.s-next=rear;rear=s C.rear=>next=s;rear=s D.s-next=front;rear=s

20)当利用大小为N的数组顺序存储的一个队列是，该队列的最大长度为（） A.n-2 B.n-1 C.n D.n+1 3.2填空题 1）栈的插入和删除只能在栈顶栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_______表；队列的插入和删除操作分别在队列的两端进行。先进队列的元素必定先出队列，所以又把队列称为_____表。

2）后缀算式9 2 3+ - 10 2 / -的值为_____中缀算式（3+4X）- 2Y/3 对应的后缀算式为____________________

3）下面程序段的功能实现数据X进栈，要求在下划线处填上真确的语句。 Typedef struct {int s [100]； int top;} sqstack Void push(sqstack & stack , int x ) {

If(stack.top==m-1) printf(“overflow”); Else{__________,___________;} }

4)设指针变量P指向双向循环链表中的结点X。则删除结点X需要执行的语句序列为_________________,_____________________,(设结点中的两个指针域分别为llink 和 rlink ). 5)设有一个顺序循环队列中有M个存储单元。则该循环队列中最多能够存储M-1个队列元素；当前实际存储________个队列元素（设头指针F指向当前队头元素的前一个位置，尾

指针指向当前队尾元素的位置）

6)设有一个顺序共享栈S[0；n-1]，其中第一个栈项指针top 1 的初值为-1，第二个栈顶指针top2 的初值为n，则判断共享栈满的条件是______________

7)设F和R分别表示顺序循环队列指针和尾指针，则判断该循环队列为空的条件为_______________

8)顺序循环队列判空的条件是（使用front,rear,n表示）_________ 9)顺序循环队列判满的条件是（使用front,rear,n表示）_________ 10)顺序循环队列MAXSIZE=N，最多可以存储____________元素 习题3参考答案 3.1.选择题

(1). D (2). C (3). D (4). C (5). B (6). C (7). C (8). C (9). B (10).AB

(11). D (12). B (13). D (14). C (15). C (16). D(17). B (18). C (19). C (20). C 3.2.填空题

（1） FILO, FIFO

（2） -1, 3 4 X * + 2 Y * 3 / -

（3） stack.top++, stack.s[stack.top]=x

（4） p>llink->rlink=p->rlink, p->rlink->llink=p->rlink （5） (R-F+M)%M （6） top1+1=top2 （7） F==R

（8） front==rear

（9） front==(rear+1)%n （10） N-1

习题4 4.1 选择题

（1）如下陈述中正确的是______。

A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中的元素只能是字母 D.空串就是空白串 （2） 下列关于串的叙述中，正确的是______。 A.串长度是指串中不同字符的个数 B.串是n个字母有序数列

C.如果两个串含有相同的字符，则它们相等

D.只有当两个串的长度相等，并且各个对应位置的字符都相符是串才相等 （3） 字符串的长度是指______。

A.串中不同字符的个数 B.串中不同字母的个数 C.串中所含字符的个数 D.串中不同数字的个数 (4) 两个字符串长度相等的充要条件是______。

A.两个字符串长度相等 B.两个字符串中对应位置上的字符相等 C.同时具备（A）和（B）D.以上答案都不对

（5） 串是一种特殊的线性表，其特殊性体现在______。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符

（6）设有两个串p和q，求q在p中首次出现的位置的运算称为______。

A.链接B.模式匹配C.求子串D.求串长

（7）设串sI=“ABCDEFG”,S2=“PQRST”,函数con(X,Y)返回X和Y串的连接串，subs（s,I,j）返回串s的从序号i的字符开始的j个字符组成的字串，len(s)返回串s的长度，则con(subs(sI,2,len(s2)),2的结果串是______。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF

（8）函数substr(“DATASTRUCTURE”,5,9)的返回值为______。 A.“STRUCTURE” B.“DATA”

C.“ASTRUCTUR” D.“DATASTRUCTURE” (9) 常对数组进行的两种基本操作是______。 A.建立与删除 B.索引与修改 C.查找与修改 D.查找与索引

（10） 设串S= “IAMATEACHER!”,其长度是______。 A.16 B.11 C.14 D.15 4.2 填空题

（1）两个串相等的充要条件是__________________。 （2）空串是______，其长度为______。 （3）空格串是______，其长度是______。 （4）s=“I am a men”长度为______。 （5）s1=“hello”，s2=“boy”,s1,s2连接后为______。 （6）s=“this is the main string”，sub= “string”,strindex(s,sub)是（7）int a[10][10],已知a=1000，sizeof(int)=2,求a[3][3]地址＿＿（8）设有两个串p和q，求q和p中首次出现的位置的运算称为______________ 。

（9）串的长度是指：________________________。

（10）s=“xiaotech”所含字串的个数是________________。

习题4参考答案 4.1 选择题：

(1). A (2). D (3). C (4). C (5). B (6). B (7). D (8). A (9). B (10). D 4.2 填空题：

（1） 串长相等且对应位置字符相等 （2） 不含任何元素的串，0

（3） 所含字符均是空格，所含空格数 （4） 10

（5） “helloboy” （6） 18 （7） 1066

（8） 由零个或多个任意字符组成的字符序列 （9） 串中所含不同字符的个数 （10） 36 第五章 一、选择题

1.树最适合用来表示（）。

A. 有序数据元素 B. 无序数据元素

C. 元素间具有分层次关系的数据 D. 元素间无联系的数据 2.在m叉树中，度为0的结点称为（）。

A. 兄弟 B. 树叶 C. 树根 D. 分支结点

3.如果树的结点A有4个兄弟，而且B为A的双亲，则B的度为（）。 A. 3 B. 4 C. 5 D. 1

4.根据二叉树的定义可知二叉树共有（）种不同的形态。 A. 4 B. 5 C. 6 D. 7

5.由3个结点可以构造出（）种不同形态的二叉树。 A. 3 B. 4 C. 5 D. 6 6.具有20个结点的二叉树，其深度最多为（）。 A. 4 B. 5 C. 6 D. 20 7.高度为h的满二叉树的结点数是（）个。 A. log2h+1 B. 2h+1 C. 2h-1 D. 2h-1 8.深度为5的二叉树至多有（）个据点。

A. 16 B. 32 C. 31 D. 10 9.设一颗二叉树共有50发业主据点（终端据点），则共有（）个度为2的结点。 A. 25 B. 49 C. 50 D. 51 10.一颗二叉树中根结点的编号为1，而且23好结点有左孩子但没有右孩子，则完全二叉树总共有（）个结点。

A. 24 B. 45 C. 46 D. 47 11.二叉树的第3层最少有（）个结点。

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

12.设n、m为一颗二叉树上的俩个结点，在中序遍历时，n在m之前的条件是（）。 A. n在m的右方 B. n是m祖先 C. n在m的左方 D. n是m子孙

13.某二叉树的先序序列和后序序列正好相反，则该二叉树可能是（）的二叉树。 A. 高度大于1的左单支 B. 高度大于1的右单支 C. 最多只有一个结点 D. 既有左孩子又有右孩子

14..某二叉树的中序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。 A. 空或只有一个结点 B, 高度等于其结点数 C. 任一结点无左孩子 D. 任一结点无右孩子 15.有n个结点的二叉树链共有（）个空指针域。 A. n-1 B. n C. n+1 D. n+2 二、填空题

1. 一颗深度为5的二叉树，至少有 1 个叶子结点。

2.一颗完全二叉树采用顺序存储结构，每个结点占4字节，设编号为5的元素地址为 1016，且它有左孩子和右孩子，则该左孩子和右孩子的地址分别为 1036 和 1040 。 3.一颗完全二叉树采用顺序存储结构，若编号为i的元素左孩子，则该左孩子的编号为

2i 。

4.一颗含有n(n>1)个结点的K叉树，当k= 1 时深度最大，此最大深度为 n ； 当k= n-1 时深度最小，此最小深度为 2 。

k-1k

5.深度为K的完全二叉树至少有 2 个结点，至多有 2-1 个结点。

6.已知一颗二叉树的先序遍历序列为EBADCFHGIKJ，中序遍历序列为ABCDEFGHIJK， 则该二叉树的后序遍历序列为 ACDBGJKIHFE 。

7.如果指针p指向一颗二叉树的一个结点，则判断p没有左孩子的逻辑表达式为p!=NULL。

8.在由n个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为Huffman树 。

9.在树的孩子兄弟表示法中，每个结点有俩个指针域，一个指向 其第一个孩子；另一个指向

下一个兄弟 。

10.树的先根遍历结果与其转换的相应二叉树的 先序遍历 结果相同；树的后根遍历结果与其转换的相应二叉树的 中序遍历 结果相同。 习题5参考答案 5.1 选择

（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C （11）B（12）C（13）C（14）C（15）C

5.2 填空 （1）1

（2）1036；1040 （3）2i

（4） 1 ； n ; n-1 ; 2

k-1k

（5）2；2-1 （6）ACDBGJKIHFE （7）p!=NULL （8）Huffman树

（9）其第一个孩子; 下一个兄弟 （10）先序遍历；中序遍历

6.1 选择题

（1）一个有8个顶点的有向图，所有顶点的入度之和与所有顶点的初读之和的差是（）。 A. 16 B. 4 C. 0 D. 2 (2)一个有n个顶点的连通无向图至少有（）条边。 A. n-1 B.n C.n+1 D. n+2 (3)具有n个顶点的完全有向图的弧数为（）。

A. n(n-1) /2 B. n(n-1) C. n^2 D. n^2-1 (4)一个n 条边的连通无向图.其顶点的个数至多为（）。 A. n-1 B. n C. n+1 D. n+2 （5）设无向图的顶点个数为n，则该图最多有（）条边。

A. n-1 B.n（n-1）/2 C. n（n+1）/2 D. 0 (6)任何一个无向连通图的最小生成树（）。

A. 只有一颗 B. 有一颗或多颗 C. 一定有多颗 D.可能不存在 （7）下列算法中，（）算法用来球图中某顶点到其他所有顶点之间的最短路径。 A.Dijkstra B.Floyed C.Prim D.Kruskal (8)在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A. 2 B. 3 C. 1 D. 1.5 （9）下面关于图的存储的叙述中正确的是（）。

A. 用邻接表法储存图，占用的存储空间大小只与图中边数有关，而与顶点个数无关 B. 用邻接表法储存图，占用的存储空间大小与图中边数喝顶点个数都有关

C. 用邻接矩阵法储存图，占用的存储空间大小与图中边数喝顶点个数都有关

D. 用邻接矩阵法储存图，占用的存储空间大小只与图中边数有关，而与顶点个数无关 （10）设有向无环图G中的有向边集合E={<1,2>,<2,3>,<3,4>,<1,4>},则下列属于该有向图G的一种拓扑排序序列的是（）

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

(11)设有无向图G中的边集合E={(a,b)(a,e)(a,c)(b,e)(e,d)(d,f)(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。

A.aedfcb B.acfebd C.aebcfd D.aedfbc (12)连通图G中有n个顶点，G的生成树是（）连通子图。 A.包含G的所有顶点 B.包含G的所有边

C.不必包含G的所有顶点 D .包含G的所有顶点喝所有边

（13）设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 A.n-1 B.n C. n+1 D. 2n-1

（14）设无向图G中有n个顶点，e 条边，则起对应的邻接中的表头结点喝边表结点的个数分别为（）。

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

(15)用邻接矩阵A 表示有向图G的存储结构，则有向图G中顶点i的入度为（）。 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和

（16）用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的出度为（）。 A. 第i行非0元素的个数之和 B. 第i列非0元素的个数之和 C. 第i行0元素的个数之和 D. 第i列0元素的个数之和 （17）可以判断一个有向图中是否含有回路的方法为（）。

A. 广度优先搜索 B. 深度优先搜索 C.拓扑排序 D. 求最短路径 6.2 填空题

（1）.一个连通无向图有5个顶点，8条边，则起生成树将要去掉（）条边。 （2）.在树结构和图结构中，前趋和后继结点之间分别存在（）和（）的联系。

（3）.有n 个顶点的连通图至少有（）条边；有n 个顶点的强连通图则至少有（）条边。 （4）.一个具有n个顶点的有向图至少有（）条弧。

（5）.如果不知道一个图是有向图还是无向图，但知道它的邻接矩阵是非对称的，那么这个图必定是（）。

（6）.在无向图G的邻接矩阵A中，若A[I][J]=1，则A[J][I]为（）。 （7）.无向图用邻接矩阵存储，其所有元素之和表示无向图的边数的（） （8）.无向图用邻接表存储，其所有边表结点之和表示无向图的边数的（） （9）.无向图用邻接表存储，顶点Vi的度为（）。 （10）.有向图用邻接表存储，顶点Vi的出度为（）。 （11）.图的遍历方式一般有（）和（）两种。 （12）.Prim算法的时间复杂度为（），与边数无关，因此适用于求边稠密的网的最小生成树。 （13）.如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图（）。 习题6参考答案 6.1 选择题

（1）C （2）A （3）B（4）C（5）B______条边。（6）B（7）A（8）A（9）B（10）A （11）A（12）A（13）B（14）A（15）B（16）A（17）C

6.2 填空

（1） 4

（2） 1对多 ; 多对多 （3） n-1 ; n （4） 0_

（5） 有向图 （6） 1 （7） 一半 （8） 一半

（9）___第i个链表中边表结点数___ （10）___第i个链表中边表结点数___ （11）深度优先遍历；广度优先遍历

2

（12）O（n） （13）___无回路

7.1选择题

（1）对于长度为n的无序线性表进行顺序查找，则查找成功、不成功时的平均数据比较次数分别为

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

（2）请指出在顺序表中{2,5,7,10,14,15,18,23,35,41,52}中，用二分法查找关键字码12须做 次关键字比较。

A 2 B 3 C 4 D 5

（3）对线性表进行折半查找时，必须要求线性表 。 A 以线性表方式存储 B 以链接式方式存储

C s以顺序方式存储，且结点按关键字有顺排列 D 以链接式方式存储，且结点按关键字有顺排列

（4）设二叉排序树中有n个结点，则二叉排序树的平均查找长度为 。 A O(1) B O(long

) C O（n） D （

）

（5）依次插入顺序（50,72,43,85,75,20,35,45,65,30）后建立的二叉搜索树中，查找元素35要进行 元素间的比较。

A 4次 B 5次 C 7次 D 10次

（6）一颗高度为5的理想平衡树中，最少含有16个结点，最多含有 个结点。 A 31 B 32 C 30 D 33

（7）对包含N个元素的散列表进行查找，平均查找度 。 A 为 O（long

） B 为O(N)

C 不直接依赖于N D 上述三者都不对

（8）设散列表中有m个存储单元，散列函数H(key)=key%p,则p最好选择 。 A 小于等于m的最大奇数 B 小于等于m的最大素数

C 小于等于m的最大偶数 D 小于等于m的最大合数 （9） 是Hash查找的冲突处理方法。

A 求余法 B 平方取中法 C 二分法 D 开放地址法

（10）当a的值较小时，散列存储通常比其他存储方式具有 的查找速度。

A 较慢 B 较快 C 相同 D 不确定

（11）对线性表进行折半查找，最方便的存储结构是 。 A 顺序表 B 有序的顺序表 C 链表 D 有序的链表 （12）对一个排好序的线性表，用二分法检索表中的元素，被检索的表应当采用 表示。

A 顺序存储 B 连接存储

C 散列法存储 D 存储表示不受限制

（13）若在线性表中采用折半查找法查找元素，该线性表应该 。（北京航天大学1999年试题）

A 元素按值有序 B 采用顺序存储结构

C 元素按值有序，且采用顺序存储结构 D元素按值有序 ，且采用链式存储结构

（14）用二分法查找一个长度为10的排好序的线性表，查找不成功时，最多需要比较 次。

A 5 B 2 C 4 D 1

（15）采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分 个结点最佳。 A 10 B 25 C 6 D 625

（16）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用 查找方法。

A 分块 B 顺序 C 二分 D 散列 7.2填空题

（1）对于长度为n的线性表，若进行顺序查找，则时间复杂度为 ；若采用折半法查找，则时间复杂度为 。

（2）假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为 ，比较两次查找成功的结点数为

，比较三次查找成功的结点数为 ， 比较四次查找成功的结点数为 ，比较五次查找成功的结点数为 ，平均查找长度为 。 （3）在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。

（4）对于一棵二叉搜索树进行遍历时，得到的结点序列是一个 （5）在一棵m阶B-树上，每个非树根结点的关键字数目最少为 个，最多为 。

（6）对于线性表（70 ，34,55,23,65,41,20）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有 ，散列地址为6的有 。

（8）散列表中解决冲突的两种方法是 和 。 （11）最优二叉树（哈夫曼树）、最优查找树均为平均查找路径长度

最小的树，

其中对最优二叉树，n表示 ，对最优查找树，n表示 ，构成这两种树 。

（12）在分块检索中，对256个元素的线性表分成 块最好，每块的最佳长度是 ；若每块的长度为 ，其平均检索长度为 。 （14）哈希表处理冲突的方法有 。

（16）在分块查找中首先查找 ，然后查找相应的

（18）当所有的结点的权值都相等时，用这些结点构造的二叉排序树 遍历它们得到的序列的顺序是一样的。

(19)对两棵具有相同关键字集合而形状不同的二叉树， 遍历它们得到的序列的顺序是一样的。 习题7参考答案 7.1 选择题

（1）C (2)C (3) C (4)B (5) A (6)A (7) D (8)B (9)D (10) B (11)B (12)A (13)C (14)C (15)A (16)D (17)C (18)B,C (19)B (20)A 7.2 填空题

（1） O(n),O(log2n)

（2） 1,2,4,8,5, log2(n+1)-1 （3） 小于，大于 （4） 增序序列 （5） ?n/2? ,m-1

（6） 70; 34,20,55 （7） n/m

（8） 开放地址法，链地址法

（9） 产生冲突的可能性就越大，产生冲突的可能性就越小 （10） 关键码直接 （11） ②, ①, ⑦ （12） 16,16,8,21

（13） 直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法 （14） 开放地址法，再哈希法，链地址法，建立一个公共溢出区 （15） 装满程度 （16） 索引，快

（17） 哈希函数，装填因子 （18） 一个结点 （19） 中序 （20） 等于

习题8 8.1选择题

（1）下述排序算法中，稳定的是 。

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

（2）下列排序算法中， 需要的辅助储存空间最大。 A.快速排序 B.插入排序 C.希尔排序 D.基数排序

（3）下列各种排序算法中平均时间复杂度为O（n2）是 。

A.快速排序 B.堆排序 C.归并排序 D.冒泡排序

（4）在基于关键码比较的排序算法中， 算法在最坏情况下，关键码比较次数不高于 O（nlog2n）。

A.冒泡排序 B.直接插入排序 C.二路归并排序 D.快速排序 （5）一组记录为｛46，79，56，38，84，40｝，则采用冒泡排序法按升序排列时第一趟排序 的结果是 。

A.46，79，56，38，40，84 B.46，56，38，79，40，84 C.38，40，46，56，84，79 D.38，46，79，56，40，84

（6）每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 排序。

A.插入 B.堆 C.快速 D.归并

（7）每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。

A.插入 B.堆 C.快速 D.归并

（8）设一组初始记录关键字序列（5，2，6，3，8），以第一个记录关机键字5为基准进行一趟快速排序的结果为 。

A.2，3，5，8，6 B.3，2，5，8，6 C.3，2，5，6，8 D.2，3，6，5，8

（9）设有n个待排序的记录关键字，则在堆排序中需要 个辅助记录单元。 A.1 B. n C.nlog2n D.n^2

（10）对于关键字值排序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为 的结点开始。 A.100 B.100 C.60 D.15

（11）下列排序方法中， 方法的比较次数与记录的初始排列状态无关。 A.直接插入排序 B.冒泡排序 C.快速排序 D.直接选择排序

（12）设有关键码初始序列｛Q，H，C，Y，P，A，M，S，R，D，F，X｝，新序列｛F，H，C，D，P，A，M，Q，R，S，Y，X｝是采用 方法对初始序列进行第一趟排序的结果。 A.直接插入排序 B.二路归并排序 C.以第一元素为分界元素的快递排序 D.基数排序

（13）在待排序文件已基本有序的前提下，下述排序方法中效率最高的是 。 A.直接插入排序 B.直接选择排序 C.快速排序 D.二路归并排序

（14）排序的算法很多，若按排序的稳定性和不稳定性分类，则 是不稳定排序。 A.冒泡排序 B.归并排序 C.直接插入排序 D.希尔排序

（15）若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是 。

A.快速排序 B.堆排序 C.归并排序 D.直接插入排序

（16）将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是 。 A.n B.2n-1 C.2n D.n-1

（17）下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(long2n)的是 。 A.堆排序 B.冒泡排序 C.直接选择排序 D.快速排序

（18）下列排序算法中， 算法可能会出现下面情况：初始数据有序时，花费的时间反

而最多。

A.堆排序 B.冒泡排序 C.快速排序 D.希尔排序 （19）数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用 最节省时间。

A.堆排序 B.希尔排序 C.快速排序 D.直接选择排序

（20）如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用 方法最快。

A.冒泡排序 B.快速排序 C.简单选择排序 D.堆排序 8.2填空题

（1）当待排序的记录数较大、排序码较随机且对稳定性不做要求时，宜采用

____________________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。

（2）在堆排序的过程中，对任意一个分支结点进行筛运算的时间复杂度为_______，整个堆排序过程的时间复杂度为__________。

（3）快速排序、堆排序、归并排序中，_________排序是稳定的。

（4）当向一个大根堆插入一个具有最大值的元素时，需要逐层________调整，直到被调整到_________位置为止。

（5）设一组初始记录关键字序列为（20，18，22，16，30，19），则以20为中轴的一趟快速排序结果为________________________。

（6）设一组初始记录关键字序列为（20，18，22，16，30，19），则根据这些初始关键字序列建成的初始堆为_____________________。

（7）设一组初始记录关键字序列为（49，38，65，97，76，13，27，50），则以d=4为增量的一趟希尔排序结束后的结果为________________________。

（8）对一组初始关键字序列为（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录比较的次数为___________，在整个排序过程中最多需要进行___________趟排序才可以完成。

（9）在插入和选择排序中，若初始数据基本正序，则选用________；若初始数据基本反序，则选用________________。

（10）在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序中，平均比较次数最少的是________________，需要内存容量最多的是________________。

（11）堆排序是不稳定的，空间复杂度为________________。在最坏情况下，其时间复杂度为________________。

（12）若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间相对位置保持不变，则这种排序方法是________________的排序方法。 （13）在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较________________次。

（14）在对一组记录（50，40，95，20，15，70，60，45，80）进行希尔排序时，假定取d(i++1)=[di/2]，0

（15）二路归并排序的时间复杂度是________________。

（16）对于n个记录的集合进行归并排序，所需的附加空间消耗是________________。 （17）设表中元素的初始状态是按键值递增的，分别用堆排序，快速排序，冒泡排序和归并排序方法对其仍按递增顺序进行排序，则________________最省时间，________________最费时间。

（18）从无序序列建立堆的方法是：首先将要排序的所有元素分放到一棵________________的各个结点中，然后从i=________________的结点ki开始，逐步把以kn/2，kn/2-1，kn/2-2，…….为根的子树排成堆，直到以k1为根的树排成堆，就完成了建堆的过程。 （19）若待排序的序列中多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保持不变，则称这种排序方法是________________的，否则称为是________________的。 （20）在利用快速排序方法对一组记录（50，40，95，20，15，70，60，45，80）进行快速排序后，递归调用使用的栈所能达到的最大深度为________________，需递归调用的次数为________________，其中第二次递归调用是对________________组记录进行快速排序。 习题8 参考答案

8．1 选择题

（1）B (2)A (3)D (4)C (5)B (6)A (7)B (8)C (9)A (10)C (11)D (12)C (13) C （14）D （15）C (16)B (17) D

8.2填空题

（1） 快速，归并

（2） O（log2n）,O(nlog2n) （3） 归并

（4） 向上，根结点

（5） 19，18，16，20，30，22 （6）

30

20 23

16 18 19

（7）49，13，27，50，76，38，65，97 （8）8，8

（9）插入，选择（每次选择最大的） （10）快速，归并 (11)O(1), O(nlog2n) (12)稳定 (13)3

(14)(15,20,50,40) (15)O(log2n)

(16)O(n2

)

(17)冒泡排序,快速排序 (18)完全二叉树,n/2 (19)稳定,不稳定

（18）C （19）B （20）D 三、判断题(10分)

1.线性表的逻辑顺序总是与其物理顺序一致。（ X ） 2.完全二叉树一定是满二叉树。(X )

3.顺序表和一维数组一样，都可以按下标随机（或直接）访问。（ V ） 4. 边数很多的稠密图，适宜用邻接矩阵表示。（V ）

5. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。（ V ）

6.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（ X ） 7.链表中的头结点仅起到标识的作用。( X)

8. 完全二叉树的某结点若无左孩子，则它必是叶结点。( V ) 9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。（V ） 10. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。( X )

四、问答求解题

1.已知稀疏矩阵A(下标使用从1开始)如下，写出右边对应格式的压缩存储的三元组表。 i j v 7 0 0 8 0 -1 0 1 3 0 0 0 1 1 1 7 A= 0 0 0 5 0 0 2 1 4 8 0 0 0 0 0 0 3 1 6 -1 9 0 0 0 0 0 4 2 2 1 0 0 0 0 0 0 5 2 3 3 6 3 4 5 7 5 1 9

2．按给定的输入序列：40，20，50，10，30，60构成一棵二叉排序树。（5分）

3. 已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试画出此二叉树，并写出它的后序遍历序列。

后序遍历序列：CBEFDA

4． 有一份电文中共使用了4个字符：a,b,c,d。它们出现的频率概率依次是a(0.4),b(0.3),c(0.2),d(0.1)，试构造的哈夫曼（Huffman）树，写出对应字符的哈夫曼编码（1分）。

5. 对以下有向无环图，画出其带入度域的邻接表（3分），写出一种拓扑排序序列（3分）。

1.已知稀疏矩阵A(下标使用从1开始，4行5列)如下，写出对应的三元组表。（5分）

0 6 0 0 7

5 0 8 0 0 0 -3 0 0 0 4 0 0 0 0

2．按给定的输入序列：33，20，50，18，28，60构成一棵二叉排序树。（5分） 3. 已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试 画出此二叉树（5分），并写出它的后序遍历序列（1分）。

4． 有一份电文中共使用了5个字符：A,B,C,D,E。它们出现的频率概率依次是A(0.13),B(0.05),C(0.25),D(0.37),E(0.20)，试构造的哈夫曼（Huffman）树（5分），写

出对应字符的哈夫曼编码（3分）。

(注意，构造树时约定：左结点值大于右结点值，左分支编码为0，右分支编码为1) 5.下面带权无向图（网）

（第5题图） （第6题图）

1） 请写出该网的邻接矩阵。（3分）

2） 列出广度优先遍历该图所得到的一个顶点序列。（3分） 3） 请画出该图的一棵最小生成树。（5分）

6.对以下有向无环图，画出其带入度域的邻接表（5分），写出一种拓扑排序序列（3分）。 7.对一组记录（50，40，70，90，80，20，30，60）进行升序排序，写出直接选择排序各趟排序结果（5分）

8.对一组记录（40，30，60，80，70，10，20，50）进行快速排序，每趟以区间第一个元素为基准，写出各趟排序结果（5分）

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

A）内部结构和外部结构 B）线性结构和非线性结构 C）动态结构和静态结构 D）连续结构和非连续结构 2.线性表Ｌ在 情况下适用于使用链式存储结构实现。

Ａ）需经常修改Ｌ中的结点值 Ｂ）需不断对Ｌ进行删除插入 Ｃ）Ｌ中含有大量的结点 Ｄ）Ｌ中结点结构复杂

3.一个向量第一个元素的存储首地址是1000，每个元素的长度为2，则第5个元素的首地址是（ ）。

A）1010 B）1008 C）1000 D）1020

4.若要在单链表中的结点*s之后插入一个结点*p，则应执行的语句为（ ）。

A）s->next=p->next ; p->next=s; B）p->next=s ; s->next=p->next ; C）p->next=s->next ; s->next=p; D）s->next=p ; p->next=s->next ;

5. 无向图的邻接矩阵是一个（ ）。 A）对称矩阵 B）上三角矩阵 6. 下面哪棵树不属于完全二叉树（ ）。

C）下三角矩阵 D）对角矩阵

A） B） C） D） 7.下面哪棵树不属于平衡二叉树（ ）。

A） B） C ） D） 8.线性表折半查找时，要求线形表必须是 ( )。

A)以顺序存储方式 B) 以顺序方式存储，且结点按关键字有序排序 C) 以链式存储方式 D)以链式存储，且结点按关键字有序排序

9．在关键字序列（12，23，34，45，56，67，78，89，91）中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为（ ）。 A）4，4，3 B）4，3，3 C）3，4，4 D）3，3，4 10.一个具有8个顶点的有向图中，把所有顶点的入度之和 减去 所有顶点的出度之和，结果为（ ）。

A）16 B）8 C）4 D）0 11. 算法分析的两个主要方面是：

A) 空间复杂性和时间复杂性 B) 正确性和简明性

C) 可读性和文档性 D) 数据复杂性和程序复杂性 12.在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ）。

Ａ） ＡＳＬ＝ｎ Ｂ） ＡＳＬ＝（ｎ＋１）／２

Ｃ） ＡＳＬ＝n＋１ Ｄ） ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

13.堆的形状是一棵（ ） 。

Ａ） 二叉排序树 Ｂ）满二叉树 Ｃ） 完全二叉树 Ｄ） 哈夫曼树 14.一个有4个顶点的有向图最多有多少条边（ ）。 A） 4 B）12 C）6 D）8

15. 一棵具有255个结点的完全二叉树，它的深度为（ ）。 A）7 B)8 C)9 D)10 1. 算法分析的两个主要方面是：（ ）

A) 空间复杂性和时间复杂性 B) 正确性和简明性

C) 可读性和文档性 D) 数据复杂性和程序复杂性 2.在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ）。

Ａ） ＡＳＬ＝ｎ Ｂ） ＡＳＬ＝（ｎ＋１）／２

Ｃ） ＡＳＬ＝n＋１ Ｄ） ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１ 3.堆的形状是一棵（ ） 。

Ａ） 二叉排序树 Ｂ）满二叉树 Ｃ） 完全二叉树 Ｄ） 哈夫曼树 4.一个有4个顶点的无向图最多有多少条边（ ）。 A） 4 B）12 C）6 D）8

5. 一棵具有２５8个结点的完全二叉树，它的深度为（ ）。 A）7 B)8 C)9 D)10

6.在数据结构中，数据的逻辑结构可以分成（ ）。

A）内部结构和外部结构 B）线性结构和非线性结构 C）动态结构和静态结构 D）连续结构和非连续结构 7.线性表Ｌ在 情况下适用于使用链式存储结构实现。

Ａ）需经常修改Ｌ中的结点值 Ｂ）需不断对Ｌ进行删除插入 Ｃ）Ｌ中含有大量的结点 Ｄ）Ｌ中结点结构复杂

8.一个向量第一个元素的存储首地址是100，每个元素的长度为2，则第5个元素的首地址是（ ）。

A）110 B）108 C）100 D）120

9.若要在单链表中的结点*s之后插入一个结点*p，则应执行的语句为（ ）。

A）s->next=p->next ; p->next=s; B）p->next=s ; s->next=p->next ; C）p->next=s->next ; s->next=p; D）s->next=p ; p->next=s->next ; 10. 无向图的邻接矩阵是一个（ ）。 A）对称矩阵 B）上三角矩阵 C）下三角矩阵 D）对角矩阵 11. 下面哪棵树不属于完全二叉树（ ）。

A） B） C） D） 12.下面哪棵树不属于平衡二叉树（ ）。

A） B） C ） D） 13.线性表折半查找时，要求线形表必须是 ( )。

A)以顺序存储方式 B) 以顺序方式存储，且结点按关键字有序排序 C) 以链式存储方式 D)以链式存储，且结点按关键字有序排序 14. 由同一关键字集合构造的各棵二叉排序树（ ）。 A）其形态不一定相同，但平均查找长度相同

B）其形态不一定相同，平均查找长度也不一定相同 C）其形态均相同，但平均查找长度不一定相同 D）其形态均相同，平均查找长度也都相同

15.一个具有8个顶点的有向图中，把所有顶点的入度之和 减去 所有顶点的出度之和，结果为（ ）。

A）16 B）8 C）4 D）0

四、算法设计题（8分）

1.有一带头结点的单链表，写出单链表上元素按值查找的算法（补充locate函数）。

结点类型定义如下：

typedef int elemtype ；

typedef struct node /*结点类型定义*/ { elemtype data ； /* 数据域 */

struct node *next ； /* 定义指针域 */ } linklist ；

linklist * head ，*p；*q ; /* head,p,q为单链表指针类型 */

main()

{ linklist *locate(linklist *head, elemtype k); linklist *head,*p; elemtype e; head=creatlist() scanf(“%d”,&e); p=locate(head,e); }

linklist *locate(linklist *head, elemtype k) /*查找值k函数*/ { }