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

长风破浪会有时，直挂云帆济沧海。东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.为使平均查找长度达到最小，当由关键字集合{05，11，21，25，37，40，41，62，84}构建二叉排序树时，第一个插入的关键字应为()。A.5B.37C.41D.622.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是()。A.访问第i个元素的前驱B.在第i个元素之后插入一个新元素C.删除第i个元素D.对顺序表中元素进行排序3.引起循环队列队头位置发生变化的操作是A.取队尾元素B.取队头元素C.出队D.入队4.ISAM文件的周期性整理是为了空出()。A.磁道索引B.柱面索引C.柱面基本区D.柱面溢出区5.适宜进行批量处理的文件类型是A.顺序文件B.索引顺序文件C.散列文件D.多关键字文件6.栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构7.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A.n-1B.nC.2n-1D.2n8.下列关键字序列中，构成小根堆的是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}9.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为一棵具有n个结点的完全二叉树的树高度(深度)是()。A.4B.5C.6D.710.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在A.BT[i/2]B.BT[2*i]C.BT[2*i-1]D.BT[2*i+1]11.数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为()。A.1140B.1145C.1120D.112512.在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行操作：()A.s->next=p->next;p->next=sB.s->next=p;q->next=sC.q->next=s;s->next=pD.p->next=s;s->next=q13.已知一个有向图如下所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为()。A.adbefcB.adcefbC.adcbfeD.adefcb14.在计算机内实现递归算法时所需的辅助数据结构是A.队列B.树C.栈D.图15.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()。A.1.0B.2.9C.3.4D.5.5第II卷一.综合考核(共15题)1.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有A.h+1B.2h-1C.2h+1D.2h2.下列数据结构中，属于非线性数据结构的是()。A.栈B.队列C.完全二叉树D.堆3.抽象数据类型的三个组成部分分别为()。A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型4.在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为A.O(n+e)B.O(n3)C.O(n2)D.O(n)5.以下属于逻辑结构的是A.顺序表B.有序表C.哈希表D.单链表6.从广义表LS=((p，q)，r，s)中分解出原子q的运算是()。A.tail(head(LS))B.head(tail(head(LS)))C.head(tail(LS))D.tail(tail(head(LS)))7.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是()。A.nB.2n-1C.2nD.n-18.按排序过程中依据的原则分类，快速排序属于A.选择类的排序方法B.插入类的排序方法C.归并类的排序方法D.交换类的排序方法9.当采用分快查找时，数据的组织方式为A.数据分成若干块，每块(除最后一块外)中数据个数需相同B.数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块C.数据分成若干块，每块内数据有序D.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块10.倒排文件的主要优点是A.节省存储空间B.便于进行文件的恢复C.便于进行插入和删除运算D.便于进行多关键字查询11.下列序列中，不构成堆的是()。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)12.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为()。A.4B.5C.8D.913.判断两个串大小的基本准则是()。A.两个串长度的大小B.两个串中首字符的大小C.两个串中大写字母的多少D.对应的第一个不等字符的大小14.判定“带头结点的链队列为空”的条件是()。A.Q.front==NULLB.Q.rear==NULLC.Q.front==Q.rearD.Q.front!==Q.rear15.对关键字序列(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)第III卷一.综合考核(共15题)1.下列程序段for(i=1;iA.O(1)B.O(0)C.O(1+n)D.O(n)2.设哈希表长为14，哈希函数H(key)=key%11，表中已有数据的关键字为15，38，61，84四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是()。A.8B.3C.5D.93.若有序表的关键字序列为(b，c，d，e，f，g，q，r，s，t)，则在二分查找关键字b的过程中，先后进行比较的关键字依次为()。A.f，c，bB.f，d，bC.g，c，bD.g，d，b4.要求具有同一逻辑结构的数据元素具有相同的特性，其含义为A.每个数据元素都一样B.数据元素具有同一的特点C.仅需要数据元素包含的数据项的个数相同D.不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致5.从逻辑上可以把数据结构分为两大类，即A.顺序结构、链式结构B.线性结构、非线性结构C.动态结构、静态结构D.初等结构、构造型结构6.ISAM文件和VSAM文件的区别之一是()。A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构D.前者的存储介质是磁盘，后者的存储介质不是磁盘7.可有效提高次关键字查找效率的文件是A.顺序文件B.散列文件C.倒排文件D.VSAM文件8.一个有向无环图的拓扑排序序列是()。A.一定唯一的B.一定不唯一的C.不一定唯一的D.都不对9.数据元素及其关系在计算机存储器内的表示，称为数据的()。A.逻辑结构B.存储结构C.线性结构D.非线性结构10.采用ISAM或VSAM组织的文件是()。A.索引非顺序文件B.顺序文件C.索引顺序文件D.散列文件11.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是A.不确定B.2C.1D.012.下面关于线性表的叙述中，错误的是A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，便于插入和删除操作D.线性表采用链接存储，不必占用一片连续的存储单元13.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为()。A.470B.471C.472D.47314.对长度为n的关键字序列进行堆排序的空间复杂度为()。A.O(log2n)B.O(1)C.O(n)D.O(n*log2n)15.若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的()。A.层次遍历算法B.前序遍历算法C.中序遍历算法D.后序遍历算法第I卷参考答案一.综合考核1.参考答案：B2.参考答案：A3.参考答案：C4.参考答案：D5.参考答案：A6.参考答案：A7.参考答案：B8.参考答案：C9.参考答案：B10.参考答案：D11.参考答案：A12.参考答案：B13.参考答案：A14.参考答案：C15.参考答案：B第II卷参考答案一.综合考核1.参考答案：B2.参考答案：C3.参考答案：A4.参考答案：A5.参考答案：B6.参考答案：A7.参考答案：A8.参