2020年四川大学计算机考研初试874真题回忆！
四川大学
发布于2020年12月5日 11:10
阅读数 4254
数据结构
选择题(每题2分)
单链表和数组定位前驱元素的时间复杂度
折半查找100个元素最多比较几次
给邻接矩阵求最短路径
关于哈希表哪个说法是对的(选项有哈希表只适合存储整数型元素、哈希表查找时间为O(1)，哈希表不适合查找某个范围内的元素，还有个忘了)
m叉树每个结点用m个指针域指向子树，共有n个结点，空链域有多少(m, n不是给定的具体数字，就是字母)
给一个序列，问建堆后某个位置元素是什么(大概如此，记不太清)
用哈夫曼编码已经编码了两个字符，分别编为1和01，哈夫曼树最大高度为4，问最多可以再编码几个字符
5(?)阶B树有53个关键字，问树最大高度
给一棵m阶B树(m是给定的具体数字)，删除某个元素后，根元素是什么(我做出来是会因为分裂产生新的根的)
给一个序列，逐个插入建立AVL树，问树中只有一个孩子的结点数
给一个序列以及一趟排序后的结果，问是哪种排序
其他题忘了
-
大题
如何判断无向图是否有回路，用自然语言或伪代码描述思路
二叉树用二叉链表表示，编写算法打印指定某一层上的所有元素
编写算法删除堆中一个元素
----
操作系统
选择题(每题2分)
分时系统设计要考虑的指标最重要的是什么
系统中有m个某类资源，一些进程要使用这些资源，每个进程最多需要k个，问不发生死锁的情况下，最多进程数是多少(m, k是给定的具体数字)
银行家算法，给Allocation和Max矩阵，有两个进程都发出同样的一个资源请求，已给出该请求向量，问操作系统应该分别同意还是拒绝这两个进程的请求
某时刻系统中有3个进程，问处于阻塞态的进程最多能有几个
会发生抖动的存储管理方法是什么(选项：连续可变分配、页式存储、段式存储、虚拟页式存储)
采用缓冲技术的目的
其他题忘了
-
大题
某时刻同时来了5个批处理作业，运行时间给出，优先级给出，每个进程的时间片为1秒，问用短作业优先调度和优先级调度的周转时间和平均周转时间，要求写出计算过程
食堂一个窗口供应面条和炒饭，且窗口只能放一碗食品。做面条的师傅如果窗口无食品就放面条，做炒饭的师傅如果窗口无食品就放炒饭，有吃面条和吃炒饭的两种学生，只有窗口有对应食品才会拿，用PV操作描述这些人之间的关系
磁盘容量为4TB，一个物理块1KB，问：
(1) 采用三级索引，索引块最多/大和最小/少是多少(原题如此，“和”字两边一个问多少，一个问大小……)
(2) 忘了
(3) 三级索引能表示的最大单个文件是多大
----
网络
选择题(每题2分)
某网站有1个HTML页面，6个图片，1个Java Applet，用持续连接非管线式HTTP访问该网站，需要几个RTT时间
标识应用层所使用的服务的是(端口号)
UDP的一道题，记不清了，我选的是目的地址和目的端口号
带宽的最大最小公平分配原则
假如发明了一种新型压缩算法，压缩性能贼好，作为首席internet架构师的你会把这种算法应用在什么网络设备中
使主机不依赖于网络的设计原则是(选项：A. 端到端设计原则 B. 分层设计原则 C. 网络的核心部分简单而边缘部分复杂 D. 网络的边缘部分简单而核心部分复杂)
其他题忘了
-
大题
给一个二进制表示的转发表，有4个接口，每个接口给出源地址和目的地址，最后一个接口是除其他接口以外的其他地址。问：
(1) 用最长前缀匹配给出每个接口的转发表
(2) 给三个二进制表示的地址，问这些地址应由哪个接口转发出去
(3) 用CIDR的形式给出路由表
有ABC三个设备，两段链路L1、L2连接它们(A-B-C)，给出L1、L2带宽、传播时延(以字母给出)，发送m bits数据，问：
(1) 最后一个bit到达C需要多少时间？如果采用电路交换，则是多少时间？
(2) 如果A的发送窗口为以下值，计算A的吞吐量，记RTT为往返时间，B为L1带宽：
a) W=0.5*B*RTT
b) W=2*B*RTT