川农《数据结构(本科)》19年12月作业考核A

[复制链接]
发表于 2019-12-9 09:20:45 | 显示全部楼层 |阅读模式
四川农业大学网络教育专升本考试
数据结构  试卷(课程代码  252259)本试题一共五道大题,共4页,满分100分。考试时间90分钟。
        
注意:1、答案必须填写在答题纸上,题号不清或无题号的以零分计;
2、答题前,请在答题纸上准确、清楚地填写各项目;
3、学号、考点名称、考室号、姓名、身份证号、课程代码、课程名称、培养层次等,不写、乱写及模糊不清者,答题纸作废;
4、开卷考试,若有雷同以零分计。一、单项选择题(本大题共10小题,每小题1分,共计10分)
在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为(    )
A)e                  B)2e                  C)n2-e                  D)n2-2e
汉诺塔(Hanoi)问题一个典型的(      )问题。
A)递归                B)排序               C)查找                 D)遍历
设二叉树根结点的层次为1,含有15个结点的二叉树中的最小高度是(  )
A) 6                                B) 5                        C) 4                                D) 3
设数组data[m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作后其头指针front值为(     )
A)front=front+1                         B)front=(front+1)%(m-1)
        C)front=(front-1)%m                     D)front=(front+1)%m
最能影响算法效率的因素是(     )。
        A)所选择的程序设计语言                        B)机器指令执行的速度
     C)问题的规模                          D)编译程序所产生的机器代码的质量
在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素,元素的移动次数为(    )。
A)i-1              B)n-i+1               C)i               D)n-i
下列有关线性表的叙述中,正确的是(    )
线性表中所有数据元素的数据类型必须相同
线性表中至少有一个元素
线性表中任何一个元素有且仅有一个直接前趋
线性表中任何一个元素有且仅有一个直接后继
一棵深度为7的满二叉树有(      )叶子结点。
        A)7              B)14                      C)32                      D)64
已知一个有向图如下图所示,则从顶点a出发进行深度优先偏历,不可能得到的DFS序列为(    )。

        A)  a d b e f c                B)  a d c e f b                C)  a d c b f e                D)  a d e f c b
设用一维数组A[n]来表示一个栈,A[n]为栈底。用整型变量T指示当前栈顶位置,A[T]为栈顶元素。往栈中推入(PUSH)一个元素时,T的值(     )
A) 加1                 B) 减1                 C) 不变                 D) 清0二、填空题(本大题共15小题,每小题2分,共计30分)
具有180个结点的二叉树,其深度至少为_________。
_____________________可以判断出一个有向图中是否有环。
设一个散列表的容量为M,用线性探测法解决冲突.。若要查找一个键值,至少要进行1次比较,至多要进行__________次比较。
栈又称为________________的线性表。
在图结构中,前驱元素和后继元素之间存在着_______________的联系。
存储地址与关键字之间存在某种映射关系的存储结构为_____________________。
一棵二叉树有67个结点,这些结点的度要么是0,要么是2。这棵二叉树中度为2的结点有__________个。
若堆栈的入栈序列为1,2,3,…,n-1,n,输出元素i需要进行__________次出栈操作。
假设一个10阶的下三角矩阵A按列优顺序压缩存储在一维数组C中,则C数组的大小应为___________。
线性表的链式存储结构是通过___________来间接反映数据元素之间逻辑关系的。
依次在初始为空的队列中插入元素a,b,c,d,e以后,紧接着作了三次删除操作,此时的队首元素是___________。
按照二叉树的定义,具有3个结点的二叉树有___________种形态。
串的长度是指_______________________。
一般可以利用__________为递归问题设计出非递归算法。
带权路径最小的二叉树称为____________________。三、判断题(本大题共10小题,每小题2分,共计20分)
(     )有n个结点的不同的二叉树有n!棵。
(     )栈是先进先出的线性表。
(     )程序就是算法,但算法不一定是程序。
(     )不管堆栈采用何种存储结构,只要堆栈不空,可以任意删除一个元素。
(     )数据的机内表示称为数据的存储结构。
(     ){101,88,46,70,34,39,45,58,66,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的过程(3分)
画出查找关键字11的过程(4分)
计算该表在等概率的情况下查找成功的平均查找次数为多少?(3分)五、算法设计(本大题共1小题,每小题10分,共计10分)
以下为带空头结点的循环链式队列逻辑结构,请写出队列的入队和出队算法。
转载注明 无忧答案网  Q 761 2 96 0 21

快速回复 返回顶部 返回列表