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

长风破浪会有时，直挂云帆济沧海。兰州大学23春“计算机科学与技术”《数据结构》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.归并排序是一种稳定的排序方法。()A.正确B.错误2.Prim(普里姆)算法适用于求()的网的最小生成树;kruskal(克鲁斯卡尔)算法适用于求()的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏3.采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。A.10B.25C.6D.6254.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。()A.正确B.错误5.哈希表不需要进行比较便可以直接取得所查记录。()A.正确B.错误6.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法7.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。()A.正确B.错误8.对于哈希函数，冲突只能尽可能的少，不可能完全避免。()A、正确B、错误9.若用单链表示列队，那么应选用()。A、带尾指针的循环链表B、带尾指针的非循环列队C、带头指针的非循环链表D、带头指针的循环链表10.链式队列Q为空的判定条件：()A.Q.front==Q.rearB.Q.front==QC.Q==Q.rearD.没有正确11.设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?12.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、单单选择排序13.完全二叉树中的叶子结点只可能在最后两层中出现。()A.正确B.错误14.在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度()。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同15.栈是限定在表尾进行插入或删除操作的线性表。()A、正确B、错误第II卷一.综合考核(共15题)1.中序遍历的递归算法平均空间复杂度为()。A.2(n)B.n(2)C.0(n)D.2n2.堆的形状是一棵()。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树3.设某完全无向图中有n个顶点，则该完全无向图中有()条边。A、n(n-1)/2B、n(n-1)C、n²D、n²-14.非空的双向循环链表中任何结点的前驱指针均不为空。()A.正确B.错误5.图的广度优先遍历算法类似于二叉树的()。A、先序遍历B、中序遍历C、后序遍历D、层次遍历6.如果某种排序算法是不稳定的，则这种算法不可用。()A.正确B.错误7.序例278、109、930经过一趟基数排序后结果为()。A、930、278、109B、109、930、278C、109、278、930D、278、109、9308.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()A.正确B.错误9.平衡二叉树的平衡因子只可能是-1、0、1。()A.正确B.错误10.对于哈希函数，冲突只能尽可能得少，不可能完全避免。()A.正确B.错误11.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()A.正确B.错误12.队列允许在队尾删除，在队头插入。()A.正确B.错误13.循环队列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)%n14.稀疏矩阵(名词解释)15.一个队列的入队序列是1、2、3、4，则队列的首次输出元素是()。A.1B.2C.3D.4第III卷一.综合考核(共15题)1.栈是后进先出的线性表。()A、正确B、错误2.单链表的结点包含()和()。A、结点域，符号域B、数据域，符号域C、结点域，指针域D、数据域，指针域3.由树转化成二叉树，其根节点的右子树总是空。()A.正确B.错误4.线性表中的所有元素都有一个前驱元素和后继元素。()A.正确B.错误5.堆排是一种()排序。A、插入B、选择C、交换D、归并6.在数据结构中，图形结构中元素之间存在()关系。A.一对一B.一对多C.多对一D.多对多7.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)2B.n2C.(n+1)2D.n8.引入二叉线索树的目的是()。A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除9.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多()。A、从小到大排列好的B、从大到小排列好的C、元素无序D、元素基本有序10.设某完全无向图中有n个顶点，则该完全无向图中有()条边。A.n(n-1)/2B.n(n-1)C.n2D.n2-111.广度优先遍历类似于二叉树的()。A.先序遍历B.中序遍历C.后序遍历D.层次遍历12.顺序存储结构是通过()表示元素之间的关系的;链式存储结构是通过()表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点13.从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为()。A.希尔排序B.归并排序C.插入排序D.选择排序14.下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆15.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是()。A.6B.4C.3D.2第I卷参考答案一.综合考核1.参考答案：A2.参考答案：A3.参考答案：B4.参考答案：A5.参考答案：A6.参考答案：C7.参考答案：A8.参考答案：A9.参考答案：A10.参考答案：A11.参考答案：方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(、-、*、/等)进行最后求值。12.参考答案：D13.参考答案：A14.参考答案：B15.参考答案：B第II卷参考答案一.综合考核1.参考答案：C2.参考答案：C3.参考答案：A4.参考答案：A5.参考答案：B6.参考答案：A7.参考答案：A8.参考答案：A9.参考答案：A10.参考答案：A11.参考答案：A12.参考答案：A13.参考答案：C14.参考答案：对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没