1、数据结构自考题-12 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.为便于判别有向图中是否存在回路，可借助于 U /U A.广度优先搜索算 B.最小生成树算法 C.最短路径算 D.拓扑排序算法（分数：2.00）A.B.C.D.2.在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是 U /U A.pnext=head B.pnextNext=head C.pnext=NULL D.p=head（分数：2.00）A.B.C.D.3.设有 6 个结点的无向图，该图至少应有U /U条边才能确保是一个连通图。
2、 A.5 B.6 C.7 D.8（分数：2.00）A.B.C.D.4.若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为 U /U A.f,c,b B.f,d,b C.g,c,b D.g,d,b（分数：2.00）A.B.C.D.5.以下有关数据结构的叙述，正确的是 U /U A.线性表的线性存储结构优于链式存储结构 B.二叉树的第 i 层上有 2i-1个结点，深度为 K 的二叉树上有 2k-1个结点 C.二维数组是其数据元素为线性表的线性表 D.栈的操作方式是先进先出（分数：2.00）A.B.C.D.6.设 rear
3、是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为U /U A.s=rear; B.rear=rearnext; rear=rearnext; free(rear); free(s); C.rear=rearnextnext; D.s=rearnextnext; free(rear); rearnextnext=snext; free(s);（分数：2.00）A.B.C.D.7.采用分治法进行排序的方法是U /U A.快速排序 B.插入排序 C.堆排序 D.希尔排序（分数：2.00）A.B.C.D.8.对长度为 n 的关键字序列进行堆排序的空间复杂度为 U /U A.O(lo
4、g2n) B.O(1) C.O(n) D.O(n*log2n)（分数：2.00）A.B.C.D.9.在桶排序中，其平均时间复杂度是U /U A.O(1) B.O(n) C.O(n2) D.O(1gn)（分数：2.00）A.B.C.D.10.森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4，那么当把森林 T 转换成一棵二叉树后，其根结点的左孩子上有U /U个结点。 A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4（分数：2.00）A.B.C.D.11.数据结构是 U /U A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元
5、素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00）A.B.C.D.12.两个字符串相等的条件是 U /U A.串的长度相等 B.含有相同的字符集 C.都是非空串 D.串的长度相等且对应的字符相同（分数：2.00）A.B.C.D.13.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的U /U A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历（分数：2.00）A.B.C.D.14.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数U /U对应的判定树的高度(假设树高 h2)。 A.大于 B.小于 C.等于 D.无法确定（分数：2
6、.00）A.B.C.D.15.一个具有 N 个顶点的有向图最多有U /U条边。 A.N(N-1)/2 B.N(N-1) C.N(N+1) D.N(N+1)/2（分数：2.00）A.B.C.D.二、B填空题/B(总题数：10，分数：20.00)16.在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。（分数：2.00）填空项 1:_17.对于一个二维数组 Amn，若按行序为主序存储，则任一元素 Aij相对于 A00的地址为 1。（分数：2.00）填空项 1:_18.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1
7、的。（分数：2.00）填空项 1:_19.对于数组，通常具有的基本操作有_种，它们分别是_。（分数：2.00）填空项 1:_20.如果我们定义一个长度为 N 的串空间，则它最多能放 1 个字符。（分数：2.00）填空项 1:_21.已知广义表 A=(a,b,c)，(d,e,f)，则运算 head(head(tail(tail(A)= 1。（分数：2.00）填空项 1:_22.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_23.无向图的邻接矩阵是 1，并且主对角线上的元素的值为
8、 2。（分数：2.00）填空项 1:_24.散列函数的作用是： 1。（分数：2.00）填空项 1:_25.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_三、B解答题/B(总题数：2，分数：20.00)利用广义表的 head 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(head(tail(L); 分别写出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。（分数：10
9、.00）_(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时所需进行的比较次数。（分数：10.00）_四、B算法阅读题/B(总题数：2，分数：20.00)假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩
10、链表 A 和 B 如图所示，画出执行算法 f31(A,B)后A 所指的链表； （分数：10.00）_阅读下列算法，并回答问题： （分数：10.00）_五、B算法设计题/B(总题数：1，分数：10.00)26.对一个有 t 个非零值元素的 mn 矩阵，用 B0t,13的数组来表示，其中第 0 行的三个元素分别是 m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素 Aij的位置，并考虑若修改其元素值须用多少时间?(设 B 中第 1 列原行号是递增的)（分数：10.00）_数据结构自考题-1
11、2 答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.为便于判别有向图中是否存在回路，可借助于 U /U A.广度优先搜索算 B.最小生成树算法 C.最短路径算 D.拓扑排序算法（分数：2.00）A.B.C.D. 解析：2.在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是 U /U A.pnext=head B.pnextNext=head C.pnext=NULL D.p=head（分数：2.00）A. B.C.D.解析：解析 在单链表中，将终端结点的指针域 NULL 改为指向表头结点或开始结点，就得
12、到了单链形式的循环链表，并简单称为单循环链表。故由题目中此单循环锚表的头指针为 head，指针 p 指向尾结点，可得 pnext=head。3.设有 6 个结点的无向图，该图至少应有U /U条边才能确保是一个连通图。 A.5 B.6 C.7 D.8（分数：2.00）A. B.C.D.解析：4.若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字 b 的过程中，先后进行比较的关键字依次为 U /U A.f,c,b B.f,d,b C.g,c,b D.g,d,b（分数：2.00）A. B.C.D.解析：5.以下有关数据结构的叙述，正确的是 U /U A.线性表的线性
13、存储结构优于链式存储结构 B.二叉树的第 i 层上有 2i-1个结点，深度为 K 的二叉树上有 2k-1个结点 C.二维数组是其数据元素为线性表的线性表 D.栈的操作方式是先进先出（分数：2.00）A.B.C. D.解析：6.设 rear 是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为U /U A.s=rear; B.rear=rearnext; rear=rearnext; free(rear); free(s); C.rear=rearnextnext; D.s=rearnextnext; free(rear); rearnextnext=snext; free(s)
14、;（分数：2.00）A.B.C.D. 解析：7.采用分治法进行排序的方法是U /U A.快速排序 B.插入排序 C.堆排序 D.希尔排序（分数：2.00）A. B.C.D.解析：8.对长度为 n 的关键字序列进行堆排序的空间复杂度为 U /U A.O(log2n) B.O(1) C.O(n) D.O(n*log2n)（分数：2.00）A.B. C.D.解析：解析 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为 0(1)，但它是不稳定的。9.在桶排序中，其平均时间复杂度是U /U A.O(1) B.O(n) C.O(n2) D.O(1gn)（分数
15、：2.00）A.B. C.D.解析：10.森林 T 中有 4 棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4，那么当把森林 T 转换成一棵二叉树后，其根结点的左孩子上有U /U个结点。 A.n1-1 B.n1 C.n1+n2+n3 D.n2+n3+n4（分数：2.00）A. B.C.D.解析：11.数据结构是 U /U A.一种数据类型 B.数据的存储结构 C.一组性质相同的数据元素的集合 D.相互之间存在一种或多种特定关系的数据元素的集合（分数：2.00）A.B.C.D. 解析：12.两个字符串相等的条件是 U /U A.串的长度相等 B.含有相同的字符集 C.都是
16、非空串 D.串的长度相等且对应的字符相同（分数：2.00）A.B.C.D. 解析：13.邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的U /U A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历（分数：2.00）A. B.C.D.解析：14.如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数U /U对应的判定树的高度(假设树高 h2)。 A.大于 B.小于 C.等于 D.无法确定（分数：2.00）A.B. C.D.解析：15.一个具有 N 个顶点的有向图最多有U /U条边。 A.N(N-1)/2 B.N(N-1) C.N(N+1) D.N(N+1)/2
17、（分数：2.00）A.B. C.D.解析：二、B填空题/B(总题数：10，分数：20.00)16.在线性表的顺序存储中，元素之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。（分数：2.00）填空项 1:_ （正确答案：相邻位置 链接指针）解析：17.对于一个二维数组 Amn，若按行序为主序存储，则任一元素 Aij相对于 A00的地址为 1。（分数：2.00）填空项 1:_ （正确答案：ij+i 全元素位置）解析：18.若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是 1 的。（分数：2.00）填空项 1:_ （正确答案：稳定）解析：19.
18、对于数组，通常具有的基本操作有_种，它们分别是_。（分数：2.00）填空项 1:_ （正确答案：两 查找和修改）解析：20.如果我们定义一个长度为 N 的串空间，则它最多能放 1 个字符。（分数：2.00）填空项 1:_ （正确答案：N1）解析：21.已知广义表 A=(a,b,c)，(d,e,f)，则运算 head(head(tail(tail(A)= 1。（分数：2.00）填空项 1:_ （正确答案：e）解析：22.若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为 3 的希尔排序，则得到的结果为 1。（分数：2.00）填空项 1:_ （正确答案
19、：15,02,21,24,26,57,43,66,80,48,73）解析：23.无向图的邻接矩阵是 1，并且主对角线上的元素的值为 2。（分数：2.00）填空项 1:_ （正确答案：对称零）解析：24.散列函数的作用是： 1。（分数：2.00）填空项 1:_ （正确答案：压缩待处理的下标范围，待处理的|u|个值减少到 m 个值，从而降低空间开销）解析：25.在按照顺序存储方式存储的数组中，元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。（分数：2.00）填空项 1:_ （正确答案：基地址）解析：三、B解答题/B(总题数：2，分数：20.00)利用广义表的 he
20、ad 和 tail 操作，可从广义表 L=(a,b)，(c,d) 中分解得到原子 c，其操作表达式为 head(head(tail(L); 分别写出从下列广义表中分解得到 b 的操作表达式。 (1)L1=(a,b,c,d); (2)L2=(a),(b),(c),(d)。（分数：10.00）_正确答案：(head(tail(L1)解析：_正确答案：(head(head(tail(head(L2)解析：(1)画出对表长为 13 的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找 37 时
21、所需进行的比较次数。（分数：10.00）_正确答案：(*)解析：_正确答案：(3)解析：四、B算法阅读题/B(总题数：2，分数：20.00)假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法 f31，并回答问题： (1)设结点结构为 ，成绩链表 A 和 B 如图所示，画出执行算法 f31(A,B)后A 所指的链表； （分数：10.00）_正确答案：(*)解析：_正确答案：(对于表 A 中成绩低于 6
22、0 的学生，如果在表 B 中也有成绩记录，则将表 A 中的成绩修改为其在表 B 中的成绩；但若其在表 B 中的成绩高于 60 分，则只改为 60 分。)解析：阅读下列算法，并回答问题： （分数：10.00）_正确答案：(3)解析：_正确答案：(返回无向图 g 中连通分量的个数。)解析：五、B算法设计题/B(总题数：1，分数：10.00)26.对一个有 t 个非零值元素的 mn 矩阵，用 B0t,13的数组来表示，其中第 0 行的三个元素分别是 m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意
23、一个元素 Aij的位置，并考虑若修改其元素值须用多少时间?(设 B 中第 1 列原行号是递增的)（分数：10.00）_正确答案：(分析题意可得其算法思想为： 首先可在数组 B 中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的 Aij，原先就具有非零值。从而可将算法描述为： lorte(B,t,i,j,v) /*确定任意一个元素 Aij的位置*/ datatype B;/*B 的杆标为 0t 和 13*/ int t,i,j; float v; datatype A; /*A 的下标为 1m 和 1n，A 表示 mn 矩阵*/ int p; p=1; while(Bp1!=1) if(pt)printf Chasnt element found/n“); else while(Bp1=i)*(p=t) if(Bp1=i) else printf (“no element found/n“); /*lorte*| 显然，在本算法中可能出现的最坏情况：一是需要修改的元素位于B 中最后一行；二是 Bij先的元素值为零，而无法在 B 中查找到相应的位置。所以，在这两种情况下的时间复杂度为 0(t)。)解析：
