大连理工大学23春“计算机科学与技术”《数据结构》补考试题库附答案

大连理工大学23春“计算机科学与技术”《数据结构》补考试题库附答案第I卷一.综合考核(共15题)1.二叉树的遍历是对一个非线性结构的元素做线性化排列的过程。()A.正确B.错误2.在n个结点的无向图中，若边数大于n-1，则该图必是连通图。()A.正确B.错误3.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的()方法是散列文件的关键。A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理4.一棵线索二叉树中含有的线索数比分支数多()个。A.2B.1C.0D.不确定5.散列函数越复杂越好，因为这样随机性好，冲突概率小。()A.正确B.错误6.采用顺序查找方法查找长度为n的线性表时，成功查找时的平均查找长度为()。A.nB.n/2C.(n+1)/2D.(n-1)/27.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。()A.正确B.错误8.在链式存储中所有结点之间的存储地址可连续也可不连续。()A.正确B.错误9.一个算法是可行的，即算法中描述的操作都是可以通过已实现的基本运算执行有限次来实现的。()A.正确B.错误10.一棵高度为8的完全二叉树至少有()叶子结点。A.63B.64C.127D.12811.下面给出的四种排序法中()排序法是不稳定性排序法。A.直接插入排序B.冒泡排序C.二路归并排序D.堆排序12.下述文件中适合于磁带存储的是()。A.顺序文件B.索引文件C.散列文件D.多关键字文件13.在二叉树的先序遍历序列中，任一结点均处在其子树结点前面。()A.正确B.错误14.使用先序遍历算法可以求得二叉树的深度。()A.正确B.错误15.用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。()A.正确B.错误第II卷一.综合考核(共15题)1.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()。A.9B.11C.15D.不确定2.度为2的有序树就是二叉树。()A.正确B.错误3.线性表的每个数据元素的数据类型都相同。()A.正确B.错误4.若一棵二叉树的先序遍历序列为efhigjk，中序遍历序列为hfiejkg，则该二叉树根结点的右孩子为()。A.eB.fC.gD.h5.树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.数据元素是数据的最小单位()。A.正确B.错误7.以下排序算法中，()在最后一趟排序结束之前可能所有元素都没有放到其最终位置上。A.快速排序B.希尔排序C.堆排序D.冒泡排序8.在二叉查找树中，新结点总是作为叶结点插入。()A.正确B.错误9.在中序线索二叉树中，每个非根结点的非空线索都指向该结点的某个祖先结点。()A.正确B.错误10.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为()。A.CBEFDAB.FEDCBAC.CBEDFAD.不定11.如果二叉树T2是由一棵树T1转换而来的二叉树，那么T1中结点的先根序列对应T2的()序列。A.先序遍历B.中序遍历C.后序遍历D.层次遍历12.在顺序表中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。()A.正确B.错误13.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。A.冒泡B.希尔C.快速D.堆14.在任何情况下，起泡排序比快速排序的速度慢。()A.正确B.错误15.算法的确定性是指算法中每一条指令必须有确切的含义，确保不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。()A.正确B.错误第III卷一.综合考核(共15题)1.算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。()A.正确B.错误2.二叉树的顺序存储只能从下标1的位置开始存放。()A.正确B.错误3.查找效率最高的二叉排序树是()。A.所有结点的左子树都为空的二叉排序树B.所有结点的右子树都为空的二叉排序树C.平衡二叉树D.没有左子树的二叉排序数4.在下列存储形式中，哪一个不是树的存储形式?()A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法5.负载因子(装填因子)是散列表的一个重要参数，它反映散列表的装满程度。()A.正确B.错误6.在二叉查找树中，新插入的关键码总是处于最底层。()A.正确B.错误7.链式栈和顺序栈相比，有一个比较明显的优点，即()。A.插入操作更加方便B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便8.设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用()排序法。A.冒泡排序B.快速排序C.堆排序D.基数排序9.以下选项属于逻辑结构的是()。A.顺序表B.散列表C.有序表D.单链表10.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表11.在后序线索二叉树中，后序下的第一个结点一定是最左下的结点。()A.正确B.错误12.队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。()A.正确B.错误13.对稀疏矩阵进行压缩存储目的是()。A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度14.对线性表进行折半查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链表方式存储，且结点按关键字有序排列15.一个递归算法必须包括()。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分第I卷参考答案一.综合考核1.参考答案：A2.参考答案：B3.参考答案：D4.参考答案：A5.参考答案：B6.参考答案：C7.参考答案：B8.参考答案：A9.参考答案：A10.参考答案：B11.参考答案：D12.参考答案：A13.参考答案：A14.参考答案：B15.参考答案：B第II卷参考答案一.综合考核1.参考答案：B2.参考答案：B3.参考答案：A4.参考答案：C5.参考答案：C6.参考答案：B7.参考答案：B8.参考答案：A9.参考答案：A10.参考答案：A11.参考答案：A12.参考答案：B13.参考答案：C14.参考答案：B15.参考答案：A