2019年西南大学[0012]《数据结构》作业答案

46、中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。

有序

47、若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间.

顺序表

48、设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。d/2

49、快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。

o(n*n),o(nlog2n)

50、设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。

9,501

51、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

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

78

15

03

57

45

20

31

23

36

12

查找成功的平均查找长度：ASL SUCC=14/10=1.4

52、写出用直接插入排序将关键字序列{54,23,89,48,64,50,25,90,34}排序过程的每一趟结果。初始： 54，23，89，48，64，50，25，90，34

1：（23，54），89，48，64，50，25，90，34

2：（23，54，89），48，64，50，25，90，34

3：（23，48，54，89），64，50，25，90，34

4：（23，48，54，64，89），50，25，90，34

5：（23，48，50，54，64，89），25，90，34

6：（23，25，48，50，54，64，89），90，34

7：（23，25，48，50，54，64，89，90），34

8：（23，25，48，50，54，64，89，90，34）

53、阅读以下二叉树操作算法，指出该算法的功能。

Template void BinTree ：：

unknown (BinTreeNode*t) {

BinTreeNode< Type> *p =t, *temp;

if (p!=NULL) {

temp = p→leftchild;

p→leftchild = p→rightchild;

p→rightchild = temp;

unknown(p→leftchild);

undnown(p→rightchild);

}

}

该算法的功能是：________________________________

交换二叉树的左右子树的递归算法。

54、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

EDCBIHJGFA

55、

已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。

划分次序

划分结果

第一次

[38 24 40]46 [56 80 95 79]

第二次

24[38 40]46 [56 80 95 79]

第三次

24 38 40 46 [56 80 95 79]

第四次

24 38 40 46 56 [80 95 79]

第五次

24 38 40 46 56 79 [80 95]

第六次

24 38 40 46 56 79 80 95

56、设待排序序列为{10,18,4,3,6,12,1,9,15,8}请写出希尔排序每一趟的结果。增量序列为5，3，2，1。

初始：10，18，4，3，6，12，1，9，15，8

d=5: 10，1，4，3，6，12，18，9，15，8

d=3: 3，1，4，8，6，12，10，9，15，18

d=2: 3，1，4，8，6，9，10，12，15，18

d=1: 1，3，4，6，8，9，10，12，15，18

57、写出下列程序的时间复杂度

s=0;

for i=0; i

for(j=0; j

s+=B[i][j];

sum=s;

0（n^2）

58、设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算

后，有

① front=11，rear=19; ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

(1)L=(40+19-11)%40=8 (2) L=(40+11-19)%40=32

59、写出下列程序的时间复杂度

for(i=0; i

for (j=0; j

A[i][j]=0;

O(m*n)

60、设给定一个权值集合W=(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度WPL。

哈夫曼树略，WPL=78

61、设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。

链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA