1、数据结构导论自考题-4 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.具有 10个顶点的有向完全图应具有( )A20 条弧 B50 条弧C90 条弧 D100 条弧（分数：2.00）A.B.C.D.2.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的( )A先根遍历 B中根遍历C后根遍历 D按层次遍历（分数：2.00）A.B.C.D.3.在无向图中，所有顶点的度数之和是所有边数的( )A0.5 倍 B1 倍C2 倍 D4 倍（分数：2.00）A.B.C.D.4.在一个具有 n个顶点的无向图中，要连通全部顶点至少需要( )An
2、 条边 Bn+1 条边Cn-1 条边 D （分数：2.00）A.B.C.D.5.从 v1出发，对下图按广度优先搜索遍历，则可能得到的一种顶点序列为( )（分数：2.00）A.B.C.D.6.设图 G采用邻接表存储，则拓扑排序算法的时间复杂度为( )AO(n) BO(n+e)CO(n 2) DO(n*e)（分数：2.00）A.B.C.D.7.设顺序表的长度为 n，则其每个元素的平均查找长度是( )An B(n-1)/2Cn/2 D(n+1)/2（分数：2.00）A.B.C.D.8.对一棵二叉排序树采用中序遍历进行输出的数据一定是( )A递增或递减序列 B递减序列C无序序列 D递增序列（分数：2.
3、00）A.B.C.D.9.二分查找算法要求被查找的表是( )A键值有序的链表 B键值不一定有序的链表C键值有序的顺序表 D键值不一定有序的顺序表（分数：2.00）A.B.C.D.10.适用于静态查找表的方法为( )A二分查找、二叉排序树查找 B二分查找、索引顺序表查找C二叉排序树查找、索引顺序表查找 D二叉排序树查找、散列法查找（分数：2.00）A.B.C.D.11.排序中关键字比较次数与序列的原始状态有关的排序方法是( )A插入排序法 B希尔排序法C直接选择排序法 D堆排序法（分数：2.00）A.B.C.D.12.下面给出的四种排序法中，属于不稳定的排序法的是( )A插入排序法 B冒泡排序法
4、C二路归并排序法 D堆排序法（分数：2.00）A.B.C.D.13.若用冒泡排序法对序列 18，14，6，27，8，12，16，52，10，26，47，29，41，24 从小到大进行排序，需要进行比较的次数是( )A33 B45C70 D91（分数：2.00）A.B.C.D.14.直接插入序列在最好情况下时间复杂度为( )AO(log 2n) BO(n)CO(n*log 2n) DO(n 2)（分数：2.00）A.B.C.D.15.一组记录的关键字为 45，80，55，40，42，85)，则利用堆排序的方法建立的初始堆为( )A80，45，55，40，42，85 B40，42，55，80，45
5、，85C40，42，45，55，80，85 D85，55，80，42，45，40（分数：2.00）A.B.C.D.二、填空题(总题数：13，分数：26.00)16.要连通具有 n个顶点的有向图，至少需要 1 条弧。（分数：2.00）填空项 1:_17.在无向图的邻接矩阵 A中，若 Ai,j等于 1，则 Aj,i等于 1。（分数：2.00）填空项 1:_18.含 n个顶点的连通图中的任意一条简单路径，其长度不可能超过 1。（分数：2.00）填空项 1:_19.有向图 G用邻接矩阵 A1n,1n存储，其第 i列的所有元素之和等于顶点 vi的 1。（分数：2.00）填空项 1:_20.对含有 n个结
6、点，e 条边的无向连通图，利用 Prim算法生成最小生成树的时间复杂度为 1。（分数：2.00）填空项 1:_21.用来标识数据元素的数据项称为 1。（分数：2.00）填空项 1:_22.对于具有 n个元素的数据序列，若采用二分查找法，当 n的值较大时其平均查找长度为 1。（分数：2.00）填空项 1:_23.在索引顺序表上的查找分两个阶段：一是 1，二是在块内查找待查的元素。（分数：2.00）填空项 1:_24.直接插入排序需要 1 个记录的辅助空间。（分数：2.00）填空项 1:_25.在插入和选择排序中，若初始数据基本正序，则选用 1 排序。（分数：2.00）填空项 1:_26.归并排序
7、要求待排序列由若干个 1 的子序列组成。（分数：2.00）填空项 1:_27.对 n个记录的集合进行快速排序，其最坏情况下所需的时间复杂度是 1。（分数：2.00）填空项 1:_28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的 1 中。（分数：2.00）填空项 1:_三、应用题(总题数：5，分数：30.00)29.已知无向图 G的邻接矩阵如图所示，假设对其每行元素访问时必须从右到左，请写出从 v0开始的深度优先搜索的序列。（分数：6.00）_30.求下图的最小生成树。（分数：6.00）_31.用二分查找法对一个长度为 10的有序表进行查找，填写查
8、找每一元素需要的比较次数。元素下标：1 2 3 4 5 6 7 8 9 10比较次数：（分数：6.00）_32.对于下列一组关键字(46，58，15，45，90，18，10，62)，试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。（分数：6.00）_33.有一组初始的无序序列为(98，65，38，40，12，51，100，77，26，88)，给出对其进行二路归并排序(升序)的每一趟的结果。（分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.试写出从大到小输出二叉排序树中所有不小于 x的元素的算法。（分数：7.00）_35.设计一个用链表表示的直接选择排序算法
9、。（分数：7.00）_数据结构导论自考题-4 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.具有 10个顶点的有向完全图应具有( )A20 条弧 B50 条弧C90 条弧 D100 条弧（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是一个具有 n个顶点的有向完全图的弧数。要点透析 任何两点之间都有弧的有向图称为有向完全图。一个具有 n个顶点的有向完全图的弧数为2.在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的( )A先根遍历 B中根遍历C后根遍历 D按层次遍历（分数：2.00）A.B.C.D. 解析：解
10、析 本题主要考查的知识点是广度优先搜索。要点透析 连通图广度优先搜索的基本思想是：从图中某个顶点 vi出发，在访问了 vi之后依次访问 vi的所有邻接点，然后分别从这些邻接点出发按广度优先搜索遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。类似于二叉树按层次(同一层从左到右)遍历的算法。3.在无向图中，所有顶点的度数之和是所有边数的( )A0.5 倍 B1 倍C2 倍 D4 倍（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是无向图中顶点的度数。要点透析 无向图中顶点的度数就是与该顶点相关联的边的数目。4.在一个具有 n个顶点的无向图中，要连通全部顶点至少需要( )
11、An 条边 Bn+1 条边Cn-1 条边 D （分数：2.00）A.B.C. D.解析：5.从 v1出发，对下图按广度优先搜索遍历，则可能得到的一种顶点序列为( )（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是广度优先搜索遍历。要点透析 连通图广度优先搜索的基本思想是：从图中某个顶点 vi出发，在访问了 vi之后依次访问 vi的所有邻接点，然后依次从这些邻接点出发按广度优先搜索方法遍历图的其他顶点，重复这一过程，直至所有顶点都被访问到。结合图形，本题答案应选 B。6.设图 G采用邻接表存储，则拓扑排序算法的时间复杂度为( )AO(n) BO(n+e)CO(n 2) DO
12、(n*e)（分数：2.00）A.B. C.D.解析：7.设顺序表的长度为 n，则其每个元素的平均查找长度是( )An B(n-1)/2Cn/2 D(n+1)/2（分数：2.00）A.B.C.D. 解析：8.对一棵二叉排序树采用中序遍历进行输出的数据一定是( )A递增或递减序列 B递减序列C无序序列 D递增序列（分数：2.00）A.B.C.D. 解析：解析 本题在 2008年 10月真题一大题 8小题考查过。主要考查的知识点是二叉排序树。要点透析 二叉排序树的组织结构能够反映其中数据元素在键值上的次序关系：任一结点的键值大于其左孩子(及其子孙)的键值且小于其右孩子(及其子孙)的键值。二叉排序树的
13、这一基本特点可以更严格地表述为二叉排序树的下述重要性质：中序遍历一棵二叉排序树所得的结点访问序列是键值的递增序列。9.二分查找算法要求被查找的表是( )A键值有序的链表 B键值不一定有序的链表C键值有序的顺序表 D键值不一定有序的顺序表（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是二分查找算法对被查找表的要求。要点透析 相比顺序查找而言，二分查找要求表元素是排好序的。当采用的存储结构不是顺序表，或者顺序表中元素未按键值的次序(递增或递减)排列时，则不能进行二分查找。10.适用于静态查找表的方法为( )A二分查找、二叉排序树查找 B二分查找、索引顺序表查找C二叉排序树查找
14、、索引顺序表查找 D二叉排序树查找、散列法查找（分数：2.00）A.B. C.D.解析：11.排序中关键字比较次数与序列的原始状态有关的排序方法是( )A插入排序法 B希尔排序法C直接选择排序法 D堆排序法（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点是插入排序法。要点透析 在关键字基本有序的情况下，插入排序每趟的关键字比较次数为 1次，总共进行 n-1次比较，而在初始关键字无序的情况下，最坏的时候，其关键字的比较的总次数为 n(n-1)/2次。而选项中的其他三种排序方法中关键字的比较次数，都与初始状态无关。12.下面给出的四种排序法中，属于不稳定的排序法的是( )A插入
15、排序法 B冒泡排序法C二路归并排序法 D堆排序法（分数：2.00）A.B.C.D. 解析：解析 本题主要考查的知识点是堆排序法。要点透析 所谓排序的稳定性，是指待排序序列中相同关键字在排序前后其相对位置不会改变。在所给选项中。只有堆排序是不稳定的。13.若用冒泡排序法对序列 18，14，6，27，8，12，16，52，10，26，47，29，41，24 从小到大进行排序，需要进行比较的次数是( )A33 B45C70 D91（分数：2.00）A.B.C.D. 解析：解析 本题主要考查的知识点是冒泡排序法。要点透析 冒泡排序法总的比较次数为 n(n-1)/2次，n 为待排序列元素个数。14.直接
16、插入序列在最好情况下时间复杂度为( )AO(log 2n) BO(n)CO(n*log 2n) DO(n 2)（分数：2.00）A.B. C.D.解析：15.一组记录的关键字为 45，80，55，40，42，85)，则利用堆排序的方法建立的初始堆为( )A80，45，55，40，42，85 B40，42，55，80，45，85C40，42，45，55，80，85 D85，55，80，42，45，40（分数：2.00）A.B. C.D.解析：二、填空题(总题数：13，分数：26.00)16.要连通具有 n个顶点的有向图，至少需要 1 条弧。（分数：2.00）填空项 1:_ （正确答案：n）解析：
17、17.在无向图的邻接矩阵 A中，若 Ai,j等于 1，则 Aj,i等于 1。（分数：2.00）填空项 1:_ （正确答案：1）解析：18.含 n个顶点的连通图中的任意一条简单路径，其长度不可能超过 1。（分数：2.00）填空项 1:_ （正确答案：n-1）解析：19.有向图 G用邻接矩阵 A1n,1n存储，其第 i列的所有元素之和等于顶点 vi的 1。（分数：2.00）填空项 1:_ （正确答案：入度）解析：20.对含有 n个结点，e 条边的无向连通图，利用 Prim算法生成最小生成树的时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：O(n 2)）解析：21.用来标识数据元素的
18、数据项称为 1。（分数：2.00）填空项 1:_ （正确答案：关键字）解析：22.对于具有 n个元素的数据序列，若采用二分查找法，当 n的值较大时其平均查找长度为 1。（分数：2.00）填空项 1:_ （正确答案：log 2(n+1)-1）解析：23.在索引顺序表上的查找分两个阶段：一是 1，二是在块内查找待查的元素。（分数：2.00）填空项 1:_ （正确答案：确定待查数据元素所在的块）解析：24.直接插入排序需要 1 个记录的辅助空间。（分数：2.00）填空项 1:_ （正确答案：1）解析：25.在插入和选择排序中，若初始数据基本正序，则选用 1 排序。（分数：2.00）填空项 1:_ （
19、正确答案：插入）解析：26.归并排序要求待排序列由若干个 1 的子序列组成。（分数：2.00）填空项 1:_ （正确答案：有序）解析：27.对 n个记录的集合进行快速排序，其最坏情况下所需的时间复杂度是 1。（分数：2.00）填空项 1:_ （正确答案：O(n 2)）解析：28.排序通常可分为内部排序和外部排序，其中内部排序是指排序的整个过程中，数据全部存放在计算机的 1 中。（分数：2.00）填空项 1:_ （正确答案：内存）解析：三、应用题(总题数：5，分数：30.00)29.已知无向图 G的邻接矩阵如图所示，假设对其每行元素访问时必须从右到左，请写出从 v0开始的深度优先搜索的序列。（分
20、数：6.00）_正确答案：(v 0v2v4v3v1)解析：30.求下图的最小生成树。（分数：6.00）_正确答案：(最小生成树如图所示：)解析：31.用二分查找法对一个长度为 10的有序表进行查找，填写查找每一元素需要的比较次数。元素下标：1 2 3 4 5 6 7 8 9 10比较次数：（分数：6.00）_正确答案：(元素下标：1 2 3 4 5 6 7 8 9 10比较次数如下：3 2 3 4 1 3 4 2 3 4)解析：32.对于下列一组关键字(46，58，15，45，90，18，10，62)，试写出快速排序每一趟的排序结果，并标出第一趟中各元素的移动方向。（分数：6.00）_正确答案
21、：(第一趟：46,58,15,45,90,18,10,62一次交换之后二次交换之后三次交换之后四次交换之后 )解析：33.有一组初始的无序序列为(98，65，38，40，12，51，100，77，26，88)，给出对其进行二路归并排序(升序)的每一趟的结果。（分数：6.00）_正确答案：(初始无序序列：98 65 38 40 12 51 100 77 26 88986538401251100772688第一次归并：65 9838 4012 5177 10026 88第二次归并：38 40 65 9812 51 77 10026 88第三次归并：12 38 40 51 65 77 98 1002
22、6 88第四次归并：12 26 38 40 51 65 77 88 98 100)解析：四、算法设计题(总题数：2，分数：14.00)34.试写出从大到小输出二叉排序树中所有不小于 x的元素的算法。（分数：7.00）_正确答案：(算法描述如下：void Print_NLT(BinTree T, int x)/从大到小输出二叉排序树 T中所有不小于 x/的元素if(T!=NULL)Print_NLT(T-rchild, x);/先对右子树进行递归遍历if(T-data=x)printf(“%d/n“, T-data);/当遇到大于等于 x的元素时，则输出 xprint_NLT(T-lchild,
23、 x);/后对左子树进行递归遍历)解析：35.设计一个用链表表示的直接选择排序算法。（分数：7.00）_正确答案：(每趟从单链表头部开始，顺序查找当前链值最小的结点。找到后，插入到当前的有序表区的最后。void selectsort(LinkList L)/设链表 L带头结点LinkList p, q, min;q=L;/指向头结点while(q-next!=NULL)min=q-next;/min指向当前已知的最小数p=q-next;while(P!=NULL)if(p-datamin-data)min=P;/找到了更小数P=p-next;/继续往下找if(min!=q-next)DataType t=min-data;min-data=q-next-data;/将最小数交换到第一个位置上q-next-data=t;q=qnext;/选择下一个最小数)解析：
