数据结构导论真题分类整理详细 下载本文

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 C.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