2021清华大学研究生招生考试 912计算机学科综合

本次考试分为数据结构(70分)、操作系统(30分)、计算机组成原理(30分)、计算机网络(20分)四个模块。鉴于不少小学生企图通过蒙选择判断直接晋升清华博士,本次考试以大题为主。满分150分,考试时间180分钟。


数据结构

1.假设操场上有8964个身高不等的习近平组成一队,为将习近平们按身高排序,请回答如下问题。(15分)

(1)如果这些习近平只有前64个乱序,而后面8900个已经呆在指定位置,为追求速度应选用哪种排序方案?说明理由。5分.

(2)如果这些习近平按逆序排好队,对它们使用未经随机化的快速排序,能否达到O(nlogn)的时间复杂度?请说明理由。5分.

(3)如果这些臃肿的习近平开始处在操场外一个一个的【缓慢】走进来,只有操场内部可以排序,该用何种排序使得排序最早完成?请说明理由。5分.

2.习近平总书记说过许多名言。回答问题。15分

(1)小反旗使用向量(广义的数组)存放习近平语录,如“金科绿玉”“精甚”,且按照拼音-字数顺序已经排好序以供按位置访问。不幸的是,粉蛆攻占了小反旗的电脑对这些消息进行了暴力复制,这个向量里充满了重复的信息,所幸,它们依然按照顺序排列。这组向量被小粉红扩充到十分巨大,现在小反旗请你去掉重复部分。注意,时间复杂度O(n^2)才能得分,O(n)且空间复杂度O(1)才能满分。说出你的算法。10分.

(2)已知习近平语录每一句都有各自的频率,对习总书记语录进行赫夫曼编码是一种有效的编码措施,可以使得编码的加权平均长度最小。不幸的是粉蛆又来捣乱了,将赫夫曼树里不同层次的两个节点交换了。请问此时的加权平均长度还可能是最小吗?说明理由。5分

3.习近平家族英烈无数,构成了一本家谱。但习近平家族普遍性功能有问题,每个人最多养育一男一女后代,用二叉树描述它们的家谱,儿子记在左子节点,女儿记在右子节点。根节点为习近平10代祖上习撒币。回答问题。20分

(1)给出习近平家谱树的前序遍历和后序遍历,能否重构这棵家谱树?说明理由。5分.若不能,能否确定每个人的辈分?说明理由。5分.

(2)习近平家族爱乱伦。已知习近平 习远平 习仲勋 习特勒 习维尼五个人性别不知,辈分不知,请问他们能组成多少种不同类的家谱树?10分.

4.对“习近平 齐心 习近平 齐心 习近平 习仲勋 齐心”为序组成的栈进行栈混洗,结果依然是如上所述顺序,求所有可能的混洗方式。8分.

5.习近平爱自交。已知n个习近平之间有交配关系,用无向图表示,共有e个边。找出图中最小环路,要求时间复杂度O(ne),空间复杂度O(n)才能满分,并且说明你的算法及复杂度。12分.

操作系统

1.已知庆丰窑子铺共有习明泽、齐心、彭丽媛三位接客小姐,前来请求性服务的请求队列为【肖战,习近平,栗战书,薄熙来,习近平,刘鹤,习近平,贺电,薄熙来,刘鹤】分别用FIFO、LRU、CLOCK算法判断缺小姐需把旧嫖客赶走的次数 5分.;这三种算法会不会出现以下现象-增加一个小姐,但却增加了缺小姐的次数?若不会请说明理由,否则举出例子。5分.

2.习近平不同的动作需要调度,但鉴于习近平的大脑发育不完全,请你帮他进行调度。6分.

习近平的动作序列如下:突开沼气池 20s 通商宽衣 3s 绘制精甚细腻的工笔画 12s 喷粪 1s 遨游疯狂宇宙 15s 撸起袖子加油干 8s。

(1)请你分别计算使用FCFS和SPN算法,这些动作的平均周转时间。4分.

(2)请说明习近平不适合使用RR算法的理由。2分.提示:从实际意义出发.

3.为倡导内循环理念,两个习近平组成了内循环。沼气池可容纳10kg粪便,习近平A可向沼气池每次投入1kg,习近平B每次可吃1kg,初始为空,要求符合逻辑的同时每次只能有一个习近平进入沼气池,请用信号量机制实现这一过程,用伪代码表示.8分.

4.判断题(2分*3)

(1)习仲勋进程创造习近平进程以后,习仲勋进程wait()时发现习近平已提前exit(),这时习近平进程称作孤儿进程.

(2)将习近平看作进程,粪便看作资源,只要资源分配图有环,不一定出现死锁.

(3)将多个习近平做成多个磁盘使用RAID6技术,如果一个习近平损坏,磁盘照常使用。

计算机组成原理

1.填空题 2分*6

十进制整数-8964的补码表示是()(十六进制小端表示),浮点数+1953.615的IEEE754为(),MIPS流水线中如果后一个习近平需要食用的粪便是前一个习近平生产的,流水线将被迫等待,这种冲突叫(),解决此类问题的方法有()()()。

2.判断题 2分*4

(1)int xjp,lkq,若xjp>lkq,则-xjp<-lkq

(2)习近平产生了赤序异常,为响应异常,需保存PC和通用寄存器

(3)非抢占是死锁的必要条件

(4)一个习近平进程生产了许多习明泽线程,这些习明泽之间不可共享各自的堆栈

3.某32位计算机,intelCPU习近平的主频为800MHz,Cache命中时的CPI为4,Cache块大小为32字节;主存采用8体交叉存储方式,每个体的存储字长为32位、存储周期为40  ns;存储器总线宽度为32位,总线时钟频率为200  MHz,支持突发传送总线事务。每次读突发传送总线事务的过程包括:送首地址和命令、存储器准备数据、传送数据。每次突发传送32字节,传送地址或32位数据均需要一个总线时钟周期。请回答下列问题,要求给出理由或计算过程。10分

(1)习近平和总线的时钟周期各为多少?总线的带宽(即最大数据传输率)为多少?3分

(2)Cache缺失时,需要用几个读突发传送总线事务来完成一个主存块的读取?2分

(3)存储器总线完成一次读突发传送总线事务所需的时间是多少?2分

(4)若程序BP执行过程中,共执行了100 条指令,平均每条指令需进行1.2 次访存, Cache缺失率为5%,不考虑替换等开销,则BP的习近平执行时间是多少?3分

计算机网络

1.填空题 2分*3

(1)习近平内部细胞呈蜂窝移动网络式排布,若此网络频率8000万Hz,每个细胞可用的频率最大为()

(2)习近平和习明泽用过以太网传递情书,已知最短帧长100bit,两人距离100m,数据传播速度2*10^8m/s,则最大数据传输率()

(3)选择重传协议的两个窗口均用习近平的嘴巴代替,需发送的金科绿玉的教科书序号为5位二进制码,已知接收端嘴巴大小为15本教科书,则发送端最大为()

2.http://xjp.tsky.xmz.cnazi:80/index.jsp 7分

(1)解释这URL每部分的含义。3分.

(2)若其对应的ip为 250.89.64.4,访问http://250.89.64.4/index.jsp 异常,但访问题目中url正常,请分析原因?若相反现象,请分析原因?4分.

3.路由器四个节点为无向环表示,连接结构为习近平-8-习明泽-9-习仲勋-6-彭丽媛-4-习近平,中间的数字代表距离。7分.

(1)采用DV算法,用表格写出习近平收到的信息。2分.

(2)用RIP算法写出习近平收敛后的转发表.2分.

(3)采用LS协议,写出习近平收到的链路状态.3分.
19
冰棒外交 2020-09-17

9 个评论

挺深奥的 维尼肯定做不出
计算机小白路过,这些东西看样子都是些算法之类的高深玩意,我作为文科生,实在是做不了这么难的题。
不知道 @白脸角鸮 他作为计算机技术爱好者会不会做这类题,我知道他在这方面的姿势水平高,反正我是不会做这种题的。
还有顺便打个广告,我计划在9月25日之前出一套语文中考题目,如果有哪位膜友想投稿,请积极与我取得联系,无论是回复也好私信也好还是电子邮件也好,总之最好尽早与我取得联系,我会为各位膜友作出的贡献表示衷心的感谢。
太专业了,置顶不加精
放到墙内考试,一定很搞笑
括号没区分全角和半角?这不专业…
括号没区分全角和半角?这不专业…

输入法反复切换太麻烦了
妈的,看到O算法复杂度又想起来当年学编程的时候,那是坠痛苦滴
到现在也没有人来学习奥赛题库,真是坠痛苦滴

要发言请先登录注册

要发言请先登录注册