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)