2022年数据结构试题及答案详解参照 .pdf

《2022年数据结构试题及答案详解参照 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试题及答案详解参照 .pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构试题一、选择题（每小题 2分，共 30分）1 若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（）存储方式最节省时间。A、单链表B、双链表C、单向循环D、顺序表2 串是任意有限个（）A、符号构成的序列B、符号构成的集合C、字符构成的序列D、字符构成的集合3 设矩阵 A（aij，l i,j 10）的元素满足：aij 0(i j,l i,j 10)aij=0(ij,l i,j 10)现将 A 的所有非 0元素以行序为主序存放在首地址为2000 的存储区域中，每个元素占有4个单元，则元素A95 的首址为A、2340 B、2336 C、2164 D、2160 4 如果

2、以链表作为栈的存储结构，则退栈操作时（）A、必须判别栈是否满B、对栈不作任何判别C、必须判别栈是否空D、判别栈元素的类型5 设数组 Data0.m 作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为（）A、front=front+1 B、front=(front+1)%m C、rear=(rear+1)%m D、front=(front+1)%(m+1)6 深度为 6（根的层次为 1）的二叉树至多有（）结点。A、64 B、32 C、31 D、63 7 将含 100 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为 1

3、。编号为 49 的结点 X 的双亲编号为（）A、24 B、25 C、23 D、无法确定名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -8 设有一个无向图G=（V，E）和 G=（V，E）如果 G 为 G 的生成树，则下面不正确的说法是（）A、G 为 G 的子图B、G 为 G 的边通分量C、G 为 G 的极小连通子图且V=V D、G 为 G 的一个无环子图9 用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）A、一定都是同义词B、一定都不是同义词C、都相同D、不一定都是同义词10 二分查找要求被查找的表是（）A、键值有序的链接表B、链接表但键值不一定有序

4、C、键值有序的顺序表D、顺序表但键值不一定有序11 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（）A、n2 B、nlog2n C、log2n D、n-1 12 堆是一个键值序列k1,k2,kn,对 i=1,2,|_n/2_|,满足()A、ki k2i k2i+1 B、kik2i+1k2i C、ki k2i 且 ki k2i+1(2i+1 n)D、ki k2i 或 ki k2i+1(2i+1 n)13 一个具有n 个顶点的无向完全图的边数为（）A、n(n+1)/2 B、n(n-1)/2 C、n(n-1)D、n(n+1)14 在索引顺序表中查找一个元素，可用的且最快的方

5、法是（）A、用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找B、用顺序查找法确定元素所在块，再用二分查找法在相应块中查找C、用二分查找法确定元素所在块，再用顺序查找法在相应块中查找D、用二分查找法确定元素所在块，再用二分查找法在相应块中查找15 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。A、单链表B、双链表C、带头结点的双循环链表D、容量足够大的顺序表二、判断题（每小题 1分，共 10分）名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -1双链表中至多只有一个结点的后继指针为空。（）2在循环队列中

6、，front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队列为满的条件是front=rear。（）3对链表进行插入和删除操作时，不必移动结点。（）4栈可以作为实现程序设计语言过程调用时的一种数据结构。（）5在一个有向图的拓朴序列中，若顶点a 在顶点 b 之前，则图中必有一条弧。()i 6对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。()7“顺序查找法”是指在顺序表上进行查找的方法。（）8向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9键值序列 A，C，D，E，F，E，F是一个堆。10 二路归并时

7、，被归并的两个子序列中的关键字个数一定要相等。（）三、填空题（每小题 2分，共 20分）1在带有头结点的单链表L 中，若要删除第一个结点，则需执行下列三条语句：；L-next=U-next；free(U)；2有一个长度为 20的有序表采用二分查找方法进行查找，共有个元素的查找长度为 3。3采用冒泡排序对有n 个记录的表A 按键值递增排序，若L 的初始状态是按键值递增，则排序过程中记录的比较次数为。若A 的初始状态为递减排列，则记录的交换次数为。4在无头结点的双链表中，指针P 所指结点是第一个结点的条件是。5G 为无向图，如果从G 的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该

8、图一定是图。6如果一个有向图中没有，则该图的全部顶点可能排成一个拓扑序列。7深度为 8（根的层次号为1）的满二叉树有个叶子结点。8将一棵有 100 个结点的完全二叉树按层编号，则编号为 49的结点 X，其双亲 PARENT（X）的编号为。名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -9设某闭散列表HT 未满，散列函数H（KEY）为键值第一字母在字母表中的序号，处理冲突方法为线性探测法，请在下列算法划线处填上适当内容，以实现按键值第一字母的顺序输出闭散列表中所有键值的算法。void printword(keytype HTm)for(i=1;idata=x;p-next

9、=NULL；四、简答题：（每小题 4分，共 20 分）1.对于一个有 10000 个结点的二叉树，树叶最多有多少个？最少有多少个？2.已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和 DGEBHFCA，则该二叉树的前序序列是什么？3.设有 1000 个无序的元素，需排出前10 个最大（小）的元素，你认为采用哪种排序方法最快？为什么？4.在 KMP 算法中，已知模式串为ADABCADADA，请写出模式串的nextj 函数值。5.中序遍历的递归算法平均空间复杂度为多少？五、算法设计题（每小题 10分，共 20 分）名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -

10、1.试编写一个算法，判断一给定的整型数组an 是不是一个堆。2.一棵二叉树的繁茂度定义为各层结点数的最大值与树的高度的乘积。试写一高效算法，求二叉树的繁茂度。参考答案一、选择题1、D 2、C 3、D 4、C 5、D 6、D 7、A 8、B 9、D 10、C 11、D 12、C 13、B14、C15、D二、判断题1.2.3.4.5.6.7.8.9.10.三、填空题1U=L-next 24。3n-1、n(n-1)/2。4p-prior=NULL。5连通6回路或环728-1=27=128 824 9HTj!=NULL或 HTj 不为空、H(HTj)=I 10 rear-next=p、rear=p 四

11、、简答题：1.答：最多是完全二叉树的形态，即5000 个叶子；最少是单支树的形态，即1个叶子。2.答：是：ABDEGCFH 3.答：用锦标赛排序或堆排序很合适，因为不必等全部元素排完就能得到所需结果，时间效率为O(nlog2n)；即 O（1000log21000）=O(10000)锦标赛排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9 10=1089 堆排序的准确比较次数为：n-1+9log2n=999+9log21000=999+9 10=1089 若 用 冒 泡 排 序 也 较 快，最 多 耗 费 比 较 次 数 为（n-1+n-2+n-10）名师资料总结

12、-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -=10n-55=10000-55=9945（次）4.答：0112112343 5.答：要考虑递归时占用了栈空间，但递归次数最多不超过树的高度，所以空间复杂度为O(log2n)五、算法设计题1.解：提示：堆的定义是：kik2i 和 K2i1 void SortA(sqlist&A,int n)if(n=0)return(0);/空表if(a1a2)for(i=1;ia2*i|aia2*i+1)return(-1);return(minleap);else for(i=1;i=n/2;i+)if(aia2*i|ailchild)EnQueue(Q,r.node-lchild,r.layer+1);if(r.node-rchild)EnQueue(Q,r.node-rchild,r.layer+1);/按层序入队时要随时标注结点所在层号h=r.layer;/最后一个队列元素所在层就是树的高度for(maxn=count0,i=1;h;i+)if(countimaxn)maxn=counti;/求出哪一层结点数最多return(h*maxn)/Width 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -