2009-2010计算机考研真题及答案（含选择题解析）WORD高清晰版(3)

（R1），R0”的功能为（R0）+（（R1））→（R1），即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。

数据通路结构

下表给出了上述指令取值和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描 述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。 功能和控制信号 时钟 C1 C2 C3 C4

功能 MAR←(PC) MDR←M(MAR) PC←(PC)+1 IR←(MDR) 指令译码 有效控制信号 PCout,MARin MemR,MDRinE PC+1 MDRout,IRin 无 45.（7分）三个进程P1、P2、P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。

6

46.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示。 页面大小为4KB，一次内存的访问时间是100ns，一

页号 页框号 有效位 次快表（TLB）的访问时间是10ns，处理一次缺页的平均

（存在位） 时间为108ns（已含更新TLB和页表的时间），进程的驻

0 101H 1 留集大小固定为2，采用最近最少使用置换算法（LRU）

1 -- 0 和局部淘汰策略。假设

2 254H 1 ①TLB初始为空；

②地址转换时先访问TLB，若TLB未命中，再访问页表 （忽略访问页表之后的TLB更新时间）；

③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列 2362H、1565H、25A5H，请问：

（1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。

（2） 基于上述访问序列，虚地址1565H的 物理地址是多少？请说明理由。

47．（9分）某公司网络拓扑图如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2， 通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是 202.118.2.1；R2的L0接口的IP地址是202.118.2.2，L1接口的IP地址是130.11.120.1，E0接口的 IP地址是202.118.3.1；域名服务器的IP地址是202.118.3.2。

将IP地址空间202.118.1.0/24划分为两个子网，分配给局域网1、局域网2，每个局域网分配的地 址数不少于120个，请给出子网划分结果。说明理由或给出必要的计算过程。

请给出R1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和 互联网的路由。 请采用路由聚合技术，给出R2到局域网1和局域网2的路由。

7

2009年计算机统考真题参考答案

一． 选择题

1 2 3 4 5 6 7 8 9 10 B C D B C B A D A B 11 12 13 14 15 16 17 18 19 20 C D D C D C A A D B 21 22 23 24 25 26 27 28 29 30 D A D D C A C B A A 31 32 33 34 35 36 37 38 39 40 B A B B C A D D C A

1.为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区，该缓冲区的逻辑结构应该是（队列）

栈的定义:栈是只准在表尾进行插入和删除的线性表，称为LIOFO（即后进先出表）。允许插入和删除的一端叫栈顶，另一端叫栈底。

队列的定义：队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列也称为先进先出表（FIFO）

树的定义：树是包含n个结点的有限集合（n>0）

图的定义：图（Graph）是由非空的顶点集合和一个描述顶点之间关系——边（或者弧）的集合组成。其形式化定义为：G=(V ,E）

其中G表一个图，V是图G中顶点的集合，E是图G中边的集合。

8

2.设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag,则栈S的容量？？？（3）

3.给定二叉树图，若遍历后的结点序列为XXX，则其遍历方式是？？？ 设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

4.平衡二叉树定义:若一棵二叉树中每个结点的左、右子树的高度至多相差1，则称此树为平衡二叉树。我们把二叉树中每个结点的左子树高度减去右子树高度定义为该结点的平衡因子(balance factor)。因此，平衡树中每个结点的平衡因子只能是1、0或-1。

5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是？？？（111）

二叉树：二叉树是一种重要的树形结构，它是n（n>=0）个结点的有限集，其子树分为互不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是如上定义的二叉树。左子树和右子树的顺序不能互换。

满二叉树：深度为k结点数为2^k-1的二叉树。

完全二叉树：若对满二叉树的结点从上到下从左到右进行编号，则深度为k且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树的编号从1到n一一对应时，称为完全二叉树。

6.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是:父子关系或兄弟关系。

森林转换为对应的二叉树:兄弟之间连线，父只与长子连线。（左孩子右兄弟）

7.无向连通图特性的叙述:所有顶点的度之和为偶数。 顶点的度定义：与定点v相关联的边数(每个环计算两次)。

度为零的顶点称为孤立顶点，度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。

8.一棵m阶B树（1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡多叉树） 定义：

9

⑴ 树中每个结点至多有m个孩子；

⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；

⑶ 若根结点不是叶子结点，则至少有2个孩子(除非B树只有一个结点)； ⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；

⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字(各节点内关键字均升序或降序排列).

9.堆(Heap)分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树： (1)若树根结点存在左孩子，则根结点的值(或某个域的值)小于等于左孩子结点的值(或某个域的值)； (2)若树根结点存在右孩子，则根结点的值(或某个域的值)小于等于右孩子结点的值(或某个域的值)； (3)以左、右孩子为根的子树又各是一个堆。

大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。

由堆的定义可知，若一棵完全二叉树是堆，则该树中以每个结点为根的子树也都是一个堆。

分别为一个小根堆和一个大根堆。根据堆的定义可知，堆顶结点，即整个完全二叉树的根结点，对于小根堆来说具有最小值，对于大根堆来说具有最大值。

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键 …… 此处隐藏：1988字，全部文档内容请下载后查看。喜欢就下载吧 ……