4. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树,它的带权路径长度为______
__。
A 24 B 48 C 72 D 53
二、填空题(每空 1 分,共 32 分)
1. 一个算法的时间复杂度为(3n
2
+2nlog
2
n+4n-7)/(5n),其数量级表示为________。
2. 在以 HL 为表头指针的带表头附加结点的单链表和循环单链表中,链表为空的条件分
别为________和________。
3.一个广义表中的元素分为________元素和________元素两类。
4.从一个链栈中删除一个结点时,需要把栈顶结点的_________域的值赋给________。
5.在进行函数调用时,需要把每个实参的值和调用后的________传送给被调用的函数
中。
6.对于一棵具有 n 个结点的二叉树,若一个结点的编号为 i(1≤i≤n),则它的左孩子结
点的编号为________,右孩子结点的编号为________,双亲结点的编号为________。
7.在一棵高度为 5 的理想平衡树中,最少含有________个结点,最多含有________个
结点。
8.在一个堆的顺序存储中,若一个元素的下标为 i(0≤i≤n-1),则它的左孩子元素的下
标为______,右孩子元素的下标为________。
9.在一个具有 n 个顶点的无向完全图中,包含有________条边,在一个具有 n 个顶点
的有向完全图中,包含有________条边。
10.对于一个具有 n 个顶点和 e 条边的有向图和无向图,若采用边集数组表示,则存
于数组中的边数分别为________和________条。
11.以二分查找方法从长度为 12 的有序表中查找一个元素时,平均查找长度为______
__。
12.假定一个线性表为(12,23,74,55,63,40,82,36),若按 Key % 3 条件进行划分,
使得同一余数的元素成为一个子表,则得到的三个子表分别为_____________、__________
___和_____________。
13.在线性表的散列存储中,装填因子又称为装填系数,若用 m 表示散列表的长度,
n 表示待散列存储的元素的个数,则等于________。
14.在一棵 m 阶 B_树上,每个非树根结点的关键字数目最少为________个,最多为__
______个,其子树数目最少为________,最多为________。
15.在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为________,整个堆
排序过程的时间复杂度为________。
16. 快速排序在平均情况下的时间复杂度为________,在最坏情况下的时间复杂度为__
______。
三、运算题(每小题 6 分,共 24 分)
1. 假定一棵二叉树广义表表示为 a(b(c),d(e,f)),分别写出对它进行先序、中序、后序、
按层遍历的结果。
先序:
中序:
后序:
按层: