《第7章参考答案08.doc》由会员分享，可在线阅读，更多相关《第7章参考答案08.doc（9页珍藏版）》请在金锄头文库上搜索。
1、练习及参考答案一 选择题： 12345678910BCCCDBCDDD1112131415CDBDB1静态查找表与动态查找表的根本区别在于（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)
2、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(k
3、ey)=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)
4、。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.根
5、结点中的数据是有序的15. m阶B树是一棵（B）。A. m叉排序树 B. m叉平衡排序树C. m一1叉平衡排序树 D. m1叉平衡排序树二、判断题12345678910111213141516171819201.顺序查找可以在顺序表上进行，不能在单链表上进行。（）2.折半查找只能在有序的顺序表上进行。（）3.对于给定的关键字集合，以不同的次序插人到初始为空的二叉排序树中，得到的二叉排序树是相同的。（）4.若二叉排序树中关键字互不相同；那么，最小值结点必定无左孩子，最大值结点必定无右孩子。（）5.在二叉排序树中，最大值结点和最小值结点一定是叶子结点。（）6.将二叉排序树T的先序遍历序列依次插人初
6、始为空的树中，所得到的二叉排序树T2和T；的形态完全相同。（）7.对二叉排序树进行中序遍历得到的序列是由小到大有序的。（）8.二叉树为二叉排序树的充分必要条件是任一非终端结点的值大于其左孩子的值、小于右孩子的值。（）9.二叉排序树的查找和折半查找的时间复杂度都是0(log2n)，时间性能相同。（）10.采用折半查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。（）11.采用线性探测法处理冲突时，当从散列表中删除一个记录时，不应将这个记录的在位置置为空，因为这将会影响以后的查找。（）12. m阶B树每一个结点的子树个数都小于或等于m。（）13.散列表的查找效率主要取决于构造散列表时选取的
7、散列函数和处理冲突的方法。（）14.散列法存储的基本思想是由关键码的值决定数据的存储地址。（）15.当负载因子小于1时，则向散列表中插人元素时不会引起冲突。（）16.查找表中数据元素的任何数据项都可以作为关键字。（x）17. m阶B树的任何一个结点的所有子树的高度都相等。（）18.在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点相应的指针域置空即可。（x）19.在散列存储方式中，负载因子的值越大，存取元素时发生冲突的可能性就越大。（）20.对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序是一样的（）。三问答题 1.画出长度为18的顺序查存储的有序表进行
8、折半查找的判定树，并指出在等概率时，查找成功的平均查找长度，以及查找失败时所需最多的关键字比较次数。【解答】（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）按表中元素的顺序构造一棵平衡二叉排序树，求其在等概率下
9、查占成功的平均查找成度。这种情况就退化成为顺序查找。【解答】 （1）二叉排序树如图所示。 （2）ASL= (11+22+33+43+52+61) /12=3.5（3）若先排序再构造二叉排序树，则构造是的一棵单枝树；ASL= (11+21+31+41+.+121) /12=6.53.试推导含有12个结点的平衡二叉树的最大深度，并画出一棵这样的树。令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。那么，可知道F1=1，F2=2，FnFn-2Fn-11。含有12个结点的平衡二叉树的最大深度为5，如图7-10所示。4.含有9个叶子结点的3阶B树中至少有多少个非叶子结点？含有10个叶子结点的3阶B
10、树中至少有多少个非叶子结点？【解答】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为关
11、键字中第一个字母在字母表中的序号。【解答】（1)结果如图7-12所示。012345678910111213141516AprAugDecFeb JanMacMayJuneJulySepOctNw图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)构造散列表，并求等概率情况下查找成功时的平均查找长度。01234567891022674130 5
12、346 13 01 ASL=17/88.画出依次插入z,v,o,q,w,y到图7-15所示的5阶B树的过程四算法设计题1.将监视哨设在高下标端，改写书中给出的顺序查找算法，并分别求出在等概率情况下查找成功时和查找失败的平均查找长度。typedef struct datatype *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将折半查找的算法改写为递归算法。【提示】对于每次查找的思想是相同
13、的，只是查找区间发生了变化，因此折折半查找算法改写为递归算法时要将查找区间的上下限作为参数，递归调甩时查找区间的上下限是变化的。int BinSearch(datatype R，int low, int hig, keytype K)int mid; if (low hig) retum(0); else mid =(lowhig)/2； if(K=Rmid.key)return(mid); else if(KRmid.key)return(Bitiseareh(R,mid+1,hig,K)； else return(Binsrch(R,low,mid-1); 3.编写算法，利用折半查找算法在一个有序表中插入一个元素x，并保持表的有序性。【提示】先在有序表R中利用折半查找法查找关键字值小于或等于x的结点，mid指向关键字正好等于x的结点或low指向关键字正好大于x的结点，然后采用移动法插入x结点即可。void Binlnsert(datatype R，KeyType x) int low =1,hign,mi
