2018北大计算机801考研真题回忆版第二版.pdf
北京大学 2018 年研究生入学试题 made by“北大信科 20 年考研 “群全体成员 数据结构部分 一、选择题(每小题 2 分): 1. 算法复杂度 :已知下面一串代码,求其算法时间复杂度: int s = i = 0; while(s :王道 2017 年真题本质是一样的 2. 线性表 :下面关于线性表的叙述中,不正确的是哪些 ( )? A、采用顺序存储的线性表,必须占用一片连续的存储单元; B、 采用顺序存储的线性表,便于进行插入和删除操作; C、采用链接存储的线性表,不必占用一片连续的存储单元; D、采用链接存储的线性表,便于插入和删除操作; 线性表的存储结构 链接和顺序 3. 栈混洗 : 给了一个字符串 HAPPY, 按照这个顺序入栈 , 则出栈顺序不可能是是哪个() A. HAYPP B. HPPAY C. HYAPA D. HAPPY :栈混洗类题目,群里有具体算法代码,但是一般只考选择题,具体算法思想:采用一个中间栈来记录每段小栈的信息。复杂度 o( n2) 4. 图的邻接矩阵 :某连通图的邻接矩阵为 A。若点 i 到点 j 存在一条长度为 m 的路径,那么可以看哪个矩阵 aij 是否为 1 ( ) A. A B. mA C. Am D. A(m-1) : 5. DFS, BFS,连通图相关概念 请 问以下说法正确的是: A. 广度优先搜索是先进后出; B. 连通图的 MST 是极大连通子图 C. 深度优先搜索是递归实现的; D. 每次深度优先搜索都能得到一个连通分支 ; : 6. 二叉树的前,中,后遍历相关类型题 :叶节点相对顺序 前中后序遍历是否一样 ( ) A. 完全一样 B. 完 全不一样 C. 前序和后序一样 D. 前序和中序一样 7. 森林,二叉树转换 :若森林 F 对应的二叉树 B 中有 m 个点, B 的根节点 r 的右子树具有 n 个节点,那么森林 F 中第 1 颗树的结点个数为: A、 m-n B、 m-n-1 C 、 n+1 D、不确定 不难,基础题 8. 散列表,二次查找法 :哈希值为 key%11 哈希表长 14 线性表插入到 15, 38, 61, 84, 8,最后插入 49,那么利用二次探测法, 49 应该放在下标为多少的表项中? A. 3 B. 5 C. 8 D. 9 9. b 树与 b+树 : B+树不同于 B 树的特点之一是 A、 B+树与 B 树都是 AVL 树 ; B、结点中含有关键字 C、 B 树和 B+树都有效支持顺序查找 D、 B 树和 B+树都有效支持随机查找 : b 树和 b+树是否支持随机查找和顺序查找 10. :针对以下无向连通图从点 1 开始,使用 Dijkstra 算法寻找单源最短路径,依次加入的点是() 图表 1无向连通图 A. ? B. ? C. ? D. ? :给了一个图,让给出根据算法所得到的次序 ,王道上面许多题目类似 11. 归并段、四路归并, WPL :若初始归并段大小分别为, 5 9 12 13 14 16 17 18 20 28 30 37 42,那么最佳归并树的带权路径长度 WPL 是 ( ) A. 460 B. 472 C. 480 D. 486 : 二、简答题(第一题 6 分,第二题 8 分,第三题 9 分): 1、一颗空 AVL 树中,顺序插入 5, 9, 4, 2, 1, 3, 8 : ( 1)、严格遵循 AVL 操作,画出插入后的 AVL 树 ; ( 2)、全部插入后,求等概率下的查找成功的平均检索长度 。 2、二叉树的内部路径长度: 假设 N 个互不相同的随机元素插入一棵空二叉搜索树,证明得到的二叉搜索树的内部路径长度期望为 O( NlogN)。 3、 给定一个长度为 N 的数组,保证其中至多存在 C 个极值点 Cai 为极值点,则满足1ai+1)或者 (ai-1ai)&(ai考虑到电路的复杂性与延迟, ALU 的加法器实现通常是由: A. 多个小规模超前进位加法器组成 B. 多个 小规模超前进位加法器和行波进位加法器级联而成 C. 大规模行波进位加法器组成 D. 大规模超前进位加法器组成 6. 程序查询、中断、 DMA 三种方式的概念题? 下列关于程序查询、中断、 DMA 的三种方说法正确的是 A. DMA 对外部输入输出的响应实时性最高; B. 中断仍需要经过 CPU 寄存器传输数据 C. 除程序查询方式外,中断和 DMA 都不再需要编写程序执行 D. DMA 总是性能最高 7. 中断向量表存储的是? A. 中断服务程序的入口地址 B. 中断号 ? C. 中断状态字 D. ? 8. 路组相联的一个计算 Cache 采用 4 路 组相联 每块 32B 16 组(编号 0-15),请问 0xDEADBEEF映射到哪一组? A . set7 B . set11 C . set13 D . set15 9. 流水 1 线的相关概念题 下面关于流水线说法正确的是 ( ) A. 通过不断加深流水线的级数,流水线的效率可以不断提高 B. 流水段的平均延迟影响了流水线的最高频率 ? C. 流水线中的冒险都可以通过插入流水线停顿来解决 D. ? 10. 磁盘的转速为 7200RPM,寻道时间为 9ms,每个磁道有 400 个扇区,数据分布均匀,问读取一个扇区的平均时间 ( ) A. 4.12ms B. 9.42ms C. 7.56ms D. 5.74ms 11.关于硬布线控制器和微指令控制器的对比,下列说法正确的是() A. 微指令控制器执行效率更高 B. 硬布线控制器电路组织更简单 C. 硬布线控制器指令执行效率更高 D. 硬布线易于扩展和修改功能 二、 解答题(第一题 9 分,第二题 14 分) 1. ( 1)给出了一个未优化的乘法器的线路图,请描述乘法器的运行步骤,请用流程图和文字描述其工作过程 ; ( 2)该乘法器还可以优化,请画出优化后的乘法器的线路图,并描述做了哪些优化。 图表 2 乘法器 2.( 1)、将 MIPS 指令集精简为 MIPSLite 指令集 ,包括 ADDU SUBU ORI LW SW BEQ。 CPU 数据通路图如下: 图表 32 CPU 数据通路图 (2)、分析指令需求以集成控制信号,请填写下列表格。 图表 4 需要进行填写 ( 3)若将如上单周期处理器改造成为流水线处理器,拥有五个流水段 F(取值 )、 D(译码 )、E(执行 )、 M(访存 )、 W(写回 ),那么流水线会产生哪些冒险?举例说明。 针对以上冒险,若要优化流水线,应该增加什么部件或者怎样修改部件,请用文字描述 。 操作系统 一、选择题(每题 2 分) 1. 根据操作系统进程五状态图 (图 *),判断进程状态哪个对? 图表 5操作系统进程五状态图 ,网上盗图,有厉害的大佬可以把里面状态换成 1,2,3,4,5,再添上去,谢谢 A. 1-创建态 B. 2-新建 C. 3-就绪 D. 4-阻塞 :原题就是把里面五个状态换成 1, 2, 3, 4, 5,让你猜里面的哪一个是正确的 2. 问什么时候不一定会发生进程切换? A. 进程时间片用完 B. 当进程创建了一个子进程之后 C. 进行读盘操作 D. 进程运行过程中产生了异常 3. 安全状态和死锁的关系? 类似题:关于死锁状态与不安全状态的关系,下列描述正确的有:() A. 死锁是一种不安全状态 B. 系统处于不安全状态,一定产生了死锁 C. 不安全状态是死锁的必要条件 D. 不安全状态是死锁的充分条件 4. 使用 LRU,问哪个被换出? 题目给出了页号,页框号,修改位,访问位, T 时间内访问的次数 A. ? B. ? C. ? D. ? 5. 给了信号量的定义,问 N 个进程竞争一个资源,需要几个信号量? 给出 P( S) V( S)的实现代码 A. 1 B. N C. N-1 D. N+1 6. 给定页表大小为 512,指令存了 2 页,数据存 1 页,然后给了一段程序要初始化一个1024*1024 的矩阵,问缺页多少次?(其中数组 A10241024,页表大小为 512B , Ai,j:=0) A. 1024*1024 B. 1024*512 C. 1024*1 D. 1024*2 7. 关于 FAT 文件系统下列说法不正确的是( ) A. FAT 文件系统文件名区分大小写 B. FAT 文件系统文件的物理结构是链式组织 C. FAT 文件系统为了提高效率,采用了目录项分解的方法 D. ? 8. 问下列哪些操作不是为了提升文件系统性能(目录项分解等)? A. 目录项分解 B. 文件高速缓存 C. 磁盘调度算法 D. 异步 I/O 9. 下列关于死锁的选项,哪一个是不正确的 ( ) A、 安全状态一定不会发生死锁; B、 不安全状态一定会发生死锁; C、 不安全状态就是死锁 D、? 10. 死锁 与 安全状态 : 下列关于死锁与安全状态的叙述中,哪一个是正确的? A.死锁状态一定是不安全状态 B.从安全状态有可能进入死锁状态 C.不安全状态就是死锁状态 D.死锁状态有可能是安全状态 二、 解答题(第一题 10 分,第二题 5 分) 1. 操作系统实现了 20 条系统调用,现在要添加一个名为 Syscall21 的系统调用,有 3 个参数输入,问: (1)、要实现这个函数硬件需要支持什么功能? (2)、问操作系统需要做什么操作? (3)、 编译器需要提供什么样的支持? :跟 17 年的简答差不多 2、 请写出多级反馈队列的原理,并简述如何它是如何进行调度的,详细论述如何对待 CPU密集型进程 /和 I/O 密集型进程。 :往年考的是 PV 操作,现在变成了多级反馈队列的处理,进程调度 计算机网络 一 . 选择题(每题 2 分) 1. 下列选项正确的是: ( ) A. 频分多用每个用户可以一直占用全部信道带宽; B. 时分多用每个用户可以一直占用全部信道带宽; C. 码分多用 每个用户可以一直占用全部信道带宽; D. 码分多用 每个用户不可以一直占用全部信道带宽; 2. ( 2 道)关于报文交换和电路交换,下列说法正确的是? A. 报文交换的转发速度要快于电路交换 B. 电路交换的转发速度要快于报文交换 C. 当数据经过交换机时,报文交换需要将数据存储然后转发 D. 当数据经过交换机时,电路交换需要将数据存储然后转发 3. 802.3 协议概念题(如是否可靠) 以下关于 802.3 协议的正确 选项是 ( )