判定树

(1)【◆题库问题◆】：[名词解释] 判定树

【◆参考答案◆】：
树中每个结点表示表中的一个记录，结点里的值为该记录在表中的位置，通常称这个查找过程的二叉树为判定树。

(2)【◆题库问题◆】：[判断题] 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。
A．正确
B．错误

【◆参考答案◆】：正确

(3)【◆题库问题◆】：[填空题] 线性结构中元素之间存在（）关系，树形结构中元素之间存在（）关系，图形结构中元素之间存在多对多关系。

【◆参考答案◆】：一对一,一对多

(4)【◆题库问题◆】：[名词解释] 散列函数

【◆参考答案◆】：
一个把查找表中的关键字映射成该关键字对应的地址的函数。

(5)【◆题库问题◆】：[判断题] 折半查找所对应的判定树，既是一棵二叉查找树，又是一棵理想平衡二叉树
A．正确
B．错误

【◆参考答案◆】：正确

(6)【◆题库问题◆】：[填空题] 从循环队列中删除一个元素时，其操作是先（），后（）。

【◆参考答案◆】：移动队首指针 取出元素

(7)【◆题库问题◆】：[单选] 在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

(8)【◆题库问题◆】：[问答题] 选取哈希函数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

(9)【◆题库问题◆】：[单选] 设有两个串p和q，求q在p中首次出现的位置的运算称为（）。
A．连接
B．模式匹配
C．求子串
D．求串长

【◆参考答案◆】：B

(10)【◆题库问题◆】：[判断题] 广义表实际上是基本线性表的推广。
A．正确
B．错误

【◆参考答案◆】：正确