数据结构 问题求解题

1. 用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。

2. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按归并排序方法进行排序时的变化过程，每归并一次书写一个次序。

3. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按快速排序方法进行排序时的变化过程，每划分一次书写一个次序。

4. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按堆排序方法进行排序时的变化过程，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

5. 已知树T的先序遍历序列为ABCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。

6. 对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。 初始堆：________________________________ 第1趟：________________________________ 第2趟：________________________________ 第3趟：________________________________

7. 在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。

8. 若对序列（76，38，65，13，97，27，50，49）采用堆积排序法（按照值的大小从小到大）进行排序，请分别在下表中写出每一趟的结果： 原始序列 76 38 65 13 97 27 50 49 第1趟结果 第2趟结果 第3趟结果 第4趟结果

9. 已知一带权连通图采用邻接矩阵存储方法，并且邻接矩阵采用三元组表表示，其中，第一个三元组 (5，5，16)分别表示邻接矩阵的行数、列数字与非零元素的个数，从第二个三元组开始，依次按行序为主序的次序分别给出16个非零元素，它们依次为(1，2，7)，(1，3，6)，(1，4，9)，(2，1，7)，(2，3，8)，(2，4，4)，(2，5，4)，(3，1，6)，(3，2，8)，(3，4，6)，(4，1，9)，(4，2，4)，(4，3，6)，(4，5，2)，(5，2，4)，(5，4，2)；请分别画出该带权连通图的两棵最小生成树。

10. 已知散列范围为[0：9]，散列函数为H(key)=key MOD 9，处理冲突的方法为链地址法，请画出依次插入关键字8,10,14,19,21,23,28,32以后的哈希表。

1

11. 已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组 ABDIC□EF□□C□□□H

请分别写出该二叉树的前序遍历序列与中序遍历序列。

12. 折半查找过程可以利用一棵称之为“判定树”的二叉树来描述，请画出在长度为13的表中进行折半查找对应的判定树。

13. 设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。

14. 已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边的信息存放于邻接矩阵中，邻接矩阵为 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0

请写出从顶点A出发对该图进行深度优先搜索后得到的顶点序列。

15. 若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟排序的结果。 原 始 序 列 49 38 27 13 97 76 50 65 第1趟的结果 第2趟的结果 第3趟的结果 第4趟的结果

16. 已知一稀疏矩阵的三元组存储如下所示，请画出其十字链表表示。 6 7 8 1 4 6 2 3 5 2 6 2 4 2 7 5 1 2 5 5 1 5 6 4 6 1 8

17. 若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD 9，并且采用链地址方法处理冲突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后，该杂凑表的状态。

18. 若一棵树有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，求该树中叶结点的个数。(要求写出推导过程)

19. 已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表表示。

2

20. 现有一组单词(WEK,SUN,MON,TUE,WED,THU,FRI,SAT),其相应的散列函数值为(3，2，6，3，2，5，6，0)，散列表长度为10(散列地址空间为0..9)，要求： (1)构造该闭散列表，并用线性探测法解决冲突； (2)若对每个元素查找一次，求总的比较次数。

21. 设要将序列(Q，H，C，Y，P，A，M，S，R)按字母升序排序，请画出采用堆排序方法时建立的初始堆及第一次输出堆顶元素后筛选调整以后的堆。

22. 假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。

23. 已知两个4×5的稀疏矩阵的三元组表分别如下： 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 -22 2 3 4 -25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 请画出这两个稀疏矩阵之和的三元组表。

24. 从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。 (1)画出该二叉排序树

(2)画出删去该树中元素值为90的结点之后的二叉排序树。

25. 画出在一个初始为空的AVL树中依次插入3，1，4，6，9，8，5，7时每一步插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。

26. 以知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉搜索树。

27. 设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋ mod m，给定的关键码序列为19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功的平均搜索长度。

0 1 2 3 4 5 6 7 8 9 10 11 12 搜索成功时的平均搜索长度为：ASLsucc= 搜索不成功时的平均搜索长度为：ASLunsucc=

28. 某二叉树的结点数据采用顺序存储表示如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B

3

（1）试画出此二叉树的图形表示。（3分）

（2）写出结点D的双亲结点及左、右子女。（3分）

（3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（3分）

29. 设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出用希尔排序每一趟的结果。增量序列取为5，3，2，1。（每一趟2分，共8分）

30、设散列表的长度为13，散列函数为H（k）=k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（8分）

0 1 2 3 4 5 6 7 8 9 10 11 12

24. 对于一个n×n的矩阵A的任一矩阵元素a[I][j]，按行存储时和按列存储时的地址之差是多少。（若设两种存储的开始存储地址LOC（0，0）及元素所占存储单元d相同）

25. 假定一组数据对象为（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵AVL树（高度平衡的二叉搜索树），根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。 数据： 调整：

26. 设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。 A[6][2]的存储字地址：

27. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a

高度： 度为2的结点数： 度为1的结点数： 度为0的结点数：

28. 假定一组记录为(36,75,83,,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？

左单旋转结点个数： 右单旋转结点个数： 先左后右双旋转结点个数： 先右后左双旋转结点个数： 不调整结点个数：

29. 已知一个带权图的顶点集V和边集G分别为：

40 28 16 56 50 32 30 63 4

V={0,1,2,3,4,5,6};

E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18, (4,5)6,(4,6)6,(5,6)12};

试根据迪克斯特拉(Dijkstra)算法求出从顶点0到其余各顶点的最短路径，在下面填写对应的路径长度。

顶点： 0 1 2 3 4 5 6

路径长度：

0

30. 已知一个数据表为{36,25,25*,62,40,53}，请写出在进行快速排序的过程中每次划分后数据表的变化。

(0) [36 25 25* 62 40 53] (1) (2) (3)

31．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分） （1） d,e,b入队 （2） d,e出队 （ V03）1i,j1入队0 001（ 出队V4）0b11 11（ 入队1V25）1n,o,p011 32V0开始的V3．已知无向图1的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从0110G深度优先搜索的序列。V401110（4分）

v0v1v2v3v4

33．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）

元素下标 比较次数

1 2 3 4 5 6 7 8 9 10 34．已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（6分）

35．设散列表HT[0..12],即表的大小为m=13。采用双散列法解决冲突。散列函数和再散列函数分别为：

H0（key）=key% 13; 注：%是求余数运算（=mod） Hi=(hi-1+REV(key+1)%11+1)%13; ⅰ=1,2,3………,m-1

其中，函数REV(x)表示颠倒10进制数x的各位，如REV(37)=73, REV(7)=7等。若插入的关键码序列为｛2，8，31，20，19，18，53，27｝试画出插入这8个关键码后的散列表。

0 1 2 3 4 5 6 7 8 9 10 11 12

5

36．设有一个1010的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。

37．已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。 前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, E, F, D, I, H, J, G 后序序列：

38．已知一个有序表 ( 15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 ) 顺序存储于一维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34, 56, 58, 63, 94时的比较次数。

34 56 58 63 94

元素值

比较次数

39．设散列表为HT[17], 待插入关键码序列为 { Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec }，散列函数为H (key) = i  2，其中，i是关键码第一个字母在字母表中的序号。现采用线性探查法解决冲突。 字母 A 序号 1 字母 N

试画出相应的散列表；

计算等概率下搜索成功的平均搜索长度；

40. 已知某二叉树的前序序列为EBADCFHGI，中序序列为ABCDEFGHI，请给出二叉树的后序序列。

41. 将关键码53，78，65，17，87，09，81，45，23依次插入到一棵初始为空的二叉搜索树中，画出每插入一个关键码后的二叉搜索树。

42. 设有150个记录要存储到散列表中，并利用线性探查法解决冲突，要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？（设α是散列表的装载因子，则有ASLsucc=（1+1/（1-α））/ 2）。

43. 假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。试为这8个字母设计不等长Huffman编码，并输出该电文的总码数。

A b c d e f g h 电文总长度：

6

B 2 O C 3 P D 4 Q E 5 R F 6 S G 7 T H 8 U I 9 V J K L Y M Z 10 11 12 13 W X 序号 14 15 16 17 18 19 20 21 22 23 24 25 26

44. 设有顺序表中的元素依次为017，094，1，170，275，503，512，553，612，677，675，7，908。试画出对其进行折半搜索时做性能分析用的扩充二叉搜索树（判定树），并计算搜索成功时的平均搜索长度和搜索不成功进的平均搜索长度。 搜索成功时的平均搜索长度ASLsucc= 搜索不成功时的平均搜索长度ASLunsucc=

45. 一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层上自左向右，顺序从1开始对全部结点进行编号，试问： (1)第j层的结点个数是多少(j=0,1,2,3,4…..h) (2)编号为I的结点(若存在)的编号是多少？ (3)编号为I的结点(若存在)的编号是多少？

(4)编号为I的结点有右兄弟的条件是什么？它的右兄弟结点的编号是多少？

7