北京大学 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-1>ai)&&(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