兰州大学2022年3月“计算机科学与技术”《数据结构》平时作业一（答案参考）试卷号：10

《兰州大学2022年3月“计算机科学与技术”《数据结构》平时作业一（答案参考）试卷号：10》由会员分享，可在线阅读，更多相关《兰州大学2022年3月“计算机科学与技术”《数据结构》平时作业一（答案参考）试卷号：10（13页珍藏版）》请在装配图网上搜索。

1、书山有路勤为径，学海无涯苦作舟！ 住在富人区的她兰州大学2022年3月“计算机科学与技术”数据结构平时作业一（答案参考）一.综合考核(共45题)1.引入二叉线索树的目的是()。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除参考答案：A2.Prim(普里姆)算法适用于求()的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求()的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A3.如何知道循环队列是空还是满?参考答案：采用循环队列是解决假溢出的途径。另外，解决

2、队满队空的办法有三：(1)设置一个布尔变量以区别队满还是队空；(2)浪费一个元素的空间，用于区别队满还是队空；(3)使用一个计数器记录队列中元素个数(即队列长度)。我们常采用方法(2)，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear；队满标志是：f=(r+1)%N4.对于哈希函数，冲突只能尽可能的少，不可能完全避免。()A、正确B、错误参考答案：A5.栈是后进先出的线性表。()A、正确B、错误参考答案：A6.线性表的唯一存储形式就是链表。()A.正确B.错误参考答案：A7.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依

3、次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是()。A.6B.4C.3D.2参考答案：C8.邻接表法只能用于有向图存储。()A.正确B.错误参考答案：B9.在单链表中设置头结点的作用是()。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A10.由树转化成二叉树，其根节点的右子树总是空。()A.正确B.错误参考答案：A11.图的遍历(名词解释)参考答案：是从图中某一顶点出发访遍图中其余顶点，且使每一个

4、顶点仅被访问一次。12.在数据结构中，图形结构中元素之间存在()关系。A.一对一B.一对多C.多对一D.多对多参考答案：D13.森林的先序遍历与其对应的二叉树的中序遍历对应。()A、正确B、错误参考答案：A14.数据的逻辑结构是指各数据元素之间的逻辑关系。()A.正确B.错误参考答案：A15.基数排序需要进行关键字的比较。()A.正确B.错误参考答案：B16.序列49、38、65、97、76、13、27、49进行一趟冒泡排序后的序列为()。A.49、38、65、97、76、13、27、49B.13、27、38、49、49、65、76、97C.38、49、65、76、13、27、49、97D.3

5、8、49、65、13、27、49、76、97参考答案：C17.二叉排序树上左子树上所有结点的值均小于它的根结点的值。()A.正确B.错误参考答案：A18.栈是限定在表尾进行插入或删除操作的线性表。()A、正确B、错误参考答案：B19.一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是()。A.AB.EC.BD.D参考答案：B20.二叉树的第K层的结点数最多为()。A、2k-1B、2K+1C、2(k-1)+1D、2(k-1)参考答案：D21.对于哈希函数，冲突只能尽可能得少，不可能完全避免。()A.正确B.错误参考答案：A22.线性表若采用顺序存储结构时，要求内存中的可用存

6、储单元的地址必须连续。()A、正确B、错误参考答案：A23.函数substr(“DATASTRUCTURE”，5，9)的返回为()。A、“STRUCTURE”B、“DATA”C、“ASTRUCTUR”D、“DATASTRUCTURE”参考答案：A24.队列的插入操作是在()。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A25.数据结构是指()。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A26.广度优先遍历类似于二叉树的()。A.先序遍历B.中序遍历C.后序遍历D.层次遍历参考答案：D27.下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位

7、置上。A.选择B.冒泡C.归并D.堆参考答案：C28.队列允许在队尾删除，在队头插入。()A.正确B.错误参考答案：A29.线性表中的所有元素都有一个前驱元素和后继元素。()A.正确B.错误参考答案：A30.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。()A.正确B.错误参考答案：A31.稀疏矩阵(名词解释)参考答案：对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。32.完全二叉树中的叶子结点只可能在最后两层中出现。()A.正确B.错误参考答案：A33.快速排序是排序算法中平均性能最好的一

8、种排序。()A.正确B.错误参考答案：A34.链式队列Q为空的判定条件：()A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A35.从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为()。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D36.可以用队列实现数值转换算法。()A.正确B.错误参考答案：A37.数据结构是带有结构的数据元素的集合。()A.正确B.错误参考答案：A38.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()A.正确B.错误参考答案：A39.中序遍历二叉排序树可以得到一个有序的

9、序列。()A.正确B.错误参考答案：A40.顺序存储结构是通过()表示元素之间的关系的;链式存储结构是通过()表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A41.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。()A.正确B.错误参考答案：A42.链表不具备的特点是()。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A43.一个队列的入队序列是1、2、3、4，则队列的首次输出元素是()。A.1B.2C.3D.4参考答案：A44.单链表的结点包含()和()。A、结点域，符号域B、数据域，符号域C、结点域，指针域D、数据域，指针域参考答案：D45.数据项是数据的基本单位。()A.正确B.错误参考答案：A