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

1、0盛世清匕®【盛世清北】北大计算机科学与技术（智能科学与技术）考研笔记北大考研辅导培训班盛世清北分享：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(sn)s 十二 i; i十+；)备注：王道2

5、017年真题本质是一样的A、O(N)B、O(NA2)C、O(logN)D、类似这样的答案2. 统性表v具体：下面关于线性表的叙述中，不正确的犯哪些()？A、采用顺序存储的线性表,必须占用一片连续的存储单元;B、采用顺序存储的线性表，便于进行陆入和删除操作，C、采用密接存储的线性表，不必占用一片连续的存储单元;D、采用链接存储的线性表，便于插入和删除操作；冬注)线性表的存储结构谜接和顺序3. 栈混洗具体"给了一个字符串HAPPY,按照这个顺序入栈，则出栈顺序不可能是是做个CA. HAYPPB. HPPAYC. HYAPAD. HAPPY(备注：栈混洗类虺H,群里有具体算法代码.但是一般

6、只考选把题,具体算法思想： 采用一个中间校来记聚每段小栈的信息。复杂度。(心)4.图的邻接矩阵具体：某连通图的邻接矩阵为A.若点i到点j存在一条长度为n】的路衿.那么可以看哪 个矩阵aij是否为1()ni AC. AAmD AA（m-l）备注：5 . DES, BFS,连通图相关概念【较二版有更改】对于联通无向图.请问以下说法正确的是：A.广度优先搜索是先进后出：B.连通图的MST是极大连通子图C.广度优先搜索是递归实现的：D每次深度优先搜索都能得到一个联通分支；v具体：6 .二叉树的前，中，后遍历相关类型题v具体；叶节点相对顺序前中后序遍历是否一样（）A.完全一样B.完全不一样C.前序和后序

7、一样D前序和中序一样7 .森林，二叉树转换（具体，若森林F对应的一叉树R中布m个点,R的根节点r的右子树H布n个节点，那么 森林F中第I额树的结点个数为：A、m-n B、m-n-l C、n+l D、不确定备注;不难，堪砒题8 .散列表，二次在找法具体会业:哈希值为ke）哈希表氏14线性表插入到15, 38, 61. 84, 8,最后插入49.那么利用二次探测法,49应诙放在下标为多少的表项中？A. 3B. 5C. 8D. 99. b树与b+树具体）：B十树不同丁 B树的特点之一是A、B树和B4树都是AVL利R、R树和R+树都能用于文件系统C、B树和B+树都布效支好I唳序代找D、B树和B+网都疗

8、效支持昵机查找备注： b树和b+树是否支持的机杳找和顺序查找供盛世清北®10. 体：针对以下无向连通图从点I开始.使用Dijkstra莫法寻找单源最短路径,依次加入的点是()A. ?B. 1、2、4、3、7、5、balabaluC ” eD. ?备注给了个图，比给出根据算法所得到的次序王道上面许多题目类似II.归并段、四路归并，WPL其体,：若初始归并段大小分况为，5 9 12 13 14 16 17 18 20 28 30 37 42,那么最佳归并树的 带权路径长陵WPL是OA. 460B. 472C. 480D. 486二、简答题(第一题6分，第二胭8分，第三题9分)：I、一颗空

9、AVL树中，1页序插入 5942 I 38 )；、严格遵循AVL悚作，画出插入后的AVL树(画出年一步；(2)、全部插入后，求等概率下的查找成功的平均检索长质.2、二义树的内部路径K度：假设N个互不相同的随机元素插入棵空二又搜索树.订明得到的一叉搜索树的内部路径长 度期望为O(NlogN> O3、蛤定 个长改为N的数组，保证其中至多存在C个极值点(ai为极值点，则淌足1 <i<N(ai-l<ai)&&(ai>aiI)5JcW(ai-l>ai)&&(ai<ai*I) . C可以看做 个常数,请设计 个时间反杂度尽可能低的算

10、法对N排序计算机组成原理丁选择题(111题为单选题，每小胭2分)1 .给出一串16进制数Ox 1234567X90.问用大端法对小瑞法储存分别是名少？ A.小端从地址小到大12 3456 78 90从地址小到大大温(X) 78 56 34 12B.?C ” D.?2 . 3.14的16进制数是XXXX,问它的阶码用二进制表示是多少？A.?B. 1000(X)00C.?D.?3 .问下列几个啷个不是汹诺依曼结构的基础部件？A. CPU D.内存C.硬盘D.打印机4 .实现5级流水线，每个阶段的运行时长为如(3ms 5ms 2ms 6m-ms ),问主须为多少？A.I66MHZ5 .248MHzC

11、.333MHZD.?®盛世清北®5 .行波进位和超前进位的概念题真题,考虑到心路的复杂性与延迟，ALU的加法器实现通常是由:A.多个小规模超前进位加法器拼接而成B.多个小规模超前进位加法器和行波进位加法曙级联而成C.大规模行波进位加法器组成D.大规模赳前进位加法器组成6 .程序式魂、中断、DMA三种方式的概念题？下列关于程序查询、中断、DMA的三种方说法正确的是A. DMA对外部输入输出的响应实肘性最高；B.中断仍需要经过CPU寄存器传输数据C.除程序台询方式外，中断和DMA都不再需要编写程序执行D. DMA总是性能最高7 .中断向量表存储的是？A.中断服务程序的入II地址

12、8 .中断号?？C.中断状态字®盛世清匕®8.即组相联的一个计算真题Cachc采用4第 用相联 每块32B 16组（编号0/5）,请问OxDEADBEEF映射到 哪一组？A. set7氏 setllC sci 13D. set 159.流水1线的相关啜念即直题 卜面关于流水线说法iE确的是（）A.通过不断加深流水线的级数，流水线的效率可以不断提高B.流水段的平均延迟影响了流水线的最高频率？C流水线中的运险阳HJ以通过插入流水线停顿来解决D. ?10.微盘的转速为7200RPM,寻道时间为9m、每个磁道右700个崩区，数据分布均匀,问读 取一个曲区的平均时间（）A. 4.70

13、msB.9.20nisC. 7.56msD. 5.74ms11.关于硬布线控制器和微指令控制器的对比，下列说法正确的是（）A.钮指令控制器执行效率更高B.硬布线控制器电路组织更简单C.硬布线拄制器指令执行效率更高D.帔布线扇干扩展和修改功能一、解答题（第一题9分,第一期14分）1. （1）给出了 个未优化的乘法器的线路图,第描述乘法器的运行步骤,请用流程图和文 字描述其工作过程：（2）该乘法器还可以优化.诂画出优化.仁的乘法密的线路图，并描述做了咖吗优化。盛世清匕®2. (I),将 MIPS 指令集精简为 MIPSLiie 指令集包括 ADDU. SUBU. ORL LW. SW.

14、BEQoCPU数掴通路图如下：(2)、分析指令需求以集成控制信号.请填写下列表格。funcopcode(op)100000100010/000000000000001101100011101011000100addusubuoriIwSWbeqRegDst10XALUSrc0011MemtoReg001XRegWr1MereWr0nPC_sol0000Ex topX1ALUctr<l:O>00(ADD)01 (SUB)10(OR)（3）若将加上单闾期处理器改造成为流水线处理困，加行丘个流水段F（取值）、D（译阳）、 E（执行）、M（访存）、W（写回），那么流水线会产生哪些冒险？举例

15、说明.针对以上冒除若要优化流水线，应该增加什么部件试者怎样修改部件，靖用文字描述.操作系统一、选择即（19题为单选题,每题2分）I.根据操作系统进程方状态图（图*）,判断进程状态哪个对?A. I。创建态B 2-新建C. 3,就第D. 4-阻塞备注：原题就是把里面五个状态换成I. 2, 3, 4, 5.让你猜里面的哪一个是正确的2 .问什么时候不一定会发生进程切换？A.进程时间片用完B.当进程创建了一个子进程之后C.进行读盘操作D.进程运行过程中产生了异常3 .安全状态和死锁的关系？模拟题类似题：关于死锁状态与不安全状态的关系,下列描述正确的力.：（）A.死城毡一种不安全状态B.系统处于不安全状

16、态,一定产牛了死锁C.不安全状态是死锁的必要条件D.不安全状态是死锁的充分条件4 .使用LRU,问哪个被换出？V给了一个表格以及一些参数, 膻R给出了页号，页框号，修改位，访问位，T时间内访问的次数 A. ?B. ?D. ? ?5.给了信号量的定义间N个避程竞争一个资源,帮要几个信号量？给Hip（S） v <s>的实现代码A. IB. NC. N-ID. N+II.给定页表大小为512字.指令存了 2页，数据存1页，然后给了一段程序要初始化一个 1024,1024的矩阵，问缺灾多少次？（其中数组A| 1024| 10241为INTERGER类霍页表大小为 512 字,Ai, j|-

17、0）A. 1024*1024B. 1024*512C. 1024”D. 1024*26.关于FAT文件系统下列说法不正的的是（）A. FAT文件系统文件名区分大小写B.卜AT文件系统文件的物理结构是链式组织C. FAT文件系统为了梃高效率,采用了口录项分解的方法D. ? ?II.向下列哪些操作不是为了提升文件系统性能（FI录顶分解等）?A.目录项分解B.文件高速缓存C.磁盘调度算法D.异步I/O9.下列关于死锁的选项,哪一个是不正确的（）A、安全状态一定不会发生死锁；B、不安全状态一定会发生死锁；C、不安全状态就是死锁D、? ?模报题）：下列关卜死锁与安全状态的叙述中,哪一个是正俑的？A.死锁

18、状态一定址不安全状态B.从安全状态有可能进入死锁状态C.不安全状态就是死锁状态D.死锁状态有可能是安全状态 二、.解答题第一题I。分，第二题5分）®盛世清北®I.操作系统实现了 20条系统调用，现在要添加 个名为SywuH2l的系统调用，力-3个参数M曰：（I）、要实现这个函数硬件需要支恃什么功能？（2）、间操作系统需要做什么操作？（3）、编评器需要如供什么样的支持？备注：跟17年的漪答差不多2、话写出多级反馈队列的原现,并谕述如何它是如何避行调度的,详细论述如何对持CPU 密集型进程/和I/O密集型进程。备注；往年考的是PV嫁作，现在变成了多级反馈队列的处理，进程调度计算

19、机网络一.选择题（1-9!也为单选越，每虺2分）1. 直题下列选项正确的是：（）A.频分多用每个用户可以宜占用全部信道带宽；B.时分多用每个用户可以一直占用全部信道带宽；C.码分多月每个用户可以一百占用全部信道带近：D.一分多用每个用户不可以直占用全部信道带宽;2. （2道）关于报文交换和电路交换,下列说法正确的是？A.报文交换的转发速度要快了电路交换B.电路交换的转发速度要快于报文交换C.当数据经过交换机时，报文交换需要将数据存储然后转发D.当数据经过交换机时，电路交换需要将数据存储然后转发3. 802.3协议概念题（如是否可靠）真题以下关802.3协议的正确选项是（）A.802.3为上层提

20、供了可靠的数据服务B.8O2.3为上层提供了不可靠的数据服务 c ? 9D.? ?4. 802.11协议概念题（如是否可靠,是不是解决了隐蔽站问题）? v真题下列关于80211协议选项正确的是（）A.802.II梃供可靠的单播数据服务B. 80211提供不可靠的多播数据服务C. 802.1 I能解决暴露节点问题D. 802.11不能解决隐藏结点问题5. IP协议、UDP协议、TCP协议概念题v真题,下列关于UDP协议说法正确的是（）A.UDP为应用层提供了不可靠的数据报服务B. UDP是提供面向连接的服务C. UDP向应用层提供无连接的服务D. UDP为应用层提供了可靠的数据报服务6 .数据校

21、驶的问题（如问发送方和接收方是不是用不同的计算公式等）？«真题以下关于数据校验的选项正确的是（）：A.发送方和接收方计算校脸和的公式不同B.编码效率与校验位数无关C.接收方能用校验码检错，就一定可以用它纠错D.校验能力越强则编码效越差7 .问CSMA概念题（比如是不是发失败后固定一段时间再发）？A.C8MA发生碰撞后放弃发送8 . ? ?9 . CSMA发生.碰撞后间隔一段时间固定时间再发送10 ?8.数据链路层和传输层的滑动窗II题（如发送、接受窗口大小是不是都固定）？i.旌路层的滑动窗I I发送窗I I和接收窗I I是固定大小的ii.传输层的发送窗n是可变的下传输的发送窗口与接收

22、一致iv.链路的发动窗I 与接收一致0盛世清匕®9,美于NA丁协议，下列晓法正痫的是A. NAT可用T给内网主机分配IP国与外界通信时NAT可以作为内网主机的代理服务器C. nJ作为城名脆苏器B 可作为木地网关10.美J AHP桃议.列说法IF题的是A.ARP用于怖设报文与MAC地址的转换氏NRP “能用于IP由坟与以太网网+ h AC地址的特换C.每次发还包前必须样要调用ARP I办议口，？二、解答地（第题E分）给定 个网络如下国大致）所示，HZII5为主机. 51s2为交换机.1【此为集线罂. 179 为端11.收出IP的格式为IJHIMAC的格式为MAC_HI 1以主机HI为例）.