【盛世清北】北大计算机科学与技术(智能科学与技术)考研笔记-北大考研辅导培训班

1、盛世清北】北大计算机科学与技术（智能科学与技术）考研笔记北大考研辅导培训班盛世清北分享：2020 年注定是不平凡的一年，虽然受到疫情的影响，北大考研复试推迟数日，但是丝毫不 会阻止 2021 届考生备考北京大学考研的决心。俗话说“早起的鸟儿有虫吃”基础差的同学更该要早做准备，早规划。 为了帮助考生在北大考研中能成功上岸，盛世清北整理了北大各专业相关复习资料。 北大计算机科学与技术（智能科学与技术）考研考试科目： 1 0 1 思 想 政 治 理 论 2 0 1 英 语 一 3 0 1 数 学 一 8 0 1 计 算 机 专业基础北大计算机科学与技术（智能科学与技术）考研参考书：1数据结构与算法，

2、张铭、王腾蛟、赵海燕，2008-06 ，高等教育出版社，普通高等教育“十一五”国家级规划教材；2计算机组成与设计：硬件与软件接口，David Patterson & John Hennessy 著，英文版第 4 版，机械工业出版社；3微型计算机基本原理与应用，王克义编著，第二版，北京大学出版社；4现代操作系统（原书第 4 版），（荷） Andrews S. Tanenbaum 著，陈向群、马洪兵 等译，机械工业出版社， 2017-07 ；5操作系统精髓与设计原理（原书第8版），（美） William Stallings 著，陈向群、陈渝译，电子工业出版社， 2017-03 ；6计算机网络 （

3、中英文 ） 第五版， Andrew S. Tanenebaum and David J. Wetherall,清华出版社， 2012-03 。盛世清北建议参考书的阅读方法：目录法： 先通读各本参考书的目录， 对于知识体系有着初步了解， 了解书的内在逻辑结 构，然后再去深入研读书的内容。体系法：为自己所学的知识建立起框架， 否则知识内容浩繁， 容易遗忘，最好能够闭上 眼睛的时候，眼前出现完整的知识体系。问题法： 将自己所学的知识总结成问题写出来， 每章的主标题和副标题都是很好的出题 素材。尽可能把所有的知识要点都能够整理成问题。北大计算机科学与技术（智能科学与技术）考研真题：北京大学 801 计

4、算机专业基础考研历年真题 ： 数据结构：1. 写出 AVL 树并计算平均查找长度。2. n 个数组成二叉树，证明排序时间复杂度为 O（nlogn） （ 这个记忆得有点模糊 ）3. 一个数组，有最多 X 个极值，设计一个时间复杂度尽可能低的算法。、 计算机体系结构：1. 结合流程图阐述乘法器的工作原理，然后对其改进。2. MIPS 指令集计算机网络：一个用户通过交换机，集线器向另一个用户发送 IP 报文，问交换机的作用，源地址和 目的地址。北京大学 801 计算机基础 2018 年研究生入学试题1. 算法复朵度丈具体已知下血一串代码.求英算法时间复杂度: int s =i = 0;while(s

5、n)s +二 i; i+;)v备注；王道2017年真題本质是一样的A、O(N)B、O(NA2)C、O(logN)D、类似这样的答案2. 线性表龙具体下面关于线性表的叙述中，不帀确的是哪些()?A、采用顺序存储的线性表,B、采用顺序存储的线性表,C、采用链接存储的线性表,D、采用链接存储的线性表,必须占用一片连续的存储单元; 便于进行插入和删除操作.不必占用一片连续的存储单兀, 便丁插入和删除操作；备注承线性表的荷储结构链接和顺序3. 栈混洗具体：给了个字符串HAPPY.按照这个顺序入栈，则岀栈師序不可能是是卯个()A. HAYPPB. HPPAYC. HYAPAD. HAPPY备注:栈混洗类题

6、H,群里冇具体算法代码.但是一般只考选择题.具体算法思想： 釆用一个中间枚氷记录毎段小栈的信息。复杂JUo (n2)丄图的邻接矩阵具体：某连通图的邻接矩阵为A若点i到点j存仔一条长麼为m的粘径.那么可以看哪 个矩阵aij是否为1()R mAC. AAmD AA(m-l)v备注：5. IMS, BFS,连通图相关概念【较一版冇更改】对于联通无向图.请问以下说法正确的是：A. 广度优先擾燃是先进后岀：B. 连通開的MST是极大连通于图C. 广喪优先捜索是递归实现的：D. 毎次探哎优先搜索都能得到一个联通分支；v具体：6二叉树的前，中，后遍历相关类型题v具体；叶节点相对顺序前中后序遍历是否一样()A

7、. 完全一样B. 完全不一样C. 前序和后序一样D 前冲和中样一样7. 森林.二叉树转换具体若森林F对应的一叉树R中冇m个点.R的根节点r的右子树貝冇n个节点.那么 徐林F中第I颗树的结点个数为：A、m-n B、m-n-l C、n+l D、不确進缶江:不难，宴砒题&散列农，二次贫找法具体:希值为ke哈希表长14线性衷插入到【15, 38, 61. 84, 8,最后播入49.那么利用二次探测法.49应该放在下标为多少的表顶中？A. 3B. 5C. 8D. 99. b树与b+树其体厂B+树不同B树的待.点之一是A、B树和B+树都是AVL枸R、R树和R+材都能用丁文件系统C、B树和B+树都旳效支持顺

8、斤介找D、B树和B+树都冇效支持随机进找备江： b树和树是否支持馳机責找和顺序查找10. V具体：针对以下无向连通图从点I开始,使用Dijkstra算法寻找单源最短路径.依次 加入的点是()A. ?B. 1、2、4、3、7. 5、balabciluC D. ?备注込给了个图，止给出根岛算法所得到的次序土逍上血许多题R类似11. 归并段、创路归并，WPL o3、恰定 个长喪为N的数组，保i正其中至多存在C个极值点(加为极值点，则満址 KiN(ai-lail)或者(ai-lai)&(akai*l) . C可以看做 个常数请设计 个时 间复余喪尽可能低的算法对N排序计算机组成原理、选择题(111题为

9、单选题，每小題2分)1. 绘岀-串16诳制数()x1234567X90.河用大端法和小瑞法餚存分别堤名少？A. 小端从1 乜址小爼大12 3456 78 90从地址小到人大端D.?2. 3.14的16进制数是XXXX,问它的阶码用二进制表示是峯少？A. ?B. 1000(X)00C. ?D. ?3 问下列儿个哪个不是旳诺依曼结构的基础部件？A. CPU D内存C硕盘D.打印机问主频为多少？4实JUZ 5级沆水线.毎个阶段的运行时长为如(3ms 5ms 2ms 6ms 4ms ),A. I66MHZB. 248MHZC. 333MHZD. ?5.行波进位和超前进位的概念题v貞题考虑到电路的負杂性

10、与延迟.ALU的加法器实现通常是山:A. 务个小规模超前进位加法器耕接而成B. 多个小规模超前进位丿川法器和行波进位加法器级联而成C. 大规模行波进位加法器组成D. 大规模超前进位加法器组成6程序金询、中断、DMA三种方式的概念题？下列关于程序査询、中臥 DMA的三种方说法正确的是A. DMA对外部输入输出的响应实时性最高；B. 中断仍需要经过CPU寄存器传输数据C. 除程序代询方式外，中断和DMA都不再需耍编写程序执行D. DMA总是性能最高7.中断向量表存储的是？A. 中断服务程序的入II地址B. 中断号?C. 中断状态字8. 路组相联的一个计鄭真Cachc采用4路 组相联 每块32B 1

11、6组（编号0-15） , i?f问OxDEADBEEF映射到 哪一组？A. set7B. setllC. sei 13D set 159. 流木1纽的柑关嘅念题v倉趙卜面关于流水线说法iF潇的是（）A. 通过不断加深流水线的级数，流水线的效率可以不断捉高B. 泳水段的平均延迟彤响了流水线的最高频率？C沆水线中的吕险都HJ以通过推入流水线停顿來解决D. ?10. 磁盘的转速为7200RPM.寻道时间为9ms每个碓道有400个扇区，数拐分布均匀,问读奴-个扇区的平均时仙（）A. 4.70msB920msC. 7.56msD. 5.74ms11. 关干硬布线控制岳和微指令控制器的对比，下列说法正确的

12、是（）A. 嶺指令控制器执行效率更高B. 硬布线控制器电路组织更简单C. 谀布线扯制器指令执彳亍效率更高D脱侑线易于扩展和修改功能一、解答題（第一制9分.第一題14分）1. （1给出了 个木比化的乘浓貉的线跑图，讹描述乘法器的运行步骤.讷用流程图和文 字描述挂T作过程：（2）该乘法器还可以代化.请画出比化心的乘达器的线賂图，并描述做了嚨些优化。2. (I) 将 MIPS 令集精简为 MIPSLke 指令集包括 ADDU、SUBU、ORL LW、SW.BEQoCPU数据通路图如下：(2)、分析指令需求以集成控制信号.沽境写下列农格。func opcode(op)100000100010/0000

13、00000000001101100011101011000100addusubuorilwswbeqRegDst10XALUSrc0011MemtoReg001XRegWr1MeraWr0nPC sol0000Ex topX1ALUctr00(ADD)01 (SUB)10(OR)（3）若将加上单用期处理器改造成为旅水线处理器，拥右五个渝水段F（収值）、D（译码）、 E（执行）、M（访存）、W（写回），那么流水线会产生哪些冒险？举例说明.针对以卜.冒险.若耍化化流水线，应该增加什么剂件或者怎样修改祁件，诸用文宁摊I述.操作系统一、选择题（19题为单选题，每题2分）I. W操作系统进稈状态图（图*

14、）判断进秤状态哪个对?A. 1-创建态B 2新建C. 3就绪D. 4-阴塞备注：原题就是把里面査个状态换成I，2. 3, 4. 5让你猜里面的哪一个是正确的2. 问什么时候不-定会发牛进程切换？A. 进程时间片用完B. 当进程创建了一个子进程之后C. 进厅读盘操作D. 进程运行过程中产牛了异常3. 安全状态和死锁的关系？模拟题类似题：关于死锁状态与不安全状态的关系，下列描述正确的冇：（）A. 死锁是一种不安全状态B. 系统处丁不安伞状态，一定产牛了死锂C. 不安全状态是死锁的必要条件D. 不安余状态是死锁的充分条件4. 使用LRU,问哪个被换出？ v给了-个表格以及-些参数題H给出了页号，页框

15、号，修改位，访问位，T时间内访问的次数A. ?B. ?D. ? ?5. 给了信号竝的定义.问N个逬程竞争一个资源.需要几个信号竝？给出P（S） V S）的实现代码A. IB. NCN1I）. N+lI. 给淀页表大小为512宁.抬令177 2页，藪据存1页，然后恰了一段程序更初始化一个 1024* 1024的矩阵，问缺贝娄少次？（其中数组AI 1024| 10241为1MERGER类里贝农人小为 512字,Ai. jJ:=0）A. 1024* 1024B. 1024*512C. 1024D. 1024*26. 关T FAT文件系统下列说広不正确的址（）A. FAT文件系统文件名区分大小写B.

16、卜AT文件系统文件的物理结构於链述绢织C. FAT文件系统为了提岛效率.采用了 R录顶分解的方法D. ? ?II问下列哪些操作不是为了提升文件系统性能录项分解等）？A. 目录项分解B. 文件高速缓存C. 廐盘调度算法D. 异步I/O9.下列关于死锁的选项哪一个是不正确的（）A、安全状态一定不会发牛死锁；B、不安全状态一定会发生死锁；C、不安全状态就是死锁D、？ ？模拟題：下列关r死锁与安全状态的叙述中喺一个是止确的？A. 死锁状态-淀是不安全状态B. 从安全状态冇可能进入死锁状态C. 不安全状态就是死锁状态D. 死锁状态冇可能是安全状态二、解答题（第一题10分，第二题5分1. 操作系统实现了

17、20条系统涮用，现在耍添加 个名为SyaulCI的系统调用，冇3个参数 输入.问：(1) 、歴实现这个函数硕件需藍支持什久功能？(2) 、问操作系统需耍做什么操作？(3) 、编讦容浙耍捏供什么样的支持？备注：跟17年的題答差不名2、沽写出第级反俺从列的讯理.井简述如何它是如何进行渭度的，详细论述如何对待CPU 密集型进阳/和I/O帝集型进程.备注：往年考的是PV操作，现在变成了多级反馈队列的处理，逬程调度计算机网络一.选择题(19也为单选题，每題2分)1. 宜题下列选项正确的耙：()A. 频分多用每个用户可以直虫用全部信道带宽；B. 时分多用稈个用户可以一頁占用全部倍适帘宽；C. 码分名冃毎个

18、用八可以一自人用全部佑逍带宽：D. 码分多用每个用户不可以直占用全部信道带宽；2. (2道)关于报文交换和电路交换.下列说法正确的是？A. 报文交换的转发速度耍快丁电路交换B. 电路交换的转发速度耍快丁报文交换C. 当数据经过交検机时，报文交换眾要将数抵存储然后转发D. 当数据经过交换机时，电路交换需要将数据存储然后转发3. 8023协议概念題(如是否可集)真题以下关F 802.3协议的正确选项是()A. 802.3为上层提供了可靠的数呃服务B. 8O2.3为上层捉供了不可靠的数堀服务c ? 9D. ? ?4802.11协议槪念题(如是否町蹴 是不是解决了隐蔽站问题)？真题a下列关于802,1

19、1协议选项正确的是()A. 802.II提供可靠的单播数据服务B. 8021提供不可靠的多播数据服务C. 802.1 I能解决暴謀节点问题D. 802.11不能解决隐藏结点问题5. IP协议、UDP协议.TCP协议概念题丈真题下列关于UDP协议说沫正确的是（）A. UDP为应用层桃供了不可靠的数据报服务B. UDP皑提供面向连接的服务C. UDP向应用层提供无连接的服务D. UDP为应用层捉供了可靠的数掘报服务6. 数期校验的问趣（如问发送力和接收方是不是用不同的计算公式等）？真题以下关于数据校骏的选顶正确的是O :A. 发送方和接收方计算校骏和的公式不同B. 编码效率与校验位数无关C. 接收方能用校验码检错，就一疋可以用它纠错D. 校验能力越强则编码效越羞7. 问CSMA概念题（比如是不是发失敗后I古I定一段时间再发）？A. CSMA发生碰撞后放弃发送B. ? ?C. C