练习及参考答案 一 选择题： 1 2 3 4 5 6 7 8 9 10 B C C C D B C D D D 11 12 13 14 15 C D B D B 1．静态查找表与动态查找表的根本区别在于（B） A.它们的逻辑结构不一样 B.施加在其上的操作不一样 C.所包含的数据元素类型不一样 D.存储实现不一样
2在表长为n的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（C）。 A. n B. l C. n+1 D. n-1 3.顺序查找适用于存储结构为（C）的线性表。 A.散列存储 B.压缩存储 C.顺序存储或链式存储 D.索引存储
4.用顺序查找法对具有n个结点的线性表查找一个结点的时间复杂度为（C)。 A. O(log2n2） B. O(nlog2n) C. O(n) D. O( log2n） 5.适用于折半查找的表的存储方式及元素排列要求为（D）。
A.链接方式存储，元素无序 B.链接方式存储，元素有序 C.顺序方式存储，元素无序 D.顺序方式存储，元素有序
6.有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。
A. 35/12 B. 37/12 C. 39/12 D. 43/12
7.在有序表｛1，3，9，12，32，41，62，75，77，82，95，100｝上进行折半查找关键字为82的数据元素需要比较（C）次。
A. 1 B. 2 C. 4 D. 5 8.设散列表长为14，散列函数为H(key)=key% 11。当前表中已有4个结点：addr(15 )=4，addr(38) = 5，addr(61)=6，addr(84)=7。如用二次探测再散列处理冲突，则关键字为49的结点的地址是（D）。
A. 8 B. 3 C. 5 D. 19
9.散列函数有一个共同的性质，即函数值应当以（D）取其值域的每个值。 A.最大概率 B.最小概率 C.平均概率 D.同等概率
10.假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少（D）次探测？
A. k-1次 B. k次 C. k＋1次 D. k（k+l）/2次 11. 取在散列函数H(k)＝k% m中，一般来讲，m应取（C)。 A.奇数 B.偶数 C.素数 D.充分大的数
12.在采用线性探测法处理冲突所构成的散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测到的这些位置上的键值（D) A.一定是同义词 B.一定不是同义词 C.都相同 D.不一定都是同义词
13.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块应分（B）个结点最佳。 A. 10 B. 25 C. 6 D. 625
14.下列关于m阶B树的说法错误的是（D）。
A.根结点至多有m棵子树 B.所有叶子都在同一层次上
C.非叶结点至少有m/2 ( m为偶数）或功i/2 +1 (m为奇数）棵子树 D.根结点中的数据是有序的 15. m阶B树是一棵（B）。
A. m叉排序树 B. m叉平衡排序树 C. m一1叉平衡排序树 D. m＋1叉平衡排序树
二、判断题 1 2 3 4 5 6 7 8 9 10 × √ × √ × √ √ × × × 11 12 13 14 15 16 17 18 19 20 √ √ √ √ × × √ × √ √ 1.顺序查找可以在顺序表上进行，不能在单链表上进行。（×） 2.折半查找只能在有序的顺序表上进行。（√）
3.对于给定的关键字集合，以不同的次序插人到初始为空的二叉排序树中，得到的二叉排序树是相同的。（×）
4.若二叉排序树中关键字互不相同；那么，最小值结点必定无左孩子，最大值结点必定无右孩子。（√）‘
5.在二叉排序树中，最大值结点和最小值结点一定是叶子结点。（×） 6.将二叉排序树T的先序遍历序列依次插人初始为空的树中，所得到的二叉排序树T2和T；的形态完全相同。（√）
7.对二叉排序树进行中序遍历得到的序列是由小到大有序的。（√）
8.二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（×）
9.二叉排序树的查找和折半查找的时间复杂度都是0(log2n)，时间性能相同。（×） 10.采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（×）
11.采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的在位置置为空，因为这将会影响以后的查找。（√）
12. m阶B树每一个结点的子树个数都小于或等于m。（√）
13.散列表的查找效率主要取决于构造散列表时选取的散列函数和处理冲突的方法。（√） 14.散列法存储的基本思想是由关键码的值决定数据的存储地址。（√） 15.当负载因子α小于1时，则向散列表中插人元素时不会引起冲突。（×） 16.查找表中数据元素的任何数据项都可以作为关键字。（x） 17. m阶B树的任何一个结点的所有子树的高度都相等。（√）
18.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（x）
19.在散列存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。（√） 20.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的（√）。 三．问答题
1.画出长度为18的顺序查存储的有序表进行折半查找的判定树，并指出在等概率时，查找成功的平均查找长度，以及查找失败时所需最多的关键字比较次数。 【解答】（1）判定树如下图所示
（2）平均查找长度：
(1+2×2+3×4+4×8+5×3) /18=32/9
2.已知如下所示长度为12的关键字有序的表：
{Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec} (1)试按表中的顺序依次插入到一棵空的二叉排序树中，画出插入完成后的二叉排序树，并求其在等概率下查占成功的平均查找成度。
（2）若对表中元素先进行排序构成有序表，求其在等概率下查找成功的平均查找成度。
（3）按表中元素的顺序构造一棵平衡二叉排序树，求其在等概率下查占成功的平均查找成度。
这种情况就退化成为顺序查找。 【解答】
（1）二叉排序树如图所示。
（2）ASL= (1×1+2×2+3×3+4×3+5×2+6×1) /12=3.5
（3）若先排序再构造二叉排序树，则构造是的一棵单枝树； ASL= (1×1+2×1+3×1+4×1+…..+12×1) /12=6.5
3.试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。
令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。那么，可知道F1=1，
F2=2，…，Fn＝Fn-2＋Fn-1＋1。
含有12个结点的平衡二叉树的最大深度为5，如图7-10所示。
4.含有9个叶子结点的3阶B树中至少有多少个非叶子结点？含有10个叶子结点的3阶B树中至少有多少个非叶子结点？
【解答】4个，7个。
5.试从空树开始，画出按以下次序向3阶B树中插人关键码的建树过程：20,30,50,52,60,68,70。如果此后删除50和68，画出每一步执行、：2后3阶B树的状态。
图7-11
【解答］建树过程如图7-11所示。
6.在地址空间为0～16的散列区中，对以下关键字序列构造两个散列表： { Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec} （l)用线性探测开放定址法处理冲突； （2）用链地址法处理冲突。
并分别求这两个散列表在等概率情况下查找成功和不成功的平均查找长度。设散列函数为H(key)=i/2，其中i为关键字中第一个字母在字母表中的序号。
【解答】·
（1)结果如图7-12所示。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Apr Aug Dec Feb Jan Mac May June July Sep Oct Nw 图7-12 平均查找长度为31/12。 （2）结果如图7-13所示。 平均查找长度为3/2。
7.设散列函数H(key)=(3×key)，用开放地址法处理冲突，探测序列为di=i×((7×key)+1),i=1,2,3,… 。试在0～10的散列地址空间扎对关键字序列(22,41,53,46,30,13,01,67)构造散列表，并求等概率情况下查找成功时的平均查找长度。
0 1 2 3 4 5 6 7 8 9 10 22 67 41 30 53 46 13 01 ASL=17/8 8.画出依次插入z,v,o,q,w,y到图7-15所示的5阶B树的过程
四．算法设计题
1.将监视哨设在高下标端，改写书中给出的顺序查找算法，并分别求出在等概率情况下查找成功时和查找失败的平均查找长度。
typedef struct
{datatype *data; int length; }SSTable
int search(SSTable st,keytype kx) {int i;
st.data[st.length+1]=kx; i=1;
while(kx!=st.data[i])i++; return(i);