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

1、盛世清北】北大计算机科学与技术（智能科学与技术）考研笔记 北大考研辅导培训班盛世清北分享: 2020年注定是不平凡的一年，虽然受到疫情的影响，北大考研复试推迟数口，但是丝毫不 会阻止2021届考生备考 北京大学考研的决心。俗话说“早起的鸟儿有虫吃”基础差的同学更该要早做准备，早规划。为了帮助考生在北大考研中能成功上岸，盛世 清北整理了北大各专业相关复习资料。北大计算机科学与技术（智能科学与技术）考研考试科目: 101思想政治理论201英语一301数学一801计算机专业基础北大计算机科学与技术（智能科学与技术）考研参考书:1.数据结构与算法，张铭、王腾蛟、赵海燕,2008-06，高等教育出版社，

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

3、andDavid J. Wetherall,华出版社,2012-03 。盛世清北建议参考书的阅读方法:了解书的内在逻辑结构，然后再去深入研目录法：先通读各本参考书的目录，对于知识体系有着初步了解,读书的内容。体系法：为自己所学的知识建立起框架，否则知识内容浩繁，容易遗忘，最好能够闭上 眼睛的时候，眼前出现完整的知识体系。问题法：将自己所学的知识总结成问题写出来，每章的主标题和副标题都是很好的出题 素材。尽可能把所有 的知识要点都能够整理成问题。北大计算机科学与技术（智能科学与技术）考研真题:北京大学801计算机专业基础考研历年真题：数据结构:1. 写出AVL树并计算平均查找长度。G盛世清北&#

4、174;2. n个数组成二叉树，证明排序时间复杂度为0 (nlogn)(这个记忆得有点模糊)3. 一个数组，有最多X个极值，设计一个时间复杂度尽可能低的算法。、计算机体系结构：1 .结合流程图阐述乘法器的工作原理，然后对其改进。2 . MIPS指令集计算机网络：一个用户通过交换机，集线器向另一个用户发送IP报文，问交换机的作用，源地址和目的地址。北京大学801计算机基础2018年研究生入学试题i.算法复朵度丈具体 :已知卜血一串代码.求英算法时间复杂度：int s =i = 0; While (Sn) S K i; i+；)V备注；王道2017年真题本质是一样的A、O(N)BX 0 (Na2)

5、C、0(I0gN)D、类似这样的答案2.线性表龙具体A下面关于线性表的叙述中，不币确的是哪些()？A、B、C、D、采用顺序存储的线性表, 采用顺序存储的线性表, 采用链接存储的线性表, 采用链惨存储的纬悴天必须占用一片连续的存储单元; 便于进行插入和删除操作.不必占用一片连续的存储单兀, 便丁插入和删除操作；V备注承线性表的荷储结构链接和顺序3.栈混洗具体：给了个字符串HAPPY.按照这个IW序入栈，则出栈如序不可能依个()A. HAYPPB. HPPAYC. HYAPAD. HAPPY备注栈混洗类题H,群里有具体算法代码但是一般只考选择题具体算法思想：采用一个中间枚水记录每 段小栈的信息。复

6、杂JUO (n2)，图的邻接矩阵具体：某连通图的邻接矩阵为A'若点i到点j存仔一条长麽为m的粘径那么可以看哪个矩阵aij是否为1()R mAC. AA1T1D AA(In-I)V备注：5. IMS, BFS,连通图相关概念【较一版有更改】 对于联通无向图.请问以下说法正确的是：G盛世清北®A.广度优先您先进后出：B.连通的MST %极大连通于图C.广提优先搜索是递归实现的：7y每次探哎优先搜索都能得到一个联通分支；V具体:6 二叉树的前，中，后遍历相关类型题V具体；叶节点相对顺序前中后序遍历是否一样()A.完全一样B. 完全不一样C. 前序和后序一样D前冲和中样一样7. 森林

7、.二叉树转换V具体若森林F对应的一叉树R中有m个点.R的根节点r的右子树同rfn个节点那么 徐林F中第I颗树的结点 个数为：As m-n B、m-n-l C、nr 1 D、不确ifilV缶江；不难，宴砒题&散列农，二次黄找法V具体:希值为ke哈希农K 14线性衷插入到15, 38, 61. 84, 8,最后播入49.那么利用二次探测法.49应该放在下标为多少的表顶中？A. 3B. 5C. 8D. 99. b树与b+树V其体RB+树不同B树的待.点之一是A、B树和B+树都是AVL枸R、R树和R+材都能用丁文件系统C、B树和B+树都日勺效支持顺斤介找D、B树和B+树都有效支持随机进找V备江

8、： b树和树是否支持驰机责找和顺序查找10. V具体A针对以下无向连通图从点I开始，使用Dijkstra Sr法寻找单源最短路径.依次加入的点是()A. ?B 1> 2、 4、 3、 7. 5、 balabciluD. ?备注iA给了个图，止给出根岛算法所得到的次序土逍上血许多题F1类似11.归并段、创路归并，WPL具体、：若初始归并及大小分别为，5 9 12 13 14 16 17 18 20 28 30 37 42,那么垠佳|并树的带权路径长度WPL 是()A. 46()B. 472C. 480D. 486二简存题(弟一题6分，第二题8分，第三题9分)：K 一颗空AVL树中.H页序插

9、入(5942 I 38 | ；(1)、严格遵循AVL操作，画出播入后的AVLW (画出每一步；(2)、全祁插入后，求等概率下的查找成功的T均检索长质。2、 二义树的内部埒径长度：假设N个互不柑同的随机元素插入棵空一又搜索树明得到的一又搜索树的内部路径长 丧期垫为0( NIOgN > 03、 恰定个长提为N的数组，保i正其中至多存在C个极值点Qi为极值点，则满址IViVMili-1 <iiiI&&QEE)或者(ai-Dai)&A (aiai*l) . C可以看做个常数请设计个时间复余丧尽可能低的算 法对N排序计算机组成原理、选择题(1 11题为单选题，每小题2

10、分)1.绘出-串16诳制数()X | 234567X9()河用大端法和小瑞法存分别堤名少？A小端从览址小爻且大12 3456 78 90从地址小到人大端90 78 56 34 12G盛世清北®B. ?67 9 >D. ?2. 3. 14的16进制数是XXXX,问它的阶码用二进制表示是茎少？A. ?Ble)OO(X) 00C. ?D. ?3问下列儿个哪个不是的诺依曼结构的基础部件？A. CPU D.内存C硕盘D.打印机问主频为多少?4,实Jur 5级流水线.每个阶段的运行时长为如(3ms 5ms 2ms 6ms 4ms ), A . I66MHZB. 248MHZC. 333MH

11、zD. ?G盛世清北®5 .行波进位和超前进位的概念题V 题考虑到电路的负杂性与延迟-ALU的加法器实现通常是山:A.务个小规模超前进位加法器耕接而成B.多个小规模超前进位J川法器和行波进位加法器级联而成C.大规模行波进位加法器组成D.大规模超前进位加法器组成6 程序金询、中断、DMA三种方式的概念题？下列关于程序查询、中以DMA的三种方说法正确的是A. DMA对外部输入输出的响应实时性最高；B.中断仍需要经过CPU寄存器传输数据C.除程序代询方式外，中断和DMA都不再需耍编写程序执行D. DMA总是性能最高7 .中断向量表存储的是？A.中断服务程序的入II地址8 .中断号?？C.中

12、断状态字8.路组相联的一个计哪真题G i chc采用4路 组相联 每块32B 16组（编号0-15） , iW OXDEADBEEF映射到 哪一组？A. set7B. SetllC. sc i 13D - set 159.流木1纽的柑关晚念题裕）Htfn关于流水线说法iF潇的是（）A.通过不断加深流水线的级数，流水线的效率可以不断捉高B.泳水段的平均延迟彤响了流水线的最高频率？C沆水线中的吕险都HJ以通过推入流水线停顿来解决D. ?10.磁盘的转速为7200RPM,寻道时间为9nls每个碓道有400个扇区，数Ie分布均匀，问读 奴一个扇区的平均时仙（）A. 4.70mSB. 9.20msC.

13、7.56TTiSD. 5.74msI I .X干硬布线控制岳和微指令控制器的对比，下列说法正确的是（）A.颔指令控制器执行效率更高B.硬布线控制器电路组织更简单C.谀布线扯制器指令执彳亍效率更高D脱侑线易于扩展和修改功能一、解答题（第一制9分.第一球14分）1.（1给出了个木比化的乘浓貉的线跑图，讹描述乘法器的运行步骤.讷用流程图和文字描述挂T作过程:（2）该乘法器还可以代化.请画出比化心的乘达器的线赂图，并描述做了嗡些优化。Multiplicand 冈侬10 0 0 x 1 0 0 1twotwo,J-V8-bit Adder8-bitProductSMnghtMultiplier8-btt

14、2- (I) 将 MIPS 令集精简为 MIPSse 指令集包括 ADDU. SUBIE ORL LW. SW. BEQoCPu数据通路图如下：Instruction Fetch Unit dk-> KU)Instruction Wordrd rtbusW&J2AdrData ln:cbusBK.iiRw Ra RbRegFile 327*32Clkl rMemmRegr°Datadk > MemoryfuncOPCOdO(OP)100000IOOoIO/000000000000001I0I10001II0I011OOoIOOadduSUbUOriIWSWbeqR

15、egDSt10XALUSrC11MemtOReg001XRegWr1MeJeWr0nPC SQI0000EXtOPX1ALUCtr<l:0>00(ADD)01 (SUB)10 (OR)(2)、分析指令需求以集成控制信号.沽境写下列农格。(3)若将加上单用期处理器改造成为旅水线处理器，ID6- /i个渝水段F (tR值)、DG盛世清北®（译码）、E （执行）、M （访存）、W （写回），那么流水线会产生哪些冒险？举例说明针对以卜,冒险,若耍化化流水线，应该增加什么剂件或者怎样修改祁件，诸用文宁t魁.操作系统一、选择题VI-9为单选题，每题2分）I.枫拥操作系统进程状态图（图

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

17、修 改位，访问位，T时间内访问的次数G盛世清北®A. ?B. ?D. ? ?5.给了信号垃的定义.问N个进程竞争一个资源.需要几个信号垃？ 给出P (S) VS)的实现代码A. IB. NC N 1I) . N+1I.给淀页表大小为512宁.抬令疗了 2页，薮据存1页，然后怡了一段程序更初始化一个1024* 1024的矩阵，问 缺贝娄少次？(其中数组A1 1024 | | 1024 |为IMERGER类里贝农人小为512字,Ai. JI-0)A. 1024* 1024B. 1024*512C. 1024D. 1024*26.关T FAT文件系统下列说区不正确的址()A. FAT文件系

18、统文件名区分大小写B.卜AT文件系统文件的物理结构於链述绢织C. FAT文件系统为了提岛效率.采用了1录顶分解的方法D. ? ?H问下列哪些操作不是为了提升文件系统性能R录项分解等)？A 目录项分解B.文件高速缓存C-厩盘调IsiSliiD.异步I/O9.下列关于死锁的选项哪一个是不正确的()A、安全状态一定不会发牛死锁；B、不安全状态一定会发生死锁；C、不安全状态就是死锁D、? ?V模拟题：下列关r死锁与安全状态的叙述中W系一个是止确的？A.死锁状态-淀是不安全状态B.从安全状态有可能进入死锁状态C.不安全状态就是死锁状态D.死锁状态有可能是安全状态G盛世清北®二、解答题（第一题1

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

20、直占用全部倍适帘宽；C.码分名目每个用八可以一自人用全部佑逍带:找D.码分多用每个用户不可以直占用全部信道带宽；2. （2道）关于报文交换和电路交换下列说法正确的是？A.报文交换的转发速度耍快丁电路交换B.电路交换的转发速度耍快丁报文交换C.当数据经过交检机时，报文交换冢要将数抵存储然后转发D.当数据经过交换机时，电路交换需要将数据存储然后转发3. 8023协议概念题（如是否可集）真题 以下 r 802.3协议的正确选项是（）A. 802. 3为上层提供了可靠的数呃服务B. 802.3为上层捉供了不可靠的数堀服务C ? 9D. ? ?4 - 802.11协议概念题（如是否町蹴 是不是解决了隐蔽

21、站问题）？V真题A下列关于802,11协议选项正确的是（）A. 802.11提供可靠的单播数据服务B. 802J I%共不可靠的多播数据服务C. 802. 1 I能解决暴节点问题G盛世清北®D. 802.11不能解决隐藏结点问题5. IP协议、UDP协议.TCP协议概念题丈真题下列关于UDP协议说沫正确的是（）A. UDP为应用层桃供了不可靠的数据报服务B. UDP为提供面向连接的服务C. UDP向应用层提供无连接的服务D.UDP为应用层捉供了可靠的数掘报服务6 .数期校验的问趣（如问发送力和接收方是不是用不同的计算公式等）？真题以下关于数据校骏的选顶正确的是0:A.发送方和接收方计算校骏和的公式不同B.编码效率与校验位数无关C.接收方能用校验码