1、数据结构导论自考题模拟 16 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为_（分数：2.00）A.机外表示、存储结构、逻辑结构B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.逻辑结构、存储结构、机外表示2.下列关于线性表的基本操作中，属于加工型的操作是_（分数：2.00）A.初始化、插入、删除操作B.初始化、求表长度、插入操作C.求表长度、读元素、定位操作D.定位、插入、删除操作3.若在长度为 n 的顺序表中插入一个结点，则其结点的移动次数_（分数：2
2、.00）A.最少为 1，最多为 nB.最少为 0，最多为 nC.最少为 0，最多为 n+1D.最少为 1，最多为 n+14.循环队列的队满条件为_（分数：2.00）A.(CQ.rear+1)%maxsize=CQ.frontB.(CQ.rear+1)%maxsize=CQ.front+1C.(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeD.CQ.rear=CQ.front5.顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置，elem 为存放栈的数组，则元素 e 进栈操作的主要语句为_（分数：2.00）A.elemtop=e;s.top=s.top+1
3、;B.elemtop+1=e;s.top=s.top+1;C.top=s.top+1;s.elemtop+1=e;D.top=s.top+1;s.elemtop=e;6.设一个栈的输入序列是 a，b，c，d，则所得到的输出序列(输入过程中允许出栈)不可能出现的是_（分数：2.00）A.a，b，c，dB.c，d，a，bC.d，c，b，aD.a，b，d，c7.若二叉树(如下图所示)采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，最合适的遍历方法是_ （分数：2.00）A.先序遍历B.中序遍历C.后序遍历D.按层次遍历8.除根结点外，树上每个结点_（分数：2.00）A.可有一个孩子、任意多
4、个双亲B.可有任意多个孩子、任意多个双亲C.可有任意多个孩子、一个双亲D.只有一个孩子、一个双亲9.设有二维数组 （分数：2.00）A.B.C.D.10.从 V 1 出发，对下图按广度优先搜索遍历，则可能得到的一种顶点序列为_ （分数：2.00）A.V1V2V3V4V5V6B.V1V3V6V4V5V2C.V1V5V2V3V6V4D.V1V2V3V5V6V411.设有无向图 G=(V，E)和 G“=(V“，E“)，如果 G“为 G 的生成树，则下面说法不正确的是_（分数：2.00）A.G“为 G 的连通分量B.G“为 G 的子图C.G“为 G 的极小连通子图且 V“=VD.G“是 G 的无环子图
5、12.设图的邻接链表如下图所示，则该图的边的数目是_ （分数：2.00）A.4B.5C.10D.2013.采用二分查找法，若当前取得的中间位置 MID 的元素值小于被查找值，则表明待查元素可能在表的后半部分，下次查找的起始位置通常应_（分数：2.00）A.从 MID/2 位置开始B.从 MID 位置开始C.从 MID+1 位置开始D.从 MID-1 位置开始14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_（分数：2.00）A.插入排序B.快速排序C.冒泡排序D.选择排序15.若对序列(25，91，23，53，1 6，34，69，39，22)进行一趟排序后所得到的结果为(2
6、2，16，23，25，53，34，69，39，91)，则该排序可能使用的方法是_（分数：2.00）A.插入排序B.冒泡排序C.快速排序D.选择排序二、填空题(总题数：13，分数：26.00)16.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为 1。 （分数：2.00）17.设有指针 head 指向不带表头结点的单链表，用 next 表示结点的一个链域，指针 q 指向与链表中结点同类型的一个新结点。现要将指针 q 指向的结点插入表中，使之成为第一个结点，则所需的操作为“q-next=head;”和“ 1”。 （分数：2.00）18.对顺序表执行删除操作，其删除算法的平均
7、时间复杂性为 1。 （分数：2.00）19.在具有 n 个单元且采用顺序存储的循环队列中，队满时共有 1 个元素。 （分数：2.00）20.在循环队列中，存储空间为 0(n-1)，设队头指针 front 指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为 front=(rear+1)%n，队空标志为 1。 （分数：2.00）21.设有二维数组 int M1020，每个元素(整数)占 2 个存储单元，数组的起始地址为 2000，元素 M610的存储位置为 1，M820的存储位置为 2。 （分数：2.00）22.若用后序遍历法遍历下图所示的二叉树，其输出序列为 1。 （分数：2.00
8、）23.对于一棵具有 m 个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为 1 个，其中 2个用于链接孩子结点。 （分数：2.00）24.一个具有 20 个顶点的完全无向图中有 1 条边。 （分数：2.00）25.对于具有 n 个元素的数据序列，采用二叉排序树查找，其平均查找长度为 1。 （分数：2.00）26.采用折半查找方法进行查找的数据序列应为 1 且 2。 （分数：2.00）27.对 20 个元素进行冒泡排序时，第一趟排序的比较次数为 1。 （分数：2.00）28.冒泡排序最好的时间复杂度为 1，平均时间复杂度为 2，是一种 3 的排序算法。 （分数：2.00）三、应用题
9、(总题数：5，分数：30.00)29.二叉树如下图所示，分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。 （分数：6.00）30.如下图所示，输入元素为 A，B，C，在栈的输出端得到一个输出序列 ABC，试写出在栈的输入端三个可能的输入序列。 （分数：6.00）31.已知连通网的邻接矩阵 （分数：6.00）32.已知一组键值序列(30，45，35，42，53，60，34，22)，试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 （分数：6.00）33.试写出下图的拓扑序列。 （分数：6.00）四、算法设计题(总题数：2，分数：14.00)34.现二叉树用二叉链表表示，试编写一算
10、法求解一棵二叉树的叶子总数(可采用递归算法描述)。 （分数：7.00）_35.设某单链表中存在多个结点，其数据值均为 D，试编写一算法统计该类结点的个数。 （分数：7.00）_数据结构导论自考题模拟 16 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为_（分数：2.00）A.机外表示、存储结构、逻辑结构B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构 D.逻辑结构、存储结构、机外表示解析：考点 实际数据转化到计算机所能表示的形式的过程 解析 实际数据转化到计算
11、机所能表示的形式的转化过程为机外表示、逻辑结构、存储结构。2.下列关于线性表的基本操作中，属于加工型的操作是_（分数：2.00）A.初始化、插入、删除操作 B.初始化、求表长度、插入操作C.求表长度、读元素、定位操作D.定位、插入、删除操作解析：考点 线性表的基本操作 解析 线性表的基本操作中，属于加工型的操作是初始化、插入、删除操作。3.若在长度为 n 的顺序表中插入一个结点，则其结点的移动次数_（分数：2.00）A.最少为 1，最多为 nB.最少为 0，最多为 n C.最少为 0，最多为 n+1D.最少为 1，最多为 n+1解析：考点 顺序表的插入操作 解析 顺序表的插入需要移动原结点，在
12、长度为 n 的顺序表中插入一个结点，最少时即插在尾部，无须移动结点；当需插入到最前面时，需要移动 n 个结点。4.循环队列的队满条件为_（分数：2.00）A.(CQ.rear+1)%maxsize=CQ.front B.(CQ.rear+1)%maxsize=CQ.front+1C.(CQ.rear+1)%maxsize=(CQ.front+1)%maxsizeD.CQ.rear=CQ.front解析：考点 循环队列队满的条件 解析 循环队列队满的条件(CQ.rear+1)%maxsize=CQ.front。5.顺序栈 S 中 top 为栈顶指针，指向栈顶元素所在的位置，elem 为存放栈的数
13、组，则元素 e 进栈操作的主要语句为_（分数：2.00）A.elemtop=e;s.top=s.top+1;B.elemtop+1=e;s.top=s.top+1;C.top=s.top+1;s.elemtop+1=e;D.top=s.top+1;s.elemtop=e; 解析：考点 栈的存取时指针的修改 解析 栈的存取时指针的修改。6.设一个栈的输入序列是 a，b，c，d，则所得到的输出序列(输入过程中允许出栈)不可能出现的是_（分数：2.00）A.a，b，c，dB.c，d，a，b C.d，c，b，aD.a，b，d，c解析：考点 元素的进栈操作 解析 元素的进栈操作。7.若二叉树(如下图所示
14、)采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，最合适的遍历方法是_ （分数：2.00）A.先序遍历 B.中序遍历C.后序遍历D.按层次遍历解析：考点 二叉树的先、中、后序遍历算法 解析 二叉树的先序遍历用递归方法完成，第一步将根结点的左右子树交换，第二步在左子树中递归调用交换函数，第三步在右子树中递归调用交换函数。因此，采用先序遍历的方法最合适。8.除根结点外，树上每个结点_（分数：2.00）A.可有一个孩子、任意多个双亲B.可有任意多个孩子、任意多个双亲C.可有任意多个孩子、一个双亲 D.只有一个孩子、一个双亲解析：考点 本题主要考查的是树的结点间关系 解析 除根结点外，树上每
15、个结点可有任意多个孩子、一个双亲。9.设有二维数组 （分数：2.00）A.B. C.D.解析：考点 总结根据矩阵存储数据的规律 解析 总结根据矩阵存储数据的规律，对角线上的元素第i，i个元素的元素值为(i+2)(i+1)/2。10.从 V 1 出发，对下图按广度优先搜索遍历，则可能得到的一种顶点序列为_ （分数：2.00）A.V1V2V3V4V5V6B.V1V3V6V4V5V2C.V1V5V2V3V6V4D.V1V2V3V5V6V4 解析：考点 图的广度优先遍历 解析 图的广度优先遍历算法。11.设有无向图 G=(V，E)和 G“=(V“，E“)，如果 G“为 G 的生成树，则下面说法不正确的
16、是_（分数：2.00）A.G“为 G 的连通分量 B.G“为 G 的子图C.G“为 G 的极小连通子图且 V“=VD.G“是 G 的无环子图解析：考点 无向图 解析 一个连通图的生成树，是含有该连通图的全部顶点的一个极小连通子图，但不一定含有全部的边，也就是不满足连通分量的定义。因此不能说 G“为 G 的连通分量。12.设图的邻接链表如下图所示，则该图的边的数目是_ （分数：2.00）A.4B.5 C.10D.20解析：考点 图邻接表表示时，边数的求取 解析 图邻接表表示时边的条数=(邻接表结点个数)/2。13.采用二分查找法，若当前取得的中间位置 MID 的元素值小于被查找值，则表明待查元素
17、可能在表的后半部分，下次查找的起始位置通常应_（分数：2.00）A.从 MID/2 位置开始B.从 MID 位置开始C.从 MID+1 位置开始 D.从 MID-1 位置开始解析：考点 二分查找算法 解析 二分查找算法，由题意可知，当判定在后半部分时，应该将 MID+1 作为起始位置，再进行二分查找。14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_（分数：2.00）A.插入排序 B.快速排序C.冒泡排序D.选择排序解析：考点 插入排序算法 解析 插入排序算法，第一趟排序后，任一元素都不能确定其最终位置。15.若对序列(25，91，23，53，1 6，34，69，39，22
18、)进行一趟排序后所得到的结果为(22，16，23，25，53，34，69，39，91)，则该排序可能使用的方法是_（分数：2.00）A.插入排序B.冒泡排序C.快速排序 D.选择排序解析：考点 排序算法 解析 快速排序算法的步骤。二、填空题(总题数：13，分数：26.00)16.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为 1。 （分数：2.00）解析：图形结构 考点 图形结构的定义 解析 在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为图形结构。17.设有指针 head 指向不带表头结点的单链表，用 next 表示结点的一个链域，指针 q
19、指向与链表中结点同类型的一个新结点。现要将指针 q 指向的结点插入表中，使之成为第一个结点，则所需的操作为“q-next=head;”和“ 1”。 （分数：2.00）解析：head=p 考点 单链表元素插入操作的指针修改 解析 将指针 p 指向的结点插入表中，使之成为第一个结点，则所需的操作为“pNext=head;”和“head=p”。18.对顺序表执行删除操作，其删除算法的平均时间复杂性为 1。 （分数：2.00）解析：O(n-1)/2 考点 顺序表执行删除操作的时间复杂度 解析 对顺序表执行删除操作，其删除算法的平均时间复杂性为 O(n-1)/2。19.在具有 n 个单元且采用顺序存储的
20、循环队列中，队满时共有 1 个元素。 （分数：2.00）解析：n-1 考点 循环队列的元素存储 解析 在具有 n 个单元且采用顺序存储的循环队列中，队满时共有 n-1 个元素。20.在循环队列中，存储空间为 0(n-1)，设队头指针 front 指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么队满标志为 front=(rear+1)%n，队空标志为 1。 （分数：2.00）解析：rear=front 考点 循环队列的队空标志 解析 循环队列的队空标志为 rear=front。21.设有二维数组 int M1020，每个元素(整数)占 2 个存储单元，数组的起始地址为 2000，元素 M6
21、10的存储位置为 1，M820的存储位置为 2。 （分数：2.00）解析：2260 2360 考点 二维数组存储位置的计算 解析 对于 m*n 的二维数组，根据存储地址计算公式 Loc(i,j)=Loc(0,0)+(n*i+j)*size;Loc(6,10)=2000+(206+10)2=2260;Loc(8,20)=2000+(208+20)2=2360。22.若用后序遍历法遍历下图所示的二叉树，其输出序列为 1。 （分数：2.00）解析：DBFHGECA 考点 后序遍历算法 解析 二叉树的后序遍历算法遍历顺序是：左子树、右子树、根结点。23.对于一棵具有 m 个结点的二叉树，当进行链接存储
22、时，其二叉链表中的指针域的总数为 1 个，其中 2个用于链接孩子结点。 （分数：2.00）解析：2m m-1 考点 本题主要考查的二叉树的二叉链表存储 解析 二叉树中有 m 个结点，用二叉链表表示则有 2m 个指针域；由于只有一个根结点，所以相对于相应的父结点，有 m-1 个孩子结点，即有 m-1 个指针域用于链接孩子结点。24.一个具有 20 个顶点的完全无向图中有 1 条边。 （分数：2.00）解析：190 考点 无向完全图的定义 解析 个具有 n 个顶点的完全无向图中有有 n(n-1)/2 条边，所以对于 20 个顶点的无向完全图共有20(20-1)/2=190。25.对于具有 n 个元
23、素的数据序列，采用二叉排序树查找，其平均查找长度为 1。 （分数：2.00）解析：1+log 2 n 考点 二叉排序树的平均查找长度 解析 采用二叉排序树查找，其平均查找长度 1+log 2 n。26.采用折半查找方法进行查找的数据序列应为 1 且 2。 （分数：2.00）解析：顺序存储 有序 考点 折半查找方法对数据序列的要求 解析 采用折半查找方法进行查找的数据序列应为顺序存储且有序。27.对 20 个元素进行冒泡排序时，第一趟排序的比较次数为 1。 （分数：2.00）解析：19 考点 冒泡排序算法 解析 对包含 20 个元素进行冒泡排序，第一趟排序的比较次数是 20-1=19。28.冒泡
24、排序最好的时间复杂度为 1，平均时间复杂度为 2，是一种 3 的排序算法。 （分数：2.00）解析：O(n) O(n 2 ) 稳定 考点 冒泡排序最好情况下的比较次数 解析 冒泡排序最好的时间复杂度为 O(n 2 )，平均时间复杂度为 O(n 2 )，是一种稳定的排序算法。三、应用题(总题数：5，分数：30.00)29.二叉树如下图所示，分别写出其先序遍历、中序遍历和后序遍历的结点访问序列。 （分数：6.00）解析：先序遍历：ABDEFC。 中序遍历：BEFDAC。 后序遍历：FEDBCA。 考点 二叉树的先序、中序、后序遍历算法30.如下图所示，输入元素为 A，B，C，在栈的输出端得到一个输
25、出序列 ABC，试写出在栈的输入端三个可能的输入序列。 （分数：6.00）解析：ABC、ACB、BAC、CBA、CAB，写出任意 3 个序列即可。考点 栈的存取规则：先进后出31.已知连通网的邻接矩阵 （分数：6.00）解析：联通网和最小生成树分别见下图。 联通网32.已知一组键值序列(30，45，35，42，53，60，34，22)，试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。 （分数：6.00）解析：初始 30 45 35 42 53 60 34 22 i=2 30 45 35 42 53 60 34 22 i=3 30 35 45 42 53 60 34 22 i=4 30
26、 35 42 45 53 60 34 22 i=5 30 35 42 45 53 60 34 22 i=6 30 35 42 45 53 60 34 22 i=7 30 34 35 42 45 53 60 22 i=8 22 30 34 35 42 45 53 60 考点 直接插入排序算法33.试写出下图的拓扑序列。 （分数：6.00）解析：有以下 3 个拓扑序列： v 1 v 3 v 2 v 5 v 6 v 4 v 1 v 3 v 6 v 2 v 5 v 4 v 3 v 6 v 1 v 2 v 5 v 4 考点 拓扑排序的处理四、算法设计题(总题数：2，分数：14.00)34.现二叉树用二叉
27、链表表示，试编写一算法求解一棵二叉树的叶子总数(可采用递归算法描述)。 （分数：7.00）_正确答案：()解析：void countleaf(bitreptr t,int * count) if(t!=NULL) if(t-lchild=NULL) countleaf(t-lchild,count); countleaf(t-rchild,count); 35.设某单链表中存在多个结点，其数据值均为 D，试编写一算法统计该类结点的个数。 （分数：7.00）_正确答案：()解析：int count_lklist(lklist head) p=head; j=0 while(p-next!=NULL) if p-data=D j+; /*j 增加 1*/ p=p-next; returu(j)
