1、数据结构导论自考题-2 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )A存储结构 B存储实现C逻辑结构 D运算实现（分数：2.00）A.B.C.D.2.所有的存储结点存放在一个连续的存储空间，该存储方式是( )存储方式。A顺序 B链式C索引 D散列（分数：2.00）A.B.C.D.3.设线性表有 n个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。A输出第 i(1in)个元素值 B交换第 1个元素与第 2个元素的值C在第 i个元素前插入一个元素 D删除第 i个
2、元素（分数：2.00）A.B.C.D.4.与单链表相比，双链表的优点之一是( )A插入、删除操作更简单 B可以进行随机访问C可以省略表头指针或表尾指针 D前后访问相邻结点更灵活（分数：2.00）A.B.C.D.5.循环队列的队满条件为( )A(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeB(CQ.rear+1)%maxsize=CQ.front+1C(CQ.rear+1)%maxsize=CQ.frontDCQ.rear=CQ.front（分数：2.00）A.B.C.D.6.数组 A0.50.5的每个元素占 5个字节，将其以列为主序存储在起始地址为 1000的
3、内存单元中，则元素 A55的地址是( )A1175 B1180C1205 D1210（分数：2.00）A.B.C.D.7.若二叉树(如图所示)采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，最合适的遍历方法是( )（分数：2.00）A.B.C.D.8.设有一个 10阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a 00为第一个元素，其存储地址为0，每个元素占有 1个存储地址空间，则 a45的地址为( )A13 B19C17 D36（分数：2.00）A.B.C.D.9.在有向图中，所有顶点的入度之和是所有顶点出度之和的( )A0.5 倍 B1 倍C2 倍 D4 倍（分数：2.00
4、）A.B.C.D.10.设无向图 G中顶点数为 n，则图 G最多拥有边的条数是( )An Bn-1Cn(n-1)/2 Dn(n-1)（分数：2.00）A.B.C.D.11.在图中，从顶点 v1出发，按深度优先遍历图的顶点序列是( )（分数：2.00）A.B.C.D.12.采用分块查找时，若线性表中共有 625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分结点的个数是( )A10 B25C6 D625（分数：2.00）A.B.C.D.13.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上，应采用( )A归并排序 B插入排序C快速
5、排序 D选择排序（分数：2.00）A.B.C.D.14.具有 24个记录的序列，采用冒泡排序最少的比较次数是( )A1 B23C24 D529（分数：2.00）A.B.C.D.15.用某种排序方法对序列(25，84，21，47，15，27，68，35，20)进行排序，记录序列的变化情况如下：25 84 21 47 15 27 68 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则采用的排序方法是( )A直接选择排序 B冒泡排序C快速排序 D二路归并排序（分数：2.00）A.B
6、.C.D.二、填空题(总题数：13，分数：26.00)16.空间复杂度是对一个算法在运行过程中临时占用 1 的度量。（分数：2.00）填空项 1:_17.在数据结构中，数据的逻辑结构分为集合、 1、树形结构和图结构等四类。（分数：2.00）填空项 1:_18.对顺序表执行插入操作，其插入算法的平均时间复杂度为 1。（分数：2.00）填空项 1:_19.如图所示，设输入元素的顺序是 A、B、C、D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为 D，则输出序列为_。（分数：2.00）填空项 1:_20.队列中，新加入的数据元素插在 1。（分数：2.00）填空项 1:_21.设有二
7、维数组 int M1020，每个元素(整数)占 2个存储单元，数组的起始地址为 2000，元素 M510的存储位置为_，M819的存储位置为_。（分数：2.00）填空项 1:_22.树在数据结构中常采用孩子链表表示法、 1、双亲表示法三种存储结构表示。（分数：2.00）填空项 1:_23.若某二叉树中度为 1的结点数为 4，度为 2的结点数为 6，则该树叶子结点数为 1。（分数：2.00）填空项 1:_24.具有 n个叶子结点的哈夫曼树，其结点总数为 1。（分数：2.00）填空项 1:_25.一个具有 n个顶点的有向完全图的弧数为 1。（分数：2.00）填空项 1:_26.已知有向图 G=(V
8、，E)，其中：V=v1，v 2，v 3，v 4，v 5，v 6，v 7E=v 1，v 2，v 1，v 3，v 1，v 4，v 2，v 5，v 3，v 7，v 3，v 6，v 4，v 6，v 5，v 7，v 6，v 7G的拓扑序列是_。（分数：2.00）填空项 1:_27. 1方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。（分数：2.00）填空项 1:_28.堆排序是不稳定的，在最坏情况下，其时间复杂度为 1。（分数：2.00）填空项 1:_三、应用题(总题数：5，分数：30.00)29.对于图所示二叉树，分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。（分数
9、：6.00）_30.有一份电文中共使用五个字符：a，b，c，d，e，它们的出现频率依次为 8，14，10，4，18，请构造相应的哈夫曼树。（分数：6.00）_31.若某无向图 G的邻接表如图所示，试给出以顶点 v1为出发点，按广度优先搜索所产生的一棵生成树。（分数：6.00）_32.从一个空的二叉排序树开始，依次插入关键字 25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。（分数：6.00）_33.已知一组键值序列(32，44，38，65，53，42，29，57)，试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次输出堆元素后筛选调整的堆。（分数：6.
10、00）_四、算法设计题(总题数：2，分数：14.00)34.若循环单链表长度大于 1，p 为指向链表中某结点的指针，试编写一算法删除 p结点的前驱结点。（分数：7.00）_35.插入排序中找插入位置的操作可以通过二分查找的方法来实现。试据此写一个改进后的插入排序算法。（分数：7.00）_数据结构导论自考题-2 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )A存储结构 B存储实现C逻辑结构 D运算实现（分数：2.00）A.B.C. D.解析：2.所有的存储结点存放在一个连续的存
11、储空间，该存储方式是( )存储方式。A顺序 B链式C索引 D散列（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点是顺序存储方式。要点透析 顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。3.设线性表有 n个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。A输出第 i(1in)个元素值 B交换第 1个元素与第 2个元素的值C在第 i个元素前插入一个元素 D删除第 i个元素（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点为顺序表和链表。要点透析 由于顺序表具有随机存取特性，所以和链
12、表相比输出第 i个元素时效率很高。本题答案为A。4.与单链表相比，双链表的优点之一是( )A插入、删除操作更简单 B可以进行随机访问C可以省略表头指针或表尾指针 D前后访问相邻结点更灵活（分数：2.00）A.B.C.D. 解析：5.循环队列的队满条件为( )A(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeB(CQ.rear+1)%maxsize=CQ.front+1C(CQ.rear+1)%maxsize=CQ.frontDCQ.rear=CQ.front（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是循环队列的队满条件。要点透析 约定循
13、环队列的队头指针指示队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。当队尾指针“绕一圈”后赶上队头指针时，视为队满。6.数组 A0.50.5的每个元素占 5个字节，将其以列为主序存储在起始地址为 1000的内存单元中，则元素 A55的地址是( )A1175 B1180C1205 D1210（分数：2.00）A. B.C.D.解析：7.若二叉树(如图所示)采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，最合适的遍历方法是( )（分数：2.00）A. B.C.D.解析：解析 本题主要考查的知识点是二叉链表存储结构。要点透析 交换二叉树的左右子树的过程可用递归
14、方法完成，第 1步将根结点的左右子树交换，第 2步在左子树中递归调用交换函数，第 3步在右子树中递归调用交换函数。因此，采用先序遍历的方法最合适。8.设有一个 10阶的对称矩阵 A，采用压缩存储方式以行序为主序存储，a 00为第一个元素，其存储地址为0，每个元素占有 1个存储地址空间，则 a45的地址为( )A13 B19C17 D36（分数：2.00）A.B. C.D.解析：9.在有向图中，所有顶点的入度之和是所有顶点出度之和的( )A0.5 倍 B1 倍C2 倍 D4 倍（分数：2.00）A.B. C.D.解析：10.设无向图 G中顶点数为 n，则图 G最多拥有边的条数是( )An Bn-
15、1Cn(n-1)/2 Dn(n-1)（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是无向图中边的条数。要点透析 在无向图为完全图时，取得的边数最多，此时任意两个顶点间都有直接边，边的条数为：(n-1)+2+1=n(n-1)/2。11.在图中，从顶点 v1出发，按深度优先遍历图的顶点序列是( )（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是深度优先遍历。要点透析 连通图深度优先搜索的基本思想是：假定图中某个顶点 vi为出发点。首先访问出发点，然后任选一个 vi的未访问过的邻接点 vj，以 vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问
16、过。12.采用分块查找时，若线性表中共有 625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分结点的个数是( )A10 B25C6 D625（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是分块查找。要点透析 分块查找一般都是要求每个块的存储空间大小是一样的，而且块数不能太多，每个块也不要太小，否则就成了顺序查找了。由于 10和 6都不能被 625整除，不宜作为划分块的标准，而如果采用625，则每个块只有一个元素，这样就失去了分块的意义了。13.从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上，应采用( )
17、A归并排序 B插入排序C快速排序 D选择排序（分数：2.00）A.B. C.D.解析：14.具有 24个记录的序列，采用冒泡排序最少的比较次数是( )A1 B23C24 D529（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是冒泡排序。要点透析 冒泡排序的思想为：在每一次排序过程中，通过相邻元素的交换，将当前没有排好序中的最大(小)移到数组的最右(左)端。在递增(减)顺序中，排序所需次数最小，24 个记录需排 23次。15.用某种排序方法对序列(25，84，21，47，15，27，68，35，20)进行排序，记录序列的变化情况如下：25 84 21 47 15 27 68
18、 35 2020 15 21 25 47 27 68 35 8415 20 21 25 35 27 47 68 8415 20 21 25 27 35 47 68 84则采用的排序方法是( )A直接选择排序 B冒泡排序C快速排序 D二路归并排序（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是快速排序。要点透析 此题可使用排除法。选项 A，若使用直接选择排序，第一个元素应为 15，而给出的是 25，所以排除。选项 B、C 两种排序方法，同属交换排序法，观察发现，第一趟排序，有明显的分组情况(按 25分为两组)，可得最佳答案应为 C。题目没有采用合并的方式。二、填空题(总题数
19、：13，分数：26.00)16.空间复杂度是对一个算法在运行过程中临时占用 1 的度量。（分数：2.00）填空项 1:_ （正确答案：存储空间大小）解析：17.在数据结构中，数据的逻辑结构分为集合、 1、树形结构和图结构等四类。（分数：2.00）填空项 1:_ （正确答案：线性结构）解析：18.对顺序表执行插入操作，其插入算法的平均时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：O(n)）解析：19.如图所示，设输入元素的顺序是 A、B、C、D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为 D，则输出序列为_。（分数：2.00）填空项 1:_ （正确答案：DC
20、BA）解析：20.队列中，新加入的数据元素插在 1。（分数：2.00）填空项 1:_ （正确答案：队尾）解析：21.设有二维数组 int M1020，每个元素(整数)占 2个存储单元，数组的起始地址为 2000，元素 M510的存储位置为_，M819的存储位置为_。（分数：2.00）填空项 1:_ （正确答案：2220 2358）解析：22.树在数据结构中常采用孩子链表表示法、 1、双亲表示法三种存储结构表示。（分数：2.00）填空项 1:_ （正确答案：孩子兄弟链表表示法）解析：23.若某二叉树中度为 1的结点数为 4，度为 2的结点数为 6，则该树叶子结点数为 1。（分数：2.00）填空项
21、 1:_ （正确答案：7）解析：24.具有 n个叶子结点的哈夫曼树，其结点总数为 1。（分数：2.00）填空项 1:_ （正确答案：2n-1）解析：25.一个具有 n个顶点的有向完全图的弧数为 1。（分数：2.00）填空项 1:_ （正确答案：n(n-1)）解析：26.已知有向图 G=(V，E)，其中：V=v1，v 2，v 3，v 4，v 5，v 6，v 7E=v 1，v 2，v 1，v 3，v 1，v 4，v 2，v 5，v 3，v 7，v 3，v 6，v 4，v 6，v 5，v 7，v 6，v 7G的拓扑序列是_。（分数：2.00）填空项 1:_ （正确答案：v 1 v3 v4 v6 v2
22、 v5 v7）解析：27. 1方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。（分数：2.00）填空项 1:_ （正确答案：快速排序）解析：28.堆排序是不稳定的，在最坏情况下，其时间复杂度为 1。（分数：2.00）填空项 1:_ （正确答案：O(nlog 2n)）解析：三、应用题(总题数：5，分数：30.00)29.对于图所示二叉树，分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。（分数：6.00）_正确答案：(先序遍历：ABDEFC中序遍历：BFEDAC后序遍历：FEDBCA)解析：30.有一份电文中共使用五个字符：a，b，c，d，e，它们的出现频率依次为
23、 8，14，10，4，18，请构造相应的哈夫曼树。（分数：6.00）_正确答案：(所求哈夫曼树如图所示：)解析：31.若某无向图 G的邻接表如图所示，试给出以顶点 v1为出发点，按广度优先搜索所产生的一棵生成树。（分数：6.00）_正确答案：(所求生成树如图所示：)解析：32.从一个空的二叉排序树开始，依次插入关键字 25、13、15、34、7、20、37，试分别画出每次插入关键字后的二叉排序树。（分数：6.00）_正确答案：(所求二叉排序树如图所示：)解析：33.已知一组键值序列(32，44，38，65，53，42，29，57)，试采用堆排序法对该组序列作升序排序，给出建立的初始堆以及第一次
24、输出堆元素后筛选调整的堆。（分数：6.00）_正确答案：(所求初始堆如图(a)所示：输出堆顶后的调整堆如图(b)所示：)解析：四、算法设计题(总题数：2，分数：14.00)34.若循环单链表长度大于 1，p 为指向链表中某结点的指针，试编写一算法删除 p结点的前驱结点。（分数：7.00）_正确答案：(Node*delete(p)Node*P;Node*q, *r;q=p;while(q-next!=p) q=q-next;r=q;while(r-next!=q) r=r-next;r-next=p;free(q);return(p);)解析：35.插入排序中找插入位置的操作可以通过二分查找的方
25、法来实现。试据此写一个改进后的插入排序算法。（分数：7.00）_正确答案：(插入排序的基本思想是：每趟从无序区间中取出一个元素，再按键值大小插入到前面的有序区间中。对于有序区间，就可以用二分查找来确定插入位置。void straightsort (DataType A, int n)/n为元素个数，数组下标从 0开始，到 n-1结束, 0 下标用来存储监视哨int low, high, mid, i, j;for(i=2; i=n; i+)low=1; high=i-1;/low, high分为当前元素低端下标和高端下标A0.key=Ai.key;/取 Ai元素找在有序区间中位置while(low=high)mid=(low+high)/2;if(A0.key=Amid.key)high=mid-1; /修改低端下标else low=mid+1; /修改高端下标for (j=i-1; j=low; j-)Aj+1.key=Aj.key; /移动数据Alow.key=A0.key;)解析：
