题8图 题10图 9.下面关于生成树的描述中，不正确的是( )
A.生成树是树的一种表现形式 B.生成树一定是连通的 C.生成树一定不含有环 D.若生成树顶点个数为n，则其边数一定为n-1
10.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列 是( ) A v1v2v3v4v5 B v1v2v3v5v4 C v1v4v3v5v2 D v1v3v4v5v2 24.图主要采用___________两种存储结构存放。
30．试用prim算法构造下图的最小生成树，要求分步给出构造过程。
题31图
9.在一个无向图中，所有顶点的度数之和等于边数的（ ） A.1倍 B.2倍 C.3倍 D.4倍
10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（ ） A.先根遍历 B.中根遍历 C.后根遍历 D.层次遍历
24.若图的邻接矩阵是一个对称矩阵，则该图一定是一个___________。
30．若某无向图G的邻接表如图所示，试给出以顶点V1为出发点，按广度优先搜索所产生的一棵生成树。
8．邻接表是图的一种（ ）
A．顺序存储结构 B．链式存储结构 C．索引存储结构 D．散列存储结构
9．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（ ） A．G肯定不是完全图 B．G一定不是连通图 C．G中一定有回路 D．G有2个连通分量 10．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（ ） A．n/2 B．n C．(n+1)/2 D．n+1
22．顶点数为n、边数为n(n-1)/2的无向图称为__________。
31．已知无向图G的邻接表如下，请写出其从顶点V2开始的深度优先搜索的序列。（4分）
21
22
第六章 查找 真题
8.对线性表进行二分查找时，要求线性表必须( )
A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列
27.动态查找中两个元素X，Y存入同一个散列表时，X、Y键值相同，则这种情况称为____________。
7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ ）A.1 B.2 C.3 D.4 12.用n个值构造一棵二叉排序树，它的最大高度为（ ） A.n/2 B. n C. n+1 D.log2n 27.顺序查找算法的平均查找长度为______。
31.题31图中二叉排序树的各结点的值为1～9，标出各结点的值。
13.二分查找算法的时间复杂度是（ ）A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)
14.已知8个元素(34，76，45，18，26，54，92，65)，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（ ） A.4 B.5 C.6 D.7
25.假定对线性表R[0…59]进行分块检索，共分为10块，每块长度等于6。若检索索引表和块均用顺序检索的方法，则检索每一个元素的平均检索长度为_________。
12.对一棵二叉排序树采用中根遍历进行输出的数据一定是（ ） A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列
13.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为（ ）A.1 B.2 C.4 D.8
32.给定表（39，14，22，8，65，28，88，29，67，13，10），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。
12.若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不超过( )A.n/2 B.n C.n+1/2 D.n+1 13.闭散列表中由于散列到同一个地址而引起的―堆积‖现象，是( ) A.由同义词之间发生冲突引起的 B.由非同义词之间发生冲突引起的 C.由同义词之间或非同义词之间发生冲突引起的 D.由散列表―溢出‖引起的 24.在一棵二叉排序树上按_________遍历得到的结点序列是一个有序序列。
25.实现二分查找的存储结构仅限于顺序存储结构，且其中元素排列必须是____________的。
31.设闭散列表容量为7（散列地址空间0..6），给定表（30，36，47，52，34）,散列函数H（K）=K mod 6，采用线性探测法解决冲突，要求：（1）构造散列表；（2）求查找数34需要比较的次数。
12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表
13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是( ) A.线性探测法 B.除留余数法 C.平方取中法 D.折叠法
24.设顺序表的表长为n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为__________。
25.在索引顺序表上的查找分两个阶段：一是查找__________，二是查找块。 33.对长度为20的有序表进行二分查找，试画出它的一棵判定树。
23
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.二叉排序树查找、散列法查找
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.二次探测法、链地址法
24
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．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值的前面，下次的查找区间为从原开始位置至（ ）
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需要的比较次数。
25