2022年全国自学考试数据结构试卷 .pdf

《2022年全国自学考试数据结构试卷 .pdf》由会员分享，可在线阅读，更多相关《2022年全国自学考试数据结构试卷 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、全国 20XX 年 1 月高等教育自学考试数据结构试题课程代码： 02331 一、单项选择题（本大题共15 小题，每小题2 分，共 30 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1抽象数据类型的三个组成部分分别为（A）A数据对象、数据关系和基本操作B数据元素、逻辑结构和存储结构C数据项、数据元素和数据类型D数据元素、数据结构和数据类型2若算法中语句的最大频度为T(n)=2006n+6nlogn+29log2n,则其时间复杂度为（C）AO(logn) BO(n) CO(nlogn) DO(log2n) 3若线性表的插入和删除操

2、作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为（B）A无头结点的双向链表B带尾指针的循环链表C无头结点的单链表D带头指针的循环链表4上溢现象通常出现在（A）A顺序栈的入栈操作过程中B顺序栈的出栈操作过程中C链栈的入栈操作过程中D链栈的出栈操作过程中5已知串s= aabacbabcaccab，串 t1= abc,串 t2= cba,函数 index(s,t)的返回值为串t 在串 s中首次出现的位置，则能求得串abcacba的操作序列为（C）Asubstr (s1,s,6,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s1,s2); Bsu

3、bstr (s1,s,7,index(s,t1); substr (s2,s,index(s,t1),1);strcat(s2,s1); Csubstr(s1,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s1,s2); Dsubstr(s1,s,6,index(s,t2); substr(s2,s,index(s,t2),3);strcat(s2,s1); 6对广义表L=(a,b),(c,d),(e,f) 执行 head(tail(head(tail(L) 操作的结果是（D）Ad Be C(e) D(e,f ) 7已知一棵完全二叉树有6

4、4 个叶子结点，则该树可能达到的最大深度为（B）A7 B8 C9 D 10 8若一棵二叉树有11 个叶子结点，则该二叉树中度为2 的结点个数是（A）A10 B11 C12 D不确定的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 7 页9对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为（B）A求一个顶点的邻接点B求一个顶点的度C深度优先遍历D广度优先遍历10若用邻接矩阵表示带权有向图，则顶点i 的入度等于矩阵中（D）A第 i 行非 元素之和B第 i 列非 元素之和C第 i 行非 元素个数D第 i 列非 元素个数11对关键字序列

5、（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5 为基准的一次划分的结果为（C）A （1，2，3，4，5，6，7，8）B （1，4，3，2，5，7，8，6）C （2，1，4，3，5，7，8，6）D （8，7，6，5，4，3，2，1）12下列二叉树中，不平衡的二叉树是（C）13下列序列中，不构成堆的是（D）A （1，2，5，3，4，6，7，8， 9，10）B （10，5，8， 4，2，6，7，1，3）C （10，9，8， 7，3，5，4，6，2）D （1，2，3，4，10，9，8，7，6，5）14主关键字能唯一标识（A）A一个记录B一组记录C一个类型D一个文件15稀疏索引是指在文

6、件的索引表中（D）A为每个字段设一个索引项B为每个记录设一个索引项C为每组字段设一个索引项D为每组记录设一个索引项精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 7 页二、填空题（本大题共10 小题，每小题2 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16链式存储结构的特点是借助_指针 _来表示数据元素之间的逻辑关系。17假设带头结点的非空单循环链表中仅设尾指针L，则在第 1 个结点之前插入指针s所指结点的语句依次是_s-next=L-next-next_ ；_L-next-next=s_ 。18无表头结点的链

7、队列Q 为空的条件是_Q.front=NULL_ 。(或 Q-front=NULL) 19不含任何字符的串称为_ _空串 _。20假设按行优先顺序将一个20 阶的三对角矩阵A 压缩存储在一维数组Q 中，其中Q0存放矩阵的第1 个元素 a1,1，那么矩阵元素a3,4在 Q 中的存储位置k=_ _7_。21 前序序列和中序序列不相同的二叉树的特征是_树中至少含有一个具有非空右子树的结点_。 （或树中存在具有右孩子的结点）22在含有 n 个顶点的连通图中，任意两个不同顶点之间的简单路径的最大长度为_n-1_。23用 _冒泡 _排序方法对关键字序列（20，25，12， 47，15，83， 30，76）

8、进行排序时，前三趟排序的结果为：20， 12，25，15， 47，30，76，83 12， 20，15，25， 30，47，76，83 12， 15，20，25， 30，47，76，83 24哈希表常用的两类解决冲突的方法是开放定址法和_拉链法 _。25倒排文件和多重表文件的主要区别在于次关键字索引的结构不同。三、解答题（本大题共4 小题，每小题5 分，共 20 分）26已知主串为 ccgcgccgcgcbcb，模式串为 cgcgcb 。下表所列为按照朴素的串匹配算法进行的前两趟匹配。请继续完成余下各趟匹配，直至结束。c c g c g c c g c g c b c b i=0 c g 匹配

9、失败时 j=1 i=1 c g c g c b 匹配失败时 j=5 i=2 c 匹配失败时 j=0 i=3 c g c g 匹配失败时 j=3 i=4 c 匹配失败时 j=0 i=5 c g 匹配失败时 j=1 i=6 c g c g c b 匹配成功精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 7 页27已知带权图G 如图所示，画出图G 的一棵最小生成树。去掉： (A,B),(A,D),(C,F),(C,E),(C,H),(D,E),(E,H) 保留： (A,C),(B,C),(B,F),(F,H),(C,D),(D,K),(K,E

10、), 28对于直接插入排序，希尔排序，冒泡排序，快速排序，直接选择排序，堆排序和归并排序等排序方法，分别写出：（1）平均时间复杂度低于O（n2）的排序方法；（2）所需辅助空间最多的排序方法；（3）最好情况和最坏情况下的时间复杂度相同的排序方法。（1）希尔排序、快速排序、堆排序和归并排序（2）归并排序（3）直接选择排序、堆排序和归并排序29已知一棵线索化的二叉排序树如图所示。（1）说明该树的线索化是基于何种遍历次序的；（2）在该树中插入元素值为53 的结点并修改相应线索，画出修改之后的树。（1）中序（2）53精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

11、-第 4 页，共 7 页四、算法阅读题（本大题共4 小题，每小题5 分，共 20 分）30假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f 30，并回答下列问题：（1）设顺序表L=(3,7,3,2,1,1,8,7,3), 写出执行算法f 30 后的 L; （2）简述算法f 30 的功能。void f 30(SeqList *L) int i,j,k; k=0; for(i=0;ilength;i+) for(j=0;jdatai!=L-dataj;j+); if(j=k) if(k!=i)L-datak=L-datai; k+; L-length=k; (1) L=(3,7,2,1,8

12、) (2) 删除顺序表L 中的重复元素31阅读算法f 31,并回答下列问题：（1）设队列Q=（ 1，3，5，2，4，6） 。写出执行算法f 31 后的队列Q; （2）简述算法f 31 的功能。void f 31(Queue *Q) DataType e; if (!QueueEmpty(Q) e=DeQueue(Q); f 31(Q); EnQueue(Q,e); (1) Q=(6,4,2,5,3,1) (2) 逆置队列Q精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 7 页32已知树的存储结构为孩子兄弟链表，其类型定义如下：typed

13、ef struct CSTNode char data; struct CSTNode leftmostchild ,*rightsibling; CSTNode, *CSTree; 阅读函数f 32,并回答下列问题：（1）对于如图所示树，写出函数调用f 32(T) 的返回值；（2）简述树T 非空时函数f 32 返回值的含义。int f32(CSTree T) int c; CSTree p; if (!T-leftmostchild) return 1; else c=0; for(p=T-leftmostchild;p;p=p-rightsibling) c+=f32(p); return

14、 c; (1) 5 (2) 树 T 的叶子结点个数33已知数组R1.p-1 中的元素序列为一个大根堆，函数 Adjust(R,p) 将 R1.p 重新调整为一个大根堆。（1）在函数Adjust 的空缺处填入适当内容，使其成为一个完整的函数；（2）简述函数f33(R,n) 的功能。void Adjust(SeqList R,int p) int i,j; RecType temp=Rp; i=p; j=i/2; while(j=1& Rj.keytemp.key) Ri=Rj; i=j; j=i/2; (或 j=j/2 ) 精选学习资料 - - - - - - - - - 名师归纳总结 - -

15、- - - - -第 6 页，共 7 页 Ri= temp; void f33(SeqList R,int n) int k; for(k=2;k=n;k+) Adjust(R,k); (1)(2) 从数组的前端开始，通过逐个插入元素建堆五、算法设计题（本大题10 分）34已知有向图的邻接表表示的形式描述如下：#define MaxNum 50 /图的最大顶点数typedef struct ArcNode int adjvex; /邻接点域struct ArcNode *nextArc; /链域 ArcNode; /弧结点类型typedef struct char vertex; /顶点域ArcNode *firstArc; /弧表头指针VertexNode; /顶点表结点类型typedef struct VertexNode adjListMaxNum; /邻接表int n,e; /图中当前的顶点数和边数ALGraph; /邻接表类型按以下函数原型编写算法，求有向图G 中第 i 顶点的度，并写出算法的时间复杂度。int f34(ALGraph *G ,int i); 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 7 页