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

长风破浪会有时，直挂云帆济沧海。东北大学23春“计算机科学与技术”《数据结构Ⅱ》考试历年高频难、易错点试题甄选答案附答案（图片大小可自由调整）第I卷一.综合考核(共12题)1.树的先根序列等同于与该树对应的二叉树的()。A.先序序列B.中序序列C.后序序列D.层序序列参考答案：A2.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为()。D.17参考答案：C3.在下列各种文件中，不能进行顺序查找的文件是A.顺序文件B.索引文件C.散列文件D.多重表文件参考答案：C4.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是B.先序C.从根开始的层次遍历D.中序参考答案：A5.已知广义表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))))参考答案：C6.按排序过程中依据的原则分类，快速排序属于A.选择类的排序方法B.插入类的排序方法D.交换类的排序方法参考答案：D7.下面关于数据结构正确的说法是A.相互之间存在一种或多种特定关系的数据元素的集合B.数据的存储结构D.一种数据类型参考答案：A8.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为()。A.4，4，3C.3，4，4D.3，3，49.在用邻接表表示图时，拓扑排序算法时间复杂度为()。B.O(n+e)C.O(n*n)D.O(n*n*n)参考答案：B10.在一个单链表中，若删除*p结点的后继结点，则执行操作()。C.p->next=q->next;free(p->next)A.4B.5C.8D.9参考答案：C12.对关键字序列(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)参考答案：B第II卷1.已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于()。A.1.0B.2.9C.3.4D.5.5参考答案：B2.二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标为j=1，2，…，10。设每个字符占一个字节，若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是()。B.A[3，10]C.A[5，8]3.栈的两种常用存储结构分别为A.顺序存储结构和链式存储结构B.顺序存储结构和散列存储结构C.链式存储结构和索引存储结构D.链式存储结构和散列存储结构参考答案：A4.稠密索引是在索引表中()。A.为每个记录建立一个索引项B.为每个页块建立一个索引项C.为每组记录建立一个索引项D.为每个字段建立一个索引项参考答案：AA.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点参考答案：CA.DEBAFCB.DEFBCAC.DEBCFA参考答案：B7.下列编码中属于前缀编码的是()。A.{1，01，000，001}B.{1，01，011，010}D.{0，1，00，11}参考答案：A8.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为()。A.1和5B.2和4D.5和1A.210.已知广义表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))))参考答案：C11.若有序表的关键字序列为