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