兰州大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库带答案

长风破浪会有时，直挂云帆济沧海。兰州大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()A.正确B.错误2.完全二叉树中的叶子结点只可能在最后两层中出现。()A.正确B.错误3.中序遍历二叉排序树可以得到一个有序的序列。()A.正确B.错误4.快速排序是排序算法中平均性能最好的一种排序。()A.正确B.错误5.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法6.如果某种排序算法是不稳定的，则这种算法不可用。()A.正确B.错误7.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。()A.正确B.错误8.链式队列Q为空的判定条件：()A.Q.front==Q.rearB.Q.front==QC.Q==Q.rearD.没有正确9.采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。A.10B.25C.6D.62510.若用单链表示列队，那么应选用()。A、带尾指针的循环链表B、带尾指针的非循环列队C、带头指针的非循环链表D、带头指针的循环链表11.栈是限定在表尾进行插入或删除操作的线性表。()A、正确B、错误12.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。()A.正确B.错误13.写出二叉树进行前序和中续遍历的过程。14.队列允许在队尾删除，在队头插入。()A.正确B.错误15.线性表中的所有元素都有一个前驱元素和后继元素。()A.正确B.错误第II卷一.综合考核(共15题)1.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。()A.正确B.错误2.循环队列SQ采用数组空间SQ.base[0，n-1]存储其元素值，已知其头尾指针分别是front和rezr，则判断此循环队列Q为满队列的条件是()。A.Q.front==Q.rearB.Q.rear!=Q.frontC.Q.front==(Q.rear+1)%nD.Q.front!=(Q.rear+1)%n3.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。()A.正确B.错误4.稀疏矩阵(名词解释)5.栈是后进先出的线性表。()A、正确B、错误6.邻接表法只能用于有向图存储。()A.正确B.错误7.顺序存储结构是通过()表示元素之间的关系的;链式存储结构是通过()表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点8.数据项是数据的基本单位。()A.正确B.错误9.二叉树的第K层的结点数最多为()。A、2^k-1B、2^K+1C、2^(k-1)+1D、2^(k-1)10.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()A.正确B.错误11.链表不具备的特点是()。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比12.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、单单选择排序13.如何知道循环队列是空还是满?14.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是()。A.希尔排序B.快速排序C.插入排序D.选择排序15.线性表的唯一存储形式就是链表。()A.正确B.错误第III卷一.综合考核(共15题)1.从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为()。A.希尔排序B.归并排序C.插入排序D.选择排序2.线性表若采用顺序存储结构时，要求内存中的可用存储单元的地址必须连续。()A、正确B、错误3.基数排序需要进行关键字的比较。()A.正确B.错误4.图的广度优先遍历算法类似于二叉树的()。A、先序遍历B、中序遍历C、后序遍历D、层次遍历5.可以用队列实现数值转换算法。()A.正确B.错误6.哈希表不需要进行比较便可以直接取得所查记录。()A.正确B.错误7.非空的双向循环链表中任何结点的前驱指针均不为空。()A.正确B.错误8.在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度()。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同9.数据的逻辑结构是指各数据元素之间的逻辑关系。()A.正确B.错误10.队列的插入操作是在()。A.队尾B.队头C.队列任意位置D.队头元素后11.Prim(普里姆)算法适用于求()的网的最小生成树;kruskal(克鲁斯卡尔)算法适用于求()的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏12.二叉排序树上左子树上所有结点的值均小于它的根结点的值。()A.正确B.错误13.图的遍历(名词解释)14.一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是()。A.AB.EC.BD.D15.平衡二叉树的平衡因子只可能是-1、0、1。()A.正确B.错误第I卷参考答案一.综合考核1.参考答案：A2.参考答案：A3.参考答案：A4.参考答案：A5.参考答案：C6.参考答案：A7.参考答案：A8.参考答案：A9.参考答案：B10.参考答案：A11.参考答案：B12.参考答案：A13.参考答案：前序遍历：(1)访问根结点(2)前序遍历左子树(3)前序遍历右子树中序遍历：(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树14.参考答案：A15.参考答案：A第II卷参考答案一.综合考核1.参考答案：A2.参考答案：C3.参考答案：A4.参考答案：对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。5.参考答案：A6.参考答案：B7.参考答案：A8.参考答案：A9.参考答案：D10.参考答案：A11.参考答案：A12.参考答案：D13.参考答案：采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：(1)设置一个布尔变量以区别队满还是队空；(2)浪费一个元素的空间，用于区别队满还是队空；(3)使用一个计数器记录队列中元素个数(即队列长度)。我们常采用方法(2)，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear；队满标志是：f=(r+1)%N14.参考答案：D15.参考答案：A第III卷参考答案一.综合考核1