数据结构作业题及参考答案.docx

1）先序序列和中序序列相同3）先序序列和后序序列相同2)4)中序序列和后序序列相同中序序列与层次遍历序列相同4.数皆为设T是一棵二叉树，除叶子结点外，其它结点的度 2,若T中有6个叶结点，试问：(1) T树的最大深度 Kmax=?g小可能深度 Kmin=?(2) T树中共有多少非叶结点？一棵有n(n>0)个结点的d度树，若 d个链域，则在表示该树的多(3)若叶结点的权值分别为123,4,5,6 o请构造一棵哈曼夫树，弁计算该哈曼夫树的带权路径长度wpl5.用多重链表表示，树中每个结点都有重链表中有多少个空链域？为什么？储，则A[7,1]和A[2,4]的第一个字节的地址是多少?1. 在一个单链表 HL 中，若要向表头插入一个由指针HL=p; p_>n ext=HL;数据结构作业题（二）p 指向的结点，则执行（B 、 p->next=HL; HL=p;3. 一个数组元素A、 * （a+i）与(B、 a+i）的表示等价a+i D、 &a+iC p_>n ext=HL; p=HL;D 、 p->next=HL->next; HL->next=p;3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（24 B 、 48 C、 72 D、 a[i] 534. 下面程序段的时间复杂度为（for ( i nt i=0; i

2. 若对关键字序列（ 43 ， 02 ， 80， 48， 26 ， 57 ， 15， 73 ， 21 ， 24， 66）进行一趟增量为 3 的希尔排序，则得到的结果为 °3. 一个算法的时间复杂度为 （ 3n2+2nlog2n+4n-7 ） /（ 5n） ，其数量级表示为 °4. 在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为和05. 快速排序在平均情况下的时间复杂度为 ，在最坏情况下的时间复杂度为 °6. 假定对长度n=50 的有序表进行二分查找，则对应的判定树高度为 ，判定树中前 5 层的结点数为 ，最后一层的结点数为 °7. 假定一棵树的广义表表示为 A（ B（ C,D（E,F,G） ,H （I,J ））），则度为 3、 2、 1、 0 的结点数分别为 、 和 个°&在一棵二叉树中，假定双分支结点数为9?数据的逻辑结构被分为 、 10?在一个长度为n的顺序存储线性表中，向第 前依次后移 个元素5个，单分支结点数为6个，则叶子结点数为一个四种i个元素(1

现采用某种方法对它们进行排序，其每趟排序结果如下第一趟:20,13,21,25,46,27,68,35,84第三趟:13,20,21,25,27,35,46,68,842.有一随机数组(25,84,21,46,13,27,68,35,20), 则该排序方法是什么？初 始:25,84,21,46,13,27,68,35,20第二趟:13,20,21,25,35,27,46,68,843.请在()内填入正确的排序方法设一数组中原有数据如下 结果15, 13, 20, 18, 12, 60卜面是一组由不同排序方法进行一遍排序后的()排序的结果为：)排序的结果为:)排序的结果为:12, 13,13, 15,13, 15,15, 18, 20, 6018, 12, 20, 6020, 18, 12, 604.数皆为设T是一棵二叉树，除叶子结点外，其它结点的度 2,若T中有6个叶结点，试问：T树的最大深度 Kmax=T®小可能深度 Kmin=?T树中共有多少非叶结点？若叶结点的权值分别为123,4,5,6 请构造一棵哈曼夫树，弁计算该哈曼夫树的带权路径长度5.用多重链表表示，树中每个结点都有一棵有n(n>0)个结点的d度树，若 d个链域，则在表示该树的多重链表中有多少个空链域？ 为什么 ？6?有一个二维数组A[0:8,1:5] ，每个数组元素用相邻的 4 个字节存储， 存储器按字节编址，假设存储数组元素 A[0,1] 的第一个字节的地址是0，那么存储数组的最后一个元素的第一个字节的地址是多少？若按行存储 ， 则 A[3,5] 和 A[5,3] 的第一个字节的地址是多少？若按列存储，则 A[7,1] 和 A[2,4] 的第一个字节的地址是多少？数据结构作业题(三)一、单选题(每题2分，共10分)1、在长度为n的顺序存储的线性表中, 删除第i个元素(1