沈阳农业大学信息与电气工程学院计算机专业基础历考研真题汇编附答案

1、沈阳师范大学教育技术学院862计算机学科专业基 础综合（数据结构、操作系统）历年考研真题汇编附答案最新资料，WORD式，可编辑修改！目录第一部分沈阳师范大学教育技术学院 862计算机学科专业基础综合（数据结构、操作 系统）历年考研真题汇编 2014年沈阳师范大学教育技术学院 867计算机学科专业基础综合 （数据结构、操作系统）考研真题2013年沈阳师范大学教育技术学院 867计算机学科专业基础综合 （数据结构、操作 系统）考研真题第二部分全国硕士研究生入学统一考试 408计算机学科专业基础综合历年真题及详解2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题 2012年全国硕士

2、研究生入学统一考试408计算机学科专业基础综合真题及详解2011年全国攸士研究生入学统受试408计算机学科专业基础综合真题 2011年全国攸士研究生入学统受试408计算机学科专业基础综合真题及详解2010年全国秋十研究生入学统支试408计算机学科专业基础综合真题 2010年全国攸士研究生入学统受试408计算机学科专业基础综合真题及详解2009年全国攸士研究生入学统受试408计算机学科专业基础综合真题 2009年全国攸士研究生入学统受试408计算机学科专业基础综合真题及详解说明：沈阳师范大学2012年之前参加全国统考 408计算机学科专业基础综合，2013 年开始自主命题，科目改为867计算机学

3、科专业基础综合（数据结构、操作系统），2015 年科目代码改为862。为帮助考生全面复习， 特提供20092012年408计算机学科专业 基础综合真题及详解。第一部分沈阳师范大学教育技术学院 862计算机学科专业基础综合（数据结构、 操作系统）历年考研真题汇编2014年沈阳师范大学教育技术学院867计算机学科专业基础综合（数据结构、操作系统）考研真题科目代码：867科目名称：计算机学科专业基础综合（数据结构、操作系统）适用专业名称：计算机应用技术考生注意：请将答案写在答题纸上，写在本题签及草纸上无效。考试后本题签同答题纸一并交回。一、单项选择题（共10题，每题2分，合计20分）1.某算法的时间

4、复杂度为 O（n2）,表明该算法（）oA问题规模是n2B.执行时间等于n2C.执行时间与n2成正比D.问题规模与n2成正比2设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更 局。A输出第i （1i next= p-next ； p-next=s;t=p-data; p-data= s-data;s-data= t;B. p-next=s ; s-next= p-next；t=p-data； p-data= s-data;s-data= t;C. s-next= p-next ； p-next=s;p-data= s-data ; t=p-data;s-data= t;D.

5、 p-next=s ; s-next= p-next；t= s-data; s-data p-data;p-data= t;4 .已知一个栈的进栈序列是1, 2, 3, ,n,其输出序列是p1,p2,，p%若p1=n,则pi的值（）。A iB. n-iC. n-i+1D.不确定5.对稀疏矩阵进行压缩存储，常用的两种方法是（）。A二元组和散列表B.三元组和十字链表C.三角矩阵和对角矩阵D.对角矩阵和十字链表6 .广义表（a） , a）的表头和表尾分别是（）。A. （ a）和（a）B. a和（a）C. （a）和 aD. （ （ a）和（a）7 .已知二叉树的先序序列为 ABDEGCF中序序列为DB

6、GEACF则后序序列为（）,A. GEDBFCAB. DGEBFCAC. DGEBAFCD. EBFDGCA8 . 一棵完全二叉树上有1000个结点，其中叶子结点的个数是（）。A 250B. 500C. 505D. 5019 .线索二叉树是一种（）结构。A.逻辑10 逻辑和存储C.物理D.线性11 .以数据集2 , 5, 7, 9, 13为权值构造一棵哈夫曼树，则其带权路径长为（）A 78B. 80C. 81D. 7911.一个有向图的邻接表存储如图1所示，现按深度优先搜索遍历，从顶点 必出发,所得到的顶点序列是（）。可能不存在D.13 .若一个有向图中的顶点不能排成一个拓扑序列，则可断定该有

7、向图（）。A是个有根有向图B.是个强连通图C.含有多个入度为0的顶点D.含有顶点数目大于1的强连通分量14 .顺序查找法适合于存储结构为（）的线性表。A哈希存储B.索引存储C.压缩存储D.顺序存储或链式存储15.在含有27个结点的二叉树排序树上，查找关键字为35的结点，则依次比较的关键字有可能是（）A. 28, 36, 18, 46, 35B. 18, 36, 28, 46, 35C. 46, 28, 18, 36, 35D. 46, 36, 18, 28, 3516.在有序表a 1.20中，采用二分查找算法查找元素值等于 a12的元素，所 比较过元素的次数为（）。A. 4B. 5C. 3D.

8、 617.数据序列 8, 9, 10, 4, 5, 6, 20, 1, 2 只能是下列排序算法中的（）的两趟排序后的结果。A选择排序B.冒泡排序C.插入排序D.堆排序18.就平均性能而言，目前最好的内部排序方法是（）排序法。A.冒泡排序B.希尔排序C.插入排序D.快速排序19.有一组数据 15, 9, 7, 8, 20,-1 , 7, 4,用堆排序的筛选方法建立的初 始堆为（）。A. -1,4,5, 9, 20,7, 15,7B. -1,7,15, 7, 4,8, 20,9C. -1,4,7, 8, 20,15, 7,9D. A, B, C都不对20 .下面说法不正确的是（）。A.关键活动不按

9、期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，将使整个工程提前完成C.所有关键活动都提前完成，则整个工程提前完成D.某些关键活动若提前完成，将使整个工程提前完成21 .下列选项中，（）不是操作系统关心的主要问题。A.管理计算机裸机B.设计、提供用户程序与计算机硬件系统的界面C.管理计算机系统资源D.高级程序设计语言的编译器22 .系统功能调用是（）。A.用户编写的一个子程序B.高级语言中的库程序C.操作系统中的一条命令D.操作系统向用户程序提供的接口23 .在处理机管理中，当（）时，进程从阻塞状态变为就绪状态。A.进程被调度程序选中B.等待某一事件发生C.等待的事件发生D.时间

10、片用完24 .高级调度是（）。A进程调度B.作业调度C.程序调度D.设备调度25 .临界区是（）。A 一个缓冲区B. 一段共享数据区C. 一段程序D. 一个互斥资源26 .产生死锁的根本原因是（）。A资源共享B.并发执行的进程太多C.进程推进顺序非法D.以上3个因素全是27 .在下述存储管理方案中，（）管理方式要求作业占用连续的存储空间。A分区B.分页C.分段D.段页式28 .操作系统中对数据进行管理的部分叫做（）。A数据库系统B.文件系统C.检索系统D.数据存储系统29 .下列文件中属于逻辑结构的文件是（）。A连续文件B.系统文件C.散列文件D.流式文件30 .在磁盘文件系统中，对于下列文件

11、物理结构，（）不具有直接读写文件任意一个记录的能力。A.顺序结构B.链接结构C.索引结构D.散列结构二、算法设计题（共2题，每题10分，合计20分）31 .设C=a1,b1,a2,b2,an, bn 为一线性表，采用带头结点的 hc单链表存放， 设计一个就地算法，将其拆分为两个线性表，使得： A= a1,a2,，an,B= b1, b2, bn32 .冒泡排序的算法是把大的元素向上移动（气泡的上升）也可以把最小的元素向 下移动（气泡的下沉）。请给出上浮和下沉过程交替的冒泡排序算法。三、综合应用题（共6题，合计70分）33 .写出用Prim算法构造图2最小生成树的过程。（10分） 图2无向网34

12、 .关键字序列 A=（36,27,68,33,97,40,81,24,23,90,32,14） 共 12 个数据，哈希表 长为13,采用的哈希函数为：h（key尸key %13如果采用开放定址的线性探测再散列方 法解决冲突，请构造哈希表并求其查找成功时的平均查找长度。（10分）35 .在如图3所示的AOEW,求：（10分）（1）完成此工程最少需要的多少天（设边上权值为天数）。（2）是否存在某项活动，当其提高速度后能使整个工程缩短工期。a12=4a1=a8=1图3 AOE网79需9=4 SJ584136.若有以下四个作业同2寸到达铀并怔作业名作业作业作业作业1234cpuH间（分钟）a6=312

13、=683_假设系统中没有其他作业，现a宛fl(15给出作业调度顺序并求出平均作业周转时间T,平均带权作业周转时间W分）37 .在一个请求式页式管理系统中，某程序在内存中分配三个页面，初始为空 .页 面走向为：4 ,3,2, 1,4,3,5,4,3,2,1,5。用学过的页面值换算法FIFO算出缺页次数。给出执行过程中内存页面的变化情况。（15分）38 .在4*100m接力赛中，4个运动员之间存在如下关系图 4,运动员1跑到终点把 接力棒交给运动员2,，运动员4接到棒后跑完全程。试用信号量机制进行描述。 试写出这四个并发进程能正确执行的程序。（10分）关系图第二部分全国硕士研究生入学统一考试408

14、计算机学科专业基础综合历年真题及详解2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题一、单项选择题：l40小题。每小题2分，共80分。下列每题给出的四个选项中， 只有一个选项是最符合题目要求的。1 .求整数n (n0)阶乘的算法如下，其时间复杂度是()。A. O (log2n)B. 0 (n)C. O (nlog2n) 一， 2、D. O ( n )2 .已知操作符包括+、 -、 *、 /、(和)。将中缀表达 式a+b-a* ( (c+d) /e-f ) +g转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来 存放暂时还不能确定运算次序的操作符。若栈初始时为空

15、，则转换过程中同时保存在栈 中的操作符的最大个数是()。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. 335 .对有2个顶点e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时 间复杂度是()。A. 0 (n)B. 0 (e)C. O (n+e)D. O (nXe)6 .若用邻接矩阵存储有向图，矩阵中主

16、对角线以下的元素均为零，则关于该图拓 扑序列的结论是()。A.存在，且唯一8 .存在，且不唯一不唯一C.存在，可能不唯一D.无法确定是否存在7 .有向带权图如题7图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a到 其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b,第二条最短路径的目标顶点是c,后续得到的其余各最短路径的目标顶点依次是（）。题7图有向带权图A. d, e, fB. e, d, fC. f, d, eD. f, e, d8 .下列关于最小生成树的叙述中，正确的是（）。I.最小生成树的代价唯一n.所有权值最小的边一定会出现在所有的最小生成树中 m.使用普里姆（P

17、rim）算法从不同顶点开始得到的最小生成树一定相同IV.使用普里姆算法和克鲁斯卡尔（Kruskal ）算法得到的最小生成树总不相同A仅IB.仅nC.仅 I、mD.仅 n、iv9 .设有一棵3阶B树，如题9图所示。删除关键字78得到一棵新B树，其最右叶 结点所含的关键字是（）。题9图3二叉树图A. 60B. 60, 62C. 62, 65D. 6510 .排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下 列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。I.简单选择排序 n .希尔排序田.快速排序iv.堆排V.二路归并排序A.仅 I、m、IVB.仅 I

18、、n、mC.仅n、m、ivD.仅田、IV、V11 .对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同 之处是（）。A.排序的总趟数B.元素的移动次数C.使用辅助空间的数量D.元素之间的比较次数12 .假定基准程序A在某计算机上的运行时间为l00秒，其中90秒为CPU时间， 其余为I/O时间。若CPU1度提高50%, I/O速度不变，则运行基准程序 A所耗费的时 同是（）。A. 55 秒B. 60 秒C. 65 秒D. 70 秒13.假定编译器规定语句：unsigned short XC语百）。A.B.C.D.00007FFAH 0000FFFAH FFFF7FFAH FFF

19、FFFFAH14. float类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（A.B.C.D.2126-22127-22127-22128-2103104103104int和short类型长度分别为32位和16位，执行下列= 65530; unsigned int y=X：得到 y 的机器数为（15 .某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：若record变量的首地址为 0xC008,则地址0xC008中内容及record.c 的地址分别 为（）。A. 0x00、0xC

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

21、（）。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. 50nsD. 80ns20 .下列关于USB总线特性的描述中，错误的是（

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

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

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

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

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

27、要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间32 .下列选项中，不能改善磁盘设备I/O性能的是（）。A.重排I/0请求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理块的分布33 .在TC% IP体系结构中，直接为ICMP提供服务的协议是（）。A. PPP B. IP C. UDP D. TCP34 .在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（）。A.机械特性 B.功能特性 C.过程特性 D.电气特性 35.以太网的MAO议提供的是（）。A无连接不可靠服务B.无连接可靠服务C.有连接不可靠服务D.有连接可靠服务36.两台主机之间的数据链路层采用后

28、退N帧协议（GBN传输数据，数据传输速率为16kbps ,单向传播时延为270ms数据帧长度范围是128512字节，接收方总是 以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为 （ ）。A. 5B. 4C. 3 D. 237 37.下列关于IP路由器功能的描述中，正确的是（）。I.运行路由协议，设置路由表；n.监测到拥塞时，合理丢弃IP分组；田.对收到的IP分组头进行差错校验，确保传输的 IP分组不丢失；IV.根据收到的IP分组 的目的IP地址，将其转发到合适的输出线路上。A.仅田、IVB.仅 I、n、mC.仅 i、n、iv d. i、n、m、iv 38. ARP协议的

29、功能是（）。A.根据IP地址查询MAC4址B.根据MAO址查询IP地址C.根据域名查询IP地址D.根据IP地址查询域名39 .某主机的IP地址为180.80.77.55 ,子网掩码为 255.255.252.0。若该主机向 其所在子网发送广播分组，则目的地址可以是（）。A. 180.80.76.0B. 180.80.76.255C. 180.80.77.255D. 180.80.79.25540 .若用户l与用户2之间发送和接收电子邮件的过程如题40图所示，则图中、阶段分别使用的应用层协议可以是()。题40图电子邮件发送接收示意图A. SMTP SMTP SMTPB. POP3 SMTP PO

30、P3C. POP3 SMTP SMTPD. SMTP SMTP POP3二、综合应用题：41-47 小题。共70分。41 . (10分)设有6个有序表 A B、C、R E、F,分别含有10、35、40、50、60 和200个数据元素，各表中元素按升序排列。要求通过 5次两两合并，将6个表最终合 并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。(1)给出完整的合并过程，并求出最坏情况下比较的总次数。(2)根据你的合并过程，描述n (n2)个不等长升序表的合并策略，并说明理由。42 . (13分)假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时， 则可共享相同的后缀存

31、储空间。例如，“ loading ”和“ being ”的存储映像如题42图所示。题42图存储映像示意图设strl和str2分别指向两个单词所在单链表的头结点，链表结点结构为data ,next,请设计一个时间上尽可能高效的算法，找出由 strl和str2所指的两个链表共 同后缀的起始位置(如图中字符 i所在结点的位置p)。要求：(1)给出算法的基本设计思想。(2)根据设计思想，采用 C或C+碱JAVA语言描述算法，关键之处给出注释。(3)说明你所设计算法的时间复杂度。43. (11分)假定某计算机的 CPUfe频为80MHz CPI为4,并且平均每条指令访 存1.5次，主存与Cache之间交

32、换的块大小为 168, Cache的命中率为99%,存储器总 线宽度为32位。请回答下列问题。(1)该计算机的 MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA 传送的情况下，主存带宽至少达到多少才能满足CPU勺访存要求？(2)假定在Cache缺失的情况下访问主存时，存在 0.0005 %的缺页率，则CPUff 均每秒产生多少次缺页异常？若页面大小为4KB,每次缺页都需要访问磁盘，访问磁盘时 DMA专送采用周期挪用方式， 磁盘I/O接口的数据缓冲寄存器为 32位，则磁盘I/O接 口平均每秒发出的DMA 青求次数至少是多少？(3) CPUffl DMA空制器同时要求使用存储器

33、总线时，哪个优先级更高？为什么？(4)为了提高性能，主存采用 4体交叉存储模式，工作时每l/4个存储周期启动 一个体。若每个体的存储周期为50ns,则该主存能提供的最大带宽是多少 ？44. (12分)某16位计算机中，带符号整数用补码表示， 数据Cache和指令Cache 分离。题44表给出了指令系统中部分指令格式，其中 Rs和Rd表示寄存器，memi示存 储单元地址，(X)表示寄存器X或存储单元X的内容。表指令系统中部分指令格式名称指令的汇编格式指令功能 1加法指令ADD R Rd(Rs) + (Rd) f Rd算术/逻辑左移SHLR d2* (Rd) f Rd 算术右移SHRR d(Rd)

34、 /2f Rd取数指令LOAD RD mem(merm f Rd存数指令STORE Rs mem(Rs) f mem该计算机采用5段流水方式执行指令，各流水段分别是取指(IF)、译码/读寄存 器(ID)、执行/计算有效地址(EX)、访问存储器(M)和结果写回寄存器(WB , 流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一 个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。(1)若int型变量x的值为-513,存放在寄存器Rl中，则执行指令 SHRRl”后, Rl的内容是多少？(用十六进制表示)(2)若某个时间段中，有连续的 4条指令进入流水线，在其执

35、行过程中没有发生任何阻塞，则执行这4条指令所需的时钟周期数为多少 ？(3)若高级语言程序中某赋值语句为x = a+b, x、a和b均为int型变量，它们的存储单元地址分别表示为x、闻和回。该语句对应的指令序列及其在指令流水线中 的执行过程如题44图所示。则这4条指令执行过程中，I 3的ID段和14的IF段被阻塞 的原因各是什么？(4)若高级语言程序中某赋值语句为x = 2*x+a, x和a均为unsigned int 类型变量，它们的存储单元地址分别表示为x、闻，则执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。45. (7分)某请

36、求分页系统的局部页面置换策略如下：系统从0时刻开始扫描，每隔5个时间单位扫描一轮驻留集(扫描时间忽略不计)，本轮没有被访问过的页框将 被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生 缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否 则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始 时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的 虚拟页号，访问时刻 是：1, 1、3, 2、0, 4、0, 6、1, 11、0, 13、2, 14。请回答下列问题。(1)访问0, 4时，

37、对应的页框号是什么？(2)访问1, 11时，对应的页框号是什么？说明理由。(3)访问2, 14时，对应的页框号是什么？说明理由。(4)该策略是否适合于时间局部性好的程序 ？说明理由。46. (8分)某文件系统空间的最大容量为 4TB (1T= 24),以磁盘块为基本分配单位，磁盘块大小为lKBo文件控制块(FCB包含一个512B的索引表区。请回答下列 问题。(1)假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节 ？可支持的单个文件最大长度是多少字节 ？(2)假设索引表区采用如下结构：第 07字节采用 起始块号，块数 格式表示文 件创建时预分配的连续存

38、储空间，其中起始块号占 6B,块数占2B;剩余504字节采用 直接索引结构，一个索引项占 6B,则可支持的单个文件最大长度是多少字节 ？为了使单 个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。47. （9分）主机H通过快速以太网连接Internet , IP地址为192.168.0.8 ,服务 器S的IP地址为211.68.71.80 。H与S使用TCP信时，在 H上捕获的其中5个IP分 组如题47-a表所示。题47-a表Sfflj七IP分组的前40字节内容（十六进制）1019b4000 8006lde8 coa80008 d3444750 0bd91388 84

39、6b41c5 000000005db00000200004000 31066e83 3d3444750 cOa8000813880bd9 e0599fef 846b41c6 6701216d037e100003019c4000 8006ldef cOa80008 d3444750 bd913888 46b41c6e 0599ff05 01043802 b3200004019d4000 80061dde cOa80008 d34447500bd91388 846b4lc6 e0599ff0c655000053106067a d3444750 cOa8000813880bd9 e0599ff0 8

40、46b41d6 501016d057d20000请回答下列问题。（1）题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了 TCP连接建立 过程？哪几个在通过快速以太网传输时进行了填充？（2）根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是多少？（3）若题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所列，则 该IP分组到达H时经过了多少个路由器？题47-b表来自S发出的上组4006eCad d3444750 ca760106 1388a108 e0599ff0 846b41d6 501016dO b7d60000注：IP分组头和TCP段头结构分别如题4

41、7-a图、题47-b图所示:版本头部长 度服务类型 （8-15）总长度(16-31 )标识标志片偏移生存时（TTL）协议头部校验和源IP地址目的IP地址题47-a图IP分组头结构源端口（ 0-15）目的端口 （ 16-31 ）序号（seq)确认号（ack）UAPRSF数据偏移保留RCSSYI窗口GKHTNN校验和1紧急指针选项（长度可艾）填充题47-b图TCP段头结构2012年全国硕士研究生入学统一考试408计算机学科专业基础综合真题及详解一、单项选择题：l40小题。每小题2分，共80分。下列每题给出的四个选项中， 只有一个选项是最符合题目要求的。1 .求整数n (n0)阶乘的算法如下，其时间

42、复杂度是()。A. O (log2n)B. 0 (n)C. O (nlog2n)一， 2、D. O ( n )【答案】Bo【解析】设fact (n)的运行时间函数是 T (n)。该函数中语句的运行时间是 0 (1),语句的运行时间是 T (n-1) +O (1),其 中O (1)为乘法运算的时间。因此，当 n1 时，T (n) =T (n-1 ) +O (1)。则，T (n) = O (1) +T (n-1 )= 2XO (1) +T (n-2) = (n-1) x O (1) +T (1) =nx O (1)=O (n)即fact (n)的时间复杂度为 O (n)。2 .已知操作符包括+、

43、-、 *、 /、(和)。将中缀表达 式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产生后缀表达式的过程如下表所列：当前字符运

44、算符栈内 容后缀表达式说明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-* (

45、-ab+acd+e/f)-*ab+acd+e/f-与其配对的左括号及其前所有运 算符出栈+-ab+acd+e/ f-*“+”的优先级小于栈顶兀素“*”， 则“出栈+ab+acd+e/ f-*-“ +”与栈顶兀素“-”的优先级 相同，则“-”出栈，“ +”进栈g+ab+acd+e/ f-*-gab+acd+e/ f-*-g+全部出栈通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。3 .若一棵二叉树的前序遍历序列为 a, e, b, d, c,后序遍历序列为b, c, d, e, a,则根结点的孩子结点（）。A.只有e8 .有 e、bC.有 e、cD.无法确定【答案】Ao【解析】由题目可知，若一棵二叉树的前序遍历序列为a, e, b, d, c,后序遍历序列为b, c, d, e, a,其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个 结点为e,而后序遍历的倒数第二个结点为 e,说明a的孩子结点只有e。4 .若平衡二叉树的高度为 6,且所有非叶结点的平衡因子均为 1,则该平衡二叉树 的结点总数为（）。A. 12B. 20C. 32D. 33【答案】Bo【解析】本题题目的实际问题是，具有 6层结点的平衡二叉树含有最少的结点数是 多少。Nh表示深度为h的平衡二叉树中含有的最少结点数，有 N=0, N = 1, Nb = 2 N=N-i+N-2+1由此可