第7章参考案08.doc

练习及参考答案 一 选择题： 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 7.在有序表｛1，3，9，12，32，41，62，75，77，82，95，100｝上进行折半查找关键字为82的数据元素需要比较（C）次。 A. 1 B. 2 C. 4 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 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)，时间性能相同。（×） 1