【盛世清北】2021北京大学801计算机专业基础考研真题.docx

盛世清北】2021北京大学801计算机专业基础考研真题盛世清北分享: 北京大学801计算机专业基础考试真题，适用北京大学以下院系+专业070921地质学（石油地质学）北京大学地球与空间科学学院北京大学前沿交叉学科研究院北京大学前沿交叉学科研0701J3数据科学（数学）0714J3数据科学（统计学）0812J3数据科学（计算机科学与技术）北京大学深圳研究生院081203计算机应用技术 北京大学801计算机专业基础科目的考研真题为：北京大学信息科学技术学 081201计算机系统结构院081202计算机软件与理北京大学信息科学技术学 论院数据结构：1. 写出AVL树并计算平均查找长度2. n个数组成二叉树，证明排序时间复杂度为0 （nlogn）（这个记忆得有点模 糊）3. 一个数组，有最多X个极值，设计一个时间复杂度尽可能低的算法计算机体 系结构：1. 结合流程图阐述乘法器的工作原理，然后对其改进2. MIPS指令集计算机网络：一个用户通过交换机，集线器向另一个用户发送IP报文，问交换机的 作用，源地址和目的地址北京大学801计算机基础2018年研究生入学试题i.算法复朵度丈具体＞ :已知下血一串代码,求英算法时间复杂度：int s二i二0; While(S＜n) {S += i; i++;)V备注☆＞；王道2017年真题本质是一样的A、0(N)BX 0 (NA2)C、0(I0gN)D、类似这样的答案2.线性表龙具体A下面关于线性表的叙述中，不币确的是哪些0?A、采用顺序存储的线性表,必须占用一片连续的存储单元;B、采用顺序存储的线性表,便于进行插入和删除操作.C、采用链接存储的线性表,D 字田链球左信的纬枇美不必占用一片连续的存储单元; 便T抽入和删除操作；〈备注八卜线性衣的荷储结构链接和顺序3. 伐混洗〈具体a：给了 A字分必HAPPY,按照这个顺序入栈，则出栈顺序不可能足堆卯个0A. HAYPPB. HPPAYC. HYAPAD - HAEEYV备栈混洗类题「I,群里有具体算法代码,但是一般只考选择题.具体算法思想：采用一个中 间栈来记录每段小栈的信息、.复杂废0 (口2＞4.图的邻按矩阵VH休、：某连通图的邻按矩阵为A •若点i到点j存在-条长度为m的埒径，那么可以看哪个 “Rai上痛;为1()A. AR TnAC. AA1T1D AA(In-I)V备注☆☆☆＞：5. DES, BFS,连通图相关概念【较一・版有更改】G盛世清北®对于联通无向图.请问以下说法正确的是：A.广度优先%圈先进后出：B.连通^的MST喊大连通于图C.广度优先抄索址递归丈现的：。

每次深哎优先搜索都能得到一个联通分支；V具体:6. 的前，中，后遍历相关类型题V具体叶节点相对顺序前中后序遍历是否一样()A.完全一样B. 完全不一样C. 前序和后序一样D 前冲和中样一样7.森林.二叉树转换〈具体〉若森林F对应的一叉树R中有m个点.R的根节点r的右子树具有n个节点•那么徐 林F中第1额树的结点个数为：A、m_n B、m-n-l C＞ n4-1 D＞ 不确ifiV备it： ☆☆☆＞不难，宴砒题&散列农，二次黄找法〈具体☆☆☆☆＞：希值为ke〉哈希表长14线性衷插入到［15, 38, 61. 84, 8},最后播入49.那么利用二次探测法.49应该放在下标为多少的表顶中？A. 3B. 5C. 8D. 99. b树与b+树〈其体RB+树不同「B树的待.点之一是A、B树和B+树都是AVL枸R、R树和R+材都能用丁•文件系统C、B树和B+树都有效支持嗾序仆找D、B树和B+树协竹效文持随机仪找〈备江☆☆☆＞： b树和》树是否支持W也机责找和顺序查找G盛世清北®10.

2.二义树的内部路栓长度：假设N个币不相同的随机兀武捕入一棵宇一.法挖索树.iiF明得钊的一义搜索郴的内部垢挎 长度期业为0 (NIogN) •3、恰定i个长嗖为N的数组，保iiEH•中至多存在C个极值点Qi为极值点，则满足 Kiai 4-1)或者(ai-l>ai)&&(ai D. ??2 . 3. 14的16进制数是XXXX,问它的阶码用二进制表示是年少?A. ??Ble)00(X)00 ro->• • •D. ??3.问下列几个嗷个不楚冯诺依曼结构的基础部件?A CPU B内存硕盘D.打印机4•实JUr 5级流水线.每个阶段的运行时长为如(3ms 5ms 2ms 6ms 4ms ), 问主频为多少?A.I66MHZB. 248MHzC. 333MHZD. ??5.行波进位和超前进位的概念题V •题〉考虑到电路的负杂性与延迟・ALU的加法器实现通常是山:A.务个小规模超前进位加法器耕接而成B.多个小规模超前进位1川法器和行波进位加法器级联而成C.大规模行波进位加法器组成D.大规模超前进位加法器组成6•程序资询、中断、DMA三种方式的概念题？下列关于程序查询、中断、DMA的二种方说法正确的足A. DMA对外部输入输出的响应实时性最高；B.中断仍需要经过CPU寄存器传输数据C.除程序代询方式外，中断和DMA都不再盂耍编写程用执行D. DMA总是性能最高7 .中断向量表存储的是？A.中断服务程序的入II地址8 .中断号?？C.中断状态字8.路组相联的一个计奠E〈真题＞G I chc采用4路 组相联每块32B 16组（编号0-15） , i%诃OXDEADBEEF映射到 哪 一组？A. set7B. SetllC. sc i !3D - set 159.流木1线的相关口既念题〈裕＞MnI关于7京水线说法托确的是（）A.通过不断加深流水线的级数，流水线的效率可以不断捉高B.泳水段的平均延迟彤响了流水线的最高频率・？C沆水线中的吕险都HJ以通过推入流水线停顿来解决D. ??10.磁盘的转速为7200RPM.寻道时间为9ms每个感道有400个扇区，数Ie分布均匀•问读奴- 个扇区的平均时仙（） A. 4. 70mSB. 9. 20msC. 7. 56TTiSD. 5. 74msI I .X干硬布线控制岳和微指令控制器的对比，下列说法正确的是（）A.覆指令控制器执行效率更高B.硬布线控制器电路组织更简单C.谀布线扯制器指令执彳亍效率更高D %「扩展和俸改功能一、解答题（第一题9分.第一/14分）1. （1）给出了个木比化的乘浓貉的线跑图，讹描述乘法器的运行步骤.讷用流程图和文字描述挂T作过程：（2）该乘法器还可以代化,请画出比化•心的乘达器的线赂图，并描述做了嘿些优化。

Multiplier nd 5M.10 0 0 x 1 0 0 1twotwo,J84)it Adder8-bitProductsniff fightMultiplier2 • (I) ■将 MIPS 指令集精简 %MlPSLite 令集包括 ADDU. SUBU. ORL LW、SW.BEQoCpIJ数泥通路图如下：rd rtbusWmm16 ■,花RegFile32・Mx32mm16 ■,花DataInstructionFetch Unitclk—> "I)),WrEn AdcDatadk— > Memory-sPC_$el Instruction Word 力(2)、分析指令^求以集成控制信号.请境写下列农格funcOPCOde(OP)100000100010/000000000000OollOI100011I0I011OOoIOOadduSUbUOriIWSWbeqRegDSt100XALUSrC0011MemtOReg001XRegWr1MemWr0nPC Sei0000EXtOPX1ALUCtr00 (ADD)01 (SUB)10(OR)(3)若将如上单用期处理器改选成为流水线处理器，| D6- /L个流水段F (取值)、D (译码)、G盛世清北®E （执行）、M （访存）、W （写回），那么流水线会产生哪些冒险?举例说明。

什对以上冒险，若耍优化流水线，应诫增加什么邹件或者怎样修改部件，诘用文宁拽I述抹弁系统一、选拯题（1・9题为单选迎.每题2分）I.枢堀挟作系统进程力状态图（图勺•判断进程状态哪个对?A. 1-＞创建态B. 2-〉新建C. 3〉就绪D. 4A阴塞V备注〉：原题就是把里面?/i个状态换成1, 2. 3, 4. 5.让你猜里面的哪一个是正确的2 .问什么时候不一定会发牛•进程切换？A.进程时间片用完B.当进程创建了一个子进程之后C.进厅读盘操作D.进程运行过程中产牛了异常3 .安全状态和死锁的关系？V模拟题 ＞类似题：关于死锁状态与不安全状态的关系，下列描述正确的有：（）A.死锁是一种不安全状态B.系统处T不安伞状态，一定产牛了死锁C.不安金状态是死锁的必要条件D不安余状态是死锁的充分条件4.使用LRU,问哪个被换出？ V给了-•个表格以及一些参数》题目给出了页号，页框号，修改 位，访问位，T时间内访问的次数G盛世清北®A. ??B. ??D • ? ?5.幺合了信号量的定义，间N个避程竞争一个资源.离更儿个信号量？ 给出P (S) V (S)的实现代码A. IB. NC. N - 1D • N4-1I.给定页汞大小为512卞•抬令存了 2页.数据存I页.然后给了一 &秤序娈初始化一个 1024。