重庆理工大学计算机科学与工程学院计算机学科专业基础综合历考研真题大全附答案

1、重庆理工大学计算机科学与工程学院813计算机学科专业基础综合历年考研真题汇编最新资料，WORD式，可编辑修改！目录第一部分重庆理工大学计算机科学与工程学院810计算机学科专业基础综合历年考研真题汇编2014年重庆理工大学计算机科学与工程学院810计算机学科专业基础综合考研真题2013年重庆理工大学计算机科学与工程学院809计算机学科专业基础综合考研真题1说明：重庆理工大学计算机学科专业基础综合的科目代码每年都不同，2015年改为813。第二部分全国硕士研究生入学统一考试408计算机学科专业基础综合历年真题及详解12012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题12012年全

2、国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解：2011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题42011年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解f2010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题72010年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解E2009年全国硕士研究生入学统一考试408计算机学科专业基础综合真题next=NULLC. head!=NULLD. head-next!=NULL11 .有一个有序表为2,3,8,10,30,当折半查找到8时，需要的比较次数为（）A. 1B.

3、 2C. 3D. 412 .栈的插入与删除操作在（）A.栈顶B.栈底C.队头D.队尾13 .一个栈的入栈顺序是a,b,c,则该栈的不可能的输出序列是（）A. abcB. cbaC. acbD. cab14 .设先序遍历某二叉树的序列为ABC中序遍历该二叉树的序列为BAC则后序遍历该二叉树的序列为（）A. ABCB. CBAC. ACBD. BCA15 .设一组初始记录关键字序列（5,2,6,3）,以第一个记录关键字5为基准进行一趟快速排序的结果为（）A. 2,3,5,6B. 5,2,3,6C. 3,2,5,6D. 2,3,6,516 .在计算机中配置操作系统的主要目的是（）A.增强计算机的功能

4、B.提高系统资源的利用率C.提高系统的运行速度D.合理组织系统的工作流程17.从静态角度讲，进程由程序段、数据段和（）组成，它是进程存在的唯一标志。A. JCBB. PCBC. FCBD.代码段18.临界区是指（）A.进程中用于访问共享资源的那段代码。B.进程中用于实现进程同步的那段代码。C.进程中用于实现进程互斥的那段代码。D.进程中用于访问临界资源的那段代码。19.下面哪种情况不会引发进程调度？（）A.进程正常结束或异常中止。B.正在执行的进程因I/O请求而被阻塞。C.某等待打印机的进程发现其它使用打印机的进程已经打印完毕。D.在引入时间片的系统中，时间片用完。20.内存管理的基本任务是提

5、高内存的利用率，使多道程序能在不受干扰的环境中运行，这主要是通过下面哪种功能实现的？（）A.内存分配B.内存扩充C.内存保护D.兑换21.在一般大型系统中，主机对外围设备的控制可通过通道、控制器和设备三个层次来实现。从下述中选择一个正确的叙述。（）A.通道控制控制器，设备在控制器控制下工作。B.控制器可控制通道，设备在通道控制下工作。C.通道和控制器分别控制设备。D.控制器控制通道和设备。22.在文件系统中，必须为每个文件建立（），其中包括文件名和文件的物理地址等信息。A.用户文件描述符表B.索引结点C.文件控制块D.索引表23.磁盘调度的策略主要是为了优化（）A.交换时间B.寻道时间C.旋转

6、延迟时间D.传输时间24.动态重定位的主要目的是使作业在内存中移动，动态重定位发生在（）A.编译过程B.装入过程C.链接过程D.运行过程25 .在命令行接口中，使命令的执行结果不在屏幕上显示，用于把第一条命令的输出作为第二条命令的输入，第二条命令的输出作为第三条命令的输入的功能设施称为（）A.管道B.链接C.脱机输入D.联机输出二、简答题（每题5分，共60分）26 .计算程序段的时间复杂度。（5分）for（i=1;i=n;i+）x+;27 .设给定权集W=23,4,7,试构造关于W的一棵赫夫曼树，并求其带权路径长度WPL（5分）28 .设有一序列30,19,3,61,请按该序列构成一棵二叉排序

7、树，并求其查找成功时的平均查找长度ASL（5分）29 .写出下图所示二叉树的先序，中序和后序遍历序列。（5分）30 .什么是线性表？线性表的元素之间的关系是什么？（5分）31 .已知待散列的线性表为（8,15,40,63）,散列用的一维地址空间为0.6,假定选用的散列函数是H（K）=Kmod7,若发生冲突采用线性探查法处理，计算出每一个元素的散列地址并在下图中填写出散列表。（5分）012345632 .请画图说明进程的三种基本状态及各状态间的转换，并说明引发状态转换的典型事件。（5分）33 .什么是操作系统，简述操作系统的主要功能。（5分）34 .什么是死锁，分析死锁发生的主要原因。（5分）3

8、5 .虚拟存储器的基本特征有哪些？为什么说请求分页系统是实现虚拟存储器是一种方式？（5分）36 .什么是中断，描述CPU问中断的一般过程。（5分）37 .在公共汽车上，司机与售票员的工作流程如下图所示。为保证乘客安全，司机和售票员必须密切配合协调工作，售票员在关车门之后向司机发送开车信号，司机接到开车信号后启动车辆，汽车正常行驶时售票员可以售票，到站时司机停车，售票员在停车后开门让乘客下车，请用信号量来实现司机与售票员之间的同步。（5分）三、综合题（每题10分，共40分）38 .编写一个函数，实现对数组a（元素个数为n）中元素进行冒泡排序的算法。（10分）voidbubblesort(inta

9、口)39 .编写两个函数，分别实现对二叉树的先序遍历(preorder)和中序遍历(inorder)的递归算法。(10分)二叉树结点的结构体为structBiTreeNodeintdata;structBiTreeNode*leftChild;structBiTreeNode*rightChild;；typedefstructBiTreeNodeNode;voidpreorder(Node*t)/*t为指向二叉树的根结点的指针*/voidinorder(Node*t)/*t为指向二叉树的根结点的指针*/40 .(本题10分)有四个进程P1,P2,P3,P4,它们进入就绪队列的先后顺序为P1,P

10、2,P3,P4,它们的优先级和需要的处理机时间如下表。假定这四个进程在执行过程中不会发生等待事件，忽略进程调度所花费的时间，从某个时刻开始进程调度，请回答下面的问题：进程要求的处理时问优先级P183P261P3225P444(1)采用“先来先服务”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；(4分)(2)采用“非抢占式的优先级”调度算法时，写出进程的执行顺序，计算各进程在就绪队列中等待的时间以及平均等待时间；(4分)(3)说明采用“时间片轮转法”调度算法时，写出进程的执行顺序，计算各进程在系统中停留的时间以及平均停留的时间。(2分)41.(本题10分)某系

11、统采用页式存储管理策略，请回答下面的问题：(1)若逻辑空间为32页，每页2K,物理空间1M写出逻辑地址的格式。若不考虑访问权限等，进程的页表有多少项，每项至少多少位？如果物理空间减少一半，页表结构应相应地怎样变化。(6分)(2)假定页表放在内存中，如果访问内存需要0.3s,计算有效访问时间；(2分)(3)如果加一快表，且假定在快表中找到页表项的几率高达90%则有效访问时间又是多少？(2分)2013年重庆理工大学计算机科学与工程学院809计算机学科专业基础综合考研真题学院名称：计算机科学与工程学院学科、专业名称：计算机科学与技术考试科目（代码）：809计算机学科专业基础综合（A卷）一、选择题1

12、.深度为2（根结点的层次号为1）的满二叉树的叶子结点个数为（）A. 2B. 3C. 4D. 62 .栈的特点是（）A.先进后出8 .先进先出C.同进同出D.同出同进3 .双向链表的指针域的个数为（）A. 0B. 1C. 2D. 34 .完全二叉树，按层次序列编号（根结点编号为1）,则编号为2的结点的左孩子的编号为（）A. 3B. 4C. 5D. 65 .具有m个顶点的无向完全图的边的数目为（）A. m（m+D/2B. m（m-1）/2C. m（m-1）D. m（m+D6 .顺序表的第1个元素存储地址是100,每个元素占用2个存储单元，则该顺序表的第3个元素地址是（）A. 102B. 104C.

13、 106D. 1087 .数据的存储结构可分为链式存储结构和（）A.顺序存储结构8 .哈希存储结构C.索引存储结构D.表存储结构9 .数据元素之间有四种基本逻辑结构，下列描述中是逻辑结构的是（）A.圆形结构8 .树形结构C.方形结构D.菱形结构9 .下列不属于线性结构的是（）A.线性表10 栈C.队列D.图10.满二叉树，按层次序列编号（根结点编号为1）,则编号为3的结点的双亲编号为（）A. 1B. 2C. 3D. 411 .第二代计算机是以（）为主要器件的。A.电子管B.晶体管C.二极管D.触发器12 .动态RAM本电路单元是靠（）来寄存信息的。A.电阻B.电容C.二极管D.晶体管13 .主

14、机、外设串行工作的方式是（）。A.程序查询B.程序中断C. DMAD. I/O处理机14.以下有关运算器的叙述，正确的是（）。A.只做加法运算B.只做算术运算C.既做算术运算又做逻辑运算D.只做逻辑运算15.指令周期是指（）。A. CPUA主存取出一条指令的时间B. CPUA主存取出一条指令加上执行指令的时间C.节拍周期时间D.时钟周期时间16.某存储器芯片规格为8Kx1位，则它的地址线和数据线共有（）根。A. 15B. 14C. 13D. 1217.Cache是为解决CPUt（A.硬盘B.光盘C.总线D.内存18.计算机系统I/O接口是（）之间速度不匹配而采用的一项技术。）之间的交接界面。A

15、.CPUf存储器B.主机与外设C.系统总线与CPUD.CPUtfCache19.DMA于高速数据块的传送，直接在（送。A.内存B.硬盘C. CPUD. Cache20.在指令操作完成后，PC中存放的是（A.下一条顺序执行的指令地址）和外设之间进行数据传B.当前指令的地址C.转移指令的地址总线D.停机指令的地址总线21.微程序存放在（）中。A.控制存储器B.硬盘C.指令寄存器D.光盘22.CPU向应中断的时间是（A.任一机器周期结束时B.外设提出中断时C.取指周期结束时D.一条指令执行结束时23.能够改变程序执行顺序的（A.数据传送指令B.加法操作指令C.跳转指令D.输入输出指令24.在主机中能

16、对指令进行译码的器件A. MARB. ALUC.控制器D.MDR25.操作数在寄存器中的寻址方式称为（）寻址。A.立即B.直接C.寄存器直接D.基址26 .操作系统的主要功能是管理计算机系统中的资源，其中包括（）管理和存储器管理，以及设备管理和文件管理。A.存储器B.虚拟存储器C.硬盘D.处理机27 .从用户的观点看，操作系统是（）A.用户与计算机之间的接口B.控制和管理计算机资源的软件C.合理地组织计算机工作流程的软件D.由若干层次的程序按一定的结构组成的有机体28 .多道程序设计是指（）oA.在实时系统中并发运行多个程序B.在分布式系统中同一时刻运行多个程序C.在一台处理器上同一时刻运行多

17、个程序D.在一台处理器上并发运行多个程序29 .下列选择中，当（）时，进程的状态从运行状态转为就绪状态。A.进程被进程调度程序选中B.进程时间片用完C.进程等待I/O操作D.进程I/O操作完成30 .进程控制块是描述进程状态的数据结构，一个进程（）。A,可以有多个进程控制块B.可以和其它进程共用一个进程控制块C,可以没有进程控制块D.只能有唯一的进程控制块31 .按照作业到达的先后顺序调度作业，排队等待时间最长的作业优先调度，这是指（）调度算法。A.先来先服务B.短作业优先C.响应比高优先D.时间片轮转32 .在下列存储管理方案中，不适应于多道程序设计的是（）。A.单一连续区分配B.固定式分区

18、分配C.可变式分区分配D.段页式存储管理33 .访问磁盘的时间不包括（）。A.寻道时间B.CPUM度时间C.读写时间D.旋转等待时间34 .下面关于虚拟设备的论述中，正确的是（）A.虚拟设备是指允许用户使用比系统中具有的物理设备更多的设备B.虚拟设备是指允许用户以标准化方式来使用物理设备C.虚拟设备是把一个物理设备变换成多个对应的逻辑设备D.虚拟设备是指允许用户程序不必全部装入内存便可使用设备系统中的设35 .文件系统的按名存取主要是通过（）来实现的。A.存储空间管理B.目录管理C.文件安全性管理D.文件读写管理36 .物理地址的长度是（）A.16bitB.32bitC48bitD.128bi

19、t37.下列传输介质中，传输光信号的是（）A,双绞线B.光纤C.同轴电缆D.电话线38.下列描述中，属于多路复用技术的是（）A,双分复用技术B.频分复用技术C.单分复用技术D.角分复用技术39.数据通信线路的工作模式分为单工通信、全双工通信和（）A.多播通信B.组播通信C.半双工通信D.P2P通信40.下列协议中属于网络层协议的是（）A.DNSB.SMTPC.IPD.HTTP二、综合题41 .计算程序段的时间复杂度（5分）t=0;for（i=1;i=N;i+）for（j=1;j=N;j+）for（k=1;k0)阶乘的算法如下，其时间复杂度是()。A. O(log2n)B. 0(n)C. O(n

20、log2n)D. O(n2)2,已知操作符包括+、-、*、/、(和。将中缀表达式a+b-a*(c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是()。A. 5B. 7C. 8D. 113.若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点()。A.只有eB.有e、bC.有e、cD.无法确定4 .若平衡二叉树的高度为6,且所有非叶结点的平衡因子均为1,则该平衡二叉树的结点总数为()。A. 12B. 20C. 32D.

21、 335 .对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是()。A. 0(n)B. 0(e)C. O(n+e)D. O(nxe)6 .若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是()。A.存在，且唯一8 .存在，且不唯一不唯一C.存在，可能不唯一D.无法确定是否存在7.有向带权图如题7图所示，若采用迪杰斯特拉(Dijkstra)算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是（）。题7图有向带权图A. d,e,fB. e,d,f

22、C. f,d,eD. f,e,d8 .下列关于最小生成树的叙述中，正确的是（）。I.最小生成树的代价唯一葭所有权值最小的边一定会出现在所有的最小生成树中田.使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同IV,使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A.仅I9 .仅HC.仅I、mD.仅H、IV10 设有一棵3阶B树，如题9图所示。删除关键字78得到一棵新B树，其最右叶结点所含的关键字是（）。题9图3二叉树图A. 60B. 60,62C. 62,65D. 6510.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每

23、一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。I.简单选择排序葭希尔排序田.快速排序IV.堆排V.二路归并排序A.仅I、m、IVB.仅I、n、mC.仅H、m、IVD.仅田、IV、V11 .对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是（）。A.排序的总趟数B.元素的移动次数C.使用辅助空间的数量D.元素之间的比较次数12 .假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间，其余为I/O时间。若CPUS度提高50%,I/O速度不变，则运行基准程序A所耗费的时间是（）。A. 55秒B. 60秒C. 65秒D. 70秒13.假定编译器规定

24、int和short类型长度分别为32位和16位，执行下列C语言语句：unsignedshortX=65530;unsignedinty=X：得至Uy的机器数为（）。A. 00007FFAHB. 0000FFFAHC. FFFF7FFAHD. FFFFFFFAH14 .float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是A.B.C.O2126-22127-22127-2103104103D.2128 2 10415 .某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：若reco

25、rd变量的首地址为0xC008,则地址0xC008中内容及record.c的地址分别为（A. 0x00、0xC00DB. 0x00、0xCOOEC. 0x11、0xC00DD. 0x11、0xC00E16 .下列关于闪存（FlashMemory）的叙述中，错误的是（）。A.信息可读可写，并且读、写速度一样快B.存储元由MOST组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可替代计算机外部存储器17 .假设某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为l个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU换算法，当访

26、问的主存地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是（）。A. 1B. 2C. 3D. 418 .某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（）。A. 5位B. 6位C. 15位D. 33位19 .某同步总线的时钟频率为100MHz,宽度为32位，地址/数据线复用,每传输一个地址或数据占用一个时钟周期。若该总线支持突发（猝发）传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（）。）A. 20nsB. 40nsC. 50

27、nsD. 80ns20.下列关于USB总线特性的描述中，错误的是（）。A.可实现外设的即插即用和热插拔B.可通过级联方式连接多台外设C.是一种通信总线，可连接不同外设D.同时可传输2位数据，数据传输率高21.下列选项中，在I/O总线的数据线上传输的信息包括（）。I.I/O接口中的命令字n.I/0接口中的状态字m.中断类型号A.仅I、nB.仅I、mC.仅n、田D.I、n、田22.响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（）。I.开关中断R.保存通用寄存器的内容田.形成中断服务程序入口地址并送PCA.仅I、nB.仅i、mC.仅n、田d.i、n、田23.下列选项中，不可能在用

28、户态发生的事件是（）。A.系统调用B.外部中断C.进程切换D.缺页24.中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）。A.程序计数器B.程序状态字寄存器C.通用数据寄存器D.通用地址寄存器25 .下列关于虚拟存储的叙述中，正确的是（）。A,虚拟存储只能基于连续分配技术B.虚拟存储只能基于非连续分配技术C.虚拟存储容量只受外存容量的限制D.虚拟存储容量只受内存容量的限制26 .操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（）。A.用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序

29、B.用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序C.用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序D.用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序27 .假设5个进程PRPl、P2、P&P4共享三类资源Rl、R2R3,这些资源总数分别为18、6、22。T0时刻的资源分配情况如题27表所示，此时存在的一个安全序列是（）。已分配资源资源最大需求进程R1R2R3R1R2R3PO3235510P14O3536P24o :54O11P32O4425P4314424题27表资源分配情况表A. P0,P2,P4,Pl,P3B. Pl ,P0,P3,P4,P2C. P2

30、,Pl,P0,P3,P4D. P3,P4,P2,Pl,P0P028 .若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）。I.若该文件的数据不在内存，则该进程进入睡眠等待状态；葭请求read系统调用会导致CPUA用户态切换到核心态；出.read系统调用的参数应包含文件的名称A.仅I、n29 仅I、mC.仅n、田d.I、nftm29.一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达。它们的计算和I/0操作顺序如下：P1:计算60msI/O80ms,计算20mqP2:计算120msI/O40ms,计算40ms若不考虑调度和切换时间，

31、则完成两个作业需要的时间最少是（）。A. 240msB. 260msC. 340msD. 360ms30 .若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）。A.在进程结束时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统调用完成并返回用户态时能进行处理机调度31 .下列关于进程和线程的叙述中，正确的是（）。A.不管系统是否支持线程，进程都是资源分配的基本单位B.线程是资源分配的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都需要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间32 .

32、下列选项中，不能改善磁盘设备I/O性能的是（）。A.重排I/0请求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理块的分布33 .在TCP/IP体系结构中，直接为ICMP提供服务的协议是（）。A. PPPB. IPC. UDPD. TCP34 .在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（）。A.机械特性B.功能特性C.过程特性D.电气特性35 .以太网的MAO议提供的是（）。A.无连接不可靠服务B.无连接可靠服务C.有连接不可靠服务D.有连接可靠服务36.两台主机之间的数据链路层采用后退N帧协议（GBN传输数据，数据传输速率为16kbps,单向传播时延为270

33、ms数据帧长度范围是128512字节,接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（）。A. 5B. 4C. 3D. 23737.下列关于IP路由器功能的描述中，正确的是（）。I.运行路由协议，设置路由表；葭监测到拥塞时，合理丢弃IP分组;田.对收到的IP分组头进行差错校验，确保传输的IP分组不丢失；IV.根据收到的IP分组的目的IP地址，将其转发到合适的输出线路上。A.仅田、IVB.仅I、n、mC.仅I、n、IVD.I、H、m、IV38.ARPft、议的功能是（）。A.根据IP地址查询MAO址B.根据MAO址查询IP地址C.根据域名查询IP地址D.根据I

34、P地址查询域名39.某主机的IP地址为5,子网掩码为。若该主机向其所在子网发送广播分组，则目的地址可以是()。A. B. 55C. 55D. 5540. 若用户l与用户2之间发送和接收电子邮件的过程如题40图所示，则图中、阶段分别使用的应用层协议可以是()。题40图电子邮件发送接收示意图A. SMTPSMTPSMTPB. POP3SMTPPOP3C. POP3SMTPSMTPD. SMTPSMTPPOP3二、综合应用题：41-47小题。共70分。41. (10

35、分)设有6个有序表A、B、GDE、F,分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。(1)给出完整的合并过程，并求出最坏情况下比较的总次数。(2)根据你的合并过程，描述n(n2)个不等长升序表的合并策略，并说明理由。42. (13分)假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，loading”和“being”的存储映像如题42图所示。题42图存储映像示意图设strl和str2分别指向两个单词所在单链表的头结点，

36、链表结点结构为data,next,请设计一个时间上尽可能高效的算法，找出由strl和str2所指的两个链表共同后缀的起始位置(如图中字符i所在结点的位置p)o要求:(1)给出算法的基本设计思想。(2)根据设计思想，采用C或C+域JAVA语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度。43. (11分)假定某计算机的CPUfc频为80MHzCPI为4,并且平均每条指令访存1.5次，主存与Cache之间交换的块大小为168,Cache的命中率为99%,存储器总线宽度为32位。请回答下列问题。(1)该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA专送

37、的情况下，主存带宽至少达到多少才能满足CPU勺访存要求？(2)假定在Cache缺失的情况下访问主存时，存在0.0005%的缺页率，则CPU均每秒产生多少次缺页异常？若页面大小为4KB,每次缺页都需要访问磁盘，访问磁盘时DMA专送采用周期挪用方式，磁盘I/O接口的数据缓冲寄存器为32位，则磁盘I/O接口平均每秒发出的DMA青求次数至少是多少？(3) CP丽DM馈制器同时要求使用存储器总线时，哪个优先级更高？为什么？(4)为了提高性能，主存采用4体交叉存储模式，工作时每1/4个存储周期启动一个体。若每个体的存储周期为50ns,则该主存能提供的最大带宽是多少？44. (12分)某16位计算机中，带符

38、号整数用补码表示，数据Cache和指令Cache分离。题44表给出了指令系统中部分指令格式，其中Rs和Rd表示寄存器，me该示存储单元地址，(X)表示寄存器X或存储单元X的内容。表指令系统中部分指令格式名称指令的汇编格式指令功能加法指令PADDRsRdP(Rs)+(Rd)一Rd算术/逻辑左移SHLRd2*(Rd)一Rd算术右移SHRRd(Rd)/2一Rd取数指令PLOADRDmem(mermfRd存数指令STORERsmem(Rs)一mem该计算机采用5段流水方式执行指令，各流水段分别是取指(IF)、译码/读寄存器(ID)、执行/计算有效地址(EX)、访问存储器(M和结果写回寄存器(WB,流水

39、线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。(1)若int型变量x的值为-513,存放在寄存器Rl中，则执行指令“SHRRl”后，Rl的内容是多少？(用十六进制表示)(2)若某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少？(3)若高级语言程序中某赋值语句为x=a+b,x、a和b均为int型变量，它们的存储单元地址分别表示为冈、a和b。该语句对应的指令序列及其在指令流水线中的执行过程如题44图所示。1则这4条指令执行过程中，13的ID段和1

40、4的IF段被阻塞的原因各是什么？(4)若高级语言程序中某赋值语句为x=2*x+a,x和a均为unsignedint类型变量，它们的存储单元地址分别表示为x、司，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。45. (7分)某请求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计)，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取

41、出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的虚拟页号，访问时亥|J是：1,1、3,2、0,4、0,6、1,11、0,13、2,14。请回答下列问题。(1)访问0,4时，对应的页框号是什么？(2)访问1,11时，对应的页框号是什么？说明理由。(3)访问2,14时，对应的页框号是什么？说明理由。(4)该策略是否适合于时间局部性好的程序？说明理由。46. (8分)某文件系统空间的最大容量为4TB(1T=240),以磁盘块为基本分配单位，磁盘块大小为lKB0文件控制块(FCB包含一个512B的索引表区。

42、请回答下列问题。(1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？(2)假设索引表区采用如下结构：第07字节采用起始块号，块数格式表示文件创建时预分配的连续存储空间，其中起始块号占6B,块数占2B;剩余504字节采用直接索引结构，一个索引项占6B,则可支持的单个文件最大长度是多少字节？为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。47. (9分)主机H通过快速以太网连接Internet,IP地址为,服务器S的IP地址为0。H与S

43、使用TCP!信时，在H上捕获的其中5个IP分组如题47-a表所示。题47-a表编号IP分组的前40字节内容(十六进制)1019b40008006lde8coa80008d34447500bd91388846b41c5000000005db0000020000400031066e833d3444750cOa8000813880bd9e0599fef846b41c66701216d037e100003019c40008006ldefcOa80008d3444750bd91388846b41c6e0599ff0501043802b3200004019d400080061ddecOa80008d344

44、47500bd91388846b4lc6e0599ff0c655000053106067ad3444750cOa8000813880bd9e0599ff0846b41d6501016d057d20000请回答下列问题。(1)题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？(2)根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是多少？(3)若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所列，则该IP分组到达H时经过了多少个路由器？题47-b表或1白Q妗中的公4006eCadd3444750c

45、a760106木日S女巾口3刀组1388a108e0599ff0846b41d6501016dOb7d60000注：IP分组头和TCP段头结构分别如题47-a图、题47-b图所示:版本头部长度服务类型(8-15)总长度(16-31)标识标志片偏移生存时(TTL)协议头部校验和源IP地址目的IP地址题47-a图IP分组头结构源端口(0-15)目的端口（16-31）序号（seq）确认号（ack）数据偏移保留URGACKPSHRSTSYNFIN窗口校验和紧急的选项（长度可变）填充题47-b图TCP段头结构2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解一、单项选择题：l40

46、小题。每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 .求整数n(n0)阶乘的算法如下，其时间复杂度是()。A. O(log2n)B. 0(n)C. O(nlog2n)D. O(n2)【答案】Bo【解析】设fact(n)的运行时间函数是T(n)。该函数中语句的运行时间是0(1),语句的运行时间是T(n-1)+O(1),其中O(1)为乘法运算的时间。因此，当n&l时，T(n)-0(1);当n1时，T(n)=T(n-1)+0(1)则，T(n)=O(1)+T(n-1)=2XO(1)+T(n-2)=(n-1)xO(1)+T(1)=nXO(1)=0(n)即fact(n

47、)的时间复杂度为O(n)。2,已知操作符包括+、-、*、/、(和。将中缀表达式a+b-a*(c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是()。A. 5B. 7C. 8D. 11【答案】Ao【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符(先出栈的运算符先计算，同优先级的运算符在栈中的先计算)。表达式a+b-a*(c+d)/e-f)+g产生后缀表达式的过程如下表所列:当

48、前字符运算符栈内容后缀表式说明a+“+”进栈b+ab-ab+“-”与栈顶元素“+”的优先级相同，则“+”出栈，“-”进栈a-ab+a*-*ab+a”的优先级大于栈顶元素“-”，则“*”进栈(-*(ab+a“(”对它之前后的运算符起隔离作用(-*(ab+a“(”对它之前后的运算符起隔离作用-*(ab+ac+-*(+ab+ac“+”进栈d-*(+ab+acd)-*(ab+acd+与其配对的左括号及其前所有运算符出栈/-*(/ab+acd+进栈e-*(/ab+acd+e-*(-ab+acd+e/“-”的优先级小于栈顶元素“/”，则出栈，“-”进栈f-*(-ab+acd+e/f)-*ab+acd+e/f-与其配对的左括号及其前所有运算符出栈+-ab+acd+e/f-*