考研计算机专业基础综合(综合应用题)模拟试卷13(题后含答案及解析)

考研计算机专业基础综合（综合应用题）模拟试卷13 (题后含答案及

解析)

题型有：1.

1． 操作系统有哪两种服务方式?它们是如何实现服务的?

正确答案：(1)系统调用：系统调用本身是一个由若干条指令构成的过程。 (2)系统程序：现代计算机系统往往都有一个系统程序包，它包含了系统提供的大量程序，用于解决带有共性的问题，并为程序的开发和执行提供了一个方便的环境。 涉及知识点：操作系统

2． 如果以单链表表示集合，设集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A一B。

正确答案：由集合运算的规则知，集合的差A-B为包含所有属于A而不属于B的元素，因此，算法的思路在于对于所有属于集合A中的元素e，在集合B中进行查找，若能找到，则说明它不属于A—B，应从LA中删除。若LA的长度为O(n)，LB的长度为O(m)，则该算法的时间复杂度为O(mXn)。 算法参考伪代码如下： void Difference(LinkList*LA，LinkList * LB) ／／设LA，LB均具有头结点 { Node*pre，*pre *p*r： pre=LA； p=LA一＞next： ／／p指向LA表中的某一结点，而pre指向P的前面一个结点 while(P!=NULL) { q=LB一＞next； ／／遍历LB表，判断LA中元素是否在LB中 Node *while (q|=NULL&&q一＞data!=一＞data) q=q一＞next if(q!=NULL){ ／／在LB中找到相同结点元素，则应在LA中删除该结点 r=P： pre一＞next=r一＞next： p=p一＞next： free(r)； }else {／／未能找到，说明该结点属于A-B继续在LA中对下一个元素进行判断 pre=P： p=p一＞next； } } } 涉及知识点：数据结构

3． 已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1．2k一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。

正确答案：二叉树采用顺序存储结构(一维数组)是按完全二叉树的形状存储的，不是完全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采用队列结构。 typedef struct{ BiTree bt； ／／二叉树结点指针 int num； }tnode； ／／num是结点在一维数组中的编号 tnode Q[maxsize]； ／／循环队列，容量足够大 void creat(BiTree T，ElemType BT[]){ ／／深度h的二叉树存于一维数组BT[1．,2h一1]中 ／／本算法生成该二叉树的二叉链表存储结构 tnode tq； ／／tq是队列

元素int len，i； ／／数组长度 len=strlen(BT)： T=(BiTree)malloc(sizeof(BiNode))； ／／申请结点 T一＞data=BT[1]； ／／根结点数据 tq．bt=T；tq．nun=l； Q[1]=tq； ／／根入队列 front=0；rear=1： ／／循环队列头、尾指针 while(front!=rear){ ／／当队列不空时循环 front=(front+1)％maxsize； tq=Q[front]；p=tq．bt；i=tq．num； ／／出队，取出结点及编号 if(BT[2*i]==‘#’ ||2*i＞len)p-＞lchild=null； ／／左子树为空，’#’表示虚结点 else{ ／／建立左子女结点并入队列 p-＞lchild=(BiTree)malloc(sizeof(BiNode))； ／／申请结点空间 P-＞lchild-＞data=BT[2*i]： ／／左子女数据 tq.bt=p-＞lehild；tq．num=2*i；rear=(rear+1)％maxsize； ／／计算队尾位置 Q[rear]=tq； ／／左子女结点及其编号入队 } if(BT[2*i+1]==‘#’||2*i+1＞len)p-＞rchild=null； ／／右子树为空 else{／／建立右子女结点并入队列 P一＞rchild=(BiTree)malloc(sizeof(BiNode)； ／／申请结点空间 P一＞rchild-＞data=BT[2*i+1]；tq．bt=p一＞rchild；tq．num=2*i+1； rear=(rear+1)％maxsize；Q[rear]=tq； ／／计算队尾位置，右子女及其编号入队 } }／／while} 涉及知识点：数据结构

4． “破圈法”是“任取一圈，去掉圈上权最大的边”，反复执行这一步骤，直到没有圈为止。请给出用“破圈法”求解给定的带权连通无向图的一棵最小代价生成树的详细算法，并用程序实现你所给出的算法。(注意：圈就是回路)

正确答案：void SpnTree(AdjList g){ ／／用“破圈法”求解带权连通无向图的一棵最小代价生成树 typedef struct{int i，j，w：}node； ／／设顶点信息就是顶点编号，权是整数 node edge[]； scanf(”％d％d”，&e，&n)； ／／输入边数和项点数 for(i=1；i<=e；i++) ／／输入e条边：顶点，权值 seanf(”％d％d％d”，&edge[i]．i，&edge[i]．j，&edge[i]．W)； for(i=2；

i<=e ； i++){ ／／按边上的权值大小，对边进行逆序排序 edge[0]=edge[i]；j=i一1； while(edge[j]．W<edge[0]．W)edge[j+1]=edge[j一一]； edge[j+1]=edge[0]; }／／for k=1；eg=e； while(eg>=n){ ／／破圈，直到边数e=n一1 if(connect(k)) ／／删除第k条边若仍连通 f edge[k]．W=0；eg--；} ／／测试下一条边edge[k]，权值置0表示该边被删除 k++； ／／下条边 }／／while } connect( )是测试图是否连通的函数，可用DFS函数或BFS函数实现，若是连通图，一次进入DFS函数或BFS函数就可遍历完全部顶点，否则，因为删除该边而使原连通图成为两个连通分量时，该边不应删除。“破圈”结束后，可输出edge中W不为0的n一1条边。 涉及知识点：数据结构

5． 假定X=0．0110011×211，Y=0．1101101×2-10(此处的数均为二进制)，计算X×Y。

正确答案：(1)阶码相加：[X+Y]移=[X]移+[Y]补=01 011+11110=01 001。 (符号位10第1位为0，不溢出；00时上溢，01时下溢。) (2)尾数相乘结果：0 1010110 110111。 (3)已满足规格化要求，不需左规，尾数不变，阶码仍为001。 (4)舍入处理：按0舍1入规则，尾数之后的6位110111舍去，尾数

+1=01010111。 所以，X×Y最终浮点数格式的结果为：1001 0 1010111即0．1010111×21。 涉及知识点：计算机组成原理

6． 已知32位寄存器中存放的变量x的机器码为C0000004H，请问： (1)当x是无符号整数时，x的真值是多少?x／2的真值是多少?x／2存放在R1中的机器码是什么?2x的真值是多少?2x存放在Rl中的机器码是什么? (2)当x是带符号整数(补码)时，x的真值是多少?x／2的真值是多少?x／2存放在R1中的机器码是什么?2x的真值是多少?2x存放在R1中的机器码是什么?

正确答案：算术移位的对象是带符号数，在移位过程中必须保持操作数的符号不变。当左移1位时，如不产生溢出，则数值乘以2；而右移1位时，如不考虑因移出舍去的末位尾数，则数值除以2。因此，对于无符号整数，所有二进制位均为数值位，而对于带符号数，最高位为符号位。2x即左移1位，x／2即右移1位。 (1)x是无符号整数，C0000004H的真值为231+230+22。 x／2是由x逻辑右移1位得到的，即(231+230+22)÷2，其真值为230+229+2，存放在R1中的机器码是 01 10 0000 0000 0000 0000 0000 0000 0010转换成十六进制为6000 0002H。 2x是由x逻辑左移1位得到 1 1000 0000 0000 0000 0000 0000 0000 1000真值发生溢出，存放在R1中的机器码是1000 0000 0000 0000 0000 0000 0000 1000，转换成十六进制为80000008H。 (2)机器码C0000004H的二进制补码表示为 1，100 0000 0000 0000 0000 0000 0000 0100这是一个负数，得到的二进制真值为 一011 1111 11 11 11111 11111 11 11 111100对应的十进制真值为一(230一22)。 x／2是由x算术右移1位得到的，其真值为一(229一2)，用二进制真值表示为 一110 0000 0000 0000 0000 0000 0000 0010存放在R1中的机器码是 1，110 0000 0000 0000 0000 0000 0000 0100转换成十六进制表示为E0000002H。 涉及知识点：计算机组成原理

7． 如果在一个CPU周期中要产生3个脉冲T1=200 ns，T2=400 ns，T3=200 ns，试画出时序产生器逻辑图。

正确答案：节拍脉冲T1、T2、T3的宽度实际等于时钟脉冲的周期或是它的倍数，此时T1=T2=200 ns，T3=400 ns，所以主脉冲源的频率应为f=1／T1=5 MHz，为了消除节拍脉冲上的毛刺，环型脉冲发生器采用移位寄存器形式。下图画出了题目要求的逻辑电路图和时序信号关系。根据关系，节拍脉冲T1、T2、T3的逻辑表达式如下： T1=C1×C2，T2=C2，T3=C1 涉及知识点：中央处理器

8． 我们为某临界区设置一把锁W，当W=1时表示关锁，W=0时表示锁已打开。试写出开锁原语和关锁原语，并利用它们去实现互斥。

正确答案：(1)开锁原语： unlock(W)： W=0； 关锁原语： lock(W)； if(W==1)do no_op； W=1； (2)利用开关锁原语实现互斥： vat W：semaphore：=0； begin parbegin process： begin repeat lock(W)； critical section unlock(W)： remainder section until false； endparend 涉及知识点：操作系统

9． 有一个程序要把100×100的数组置初值“0”，现假定有两个主存块可用来存放数组中的元素，每个主存块可以存放200个数组元素，数组中的元素按行编址。两个主存块的初始状态都为空，若程序编制如下： (1)Var A：array[1．．100]of array[1．．100]of integer； for j：=1 to 100 do for i：=1 to 100 doA[i，j]：=0 (2)Vat A：array[1．．100]of array[1．．100]of integer； for i：=1 to 100 do for i：=1 to 100 do A[i，j]：=0当采用LRU页面调度算法时，对上述两种程序编制方法各会产生多少次缺页中断?

正确答案：根据题意，主存块的大小为每块可存放200个数组元素，故作业信息也按每页200个元素来划分。现作业信息是由100×100的数组元素组成，因而共被分成50页。由于作业信息是按行编址的，故每顺序的两行元素在同一页面中，可被同时装到一个主存块中。有两个主存块可供该程序使用，因而程序被装入主存时可把开始两页(共四行元素)的信息分别装入两个主存块。那么，程序执行时若按(1)的编制方法，将对每一列中的各元素顺序清零，即对一列中的元素都清零后再对下一列的元素清零。由于开始两页已被装入主存，所以第一列的四个元素将首先被顺序清零。但当要对第一列的第五个元素清零时却发现该元素不在主存中，因而产生一次缺页中断，按LRU调度算法应淘汰最近最少使用的第一页，使腾出的主存空间可用来存放当前需访问的第三页，即装入第五、六两行元素。程序继续执行时每对两个元素初始化后都要产生一次缺页中断，因而对第一列的100个元素初始化会产生(50—2)次缺页中断。对以后的99列来说，为对每一列元素初始化都将产生50次缺页中断，故(1)的编制方法执行程序时总共会产生(50×100—2)次缺页中断。若按(2)的编制方法，将对一行的元素都清零后再对下一行的元素清零。因而，开始的两页(四行元素)信息先被初始化。当要对第五行元素初始化时将产生缺页中断，按LRU调度算法淘汰最近最少用的第一页后可把当前需访问的包含第五、六两行元素的第三页装入主存。程序继续执行时每对两行元素全部初始化后才产生一次缺页中断，因而共会产生50一2次缺页中断。 因此，程序被装入主存时可把开始两页(四行)装入所分到的主存块中。对于(1)所编制的程序执行时将按列对元素初始化，除对第一列的前四个元素初始化时不会产生缺页中断外，以后每对两个元素初始化时都要产生一次缺页中断，故缺页中断次数为50×100—2次。 对于(2)所编制的程序执行时将按行对元素初始化，除对前四行元素初始化时不会产生缺页中断外，以后每对两行元素初始化时都要产生一次缺页中断，故缺页中断次数为50—2次。 涉及知识点：存储管理

10． 什么是存储器的内零头和外零头?它们是怎么造成的?减少它们应采取什么措施?

正确答案：(1)分配给用户而未被利用的部分(各分区中的空闲部分)称为存储器的内零头。造成的原因是分区的大小不是根据每个作业的大小划分的。减少内零头的方法是根据作业的实际需要动态地划分存储空间，即分区的个数和大小都是不固定的。 (2)存在于各分区之间的不能再充分利用的小的空闲区称为外零头。产生外零头的一个主要原因是，分区分配要求作业运行前一次全部装入主存，且必须占用连续的存储空间。 (3)解决办法： ①把程序分成几部分

装入不同的分区(在虚拟存储管理中讨论)。 ②采用“拼接”技术，把零头集中起来形成一个大的空闲区。 涉及知识点：存储管理

11． 一个UNIX／Linux文件，如果一个盘块的大小为1 KB，每个盘块占4 B，那么，若进程欲访问偏移为263 168 B处的数据，需经过几次间接寻址?

正确答案：UNIX／Linux文件系统中，直接寻址为10块，一次间接寻址为256块，二次间接寻址为2562块，三次间接寻址为2563块。 偏移为263 168 B的逻辑块号是263 168÷1 024=257。块内偏移量=263 168—257×1 024=0。由于10

正确答案：从入度为0的顶点开始，当有多个顶点可以输出时，将其按序从上往下排列，这样不会丢掉一种拓扑序列。从顶点1开始的可能的拓扑序列为12345678、12354678、13456278、13546278。 涉及知识点：图

有一台磁盘机，平均寻道时间为30ms，平均旋转等待时间为120ms，数据传输速率为500B／ms，磁盘机上存放着1000件每件3000B的数据。现欲把一件数据取走，更新后再放回原处。假设一次取出或写入所需时间为：平均寻道时间+平均等待时间+数据传送时间。另外，使用CPU更新信息所需时间为4ms，且更新时间同输入／输出操作不相重叠。试问：

16． 更新磁盘上全部数据需要多少时间?

正确答案：磁盘上总数据量为 1000×3000B=3000000B 读出全部数据所需时间为 3000000 B÷500 B／ms=6000ms 重新写入全部数据所需时间为6000 ms。所以，更新磁盘上全部数据所需的时间为2×(平均寻道时间+平均等待时间+数据传送时间)+CPU更新时间=2×(30+120+6 000)ms+4ms=12304ms 涉及知识点：输入/输出系统

17． 若磁盘及旋转速度和数据传输率都提高一倍，更新全部数据需要多少时间?

正确答案：磁盘机旋转速度提高一倍后，平均等待时间为60ms；数据传输率提高一倍后，数据传送时间变为3000000B÷1000B／ms=3000ms更新全部数据所需时间为2×(30+60+3000)ms+4ms=6184ms 涉及知识点：输入/输出系统

18． 有一阅览室，读者进入时必须先在一张登记表上登记，该表为每一座位列出一个表目，包括座号、姓名，读者离开时要注销登记信息；假如阅览室共有100个座位。试分别用信号量和P、V操作以及管程来实现用户进程的同步算法。

正确答案：(1)使用信号量和P、V操作：var A：array[1..100]of Rec；Rec=record

number：integer； name：string；end；i：integer；for i：=1 to 100 do{A[i]．number：=i；A[i]．name：=null；}mutex，seatcount：semaphore； ／／semaphore：信号量mutex：=1：seatcount：=100；cobeginprocess readeri(var readername：string)(i=1，2，…){ P(seatcount)； P(mutex)； for i：=1 to 100 do{i++： if A[i]．name=-null then A[i]．name：=readername； ／／读者登记 } ／*必须采用这种方式，因为该空位是随机产生的。我们无法知道哪个读者何时离开*／ V(mutex) 进入阅览室，座号i，坐下读书： P(mutex)； ／／读书完毕，需要退场 A[i]name：=null； V(mutex)； V(seatcount); 离开阅览室；} coend (2)使用管程操作： TYPE readbook=monitor VAR R：condition； i，seatcount：integer； name：array[1．．100]of string； DEFINE readercome，readerleave； USE check，wait，signal，release； procedure readereome(readername) began check(IM)： if seatcount≥1100 wait(R，IM) seatcount：=seatcount+1： for i=1 to 100 do i++ if name[i]==null then name[i]：=readername： get the seat number=i； release(IM)； end procedure readerleave(readername) begin check(IM)； seatcount--： for i=1 t0 100 do i++ if name[i]==readername then name[i]：=null： release(IM)： end begin seatcount：=100；name：=null： end eobegin process readeri(1=1，2．…) begm readercome(readername)； read the book： readerleave(readername)： leave the readroom； end coend 涉及知识点：进程管理

19． OSPF协议采用什么路由算法?有什么特点?

正确答案：OSPF是一种基于链路状态的路由协议，需要每个路由器向其同一管理域的所有其他路由器发送链路状态广播信息。在OSPF的链路状态广播中包括所有接口信息、所有的量度和其他一些变量。利用OSPF的路由器首先必须收集有关的链路状态信息，并根据一定的算法计算出到每个结点的最短路径。而基于距离一向量的路由协议仅向其邻接路由器发送有关路由更新信息。 与RIP不同，OSPF将一个自治域再划分为区，相应地有两种类型的路由选择方式：当源和目的地在同一区时，采用区内路由选择；当源和目的地在不同区时，则采用区间路由选择。这就大大减少了网络开销，并增加了网络的稳定性。当一个区内的路由器出了故障时并不影响自治域内其他区路由器的正常工作，这也给网络的管理、维护带来方便。 涉及知识点：网络层

20． 简述移动IP的通信过程。

正确答案：移动主机在不同子网间漫游，其数据包的通信过程如下： (1)本地代理和外地代理不停地向网上发送代理广告消息，以声明自己的存在。 (2)移动主机收到这些消息，确定自己是在本地网还是在外地网。 (3)如果移动主机发现自己仍在本地网，即收到的是本地代理发来的消息，则不启动移动功能。如果是从外地网络重新返回的，则向本地代理发出取消注册的消息，声明自己回到了本地网。 (4)当移动主机检测到它移动到外地网时，则获得接管地址(CoA)。 (5)然后移动主机向本地代理登记，表明自己已离开本地网，把所获得的接管地址通知本地代理。 (6)登记完毕后，所有发给移动主机的数据

包被本地代理截获，经本地代理封装后，通过隧道发到外地网络的外地代理FA(第一种CoA地址)或移动主机自身(第二种CoA地址)。第一种情况下，外地代理再把数据包转发给移动主机。此时，数据包在不同子网间传送成功。 (7)移动主机发送数据到一般的IP主机时，按正常的IP寻址方法发送，不必通过本地代理。 上述工作过程有效地解决了移动主机在子网间漫游通信的问题。但是，却在路由上存在着问题。当移动主机发送数据时，不管它是在本地网络还是在外地网络，它始终保留了它的本地网络地址，当它发送数据包时，可以用通常的IP协议发送。反之，当一般IP主机给移动主机发送数据包时，首先到达移动主机的本地代理(HA)。HA再根据收到的移动主机当前的接管地址CoA(假定为第一种地址)，将数据包发往外地网络，由外地代理最终将数据包发给移动主机，这就出现了路由的“三角问题”。最差的情况是当发送数据包的一般IP主机靠近移动主机所在的外地网络或移动主机已经漫游到发送主机所在的网络时，发送的数据包却仍要先到达移动主机的本地代理，再由本地代理发到外地代理，最后到达移动主机，这不仅增大了传输延迟，同时对一些延迟敏感的业务如音频、视频等造成极大的损害。其次，数据包在网络中运行时间过长，浪费了网络资源，增加了网络负担。 涉及知识点：网络层