2022年计算机数据结构今年考研真题及答案.docx
《2022年计算机数据结构今年考研真题及答案.docx》由会员分享,可在线阅读,更多相关《2022年计算机数据结构今年考研真题及答案.docx(41页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选学习资料 - - - - - - - - - 2022 1.为解决电脑与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机就依次从该缓冲区中取出数据;该缓冲区的规律结构应当是4.以下二叉排序树中,满意平稳二叉树定义的是5.已知一棵完全二叉树的第 叉树的结点个数最多是6 层设根为第 1 层有 8 个叶结点,就完全二A.只有 II B.I 和 II C.I 和 III D.I 、II 和 III 7.以下关于无向连通图特性的表达中,正确的选项是8.以下表达中,不符合m 阶 B 树定义要求的是9.已知关键序列 5,8,12,19,28,20,15
2、,22 是小根堆最小堆,插 入关键字 3,调整后得到的小根堆是A3,5,12, 8,28,20,15,22,19 B.3,5,12,19,20,15,22,8,28 C3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19 10.假设数据元素序列 11,12,13,7,8,9,23,4,5 是采纳以下排序方 法之一得到的其次趟排序后的结果,就该排序算法只能是41.10 分带权图权值非负,表示边连接的两顶点间的距离的最短路 径问题是找出从初始顶点到目标顶点之间的一条最短路径;假定从初始顶点到目标顶点之间存在路径,现有一种解决该问题的方法:设最短路径初始
3、时仅包含初始顶点,令当前顶点 挑选离 u 最近且尚未在最短路径中的一个顶点 改当前顶点 u=v;重复步骤,直到 u 是目标顶点时为止;u 为初始顶点;v,加入到最短路径中,修名师归纳总结 - - - - - - -第 1 页,共 23 页精选学习资料 - - - - - - - - - 请问上述方法能否求得最短路径?假设该方法可行,例说明;请证明之; 否就,请举42.15 分已知一个带有表头结点的单链表,结点结构为 data link 假设该链表只给出了头指针list;在不转变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第 k 个位置上的结点 k 为正整数;假设查找 胜利,算法输出
4、该结点的 data值,并返回 1;否就,只返回 0;要求:1描述算法的基本设计思想2描述算法的具体实现步骤3依据设计思想和实现步骤, 采纳程序设计语言描述算法 使用 C 或 C+ 或 JAVA 语言实现,关键之处请给出简要注释;2022 1、假设元素 a,b,c,d,e,f依次进栈,答应进栈、退栈操作交替进行;但不答应连续三次进行退栈工作,就不行能得到的出栈序列是A:dcebfa B:cbdaef C :dbcaef D :afedcb 2、某队列答应在其两端进行入队操作,但仅答应在一端进行出队操作,就 不行能得到的次序是A:bacde B :dbace C :dbcae D :ecbad 3
5、、以下线索二叉树中用虚线表示线索,符合后序线索树定义的是4、在以下所示的平稳二叉树中插入关键字 48 后得到一棵新平稳二叉树, 在 新平稳二叉树中, 关键字 37 所在结点的左、 右子结点中储存的关键字分别是 A:13,48 B :24,48 C :24,53 D :24,90 5、在一棵度为 4 的树 T 中,假设有 20 个度为 4 的结点, 10 个度为 3 的结 点, 1 个度为 2 的结点, 10 个度为 1 的结点,就树 T 的叶节点个数是A:41 B :82 C :113 D :122 名师归纳总结 - - - - - - -第 2 页,共 23 页精选学习资料 - - - -
6、- - - - - 6、对 nn 大于等于 2 个权值均不相同的字符构成哈夫曼树,关于该树的表 达中,错误的选项是A:该树肯定是一棵完全二叉树 B:树中肯定没有度为 1 的结点 C:树中两个权值最小的结点肯定是兄弟结点 D:树中任一非叶结点的权值肯定不小于下一任一结点的权值7、假设无向图 G-V.E中含 7 个顶点,就保证图 通的,就需要的边数最少是A:6 B :15 C :16 D :21 G在任何情形下都是连8、对以下图进行拓补排序,可以得到不同的拓补序列的个数是eadcbA:4 B :3 C :2 D :1 9、已知一个长度为 16 的次序表 L,其元素按关键字有序排列,假设采纳折 半查
7、找法查找一个不存在的元素,就比较次数最多是A:4 B :5 C :6 D :7 10、采纳递归方式对次序表进行快速排序,以下关于递归次数的表达中,正确的选项是A:递归次数与初始数据的排列次序无关 B:每次划分后,先处理较长的分区可以削减递归次数 C:每次划分后,先处理较短的分区可以削减递归次数 D:递归次数与每次划分后得到的分区处理次序无关 11、对一组数据 2,12,16,88,5,10进行排序,假设前三趟排序结果 如下 第一趟: 2,12,16,5,10,88 其次趟: 2,12,5,10,16,88 第三趟: 2,5,10,12,16,88 就采纳的排序方法可能是:A:起泡排序 B :希
8、尔排序 C :归并排序 D :基数排序问题: 1请画出所构造的散列表;2分别运算等概率情形下, 查找胜利和查找不胜利的平均查找长度;42.13 分设将 nn,1 个整数存放到一维数组R 中,试设计一个在时间和空间两方面尽可能有效的算法, 将 R 中保有的序列循环左移 P0 P n个位置,即将 R 中的数据由 X0X1 Xn-1变换为 XpXp+1 Xn -1X0X1 Xp-1要 求:1给出算法的基本设计思想;2依据设计思想, 采纳 C 或 C+ 或 JAVA语言表述算法关键之处给出注释;3说明你所设运算法的时间复杂度和空间复杂度2022 名师归纳总结 - - - - - - -第 3 页,共
9、23 页精选学习资料 - - - - - - - - - 1. 设 n 是描述问题规模的非负整数,下面程序片段的时间复杂度是 x = 2; while x n/2 x = 2*x; A.Olog2n B.On C.On log2n D.On2 3. 已知循环队列储备在一维数组 A0.n-1 中,且队列非空时 front 和 rear 分别指向队头元素和队尾元素; 假设初始时队列为空, 且要求第 1 个进入队列的 元素储备在 A0 处,就初始时 front 和 rear 的值分别是 A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1 4. 假设一棵完全二叉树有768 个结点,
10、就该二叉树中叶结点的个数是5. 假设一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和 4, 3, 2, 1,就该二叉树的中序遍历序列不会是A.1, 2, 3, 4 B.2, 3, 4, 1 C.3, 2, 4, 1 D.4, 3, 2, 1 6. 已知一棵有 2022 个结点的树,其叶结点个数为 中无右孩子的结点个数是116,该树对应的二叉树7. 对于以下关键字序列, 不行能构成某二叉排序树中一条查找路径的序列是 A.95, 22, 91, 24, 94, 71 B.92, 20, 91, 34, 88, 35 C.21, 89, 77, 29, 36, 38 D.12, 2
11、5, 71, 68, 33, 34 8. 以下关于图的表达中,正确的选项是 I. 回路是简洁路径 II. 储备稀疏图,用邻接矩阵比邻接表更省空间 假设有向图中存在拓扑序列,就该图不存在回路 III.A.仅 II B. 仅 I 、II C. 仅 III D. 仅 I 、III 9. 为提高散列 Hash 表的查找效率,可以实行的正确措施是 I. 增大装填 载 因子 设计冲突 碰撞 少的散列函数 II. III. 处理冲突 碰撞 时防止产生集合 积累 现象 A.仅 I B. 仅 II C. 仅 I 、II D. 仅 II 、III 10. 为实现快速排序算法,待排序序列宜采纳的储备方式是11. 已
12、知序列 25, 13, 10, 12, 9是大根堆,在序列尾部插入新元素18,将其再调整为大根堆,调整过程中元素之间进行的比较次数是41.8 分 已知有 6 个顶点 顶点编号为 0 5 的有向带权图 G,其邻接矩阵 A 为 上 三 角 矩 阵 , 按 行 为 主 序 行 优 先 保 存 在 如 下 的 一 维 数 组 中 ;要求: 1 写出图 G的邻接矩阵 A;2 画出有向带权图 G;3 求图 G的关键路径,并运算该关键路径的长度;名师归纳总结 - - - - - - -第 4 页,共 23 页精选学习资料 - - - - - - - - - 42.15 分 一个长度为 LL 1 的升序序列
13、S,处在第 L/2 个位置的数称为S的中位数;例如,假设序列S1=11, 13, 15, 17, 19,就 S1 的中位数是 15;两个序列的中位数是含它们全部元素的升序序列的中位数;例如,假设 S2=2, 4, 6, 8, 20,就 S1 和 S2的中位数是 11;现有两个等长升序序列 A 和 B,试设计 一个在时间和空间两方面都尽可能高效的算法,找出两个序列 A 和 B 的中位数;要求 :1 给出算法的基本设计思想;2 依据设计思想, 采纳 C或 C+或 JAVA语言描述算法, 关键之处给出注释;3 说明你所设运算法的时间复杂度和空间复杂度;2022 1、求整数 nn0阶乘的算法如下,其时
14、间复杂度是 intfactintn ifn=1return1; returnn*factn-1; A.Olog2n B.On C.nlog2n D.On2 2、已知操作符包括+、-、* 、达式 a+b-a*c+d/e-f+g 转换为等价的后缀表达式/、和;将中缀表ab+acd+e/f-*-g+时,用栈来存放临时仍不能确定运算次序的操作符,假设栈初始时为空, 就转换过程中同时保存栈中的操作符的最大个数是 3、假设一颗二叉树的前序遍历序列为 a,e,b,d,c,后续遍历序列为 b,c,d,e,a,就根节点的孩子节点 4、假设平稳二叉树的高度为 6,且全部非叶节点的平稳因子均为 1,就该平衡二叉树的
15、节点总数为 5、对有 n 个节点、 e 条边且使用邻接表储备的有向图进行广度优先遍历,其算法时间复杂度 A.On B.Oe C.On+e D.On*e 6、假设用邻接矩阵储备有向图,矩阵中主对角线以下的元素均为零,就关于该图拓扑序列的结构是 A.存在,且唯独 B.存在,且不唯独7、如下有向带权图,假设采纳迪杰斯特拉Dijkstra 算法求源点 a 到其他各顶点的最短路径,得到的第一条最短路径的目标顶点是 b,其次条最短路径的目标顶点是 c,后续得到的其余各最短路径的目标顶点依次是 A.d,e,f B.e,d,f C.f,d,e D.f,e,d 名师归纳总结 - - - - - - -第 5 页
16、,共 23 页精选学习资料 - - - - - - - - - 8、以下关于最小生成树的说法中,正确的选项是 、最小生成树的代价唯独 、全部权值最小的边肯定会显现在全部的最小生成树中、使用普里姆 Prim算法从不同顶点开头得到的最小生成树肯定相同相同、使用普里姆算法和克鲁斯卡尔Kruskal算法得到的最小生成树总不、9、已知一棵 3 阶 B-树,如以下图所示;删除关键字 78 得到一棵新 B-树,其最右叶结点中的关键字是 B.60,62 C.62,65 10、在内部排序过程中, 对尚未确定最终位置的全部元素进行一遍处理称为一趟排序; 以下排序方法中, 每一趟排序终止都至少能够确定一个元素最终位
17、置的方法是 .简洁项挑选择排序.希尔排序.快速排序.堆排序.二路归并排序、11对一待排序序列分别进行折半插入排序和直接插入排序,的不同之处是 两者之间可能二、问答题;41、10 分设有 6 个有序表 A、B、C、D、E、F,分别含有 10、35、40、50、60 和 200 个数据元素,各表中元素按升序排列;要求通过 5 次两两合并,将 6 个表最终合并成 1 个升序表, 并在最坏情形下比较的总次数到达最小;请答复以下问题;1给出完整的合并过程,并求出最坏情形下比较的总次数;2依据你的合并过程,描述 NN2个不等长升序表的合并策略,并说明理由;42、 13 分假定采纳带头结点的单链表储存单词,
18、当两个单词有相同的后时缀,就可共享相同的后缀储备空间,例如,“loaging” 和“being” ,如以下图所示;名师归纳总结 - - - - - - -第 6 页,共 23 页精选学习资料 - - - - - - - - - 设 str1 和 str2 分别指向两个单词所在单链表的头结点,链表结点结构为data,next,请设计一个时间上尽可能高效的算法,找出由 str1 和 str2 所指向两个链表共同后缀的起始位置如图中字符1给出算法的基本设计思想;i 所在结点的位置 p;要求:2依据设计思想,采纳 C 或 C+或 java 语言描述算法关键之处给出注释;3说明你所设运算法的时复杂度;2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022 计算机 数据结构 今年 考研 答案
限制150内