南京大学计算机考研试题.pdf
南京大学计算机考研试题 文档编制序号：KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688 2015南京大学计算机845考研试题 说明：本人在 28 号考试过程中抄下来的，时间有限有部分试题（13 个选择/共 40个，1 个算法大题/大题共 7 个）遗漏，后又根据论坛和考研群其他研友的回忆版资料进行过补充，基本完全。其余因笔记仓促亦可能有少量笔误，见谅。望后来考生，应知年与时驰、意与日去，备考及早动手，坚持到底，衷心祝福大家都能学有所成，梦想成真。感谢在我半年备考期间与我同一自习室复习的研友们，陈梅，王超，李玲，李浩，大白，王丽坤。感谢好友比助，姗姗，贝贝，成云，康师傅，丁小琳。感谢王道南大考研群诸位学长学姐和战友们，let，嘛嘛，木哥，Tomorrow，胸大的绿色兔子汪 a（没错我就是在黑你），六月（强迫症死敌！），地下铁（真诚祝福兄弟），句号，皮卡丘，倩倩，唯安，沧海，浅月，绝，别情，夜吟，风之天炼，河北的妹子 i（冒泡一次激励我三天加倍努力），亮靓（学妹加油），马克图布。仰头望明月，寄情千里光。愿你们拥有想要的未来，想去的远方。2014 年 12 月 30 日于天津师范大学劝学楼 C 区 503 自习室。作者：王道论坛章凝苏 一、单项选择题（40X2 分）1.和动态链表相比，以下反映了静态链表缺点的是（）A.插入、输入输出操作不便 B.存储空间有时得不到充分利用 C.要求各结点有相同的类型 D.表中各结点只能读取不能修改 2.二维数组 A810按列优先次序存储在起始地址为 0 的连续内存单元中，其中每个元素占 5 个单元，元素 A6，7的存储地址是（）A.275 B.310 C.315 D.330 3.二叉线索树中执行较困难的运算是（）A.中序线索树下查找结点的前驱 B.中序线索树下查找结点的后继 C.前序线索树下查找结点的前驱 D.后序线索树下查找结点的前驱 4.设散列表为 H11（下标从 0 开始）。将关键码序列（20，15，19，43，67，30）散列到该地址空间中，散列函数为 H(key)=key%11，处理冲突采用线性探查法。则等概率情况下查找成功时平均搜索长度是（）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(n2)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*e2)B.O(n3)C.O(n2)D.O(n 的平方再乘以 e)12.既希望较快查找又便于线性表动态变化的查找方法是（）A.顺序查找 B.折半查找 C.分块查找 D.基于属性的查找法 13.假定某程序在计算机 A 上运行需要 10 秒钟，A 的时钟频率为 1GHz。现在硬件设计人员想设计计算机 B，希望该程序在 B 上的运行时间缩短为 8 秒钟，而使用新技术可以使时钟频率大幅度提高，但在 B 上运行该程序所需要的时钟周期数是 A 上的 1.5 倍。那么，B 的时钟频率至少应为多少，才能达到希望的要求（）A533MHz 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=758E 0000H，y=C0D3 0000H，计算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 开始，主存单元 0 x8048900 所在主存块对应的 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 同学）9.A.FCFS?B.最佳置换算法 OPT?C.LRU?D.（忘了）10.已知 IP 网络地址（形如：）,现有 4 台主机，问使用多少位掩码（描述可能不规范，就是划分后的子网占多少位）来划分最为经济？（感谢王道论坛musttome同学）11.A.27?B.28?C.29?D.30 12.使用停止-等待协议，已知单程传播时间和数据发送速率，帧为多大才能使数据传输效率大于 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 /二叉树链表结点 int data;struct PtrNode*llink,*rlink;class PtrNode()private:PtrNode*ptrArrayMaxSize;/栈 PtrNode*p;/初始为根结点 int t=-1;/栈顶指针 public:void InOrder()while(p!=NULL&t!=-1)if(_(1)_)/当左结点非空时（3 分）_(2)_;/（3 分）p=p-llink;else _(3)_;/（3 分）_(4)_;/（3 分）p=p-rlink;43.（23 分）下图是某个早期计算机 M 的结构示意图。M 字长 16 位，存储器按字节编址，小端方式存储数据，其 ALU 中包含了一个补码加/减运算器以及各类逻辑运算部件和移位部件，无乘/除法器。在 M 中取指令过程如下：PCMAR地址线；“读命令”控制线；存储器读出命令数据线MDRIR。以下是一个 C 语言程序 add：Void main()int x=32767;int y=2;printf(“sum=%d”,x+y);已知 sizeof(int)=2，回答并计算下列问题：（1）图中 PC，MAR，ALU，IR 的中文含义（4 分）（2）若 k 和 N 分别为 8 和 1M，通用寄存器编号至少几位？地址线至少多少根？（2分）（3）M 是否肯定不能提供乘法指令？为什么？（2 分）（4）若 M 的指令集没有除法指令，则 M 是否一定不能实现赋值语句“z=x/y”？为什么？（2 分）（5）程序 add 在 M 上执行结果为”sum=-32767”，请解释为什么 add 的结果为-32767？（3 分）（6）变量 x 地址为 C0050H，则执行到 printf 语句时，存储单元 C0050H 中内容（用十六进制表示）是什么？（2 分）（7）要使 M 执行程序 add 过程中能发现溢出并调出“溢出处理程序”执行，则 M 中的“带符号加法指令”不仅要能进行加法运算，还要能根据溢出标志位（OF）来触发“溢出异常”，请问溢出判断条件是什么？简要说明从 CPU 发现溢出异常到操作系统执行“溢出处理程序”的过程。（4 分）（8）程 序add中 计 算x+y的 加 法 指 令 为“add R0,(R1)”，其 功 能为”RR0RR0+MRR1”，其中 RRi表示寄存器 Ri 内容为地址的存储单元的内容，请仿照题目中给出的取指令过程的描述给出“add R0,(R1)”指令执行过程的描述。（4 分）44.（8 分）有 7 个哲学家围坐在圆桌边，两人之间有一把吃饭的叉子。哲学家在思考一段时间（Thinking()）后，要吃饭。在拿到左右两把叉子时，才可吃饭 （Eating()）。在饭后，要去健身（Playing()）。共有 3 套健身器材，健身时每人独占一套。健身之后，继续工作。请用信号量和 PV 操作写出哲学家们并发工作的程序，要求不会出现死锁，并说明信号量含义。45.（7 分）某多道程序系统，用户作业可使用主存容量为 100M，主存管理采用可变分区方法，优先分配低地址区且不准移动。系统有磁带机 2 台，打印机 1 台，外设分配采用静态方法。忽略 I/O 时间，作业调度采用 FCFS，主存中各作业平分 CPU 时间运行，现有如下作业序列：作业 进入后备队列时间 运行时间 主存需求量 磁带机需求 打印机需求 J1 6：00 25 分 15M 1 1 J2 6：20 20 分 40M 0 1 J3 6：20 20 分 60M 1 0 J4 6：30 20 分 20M 1 0 回答下列问题：（1）作业被调度的先后次序。（2 分）（2）全部作业运行结束时间。（2 分）（3）各作业的周转时间。（2 分）（4）作业平均周转时间。（1 分）46.（7 分）考虑下图以太网配置，X、Y、Z 为主机，B1B3 为网桥，网桥的转发表初始化为空。问：（1）X 发一个数据帧给 Y，哪些网桥收到了这个帧？（1 分）Z 的网卡能否收到该帧？（1 分）（2）Y 发一个数据帧给 X，哪些网桥收到了这个帧？（1 分）Z 的网卡能否收到该帧？（1 分）（3）按表绘制网桥 B1 这时的转发表。（1 分）（4）简述网桥的数据帧转发过程。（2 分）47.（4 分）以下是一个十六进制的 UDP 数据段首部：06 32 00 0D 00 1C E2 17，参考下图所示 UDP 首部格式，回答问题：位 015 1631 0 来源连接端口 目的连接端口 32 报长 检查码（1）源端口号和目的端口号（十进制）分别是多少？（2 分）（2）数据段总长度是多少？（1 分）（3）发出数据段的进程是客户还是服务器？（1 分）主机 下一结
