2021南京大学计算机845考研试题（已根据回忆版增补）
2021南京大学计算机845考研试题
说明：本人在28号考试过程中抄下来的，时间有限有部分试题（13个选择/共40个，1个算法大题/大题共7个）遗漏，后又根据论坛和考研其他研友的回忆版资料进行过补充，基本完全。其余因笔记仓促亦可能有少量笔误，见谅。望后来考生，应知年与时驰、
意与日去，备考及早动手，坚持到底，衷心祝福大家都能学有所成，梦想成真。
感谢在我半年备考期间与我同一自习室复习的研友们，陈梅，王超，李玲，李浩，大白，王丽坤。感谢好友比助，姗姗，贝贝，成云，康师傅，丁小琳。感谢王道南大考研
诸位学长学和战友们，let，嘛嘛，木哥，Tomorrow，胸大的绿兔子汪a（没错我就是在黑你），六月（强迫症死敌！），地下铁（真诚祝福兄弟），句号，皮卡丘，倩倩，唯安，沧海，浅月，绝，别情，夜吟，风之天炼，河北的妹子i（冒泡一次激励我三天加倍
努力），亮靓（学妹加油），马克图布。仰头望明月，寄情千里光。愿你们拥有想要的未来，想去的远方。2021年12月30日于天津师范大学劝学楼C区503自习室。
作者：王道论坛章凝苏
一、单项选择题（40X2分）
1. 和动态链表相比，以下反映了静态链表缺点的是（）
A.插入、输入输出操作不便
B.存储空间有时得不到充分利用
C.要求各结点有相
同的类型    D.表中各结点只能读取不能修改
2. 二维数组A[8][10]按列优先次序存储在起始地址为0的连续内存单元中，其中每
个元素占5个单元，元
素A[6，7]的存储地址是（） A.275    B.310    C.315    D.330
3. 二叉线索树中执行较困难的运算是（）
A.中序线索树下查结点的前驱
B.中序线索树下查结点的后继
C.前序线索树
下查结点的前驱    D.后序线索树下查结点的前驱
4. 设散列表为H[11]（下标从0开始）。将关键码序列（20，15，19，43，67，30）散列到该地址空间中，
散列函数为H(key)=key，处理冲突采用线性探查法。则等概率情况下查成功时平均搜索长度是（） A. 1.2    B.  1.5    C.  1.6    D.  2
5. 已知一颗二叉树的前序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为（）
A. CBEFDA
B.  FEDCBA
C.  CBEDFA
D.  不确定
6. 以下与数据的存储结构无关的术语是（）
A.循环队列
B.链表
C.哈希表
D.优先级队列
7. 具有n个关键字的有序表，采用监视哨方式查，时间复杂度是（）
A.O(n)
B.O(n^2)
考研时间2021考试时间
C.O(log以2为底n)
D.O(nlog以2为底n)
8. 下列序列中哪一个是堆（）
A.（100，80，55，60，50，40，58，35，20）
B.（100，80，55，58，50，40，60，35，20）
C.（100，80，55，60，50，40，35，58，20）
D.（100，70，55，60，50，40，58，35，20）
9. 从任一结点出发到根的路径上所经过的结点序列按其关键字有序的结构是（）
A.二叉排序树
B.哈夫曼树
C.AVL树
D.堆
10. 下列排序算法中，在某些特殊情况下可能只需一趟排序就可完成的是（）
A.快速排序
B.冒泡排序
C.直接选择排序
D.堆排序
11. 用邻接表来存储图时（其中n为顶点数，e为边数），多点间最短路径Floyd算
法的时间复杂度是（）
A.O(n*e^2)
B.O(n^3)
C.O(n^2)
D.O(n的平方再乘以e)
12. 既希望较快查又便于线性表动态变化的查方法是（）
A.顺序查
B.折半查
C.分块查
D.基于属性的查法
13. 假定某程序在计算机A上运行需要10秒钟，A的时钟频率为1GHz。现在硬件设
计人员想设计计算机B，
希望该程序在B上的运行时间缩短为8秒钟，而使用新技术可以使时钟频率大幅度提高，但在B上运行该程序所需要的时钟周期数是A上的1.5倍。那么，B的时钟频率至少
应为多少，才能达到希望的要求（）
A．533MHz    B.  1.2GHz    C.  1.25GHz    D.  1.875GHz
14. 考虑以下C语言代码，
short si= -16384; unsigned short usi=si;
执行后usi的值是（）
A.16383
B.16384
C.32768
D.49152
15. 若两个float型变量x和y机器数分别为x=758E0000H，y=C0D30000H，计算x+y
第一步对阶操作的结
果[三角形E]补为（）
A.01101001
B.10010101
C.01101010
D.10010110
16. 关于半导体存储器，错误的是（）
A. 闪存（flash memory）不是半导体存储器
B. 半导体存储器都采用随机存取方式
读写
C. SRAM是半导体静态随机访问存储器，可用作cache
D. DRAM是半导体动态随机访
问存储器，可用主存
17. 以下哪种特征可以很好发挥cache作用（）
A. 程序中各指令间相关度不高
B. 程序中有大量循环语句及数组顺序访问
C. 程序整个大小不超过实际内存容量
D. 程序中主要是各类算术或逻辑运算操作
18. 主存按字节编址，cache有1024行，采用8路组相联映射，主存块大小64字节，所有编号从0开始，
主存单元0x8048900所在主存块对应的cache组号是（） A.0    B.4    C.36    D.548
19. 关于“自陷”（Trap）错误的是（）
A. 一定是出现了异常情况才发生自陷
B. 单步跟踪功能可用自陷机制实现
C. 系统
调用是一种特殊的自陷异常
D. 自陷发生后，CPU将进入操作系统内核程序执行
20. 某计算机最复杂指令要完成6个子功能，分别用时70ps，30ps，50ps，60ps，
20ps，40ps，流水段寄
存器延时为20ps，现把最后两个合并，产生一个五段流水，其时钟周期至少是（）
A.60ps
B.70ps
C.80ps
D.90ps
21. 不能提高总线带宽的是（）
A. 采用信号线复用技术
B. 增加总线带宽
C. 采用突发（burst）传送方式
D. 提高总线时钟频率
22. 必须在指令执行过程中由硬件完成的是（）（组成原理教材配套习题P252第33题原题）
A.保护断点
B.保护现场
C.设置中断屏蔽字
D.从I/O接口取数
23. 太长，略去
24. 关于特权指令，准确的是（）
A.可被操作系统内核使用
B.可被系统管理员使用
C.可被授权用户使用
D.可在用户程序中使用
25. 关于进程描述不准确的是（）
A.进程是程序的执行
B.一个程序可产生多个进程
C.进程间可共享代码
D.进程间不可共享变量
26. 用户程序执行时，使模式切换的原因不可能是（）
A.出现中断事件
B.发生异常
C.执行系统调用
D.程序内跳转
27. 管程中的条件变量，主要作用是（）
A.管理等待程序
B.表示资源数量
C.申请资源
D.回收资源
28. 关于信号，描述不准确的是（）
A.信号是进程通信机制
B.信号是软件中断
C.信号是进程同步机制
D.信号可用于程序异常处理过程
29. ~40. 时间关系欠缺，现补充几道其他研友的回忆版本：
1. 实现IP地址到MAC地址转换用的协议是？（感谢南大考研马克图布同学）
2. TCP/IP参考模型应用层相当于OSI参考模型的哪几层？（感谢南大考研马克图布同学）
3. 以下哪个方法不能用于拥塞控制？（感谢南大考研马克图布同学）
4. CSMA/CD协议中的CD表示什么？（感谢王道论坛just-同学）
5. 文件目录的作用？（感谢王道论坛just-同学）
6. 反置页表（感谢王道论坛just-同学）
7. 已知主频1.0GHz，现在进行DMA传送，已知DMA初始化工作需要1000个时钟，结束时中断处理
需要500个时钟，每次传送4KB数据，带宽4MB/s，求DMA传送效率？（感谢王道论坛musttome同学）不过我记得貌似这题是考DMA中断占CPU百分比吧，我算出来的值选项没有，有点印象。 8. 下面哪个页面置换算法效率最高？（感谢王道论坛musttome同学）
A.FCFS
B.最佳置换算法OPT
C.LRU
D.（忘了）
9. 已知IP网络地址（形如：11.22.33.44/24），现有4台主机，问使用多少位掩码（描述可能不规范，
就是划分后的子网占多少位）来划分最为经济？（感谢王道论坛musttome同学）
A.27
B.28
C.29
D.30
10. 使用停止-等待协议，已知单程传播时间和数据发送速率，帧为多大才能使数据传输效率大于50%？
（感谢王道论坛musttome同学）这题略不全
二、综合应用题（7题，70分） 41.（9分）斐波纳契数列Fn定义如下：
F0=0，F1=1，Fn=Fn-1 + Fn-2，n=2，3.・・・・・
（1）递归计算Fn时，需对较小的Fn-1，Fn-2，・・・・・・・F1，F0计算调用共多少次？（4分）（2）给出迭代法计算Fn的算法，并分析迭代法下的时间复杂度（大O表示法）（5分）
42.（12分）【回忆版，感谢王道论坛musttome同学】如下算法的功能是实现树的中序遍历并输出结点数据，树的结构用二叉链表表示，请补全算法代码。 struct PtrNode  {  };
class PtrNode() {
private:
PtrNode *ptrArray[MaxSize]; //栈 PtrNode *p;  int t = -1;