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

长风破浪会有时，直挂云帆济沧海。东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试高频考点参考题库带答案（图片大小可自由调整）第I卷一.综合考核(共15题)1.对关键字序列(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)2.快速排序在最坏情况下的时间复杂度是A.O(nlog2n)B.O(n2log2n)C.O(n2)D.O(log2n)3.已知一个散列表如图所示，其散列函数为H(key)=key%11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为()。A.2B.3C.8D.94.若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为()。A.4B.5C.8D.95.已知一个有向图如下所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为()。A.adbefcB.adcefbC.adcbfeD.adefcb6.在线性表的下列运算中，不改变数据元素之间结构关系的运算是A.查找B.插入C.排序D.删除7.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是()。A.访问第i个元素的前驱B.在第i个元素之后插入一个新元素C.删除第i个元素D.对顺序表中元素进行排序8.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是A.O(nlogn)B.O(n2)C.O(n)D.O(1)9.引入二叉线索树的目的是()。A.加快查找结点的前驱或后继的速度B.为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一10.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为一棵具有n个结点的完全二叉树的树高度(深度)是()。A.4B.5C.6D.711.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有A.h+1B.2h-1C.2h+1D.2h12.下面关于数据结构正确的说法是A.相互之间存在一种或多种特定关系的数据元素的集合B.数据的存储结构C.一组性质相同的数据元素的集合D.一种数据类型13.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()。A.1.0B.2.9C.3.4D.5.514.设一个栈的输入序列为1、2、3、4、5，则借助一个栈所得到的输出序列不可能是()。A.23415B.54132C.23145D.1543215.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系A.都相同B.都不相同C.互为逆序D.不一定相同第II卷一.综合考核(共15题)1.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是()。A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表2.在目标串T[0..n-1]=″xwxxyxy″中，对模式串P[0..m-1]=″xy″进行子串定位操作的结果是A.5B.3C.2D.13.以下数据结构中，属于线性结构的是()。A.广义表B.二叉树C.稀疏矩阵D.串4.ISAM文件和VSAM文件的区别之一是()。A.前者是索引顺序文件，后者是索引非顺序文件B.前者只能进行顺序存取，后者只能进行随机存取C.前者建立静态索引结构，后者建立动态索引结构D.前者的存储介质是磁盘，后者的存储介质不是磁盘5.在目标串T[0..n-1]=“xwxxyxy”中，对模式串P[0..m-1]=“xy”进行子串定位操作的结果是()。A.1B.2C.3D.56.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()。A.1和5B.2和4C.4和2D.5和17.若要在单链表中的结点p之后插入一个结点s，则应执行的语句是()。A.s->next=p->next;p->next=sB.p->next=s;s->next=p->nextC.p->next=s->next;s->next=pD.s->next=p;p->next=s->next8.倒排文件的主要优点是A.节省存储空间B.便于进行文件的恢复C.便于进行插入和删除运算D.便于进行多关键字查询9.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=head，则()。A.p指向头结点B.p指向尾结点C.p的直接后继是头结点D.P的直接后继是尾结点10.在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系()。A.不一定相同B.都相同C.都不相同D.互为逆序11.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是()。A.栈B.线性表C.队列D.二叉排序树12.n个顶点的强连通图中至少含有()。A.n-1条有向边B.n条有向边C.n(n-1)/2条有向边D.n(n-1)条有向边13.已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为()。A.7B.8C.9D.1014.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为()。A.n-i+1B.n-iC.iD.i-115.下面说法错误的是(1)算法原地工作的含义是指不需要任何额外的辅助空间(2)在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界(4)同一个算法，实现语言的级别越高，执行效率就越低A.(1),(4)B.(1),(2)C.(3)D.(1)第III卷一.综合考核(共15题)1.某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是()。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子2.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是()。A.head(tail(LS))B.tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))3.ISAM文件的周期性整理是为了空出()。A.磁道索引B.柱面索引C.柱面基本区D.柱面溢出区4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为()。A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点5.已知散列表的存储空间为T[0..18]，散列函数H(key)=key%17,并用二次探测法处理冲突。散列表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是A.T[8]B.T[4]C.T[2]D.T[10]6.树的先根序列等同于与该树对应的二叉树的()。A.先序序列B.中序序列C.后序序列D.层序序列7.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为()。A.ABCDEFB.ABCEFDC.ABFCDED.ABCDFE8.在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为()。A.iB.i+1C.n-iD.n-i+19.栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构10.从逻辑上可以把数据结构分为两大类，即A.顺序结构、链式结构B.线性结构、非线性结构C.动态结构、静态结构D.初等结构、构造型结构11.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)12.下列程序段for(i=1;iA.O(n)B.O(1+n)C.O(1)D.O(0)13.下列序列中，不构成堆的是()。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)14.ALV树是一种平衡的二叉排序树，树中任一结点的A.左子树的高度均小于右子树的高度B.左子树的高度均大于右子树的高度C.左、右子树高度差的绝对值不超过1D.左、右子树的高度均相同15.能进行二分查找的线性表，必须以()。A.顺序方式存储，且元素按关键字有序B.链式方式存储，且元素按关键字有序C.顺序方式存储，且元素按关键字分块有序D.链式方式存储，且元素按关键字分块有序第I卷参考答案一.综合考核1.参考答案：B2.参考答案：C3.参考答案：C4.参考答案：C5.参考答案：A6.参考答案：A7.参考答案：A8.参考答案：C9.参考答案：A10.参考答案：B11.参考答案：B12.参考答案：A13.参考答案：B14.参考答案：B15.参考答案：A第II卷参考答案一.综合考核1.参考答案：A2.参考答案：B3.参考答案：A4.参考答案：C5.参考答案：C6.参考答案：B7.参