数据结构--图练习含答案.doc

《数据结构--图练习含答案.doc》由会员分享，可在线阅读，更多相关《数据结构--图练习含答案.doc（4页珍藏版）》请在金锄头文库上搜索。

1、数据结构-图练习含答案一单项选择题在一个图中，所有顶点的度数之和等于所有边数的_c_倍。A）1/2 B) 1 C) 2 D) 4在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的_b_倍。A) 1/2 B) 1 C) 2 D) 4一个有n个顶点的无向图最多有_c_条边。A) n B) n(n-1) C) n(n-1)/2 D) 2n具有4个顶点的无向完全图有_a_条边。A) 6 B) 12 C) 16 D) 20具有6个顶点的无向图至少应有_a_条边才能确保是一个连通图。A) 5 B) 6 C) 7 D) 8在一个具有n个顶点的无向图中，要连通全部顶点至少需要_c_条边。A) n B)

2、 n+1 C) n-1 D) n/2对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_d_。A) n B) (n-1)2 C) n-1 D) n2对于一个具有n个顶点和e条边的无向图，若采用邻接表示，则表头向量的大小为_a_，所有邻接表中的结点总数是_c_。 A) n B) n+1 C) n-1 D) n+e A) e/2 B) e C) 2e D) n+e已知一个图如下所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为_d_；按宽度搜索法进行遍历，则可能得到的一种顶点序列为_b_ _。 A) a,b,c,d,e,f B) a,c,f,e,b,dC) a,e

3、,b,c,f,d D) a,e,d,f,c,b A) a,b,c,d,e,f B) a,b,c,e,f,dC) a,e,b,c,f,d D) a,c,f,d,e,b已知一有向图的邻接表存储结构如图所示。根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是_c_。A) v1,v2,v3,v5,v4 B) v1,v2,v3,v4,v5 C) v1,v3,v4,v5,v2 D) v1,v4,v3,v5,v2根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是_b_。A) v1,v2,v3,v4,v5 B) v1,v3,v2,v4,v5 C) v1,v2,v3,v5,v4 D)

4、 v1,v4,v3,v5,v2采用邻接表存储的图的深度优先遍历算法类似于二叉树的_a_。A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历采用邻接表存储的图的宽度优先遍历算法类似于二叉树的d_。A) 先序遍历 B）中序遍历 C） 后序遍历 D） 按层遍历判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用_d_。A） 求关键路径的方法 B） 求最短路径的Dijkstra方法C） 宽度优先遍历算法 D） 深度优先遍历算法二填空题（将正确的答案填在相应的空中）N个顶点的连通图至少_N-1_条边。在无权图G的邻接矩阵A中，若（vi,vj）或属于图G的边集合，则对应元素Aij等于

5、_1_，否则等于_0_。在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于_1_。已知图G的邻接表如图1所示，其从顶点v1出发的深度优先搜索序列为_v1v2v3v6v5v4_，其从顶点v1出发的宽度优先搜索序列为_v1v2v5v4v3v6_。已知一个图的邻接矩阵表示，计算第I个结点的入度的方法是_。已知一个图的邻接矩阵表示，删除所有从第I个结点出发的边的方法是_。查找一单项选择题顺序查找法适合于存储结构为_b_的线性表。A） 散列存储 B） 顺序存储或链接存储C） 压缩存储 D） 索引存储对线性表进行二分查找时，要求线性表必须_b_。A） 以顺序方式存储 B） 以顺序方式存储，且结点关键字

6、有序排序C） 以链接方式存储 D） 以链接方式存储，且结点关键字有序排序采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_c_。A） n B) n/2 C) (n+1)/2 D) (n-1)/2采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为_c_。A) O(n2) B) O(nlog2n) C) O(n) D) O(log2n)二分查找和二叉排序树的时间性能_b_。A) 相同 B） 不相同有一个有序表为1，3，9，12，32，41，45，62，75，77，82，95，100，当二分查找值82为的结点时，_c_次比较后查找成功。A） 1 B） 2 C） 4 D）

7、 8设哈希表长m=14，哈希函数H(key)=key % 11。表中已有4个结点：addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是_d_。A） 8 B） 3 C） 5 D） 98有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_b_。A） 35/12 B） 37/12 C） 39/12 D） 43/12分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分_b_个结点最佳。A）

8、 10 B） 25 C） 6 D） 625如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_d_查找方法。A） 分块 B） 顺序 C） 二分 D） 散列二填空题顺序查找法的平均查找长度为_；二分查找法的平均查找长度为_；分块查找法（以顺序查找确定块）的平均查找长度为_；分块查找法（以二分查找确定块）的平均查找长度为_；哈希表查找法采用链接法处理冲突时的平均查找长度为_。在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_。二分查找的存储结构仅限于_，且是_。在分块查找方法中，首先查找_，然后再查找相应的_。长度为255的表，采用分块查找法，每块的最佳长度是_。在散列函

9、数H(key)=key % p中，p应取_。假设在有序线性表A1.20上进行二分查找，则比较一次查找成功的结点数为_10_，则比较二次查找成功的结点数为_5,15_，则比较三次查找成功的结点数为_2,7_12,18_，则比较四次查找成功的结点数为_1,3_,6,8,11,13,16,19_，则比较五次查找成功的结点数为_4,9,14,17,20_，平均查找长度为_3.7_。对于长度为n的线性表，若进行顺序查找，则时间复杂度为_o(n)_；若采用二分法查找，则时间复杂度为_o(logn)_。在散列存储中，装填因子的值越小，则_发生冲突的机会越小_。内排序一选择填空题在所有排序方法中，关键字比较的

10、次数与记录的初始排列次序无关的是_d_。A） 希尔排序 B） 起泡排序 C） 插入排序 D） 选择排序设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用_d_排序法。A） 起泡排序 B） 快速排序 C） 堆排序 D） 基数排序在待排序的元素序列基本有序的前提下，效率最高的排序方法是_a_。A） 插入排序 B） 选择排序 C） 快速排序 D） 归并排序一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为_b_。A） 79，46，56，38，40，80 B） 84，79，56，38，40，46C） 84，79，56，40，38 D

11、） 84，56，79，40，46，38一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为_c_。A） 38，40，46，56，79，84 B） 40，38，46，79，56，84C） 40，38，46，56，79，84 D） 40，38，46，84，56，79一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为_a_。A）16，25，35，48，23，40，79，82，36，72B）16，25，35，48，79，82，23

12、，36，40，72C）16，25，48，35，79，82，23，36，40，72D）16，25，35，48，79，23，36，40，72，82排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为_c_。A） 希尔排序 B） 起泡排序 C） 插入排序 D） 选择排序排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为_d_。A） 希尔排序 B） 归并排序 C） 插入排序 D） 选择排序用某种排序方法对线性表（25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变

13、化情况如下：（1）25，84，21，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84则所采用的排序方法是_c_。A） 希尔排序 B） 归并排序 C） 快速排序 D） 选择排序下述几种排序方法中，平均时间复杂度最小的是_a_。A） 快速排序 B） 归并排序 C） 插入排序 D） 选择排序下述几种排序方法中，要求内存量最大的是_b_。A） 快速排序 B） 归并排序 C） 插入排序 D） 选择排序快速排序方法在_c_情况下最不利于发挥其长处。

14、A） 要排序的数据量太大 B）要排序的数据中含有多个相同的值C） 要排序的数据已基本有序 D） 要排序的数据个数为奇数二填空题在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_3_次。在堆排序，快速排序和归并排序中，若只从存储窨考虑，则应首先选取_堆排序_方法，其次选取_快速排序_方法，最后选取归并排序_方法；若只从排序结果的稳定性考虑，则应选取_归并排序_方法；若只从平均情况下排序最快考虑，则应选取_快速排序_方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取_堆排序_方法。在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有_希尔排序、快速排序、堆排序_。在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是_基数排序_，需要内存容量最多的是_归并排序_。在堆排序和快速排序中，若原始记录接近正序或反序，则选用_堆排序_，若原始记录无序，则最好选用_快速排序_。在插入和选择排序中，若初始数据基本正序，则选用_插入排序_；若初始数据基本反序，则选用_选择排序_。对n个元素的序列进行起泡排序时，最少的比较次数是_n-1_。