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

长风破浪会有时，直挂云帆济沧海。东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是()。A.栈B.线性表C.队列D.二叉排序树2.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素A[0][0][0]的存储地址为120，则元素A[3][4][5]的存储地址为()。A.356B.358C.360D.3623.队列和栈的主要区别是A.限定插入和删除的位置不同B.逻辑结构不同C.所包含的运算个数不同D.存储结构不同4.数据元素及其关系在计算机存储器内的表示，称为数据的()。A.逻辑结构B.存储结构C.线性结构D.非线性结构5.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有A.h+1B.2h-1C.2h+1D.2h6.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为()。A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA7.已知一组关键字为{25，48，36，72，79，82，23，40，16，35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是()。A.{25，36，48，72，23，40，79，82，16，35}B.{25，36，48，72，16，23，40，79，82，35}C.{25，36，48，72，16，23，35，40，79，82}D.{16，23，25，35，36，40，48，72，79，82}8.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为A.左子树的叶子结点B.左子树的分支结点C.右子树的叶子结点D.右子树的分支结点9.在目标串T[0..n-1]=″xwxxyxy″中，对模式串P[0..m-1]=″xy″进行子串定位操作的结果是A.5B.3C.2D.110.引入二叉线索树的目的是A.加快查找结点的前驱或后继的速度B.使二叉树的遍历结果唯一C.为了能方便的找到双亲D.为了能在二叉树中方便的进行插入与删除11.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是()。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子12.在一个单链表中，若删除*p结点的后继结点，则执行操作()。A.q=p->next;p->next=q->next;free(q)B.p=p->next;p->next=p->next->next;free(p)C.p->next=q->next;free(p->next)D.p=p->next->next;free(p->next)13.一个具有1025个结点的二叉树的高h为()。A.11B.10C.11至1025之间D.10至1024之间14.设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为()。A.21B.23C.41D.6215.按排序过程中依据的原则分类，快速排序属于()。A.插入类的排序方法B.选择类的排序方法C.交换类的排序方法D.归并类的排序方法第II卷一.综合考核(共15题)1.深度为h的满m叉树的第k层的结点(1=A.mk-1B.mk-1C.mh-1D.mh-12.ISAM文件和VSAM文件的区别之一是()。A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构D.前者的存储介质是磁盘，后者的存储介质不是磁盘3.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.44.下列编码中属于前缀编码的是()。A.{1，01，000，001}B.{1，01，011，010}C.{0，10，110，11}D.{0，1，00，11}5.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是A.后序B.先序C.从根开始的层次遍历D.中序6.以下属于逻辑结构的是A.顺序表B.有序表C.哈希表D.单链表7.带行表的三元组表是稀疏矩阵的一种()。A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构8.对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为A.55/15B.51/15C.49/15D.39/159.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在A.BT[i/2]B.BT[2*i]C.BT[2*i-1]D.BT[2*i+1]10.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。A.栈B.队列C.树D.图11.适宜进行批量处理的文件类型是A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件12.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A.n-1B.nC.2n-1D.2n13.以下数据结构中，属于线性结构的是()。A.广义表B.二叉树C.稀疏矩阵D.串14.对长度为n的关键字序列进行堆排序的空间复杂度为()。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)15.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为A.O(n2)B.O(n)C.O(1)D.O(0)第I卷参考答案一.综合考核1.参考答案：A2.参考答案：B3.参考答案：A4.参考答案：B5.参考答案：B6.参考答案：B7.参考答案：D8.参考答案：A9.参考答案：B10.参考答案：A11.参考答案：B12.参考答案：A13.参考答案：C14.参考答案：C15.参考