数据结构第9章例题与答案
一、 选择题
1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度asl为( )。【北京航空航天大学 2000 一、8 （2分）】
a． (n-1)/2 b. n/2 c. (n+1)/2 d. n
2. 对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】
a．（n+1）/2 b. n/2 c. n d. [（1+n）*n ]/2
3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定n为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】
a.n+1 b.2log2n c.logn d.n/2 e.nlog2n f.n2
4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】
a. 表必须有序，表可以顺序方式存储，也可以链表方式存储 c. 表必须有序，而且只能从小到大排列
b. 表必须有序且表中数据必须是整型，实型或字符型 d. 表必须有序，且表只能以顺序方式存储
5. 对线性表进行二分查找时，要求线性表必须（ ）【燕山大学 2001 一、5 （2分）】
a.以顺序方式存储 b.以顺序方式存储,且数据元素有序 c.以链接方式存储 d.以链接方式存储,且数据元素有序
6．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】
a．链接方式存储，元素无序 b．链接方式存储，元素有序
c．顺序方式存储，元素无序 d．顺序方式存储，元素有序
7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】
a． 必然快 b. 必然慢 c. 相等 d. 不能确定
8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )
a．必定快 b.不一定 c. 在大部分情况下要快 d. 取决于表递增还是递减
【南京理工大学 1997 一、7 （2分）】
9. 具有12个关键字的有序表，折半查找的平均查找长度（ ）【中山大学 1998 二、10 （2分）】
a. 3.1 b. 4 c. 2.5 d. 5
10. 折半查找的时间复杂性为（ ）【中山大学 1999 一、15】
a. o（n2） b. o（n） c. o（nlogn） d. o（logn）
11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】
a．数据分成若干块，每块内数据有序
b．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
c. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
d. 数据分成若干块，每块（除最后一块外）中数据个数需相同
12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】
(1): a. 高度 b. 结点的多少 c. 树型 d. 结点的位置
(2): a. 结点太多 b. 完全二叉树 c. 呈单枝树 d. 结点太复杂。
13. 要进行顺序查找，则线性表（1）；要进行折半查询，则线性表（2）；若表中元素个数为n,则顺序查找的平均比较次数为（3）；折半查找的平均比较次数为（4）。【北方交通大学 1999 一、2 （4分）】
（1）（2）：a. 必须以顺序方式存储； b. 必须以链式方式存储；c. 既可以以顺序方式存储，也可以链式方式存储；
d. 必须以顺序方式存储，且数据已按递增或递减顺序排好；
e. 必须以链式方式存储，且数据已按递增或递减的次序排好。
（3）（4）：a.n b.n/2 c.n*n d.n*n/2 e.log2n f.nlog2n g.(n+1)/2 h.log2(n+1)
【西安电子科技大学 2001应用一、8 （2分）】
17. 既希望较快的查找又便于线性表动态变化的查找方法是 ( ) 【北方交通大学 2000 二、4 （2分）】
a．顺序查找 b. 折半查找 c. 索引顺序查找 d. 哈希法查找
18．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) 【合肥工业大学2000一、4（2分）】
a．（100，80， 90， 60， 120，110，130） b.（100，120，110，130，80， 60， 90）
c.（100，60， 80， 90， 120，110，130） d. (100，80， 60， 90， 120，130，110)
19. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为a,并已知a的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。【合肥工业大学 2001 一、4 （2分）】
a. ll b. lr c. rl d. rr
20．下列关于m阶b-树的说法错误的是( ) 【南京理工大学 1997 一、9 （2分）】
a．根结点至多有m棵子树 b．所有叶子都在同一层次上
c. 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 d. 根结点中的数据是有序的
21. 下面关于m阶b树说法正确的是( ) 【南京理工大学 1999 一、5 （2分）】
①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字;
③所有叶子在同一层上; ④当插入一个数据项引起b树结点分裂后，树长高一层。
a． ①②③ b. ②③ c. ②③④ d. ③
22. 下面关于b和b+树的叙述中，不正确的是( ) 【北方交通大学 2001 一、17 （2分）】
a. b树和b+树都是平衡的多叉树。 b. b树和b+树都可用于文件的索引结构。
c. b树和b+树都能有效地支持顺序检索。 d. b树和b+树都能有效地支持随机检索。
23. m阶b-树是一棵( ) 【北京邮电大学 2000 二、2 （20/8分）】
a. m叉排序树 b. m叉平衡排序树 c. m-1叉平衡排序树 d. m+1叉平衡排序树
24. 在一棵含有n个关键字的m阶b-树中进行查找，至多读盘( )次。【中科院计算所 2000 一、6 （2分）】
a. log2n b. 1+log2n c. 1+log d. 1+log 25. m路b+树是一棵(（1）) ，其结点中关键字最多为(（2）)个，最少(（3）)个。【中科院计算机 1999 一、5】
a. m路平衡查找树 b. m路平衡索引树 c. m路ptrie树 d. m路键树 e. m-1 f. m g. m+1
h. -1 i. j. +1
26在一棵m阶的b+树中, 每个非叶结点的儿子数s 应满足 ( ). 【武汉交通科技大学 1996 一、3 (4分) 】
a. ≤s≤m b. ≤s≤m c. 1≤s≤ d. 1≤s≤ 27. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为h（key）=key mod 13,散列地址为1的链中有（ ）个记录。【南京理工大学 1997 一、4 （2分）】
a．1 b. 2 c. 3 d. 4
28. 下面关于哈希(hash，杂凑)查找的说法正确的是( ) 【南京理工大学 1998 一、10 （2分）】
a．哈希函数构造的越复杂越好，因为这样随机性好，冲突小
b．除留余数法是所有哈希函数中最好的
c．不存在特别好与坏的哈希函数，要视情况而定
d．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
29. 若采用链地址法构造散列表，散列函数为h（key）=key mod 17，则需 (（1）) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）) 【南京理工大学 1999 一、12(13) （4分）】
（1） a．17 b. 13 c. 16 d. 任意
（2） a．0至17 b. 1至17 c. 0至16 d. 1至16
30. 关于杂凑查找说法不正确的有几个( ) 【南京理工大学 2000 一、16 （1.5分）】
（1）采用链地址法解决冲突时，查找一个元素的时间是相同的
（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的
（3）用链地址法解决冲突易引起聚集现象
（4）再哈希法不易产生聚集
a. 1 b. 2 c. 3 d. 4
31. 设哈希表长为14，哈希函数是h(key)=key,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( ) 【南京理工大学 2001 一、15 （1.5分）】
a．8 b．3 c．5 d．9
32. 假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( )
a．k-1次 b. k次 c. k+1次 d. k（k+1）/2次
【中国科技大学 1998 二、3 （2分）】【中科院计算所1998 二、3 （2分）】
33. 哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。【西安电子科技大学 1998 一、8 （2分）】
a． k b. k+1 c. k(k+1)/2 d.1+k(k+1)/2
34. 散列函数有一个共同的性质，即函数值应当以( )取其值域的每个值。
a. 最大概率 b. 最小概率 c. 平均概率 d. 同等概率
【西安电子科技大学2001应用一、7 （2分）】 【北京邮电大学 1999 一、4 （2分）】
35. 散列表的地址区间为0-17,散列函数为h(k)=k mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。
（1）元素59存放在散列表中的【北方交通大学 2001 一、（19，20）（4分）】地址是（ ）。
a． 8 b. 9 c. 10 d. 11
（2）存放元素59需要搜索的次数是（ ）。
a． 2 b. 3 c. 4 d. 5
36. 将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。【北京邮电大学 2001 一、4 （2分）】
a. 一定会 b. 一定不会 c. 仍可能会
二、 判断题
1．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。【长沙铁道学院 1998 一、3 (1分)】
2．在散列检索中，“比较”操作一般也是不可避免的。【华南理工大学 2001 一、4 （1分）】
3．散列函数越复杂越好，因为这样随机性好，冲突概率小. 【南京理工大学 1997 二、5 （2分）】
4．哈希函数的选取平方取中法最好。 【青岛大学 2000 四、7 （1分）】
5．hash表的平均查找长度与处理冲突的方法无关。 【南京航空航天大学 1997 一、9 （1分）】
6．负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。【中科院软件所1999 六（1-3）（2分）】
7. 散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。【中山大学 1994 一、8 (2分)】
8. 哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 【山东大学 2001 一 、6 (1分)】
9. 若散列表的负载因子α<1，则可避免碰撞的产生。 【北京大学 1994 】
10．查找相同结点的效率折半查找总比顺序查找高。 【北京邮电大学 2002 一、8 （1分）】
11．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 【中科院软件所 1997 一、6 （1分）】
12. 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。【上海交通大学 1998 一、17】
13. 顺序查找法适用于存储结构为顺序或链接存储的线性表。 【山东大学 2001 一、 1 (1分)】
14. 折半查找法的查找速度一定比顺序查找法快 。【山东大学 2001 一、 8 (1分)】
15. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。【西安交通大学 1996 二、 3 (3分)】
16．对无序表用二分法查找比顺序查找快。【青岛大学 2002 一、8 （1分）】
17．对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。【上海海运学院 1995 一、11 （1分） 1998 一、12 （1分）】
18．任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间.
【上海海运学院 1997 一、10 （1分）】
19． 最佳二叉树是avl树（平衡二叉树）。【北京大学 1994 】
20．在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 【上海海运学院 1999 一、8 （1分）】
21．完全二叉树肯定是平衡二叉树。 【南京航空航天大学 1996 六、5 （1分）】
22．对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 【南京航空航天大学 1995 五、4 （1分）】
23．二叉树中除叶结点外, 任一结点x，其左子树根结点的值小于该结点（x）的值；其右子树根结点的值≥该结点（x）的值,则此二叉树一定是二叉排序树。【北京邮电大学 1998 一、4 （2分）】
24．有n个数存放在一维数组a[1..n]中，在进行顺序查找时，这n个数的排列有序或无序其平均查找长度不同。
【北京邮电大学 1998 一、6 （2分）】
25. n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 【上海交通大学 1998 一、9】
26. 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。
【中科院软件所 1997 】
27. 设t为一棵平衡树，在其中插入一个结点n，然后立即删除该结点后得到t1，则t与t1必定相同。
【上海交通大学 1998 一、11】
28. 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级（n为线形表中的结点数目）。 【中山大学 1994 一、9 (2分)】
29. b-树中所有结点的平衡因子都为零。 【大连海事大学2001 一、（1，17） (1分)】
30. 在m阶b-树中每个结点上至少有 个关键字，最多有m个关键字。 【东北大学 1997 二、 4 (2分)】
31. 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。【长沙铁道学院 1998 一、9 (1分)】
32. 在9阶b-树中，除叶子以外的任意结点的分支数介于5和9之间。【合肥工业大学 2001 二、9 （1分）】
33. b-树的插入算法中，通过结点的向上“分裂”，代替了专门的平衡调整。【华南理工大学 2001 一、3 （1分）】
34. 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。
【南京理工大学 1997 二、3 （2分）】
35. 二叉排序树删除一个结点后，仍是二叉排序树。【青岛大学 2000 四、4 （1分）】
36. b+树既能索引查找也能顺序查找。【青岛大学 2002 一、10 （1分）】
三、填空题
1. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为__ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ __。【华中理工大学 2000 一、8 （2分）】
2. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____.
【北方交通大学 2001 二、2】
3．在有序表a[1..12]中，采用二分查找算法查等于a[12]的元素，所比较的元素下标依次为__________。
【中国人民大学 2001 一、2 （2分）】
4. 在有序表a[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__________
【合肥工业大学 1999 三、9 （2分）】
5. 高度为4的3阶b-树中，最多有__________个关键字。【合肥工业大学 2000 三、9 （2分）】
6. 在有序表a[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依次是__________
【合肥工业大学 2000 三、10 （2分）】
7. 给定一组数据{6，2，7，10，3，12}以它构造一棵哈夫曼树，则树高为__________，带权路径长度wpl的值为__________。
【南京理工大学 1997 三、4 （2分）】
8. 在一棵m阶b-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是__________;若在某结点中删除一个关键字而导致结点合并,则该结点中原有的关键字的个数是__________。
【中国科技大学 1998 一、5 （3分）】【南京理工大学 2001 二、4 （3分）】
9. 己知有序表为(12,18,24,35,47,50,62,83,90,115，134)当用二分法查找90时，需__________次查找成功，47时__________成功，查100时，需__________次才能确定不成功。【南京理工大学 2000 二、7 （4.5分）】
10. 哈希表是通过将查找码按选定的__(1)__和 __(2)__，把结点按查找码转换为地址进行存储的线性表。哈希方法的关键是_(3)__和 __(4)__。一个好的哈希函数其转换地址应尽可能__(5)__，而且函数运算应尽可能__(6)__。
【青岛大学 2000 六、2 （2分）】
11. 平衡二叉树又称__________，其定义是__________。【青岛大学 2001 六、3 （3分）】
12. 在哈希函数h（key）=key%p中，p值最好取__________。【青岛大学 2002 三、9 （2分）】
13. 对于长度为255的表，采用分块查找，每块的最佳长度为__________。【青岛大学 2002 三、10 （2分）】
14. 在n个记录的有序顺序表中进行折半查找，最大比较次数是__________。【中国科技大学 1998 一、4 （3分）】
15．有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则每块的理想长度是__(1)___，分成__(2)___块最为理想，平均查找长度是__(3)___。【中国矿业大学 2000 一、6 （3分）】
16．假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行__________次探测。
【西安电子科技大学2001软件一、7 （2分）】
17. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成__________块最好：若分成25块，其平均查找长度为__________。【北京工业大学 1999 一、 5 ( 2分)】
18. 执行顺序查找时，储存方式可以是__(1)__，二分法查找时，要求线性表__(2)__，分块查找时要求线性表 __(3)__，而散列表的查找，要求线性表的存储方式是 __(4)__。【山东大学 1998 一 、1 (3分)】
19. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。 【山东大学 1999 二、1 (４分)】
20. 如果关键码按值排序，而后用二分法依次检索这些关键码，并把检索中遇到的在二叉树中没有出现的关键码依次插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为__________。【山东大学 1999 二、２ (４分)】
21. 平衡因子的定义是__________【北京轻工业学院 2000 一、2 （2分）】
22. 查找是非数值程序设计的一个重要技术问题，基本上分成__(1)__查找，__(2)__查找和__(3)__查找。处理哈希冲突的方法有__(4)__、__(5)__、__(6)__和__(7)__。【华北计算机系统工程研究所 1999 一 （5分）】
23. __________法构造的哈希函数肯定不会发生冲突。【重庆大学 2000 一、3】
24. 具有n个关键字的b树的查找路径长度不会大于__________。【中科院计算机 1999 二、2】
25. 在一棵有n 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为________ 。
【西南交通大学 2000 一、8】
26. 假设有n个关键字，它们具有相同的hash函数值，用线性探测方法解决冲突，把这n个关键字散列到大小为n的地址空间中，共计需要做__________次插入和探测操作。【武汉大学 2000 一、8】
27. 高度为8的平衡二叉树的结点数至少有__________个。【武汉大学 2000 一、6】
28. 高度为5（除叶子层之外）的三阶b-树至少有__________个结点。【武汉大学 2000 一、4】
29. 假定查找有序表a[1..12]中每个元素的概率相等，则进行二分查找时的平均查找长度为__________
【燕山大学 2001 二、4 （3分）】
30. 可以唯一的标识一个记录的关键字称为__________。【燕山大学 1998 一、7 （1分）】
31. 已知二叉排序树的左右子树均不为空，则__________上所有结点的值均小于它的根结点值，__________上所有结点的值均大于它的根结点的值。【燕山大学 1998 一、8 （2分）】
32. 动态查找表和静态查找表的重要区别在于前者包含有__________和__________运算，而后者不包含这两种运算。
【厦门大学 2001 一、3 （14%/5分）】
33. 对于具有144 个记录的文件，若采用分块查找法，且每块长度为8，则平均查找长度为__________.
【北方交通大学 2001 二、8】
34. 127阶b-树中每个结点最多有__(1)__个关键字；除根结点外所有非终端结点至少有__(2)__棵子树；65阶b+树中除根结点外所有结点至少有__(3)__个关键字；最多有__(4)__棵子树；【北方交通大学 1999 二、5 （4分）】
35. 若静态查找表的类型定义如下：
type rectype=record key：keytype； ……； end；
ordlisttp=array[1..n] of rectype；
请完成以下二分查找的算法：
func binsrch（r：ordlisttp；k：keytype）：integer；
begin low:=1；hig:=n；suc:=false；
while ___(1)___ and not（suc）do
[ mid：=__(2)____；
case
k>r[mid].key：low:=mid+1；
k=r[mid].key：suc:=true；
k
if suc then __(3)__ else __(4)__
end； 【福州大学 1998 二、8 (2分)】
25． 已知某哈希表ht的装填因子小于1，哈希函数h(key)为关键字的第一个字母在字母表中的序号。
（1） 处理冲突的方法为线性探测开放地址法。编写一个按第一个字母的顺序输出哈希表中所有关键字的程序。
（2） 处理冲突的方法为链地址法。编写一个计算在等概率情况下查找不成功的平均查找长度的算法。注意，此算法中规定不能用公式直接求解计算。【西北大学 2001】
26． 有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求用哈希表作存储结构。
（1）请你设计一个哈希表
（2）请写一个对你所设计的哈希表中给定行值和列值存取矩阵元素的算法；并对你的算法所需时间和用一维数组（每个分量存放一个非零元素的行值，列值，和元素值）作存储结构时存取元素的算法（注：此算法不需要写出，仅需说明存取的方法和所用时间）进行比较。【北方交通大学 1994 六 （16分）】
27．将一组数据元素按哈希函数h（key）散列到哈希表ht（0:m）中，用线性探测法处理冲突（h（key）+1、h（key）+2、…、h（key）-1），假设空单元用empty表示，删除操作是将哈希表中结点标志位从inuse标记为deleted，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学 2001 五、2 （10分）】
28. 设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列0-10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少？
【东北大学 1996 四 (12分)】
类似本题的另外叙述有：
(1) 已知输入关键字序列为（100,90,120,60,78,35,42,31,15）地址区间为０～１１。设计一个哈希表函数把上述关键字散到０～１１中，画出散列表（冲突用线性探测法）；写出查找算法，计算在等概率情况下查找成功的平均查找长度。
【东北大学 1997 五 (15分)】
29. 已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到o(m).
【清华大学 1994 八 （15分）】