2020年10月自考数据结构导论真题（四）

三、应用题:本大题共5小题,每小题6分,共30分。

29.题29图给出了一个稀疏矩阵 A,请写出该稀疏矩阵的三元组表。

30.已知二叉树如题30图所示,请将该二叉树转换为对应的森林。

31.设某通信系统中一个待传输的文本有6个不同字符,它们的出现频率分别是0.5,0.7,1.4,2.2,2.4,2.8,试画出哈夫曼树,并给出每个字符的哈夫曼编码。(要求任一结点的左孩子权值小于右孩子)

32.选定散列函数为 H(key)= keymod13,试用链地址法建立键值为26,41,25,05,07,15,12,49,51,31,62的散列表。

33.对于给定的一组键值:83,40,63,13,84,35,96,57,39,79,61,15,请分别写出直接选择排序和冒泡排序的第一趟排序结果。

四、算法设计题:本大题共2小题,每小题7分,共14分。

34.写出一个将线性表的顺序表存储方式(数组a、表长为n)改成单链表存储方式(其头结点由头指针head指向)的算法。设函数头为:Node*CreateLinkedList(DataTypea[],intn)

35.以二叉链表作存储结构,请写出二叉链表类型定义;利用二叉树遍历的递归算法,试编写求二叉树高度的算法。