软件技术数据结构部分习题解答

软件技术数据结构部分习题解答

2.21 有一铁路交换站如题图（栈），火车从右边开进交换站，然后再开到左边，每节车厢均有编号如1，2，3，…，n。请问：

（1）当n=3和n=4时有哪几种排序方式？哪几种排序方式不可能发生？ （2）当n=6时，325641这样的排列是否能发生？154623的排列是否能发生？ N=3时可能的出栈序列： 123 1S1X2S2X3S3X 132 1S1X2S3S3X2X 213 1S2S2X1X3S3X 231 1S2S2X3S3X1X 312 CAB

321 1S2S3S3X2X1X N=4，不可能的排列： 4312 4213 4231 4123 4132 3124 3142 3412 1423 2413

N=6时，325641可能 154623不可能

2.22 CQ[0：10]为一循环队列，初态front=rear=1，画出下列操作后队的头、尾指示器状态： （1）d,e,b,g,h入队； （2）d,e出队； （3）i,j,k,l,m入队； （4）b出队； （5）n,o,p,q,r入队；

软件技术数据结构部分习题解答

初态

1）d,e,b,g,h入队（2）d,e出队

3）i,j,k,l,m入队

4）b出队

5）n,o,p,q,r入队

rear

0 2 3 4 5 6 7 8 9 10

front

rear

0 1 2 3 4 5 7 8 9 10

front

rear

0 1 2 3 4 5 7 8 9 10

rear

front

0 1 2 3

4 5 6 7 8 9 10

front

0 1 2 3 4 5 6 7 8 9 10

front

0 1 2 4 5 6 7 8 9 10

front

（

（（（

软件技术数据结构部分习题解答

2.23试画出表达式A*（B-D）/D+C**（E*F）执行过程中NS，OS栈的变化情况。

NS

OS

NS

NS

OS OS

返回结果T6

NS

OS

NS

OS

NS

OS

NS

OS

软件技术数据结构部分习题解答

2.28将下面的树转换成二叉树。

软件技术数据结构部分习题解答

2.29 完全二叉树有1000个结点，问：

叶子结点有多少？度为2的结点有多少？多少个结点只有非空的左子树？ 第一种做法：

N1=0/1，N是奇 N1=0；N是偶 N1=1 N=1000，N1=1 1000=N0+1+N2 1 N0=N2+1 2 N0=500，N2=499 第二法：

N=1000，29<N<210 完全二叉的深度H=10 第10层叶子结点数：N01=N-(29-1)=1000-511=489 第10层总结点数：29 =512 第10层空的结点数：512-489=23 空结点数是奇数 N1=1

第9层叶子结点数：N02=（23-1）/2=11 总叶子结点数：N0=N01+N02=489+11=500 N2=N-N0-N1=1000-500-1=499

补充：度为3的树，1个度为1的结点，3个度为2的结点，求叶子结点数？

N=N0+N1+N2+N3=N0+1+3+4

B=N-1=N1+2*N2+3*N3=1+2*3+3*4=19 N=20 N0=12

4个度为3的结点，

软件技术数据结构部分习题解答

2.30 设一棵二叉树的中序遍历和后序遍历结果为： 中序：BDCEAFHG 后序：DECBHGFA 求先序？ABCDEFGH

2.32给定一组元素{17，28，36，54，30，27，94，15，21，83，生成的二叉排序树。

40}，画出由此

软件技术数据结构部分习题解答

2.33给定一组权值W={8，2，5，3，2，17，4}，画出由此生成的哈夫曼树。

17： 0 8： 111 5： 101 4： 1101 3： 1100 2： 1000 2： 1001

2．34 有一图如题图所示：

（1）写出此图的邻接表与邻接矩阵；

（2）由结点V1作深度优先搜索和广度优先搜索； （3）试说明上述搜索的用途。

软件技术数据结构部分习题解答

邻接矩阵：

邻接表：

软件技术数据结构部分习题解答

DFS：V1，V2，V3，V4，V5，V6，V7，V8，V9，V10，V11，V12，V15，V16，V17，V18，V19，V20

BFS：V1，V2，V5，V8，V3，V10，V4，V6，V7，V9，V12，V11，V18，V13，V19，V16，V17，V20

V13，V14，V14，V15，

软件技术数据结构部分习题解答

2．35 有一有向图如下：

（1）写出每一个结点的入度和出度各为多少； （2）写出此图的邻接矩阵与邻接表；

2．36 求下图中结点a到各结点之间的最短路径。

软件技术数据结构部分习题解答

2．37 求下图中所示AOV网所有可能的拓扑排序结果。

栈保存入度为0的点

拓扑排序：V7->V5->V2->V4->V3->V6->V1->V8

软件技术数据结构部分习题解答

2.38 下图所示AOE网，求

（1）每一事件最早开始时间和最晚开始时间； （2）该计划最早完成时间为多少。

事件最早最迟开始时间

活动最早最迟开始时间

关键活动是：a2,a4,a6,a9,a10,a12,a13,a14

关键路径：a2->a4->a6->a9->a12->a14或a2->a4->a6->a10->a13->a14 最早完成时间=关键路径权值之和：6+6+7+1+5+2或6+6+7+4+2+2=27

软件技术数据结构部分习题解答

2.40 画一棵以20个记录进行对分查找的判定树，并求等概率下的平均查找长度。

ASL=(1+2*2+3*4+4*8+5*5)/20=74/20

软件技术数据结构部分习题解答

(13,29,01,23,44,55,20,84,27,68,11,10,79,14)

线性探测再散列：p=17,m=19

ASL1=（1+1+1+1+1+1+2+1+1+4+6+1+7+5）/14=33/14

平方探测再散列：(13,29,01,23,44,55,20,84,27,68,11,10,79,14) ASL2=(1+1+1+1+1+5+3+1+2+1+1+1+4+1)/14=24/14

随机探测再散列：Rj={3,16,55,44,...}

ASL3=(1+1+1+1+1+3+4+1+1+1+1+2+1+2)/14=21/14

软件技术数据结构部分习题解答

2．41设有10个记录的关键字为：ICKES(9)，BARBER(2)，ELYOT(5)，KERN(11)，FRENCE(6)，LOWES(12)，BENSDN(2)，FONK(6)，ERVIN(5)，KNOX(11)。构造a=10/13的哈希表，取关键字首字母在字母表中的序号为哈希函数值，用随机探测解决冲突，dj=(d1+Rj) mod 13，Rj取自随机数列：3，7，1，12，10，…，统计该表的平均查找长度ASL。

ASL=(3+2+1+4+1+1+2+1+1+1)/10=1.7

2.42 对于给定的一组关键字：41，62，13，84，35，96，57，39，79，61，15，83。分别写出：插入排序、简单选择排序、堆排序、冒泡排序、快速排序、二叉排序树的排序过程，并对各排序方法进行分析。

简单选择排序：41，62，13，84，35，96，57，39，79，61，15，83 第一趟：13，62，41，84，35，96，57，39，79，61，15，83 第二趟：13，15，41，84，35，96，57，39，79，61，62，83 第三趟：13，15，35，84，41，96，57，39，79，61，62，83 第四趟：13，15，35，39，41，96，57，84，79，61，62，83 第五趟：13，15，35，39，41，96，57，84，79，61，62，83 第六趟：13，15，35，39，41，57，96，84，79，61，62，83 第七趟：13，15，35，39，41，57，61，84，79，96，62，83 第八趟：13，15，35，39，41，57，61，62，79，96，84，83

软件技术数据结构部分习题解答

第九趟：13，15，35，39，41，57，61，62，79，96，84，83 第十趟：13，15，35，39，41，57，61，62，79，83，84，96 第11趟：13，15，35，39，41，57，61，62，79，83，84，96 堆排序：41 …… 此处隐藏：1728字，全部文档内容请下载后查看。喜欢就下载吧 ……