结点的度

(1)【◆题库问题◆】：[名词解释] 结点的度

【◆参考答案◆】：
树的某个结点的分支（子树）个数叫做该结点的度。

(2)【◆题库问题◆】：[判断题] 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。
A．正确
B．错误

【◆参考答案◆】：正确

(3)【◆题库问题◆】：[单选] 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素r[i+1]的插入位置为r[j]，则需要移动元素的次数为（）。
A．j-i
B．i-j-1
C．i-j
D．i-j+1

【◆参考答案◆】：D

(4)【◆题库问题◆】：[问答题] 写出下列用快排序对下列序列进行两次划分的过程及结果。

【◆参考答案◆】：
18 26 21 13 17 21 【37】 82 69 77 48 39 55 51

(5)【◆题库问题◆】：[单选] 在深度为7的满二叉树中，叶子结点的个数为（）
A．32
B．31
C．64
D．63

【◆参考答案◆】：C

(6)【◆题库问题◆】：[单选] 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）。
A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B．在第i个结点后插入一个新结点（1≤i≤n）
C．删除第i个结点（1≤i≤n）
D．将n个结点从小到大排序

【◆参考答案◆】：A

(7)【◆题库问题◆】：[填空题] 函数depth实现返回二叉树的高度，请在空格处将算法补充完整。intdepth（Bitree*t）{if（t==NULL）return0；else{hl=depth（t->lchild）；hr=（））；if（（））returnhl+1；elsereturnhr+1；}}

【◆参考答案◆】：depth（t->rchild hl>hr

(8)【◆题库问题◆】：[单选] 一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（）。
A．a，b，c，d，e
B．d，e，c，b，a
C．d，c，e，a，b
D．e，d，c，b，a

【◆参考答案◆】：C

(9)【◆题库问题◆】：[判断题] 数据元素是数据的最小单位。
A．正确
B．错误

【◆参考答案◆】：正确

(10)【◆题库问题◆】：[问答题] 选取哈希函数H（k）=（k）MOD 11。用二次探测再散列处理冲突，试在0-10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情况下查找成功时的平均查找长度。

【◆参考答案◆】：（1）表形态：(2)ASL：ASL(7)=(1*5+2*1+3*1)/7=(5+2+3)/7=10/7