数据结构复习题有答案的打印版

更新时间：2024-05-03 17:35:02 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构题库及答案推荐度：
相关推荐

一、选择题

1．下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 3．线性表是具有n个（ C ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项

3. 设给定权值总数有n 个，其哈夫曼树的结点总数为( D ) A．不确定 B．2n C．2n+1 D．2n-1 4．若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（A ）。

A．n-1 B．?n/m?-1 C．?(n-1)/(m-1)? D． ?n/(m-1)?-1 E．?(n+1)/(m+1)?-1 5. 有关二叉树下列说法正确的是（ B ）

A．二叉树的度为2 B．一棵二叉树的度可以小于2

2．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

3．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 4. 静态链表中指针表示的是（ C ）. A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址

5. 链表不具有的特点是（ B ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比

1. 对于栈操作数据的原则是（ B ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

2. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ A ）

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

3. 设栈的输入序列是1，2，3，4,则（ D ）不可能是其出栈序列。

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

D. 4，3，1，2， E. 3，2，1，4，

1. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，求A[6，8]的地址。1340

2. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，求A[5，9]的地址。1196

1．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）

A．9 B．11 C．15 D．不确定 2．具有10个叶结点的二叉树中有（ B ）个度为2的结点， A．8 B．9 C．10 D．ll

C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2

1．图中有关路径的定义是（ A ）。

A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C

．

由

不

同

边

所

形

成

的

序

列 D．上述定义都不是

2．设无向图的顶点个数为n，则该图最多有（ B ）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2

3．一个n个顶点的连通无向图，其边的个数至少为（ A ）。 A ．n-1 B．n C．n+1 D．nlogn；

4．要连通具有n个顶点的有向图，至少需要（ B ）条边。 A．n-l B．n C．n+l D．2n

5．n个结点的完全有向图含有边的数目（ D ）。【中山大学 1998 二、9 （2分）】

A．n*n Ｂ．n（n＋１） C．n／2 D．n*（n－l）

6．一个有n个结点的图，最少有（ B ）个连通分量，最多有（ D ）个连通分量。

A．0 B．1 C．n-1 D．n

7．在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。

A．1/2 B．2 C．1 D．4

8．用有向无环图描述表达式(A+B)*（（A+B）/A），至少需要顶点的数目为( A )。 A．5 B．6 C．8 D．9

9．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( A )。

A．逆拓扑有序 B．拓扑有序 C．无序的

10．下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV网 D．AOE网

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A )

A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3. 下面关于二分查找的叙述正确的是 ( D )

A．顺序查找 B. 折半查找 C. 索引顺序查找 D. 哈希法查找

构造的结果不同的是( C )

A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90）

C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)

ASL为(C )。【北京航空航天大学 2000 一、8 （2分）】 13 ．分别以下列序列构造二叉排序树，与用其它三个序列所

A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 1．某内排序方法的稳定性是指( D )。

B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储

4. 对线性表进行二分查找时，要求线性表必须（ B ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序

C.以链接方式存储 D.以链接方式存储,且数据元素有序

5．适用于折半查找的表的存储方式及元素排列要求为( D ) A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

6. 用二分（对半）查找表的元素的速度比用顺序法( D ) A. 必然快 B. 必然慢 C. 相等 D. 不能确定

7．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减

8. 具有12个关键字的有序表，折半查找的平均查找长度（ A ）

A. 3.1 B. 4 C. 2.5 D. 5

9. 折半查找的时间复杂性为（ D ）

A. O（n2

） B. O（n） C. O（nlogn

） D. O（logn

） 10．当采用分快查找时，数据的组织方式为 ( B ) A．数据分成若干块，每块内数据有序

B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块

D. 数据分成若干块，每块（除最后一块外）中数据个数需相同

11．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( A )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性

12. 既希望较快的查找又便于线性表动态变化的查找方法是 ( C )

A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录

C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面给出的四种排序法中( D )排序法是不稳定性排序法。

A. 插入 B. 冒泡 C. 二路归并 D. 堆积

3．下列排序算法中，其中（ D ）是稳定的。【福州大学 1998 一、3 (2分)】

A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序

4．稳定的排序方法是（ B ）

A．直接插入排序和快速排序 B．折半插入排序和起泡排序

C．简单选择排序和四路归并排序 D．树形选择排序和shell排序

5 ．下列排序方法中，哪一个是稳定的排序方法？（ B ） A．直接选择排序 B．二分法插入排序 C．希尔排序 D．快速排序

6．若要求尽可能快地对序列进行稳定的排序，则应选 B （A．快速排序 B．归并排序 C．冒泡排序）。

7．若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ A ）排序为宜。

A．直接插入 B．直接选择 C．堆 D．快速 E．基数 8．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序

9．下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( A )

A．选择排序法 B. 插入排序法 C. 快速排序法 D. 堆积排序法

10．对下列四种排序方法，在排序中关键字比较次数同记录初始排列无关的是( D )。

A．直接插入 B. 二分法插入 C. 快速排序 D. 归并排序

11．在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（D ）。

A．直接插入排序 B. 气泡排序 C. 快速排序

D. 直接选择排序

12．比较次数与排序的初始状态无关的排序方法是( D )。

D．以上均不正确

A．直接插入排序 B．起泡排序 C．快速排序 D．简单选择排序

13．数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的( C )的两趟排序后的结果。

A．选择排序 B.冒泡排序 C.插入排序 D.堆排序

14．数据序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的( A )的两趟排序后的结果。

6．一个具有1026个结点的二叉树的高h为（）。

A．11 B．12 C．11至1026之间 A. 快速排序 B. 冒泡排序 C. 选择排序 D ． 10 至1024之间

D. 插入排序

15．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为

A. 84 47 25 15 21 B. 15 47 25 84 21 C. 15 21 25 84 47 D. 15 21 25 47 84

则采用的排序是 ( A )。 A. 选择 B. 冒泡 C. 快速 D. 插入

16．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（ C ）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡

1．一个堆栈的入栈序列为A、B、C、D、E，则可能的出栈序列是（）。 A. DCEAB B. DECBA C. EDCBA D. ABCDE

2. （）属于不稳定的排序算法。

A. 希尔排序 B. 堆排序 C.

快速排序 D. 基数排序

3. 向单链表中指针hs指向的结点后插入一个新节点s，应执行（）。 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;

4. 一个n个顶点的连通有向图，其边的数量至少为（）。 A．n-1 B．n C．n+1 D．nlogn；

5. 设图如下所示，在下面的5个序列中，不符合深度优先遍历的序列有（）种。 a e b d f c a c f d e b a e d f c b a e f d c b a e f d b c

A．2 B．3 C．4

7．某二叉树中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则其先序序列不是（）。

A．EACBDGF B．EFGACBD C．EAGCFBD D．EGFACDB

8 ．不适用于折半查找的表的存储方式及元素排列要求为

（）。

A．链接方式存储，元素无序 B．链接方式存储，元素有序

C．顺序方式存储，元素无序 D．顺序方式存储，元素有序

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

10．用户依次输入如下一组查询关键字：70、50、30、60、66、56、80。请问最后建立的平衡二叉树树根是（）。 A. 50 B. 56 C. 60 D. 70

二、填空题

1 ．当线性表的元素总数基本稳定，且很少进行插入和删除

操作，但要求以最快的速度存取线性表中的元素时，应采用__顺序 _____存储结构。

2．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__（n-1）/2 ______。【北方交通大学 2001 二、9】 3 ．设单链表的结点结构为 (data,next)，next为指针域，已知

指针px指向单链表中data为x的结点，指针py指向data为y的新结点 , 若将结点y插入结点x之后，则需要执行以下语句:_______；py->next=px->next; px->next=py ______; 4．在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动_ n-i+1_______个元素。 5．对于一个具有n个结点的单链表，在已知的结点*p后插

入一个新结点的时间复杂度为 _ O(1)， _______,在给定值为

x的结点后插入一个新结点的时间复杂度为__ O(n)______ 6．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。

7．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、f->next=p->next; f->prior=p; p->next->prior=f; p->next=f; _______、_______、________。

8. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s^ .next:=p； s^ .prior:= _ p^.prior

_______；p^ .prior:=s；__ s^.prior^.next______:=s； 9．链接存储的特点是利用__指针 ______来表示数据元素之间的逻辑关系。

10.顺序存储结构是通过__物理上相邻 _____表示元素之间的关系的;链式存储结构是通过__指针_______表示元素之间的关系的。

11. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 __4__个，单链表为____2___个。

12. 循环单链表的最大优点是：_从任一结点出发都可访问到链表中每一个元素。_______。13. 已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_ u=p->next; p->next=u->next; free(u); _______

14. 带头结点的双循环链表L中只有一个元素结点的条件是：__ L->next->next==L ______

15. 在单链表L中，指针p所指结点有后继结点的条件是：_ p->next!=null_

16.带头结点的双循环链表L为空表的条件是：____ L->next==L && L->prior==L ____。

17. 在单链表p结点之后插入s结点的操作是：_ s->next=p->next;p->next=s;______。

1．栈是_操作受限（或限定仅在表尾进行插入和删除操作） ______的线性表，其运算遵循__后进先出 _____的原则。 2．___栈____是限定仅在表尾进行插入或删除操作的线性表。

3. 一个栈的输入序列是：1，2，3则不可能的栈输出序列是_3 1 2 ______。

4. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为

，2

，3，4

，5，

经过

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

5. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为__0 ，栈2空时，top[2]为___ n+1 ____，栈满时为__ top[1]+1=top[2]_____。

6．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式

是：M：= M= _(M+1)% N；_______。 7．___队列_____又称作先进先出表。 8. 队列的特点是__先进先出 _____。

9．队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是__先进先出 _____。

1. 数组的存储结构采用___顺序存储结构 ____存储方式。 2. 设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为__（1）9572_；如按列优先顺序存储,则元素A[-18,-25]的存储地址为__（2）1228_。

3. 设数组a[1..50,1..80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为（_1）9174_;若以列序为主序顺序存储，则元素a[45,68]的存储地址为_（2）8788 _。

4. 将整型数组A[1..8，1..8]按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[7，3]的地址是：__1100_____。

5. 设有二维数组A[0..9,0..19],其每个元素占两个字节，第一个元素的存储地址为100，若按列优先顺序存储，则元素A[6,6]存储地址为__232_____。

6. 已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为__ 1340 _____。

7. 已知二维数组A[1..10，0..9]中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，A[5，9]的地址是：___1196____。

8. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_1_行，第_3_列的元素。

1．二叉树由_(1)根结点(2)左子树(3)右子树(1)__，__(2)_，_(3)__三个基本单元组成。

2．在二叉树中，指针p所指结点为叶子结点的条件是_ p->lchild==null && p->rchlid==null _____。

3．二叉树中某一结点左子树的深度减去右子树的深度称为该结点的__平衡因子__。

4．具有256个结点的完全二叉树的深度为__9 ____。 5．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有___12___个叶子结点。 6．假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是__ n ____。

7．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =__ N2+1____ 8．设有N个结点的完全二叉树顺序存放在向量A[1:N]中，其下标值最大的分支结点为__ ?N/2? ____。

9．高度为K的完全二叉树至少有__2k-2

____个叶子结点。 10．高度为8的完全二叉树至少有___64___个叶子结点。 11．已知二叉树有50个叶子结点，则该二叉树的总结点数

至少是_ 99 _____。

12．一个有2001个结点的完全二叉树的高度为__11 ____。 13．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为__69____。

14．具有N个结点的二叉树，采用二叉链表存储，共有__ N+1____个空链域。

15．二叉树的先序序列和中序序列相同的条件是_任何结点至多只有右子女的二叉树。 _____。

16．已知二叉树前序为ABDEGCF，中序为DBGEACF，则后序一定是__ DGEBFCA __。

17．一个无序序列可以通过构造一棵___二叉排序树___树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。

18．利用树的孩子兄弟表示法存储，可以将一棵树转换为__二叉树____。

19．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树的___前序 ___序列中的最后一个结点。

20．哈夫曼树是_带权路径长度最小的二叉树，又称最优二叉树 _____。

21．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__69____。

22．有数据WG={7，19，2，6，32，3，21，10}，则所建Huffman树的树高是_6 __，带权路径长度WPL为_261 __。 23. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__5, ________，带权路径长度WPL的值为___96_______。

1.判断一个无向图是一棵树的条件是_有n个顶点，n-1条边的无向连通图_____。

2．有向图G的强连通分量是指__有向图的极大强连通子图____。

3．一个连通图的__生成树____是一个极小连通子图。 4．具有10个顶点的无向图，边的总数最多为__45 ____。 5．若用n表示图中顶点数目，则有__ n(n-1)/2 _____条边的无向图成为完全图。

6．G是一个非连通无向图，共有28条边，则该图至少有__9 ____个顶点。

7. 在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ n _____条弧。

8．在有n个顶点的有向图中，每个顶点的度最大可达__2(n-1) ____。

9．设G为具有N个顶点的无向连通图，则G中至少有_ N-1_____条边。

10．n个顶点的连通无向图，其边的条数至少为__ n-1____。 11．如果含n个顶点的图形形成一个环，则它有__ n ____棵生成树。

12．N个顶点的连通图的生成树含有__ N-1 ____条边。

13．构造n个结点的强连通图，至少有__ n ____条弧。

14．有N个顶点的有向图，至少需要量__ N ____条弧才能保证是连通的。

15．右图中的强连通分量的个数为（ 3 ）个。

16．N个顶点的连通图用邻接矩阵表示时,该矩阵至少有___ 2（N-1）____个非零元素。

17．在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的__度 ____；对于有向图来说等于该顶点的_出度_____。

18. 在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是_第I列非零元素个数 _____。

19．构造连通网最小生成树的两个典型算法是__普里姆（prim）算法和克鲁斯卡尔（Kruskal）算法____。 20．求图的最小生成树有两种算法，__克鲁斯卡尔____算法适合于求稀疏图的最小生成树。

21. Prim（普里姆）算法适用于求__边稠密 ___的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_边稀疏______的网的最小生成树。

22. 有向图G可拓扑排序的判别条件是__不存在环____。 23．求最短路径的Dijkstra算法的时间复杂度为__ O(n2

）____。 24. 上面的图去掉有向弧看成无向图则对应的最小生成树的边权之和为__ 75 ____。

25．设有向图有n个顶点和e条边，进行拓扑排序时，总的计算时间为__.O(n+e）____。

26．在AOE网中，从源点到汇点路径上各活动时间总和最长的路径称为__关键路径 ____。

1．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为__6,9,11,12 ________。 2. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 ________

3. 在有序表A[1?20]中，按二分查找方法进行查找，查找长度为4

的元素的下标从小到大依次是

__1,3,6,8,11,13,16,19________

4. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需___2,

_______次查找成功，47时_____4,____成功，查100时，需___3_______次才能确定不成功。

5. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把

结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。 5. 平衡二叉树又称__________，其定义是__________。 6. 在哈希函数H（key）=key%p中，p值最好取__________。

7. 对于长度为255的表，采用分块查找，每块的最佳长度为___16_______。

8. 在n个记录的有序顺序表中进行折半查找，最大比较次数是___．?㏒2n

」+1_______。

9．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__ k(k+1)/2 ________次探测。

10. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为___(n+1)/2 _______。

11. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__(n+1)/n*log2(n+1)-1 ________。

12. 平衡因子的定义是__结点的左子树的高度减去结点的右子树的高度________

13. ___．直接定址法 _______法构造的哈希函数肯定不会发生冲突。

14. 在一棵有N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为___ O(N)_____ 。

15. 假设有n个关键字，它们具有相同的Hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做___ n(n+1)/2 ___次插入和探测操作。 16. 高度为8的平衡二叉树的结点数至少有___54_______个。

17. 高度为5（除叶子层之外）的三阶B-树至少有___31 _______个结点。

18. 假定查找有序表A[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度为___37/12 _______

19. 可以唯一的标识一个记录的关键字称为___主关键字 _______。

20. 已知二叉排序树的左右子树均不为空，则___126 _____上所有结点的值均小于它的根结点值，__ 64 __________上所有结点的值均大于它的根结点的值。

21. 动态查找表和静态查找表的重要区别在于前者包含有____插入 ______和____删除______运算，而后者不包含这两种运算。

1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较, _____和记录的_移动____。 2. 属于不稳定排序的有_希尔排序、简单选择排序、快速排序、堆排序等_________。

3．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_冒泡, ____算法，最费时间的是__快速____算法。

4. 不受待排序初始序列的影响，时间复杂度为O(N2

)的排序算法是_(1)简单选择排序

____，在排序算法的最后一趟开始之前，所有元素都可能不

在其最终位置上的排序算法是_(2)直接插入排序（最小的元素在最后时） ____。

5．直接插入排序用监视哨的作用是_______。

6．对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_ n(n-1)/2 ______。

7．从平均时间性能而言，__快速 ________排序最佳。 8．对于7个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为_(4,1,3,2,6,5,7)____。

9．快速排序在_____的情况下最易发挥其长处。

10．在数据表有序时，快速排序算法的时间复杂度是_.O(n2

) ___。

11．堆排序的算法时间复杂度为：__ O(nlog2n) ___。 12．堆是一种有用的数据结构。试判断下面的关键码序列中哪一个是堆___ ④ _______。

①16，72，31，23，94，53 ②94，53，31，72，16，23

③16，53，23，94，13，72 ④16，31，23，94，53，72

⑤94，31，53，23，16，72 1.

下面程序段中，带波浪线语句的执行频度为。 i=1；

while (i<=n) i=i*4; 2.

设有一空栈，现有输入序列e，d，c，b，a，经过push, push, push,pop, pop, push, push,pop操作后，输出序列是___ ___。 3. 长为n的循环队列满时，队头指针front和队尾指针rear须满足以下关系: 。

4. 在字符串的模式匹配算法中，模式串“aaabcaaabcad”第7个字符（带下划线）的next[j]值为：___ ___。 5.

数组A中每个元素的长度为3字节，行下标i从1到18，列下标j从1到30，从首地址1000开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为。 6. 二叉树的先序序列和中序序列相同的条件是：_ __。

7. 广义表A=(x, ((a, b) , z) , y )，则运算tail(head(tail(A)))的结果为。

8. 具有四个结点的二叉树有种不同形态。

已知一棵完全二叉树的结点总数为60个，则最后一层的结点数为。

10. 在一棵度为3的树中，度为3的结点数为3个，度为2

的结点数为1个，度为1的结点数为20个，则叶子结点数为个。

11. 高度为h的二叉树中只有度为0和2的结点，则此二叉

树中包含的结点数至少为。

12. 具有11个顶点的无向图，边的总数最多为____

_ _。

13. 下图所示无向网的最小生成树各边权值之和

为。

14. 在伙伴系统中，起始地址为320，大小为8的块，其伙

伴块的起始地址是。

15. 具有15个关键字的有序表，折半查找的平均查找长度

为。

16. 哈希表的平均检索长度不随表中结点数目的增加而增

加，而是随的增大而增大。

三、应用题

1请按照迪杰斯特拉算法的思想填写下表，并依此列出从顶点A到图中所有其它顶点的最短路径（要求写出每条最短路径经过的顶点序列，并指出该路径长度）。

从A到所有其它顶点的最短路径如下：

2请填写下表，求出下面AOE-网中各个活动的最早和最迟开始时间，并据此求出该图的关键路径和工程的工期，指出哪些活动是关键活动。

1 2 3 4 5 6 7 Ve Vl

关键路径是：

工程工期（即关键路径长度）为：

关键活动是：

3已知ABCDEFG在报文中出现的概率分别为：5、20、16、37、12、8、7；请为这7种字符设计相应的赫夫曼编码。要求：① 画出用于编码的赫夫曼树； ② 给出各字符编码结果。

4使用哈希函数hashf(x)=x mod 13，现要把数据：1，13，12，34，38，33，27，22依次插入到哈希表中。要求：（1）使用线性探查再散列法来构造哈希表。（2）使用链地址法构造哈希表。

（3）针对这两种情况，确定其装填因子，计算查找成功所需的平均比较次数。

5已知一待排序记录关键字序列如下：（17、89、46、35、49、96、13、5、22）。

写出利用快速排序法对其进行第一趟排序后所得的序列：画出由原始关键字序列筛选后建立的堆结构：

6画出该森林对应的二叉树结构，写出该二叉树的中序遍历结点序列。

1. 对下面过程写出调用P(3)的运行结果。 PROCEDURE p（w：integer）; BEGIN

IF w>0 THEN BEGIN

p(w-1);

writeln(w);{输出W} p(w-1）

END； END；

(3) 求每个活动的最早开始时间e( )和最迟开始时间l( )。

(4) 确定哪些活动是关键活动。画出由所有关键活动构

成的图，指出哪些活动加速可使整个工程提前完成。

解：运行结果为：1 2 1 3 1 2 1（注：运行结果是每行一个数，为节省篇幅，放到一行。）

1. 设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。

2．已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。

3．假定用于通讯的电文仅有8个字母C1，C2，?，C8组成，各个字母在电文中出现的频率分别为5，25，3，6，10，11，36，4，试为这8个字母设计哈夫曼编码树。

4．设通信中出现5中字符A、B、C、D、E对应的频率为0.2,0.1,0.5,0.15,0.25构造哈夫曼树，并给出对应字符的哈夫曼编码。

5．假设用于通讯的电文由8个字符组成，其出现的频率为5,29,7,8,14,23,3,11。试为这8个字符设计哈夫曼编码。 6．假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们

在电

文中

出现

的频

度分

别为

{0.31,0.16,0.10,0.08,0.11,,0.20,0.04}, 为这7个字母设计哈夫曼编码。

7．试构造一棵二叉树,包含权为1,4,9,16,25,36,49,64,81,100等10个终端结点,且具有最小的加权路径长度WPL。

（10）以数据集{2,5,7,9,13}为权值构造一棵哈夫曼树，并计算其带权路径长度。

1. 以右图为例，按Dijkstra算法计算得到的从顶点①(A)到

其它各个顶点的最短路径和最短路径长度。

2. 试对右图所示的AOE网络，解答下列问题。

(1) 这个工程最早可能在什么时间结束。

(2) 求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[I]。

按拓扑有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间Vl。然后再计算各个活动的最早可能开始时间e和最迟允许开始时间l，根据l - e = 0? 来确定关键活

动，从而确定关键路径。

此工程最早完成时间为（）。关键路径为：

（）

此工程最早完成时间为43。关键路径为<1, 3><3, 2><2, 5><5, 6>

3．已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树（假设以①为起点，试画出构造过程）。

1 20 2 10 9 11 5

10 6 14 6 3

5 18 4 6 4．试写出用克鲁斯卡尔（

Kruskal ）算法构造下图的一棵最

小生成树的过程。 6 1 18 2 5 7 4 23 12

5 25 15 8 3 7 6 10 20 4

第29图

解：V（G）={1，2，3，4，5，6，7}

E（G）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）}

1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：

H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=1,2,3,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。解：

找长度。

(2) 试用以下两种方法构造两个Hash表，Hash函数

H(K)=[i/2],其中i为关键字K中第一个字母在字母表中的序号，[x]表示取整数。

a. 用线性探测开放定址法处理冲突(散列地址空间为0～16); b. 用链地址法处理,然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。

5. 一棵二叉排序树结构如下,各结点的值从小到大依次为1-9，请标出各结点的值。

已知长度为

的表

（xal,wan,wil,zol,yo,xul,yum,wen，wim,zi,yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，

并求其在等概率的情况下查找成功的

平均查找长度：ASLsucc=（1+1+1+2+3+4+1+2）/8=15/8 以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）=7（冲突）

H2=（6+2）=0（冲突） H3=（6+3）=5 所以比较了4次。

2. 设哈希表a 、b分别用向量a[0..9],b[0..9]表示，哈希函

数均为H（key）=key MOD 7,处理冲突使用开放定址法，Hi=[H(key)+Di]MOD 10,在哈希表a中Di用线性探测再散列法，在哈希表b中Di用二次探测再散列法,试将关键字{19,24, 10,17,15,38,18,40}分别填入哈希表a,b中,并分别计算出它们的平均查找长度ASL。解：

平均查找长度。

7. 用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度.【北京邮电大学 1999 七（10分）】

49. 依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树。 (1) 试画出生成之后的二叉排序树;

(2) 对该二叉排序树作中序遍历，试写出遍历序列; (3) 假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度。

8. 已知关键字序列R={11,4,3,2,17,30,19}，请按算法步骤：（1）构造一棵哈夫曼树，并计算出它的带权路径长度WPL

（2）构造一棵二叉排序树，如果对每个关键字的查找概率相同，求查找成功时的平均查找长度ASL。

9. 输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题。

（1）按次序构造一棵二叉排序树BS。(2) 依此二叉

排序树，如何得到一个从大到小的有序序列？

（2）画出在此二叉排序树中删除“66”后的树结构。

哈希表a: ASLsucc=24/8=3；

哈希表b: ASLsucc =18/8

3. 采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51

（1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 4.

已

知

长

度

为

的

表

(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)

(1) 试按表中元素的顺序依次插入一棵初始为空的分

类二叉树，试画出插入完成之后的分类二叉树并计算其在等概率查找情况下，查找成功的平均查

10. 设二叉排序树中关键字由1到1000的整数组成，现要查找关键字为363的结点，下述关键字序列哪一个不可能是在二叉排序树中查到的序列？说明原因。

（1）51，250，501，390，320，340，382，363 （2）24，877，125，342，501，623，421，363

1．写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。

PROC bbsort(VAR r: sequence; n: integer); {r是一个数组}

d:=1; pos[-1]:=1; pos[1]:=n; i:=1; exchanged:= true;

WHILE exchanged DO [ exchanged:= false; WHILE i<>pos[d] DO

[IF (r[i]-r[i+d])*d>0 THEN [r[i]与r[i+d]交换; exchanged:=true;]; i:=i+d; ]

pos[d]:=pos[d]-d; i:=pos[d]; d:=-d; ] ENDP;

答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。一趟：12,23,35,16,25,36,19,21,16,47 二趟：12,16,23,35,16,25,36,19,21,47 三趟：12,16,23,16,25,35,19,21,36,47 四趟：12,16,16,23,19,25,35,21,36,47

五趟：12,16,16,19,23,25,21,35,36,47

六趟：12,16,16,19,21,23,25,35,36,47 七趟：12,16,16,19,21,23,25,35,36,47

2．设待排序的关键码分别为28，13，72，85，39，41，6，20。按二分法插入排序算法已使前七个记录有序，中间结果如下:

6 13 28 39 41 72 85 20 i=1 m=4 r=7 试在此基础上，沿用上述表达方式，给出继续采用二分法插入第八个记录的比较过程。

(1) 使用二分法插入排序所要进行的比较次数，是否与待排序的记录的初始状态有关？

(2) 在一些特殊情况下，二分法插入排序比直接插入排序要执行更多的比较。这句话对吗？

解： 6, 13, 28, 39, 41, 72, 85, 20 i=1↑ m=4↑ r=7↑ 20<39 i=1↑m=2↑r=3↑ 20>13 i=3 r=3 m=3 20<28 r=2 i=3

将r+1(即第3个)后的元素向后移动，并将20放入r+1处，结果为6,13,20,28,39,41,72,85。

（1）使用二分法插入排序所要进行的比较次数，与待排序的记录的初始状态无关。不论待排序序列是否有序，已形成的部分子序列是有序的。二分法插入首先查找插入位置，插入位置是判定树查找失败的位置。失败位置只能在判定树的最下两层上。

（2）一些特殊情况下，二分法插入排序要比直接插入排序要执行更多的比较。例如，在待排序序列已有序的情况下就是如此。 3．算法模拟

设待排序的记录共7个，排序码分别为8，3，2，5，9，1，

6。

(1) 用直接插入排序。试以排序码序列的变化描述形式说明排序全过程（动态过程求按递减顺序排序。

(2) 用直接选择排序。试以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。

(3) 直接插入排序算法和直接选择排序算法的稳定性如何？

解：. (1)直接插入排序第一趟 (3)[8,3],2,5,9,1,6 第二趟 (2)[8,3,2],5,9,1,6 第三趟 (5)[8,5,3,2],9,1,6

第四趟 (9)[9,8,5,3,2],1,6 第五趟 (1)[9,8,5,3,2,1],6 第六趟

(6)[9,8,6,5,3,2,1]

(2)直接选择排序（第六趟后仅剩一个元素，是最小的，直接选择排序结束）第一趟 (9)[9],3,2,5,8,1,6 第二趟 (8)[9,8],2,5,3,1,6 第三趟 (6)[9,8,6],5,3,1,2

第四趟 (5)[9,8,6,5],3,1,2 第五趟 (3)[9,8,6,5,3],1,2 第六趟

(2)[9,8,6,5,3,2],1

(3)直接插入排序是稳定排序，直接选择排序是不稳定排序。 4．在执行某个排序算法过程中，出现了排序关键字朝着最终排序序列相反的方向的移动，从而认为该算法是不稳定的。这种说法对么？为什么？

解：这种看法不对。本题的叙述与稳定性的定义无关，不能据此来判断排序中的稳定性。例如 5,4,1,2,3 在第一趟冒泡排

序后得到4,1,2,3,5。其中4 向前移动，与其最终位置相反。但冒泡排序是稳定排序。快速排序中无这种现象。

5一最小最大堆（min max heap）是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小（或最大）。如图所示为一最小最大堆；

(1) 画出在上图中插入关键字为5的结点后的

最小最大堆。

(2) 画出在上图中插入关键字为80 的结点后的最小最大堆；

四、算法题

1. 在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队操作的实现过程。

解：void EnQueue (LinkedList rear, ElemType x)

// rear是带头结点的循环链队列的尾指针，本算法将元素x插入到队尾。

{ s= (LinkedList) malloc (sizeof(LNode)); //申请结点空间

s->data=x; s->next=rear->next; //将s结点链入队尾

rear->next=s; rear=s; //rear指向新队尾 }

2、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的出队操作的实现过程。

解：void DeQueue (LinkedList rear)

// rear是带头结点的循环链队列的尾指针，本算法执行出队操作，操作成功输出队头元素；否则给出出错信息。 { if (rear->next==rear) { printf(“队空\\n”); exit(0);} s=rear->next->next; //s指向队头元素， rear->next->next=s->next; //队头元素出队。 printf (“出队元素是”，s->data); if (s==rear) rear=rear->next; //空队列 free(s); }

3．请编写直接插入排序算法。 #define maxsize 100 typedef struct

{ Elemtype data[maxsize]; int last; }Sqlist; 解：

StraightInsertSort (SQLIST *v) ;n:integer);

VAR i,j:integer; BEGIN

FOR i:=2 TO n DO {假定第一个记录有序} BEGIN

v.data[0]:=v.data[i]; j:=i-1; {将待排序记录放进监视哨}

WHILE v.data[0]

BEGIN v.data[j+1]:=v.data[j]; j:=j-1; END; v.data[j+1]:=v.data[0] {将待排序记录放到合适位置} END {FOR} END；

4．二叉树以下列二叉链表为存储结构，其头指针为*Bitree, 编写将二叉树中每个结点的左右孩子交换的算法。 struct bitreptr {Elemtype data;

struct bitreptr *lchild,*rchild; };

SwepBitree(BITREPTR *bt)

{ if(bt!=NULL){t=bt->lchild; bt->lchild= bt->rchild ; bt->rchild=t;}