《2020年1月全国自考数据结构导论试题及答案解析.docx》由会员分享，可在线阅读，更多相关《2020年1月全国自考数据结构导论试题及答案解析.docx（4页珍藏版）》请在三一文库上搜索。
1、精品自学考 料推荐全国 2018 年 1 月高等教育自学考试数据结构导论试题课程代码： 02142一、单项选择题(本大题共15 小题，每小题2 分，共 30 分 )在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.数据结构中所定义的数据元素，是用于表示数据的（）A. 最小单位B.最大单位C.基本单位D.不可分割的单位2.数据的四种基本存储结构是指（）A. 顺序存储结构、索引存储结构、直接存储结构、倒排存储结构B顺序存储结构、索引存储结构、链式存储结构、散列存储结构C顺序存储结构、非顺序存储结构、指针存储结构、树型存储结构D.顺序存储结
2、构、链式存储结构、树型存储结构、图型存储结构3.对于长度为n 的顺序表执行删除操作，则其结点的移动次数（）A. 最少为 0，最多为nB.最少为 1，最多为nC.最少为 0，最多为n-1D.最少为 1，最多为n-14.在一个单链表中，若p 所指结点是q 所指结点的前驱结点，则删除结点q 的正确操作是（）A. p-next=qB. p-next=q-nextC. p=q-nextD. p-next=q-next-next5.有关栈的描述，正确的是（）A. 栈是一种先进先出的特殊的线性表B.只能从栈顶执行插入、删除操作C.只能从栈顶执行插入、栈底执行删除D.栈顶和栈底均可执行插入、删除操作6.二维数
3、组A 10 20采用按行为主序的存储方式，每个元素占4 个存储单元， 若 A 0 0的存储地址为300，则 A 10 10的地址为（）A.700B.1120C.1180D.11407.关于二叉树性质的描述，正确的是（）1精品自学考 料推荐A. 二叉树结点的个数可以为0B.二叉树至少含有一个根结点C.二叉树若存在两个结点，则必有一个为根，另一个为左孩子D.二叉树若存在三个结点，则必有一个为根，另两个分别为左、右孩子8.具有 4 个结点的二叉树可有（）A.4 种形态B.7 种形态C.10 种形态D.11 种形态9.若采用邻接表存储结构，则图的深度优先搜索类似于二叉树的（）A. 先根遍历B.中根遍历
4、C.后根遍历D.层次遍历10.具有 n 个顶点的无向图，若要连通全部顶点，至少需要（）A. （ n-1）条边B. n 条边C. n(n-1) 条边D. n(n-1)/2条边11.下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A. 集合B.线性结构C.树形结构D.图形结构12.闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A. 同义词之间发生冲突引起的B.非同义词之间发生冲突引起的C.同义词与非同义词之间发生冲突引起的D.散列地址“溢出”引起的13.ISAM 文件组织方式是一种（）A. 专门适用于磁带的存取方法B.专门适用于磁盘的存取方法C.专门适用于光盘的存取方法
5、D.可适用于磁带、磁盘、光盘等多用途的存取方法14.当待排序序列中记录数较多时，速度最快的排序方法是（）A. 冒泡排序法B.快速排序法C.堆排序法D.归并排序法15.若对序列（ 15， 30， 26， 22， 69， 50， 53， 87）采用二路归并法排序，则进行一趟归并后产生的序列为（）A.15 ， 22， 26， 30， 50， 53， 69， 87B.15， 30， 22， 26， 50， 69， 53， 87C.15， 26， 30， 22， 50， 69， 53， 87D.15， 26， 22， 30， 50， 53， 69， 87二、填空题 (本大题共 13 小题，每小题2 分，
6、共 26分 )2精品自学考 料推荐请在每小题的空格中填上正确答案。错填、不填均无分。16.数据表示和 _ 是程序设计者所要考虑的两项基本任务。17.一个算法通常可从正确性、易读性、健壮性和 _ 等四个方面评价、分析。18. 对长度为 n 的顺序表执行删除操作，其删除算法在最坏情况下的时间复杂性为_ 。19.串是一种特殊的线性表，串常见的存储结构有顺序存储和_ 两种方式。20.我们通常把队列中允许插入的一端称为_ 。21.二维数组在机器级的具体实现，通常均采用_ 存储结构。22.深度为 k 的满二叉树其叶子结点个数共有_ 个。23.二叉树通常采用_ 两种存储结构表示。24.若一个完全无向图具有n
7、 条边，则该图的顶点个数为_ 。25.查找表的逻辑组织结构实际上是_ 结构。26.对于具有n 个元素的数据序列，采用顺序查找法，其平均查找长度为_ 。27.若构成索引文件的索引表有序而主文件无序，则该索引文件称为_ 文件。28.对于具有n 个元素的有序序列，若采用冒泡排序，最多需要进行_ 趟起泡。三、应用题 (本大题共 5 小题，每小题6 分，共 30 分 )29.试采用类C 语言，给出二叉树的二叉链表结构描述。30.试用 Prim 算法构造题30 图的最小生成树，要求分步给出构造过程。题 30 图31.请按照数列 28 ， 45， 33， 12， 37，20， 18，55 的先后插入次序，生成一棵二叉排序树。32.已知一组键值序列（33， 37， 26，43，55，67， 42，38），试采用堆排序法对该组序列作升序排序，给出建立的初始堆，以及第一次输出堆元素后筛选调整的堆。33.已知一组键值序列（22， 24， 26，25，27，29， 21，28），试给出采用直接插入排序法对该组序列作升序排序的每一趟结果。3精品自学考 料推荐四、设计题 (本大题共 2 小题，每小题7 分，共 14 分 )34.试编写一个函数，以读取单链表的第i 个元素。35.若二叉树采用二叉链表表示，试给出二叉树先根遍历的非递归算法描述。4