[自学考试密押题库与答案解析]数据结构自考题模拟13

1、自学考试密押题库与答案解析数据结构自考题模拟13自学考试密押题库与答案解析数据结构自考题模拟13数据结构自考题模拟13一、单项选择题问题:1. 为便于判别有向图中是否存在回路，可借助于A.广度优先搜索算B.最小生成树算法C.最短路径算D.拓扑排序算法答案:D问题:2. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是A.pnext=headB.pnextNext=headC.pnext=NULLD.p=head答案:A解析 在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。故由题目中此单循环锚表的头指针为

2、head，指针p指向尾结点，可得pnext=head。问题:3. 设有6个结点的无向图，该图至少应有 条边才能确保是一个连通图。A.5B.6C.7D.8答案:A问题:4. 若有序表的关键字序列为(b,c,d,e,f,g,q,r,s,t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为A.f,c,bB.f,d,bC.g,c,bD.g,d,b答案:A问题:5. 以下有关数据结构的叙述，正确的是A.线性表的线性存储结构优于链式存储结构B.二叉树的第i层上有2i-1个结点，深度为K的二叉树上有2k-1个结点C.二维数组是其数据元素为线性表的线性表D.栈的操作方式是先进先出答案:C问题:6.

3、设rear是指向非空带头结点的循环单链表的尾指针，则删除起始结点的操作可表示为A.s=rear;B.rear=rearnext; rear=rearnext; free(rear); free(s); C.rear=rearnextnext;D.s=rearnextnext; free(rear); rearnextnext=snext; free(s); 答案:D问题:7. 采用分治法进行排序的方法是A.快速排序B.插入排序C.堆排序D.希尔排序答案:A问题:8. 对长度为n的关键字序列进行堆排序的空间复杂度为A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)答案:B解析

4、由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为0(1)，但它是不稳定的。问题:9. 在桶排序中，其平均时间复杂度是A.O(1)B.O(n)C.O(n2)D.O(1gn)答案:B问题:10. 森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1，n2，n3，n4，那么当把森林T转换成一棵二叉树后，其根结点的左孩子上有 个结点。A.n1-1B.n1C.n1+n2+n3D.n2+n3+n4答案:A问题:11. 数据结构是A.一种数据类型B.数据的存储结构C.一组性质相同的数据元素的集合D.相互之间存在一种或多种特定关系的数据元素的集合答案:D问

5、题:12. 两个字符串相等的条件是A.串的长度相等B.含有相同的字符集C.都是非空串D.串的长度相等且对应的字符相同答案:D问题:13. 邻接表存储结构下图的深度优先遍历算法结构类似于于叉树的A.先序遍历B.中序遍历C.后序遍历D.按层遍历答案:A问题:14. 如果我们采用二分查找法查找一个长度为n的有序表，则查找每个元素的平均比较次数 对应的判定树的高度(假设树高h2)。A.大于B.小于C.等于D.无法确定答案:B问题:15. 一个具有N个顶点的有向图最多有 条边。A.N(N-1)/2B.N(N-1)C.N(N+1)D.N(N+1)/2答案:B二、填空题问题:1. 在线性表的顺序存储中，元素

6、之间的逻辑关系是通过_决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_决定的。答案:相邻位置 链接指针问题:2. 对于一个二维数组Amn，若按行序为主序存储，则任一元素Aij相对于A00的地址为_。答案:ij+i全元素位置问题:3. 若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是_的。答案:稳定问题:4. 对于数组，通常具有的基本操作有_种，它们分别是_。答案:两 查找和修改问题:5. 如果我们定义一个长度为N的串空间，则它最多能放_个字符。答案:N1问题:6. 已知广义表A=(a,b,c)，(d,e,f)，则运算head(head(tail(tail(A)=_。答

7、案:e问题:7. 若对关键字序列(43,02,80,48,26,57,15,73,21,24,66)进行一趟增量为3的希尔排序，则得到的结果为_。答案:15,02,21,24,26,57,43,66,80,48,73问题:8. 无向图的邻接矩阵是_，并且主对角线上的元素的值为_。答案:对称零问题:9. 散列函数的作用是：_。答案:压缩待处理的下标范围，待处理的|u|个值减少到m个值，从而降低空间开销问题:10. 在按照顺序存储方式存储的数组中，元素aij的存储地址应该是数组的_加上排在aij前面的元素所占用的单元数。答案:基地址三、解答题问题:1. 对序列(48,37,63,96,22,31,

8、50,55,11)进行升序的堆排序，写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆： 第1趟： 第2趟： 答案:初始堆：(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)。

9、 2.答案:head(tail(L1)3.答案:head(head(tail(head(L2)(1)画出对表长为13的有序顺序表进行二分查找的判定树； (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99)，写出在该序列中二分查找37时所需进行的比较次数。 4.答案:5.答案:3四、算法阅读题假设学生成绩按学号增序存储在带头结点的单链表中，类型定义如下： typedef struct Node int id; /*学号*/ int score; /*成绩*/ srruct Node*next; LNode,*LinkList; 阅读算法f31，并

10、回答问题： (1)设结点结构为，成绩链表A和B如图所示，画出执行算法f31(A,B)后A所指的链表； (2)简述算法f31的功能。 void f31(LinkList A,LinkList B) LinkList p,q; p=Anext; q=Bnext; while(p else if(pidqid) q=qnext; else if(pscore60) if(qscore60) pscore=qscore; else pscore=60; p=pnext; q=qnext; 1.答案:2.答案:对于表A中成绩低于60的学生，如果在表B中也有成绩记录，则将表A中的成绩修改为其在表B中的成绩

11、；但若其在表B中的成绩高于60分，则只改为60分。阅读下列算法，并回答问题： (1)无向图G如图所示，写出算法f30( void DFS(Graph*g,int i); /*从顶点vi出发进行深度优先搜索，访问顶点vj时置visitedj为1*/ int f30(Graph*g) int i,k; for(i=0;igN;I+) 答案:34.答案:返回无向图g中连通分量的个数。五、算法设计题问题:1. 对一个有t个非零值元素的mn矩阵，用B0.t,1.3的数组来表示，其中第0行的三个元素分别是m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列

12、为其元素量，对这样的表示法，试编写一个算法确定任意一个元素Aij的位置，并考虑若修改其元素值须用多少时间?(设B中第1列原行号是递增的)答案:分析题意可得其算法思想为： 首先可在数组B中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的Aij，原先就具有非零值。从而可将算法描述为： lorte(B,t,i,j,v) /*确定任意一个元素Aij的位置*/ datatype B;/*B的杆标为0.t和1.3*/ int t,i,j; float v; datatype A; /*A的下标为1.m和1.n，A表示mn矩阵*/ int p; p=1; while(Bp1!=1)(p=t) P+; if(pt)printf Chasn