数据结构第四教学单元测验练习题(答案)(自动保存的).pdf

第 1 页共 9 页《数据结构》第 4 教学单元测试练习题一、 选择题1. 对 N个元素的表做顺序查找时，若查找每个 元素的概率相同，则平均查找长度为( ) A．（N+1 ） /2 B. N/2 C. N D. [（1+N ） *N ]/2 AB2 ．适用于折半查找的表的存储方式及元素排 列要求为 ( ) A．链接方式存储， 元素无序 B．链接方式存储， 元素有序 C．顺序方式存储， 元素无序 D．顺序方式存储， 元素有序 3．当在一个有序的顺序存储表上查找一个数据 时，即可用折半查找，也可用顺序查找，但前者 比后者的查找速度 ( ) A． 必定快 B.不一定C. 在大部分情况 下要快 D. 取决于表递增还是递减 4. 具有 12 个关键字的有序表， 折半查找的平均 查找长度（）第 2 页共 9 页A. 3.1 B. 4 C. 2.5 D. 5 5. 折半查找的时间复杂性为（）A. O （n2） B. O （n） C. O （nlogn） D. O （logn ）6. 对有 18 个元素的有序表作折半查找，则查找A[3] 的比较序列的下标为 （ ） A.1， 2， 3B.9， 5，2，3 C.9 ，5，3 D.9，4，2，37. 设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，当用二分查找法查找健值为84 的结点时，经 （）次比较后查找成功。

A.2 B. 3 C. 4 D.12 8、用 n 个键值构造一 棵二叉排序树，最低高度为（ ）A.n/2 B.、n C.logn D.logn+1 9．分别以下列序列构造二叉排序树，与用其它 三个序列所构造的结果不同的是( ) A． （100，80， 90 ， 60 ， 120 ，110，130）第 3 页共 9 页B.（100，120，110，130，80， 60 ， 90 ） C.（100，60， 80 ， 90 ， 120 ，110，130） D.(100 ，80， 60 ， 90 ， 120 ，130，110) 10. 设有一组记录的关键字为{19，14，23，1， 68，20，84，27，55，11，10，79}，用链地址 法构造散列表，散列函数为H（key）=key% 13, 散列地址为 1 的链中有（）个记录 A．1 B. 2 C. 3 D. 4 11．已知一采用开放地址法解决Hash表冲突，要从此 Hash表中删除出一个记录，正确的做法是( ）A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素代替C.将与该元素有相同Hash地址的后继元素顺次前移一个位置。

D.用与该元素有相同Hash地址的最后插入表中的元素替代11. 假定有 k 个关键字互为同义词， 若用线性探 测法把这 k 个关键字存入散列表中， 至少要进行第 4 页共 9 页多少次探测？ ( ) A．k-1 次 B. k次 C. k+1 次 D. k （k+1）/2 次 12. 散列表的地址区间为0-17, 散列函数为 H(K)=K mod 17采用线性探测法处理冲突，并 将关键字序列 26，25，72，38，8，18，59 依次 存储到散列表中 （1） 元素 59 存放在散列表中的地址是 （） A． 8 B. 9 C. 10 D. 11 （2）存放元素 59 需要搜索的次数是（） A． 2 B. 3 C. 4 D. 5 13. 将 10个元素散列到 100000个单元的哈希表 中，则（）产生冲突 A. 一定会 B. 一定不会 C. 仍可能会 二、 判断题 1．查找相同结点的效率折半查找总比顺序查找 高 × 2．对无序表用二分法查找比顺序查找快× 3．对大小均为 n 的有序表和无序表分别进行顺 序查找，在等概率查找的情况下， 对于查找成功， 它们的平均查找长度是相同的， 而对于查找失败， 它们的平均查找长度是不同的。

√第 5 页共 9 页4．在查找树（二叉树排序树）中插入一个新结 点，总是插入到叶结点下面× 5．对一棵二叉排序树按前序方法遍历得出的结 点序列是从小到大的序列× 6．二叉树中除叶结点外, 任一结点X，其左子 树根结点的值小于该结点（X）的值；其右子树 根结点的值≥该结点 （X）的值, 则此二叉树一定 是二叉排序树 × 7. 在任意一棵非空二叉排序树中，删除某结点 后又将其插入，则所得二排序叉树与原二排序叉 树相同 × 8．采用线性探测法处 理散列时的冲突，当从哈 希表删除一个记录时， 不应将这个记录的所在位 置置空，因为这会影响以后的查找√ 9．在散列检索中，“比较”操作一般也是不可避免 √ 10．散列函数越复杂越好，因为这样随机性好， 冲突概率小 . × 11．Hash 表的平均查找长度与处理冲突的方法 无关 × 12．负载因子 ( 装填因子 ) 是散列表的一个重要 参数，它反映散列表的装满程度√第 6 页共 9 页13. 若散列表的负载因子 α<1， 则可避免碰撞的 产生 × 三、填空题 1. 顺序查找 n 个元素的顺序表， 若查找成功， 则 比较关键字的次数最多为__（1）n__次。

2. 在有序表A[1..20]中，按二分查找方法进行 查找，查找长度为 5 的元素个数是 __ （2） 5 __ 3. 在有序表A[1,20] 中，按二分查找方法进行 查找，查找长度为 4 的元素的下标从小到大依次 是____（3）1,3,6,8,11,13,16,19__ 4. 有序表 (12,18,24,35,47,50,62,83,90,115， 134)使用二分法查找90 时，需 ___（4）2_次 查找成功，查 100 时，需___（5）4_次才能确 定不成功 5. 在 n 个记录的有序顺序表中进行折半查找，最 大 比较次数是 ___（6）log2n+1__ （取下界） 6. 平衡因子的定义是 ___ （7）结点的左子树的高 度减去结点的右子树的高度___ 7. 高度为 8 的平衡二叉树的结点数至少有___ （8） 54__个 （参照教材P238：N0=0,N1=1,N2=2,公 式 Nh=Nh-1+Nh-2+1）第 7 页共 9 页8. 动态查找表和静态查找表的重要区别在于前 者包含有 ___（9）插入 _和__（10）_删除__运 算，而后者不包含这两种运算 四、应用题 1.假定对有序表： (3,4,5,7,24,30,42,54,63,72,87,95)进 行 折 半查找，试回答下列问题： (1). 画出描述折半查找过程的判定树； (2). 若查找元素54，需依次与那些元素比 较? (3). 若查找元素90，需依次与那些元素比 较? (4). 假定每个元素的查找概率相等，求查 找成功时的平均查找长度。

2. 一棵二叉排序树结构如下, 各结点的值从小到 大依次为 1-9，请标出各结点的值第 8 页共 9 页3.依次输入表 (30,15,28,20,24,10,12,68,35,50,46,5 5)中的元素，生成一棵二叉排序树 【华中 理工大学 2000 五 （10 分） 】 (1) 试画出生成之后的二叉排序树; (2) 对该二叉排序树作中序遍历，试写出遍历序列; (3) 假定每个元素的查找概率相等， 试计算 该二叉排序树的平均查找长 度第 9 页共 9 页4. 设哈希函数 H（k）=3 K mod 11，散列地址空 间为0～10，对关键字序列 （32,13,49,24,38,21,4,12） 按下述两种解决冲 突的方法构造哈希表（1）线性探测再散列（ 2） 链地址法，并分别求出等概率下查找成功时的平 均查找长度；。