练习及参考答案一 选择题：1 2 3 4 5 6 7 8 9 10B C C C D B C D D D11 12 13 14 15C D B D B1静态查找表与动态查找表的根本区别在于（B）A.它们的逻辑结构不一样 B.施加在其上的操作不一样C.所包含的数据元素类型不一样 D.存储实现不一样2 在表长为 n 的顺序表上实施顺序查找，在查找不成功时与关键字比较的次数为（C） 。A. n B. l C. n+1 D. n-13.顺序查找适用于存储结构为（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/127.在有序表1，3，9，12，32，41，62，75，77，82，95，100上进行折半查找关键字为 82 的数据元素需要比较（C）次。A. 1 B. 2 C. 4 D. 58.设散列表长为 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. 199.散列函数有一个共同的性质，即函数值应当以（D ）取其值域的每个值。A.最大概率 B.最小概率 C.平均概率 D.同等概率10.假定有 k 个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列表中，至少要进行多少（D）次探测？ A. k-1 次 B. k 次 C. k1 次 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. 62514.下列关于 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. m1 叉平衡排序树二、判断题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+22+34+48+53) /18=32/92.已知如下所示长度为 12 的关键字有序的表：Jan，Feb，Mar，Apr，May，June ，July ，Aug ，Sep，Oct，Nov，Dec(1)试按表中的顺序依次插入到一棵空的二叉排序树中，画出插入完成后的二叉排序树，并求其在等概率下查占成功的平均查找成度。（2）若对表中元素先进行排序构成有序表，求其在等概率下查找成功的平均查找成度。（3）按表中元素的顺序构造一棵平衡二叉排序树，求其在等概率下查占成功的平均查找成度。这种情况就退化成为顺序查找。【解答】（1）二叉排序树如图所示。（2）ASL= (11+22+33+43+52+6 1) /12=3.5（3）若先排序再构造二叉排序树，则构造是的一棵单枝树；ASL= (11+21+31+41+.+121) /12=6.53.试推导含有 12 个结点的平衡二叉树的最大深度，并画出一棵这样的树。令 Fk 表示含有最少结点的深度为 k 的平衡二叉树的结点数目。那么，可知道 F1=1，F2=2，FnFn-2Fn-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.在地址空间为 016 的散列区中，对以下关键字序列构造两个散列表： 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 16Apr Aug Dec Feb Jan Mac May June July Sep Oct Nw图 7-12平均查找长度为 31/12。（2）结果如图 7-13 所示。平均查找长度为 3/2。7.设散列函数 H(key)=(3key)%11，用开放地址法处理冲突，探测序列为di=i(7key)%10+1),i=1,2,3, 。试在 010 的散列地址空间扎对关键字序列(22,41,53,46,30,13,01,67)构造散列表，并求等概率情况下查找成功时的平均查找长度。0 1 2 3 4 5 6 7 8 9 1022 67 41 30 53 46 13 01ASL=17/88.画出依次插入 z,v,o,q,w,y 到图 7-15 所示的 5 阶 B 树的过程四算法设计题1.将监视哨设在高下标端，改写书中给出的顺序查找算法，并分别求出在等概率情况下查找成功时和查找失败的平均查找长度。typedef structdatatype *data;int length;SSTableint search(SSTable st,keytype kx)int i;st.datast.length+1=kx;i=1;while(kx!=st.datai)i+;return(i);2将折半查找的算法改写为递归算法。【提示】对于每次查找的思想是相同的，只是查找区间发生了变化，因此折折半查找算法改写为递归算法时要将查找区间的上下限作为参数，递归调甩时查找区间的上下限是变化的。int BinSearch(datatype R，int low, int hig, keytype K)int mid;if (low Rmid.key) lowmid+1；else i = mid;find=1；if(find)inspace=mid;else inspacelow;for(i=n;i =inspace；i-)Ri+l=Ri;Rinspac=x;4.假设二叉排序树 T 的各个元素值均不相同，设计一个算法按递减次序打印各元素的值。【提示】调整中序递归遍历算法，先遍历右子树，然后输出根结点的值，再遗历左子树。viod PrintNode(BiSTree T)if(T)PrintNode(T-rchild);printf（T-data ） ；PrintNode(T-lchild);5.已知一棵二叉排序树上所有关键字中的最小值为-max，最大值为 max，又知-maxdata. key) /*当 x 小于根结点时，修改 b,在左子树上继续查找*/*b=T-data. key;fun(T=lchild, x,a,b);else if（xT-data) /*当 x 大于根结点时，修改 a,在右子树上继续查找*/*a=T-data.key;fun(T=rchild, x,a,b);else /*当 x 等于根结点时，a 是其左子树的最右下结点，b 是其右子树的最左下结点*if(T-lchild)p=T-lchild;while(p- rchilt) p = p - rchiid;*a = p - data.key;if(T-rchild）