川农《数据结构（专科）》19年12月作业考核A

欧阳老师

四川农业大学网络教育专科考试
数据结构  试卷（课程代码  352098）本试题一共五道大题，共3页，满分100分。考试时间90分钟。
       
注意：1、答案必须填写在答题纸上，题号不清或无题号的以零分计；
2、答题前，请在答题纸上准确、清楚地填写各项目；
3、学号、考点名称、考室号、姓名、身份证号、课程代码、课程名称、培养层次等，不写、乱写及模糊不清者，答题纸作废；
4、开卷考试，若有雷同以零分计。一、单项选择题（本大题共10小题，每小题2分，共计20分）
线性表采用链式存储时，结点的存储地址（   ）
A、必须是不连续的                        B、连续与否均可
        C、必须是连续的                        D、和头结点的存储地址相连续
设计递归问题的非递归算法一般需要用到（     ）。
A、链表       B、队列                C、树                D、堆栈
在需要经常查找结点的前驱与后继的场合中，使用(      )比较合适。
A、顺序表       B、单链表        C、双向链表            D、循环链表
将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（  ）
A、O（1）      B、O（n）            C、O（m）           D、O（m+n）
若结构中的数据元素之间存在一个对应多个的关系，则该结构属于（     ）。
A、集合              B、线性结构              C、树形结构            D、图形结构
对下面二叉树，按中序遍历所得到的结点序列为（      ）。


A、DBEAFC                B、DEBFCA                        C、BDEACF                 D、ABCDEF
对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为（    ）。
A、n                                B、n+1                                C、n-1                                 D、n+边数
为查找某一特定单词在文本中出现的位置，可应用的串运算是(   )
A、插入                B、删除                C、串联接                D、子串定位
串的下列存储结构中，最节省空间的是（     ）。
A、紧缩格式的顺序存储方式                 B、非紧缩格式的顺序存储方式
C、结点大小为1的链接存储方式             D、自定义结点大小的链接存储方式
设有一个含有n 个(n>2)关键字的有序表，设s和h分别是用顺序查找法和二分查找法进行查找时的等概率情况下查找成功的平均查找次数，则s和h的关系是（    ）。
A、s = h               B、s > h                        C、s < h                        D、不能确定二、填空题（本大题共10小题，每小题2分，共计20分）
具有180个结点的二叉树，其深度至少为_________。
_____________________可以判断出一个有向图中是否有环。
设一个散列表的容量为M，用线性探测法解决冲突.。若要查找一个键值，至少要进行1次比较，至多要进行__________次比较。
栈又称为________________的线性表。
在图结构中，前驱元素和后继元素之间存在着_______________的联系。
存储地址与关键字之间存在某种映射关系的存储结构为_____________________。
一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有__________个。
若堆栈的入栈序列为1,2,3,…,n-1,n，输出元素i需要进行__________次出栈操作。
假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中，则C数组的大小应为___________。
线性表的链式存储结构是通过___________来间接反映数据元素之间逻辑关系的。三、判断题（本大题共10小题，每小题2分，共计20分）
（     ）有n个结点的不同的二叉树有n！棵。
（     ）栈是先进先出的线性表。
（     ）程序就是算法，但算法不一定是程序。
（     ）不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。
（     ）数据的机内表示称为数据的存储结构。
（     ）{101，88，46，70，34，39，45，58，66，10}是堆。
（     ）哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
（     ）将一棵树转换成二叉树后，根结点没有左子树。
（     ）非空二叉排序树的任意一棵子树也是二叉排序树。
10、（     ）一个无向图的邻接矩阵中各元素之和与图中边的条数相等。四、应用题（本大题共3小题，每小题10分，共计30分）
逐个结点插入构成平衡二叉树，插入结点的数据顺序为：12,4,1,7,8,10,9,2,11,6,5，在插入过程中平衡树条件如被破坏，则进行必要的调整，试画出每插入一个结点后平衡树的情况。
已知待排序文件各记录的排序码顺序如下72, 73, 71, 23, 94, 16, 05, 68。写出线性插入排序过程中每一趟的排序结果 。
设有升序排列的线性表（2,4,7,10,12,16,18,19,20,24,27,29,30,35,36,40,41），用二分查找法进行查找。
画出查找关键字27的过程（4分）
画出查找关键字11的过程（6分）五、算法设计（本大题共1小题，每小题10分，共计10分）
以下为带空头结点的循环链式队列逻辑结构，请写出队列的入队和出队算法。
转载注明 无忧答案网  Q 761 2 96 0 21