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

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. 具有四个结点的二叉树有 种不同形态。

9.

已知一棵完全二叉树的结点总数为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

2

2

找长度。

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

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

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

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

6.

已知长度为

11

的表

（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。解：

2

3

平均查找长度。

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.

已

知

长

度

为

12

的

表

(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;}

preptr(bt->lchild); preptr(bt->rchild);} }

5有n个人围成一圈做循环报数游戏，规定报到m的人出列。请编写程序输出所有人的出列顺序。要求：使用循环队列循环链表实现该算法。

6请编写一个判别给定二叉树是否为（平衡）二叉排序树的算法。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构复习题 有答案的打印版(2)在线全文阅读。