[答案]C)
2.一有向图G的邻接表存储结构如图8所示。现按深度优先遍历算法，从顶点V1出发，所得到的顶点序列是( )。
A)V1,V3,V2,V4,V5 B)V1,V3,V4,V2,V5
C)V1,V2,V3,V4,V5 D)V1,V3,V4,V5,V2 注:其中12345全是下标
3.设有两个无向图G=(V,E),G＇=(V＇,E＇)，如果G＇是G的生成树，则下述不正确的说法是( )。
A)G＇是G的子图 B)G＇是G的连通分量
C)G＇是G的无环子图 D)G＇是G的极小连通子图,且V＇=V
[分析]如果 是G的生成树，显然 是G的子图，也是G的无环子图，并且还是G的极小连通子图，且 。而连通分量则是无向图的极大连通子图，故答案B)是错误的。
[答案]B)
4.在无向图中，所以顶点的度数之和是所有边数的( )倍。
A)0.5 B)1 C)2 D)4
5.在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的( )。
A)先根遍历 B)中根遍历 C)后根遍历 D)按层次遍历
[分析]深度优先搜索遍历的核心思想是从某顶点出发，先访问该顶点，再依次搜索该点的每一个邻接点，如果找到尚未访问过的邻接点，则以此邻接点为新的出发点进行深度优先搜索遍历。从这里可以看出，它是先访问出发点(相当于根结点)，再依次遍历邻接点(相当于根的孩子)，因此深度优先搜索遍历类似于二叉树的先根遍历。
[答案]A)
6.设有一无向图 ，其中V={1,2,3,4,5,6}，E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5)}。
1)按上述顺序输入后，画出其相应的邻接表；
2)在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。
[分析]建立邻接表的过程可以参照教材上的build-adjlist算法进行，但要注意教材上的算法是针对有向图的，而本例是无向图。另外，建表时每次都是在边表的头部插入结点，而且对边(i,j)既要链到i边表上，也要链到j边表上。
[答案]1)按题中顺序输入各条边后建立起来的邻接表如图9所示。
2)在邻接表上进行深度优先遍历所得到的DFS序列为4,5,3,1,6,2；在邻接表上进行广度优先遍历所得到的BFS序列为4,5,3,6,1,2。
六.查找表
1.设顺序表的长度为n，则其每个元素的平均查找长度是( )。
A)n B)(n-1)/2 C)n/2 D)(n+1)/2
[分析]对长度为n的顺序表，在查找成功的前提下，最好情况为1(查找第一个元素)，最坏为n(查找最后一个元素),故其每个元素的平均查找长度为(1+n)/2。
[答案]D)
2.静态查找表与动态查找表两者的根本差别在于( )。
A)逻辑结构不同 B)存储实现不同 C)施加的操作不同 D)数据元素的类型不同
[分析]根据施加的运算不同，查找表被分为静态查找表和动态查找表。前者仅包含检索操作，后者除检索操作外，还允许施加修改操作。
[答案]C)
3._________查找法的平均查找长度与元素个数n无关。
[分析]散列表查找法是将元素的键值代入散列函数中，通过计算得到散列地址，因此它的平均查找长度与元素个数n无关。
[答案]散列表。
4.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为______，比较二次查找成功的结点数为________，比较三次查找成功的结点数为_________，比较四次查找成功的结点数为________，比较五次查找成功的结点数为__________。总的比较查找长度为__________。
[分析]二分查找过程可以与一棵有序二叉树相对应，那么第一层上1个结点，第二层上2个结点，第三层上4个结点，第四层上8个结点，第5层上9个结点。平均查找长度ASL=(1*1+2*2+3*4+4*8+5*9)/24=3.92
[答案]1,2,4,8,9,3.92。
5.在二叉排序树上插入新结点时，不必移动其他结点，仅需使某结点的指针域由________变为_________即可。
[分析]在二叉排序数上插入的新结点一定是个叶子，因此无需移动其他结点，只要将该叶子的双亲结点的指针域由空改为指向该叶子即可。
[答案]空，非空。
七.文件
1.文件的基本运算分为检索和修改两类，前者有3中方式，分别是________、_________和__________。
[答案]顺序存取，直接存取，按关键字存取。
八.排序
1.当文件局部有序或文件长度较小的情况下，最佳的排序方法是( )。
A)直接插入排序 B)直接选择排序 C)冒泡排序 D)归并排序
[分析]在教材介绍的几种排序方法中，冒泡排序算法里设置了一个标志，以判断某趟排序过程中，待排序空间是否自然有序。因此它适用于局部有序的文件。另外，冒泡排序属于内部排序，在文件较小时，允许用内部排序算法进行排序，故本题的正确答案是B)。
[答案]B)
2.当初始序列已按键值有序时，用直接插入算法进行排序，需要比较的次数为( )。
A)n-1 B)log2n（注：2是下标） C)2log2n（注：后一个2是下标） D)n2（注：2是上标）
[分析]直接插入排序是每趟从待排序空间取一个元素，按键值从有序区间的尾部向前查找插入位置。当初始序列已按键值有序时，则每趟比较一次就找到了正确的插入位置。n个元素进行n-1趟排序，故总的比较次数是n-1。
[答案]A)。
3.快速排序在最坏情况下的时间复杂度是( )。
A)O(log2n)（注：2是下标） B)O(nlog2n)（注：2是下标） C)O(n2)（注：2是上标） D)O(n3)（注：3是上标）
[分析]当待排序空间事先已基本有序时，每趟快速排序后得到的左、右两个待排序小空间严重不对称，因此，差不多要进行n趟次快速排序，每趟排序又要进行n级次数的比较，故最坏情况下，总的比较次数将达到O( )。
[答案]C)。
4.用某种排序方法对序列(25,84,21,15,27,68,35,20)进行排序，记录序列的变化情况如下：
25 84 21 47 15 27 68 35 20
20 15 21 25 47 27 68 35 84
15 20 21 25 35 27 47 68 84
15 20 21 25 27 35 47 68 84
则采用的排序方法是()。
A)直接选择排序 B)冒泡排序 C)快速排序 D)二路归并排序
[答案]C)。
5.在排序过程中，键值比较的次数与初始序列的排列顺序无关的是()。
A)直接插入排序和快速排序 B)直接插入排序和归并排序
C)直接选择排序和归并排序 D)快速排序和归并排序和归并排序
[分析]初始序列的排列顺序对直接插入排序和快速排序有影响，而对直接选择排序和归并排序则没有影响，故正确的答案是C)。
[答案]C)。
6.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则________最省时间，_________最费时间。
[分析]对冒泡排序来讲，由于算法中设置了一个标志flag，用于记载一趟排序中是否出现了记录交换，以便判断当前排序区域是否已自然有序。因此本题中用冒泡排序最省时间。
当初始时记录已按键值递增有序，若按快速排序，因每次所选取的中间元素都是最小的，故划分出的左右两个区域一个为空，另一个比原区域少一个元素，使得元素的比较次数只比上一趟少1，所以总的时间消耗是O( )，因此在本题中用快速排序法最费时间。
[答案]冒泡排序，快速排序。
7.对于下列一组关键字46,58,15,45,90,18,10,62。试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。
[分析]按快速排序算法得到的各趟结果如图10所示。其中，方括号里的是待排序区域，方括号外面的元素表示已找到的最终位置。在第一趟中，箭头表示的是元素的移动方向，而旁边的序号则表示移动的次序。 |
