《集合(散列、搜索树、折半)习题》由会员分享，可在线阅读，更多相关《集合(散列、搜索树、折半)习题（8页珍藏版）》请在金锄头文库上搜索。
1、一、选择题：一、选择题： 1、对、对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找 长度为长度为( A ) 【南京理工大学南京理工大学 1998 一、一、7（2 分）分） 】A （N+1）/2 B. N/2 C. N D. （1+N）*N /22、下面关于二分查找的叙述正确的是下面关于二分查找的叙述正确的是 ( D ) 【南京理工大学南京理工大学 1996 一、一、3 （2 分）分） 】 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而
2、且只能从小到大排列表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储表必须有序，且表只能以顺序方式存储3、适用于折半查找的表的存储方式及元素排列要求为适用于折半查找的表的存储方式及元素排列要求为( D ) 【南京理工大学南京理工大学 1997 一、一、6 （2 分）分） 】 A链接方式存储，元素无序链接方式存储，元素无序 B链接方式存储，元素有序链接方式存储，元素有序 C顺序方式存储，元素无序顺序方式存储，元素无序 D顺序方式存储，元素有序顺序方式存储，元素有序4、当在一个有
3、序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺 序查找，但前者比后者的查找速度序查找，但前者比后者的查找速度( C ) A必定快必定快 B.不一定不一定 C. 在大部分情况下要快在大部分情况下要快 D. 取决于表递增还是递减取决于表递增还是递减 【南京理工大学南京理工大学 1997 一、一、7 （2 分）分） 】5、具有具有 12 个关键字的有序表，折半查找的平均查找长度（个关键字的有序表，折半查找的平均查找长度（A ） 【中山大学中山大学 1998 二、二、10 （2 分）分） 】 A. 3.1 B. 4 C. 2.
4、5 D. 56、折半查找的时间复杂性为、折半查找的时间复杂性为（ D ） 【中山大学中山大学 1999 一、一、15】 A. O（n2） B. O（n） C. O（nlogn） D. O（logn）7、散列函数有一个共同的性质，即函数值应当以散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。取其值域的每个值。 A. 最大概率最大概率 B. 最小概率最小概率 C. 平均概率平均概率 D. 同等概率同等概率8、二叉查找树的查找效率与二叉树的二叉查找树的查找效率与二叉树的( （1）C)有关有关, 在在 (（2）C)时其查找效时其查找效 率最低率最低【武汉交通科技大学武汉交通科技大学
5、 1996 一、一、2(4 分分)】(1): A. 高度高度 B. 结点的多少结点的多少 C. 树型树型 D. 结点的位置结点的位置 (2): A. 结点太多结点太多 B. 完全二叉树完全二叉树 C. 呈单枝树呈单枝树 D. 结点太复杂。结点太复杂。9、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是 ( C ) 【合肥工业大学合肥工业大学 2000 一、一、4（2 分）分） 】A （100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（
6、100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)10、下面关于哈希、下面关于哈希(Hash，杂凑，杂凑)查找的说法正确的是查找的说法正确的是( C ) 【南京理工大学南京理工大学 1998 一、一、10 （2 分）分） 】 A哈希函数构造的越复杂越好，因为这样随机性好，冲突小哈希函数构造的越复杂越好，因为这样随机性好，冲突小 B除留余数法是所有哈希函数中最好的除留余数法是所有哈希函数中最好的 C不存在特别好与坏的哈希函数，要视情况而定不存在特别好与坏的哈希函数，要视情况而定 D若需在哈希表中删去一个元素，不管用何种方法解
7、决冲突都只要简单的将若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将 该元素删去即可该元素删去即可11、设哈希表长为、设哈希表长为 14，哈希函数是，哈希函数是 H(key)=key%11, 表中已有数据的关键字为表中已有数据的关键字为 15，38，61，8 共四个，现要将关键字为共四个，现要将关键字为 49 的结点加到表的结点加到表 中，用中，用二次探测二次探测再散列法解决冲突，则放入再散列法解决冲突，则放入 的位置是的位置是( D ) 【南京理工大学南京理工大学 2001 一、一、 15 （1.5 分）分） 】A8 B3 C5 D9 二次探测：二次探测：h2i-1(x)=(
8、h(x)+i2)%B;h2i+1(x)=(h(x)-i2)%B;12、假定有、假定有 k 个关键字互为同义词，若用线性探测法把这个关键字互为同义词，若用线性探测法把这 k 个关键字存入散列个关键字存入散列 表中，至少要进行多少次探测？表中，至少要进行多少次探测？( D ) Ak-1 次次 B. k 次次 C. k+1 次次 D. k（k+1）/2 次次13、散列表的地址区间为、散列表的地址区间为 0-17,散列函数为散列函数为 H(K)=K mod 17。 采用线性探测法处理冲突，并将关键字序列采用线性探测法处理冲突，并将关键字序列 26，25，72，38，8，18，59 依次存储到散依次存储
9、到散 列表中。列表中。 【北方交通大学北方交通大学 2001 】（1）元素）元素 59 存放在散列表中的地址是（存放在散列表中的地址是（ D ） 。 A 8 B. 9 C. 10 D. 11（2）存放元素）存放元素 59 需要搜索的次数是（需要搜索的次数是（ C ） 。 A 2 B. 3 C. 4 D. 514. 将将 10 个元素散列到个元素散列到 100000 个单元的哈希表中，则（个单元的哈希表中，则（ C ）产生冲突。）产生冲突。 【北京邮电大学北京邮电大学 2001 一、一、4 （2 分）分） 】 A. 一定会一定会 B. 一定不会一定不会 C. 仍可能会仍可能会二、判断题：二、判断
10、题：1在散列检索中，在散列检索中， “比较比较”操作一般也是不可避免的。操作一般也是不可避免的。( )【华南理工大学华南理工大学 2001 一、一、4 （1 分）分） 】2散列函数越复杂越好，因为这样随机性好，冲突概率小散列函数越复杂越好，因为这样随机性好，冲突概率小.( ) 【南京理工大南京理工大 学学 1997 二、二、5 （2 分）分） 】3哈希函数的选取平方取中法最好。哈希函数的选取平方取中法最好。( ) 【青岛大学青岛大学 2000 四、四、7 （1 分）分） 】4Hash 表的平均查找长度与处理冲突的方法无关。表的平均查找长度与处理冲突的方法无关。 （） 【南京航空航天大南京航空航
11、天大 学学 1997 一、一、9 （1 分）分） 】5、顺序查找法适用于存储结构为顺序或链接存储的线性表。、顺序查找法适用于存储结构为顺序或链接存储的线性表。 （） 【山东大学山东大学 2001 一、一、 1 (1 分分)】6. 折半查找法的查找速度一定比顺序查找法快折半查找法的查找速度一定比顺序查找法快 。 （） 【山东大学山东大学 2001 一、一、 8 (1 分分)】7对大小均为对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，的有序表和无序表分别进行顺序查找，在等概率查找的情况下， 对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均对于查找成功，
12、它们的平均查找长度是相同的，而对于查找失败，它们的平均 查找长度是不同的。查找长度是不同的。 （）8、在查找在查找树树（二叉树排序（二叉树排序树树）中插入一个新结点，总是插入到叶结点下面。）中插入一个新结点，总是插入到叶结点下面。 （） 【上海海运学院上海海运学院 1999 一、一、8 （1 分）分） 】9、完全二叉树肯定是平衡二叉树。（完全二叉树肯定是平衡二叉树。（） 【南京航空航天大学南京航空航天大学 1996 六、六、5 （1 分）分） 】10 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 （） 【南京航空航
13、天大学南京航空航天大学 1995 五、五、4 （1 分）分） 】11二叉树中除叶结点外二叉树中除叶结点外, 任一结点任一结点 X，其左子树根结点的值小于该结点（，其左子树根结点的值小于该结点（X） 的值；其右子树根结点的值的值；其右子树根结点的值该结点（该结点（X）的值）的值,则此二叉树一定是二叉排序树。则此二叉树一定是二叉排序树。 （ ） 【北京邮电大学北京邮电大学 1998 一、一、4 （2 分）分） 】12、N 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 （ ） 【上海交通大学上海交通大学 1998 一、一、9
14、】三、填空题三、填空题 1、 顺序查找顺序查找 n 个元素的顺序表，若查找成功，则比较关键字的次数最多为个元素的顺序表，若查找成功，则比较关键字的次数最多为 _n _次；当使用监视哨时，若查找失败，则比较关键字的次数为次；当使用监视哨时，若查找失败，则比较关键字的次数为_n+1 _。 【华中理工大学华中理工大学 2000 一、一、8 （2 分）分） 】2. 在顺序表（在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键）中，用二分（折半）法查找关键 码值码值 20，需做的关键码比较次数为，需做的关键码比较次数为_4_. 【北方交通大学北方交通大学 2001 二、二、2】3在有序表在有序表 A1.12中，采用二分查找算法查等于中，采用二分查找算法查等于 A12的元素，所比较的元的元素，所比较的元 素下标依次为素下标依次为_6，9，11，12_。 【中国人民大学中国人民大学 2001 一、一、2 （2 分）分）】4. 在有序表在有序表 A1.20中，按二分查找方法进行查找，查找长度为中，按二分查找方法进行查找，查找长度为 5 的元素个数的元素个数 是是_5_ 【合肥工业大学合肥工业大学
