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

长风破浪会有时，直挂云帆济沧海。东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向()。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点D.一个表的头结点，另一个表的尾结点2.一个具有1025个结点的二叉树的高h为()。A.11B.10C.11至1025之间D.10至1024之间3.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为一棵具有n个结点的完全二叉树的树高度(深度)是()。A.4B.5C.6D.74.执行下列程序段后，串X的值为S=“abcdefgh”;T=“xyzw”;substr(X，S，2，strlen(T));substr(Y，S，stelen(T)，2);strcat(X，Y)。A.“cdefgh”B.“cdxyzw”C.“defxy”D.“cdefef”5.已知含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，2，5，3，4，6，7，8，9，10)B.(10，5，8，4，2，6，7，1，3)C.(10，9，8，7，3，5，4，6，2)D.(1，2，3，4，10，9，8，7，6，5)7.判定“带头结点的链队列为空”的条件是()。A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!==Q.rear8.在下列各种文件中，不能进行顺序查找的文件是()。A.顺序文件B.索引文件C.散列文件D.多重表文件9.抽象数据类型的三个组成部分分别为()。A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型10.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是A.树的后根遍历与其对应的二叉树的后根遍历相同B.树的后根遍历与其对应的二叉树的中根遍历相同C.树的先根遍历与其对应的二叉树的中根遍历相同D.以上都不对11.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是()。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表12.下列程序段for(i=1;iA.O(1)B.O(0)C.O(1+n)D.O(n)13.下面说法错误的是()。(1)算法原地工作的含义是指不需要任何额外的辅助空间;(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法;(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界;(4)同一个算法，实现语言的级别越高，执行效率就越低。A.(1)B.(1)，(2)C.(1)，(4)D.(3)14.以下数据结构中，属于线性结构的是()。A.广义表B.二叉树C.稀疏矩阵D.串15.若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为()。A.f，c，bB.f，d，bC.g，c，bD.g，d，b第II卷一.综合考核(共15题)1.当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为A.左子树的叶子结点B.左子树的分支结点C.右子树的叶子结点D.右子树的分支结点2.顺序存储设计时，存储单元的地址A.部分连续，部分不连续B.不一定连续C.一定连续D.一定不连续3.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在A.BT[i/2]B.BT[2*i]C.BT[2*i-1]D.BT[2*i+1]4.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是()。A.栈B.队列C.树D.图5.倒排文件的主要优点是()。A.便于进行插入和删除运算B.便于进行文件的恢复C.便于进行多关键字查询D.节省存储空间6.下列数据结构中，属于非线性数据结构的是()。A.栈B.队列C.完全二叉树D.堆7.在计算机内实现递归算法时所需的辅助数据结构是A.队列B.树C.栈D.图8.ISAM文件的周期性整理是为了空出()。A.磁道索引B.柱面索引C.柱面基本区D.柱面溢出区9.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n)B.O(n+e)C.O(n2)D.O(n3)10.下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是A.直接选择排序B.快速排序C.堆排序D.冒泡排序11.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的()。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法12.链栈与顺序栈相比，比较明显的优点是()。A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况13.快速排序在最坏情况下的时间复杂度是A.O(nlog2n)B.O(n2log2n)C.O(n2)D.O(log2n)14.下列关键字序列中，构成小根堆的是A.{84，62，58，46，41，37，28，15}B.{84，46，62，41，28，58，15，37}C.{15，28，46，37，84，58，62，41}D.{15，28，46，37，84，41，58，62}15.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为A.9B.8C.5D.4第I卷参考答案一.综合考核1.参考答案：B2.参考答案：C3.参考答案：B4.参考答案：D5.参考答案：D6.参考答案：D7.参考答案：C8.参考答案：C9.参考答案：A10.参考答案：B11.参考答案：A12.参考答案：D13.参考答案：C14.参考答案：A15.