湖南科技大学数据结构综合应用题

第1页 共13页

1．简述栈的基本操作

2．给定权值组W={1，3，78，14，20，28}，建立哈夫曼树。 3．试求下面的网络的最小生成树

10 1C10

69 B15E5 613 6AD

84.对一组关键字49，7，50，5，94，16，90，29，71，使用希尔排序，写出对d13时的一趟排序的结果。 1-4题答案：

1、栈的基本操作有：

栈的建立，判栈满，判栈空，压栈，退栈和取栈顶元素等。 2、

144

66

7838

28 1820 414

3 13、 41 96 536 625 84、

4950594169029717

1649295090947175

5．写出队列的基本操作。

a 6．对下面的二叉树

（１） 其中序遍历序列为

b

c （２）其后序遍历序列为 d e

5

g

h 7．给定一组关键字序列12，7，51，32，23，试构造一棵查找树。

8．对一组关键字49，7，50，5，94，16，90，29，71，使用快速排序，试给出第一次划分过程。

5-8题答案：

5．队列的基本操作有：

队列的建立，判队空，判队满，入队、出队及取队首元素等。

计算机——《数据结构》

6．（１）中序遍历序列：d g b a e c h f （２）后序遍历序列：g d b e h f c a 7．

12

７ 51

32

23

8．49 7 50 5 94 16 90 29 71

head tail

49 7 50 5 94 16 90 29 71

head tail

29 7 50 5 94 16 90 49 71 head tail 29 7 49 5 94 16 90 50 71 head tail 29 7 16 5 94 49 90 50 71 head tail

29 7 16 5 49 94 90 50 71 headtail

9．

// 设元素的类型为T， aList是存储顺序表的数组， maxSize是其最大长度； // p为新元素value的插入位置，插入成功则返回true， 否则返回false

template bool arrList :: insert (const int p, const T value) { int i;

if (curLen >= maxSize) { // 检查顺序表是否溢出 cout << \"The list is overflow\"<if (p < 0 || p > curLen) { // 检查插入位置是否合法

cout << \"Insertion point is illegal\"<for (i = curLen; i > p; i--)

aList[i] = aList[i-1]; // 从表尾curLen -1起往右移动直到p aList[p] = value; // 位置p处插入新元素 curLen++; // 表的实际长度增1 return true; }

第2页 共13页

计算机——《数据结构》

第3页 共13页

10．图如下，请画出Kruskal算法构造最小生成树的过程。

1 5 6

1 2 4 5 5

2 3 3 6 4

5 6

6

11． 一份电文中共使用的字符有A，B，C，D，E，它们出现的频率依次为4，7，5，2，9。试画出其对

应的Huffman树

12．用拉链法建立Hash表，Hash函数为H(key)=key mod 11,Hash表长度为10，现有一组关键字（61，18，

30，72，13，24，12，11），请画出相应的Hash表。

13．怎样将一棵树转化成等价的二叉树？试画出下列树所对应的二叉树，要求有中间过程图。

3

5 2

64 1

9-13题答案：

10、

1 1

4 1 2 4 2

3

3

5 6 5 6

1 1

4 4 1 1 2 2

2 2 3 3 3

5 6 5 6

计算机——《数据结构》

第4页 共13页

11、 12、

1 2 2 1 1 4 3 4 2 2 5 1 4 3 3 6 3 4 5 5 6 27 9 E 7 B 5 C 2 D 6 4 A 11 18

61 mod 11=6 18 mod 11=7 30 mod 11=7 72 mod 11=6 13 mod 11=2 24 mod 11=1 12 mod 11=1 11 mod 11=0

13、树转化为二叉树的方法如下：

① 将树中的各兄弟之间加一条连线。

② 对于任一结点，除保留宽经与最左边孩子的连线外，删除它与其它孩子之间的分支。

○

③ 以树的根这轴心，将整棵树按顺时针方向旋转大约45。

0 1 2 3 4 5 6 7 8 9 11 ^ 24 13 ^ 12 ^ 61 18 72 ^ 30 ^ 计算机——《数据结构》

第5页 共13页

3

5 2

6 4 1

3

5 2

6 4 1

3

2

1 5 4 6

14、画出具有三个结点的二叉树的所有形态。

15、图如右，请画出prim算法构造最小生成树的过程。

16、对于如下无向图，请画出其深度优先搜索和广度优先搜索生成的树（画出一棵即可）。

1 3

5

2 4

17、用线性探测法建立Hash表，Hash函数为H(key)=key mod 11,Hash表长度为10，现有一组关键字（61，

18，30，72，13，24），请画出相应的Hash表。

18、// 设元素的类型为T；aList是存储顺序表的数组； p为即将删除元素的位置 // 删除成功则返回true，否则返回false

template // 顺序表的元素类型为T bool arrList :: delete(const int p) { int i; if (curLen <= 0 ) { // 检查顺序表是否为空 cout << \" No element to delete \\n\"<计算机——《数据结构》

第6页 共13页

if (p < 0 || p > curLen-1) { // 检查删除位置是否合法 cout << \"deletion is illegal\\n\"<aList[i] = aList[i+1]; // 从位置p开始每个元素左移直到curLen curLen--; // 表的实际长度减1 return true; }

14-18题答案： 14、 A A A A A

B B B C B B

C C C C

15、 1 1 1 1

1 1 1 2 2

5 5 2 3 3 3 5

11

4 1 1 22 5 5 2 4 2 4 3 3 3

5 6 56

16、注意：生成树是不唯一的，应该是一个生成树森林。所以此题还存在其它画法。

1 3 5 2 4 计算机——《数据结构》

第7页 共13页

设从结点1出发开始深度优先搜索，得到如下一棵深度优先生成树：

1 3

5

2 4

设从结点1出发开始广度优先搜索，得到如下一棵广度优先生成树：

1 3 5

2 4 17、

0 1 2 3 4 5 6 7 13 24 61 18 61 mod 11=6 18 mod 11=7 30 mod 11=8

72 mod 11=6→7→8→9 13 mod 11=2 24 mod 11=2→3

8 30 9 72 19．设一棵二叉树的先序遍历序列为： A B D F C E G H

中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。（5分）

（2）画出这棵二叉树的后序线索树。（5分） （3）画出由这棵二叉树转换成的树（或森林）。（5分）

20．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。（要求画出Huffman树并写出编码）（15分）

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

22．对于以下的图，写出它的四个不同的拓扑有序序列。（10分）

计算机——《数据结构》

第8页 共13页

23．采用哈希函数H（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51。 （1） 构造哈希表（画示意图）；（5分） （2） 求装填因子；（1分）

（3） 等概率下成功的和不成功的平均查找长度。（4分）

24．数据结构与数据类型有什么区别？

24.“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。

25．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。 *25.该算术表达式转化的二叉树如右图所示。

++ +fgh

+*

a+bc de

26．将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果） D G A J H I E B C L M K N O F

P A

B D E G C

H F I KO J L M

P N O 计算机——《数据结构》

第9页 共13页

27. 设一棵二叉树的先序、中序遍历序列分别为

先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。

（2）画出这棵二叉树的后序线索树。 （3）将这棵二叉树转换成对应的树（或森林）。 27. A A A C C BBCBM D EM H DEF G DE null(3) FGHFGH

28. 已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

29. 对有五个结点{ A,B, C, D, E}的图的邻接矩阵，

01003010060020100500 （1）．画出逻辑图 ； （2）．画出图的十字链表存储； （3）．基于邻接矩阵写出图的深度、广度优先遍历序列；

. 30.一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。

计算机——《数据结构》

第10页 共13页

设顶点集合为{1，2，3，4，5，6}， 1 1 2 由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中， 1 1 各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。 2 4 3

1 3 1

6 5 1

31. 试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。

18 1 2 5 6 12 23 5 3 4 8 7 15 25 7 10 4 6 20

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）}

32. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K为关键字，用线性探测再散列法处

理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题： (1) 画出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较?

(3) 若查找关键字60，需要依次与哪些关键字比较?

(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

（1） 散列地址 0 关键字 比较次数 1 1 1 2 6 3 3 4 5 6 7 8 1 9 2 10 11 12 13 14 15 16 17 30 31 46 47 1 1 3 3 1 32 17 63 49 24 40 10 （2）查找关键字63，H（k）=63 MOD 16=15，依次与31，46，47，32，17，63比较。 （3）查找关键字60，H（k）=60 MOD 16=12，散列地址12内为空，查找失败。

（4）ASLsucc=23/11

33. 选取哈希函数Ｈ（key）=key mod 7,用链地址法解决冲突。试在０-６的散列地址空间内对关键字序列｛31,23,17,27,19,11,13,91,61,41｝构造哈希表，并计算在等概率下成功查找的平均查找长度。

计算机——《数据结构》

第11页 共13页

ASLsucc =15/10

34. 设散列函数H(k)=K mod 7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。

查找时，对关键字49,22,38,32,13各比较一次，对21,18各比较两次

35. 设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。

可以做到。取a与b进行比较，c与d进行比较。设a>b,c>d(ad，则有序a>b>d；若bd>b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。

36. 请阅读下列算法，回答问题

PROCEDURE sort（r，n） BEGIN

FOR i:=2 TO n DO

BEGIN

x:=r(i)；r(O):=x；j:=i-1； WHILE x.keyr(j+1):=r(j); j:=j-1 END; r(j+1):=x END

END;

问题一：这是什么类型的排序算法，该排序算法稳定吗？

问题二：设置r(O)的作用是什么？若将WHILE—DO 语句中判断条件改为x.key<=r(j).KEY,该算法将会有什么变化，是否还能正确工作？

计算机——《数据结构》

第12页 共13页

(1)此为直接插入排序算法，该算法稳定。

(2)r[O]的作用是监视哨，免去每次检测文件是否到尾，提高了排序效率。 采用x.key<=r[j].key描述算法后，算法变为不稳定排序，但能正常工作。

37. 对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

初始序列：[28],07,39,10,65,14,61,17,50,21 21移动：21,07,39,10,65,14,61,17,50,[]

39移动：21,07,[],10,65,14,61,17,50,39 17移动：21,07,17,10,65,14,61,[],50,39 65移动：21,07,17,10,[],14,61,65,50,39 14移动：21,07,17,10,14,[28],61,65,50,39

38. 如果只要找出一个具有n个元素的集合的第k（1≤k≤n）个最小元素，你所学过的排序方法中哪种最适合？给出实现的思想。

在具有n个元素的集合中找第k（1≤k≤n）个最小元素，应使用快速排序方法。其基本思想如下：设n个元素的集合用一维数组表示，其第一个元素的下标为1，最后一个元素下标为n。以第一个元素为“枢轴”，经过快速排序的一次划分，找到“枢轴”的位置i，若i=k，则该位置的元素即为所求；若i>k，则在1至i-1间继续进行快速排序的划分；若i39. 全国有10000人参加物理竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出。而对落选的其他考生，不需排出名次，问此种情况下，用何种排序方法速度最快？为什么？

在内部排序方法中，一趟排序后只有简单选择排序和冒泡排序可以选出一个最大（或最小）元素，并加入到已有

2

的有序子序列中，但要比较n-1次。选次大元素要再比较n-2次,其时间复杂度是O(n)。从10000个元素中选10个元素不能使用这种方法。而快速排序、插入排序、归并排序、基数排序等时间性能好的排序，都要等到最后才能确定各元素位置。只有堆排序，在未结束全部排序前，可以有部分排序结果。建立堆后，堆顶元素就是最大（或最小，视大堆或小堆而定）元素，然后，调堆又选出次大（小）元素。凡要求在n个元素中选出k(k<2)个最大（或最小）元素，一般均使用堆排序。因为堆排序建堆比较次数至多不超过4n,对深度为k的堆，在调堆算法中进行的关键字的比较次数至多为2(k-1)次，且辅助空间为O(1)。

40.// 插入数据内容为value的新结点作为第i个结点

template // 线性表的元素类型为T bool lnkList :: insert(const int i, const T value) { Link *p, *q;

if ((p = setPos(i -1)) == NULL) { // p 是第i个结点的前驱 cout << \" 非法插入点\"<q = new Link(value, p->next); p->next = q;

计算机——《数据结构》

第13页 共13页

if (p == tail) // 插入点在链尾，插入结点成为新的链尾 tail = q; return true; }

41. template // 线性表的元素类型为T bool lnkList:: delete((const int i) { Link *p, *q;

// 待删结点不存在，即给定的i大于当前链中元素个数 if ((p = setPos(i-1)) == NULL || p == tail) { cout << \" 非法删除点 \" <q = p->next; // q是真正待删结点

if (q == tail) { // 待删结点为尾结点，则修改尾指针 tail = p;

p->next = NULL: delete q; }

else if (q != NULL) { // 删除结点q 并修改链指针 p->next = q->next; delete q; }

return true; }

42.template

void InsertSort (Record Array[], int n) { //Array[]为待排序数组，n为数组长度 Record TempRecord; // 临时变量

for (int i=1; i//从i开始往前寻找记录i的正确位置 int j = i-1;

//将那些大于等于记录i的记录后移

while ((j>=0) && (TempRecord < Array[j])) { Array[j+1] = Array[j]; j = j - 1; }

//此时j后面就是记录i的正确位置，回填 Array[j+1] = TempRecord; } }