数据结构考题研究生.docx

数据结构考题研究生.docx

《数据结构考题研究生.docx》由会员分享，可在线阅读，更多相关《数据结构考题研究生.docx（40页珍藏版）》请在冰点文库上搜索。

数据结构考题研究生

第九章集合

一、选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（）。

【北京航空航天大学2000一、8（2分）】

A．（n-1）/2B.n/2C.（n+1）/2D.n

2.对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）【南京理工大学1998一、7（2分）】

A．（N+1）/2B.N/2C.ND.[（1+N）*N]/2

3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（

（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（

（2））。

在此假定N为线性表中结点数，且每次查找都是成功的。

【长沙铁道学院1997四、3（4分）】

A.N+1B.2log2NC.logND.N/2E.Nlog2NF.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.1B.4C.2.5D.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.nB.n/2C.n*nD.n*n/2E.log2nF.nlog2nG.（n+1）/2H.log2（n+1）

14．在等概率情况下,线性表的顺序查找的平均查找长度ASL为（

（1））,有序表的折半查找的ASL为（

（2））,对静态树表,在最坏情况下,ASL为（（3））,而当它是一棵平衡树时,ASL为（（4））,在平衡树上删除一个结点后可以通过旋转使其平衡,在最坏情况下需（（5））次旋转。

供选择的答案：

【上海海运学院1999二、3（5分）】

（1）

（2）（3）（4）（5）:

A.O

（1）B.O（log2n）C.O（（log2n）2）D.O（nlog2n）E.O（n）

15.对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失败,它们的平均查找长度是（

（1））,对于查找成功,他们的平均查找长度是（

（2））供选择的答案:

【上海海运学院1997二、4（3分）】

A.相同的B.不同的

16．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用（）查找法。

A.分快查找B.顺序查找C.折半查找D.基于属性

【西安电子科技大学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.LLB.LRC.RLD.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.log2nB.1+log2nC.1+log

D.1+log

25.m路B+树是一棵（

（1）），其结点中关键字最多为（

（2））个，最少（（3））个。

【中科院计算机1999一、5】

A.m路平衡查找树B.m路平衡索引树C.m路Ptrie树D.m路键树E.m-1F.mG.m+1

H.

-1I.

J.

+1

26在一棵m阶的B+树中,每个非叶结点的儿子数S应满足（）.【武汉交通科技大学1996一、3（4分）】

A.

≤S≤mB.

≤S≤mC.1≤S≤

D.1≤S≤

27.设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=keyMOD13,散列地址为1的链中有（）个记录。

【南京理工大学1997一、4（2分）】

A．1B.2C.3D.4

28.下面关于哈希（Hash，杂凑）查找的说法正确的是（）【南京理工大学1998一、10（2分）】

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可

29.若采用链地址法构造散列表，散列函数为H（key）=keyMOD17，则需（

（1））个链表。

这些链的链首指针构成一个指针数组，数组的下标范围为（

（2））【南京理工大学1999一、12（13）（4分）】

（1）A．17B.13C.16D.任意

（2）A．0至17B.1至17C.0至16D.1至16

30.关于杂凑查找说法不正确的有几个（）【南京理工大学2000一、16（1.5分）】

（1）采用链地址法解决冲突时，查找一个元素的时间是相同的

（2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

（3）用链地址法解决冲突易引起聚集现象

（4）再哈希法不易产生聚集

A.1B.2C.3D.4

31.设哈希表长为14，哈希函数是H（key）=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是（）【南京理工大学2001一、15（1.5分）】

A．8B．3C．5D．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．kB.k+1C.k（k+1）/2D.1+k（k+1）/2

34.散列函数有一个共同的性质，即函数值应当以（）取其值域的每个值。

A.最大概率B.最小概率C.平均概率D.同等概率

【西安电子科技大学2001应用一、7（2分）】【北京邮电大学1999一、4（2分）】

35.散列表的地址区间为0-17,散列函数为H（K）=Kmod17。

采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。

（1）元素59存放在散列表中的【北方交通大学2001一、（19，20）（4分）】地址是（）。

A．8B.9C.10D.11

（2）存放元素59需要搜索的次数是（）。

A．2B.3C.4D.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.动态查找表和静态查找表的重要区别在于前者包含有__________和___