东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试历年高频难、易错点试题甄选答案附答案

长风破浪会有时，直挂云帆济沧海。东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试历年高频难、易错点试题甄选答案附答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.希尔排序的增量序列必须是()。A.递增的B.随机的C.递减的D.非递减的2.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()。A.1.0B.2.9C.3.4D.5.53.对关键字序列(5，1，4，3，7，2，8，6)进行快速排序时，以第一个元素5为基准的一次划分的结果为A.(8，7，6，5，4，3，2，1)B.(2，1，4，3，5，7，8，6)C.(1，4，3，2，5，7，8，6)D.(1，2，3，4，5，6，7，8)4.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为()。A.7B.8C.9D.105.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为A.(v0，v1，v5，v2，v3，v4)B.(v0，v1，v4，v5，v2，v3)C.(v0，v1，v2，v5，v4，v3)D.(v0，v1，v2，v3，v4，v5)6.数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为()。A.1140B.1145C.1120D.11257.设一个栈的输入序列为1、2、3、4、5，则借助一个栈所得到的输出序列不可能是()。A.23415B.54132C.23145D.154328.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为()。A.21B.23C.41D.629.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.410.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是()。A.树的后根遍历与其对应的二叉树的后根遍历相同B.树的后根遍历与其对应的二叉树的中根遍历相同C.树的先根遍历与其对应的二叉树的中根遍历相同D.以上都不对11.树的先根序列等同于与该树对应的二叉树的()。A.先序序列B.中序序列C.后序序列D.层序序列12.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()。A.1和5B.2和4C.4和2D.5和113.若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向()。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点14.上溢现象通常出现在A.顺序栈的出栈操作过程中B.顺序栈的入栈操作过程中C.链栈的出栈操作过程中D.链栈的入栈操作过程中15.要求具有同一逻辑结构的数据元素具有相同的特性，其含义为A.每个数据元素都一样B.数据元素具有同一的特点C.仅需要数据元素包含的数据项的个数相同D.不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致第II卷一.综合考核(共15题)1.下列说法正确的是：(1)二叉树按某种方式线索化后，任一节点均有指向前趋和后继的线索;(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前;(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值。A.(1)(2)(3)B.(1)(2)C.(1)(3)D.前面的可选答案都不对2.一个有向无环图的拓扑排序序列是()。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是()。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表4.数据结构中所定义的数据元素，是用于表示数据的()。A.最小单位B.最大单位C.基本单位D.不可分割的单位5.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为A.DEFBCAB.DEBFCAC.DEBCFAD.DEBAFC6.ISAM文件的周期性整理是为了空出()。A.磁道索引B.柱面索引C.柱面基本区D.柱面溢出区7.在用邻接表表示图时，拓扑排序算法时间复杂度为()。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)8.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为A.O(n+e)B.O(n3)C.O(n2)D.O(n)9.若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为()。A.f，c，bB.f，d，bC.g，c，bD.g，d，b10.判断两个串大小的基本准则是()。A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小11.以下数据结构中，属于线性结构的是()。A.广义表B.二叉树C.稀疏矩阵D.串12.引入二叉线索树的目的是A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除13.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素A[0][0][0]的存储地址为120，则元素A[3][4][5]的存储地址为()。A.356B.358C.360D.36214.有关二叉树下列说法正确的是()。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为215.按排序过程中依据的原则分类，快速排序属于()。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法第I卷参考答案一.综合考核1.参考答案：C2.参考答案：B3.参考答案：B4.参考答案：D5.参考答案：D6.参考答案：A7.参考答案：B8.参考答案：C9.参考答案：B10.参考答案：B11.参考答案：A12.参考答案：B13.参考答案：B14.参考答案：B15