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的路由。
一． 选择题
6
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
为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区，该缓冲区的逻辑结构应该是（队列）
栈的定义:栈是只准在表尾进行插入和删除的线性表，称为LIOFO（即后进先出表）。允许插入和删除的一端叫栈顶，另一端叫栈底。队列的定义：队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列也称为先进先出表（FIFO） 树的定义：树是包含n个结点的有限集合（n>0）
图的定义：图（Graph）是由非空的顶点集合和一个描述顶点之间关系——边（或者弧）的集合组成。其形式化定义为：G=(V ,E）
其中G表一个图，V是图G中顶点的集合，E是图G中边的集合。
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提出了一种适用于外查找的树，它是一种平衡多叉树） 定义：
⑴ 树中每个结点至多有m个孩子；
⑵ 除根结点和叶子结点外，其它每个结点至少有m/2个孩子；
⑶ 若根结点不是叶子结点，则至少有2个孩子(除非B树只有一个结点)； ⑷ 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；
⑸ 有k个孩子的非终端结点恰好包含有k-1个关键字(各节点内关键字均升序或降序排列).
9.堆(Heap)分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树： (1)若树根结点存在左孩子，则根结点的值(或某个域的值)小于等于左孩子结点的值(或某个域的值)；
7
(2)若树根结点存在右孩子，则根结点的值(或某个域的值)小于等于右孩子结点的值(或某个域的值)； (3)以左、右孩子为根的子树又各是一个堆。
大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。
由堆的定义可知，若一棵完全二叉树是堆，则该树中以每个结点为根的子树也都是一个堆。
分别为一个小根堆和一个大根堆。根据堆的定义可知，堆顶结点，即整个完全二叉树的根结点，对于小根堆来说具有最小值，对于大根堆来说具有最大值。
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层向上调整,直到被调整到堆顶位置为止。 10.数据元素序列11，12，13，7，8，9，23，4，5是第二趟排序后的结果，则该排序算法只能是插入排序。 气泡排序基本思想：
设待排序对象序列中的对象个数为n。一般地，第i趟起泡排序从1到n-i+1依次比较相邻两个记录地关键字，如果发生逆序，则交换之，其结果是这n-i+1个记录中，关键字最大的记录被交换到第n-i+1的位置上，最多作n-1趟。 简单选择排序基本思想：
第一趟在R[1..n]中选最小的，与R[1]交换
第二趟在R[2..n]中选最小的，与R[2]交换，依次类推，进行n-1次选择后，整个文件有序。 直接插入排序基本思想:
将一个记录插入到已排序的有序表中，使插入后的表仍然有序。 折半插入排序基本思想：
将一个记录插入到已排序的有序表中，使插入后的表仍然有序，但插入时利用折半搜索法寻找元素的插入位置。
归并排序基本思想：
又一类不同的排序方法，将两个或两个以上的有序表合并成一个新的有序表。
快速排序基本思想：
取R[1..n]中任一记录作为“枢轴”，一趟排序之后枢轴的值均小于“枢轴”左边的值，枢轴右边的值均大于“枢轴”的值。
堆排序基本思想：
1.如何将一个无序序列调整为堆？
2.如何在互换堆顶之后重新调整为堆（关键）？ 希尔排序 (Shell Sort) 基本思想：
1.n大，划分成若干子序列，分别直接插入排序。 2.待整个记录“基本有序”时，对整体直接重排。 11.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是指令周期的不同阶段。
12.十进制转换：
十进制转任意进制的通用方法是：除x取余倒排法（x代表进制数）。 如：将十进制数76转换成任意进制 1.转成二进制 76 / 2 ... 0 = 38 / 2 ... 0 = 19 / 2 ... 1 = 9 / 2 ... 1 = 4 / 2 ... 0 = 2 / 2 ... 0
8
= 1 / 2 ... 1
76(10) = 1001100(2)
2.转成八进制 76 / 8 ... 4 = 9 / 8 ... 1 = 1 / 8 ... 1 76(10) = 114(8)
3.转成十六进制 76 / 16 ... 12 = 4 / 16 ... 4 76(10)=4C(16) B ：二进制数。 Q ：八进制数。 D ：十进制数。 H ：十六进制数。
负数用十六进制和八进制怎么表示？ 使用补码（二进制），而且还要指定字长 比如说一个二字节整型的 -2 就应该是： 11111111 11111110 再转化其它进制 十六进制：FFFE 八进制：177776
13.浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数X=2^7*29/32，Y=2^5*5/8,则用浮点加法计算X+Y的最终结果是发生溢出
浮点数表示：小数点的位置可以在一定范围内浮动。 E为阶，包括阶符和阶码（整数），阶码为数决定了浮点数的表示范围。 M为位数，包括数符和尾数，表示数的精度和正负。 对阶原则：小阶对大阶。
双符号位判溢：加，减后。两个符号位出现“01”，表示已经溢出，即结果大于+1. 14.存储器的分类：
1.按存储介子分:(1)半导体存储器;(2)磁表面存储器;(3)光介子存储器。
2.按存取方式分类:(1)随机存取存储器 RAM；(2)顺序存储器 SAM；(3)直接存取存储器 DAM。 3.按计算机功能分类: (1)主存储器（主存）
用于存放计算机运行期间的大量程序和数据的存储器，CPU能直接访问。由MOS存储器构成。 (2)高速缓冲存储器（Cache）
Cache是介于CPU和主存之间高速小容量存储器，用于存放最活跃的程序块和数据。由静态MOS存储器构成。
特点：速度快，但容量小，位价格较高。
主存和Cache一起构成计算机的内存储器（内存），是CPU能直接访问的存储器。 (3)辅助存储器（外存储器）
存放当前暂不参与运行的程序和数据，需要时再与主存成批交换信息的存储器。 特点是容量大，可存放大量的程序和数据，但速度慢。
9
(4)控制存储器（CM）
在微程序控制的计算机中，用于存放执行指令的微程序的存储器。 CM一般由ROM构成，属于控制器的一部分。 4.其它分类：
a.按读写功能分类：
(1)只读存储器(ROM):工作时只能读出不能写入的存储器。 (2)读写存储器(RAM):既能读出又能写入的存储器。 b.按信息的可保存性分类
(1)永久性存储器：指断电后仍能保存信息的存储器，如磁表面存储器。 (2)非永久性存储器:指断电后信息即消失的存储器，如半导体读写存储器。 某计算机的Cache共有16块，采用2路组相连映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到Cache组号是(4)
15.主存容量是根据地址线的位数来确定的,在16位PC机中地址总线的宽度是20位,则主存大小为:2^20 byte=1MB,现在的PC机一般都是32位地址总线的,最大直接寻址空间为:2^32,即主存最大容量为4GB 某计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区，按字节编址。现要用2K*8位的ROM芯片和4K*4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是2 30 16.某计算机字长16位，主存按字节编址，转换指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是(2008H)
相对寻址:以当前程序计数器pc的内容为基址，加上指令给出的一字节补码数（偏移量）形成新的pc值的寻址方式称为相对寻址。
目的地址=源地址+相对转移指令字节数+指令中给定的偏移量(rel). 17.RISC(精简指令系统)的叙述:
(1).选用的是使用频率很高的一些简单指令； (2).指令长度固定，指令格式及寻址方式种类少；
(3).只有取数/存数指令访问存储器，其余指令的操作都在寄存器之间进行； (4).大多数指令可在一个计算机周期内完成。 18.指令周期是取出并执行一条指令的时间。
指令周期常常有若干个CPU周期，CPU周期也称为机器周期，由于CPU访问一次内存所花费的时间较长，因此通常用内存中读取一个指令字的最短时间来规定CPU周期。这就是说一条指令取出阶段（通常为取指）需要一个CPU周期时间。而一个CPU周期时间又包含若干个时钟周期(通常为节拍脉冲或Ｔ周期，它是处理操作的最基本的单位)。这些时钟周期的总和则规定了一个CPU周期的时间宽度。
某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓冲时间）分别是90ns、80ns、70ns、60ns，则计算机的CPU时钟周期是(90ns)。
19.相对于微程序控制器，硬布线控制器的特点是指令执行速度快，指令功能的修改和扩展难。
20.假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是(20MB/S) 时钟周期和时钟频率互为倒数关系。 1KHz=1000Hz； 1MHz=1000KHz
并行总线带宽(MB/s) = 并行总线时钟频率(MHz) * 并行总线位宽(bit/8 = B) * 每时钟传输几组数据(cycle) 串行总线带宽(MB/s) = 串行总线时钟频率(MHz) * 串行总线位宽(bit/8 = B) * 串行总线管线 * 编码方式 * 每时钟传输几组数据(cycle) 1字节（Byte）= 8位（bit）
21.假设某计算机的存储系统由Cache和主存组成，某程序执行过程中访存1000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是(95%)
10