2021南京大学计算机考研试题.pdf

《2021南京大学计算机考研试题.pdf》由会员分享，可在线阅读，更多相关《2021南京大学计算机考研试题.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2021南京大学计算机考研试题一、单项选择题（40X2分）1.和动态链表相比，以下反映了静态链表缺点的是（）A.插入、输入输出操作不便 B.存储空间有时得不到充分利用C.要求各结点有相同的类型 D.表中各结点只能读取不能修改2.二维数组A10按列优先次序存储在起始地址为0 的连续内存单元中，其中每个元素占5 个单元，元素 A6,7的存储地址是（）A.275 B.310 C.315 D.3303.二叉线索树中执行较困难的运算是（）A.中序线索树下查找结点的前驱 B.中序线索树下查找结点的后继C.前序线索树下查找结点的前驱 D.后序线索树下查找结点的前驱4.设 散 列 表 为（下标从0 开始）。将

2、关键码序列（20,15,19,43,67,30）散列到该地址空间中，散列函数为H（key）=key%ll,处理冲突采用线性探查法。则等概率情况下查找成功时平均搜索长度是（）A.1.2 B.1.5 C.1.6 D.25.已知一颗二叉树的前序遍历为ABCDEF,中序遍历为CBAEDF,则后序遍历为（）A.CBEFDA B.FEDCBA C.CBEDFA D.不确定6.以下与数据的存储结构无关的术语是（）A.循环队列 B.链表 C.哈希表 D.优先级队列7.具有n 个关键字的有序表，采用监视哨方式查找，时间复杂度是（）A.O（n）B.O（nA2）C.O（log 以 2 为底 n）D.O（nlog 以

3、 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 为边数）

4、，多点间最短路径Floyd算法的时间复杂度是（）A.0（n*eA2）B.O（nA3）C.0（nA2）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.

5、25GHz D.1.875GHz14.考虑以下C 语言代码，short si=-16384;unsigned short usi=si;执行后usi的 值 是（）A.16383 B,16384 C.32768 D,4915215.若两个float型变量x 和 y 机器数分别为x=758E0000H,y=C0D3 0000H,计算x+y第一步对阶操作的结果 三角形E 补为（）A.01101001 B,10010101 C.01101010 D.1001011016.关于半导体存储器，错误的是（）A.闪 存（flash memory）不是半导体存储器B.半导体存储器都采用随机存取方式读写C.SRA

6、M是半导体静态随机访问存储器，可用作cacheD.DRAM是半导体动态随机访问存储器，可用主存1 7.以下哪种特征可以很好发挥cache作 用（）A.程序中各指令间相关度不高B.程序中有大量循环语句及数组顺序访问C.程序整个大小不超过实际内存容量D.程序中主要是各类算术或逻辑运算操作18.A.O B.4 C.36 D.54819.关于 自陷（Trap）错误的是（）A.一定是出现了异常情况才发生自陷B.单步跟踪功能可用自陷机制实现C.系统调用是一种特殊的自陷异常D.自陷发生后，CPU将进入操作系统内核程序执行20.某计算机最复杂指令要完成6 个子功能，分别用时70ps,30ps,50ps,60p

7、s,20ps,40 p s,流水段寄存器延时为2 0 p s,现把最后两个合并，产生一个五段流水，其时钟周期至少是（）A.60ps B.70ps C.80ps D.90ps21.不能提高总线带宽的是（）A.采用信号线复用技术B.增加总线带宽C.采用突发（burst）传送方式D.提高总线时钟频率22.必须在指令执行过程中由硬件完成的是（）（组成原理教材配套习题P252第 33题原题）A.保护断点 B.保护现场 C.设置中断屏蔽字 D.从 I/O接口取数23.太长，略去2 4.关于特权指令，准确的是A.可被操作系统内核使用C.可被授权用户使用）B.可被系统管理员使用D.可在用户程序中使用25.关于

8、进程描述不准确的是（）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

9、参考模型应用层相当于OSI参考模型的哪几层？（感谢南大考研群马克图布同学）3.以下哪个方法不能用于拥塞控制？（感谢南大考研群马克图布同学）4.CSMA/CD协议中的CD表示什么？（感谢王道论坛just-同学）5.文件目录的作用？（感谢王道论坛just-同学）6.反置页表（感谢王道论坛just-同学）7.已知主频1.0GHz,现在进行DMA传送，已知DMA初始化工作需要1000个时钟，结束时中断处理需要500个时钟，每次传送4KB数据，带宽4M B/S,求 DMA传送效率？（感谢王道论坛musttome同学）不过我记得貌似这题是考DMA中断占CPU百分比吧，我算出来的值选项没有，有点印象。8,下

10、面哪个页面置换算法效率最高？（感谢王道论坛musttome同学）A.FCFS B.最佳置换算法OPT C.LRU D.（忘了）9.已知IP 网络地址（形如：11.22.33.44/24），现 有 4 台主机，问使用多少位掩码（描述可能不规范,就是划分后的子网占多少位）来划分最为经济？（感谢王道论坛musttome同学）A.27 B.28 C.29 D.3010.使用停止-等待协议，已知单程传播时间和数据发送速率，帧为多大才能使数据传输效率大于50%?（感谢王道论坛musttome同学）这题略不全二、综合应用题（7 题，70分）41.（9 分）斐波纳契数列Fn定义如下：F0=0,Fl=l,Fn=

11、Fn-l+Fn-2,n=2,3.（1）递归计算Fn时，需对较小的Fn-1,Fn-2,Fl,F0计算调用共多少次？（4 分）（2）给出迭代法计算Fn的算法，并分析迭代法下的时间复杂度（大 0 表示法）（5 分）4 2.（1 2 分）【回忆版，感谢王道论坛musttome同学】如下算法的功能是实现树的中序遍历并输出结点数据，树的结构用二叉链表表示，请补全算法代码。struct PtrNode 二叉树链表结点（int data;struct PtrNode*llink,*rlink;）;class PtrNode（）（private:PtrNode*ptrArrayMaxSize;栈PtrNode*

12、p;初始为根结点intt=-1;栈顶指针public:void lnOrder（）while（p!=NULL&t!=-l）（if（）当左结点非空时（3 分）（；（3 分）p=p-llink;else（_ _ _ _ _；（3 分）（4）;（3 分）p=p-rlink;)43.（23分）下图是某个早期计算机M的结构示意图。M字 长16位，存储器按字节编址，小端方式存储数据，其ALU中包含了一个补码加/减运算器以及各类逻辑运算部件和移位部件，无乘/除法器。在M中取指令过程如下：PC-MART地址线；“读命令”一控制线；存储器读出命令一数据线-M D R TR。CPU以下是一个C语言程序add：Vo

13、id main（）int x=32767;int y=2;printf（sum=%d”,x+y）;己知sizeof（int）=2,回答并计算下列问题：（1）图中PC,MAR,ALU,IR的中文含义（4分）（2）（3）M是否肯定不能提供乘法指令？为什么？（2分）（4）若M的指令集没有除法指令，则M是否一定不能实现赋值语句“z=x/y”?为什么？（2分）（5）程序add在M上执行结果为sum=-32767,请解释为什么add的结果为-32767?（3分）（6）变量x地址为C0050H,则执行到printf语句时，存储单元COO50H中内容（用十六进制表示）是什么？（2分）（7）要使M执行程序add

14、过程中能发现溢出并调出“溢出处理程序”执行，则M中的“带符号加法指令”不仅要能进行加法运算，还要能根据溢出标志位（OF）来触发“溢出异常”，请问溢出判断条件是什么？简要说明从CPU发现溢出异常到操作系统执行“溢出处理程序”的过程。（4分）（8）程序add中计算x+y的加法指令为add RO,（R1）,其功能为RROGRRO+MRR1，其中RRi表示寄存器R i内容为地址的存储单元的内容，请仿照题目中给出的取指令过程的描述给出add RO,（R1）指令执行过程的描述。（4分）44.（8分）有7个哲学家围坐在圆桌边，两人之间有一把吃饭的叉子。哲学家在思考一段时间（Thinking。）后，要吃饭。在

15、拿到左右两把叉子时，才可吃饭（Eating。）。在饭后，要去健身（Playing。）。共有3套健身器材，健身时每人独占一套。健身之后，继续工作。请用信号量和PV操作写出哲学家们并发工作的程序,要求不会出现死锁，并说明信号量含义。45.（7 分）某多道程序系统，用户作业可使用主存容量为100M,主存管理采用可变分区方法，优先分配低地址区且不准移动。系统有磁带机2 台，打印机1 台，外设分配采用静态方法。忽 略 I/O时间，作业调度采用FC FS,主存中各作业平分CPU时间运行，现有如下作业序列：作业进入后备队列时间运行时间主存需求量磁带机需求打印机需求J16：0025分15M11J26：2020

16、分40M01J36：2020分60M10J46：3020分20M10回答下列问题：（1）作业被调度的先后次序。（2 分）（2）全部作业运行结束时间。（2 分）（3）各作业的周转时间。（2 分）（4）作业平均周转时间。（1 分）46.（7 分）考虑下图以太网配置，X、Y、Z 为主机，B1B3为网桥，网桥的转发表初始化为空。问:（1）X 发一个数据帧给Y,哪些网桥收到了这个帧？（1 分）Z 的网卡能否收到该帧？（1 分）（2）丫发一个数据帧给X,哪些网桥收到了这个帧？（1 分）Z 的网卡能否收到该帧？（1 分）（3）按表绘制网桥B1这时的转发表。（1 分）（4）简述网桥的数据帧转发过程。（2 分）主机下一结点47.（4 分）以下是一个十六进制的UDP数据段首部：06 32 00 0D 00 IC E2 17 ,参考下图所示UDP首部格式，回答问题：位0-1516310来源连接端口目的连接端口32报长检查码（1）源端口号和目的端口号（十进制）分别是多少？（2 分）（2）数据段总长度是多少？（1 分）（3）发出数据段的进程是客户还是服务器？（1 分）