2016年东南大学935计算机专业基础考研真题(回忆版)【圣才出品】

计算机学科2016考研真题1、合同主体11 甲方（出售方）：姓名：＿___________________身份证号：＿___________________12 乙方（购买方）：姓名：＿___________________身份证号：＿___________________2、合同标的21 本合同的标的为计算机学科 2016 考研真题。

22 该真题应包含计算机学科当年考试的全部科目及题型，且内容完整、准确、清晰。

3、权利义务31 甲方的权利义务311 甲方有权按照约定的价格向乙方出售考研真题。

312 甲方有义务保证所提供的考研真题真实、有效，且未经过篡改或伪造。

313 甲方应在约定的时间内将考研真题交付给乙方。

32 乙方的权利义务321 乙方有权要求甲方提供真实、有效的考研真题。

322 乙方有义务按照约定的价格向甲方支付购买真题的费用。

323 乙方不得将所购买的考研真题用于非法目的，如传播、售卖等。

4、违约责任41 若甲方未能按照约定提供真实、有效的考研真题，甲方应退还乙方已支付的费用，并按照费用的一定比例向乙方支付违约金。

42 若乙方未按照约定支付费用，每逾期一天，应按照未支付金额的一定比例向甲方支付滞纳金。

43 若乙方将考研真题用于非法目的，乙方应承担由此产生的一切法律责任，并向甲方支付高额的赔偿金。

5、争议解决方式51 本合同在履行过程中发生的争议，由双方协商解决。

52 协商不成的，任何一方均有权向合同签订地的人民法院提起诉讼。

6、其他条款61 本合同自双方签字（或盖章）之日起生效。

62 本合同一式两份，双方各执一份，具有同等法律效力。

63 本合同未尽事宜，可由双方另行签订补充协议。

补充协议与本合同具有同等法律效力。

2016年全国硕士研究生入学统一考试《计算机学科专业基础综合》真题(总分：150.00，做题时间：180分钟)一、单项选择题(总题数：40，分数：80.00)1.已知表头元素为c的单链表在内存中的存储状态如下表所示现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a,e,f的“链接地址”依次是（）。

（分数：2.00）A.1010H，1014H，1004HB.1010H，1004H，1014HC.1014H，1010H，1004HD.1014H，1004H，1010H√prev data next结点，正确的语句序列是（）。

（分数：2.00）A.p->next->prev=p->prev;p->prev->next=p->prev;free(p);B.p->next->prev=p->next;p->prey->next=p->next;free(p);C.p->next->prev=p->next;p->prev->next=p->prev;free(p);D.p->next->prey=p->prey;p->prev->next=p->next;fr ee(p);√3.设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。

现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。

若期望驶出的次序依次为1～9，则n至少是（）。

2.00）A.2B.3C.4√D.54.有一个100阶的三对角矩阵M，其元素mi,j(1≤i≤100，1≤j≤100)按行优先次序压缩存入下标从0开始的一维数组Ⅳ中。

元素m30,30在N中的下标是（）。

（分数：2.00）A.86B.87√C.88D.895.若森林F有15条边、25个结点，则F包含树的个数是（）。

2017年东南大学935计算机专业基础考研真题（回忆版）一、选择题（共80分）1．在多对一的线程模型中，一个多线程中的某个线程执行一个需阻塞的系统调用时，下列选项中正确的是（）A．整个进程都将被阻塞B．该进程的其他线程仍可继续执行C．该阻塞线程将被撤销D．该阻塞线程将阻塞直到进程退出2．进程可能发生调度的时机为（）Ⅰ．正在执行的进程时间片用完Ⅱ．正在执行的进程提出I/O请求进入等待Ⅲ．系统创建新进程Ⅳ．等待从硬盘中读数据的进程获得了数据A．ⅠB．Ⅱ、ⅣC．Ⅰ、Ⅲ、ⅣD．Ⅰ、Ⅱ、Ⅲ、Ⅳ3．某分段系统，地址为32位，段号为8位，最大段长为多少位（）A．2^8B．2^16C．2^24D．2^324．关于临界区，正确的是（）A．访问临界资源的那段代码B．访问共享资源的那段代码C．用于系统同步的那段代码D．用于系统互斥的那段代码5．访问主存的时间为100ns，访问快表的时间为10ns，TLB命中率为0.9，平均访问时间为（）A．119nsB．130nsC．120nsD．125ns7．有一个链接结构的文件，其中被链接的每个物理块存放一个逻辑记录和一个链接指针。

目前，该文件中共存放了1、2、3、4、5五个逻辑记录。

假设对应于该文件的目录项已经在主存储器中，那么完成删除记录4最少需访问磁盘几次（）A．1B．2C．3D．5连续分配和非连续分配方式中，哪些产生内部碎片哪些产生外部碎片问题13．通过破坏产生死锁的必要条件之一，可以保证死锁的不发生，资源有序分配破坏的是（）A．互斥条件B．不剥夺条件C．占有并等待条件D．循环等待条件14．有关银行家算法正确的描述为（）Ⅰ．银行家算法是死锁预防Ⅱ．银行家算法是死锁避免Ⅲ．银行家算法中不安全状态，一定会是死锁Ⅳ．银行家算法中不安全状态，未必是死锁15．请求分页管理中，逻辑地址为32位，页面大小为8192B，两级页表，每一个页表项2B。

则外层页表、内层页表、页内偏移分为占多少位（）A．10，10，12B．6，13，13C．7，12，13D．7，13，1216．有关颠簸的描述正确的有（）Ⅰ．颠簸时，CPU利用率迅速下降Ⅱ．颠簸时，应该增加进程，使CPU利用率提高Ⅲ．颠簸时，通过挂起进程，可以缓解内存Ⅳ．可变分配中的局部置换，不会发生颠簸现象17．一个n个元素的数组，左边全是1右边全是0，没有其他元素，问要找出1的个数，最佳的算法的时间复杂度是（）A．lognB．nC．根号nD．nlogn18．a[10][10][15]，每个数组元素占两个主存单元，问a[2][3][5]起始地址（）A．710B．720C．730D．74019．abcde依次入栈，问dc开头的出栈序列共有几个（）A．3B．4C．5D．620．哈夫曼树，不存在相同数值叶结点，错误的是（）A．树中不存在度为1的节点B．父层节点的数值不小于下一层节点数值C．这是一颗完全二叉树D．树中权值最小的两个节点一定是兄弟节点21．下列序列可能是二叉排序树的前序序列的是（）A．4，2，3，5，6，7B．4，3，2，7，6，5C．6，5，4，2，3，7D．6，5，3，4，2，722．无向图G如下图所示，可能是G的广度优先遍历序列的是（）A．a，b，e，c，f，dB．a，c，e，b，d，fC．a，c，b，e，f，dD．a，e，b，c，f，d23．用Prim算法（从顶点V0开始）和Kruskal算法构造下图的最小生成树，最后添加的一条边是（）24．如果缩短下图中的活动时间从而使整个工程的时间变短，选择哪个最合适（）（其他数字记不得了）。

计算机组成原理第一章：蓝字的三部分，和冯·诺依曼模型第二章：依旧是画蓝字的部分，其中字符的表示这里他着重说了一下。

还有溢出逻辑这里是重点部分。

比如判断A＜B，哪些寄存器为0哪些为1之类的。

校验码这里CRC和海明太麻烦，奇偶校验码比较简单，不过他今天一点都没有提到校验码的事情，不过我觉得CRC和海明几乎不用看。

几乎不用看的部分有：进制转换，原补码乘除，浮点数的加减。

重点是蓝字部分，Cache这重中之重，虚拟存储这主要是操作系统那考，计组这边主要考TLB。

多体存储器这里他也单独讲了下。

几乎不用看：DRAM，主存和CPU连接的需要画图的题第四章：比较简单，他也没怎么细说。

全看。

他今天重点说了一下，小端存储，大端存储，以及对齐方式和不对齐方式。

这边依旧主要看蓝字部分，但是需要跟其他章节的知识结合在一起，比如第二章、第六章、第七章。

大题也是出在这几章的结合题里。

时序是重点，微操作步序列、微操作命令序列几乎不用看：控制器的设计第六章：重点看蓝字部分，他还单独讲了一下性能指标这里，总线带宽。

几乎不用看：总线标准，多总线的I/O方式是重点，其中中断方式又是重点。

他还比较了一下无条件转移、程序查询、程序中断、DMA方式的速度。

压根没提到通道。

几乎不用看：输入输出设备，什么键盘啊鼠标啊显示器啊打印机啊最后：以考简单的基本原理为主，不考那种需要背的，复杂的。

以他的课本复习，尽量别用王道，练习题也是。

操作系统第一章：不出大题，重点：内核态、用户态、特权指令、访管指令、中断、系统调用第二章：重点：进程：概念、进程与程序的关系、进程的状态转换、PCB、进程切换线程：概念、多线程模型、进程与线程的区别CPU调度：这一块可能会出大题。

长中短期调度、调度的时机、典型调度算法（FCFS、SJF、优先级、RR、多级队列、多级反馈队列，后两者考得少）以及评价的标准（CPU利用率、周转时间、等待时间、响应时间、吞吐量）、护航效应护航效应：进程同步问题：临界区的概念、经典同步问题。

东南大学计算机技术岗位考试真题一、计算机基础知识（1 - 10题）1. 计算机中最小的存储单位是什么？（）A. 字节。

B. 位。

C. 字。

D. 双字。

答案：B。

解析：在计算机中，位（bit）是最小的存储单位，它表示一个二进制数位的值为0或1。

字节（Byte）是由8个位组成的存储单元，字和双字是根据计算机体系结构定义的更大的存储单位概念。

2. 以下哪种编程语言属于面向对象编程语言？（）A. C.B. Fortran.C. Java.D. Pascal.答案：C。

解析：Java是一种典型的面向对象编程语言，它具有类、对象、继承、封装、多态等面向对象的特性。

C语言是过程式编程语言，Fortran主要用于科学计算，是一种面向过程的语言，Pascal也是一种早期的过程式编程语言。

3. 计算机的硬件系统主要由哪几部分组成？（）A. 运算器、控制器、存储器、输入设备和输出设备。

B. 主机、显示器、键盘、鼠标。

C. 中央处理器、内存、硬盘、显示器。

D. 主板、CPU、内存、硬盘、显卡。

答案：A。

解析：计算机硬件系统由运算器、控制器（二者合称为中央处理器CPU）、存储器、输入设备和输出设备这五大基本部分组成。

选项B中主机包含了运算器、控制器和存储器等部分，但这种表述不够全面准确；选项C和D只是列举了部分硬件组件，没有涵盖硬件系统的完整组成结构。

4. 在计算机网络中，IP地址的作用是什么？（）A. 标识网络中的主机。

B. 提供网络连接的物理地址。

C. 用于加密网络通信。

D. 确定网络传输的速度。

答案：A。

解析：IP地址在计算机网络中用于唯一标识网络中的主机（或网络接口），以便在网络中进行数据的路由和传输。

物理地址是MAC地址，与IP地址不同；IP地址本身不用于加密网络通信；网络传输速度由网络设备的性能、网络带宽等多种因素决定，与IP地址无关。

5. 计算机操作系统的主要功能不包括以下哪一项？（）A. 进程管理。

B. 存储管理。

2016考研计算机学科专业基础综合真题及答案一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。

请在答题卡上将所选项的字母涂黑。

)1. 设n 是描述问题规模的非负整数，下面程序片段的时间复杂度是x=2;while(xx=2*x;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)解答：A。

程序中，执行频率最高的语句为“x=2*x”。

设该语句执行了t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。

2. 元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是A.3B.4C.5D.6解答：B。

出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。

3. 已知循环队列存储在一维数组A[0...n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。

若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是A.0,0B.0，n-1C.n-1,0D.n-1，n-1解答：B。

插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。

4. 若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是A.257B.258C.384D.385解答：C。

叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1(总结点数为偶数)，故而即2n=768。

5. 若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1解答：C。

由前序和后序遍历序列可知3为根结点，故(1,2)为左子树，(4)为右子树，C不可能。

东南大学考试卷（ A 卷） 学号姓名密 封 线自觉遵守考场纪律如考试作弊此答卷无效学号 姓名4.(3points) One technique for implementing a control unit is referred to as hardwiredimplementation, in which the control unit is a combinatorial circuit. Its input logic signals, governed by the current machine instruction, are transferred into a set of output control signals.二、Fill blanks (Total 10points, 2 points/blank)1. A computer has a cache of 8k Bytes and a main memory of 16M Bytes dressed on Bytes.The address format is 13, 8, and 3 bits for Tag, Set, and Word respectively. It is needed to compare tags to search a word in the cache. For one word access, the times of tag comparison is ( ) at most.puter memory is organized into a hierarchy. At the highest level (closest to theprocessor) are the processor ( ).3.In ( ) addressing, the operand value is present in the instruction.4.In register windows the ( ) at one level are physically the sameas the parameter registers at the next lower level.5.Some dependencies, such as the write-write dependency of a symbol, can be solved by( ).三、Select A, B, C, or D corresponding to the best answer from the given items (Total 10 points, 2 points/blank)1.When a processor accesses a cache, the reference address is ( )A.Register addressB.Cache addressC.Main memory addressD.Disk address2.By using the ( ), a word is retrieved based on a portion of its contents ratherthan its address.A.direct accessB.random accessC.sequential accessD.associative access3.If most memory references are relatively near to the instruction being executed, then theuse of ( ) addressing saves address bits in the instruction.A.directB.indirectC.registerD.relative4.To perform a sequence of 16 instructions using pipeline, each instruction is divided into4 stages FI, DI, EI and WO, where each of the stages require 1 cycle, 1 cycle, 2 cyclesand 1 cycle respectively. No branch is in the sequence. The speed up factor of the pipeline is ( )A.5B.16/7C.4D.64/195.The degree of instruction-level parallelism is determined by the frequency of ( )and procedure dependency in the code.A.Read-Write dependencyB.Write-Write dependencyC.Write-Read dependencyD.Resource conflict四、Answer according to given contents ( Total 10 points,2 points/blank)Based on the current microinstruction, condition flags, and the contents of the instruction register, a control memory address must be generated for the next microinstruction. A wide variety of techniques have been used. We can group them into three general categories. These categories are based on the format of the address information in the microinstruction: two address fields, single address field, and variable format.The simples approach is to provide two address fields in each microinstruction. A multiplexer is provided that serves as a destination for both address fields plus the instruction register. Based on an address-selection input, the multiplexer transmits either the opcode or one of the two addresses to the control address register (CAR). The CAR is subsequently decoded to produce the next microinstruction address. The address-selection signals are provided by a branch logic module whose input consists of control unit flags plus bits from the control portion of the microinstruction.Although the two-address approach is simple, it requires more bits in the microinstruction than other approaches. With some addition logic, saving can be achieved. A common approach is to have a single field. With this approach, the options for next address are address field, instruction register code, and next sequential address.The address-selection signals determine which option is selected. This approach reduces the number of address fields to one. Note, however, that the address field often will not be used. Thus, there is some inefficiency in the microinstruction coding scheme.Another approach is to provide for two entirely different microinstruction formats. One bit designates which format is being used. In one format, the remaining bits are used to activate control signals. In the other format, some bits drive the branch logic module, and the remaining bits provide the address. With the first format. The next address is either the next sequential address or an address derived from the instruction register. With the second format, either a conditional or unconditional branch is being specified. One disadvantage of this approach is that one entire cycle is consumed with each branch microinstruction. With the other approaches. Address generation occurs as part of the same cycle as control signal generation, minimizing control memory accesses.The approaches just described are general. Specific implementations will often involve a variation or combination of these techniques.(1)Give a title for the above phases:(2)What are the “other approaches” underlined in the third phase?(3)What are the “these techniques” underlined in the last phase?(4)What are the “two entirely different microinstruction formats” underlined in the fifthphase?(5)Which of the mentioned address designate techniques has the highest bit efficiency onaverage? Why?五、Questions (Total 10 points)1.(4points) What is the relationship among direct mapping, associative mapping, and setassociative mapping in cache design?2.(3points) What are characteristics of RISC?3.(3points) What is the purpose of an instructionwindow?六、Problems (Total 48 points)1.(5 points) Suppose that a processor has access to two levels of memory. Level 1 contains1000 words and has an access time of 0.01 us; level 2 contains 100,000 words and has an access time of 0.1 us. Assume that if a word to be accessed is in level 1, then the processor accesses it directly. If it is in level 2, then the word is first transferred to level1 and then accessed by the processor. For simplicity, we ignore the time required for theprocessor to determine whether the word is in level 1 or level 2. Shows the average access time to the two-level memory as a function of the hit ratio H using a figure, where H is defined as the fraction of all memory accesses that are found in the faster memory.2.(5 points) An encoded microinstruction format is to be used. Show how an 8-bit micro-operation field can be divided into subfields to specify 38 different actions.3.(5 points) To compute Y=(A-B)÷(C+D ×E), we can use one-, two-, or three-address instructions, and we can also use zero addresses for some instructions. Zero-address instructions are applicable to a special memory organization, called a stack.a)Convert Y=(A-B)÷(C+D ×E) from infix to reverse Polish;b)List the instructions using a stack to compute Y=(A-B)÷(C+D ×E).4.(5 points) An instruction is 4 bytes long, and the start address in byte of the instruction is 360000 in decimal. PC-relative addressing mode is used in the instruction to access 0.010.1 0.111an operand and the displacement value in the address field is -30. Determine the address of the target operand.5.(10 points) A four-way set-associative cache has lines of 16 bytes and a total size of8kbytes.The main memory of 16-Mbyte is byte addressable.a)Show the format of main memory addresses;b)CPU is to read a data with address ABCDEF from the Cache-Memory structure.Describe the reading process step by step considering the cases of Hit and Miss;c)Draw a block diagram of this cache showing its organization and how the differentaddress fields are used to determine a cache hit/miss.6.(10 points) The instruction “AND X, (Y)” includes the following stages:a.Instruction Fetchb.Load AC the Data with address Xc.Indirect Addressingd.AND executione.Store AC to memory with address XShow the micro-operations of these stages and the corresponding control signals gate inthe figure.7.(8 points) Consider the following programA compiler for a RISC machine can either insert NOOP instructions or use delayed branch todeal with data dependencies and procedure dependences among instructions in the operation of pipelines. Assume that each instruction is divided into three stages: Fetch, Execute, (with or without) Write,a.Show the compiled code using NOOP instruction.b.Show the compiled code using delayed branch method.c.Draw diagrams to show the timing of instruction pipelines for traditional pipeline, RISCpipeline with inserted NOOP, and RISC pipeline with delayed branch.。

选择：12。

运行程序，打印输出行数为（）Intmain(intorgc,char *argv[]){int i,id1,id2;for(i=1;i<2;i++){id1=fork();id2=fork();if(id1==0||id2==0){fork();}Printf(“2 am %d\n”,getpid(1));}A.5B.6C.7D.8（考操作系统的fork()，getpid()函数）41、对于如下表格中的页访问序列，请按照表格的形式，分别写出使用最优OPT、LRU算法的页替换过程，并分别计算缺页中断率。

其中，表格中的横杠符号“—”表示页框空闲，当有多个页可以作为页替换的牺牲对象时，总是选择最低页框号42、在一个单处理器系统中，假设有四个进程（P1～P4），它们的到达时刻分别为0，10，20，30，完成作业所需时间分别为30，10，5，10.如果对以上进程分别采用先来先服务和可抢占式最短作业优先策略进行调度处理，请回答下列问题：（1）请分别画出不同调度策略下，四个进程执行过程的甘特图（2）如果忽略上下文切换时间，不同调度策略下四个进程的平均等待时间和平均周转时间分别是多少？（3）假设每次上下文切换时间为1，不同调度策略下四个进程的平均周转时间分别是多少？43、若干个发送进程通过一个缓冲区向两个接受进程不断发送信息，缓冲区最多可存放m条消息。

每个发送进程一次发送一个消息，当缓冲区满时，发送进程等待；对于每一个消息，两个接受进程各需接收一次，当两个进程都接收后，从缓冲区中移除该消息。

请使用信号量描述上述进程间的同步关系。

44、已知无向图G中各个顶点的度如下，请回答下列问题：（1）（2）说明你所采用的方法45、试编写效率尽可能高的方法，找出一个整数序列A中所有和等于给定数K 的连续子序列。

例如：若A为{5，7，3，3，3，9，14，4，11，5，5，4，14，14，8}，K=25,则有（序列A中元素位置的编号从0开始）：复杂度。