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

计算机——《数据结构》

第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 << \ }

if (p < 0 || p > curLen) { // 检查插入位置是否合法

cout << \ }

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 << \ return false ; }

本文来源：https://www.bwwdw.com/article/lmmh.html