北京大学2018年计算机考研真题回忆第一版.pdf
北京大学 2018 年研究生入学试题 made by“北大信科 20 年考研 “群全体成员 数据结构部分 一、选择题: 1. 算法复杂度 :已知下面一串代码,求其算法时间复杂度: int s = n = 0; for(int i = 0; a : 王道 2017 年真题本质是一样的 2. 线性表 :下面关于线性表的叙述中,不正确的是哪些 ( )? A、采用顺序存储的线性表,必须占用一片连续的存储单元; B、采用顺序存储的线性表,便于进行插入和删除操作; C、采用链接存储的线性表,不必占用一片连续的存储单元; D、采用链接存储的线性表,便于插入和删除操作; 线性表的存储结构 链接和顺序 3. 出栈 /入栈 : 给了一个字符串 HAPPY(意思就是字符串 “H“,“A“,“P“,“P“,“Y“) , 按照这个顺序入栈 , 则出栈顺序不可能是是哪个 : :栈混洗类题目,群里有具体算法代码,但是一般只考选择题。 具体算法思想:采用一个中间栈来记录每段小栈的信息。复杂度 o( n2) 4. 图、邻接矩阵的算法相关 :邻接矩阵 i 和 j 是否有长度 m 的路径; (,其实就是某年 408 数据结构大题的一个小问,邻接矩阵的 n 次方的第 i 行 j 列表示有没有长度为 n 的路径) 5. 广度优先搜索 图的算法相关 请问 以下说法正确的是: A、广度优先搜索是先进 后 出; B、 C、深度优先搜索是递归实现的; D、 : 6. 二叉树的遍历次序 : 叶节点相对顺序 前中后序是否一样 7. 森林 二叉树之间的转换: :若森林 F 对应的二叉树 B 中有 m 个点, B 的根节点 r 的右子树具有 n 个节点,那么森林 F 中第 1 颗树的结点个数为: A、 m-n B、 m-n-1 C 、 n+1 D、不确定 8. 散列表,二次查找法 : 线性表插入到 4, 5, 6, 7, 8,最后插入个 5,二次探测插在哪个结点? 9. b 树与 b+树 : B+树不同于 B 树的特点之一是 A、能支持顺序查找 B、结点中含有关键字 C、根节点至少有两个分支 D、所有叶节点都在同一层上 : b 树和 b+树是否支持随机查找和顺序查找 10. 最短路问题 Dijkstra 算法 :给了一个图,让给出根据算法所得到的次序 :参考王道上面出的题目 11. 归并段、四路归并, WPL :已知三叉树 T 中 13 个叶子结点的权重分别是 5 9 12 13 14 16 17 18 20 28 30 37 42, T 的带权 (外部路径长度最小是 ( ) : 二、 简答题: 12、一颗空 AVL 树中,顺序插入 5,9,4,2,1,3,8 ( 1)、严格遵循 AVL 操作,画出插入后的 AVL 树 ( 2)、全部插入后,求等概率下的查找成功的平均检索长度 13、二叉树的内部路径长度: 假设 N 个互不相同的随机元素插入一棵空二叉搜索树,证明得到的二叉搜索树的内部路径长度期望为 O( NlogN)。 14、给定一个长度为 N 的数组,保证其中至多存在 C 个极值点 Cai 为极值点,则满足1ai+1)或者 (ai-1ai)&(ai 2. ( 1)给出 MIPS 里几条指令的定义 如 ADDU SUBU ORI LW SW BEQ。还给出了CPU 数据通路图(见 PPT 相应部分),然后给出了 CPU 数据通路图的控制信号的表格,每列代表上述几条指令,每行代表 CPU 数据通路图中各个控制信号(如 RegWr、ALUSrc、 ExtOp、 ALUCtr 等等),然后要求把表格填充完整。(本题答案就是 PPT 上相应的控制信号的表格) ( 2)假如用流水线实现上述的数据通路图,问会产生哪些冒险?举例说明。 图 *( CPU)数据通路图 操作系统 一、选择题 1.给了一个图,判断进程状态哪个对? 2.问什么时候不一定会发生进程切换? 3.安全状态和死锁的关系? 4.使用 LRU,问哪个被换出? 5.给了信号量的定义,问 N 个进程竞争一个资源,需要几个信号量? 6.给定页表大小,指令存了 2 页,数据存 1 页,然后给了一段程序要初始化一个1024*1024 的矩阵,问缺页多少次? 7.问 FAT 中没有实现下面哪个(目录项分解,不区分文件大小写等)? 8.问下列哪些操作不是为了提升文件系统性能(目录项分解等)? 二、解答题 1. 操作系统实现了 20 条系统调用,现在要实现一个函数,有 3 个参数输入,问要实现这个函数硬件需要支持什么功能?问操作系统需要做什么操作? ? :跟 17 年的简答差不多 11、 请写出多级反馈队列的原理,并简述如何它是如何进行 调度 的,详细论述如何对待CPU 密集型进程 /和 I/O 密集型进程 :往年考的是 PV 操作,现在变成了多级反馈队列的处理,进程调度 计算机网络 一、选择题 1.( 2 道)对比报文交换和电路交换? 2. 802.3 协议概念题(如是否可靠)? 3. 802.11 协议概念题(如是否可靠,是不是解决了隐蔽站问题)? 4. IP、 UDP 等协议概念题(是否可靠等)? 5. 数据校验的问题(如问发送方和接收方是不是用不同的计算公式等)? 6. 问 CSMA 概念题(比如是不是 发失败后固定一段时间再发)? 7. 数据链路层和传输层的滑动窗口题(如发送、接受窗口大小是不是都固定)? 二、解答题: 给定一个网络如下图(大致)所示。 H1H15 为主机, S1 S2 为交换机, Hub 为集线器。 119 为端口。假设 IP 的格式为 IP_H1,MAC 的格式为 MAC_H1(以主机 H1 为例)。假设现在刚布置好如下的网络,现在 H1 给 H13 发一个数据包。则回答如下问题: 图表 1 计算机网络 ( 感谢 两位 大佬 供图 +绘图 ) ( 1)、交换机( S1/S2)主要的功能是什么,举例说明? ( 2)、数据帧在 S1 发往 S2 的链路上时,问数据帧的 IP 源地址和目的地址分别是什么? ( 3)、数据帧在 S1 发往 S2 的连路上时,问数据帧的 802.3 数据帧的源地址和目的地址分别是什么? ( 4)、发送完数据包后, S1 和 S2 的哈希表中更新了什么?。 选择题 :连续问了好几个协议的内容,是不是可靠的数据传输,是单播还是组播,等,如APR, NAT, UDP 等,没有网络安全和流媒体协议的题。 数据结构选择题答案: 2. B : 备注:数学有步骤分 。 备注:跟 408 非常像,有历年 408 原题,至少 5 到 6 个;好好刷 408,好好刷华文 mooc 的题目; :数据结构选择 2、 7 均是出自于一个 github 上面的原题 , 网址:https:/github.com/EECS-PKU-XSB/Shared-learning-materials