12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表

13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( ) A.线性探测法 B.除留余数法 C.平方取中法 D.折叠法 24.设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为__________。

25.在索引顺序表上的查找分两个阶段：一是查找__________，二是查找块。

33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。

14．设一组记录的关键字key值为{62，50，14，28，19，35，47，56，83}，散列函数为H(key)=key mod 13，则它的开散列表中散列地址为1的链中的结点个数是（ ）A．1 B.2 Ｃ．3 D.4 25．一棵平衡二叉树中任一结点的平衡因子只可能是_______。 26．二分查找的时间复杂度为_______。

32．题32图所示二叉树是否为平衡二叉树？若是，说明理由；若不是，将其转换为平衡二叉树。

13.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90的元素时，检索成功需比较的次数是（ ） A.1 B.2 C.3 D.4

24.对二叉排序树进行________遍历，可得到排好序的递增结点序列。 25.采用折半查找方法进行查找的数据序列应为________且________。

31.设散列函数H（key）=key mod 11，给定键值序列为13、41、15、44、6、68、17、26、39、46，试画出相应的开散列表，并计算在等概率情况下查找成功时的平均查找长度。

32.从一个空的二叉排序树开始，依次插入关键字25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。

12.闭散列表中由于散列到同一个地址而引起的―堆积‖现象，是由（ ） A.同义词之间发生冲突引起的 B.非同义词之间发生冲突引起的 C.同义词与非同义词之间发生冲突引起的 D.散列地址―溢出‖引起的 25.查找表的逻辑组织结构实际上是________________结构。

26.对于具有n个元素的数据序列，采用顺序查找法，其平均查找长度为________________。 31.请按照数列{28，45，33，12，37，20，18，55}的先后插入次序，生成一棵二叉排序树。 11.适用于静态的查找方法为( )

A.二分查找、二叉排序树查找 B.二分查找、索引顺序表查找 C.二叉排序树查找、索引顺序表查找 D.二叉排序树查找、散列法查找

25

12.采用二分查找法，若当前取得的中间位置MID的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应( )

A.从MID/2位置开始 B.从MID位置开始 C.从MID-1位置开始 D.从MID+1位置开始 25.对于具有n个元素的数据序列，若采用二分查找法，当n的值较大时其平均查找长度为__________。 26.解决散列所引起冲突的方案中，__________法是介于开散列表与闭散列表之间的一种方法。 30．设散列函数H(key)=key，散列表长度为11（散列地址空间为0…10），在给定表（SUN， MON，TUE，WED，THU，FRI，SAT）中，取单词的第一个字母在英语字母表中的序号为键值K，构造一散列表，并利用线性探测法解决有关的地址冲突。 11.下列查找方法中，不属于动态的查找方法是( )

A.二叉排序树法 B.平衡树法 C.散列法 D.斐波那契查找法 12.要解决散列引起的冲突问题，常采用的方法有( ) A.数字分析法、平方取中法 B.数字分析法、线性探测法 C.二次探测法、平方取中法 D.二次探测法、链地址法

25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用______法在块中找到具体的元素值。

26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用______法遍历。

31.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：

(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突； (2)若要用该散列表查找元素68，给出所需的比较次数。

11.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为（ ） A.从第0个元素开始往后查找该数据元素 B.从第1个元素开始往后查找该数据元素 C.从第n个元素开始往前查找该数据元素 D.从第n+1个元素开始往前查找该数据元素 12.下列查找中，效率最高的查找方法是（ ）

A.顺序查找 B.折半查找 C.索引顺序查找 D.分块查找

25.对于具有n个元素的数据序列，采用二叉排序树查找，其平均查找长度为___________。 26.要完全避免散列所产生的―堆积‖现象，通常采用___________法。

31．已知某二叉排序树10个结点值依次为1~10，其结构如图所示，试标出该二叉树各结点所对应得具体值。

10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A．n/2 B．n C．(n+1)/2 D．n+1

11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次

26

的查找区间为从原开始位置至（ ）

A．该中间位置 B．该中间位置－1 C．该中间位置＋1 D．该中间位置／2 12．散列文件不能（ ）

A．随机存取 B．索引存取 C．按关键字存取 D．直接存取

24．对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有序表中的位置可能是______________。

25．查找表的逻辑结构与线性结构、树型结构等相比，根本区别在于______________。

32．设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34），散列函数H（k）=k mod 6，采用线性探测法解决冲突，要求：（7分） （1）构造散列表； （2）求查找数34需要的比较次数。

27

第七章 文件 真题

1.下述文件中适合于磁带存储的是（ ）

A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件

26.文件在外存储器上的组织结构主要有三种：顺序文件、散列文件和索引文件，其中_________特别适应磁带存储器，也适应磁盘存储器。

15.关于VSAM文件存取操作的说法，正确的是（ ）

A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取 C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取 26.文件的检索有三种方式，它们是顺序存取、直接存取和____________存取。

26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是__________存取、直接存取和按关键字存取。

28．文件的基本存取单位是_______。

26.索引文件只能是________，因为索引文件的组织方式是为随机存取而设计的。 13.ISAM文件组织方式是一种（ ）

A.专门适用于磁带的存取方法 B.专门适用于磁盘的存取方法

C.专门适用于光盘的存取方法 D.可适用于磁带、磁盘、光盘等多用途的存取方法 27.若构成索引文件的索引表有序而主文件无序，则该索引文件称为________________文件。 13.磁盘是一种广泛使用的外部存储设备，对磁盘的存取操作( ) A.只能用顺序方式 B.只能用随机方式

C.既能用顺序方式也能用随机方式 D.方式取决于具体的机器

27.多关键字文件是指同时对__________两部分都建立索引的文件组织形式。 13.用于外存储器的数据组织结构散列文件，主要适用于( )

A.顺序存取 B.随机存取 C.索引存取 D.以上三种都可以 27.文件常见的存储结构有顺序文件、链接文件、 索引文件和____四种。 13.索引文件通常由索引表和主文件两部分构成，其中（ ）

A.索引表和主文件均必须是有序文件 B.索引表和主文件均可以是无序文件 C.索引表必须是有序文件 D.主文件必须是有序文件

27.ISAM其中文含义为___________方法。 12．散列文件不能（ ）

A．随机存取 B．索引存取 C．按关键字存取 D．直接存取

13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取时的平均访问外存次数为（

A．n/2 B．n C．n/4 D．log n

26．文件的基本运算包括______________和修改两类。

28