《兰州大学21春“计算机科学与技术”《数据结构》补考试题库2附带答案》由会员分享，可在线阅读，更多相关《兰州大学21春“计算机科学与技术”《数据结构》补考试题库2附带答案（12页珍藏版）》请在装配图网上搜索。
1、长风破浪会有时，直挂云帆济沧海。 住在富人区的她 兰州大学21春“计算机科学与技术”数据结构补考试题库附带答案一.综合考核(共50题)1.单链表的结点包含()和()。A、结点域，符号域B、数据域，符号域C、结点域，指针域D、数据域，指针域参考答案：D2.下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择B.冒泡C.归并D.堆参考答案：C3.数据结构是带有结构的数据元素的集合。()A.正确B.错误参考答案：A4.堆排是一种()排序。A、插入B、选择C、交换D、归并参考答案：B5.对于哈希函数，冲突只能尽可能的少，不可能完全避免。()A、正确B、错误参考答案：A6.数
2、据的逻辑结构是指各数据元素之间的逻辑关系。()A.正确B.错误参考答案：A7.中序遍历二叉排序树可以得到一个有序的序列。()A.正确B.错误参考答案：A8.写出二叉树进行前序和中续遍历的过程。参考答案：前序遍历：(1)访问根结点(2)前序遍历左子树(3)前序遍历右子树中序遍历：(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树9.若用单链表示列队，那么应选用()。A、带尾指针的循环链表B、带尾指针的非循环列队C、带头指针的非循环链表D、带头指针的循环链表参考答案：A10.序列49、38、65、97、76、13、27、49进行一趟冒泡排序后的序列为()。A.49、38、65、97、76、1
3、3、27、49B.13、27、38、49、49、65、76、97C.38、49、65、76、13、27、49、97D.38、49、65、13、27、49、76、97参考答案：C11.对线性表进行折半查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案：C12.若用n表示图中顶点数目，则有()条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C13.不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。()A.正确B.错误参考
4、答案：A14.完全二叉树中的叶子结点只可能在最后两层中出现。()A.正确B.错误参考答案：A15.设某完全无向图中有n个顶点，则该完全无向图中有()条边。A、n(n-1)/2B、n(n-1)C、nD、n-1参考答案：A16.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是()。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B17.图的遍历(名词解释)参考答案：是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。18.在单链表中设置头结点的作用是()。A.主要是使插入
5、和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A19.循环队列SQ采用数组空间SQ.base0，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)%n参考答案：C20.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。()
6、A.正确B.错误参考答案：A21.栈是后进先出的线性表。()A、正确B、错误参考答案：A22.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是()。A.希尔排序B.快速排序C.插入排序D.选择排序参考答案：D23.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多()。A、从小到大排列好的B、从大到小排列好的C、元素无序D、元素基本有序参考答案：B24.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是()。A.6B.4C.3D.2参
7、考答案：C25.归并排序是一种稳定的排序方法。()A.正确B.错误参考答案：A26.可以用队列实现数值转换算法。()A.正确B.错误参考答案：A27.森林的先序遍历与其对应的二叉树的中序遍历对应。()A、正确B、错误参考答案：A28.链表不具备的特点是()。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A29.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、单单选择排序参考答案：D30.不论是入队列操作还是入栈操作，在顺序存储
8、结构上都需要考虑“溢出”情况。()A.正确B.错误参考答案：A31.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C32.在数据结构中，图形结构中元素之间存在()关系。A.一对一B.一对多C.多对一D.多对多参考答案：D33.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。()A.正确B.错误参考答案：A34.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()A.正确B.错误参考答案：A35.如果某种排序算法是不稳定的，则这种算法不可用。()A
9、.正确B.错误参考答案：A36.采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。A.10B.25C.6D.625参考答案：B37.链式队列Q为空的判定条件：()A.Q.front=Q.rearB.Q.front=QC.Q=Q.rearD.没有正确参考答案：A38.数据结构是指()。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A39.函数substr(“DATASTRUCTURE”，5，9)的返回为()。A、“STRUCTURE”B、“DATA”C、“ASTRUCTUR”D、“DATAST
10、RUCTURE”参考答案：A40.栈是限定在表尾进行插入或删除操作的线性表。()A、正确B、错误参考答案：B41.线性表的唯一存储形式就是链表。()A.正确B.错误参考答案：A42.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()A.正确B.错误参考答案：A43.对于双向链表，在两个结点之间插入一个新结点需修改的指针共()个，单链表为()个。A.4，1B.4，2C.1，4D.2，4参考答案：B44.稀疏矩阵(名词解释)参考答案：对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。45.设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?参考
11、答案：方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(、-、*、/等)进行最后求值。46.任何有向网的拓扑排序的结果是唯一的。()A.正确B.错误参考答案：A47.平衡二叉树的平衡因子只可能是-1、0、1。()A.正确B.错误参考答案：A48.一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是()。A.AB.EC.BD.D参考答案：B49.中序遍历的递归算法平均空间复杂度为()。A.2(n)B.n(2)C.0(n)D.2n参考答案：C50.冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。()A.正确B.错误参考答案：A
兰州大学21春“计算机科学与技术”《数据结构》补考试题库2附带答案
