数据结构实验报告（华夏）

（1）中序遍历时的顺序是_____________ （2）后序遍历时的顺序是____________ （3）如果值30被插入到该树中，则其双亲结点和兄弟结点分别是____________ （4）如果值41被插入到该树中，则其双亲结点和兄弟结点分别是___________

5、设电文为：ABEAACCDAACABBBBEAACDDE试为字符A、B、C、D、E设计Huffman编码，画出相应的Huffman树并计算其WPL。

6、给出有32个字符长度的字符串{ABCD ABCD AAA BBCD DEE FGE GCCCA}， 试为字符A、B、C、D、E、F、G设计哈夫曼编码。并求： （1）画出哈夫曼树。 （2）列出各字符的哈夫曼编码 （3）计算带权的路径长度

7、试将森林F={T1，T2，T3}转换为一棵二叉树。

B A C E D F I H K G J M L T1 T2 T3

8、试画出如下二叉树的顺序存储结构图。

E A B F G C D 9、已知下图为一棵二叉排序数，各结点的值依次为1—9，请标出树中各结点的值。

10、设计求二叉树结点数目的算法

11、试证明：一棵满K度树中，度为K的结点个数n1与度为零的结点个数n0之间满足

关系：N0=（K-1）*N1+1

第7章 图

1、单项选择题

（1）n个顶点的无向图的的邻接表中结点总数最多有______个。

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

（2）设连通图G的顶点数为n，则G的生成树的边数为______。 (A) n-1 (B) n (C) 2n (D) 2n-1

（3）在建立邻接表或逆邻接表时，若输入的顶点信息即为顶点的编号，则建立图的算法

的时间复杂度为______。

(A) O(n+e) (B) O(n2) (C) O(n×e) (D) O(n3)

（4）判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用______。 (A)求关键路径的方法 (B)求最短路径的方法 (C)深度优先扫描算法 (D)宽度优先扫描算法 （5）设无向图的顶点个数为n，则该图最多有_____条边。 (A) n-1 (B) n(n-1)/2 (C)n(n+1)/2 (D) n （6）如下图所示：

1 9 2 10 2 4 7 7 5 6 5 3 6 3 8 4

从顶点6出发进行广度优先遍历， 其广度优先遍历序列是： (A) 612345 (B)612453 (C)612543 (D)654321

2、给定下列网络G：

（1）求最小生成树，画出逻辑图；

（2）画出G的邻接矩阵和邻接表。

A 4 E 2 8 6 B 9 F 20 C

3、设图的顶点是A、B、C、D、E，根据下面的邻接矩阵画出对应的无向图。

| 0 1 0 1 0 |

| 1 0 1 0 0 | | 0 1 0 1 1 | | 1 0 1 0 0 | | 0 0 1 0 0 |

4、 如下图所示，完成下列各题 （1）写出该图的邻接矩阵表示， （2）用prim方法构造最小生成树

（3）用kruskal方法构造最小生成树（要求写出构造过程）。

1 9 8 10 2 4 7 7 5 6 5 3 6 3 8

4 5、 写出求下图所示 AOE网的关键路径的过程，并给出每一个事件和活动的最早开

始时间和最晚开始时间。（选做题）

A0=2 A0=2 A1=3 A

A2=4 C

6、试画出下列有向网的逆邻接表。 A3=1 B A5=2 A4=5 D A6=3 A9=4 A7=4 E A8=5 G A10=4 F

第8章 查找

1、填空题

（1）设哈希表长M=14，哈希函数H（KEY）=KEY % 11，表中已有四个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7

其余地址为空，若用线性探测处理冲突，key=49 的结点地址是________。 （2）装载因子是指___________________

（3）在线性表的散列存储中，处理冲突的方法有________和__________两类。 （4）有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100｝，当用二分法查找值82的结

点时，__________比较后查找成功。

（5）分块查找时是分两步完成的，即________和__________。

（6）冲突指的是 ，当装载因子太大越大，发生冲突的可能性就越大。处理冲突

的两类主要方法是 。

2、设有一组关键字（17,13,14,153,29,35）需插入到表长为12的散列表中，请完成下列操作：

（1） 利用除留余数法设计一个适合该散列表的散列函数；

（2） 将上述数据利用该散列函数插入到散列表中，若用线性探测法处理冲突，

画出其结构； 序号 数据 0 1 2 3 4 5 6 7 8 9 10 11 （3）其装载因子是多少？

（4）在等概率情况下查找成功时的平均查找长度是多少？

3、二分查找的先决条件是什么？请简述其查找方法。

4、设计出对有序表进行二分查找的算法。

5、将{50,20,10,100,120,30,110,60,70,90,80,40}依次插入到一棵原来为空的二叉排序树中，画出插入这些关键字后的二叉排序树，中序遍历该二叉排序树。

6、设有2000个元素D的表，希望用分块顺序查找方法进行查找，问： （1）每块的理想长度是多少 ？ （2） 分多少块最理想？ （3） 平均查找长度是多少？

7、依次输入元素：10，6，8，3，42，25，7，30，27，60试生成一棵二叉排序树， （1）画出生成之后的二叉排序树；

（2）写出中序遍历该二叉排序树的序列；

（3）假定每个元素的查找概率相等，计算查找成功时的平均查找长度。

第9章 排序

1、填空题

（1）将一组任意排列的数据重新排列成按关键字有序的序列的操作过程称为 。 （2） 快速排序算法在最好情况下的时间复杂度为______。

（3）下面4个序列中，只有 满足堆的定义。

A. 97,76,85,49,76,38,27,13 B. 97,13,85,76,49,27,38,76 C. 97,85,38,27,76,49,76,13 D. 97,85,38,76,76,49,27,13

（4）主关键字是指 。

（5）将n个无序数据排列成从大到小的有序序列,完成下列算法。

typedef struct

{ int key; …………

} elemtype;

void select_sort(elemtype a[], int n )

{ /* 该算法的策略是，在待排序的数据r[1]..r[n]中选择最大值 */

int i , j , t, k;

for (i=1 ; ________; i++) { max = i ;

for (j=________ ; i<=n ; i++)

if (r[max].key

{ }

} }

该算法适于何种情形使用？

（6）如果要把序列{50,16,23,68,90,70,71}建成堆，只需将16与_______交换。 2、简述什么是内部排序？什么是外部排序？

3、什么是排序的稳定性？

4、已知数据表A中每个元素距其最终位置不远，则采用何种排序算法最省时间？

5、某地参加高考的学生人数为550000人，采用什么排序方法来完成排序最好。

6、对于给定的关键值序列 {19,23,3,15,7,21,29，1} ，写出归并排序的排序过程。

7、对{ 278, 109, 63, 930, 589, 184, 505, 269, 8, 83}进行基数排序，写出每一趟的排序结果。对第一趟排序，写出借助队列进行基数排序的过程。

8、用图示方法画出将序列｛34,12,25,60,41,23｝按直接插入法排序的过程。

9、对下列关键字序列用快速排序法排序，哪一种情况速度最快？哪一种 情况速度最慢？为什麽？

A（19，23，3，15，7，21，28） B（ 23，21，28，15，19，3，7） C （3，7，15，19，21，23，28）

10、判断下列序列是否为堆? （1）（100，86，48，73，35，39，42，57，66，21） （2）(12,20,33,65,24,56,48,92,86,23)

（3）(103,97,56,38,66,23,42,12,30,52,06,20) （4）(5,56,20,23,40,38,29,61,35,76,28,100)

11、写一算法： 在1000000个无序的数据中，选择前100个大数。

12、写一算法：对本班学生某门课程的成绩进行排序（方法自定）。