2022年7月自考数据结构试题真题.docx

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

1、精品学习资源全国2007年1月高等训练自学考试数据结构试卷课程代码： 02331一、单项挑选题 本大题共 15 小题，每道题2 分，共 30 分）在每道题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内；错选、多项或未选均无分；1抽象数据类型的三个组成部分分别为=2006n+6nlogn+29logn,就其时间复杂度为B On2C OnlognD Olog n3如线性表的插入和删除操作频繁地在表头或表尾位置进行，就更相宜采纳的储备结构为）A 无头结点的双向链表B 带尾指针的循环链表C无头结点的单链表D 带头指针的循环链表4上溢现象通常显现在 的返回值为串 t在串 s中首

2、次显现的位置，就能求得串abcacba的操作序列为 ； substr s2,s,indexs,t1,1 ；strcats1,s2；B substr s1,s,7,indexs,t1 ； substr s2,s,indexs,t1,1 ；strcats2,s1；C substrs1,s,6,indexs,t2 ； substrs2,s,indexs,t2,3 ； strcats1,s2；D substrs1,s,6,indexs,t2 ； substrs2,s,indexs,t2,3 ；strcats2,s1；6. 对广义表 L=a,b,c,d,e,f 执行 headtailheadtailL

3、操作的结果是 D e,f 欢迎下载精品学习资源7. 已知一棵完全二叉树有64个叶子结点，就该树可能达到的最大深度为A 7B 8C 9D 108. 如一棵二叉树有11个叶子结点，就该二叉树中度为2的结点个数是A 10B 11）C 12D 不确定的9对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为）A 求一个顶点的邻接点B 求一个顶点的度C深度优先遍历D 广度优先遍历10如用邻接矩阵表示带权有向图，就顶点i 的入度等于矩阵中） A 第 i行非 元素之和B 第i列非 元素之和C第 i行非 元素个数D 第i列非 元素个数11对关键字序列 5， 1， 4， 3， 7， 2， 8，6）进行快速排

4、序时，以第一个元素5为基准的一次划分的结果为）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以下二叉树中，不 平稳的二叉树是 ）13以下序列中，不 构成堆的是 ） 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

5、 一个记录B 一组记录C一个类型D 一个文件15稀疏索引是指在文件的索引表中）A 为每个字段设一个索引项B 为每个记录设一个索引项C为每组字段设一个索引项D 为每组记录设一个索引项二、填空题 本大题共 10 小题，每道题 2 分，共 20 分） 请在每道题的空格中填上正确答案；错填、不填均无分；16. 链式储备结构的特点是借助 来表示数据元素之间的规律关系；17. 假设带头结点的非空单循环链表中仅设尾指针L，就在第 1个结点之前插入指针 s所指结点的语句依次是；18. 无表头结点的链队列Q为空的条件是；19. 不含任何字符的串称为；20. 假设按行优先次序将一个20阶的三对角矩阵 A 压缩储备

6、在一维数组 Q中，其中 Q0 存放矩阵的第 1个元素 a1,1，那么矩阵元素 a3,4在Q中的储备位置 k=； 21前序序列和中序序列不 相同的二叉树的特点是 ；22在含有 n个顶点的连通图中，任意两个不同顶点之间的简洁路径的最大长度为 ；23用排序方法对关键字序列20， 25， 12， 47， 15， 83， 30， 76）进行排序时， 前三趟排序的结果为：20， 12， 25， 15， 47， 30， 76，8312， 20， 15， 25， 30， 47， 76，8312， 15， 20， 25， 30， 47， 76，8324. 哈希表常用的两类解决冲突的方法是 和；25. 倒排文件和

7、多重表文件的主要区分在于 的结构不同；三、解答题 本大题共 4 小题，每道题 5 分，共 20 分）26. 已知主串为 ccgcgccgcgcbcb，模式串为 cgcgcb；下表所列为根据朴实的串匹配算法进行的前两趟匹配；请连续完成余下各趟匹配，直至终止；欢迎下载精品学习资源27已知带权图 G如下列图，画出图G的一棵最小生成树；欢迎下载精品学习资源28对于直接插入排序，希尔排序，冒泡排序，快速排序，直接挑选排序，堆排序和归并排序等排序方法，分别写出：1 ）平均时间复杂度低于 On2）的排序方法；2 ）所需帮助空间最多的排序方法；3 ）最好情形和最坏情形下的时间复杂度相同的排序方法；1 ）2 ）

8、3 ） 29已知一棵线索化的二叉排序树如下列图；1 ）说明该树的线索化是基于何种遍历次序的；2 ）在该树中插入元素值为53的结点并修改相应线索，画出修改之后的树；1 ）2 ）四、算法阅读题 本大题共 4 小题，每道题5 分，共 20 分） 30假设线性表采纳次序储备结构，表中元素值为整型；阅读算法f30，并回答以下问题：, 写出执行算法 f30 后的L ； int i,j,k ；k=0 ；fori=0 ；ilength ；i+ forj=0 ；jdatai.=L-dataj；j+ ；欢迎下载精品学习资源ifj=k ifk.=iL-datak=L-datai；k+ ；L-length=k ；12

9、31. 阅读算法 f31, 并回答以下问题：1 ）设队列 Q=1 ， 3， 5，2， 4， 6）；写出执行算法f31后的队列 Q；DataTypee；if .QueueEmptyQ e=DeQueueQ ；f 31Q ；EnQueueQ,e；1232. 已知树的储备结构为孩子兄弟链表，其类型定义如下： typedef struct CSTNode char data；struct CSTNode leftmostchild ,* rightsibling ； CSTNode, *CSTree ；阅读函数 f32, 并回答以下问题： 的返回值； int c ；CSTree p；if .T-lef

10、tmostchild return 1；else c=0；forp=T-leftmostchild；p；p=p-rightsiblingc+=f32p ；return c；1233. 已知数组 R1.p-1 中的元素序列为一个大根堆，函数AdjustR,p 将R1.p 重新调整为一个大根堆；1 ）在函数 Adjust 的空缺处填入适当内容，使其成为一个完整的函数； 的功能；void AdjustSeqList R,int p int i,j ；RecType temp=Rp ；i=p ；j=i/2 ；whilej=1& Rj.key Ri=Rj；i=j ；Ri= ；void f33SeqList R,int n欢迎下载精品学习资源 int k ；fork=2 ；k AdjustR,k ； 12五、算法设计题 ；欢迎下载精品学习资源欢迎下载