[考研类试卷]计算机专业（基础综合）模拟试卷70及答案与解析.doc

1、计算机专业（基础综合）模拟试卷 70 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 以下算法中加下划线语句的执行次数为( )。int m=0，i， j；for(i=1；im ；（A）n(n+1)（B） n（C） n+1（D）n2 用链接方式存储的队列，在进行删除运算时，下列说法正确的是( )。（A）仅修改头指针（B）仅修改尾指针（C）头、尾指针都要修改（D）头、尾指针可能都要修改3 下列( ) 单链表最适合用作队列的存储方式。（A）带队头指针和队尾指针的循环链表（B）带队头指针和队尾指针的非循环链表（C）只

2、带队头指针的非循环链表（D）只带队头指针的循环链表4 已知完全二叉树的第 9 层有 240 个结点，则整个完全二叉树有( )个结点。（A）256（B） 258（C） 495（D）4895 已知一棵有 2011 个结点的树，其叶子结点个数是 116，该树对应的二叉树中无右孩结点个数是( ) 。（A）115（B） 116（C） 1895（D）18966 有 n 个叶子结点的哈夫曼树的结点总数为( )。（A）不确定（B） 2n（C） 2n+1（D）2n-17 在一个具有 n(n0) 个顶点的连通无向图中，至少需要的边数是( )。（A）n（B） n+1（C） n-1（D）n28 判断有向图是否存在回路

3、，除了可以利用拓扑排序方法外，还可以利用的是( )。（A）求关键路径的方法（B）求最短路径的迪杰斯特拉方法（C）深度优先遍历算法（D）广度优先遍历算法9 下列叙述正确的个数是( )。 (1)m=2 的平衡 m 路查找树是 AVL 树；(2)m=3 的平衡 m 路查找树是 2-3 树；(3)m=2 的平衡 m 路查找树的叶结点不一定在同一层；(4)m 阶 B-树的叶结点必须在同一层；(5)m 阶 B-树是平衡 m 路查找树；(6)平衡 m 路查找树不一定是 B-树。（A）3（B） 4（C） 5（D）610 采用简单选择排序，比较次数与移动次数分别是( )。（A）O(n)， O(logn)（B）

4、D(logn)，D(n 2)（C） O(n2)，D(n)（D）D(nlogn) ，O(n)11 已知关键序列 5，8，12，1 9，28，20，15，22 是小根堆(最小堆)，插入关键字3，调整后得到的小根堆是( )。（A）3，5，12，8，28，20，15，22，19（B） 3，5，1 2，1 9，20，15，22，8，28（C） 3，8，12，5，20，15，22，28，19（D）3，12，5，8，28，20，15，22，1912 计算机系统的层次结构，下列五个级别机器由下到上的顺序是( )。I机器语言机器汇编语言机器高级语言机器 Iv微程序控制机器V操作系统机器（A）I V（B） IV（

5、C） VIIV（D）VI13 计算机中常采用下列几种编码表示数据，其中，O 编码相同的是( )。I 原码 反码 补码 IV 移码（A）I 和（B） 和（C） 和（D）I 和14 按照 IEEE754 标准规定的 32 位浮点数(41A4C000) 16 对应的十进制数是( )。（A）459375（B） -2059375（C） -459375（D）20.593815 已知单个存储体的存储周期为 110 ns，总线传输周期为 10 ns，则当采用低位交叉编址的多模块存储器时，存储体数应( )。（A）11（B） =11（C） 11（D）t1116 设存储器容量为 32 字，字长 64 位，模块数 m

6、=4，存储周期 T=200 ns，数据总线宽度为 64 位，总线传送周期 T=50 ns。用交叉方式进行组织，交叉存储器的带宽是( )。（A）3210 7 位s（B） 8107 位s（C） 73107 位s（D）1 810 7 位s17 变址寻址与相对寻址的共同特点是( )。（A）利于编制循环程序、实现程序浮动（B）实现程序浮动、处理数组问题（C）实现转移指令、利于编制循环程序（D）实现程序浮动、利于编制循环程序18 假设某计算机系统采用 32 位单字长指令，地址码为 12 位，如果定义了 250 条二地址指令，那么还可以有( )条单地址指令。（A）4 K（B） 8 K（C） 16 K（D）2

7、4 K19 CPU 响应中断时需要保护断点，断点指的是( )。（A）中断服务程序的入口地址（B）程序计数器 PC 的内容（C） CPU 内各寄存器的内容（D）指令寄存器 IR 的内容20 在微程序控制器设计中，假设微命令采用最短编码法，需产生 n 种微操作，则微命令控制字段要设置的位数是( )。（A）log 2(n+1)（B） n（C） log1n（D）log 1n+121 在一个 16 位的总线系统中，若时钟频率为 100 MHz，总线周期为 5 个时钟周期传输一个字，则总线带宽是( )MBs。（A）4（B） 40（C） 16（D）6422 已知磁道转速为 360 rmin，假设寻道时间为

8、1040 ms，若在一个磁道上写入 4 096 B 的数据，平均需要( )。（A）833 ms（B） 1233 ms（C） 50 ms（D）1083 ms23 为了在通用操作系统管理下的计算机上运行一个程序，需要经历几个步骤，但是( )不是一定需要。（A）向操作系统预定运行时间（B）将程序装入内存（C）确定起始地址，并从这个地址开始执行指令（D）用控制台监控程序执行过程24 设有五个进程共享一个互斥段，如果最多允许两个进程同时进入互斥段，则所采用的互斥信号量初值应该是( )。（A）5（B） 2（C） 1（D）025 进程创建的时候，不需要做的是( )。（A）填写一个该进程的进程表项（B）为该进

9、程分配适当的内存（C）将该进程插入就绪队列（D）为该进程分配 CPU26 关于临界区问题(critical section problem)是一个算法 (假设只有进程 P0 和 P1 可能进入该临界区)，算法如下(i 为 0 或 1)，该算法( )。 repeat retry：if(turn-1)turn：=i； if(turni)go to retry ； tum：=-1： critical section(临界区) tum=0： remainder section(其他区域) until false：（A）不能保证进程互斥进入临界区，且会出现“饥饿”（B）不能保证进程互斥进入临界区，但不会

10、出现“饥饿”（C）保证进程能互斥进入临界区，但会出现“饥饿 ”（D）保证进程互斥进入临界区，不会出现“饥饿”27 进程 P1， P2 和 P3 单独执行时间分别为 10 min、15 min 和 20 min，其中处理机占用时间分别为 2 min、3 min 和 12 min。如果采用多道程序设计技术使其并发，并假设处理机的利用率可以达到 60，加上系统开销 5 分，那么并发使得计算机系统的效率提高了( ) 。（A）63（B） 38（C） 74（D）2628 段页式存储管理中，地址映射表是( )。（A）每个进程有一张段表、两张页表（B）每个进程的每个段有一张段表、一张页表（C）每个进程一张段表

11、，每个段一张页表（D）每个进程一张页表，每个段一张段表29 请求分页存储管理方案中，如果所需的页面不在内存中，则产生缺页中断，它属于( )。（A）硬件故障中断（B） IO 中断（C）外中断（D）程序中断30 文件的顺序存取是( )。（A）按终端号一次存取（B）按文件的逻辑号逐一存取（C）按文件的物理块号逐一存取（D）按文件逻辑记录的大小逐一存取31 物理文件的组织方式是由( )确定的。（A）应用程序（B）内存容量（C）外存容量（D）操作系统32 磁盘是一种可共享的设备，因此某一时刻读写它的用户进程可以是( )。（A）任意多个（B）能限定多个（C）至少能有一个（D）至多能有一个33 以下关于接口

12、概念的描述中，错误的是( )。（A）接口是通信节点之间交换信息的连接点（B）协议对接口信息交互过程与格式有明确的规定（C）低层通过接口向高层提供服务（D）只要接口条件与功能不变，低层功能具体实现方法不会影响整个系统的工作34 现采用调相与调幅相结合的调制方式，载波有四种相位变化和两种振幅变化，调制速率是 600 波特，那么数据速率是( )。（A）1 200 bps（B） 1 800 bps（C） 2 400 bps（D）3 600 bps35 在 CSMACD 协议中，下列指标与冲突时间没有关系的是( )。（A）检测一次冲突所需的最长时间（B）最小帧长度（C）最大帧长度（D）最大帧碎片长度36

13、 一个广域网信道的比特率是 4 Kbps，传播延迟为 20 ms，为了确保停止一等待协议至少 50的效率，那么，帧的大小至少是( )。（A）大于 160 bit，（B）大于 150 bit（C）大于 140 bit（D）大于 130 bit37 假设一个应用每秒产生 60 bytes 的数据块，每个数据块被封装在一个 TCP 报文中，然后再封装到一个 IP 数据报中。那么最后每个数据报所含有的应用数据所占的百分比是( ) 。（A）20（B） 40（C） 60（D）8038 以下动态路由算法中，使用距离一矢量路由算法的是( )。（A）RIP 协议（B） OSPF 协议（C） BGP 协议（D）I

14、CMP 协议39 当使用鼠标点取一个万维网文档时，若该文档除了有文本外，还有一个本地gif 图像和两个远地gif 图像。需要建立( )次 UDP 连接和( )次 TCP 连接。（A）0，3 次（B） 4，0 次（C） 0，4 次（D）4，4 次40 当客户端请求域名解析时，如果本地 DNS 服务器不能完成解析，就把请求发送给其他服务器，依次进行查询，直到把域名解析结果返回给请求的客户端，这种方式叫( ) 。（A）迭代解析（B）递归解析（C）迭代与递归解析相结合（D）高速缓存解析二、综合应用题41-47 小题，共 70 分。41 已知无向网 G 的邻接矩阵如下图所示，要求： (1)请画出该网；

15、(2) 画出基于该邻接矩阵的网 G 的宽度优先搜索生成树； (3)按克鲁斯卡尔算法给出 G 的一棵最小生成树的生成过程 (要求给出步骤)。42 有两个单链表 La 和 Lb，La 中有 m 个元素，Lh 中的元素个数为 n。已知两个链表均为递增的单向链表。现想将两个链表归并成一个递增的单向链表，且希望利用原来的结点空间，请回答下列问题：(1)给出算法的主要思想；(2)写出算法的实现函数；(3)总结所用算法的时间和空间复杂度。43 在虚拟地址和物理地址均为 32 位、页面大小为 4 KB 的某种体系结构中，假定存在下表所示的地址映像关系，问：对应于下列虚拟地址的物理地址分别是什么? (1)224

16、33007H； (2)13385ABCH ； (3)ABC89011H。44 某机器字长为 16 位，主存容量为 1 M16 位，有 63 种指令，CPU 有PC， IR，AR，DR 4 个基址寄存器和 4 个变址寄存器，16 个通用寄存器。(1)请设计合适字长的二地址(RS 型)指令，其中一个操作数有 4 种寻址方式；(2)说明各寄存器合适的位数；(3)说明各操作数的寻址方式及有效地址；(4)在上述指令格式的基础上如何增加 16 条一地址 S 型指令?45 系统中有 5 个进程，每个进程的运行时间(单位：ms)、优先级和到达时刻，如下表所示：请给出当系统分别采用时间片轮转算法(时间片为 Ir

17、es)、不可抢占优先级调度算法和抢占式优先级调度算法时，各进程的执行情况。46 在一个根目录常驻内存的文件系统中，目录文件采用链接结构，每个目录下最多存放 80 个文件或目录(称为下级文件)。每个磁盘块最多可存放 10 个文件目录项，且满足下列要求：如果下级文件是目录文件，则上级目录项指向该目录文件的第一块地址。假设目录结构中文件或子目录按自左向右的次序排列。请回答下列问题：(1)普通文件采用 UNIX 三级索引结构，即文件控制块中给出 13 个磁盘地址。前10 个磁盘地址指出文件前 10 块的物理地址；第 11 个磁盘地址指向一级索引表，一级索引表给出 256 个磁艋地址，即指出该文件第 1

18、1 块至第 266 块的物理地址；第 12 个磁盘地址指向二级索引表，二级索引表中指出 256 个一级索引表的地址；第 13 个磁盘地址指向三级索引表，三级索引表中指出 256 个二级索引表的地址。主索引表放在目录项中，若要读ADGI K 的第 7456 块，最多启动硬盘几次?(2)在(1)的条件下，若将 I 没置为当前目录，可以减少几次启动硬盘的次数 ?47 某公司网络拓扑图如下图所示，路由器 R1 通过接口 E1、E 2 分别连接局域网 1、局域网 2，通过接口 L0 连接路由器 R2，并通过路由器 R2 连接域名服务器与互联网。R1 的 L0 接口的 IP 地址是 20211821；R

19、2 的 L0 接口的 IP 地址是20211822；L 1 接 U 的 IP 地址是 13011 1201；E 0 接口的 IP 地址是20211831；域名服务器的 IP 地址是 202118 32。将 IP地址空间 2021181024 划分为两个子网，分配给局域网 1、局域网 2，每个局域网分配的地址数不少于 120 个，请给出子网划分结果，说明理由或给出必要的计算过程。请给出 R1 的路由表，使其明确包括到局域网 1 的路由、局域网 2 的路由、域名服务器的主机路由和互联网的路由。请采用路由聚合技术，给出 R2 到局域网 1 和局域网 2 的路由。计算机专业（基础综合）模拟试卷 70

20、答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 A【试题解析】 m+语句的执行次数为 n(n+1)，结果为 A。2 【正确答案】 D【试题解析】 链队列中删除元素一般仅修改队头指针，但只有一个元素时，出队后队空，此时还要修改队尾指针。3 【正确答案】 B【试题解析】 由于队列在队头和队尾都需要进行操作，只有 A，B 比较符合题意。对于一个队列来说，有了队头指针就可以完成删除操作，有了队尾指针就可以完成入队操作，不需要循环链表，非循环是较为合适的，答案选 B。4 【正确答案】 C【试题解析】 在完伞

21、二叉树中，若第 9 层是满的，则第 9 层结点数=2 8=256，而现在第 9 层只有 240 个结点，说明第 9 层术满，是最后一层。其 18 层是满的，所以总的结点数=2 8 一 1+240=495。5 【正确答案】 D【试题解析】 可以采用特殊情说法求解。可举如下特例二又树中仅有前 115 个结点有右孩子结点，其余 1896 个结点均无右孩子结点。6 【正确答案】 D【试题解析】 在哈夫曼树中，由计算公式可得，结点总数为 2n 一 1，所以选D。7 【正确答案】 C【试题解析】 在无向图中，如果从一个顶点 Vi 到另一个顶点 Vj(ij)有路径，则称顶点 Vi 和 Vj 是连通的。如果图

22、中仟意两顶点都是连通的，则称该图是连通图。所以具有 n 个顶点的连通无向图至少有 n1 条边8 【正确答案】 C【试题解析】 当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序为逆向的拓扑序列。9 【正确答案】 D【试题解析】 参见 B-树定义。10 【正确答案】 C【试题解析】 对 n 个记录进行简单选择排序，所需进行的关键字间的比较次数为n(n 一 1)2；移动记录的次数，最小值为 0，最大值为 3(n1)，所以简单选择排序的最好和平均时间复杂度均为 O(n2)。11 【正确答案】 A【试题解析】 根据题目中给出的序列建立一个堆，并将其调整为小根堆，其过程如下： 可以得出调整后

23、的小根堆为 3，5，12，8，28，20，15，22，19。12 【正确答案】 B【试题解析】 现代计算机系统是一个硬件与软件组成的综合体，可以把它看成按功能划分的多级层次结构。计算机系统的多层次结构，如下图所示。层次结构由高到低的次序分别是：应用语言机器级、高级语言机器级、汇编语言机器级、操作系统机器级、传统机器级、微稃序机器级。对每一个机器级的用户来说，都可以将此机器看成是一台独立的使用自己特有的“机器语言”的机器。13 【正确答案】 C【试题解析】 假设字长为 8 位，+0 原 =00000000，-0 原 =1 0000000；+0 反=00000000，-0 反 =11111111；

24、+0 补 ：-0 补 =00000000；+0 移 =-0移 =1 00000000，对于真值 0，原码和反码各有两种不同的表示形式，而补码和移码只有唯一的一种表示形式。正因为补码和移码 0 的表示形式唯一，才使得补码和移码比原码和反码能多表示一个负数。14 【正确答案】 D【试题解析】 IEEE754 标准浮点数的格式如下图所示：(41A4C000)16=(0100000110100100I 100000000000000)2 符号位=0 阶码=1000 0011阶码真值=131-127=4 真值=+1 010010011 0002 4=1010010011=(20 59375) 10 对于

25、 32 位的短浮点数，最高位为数符位，其后是 8 位阶码，以 2 为底，用移码表示，阶码的偏置值为 127。其余 23 位是尾数数值位。对于规格化的二进制浮点数，数值的最高位总是“1”。为了能使尾数多表示一位有效值，可将这个“1”隐含，因此尾数数值实际上是 24 位(1 位隐含位+23 位小数位)。将十六进制代码写成二进制形式，并分离出符号位、阶码和尾数，然后计算出阶码真值(移码减去偏置值)，接着先以规格化二进制数形式写出此数，再将它写成非规格化二进制数形式，最后转换成十进制数，并加上符号位。15 【正确答案】 D【试题解析】 为了保证第二次启动某个体时，它的 1 次存取操作已完成，存储体的数

26、量应大于等于 11(110 ns10 ns=11)。16 【正确答案】 C【试题解析】 顺序存储存储器连续读出 4 个字需要 4 个存储周期，而交叉存储存储器连续读出 4 个字，由于采用分时启动的方法，只需要一个存储周期加上三个总线传输周期的时间。现字长为 64 位，交叉存储器连续读出 4 个字的信息总量 q=64位4=256 位，交叉存储器连续读出 4 个字所需的时间 t=T+(41)=200 ns+350 ns=350 ns=3510 -7s，所以交叉存储器的带宽 W=gt=256(3510 -7)=73107(位5)。17 【正确答案】 A【试题解析】 变址寻址便于处理数组问题和编制循环

27、程序；而相对寻址的有效地址是将 PC 的内容与指令中的形式地址 A 相加而成的。这样程序的转移地址不周定，可随 PC 值的变化而变，可以很方便地将程序装入主存的任意区域，有利于浮动程序的编制。18 【正确答案】 D【试题解析】 地址码为 12 位，则二地址指令的操作码长度为 32-12-12=8 位，已定义了 250 条二地址指令，2 8-250=6，即可以设计出单地址指令 6212=24 K 条。19 【正确答案】 B【试题解析】 CPU 在一条指令执行结束时响应中断。断点指的是程序计数器 PC的内容，也就是现行程序下一条将要执行指令的地址。20 【正确答案】 C【试题解析】 由于微命令控制

28、字段必须是一个整数，所以在最短编码法中为log2n位。最短编码法将所有的微命令统一编码，每条微指令只定义一个微命令。若微命令的总数为 n，操作控制字段的长度为 L，则最短编码法应满足下列关系式：Llog2n。21 【正确答案】 B【试题解析】 总线频率=1总线周期=1(5*时钟周期)=1 (5时钟频率)=时钟频率5=100MHz 5=20 MHz 。总线带宽=总线频率总线宽度=20*(16 8)=40 MBs。22 【正确答案】 D【试题解析】 磁盘转速为：360 rmin=6 rs。平均等待时间为：161 000 ms1 2=833 ms。写入一道数据(平均)时间为：平均等待时间+平均找道时

29、间=(10+40)2+833=108 3 ms。由于信息写入 4 096 B 在同一条磁道上，因此写入数据所用道数为 1，写入数据平均需要时间为 1083 ms 。23 【正确答案】 A【试题解析】 实时系统才需要预定 CPU 时间。24 【正确答案】 B【试题解析】 因为最多允许两个进程同时进入互斥段，所以信号量为 2。如果一个互斥段可以同时允许两个进程进入，则相当于有两个互斥段。25 【正确答案】 D【试题解析】 本题考查的是进程创建的过程。进程创建最主要的工作是为该进程申请并填写一张进程表。进程表内包含有多个与进程有关的数据结构，例如进程号、进程组、进程的优先级、进程所分配的内存、进程需

30、要的 IO 设备、进程要打开的文件等。当填写好了进程表以后，进程创建模块，按照该系统规定的法则将进程表插入就绪队列的适当位置，等待进程调度模块进行下一步的调度。所以进程创建的过程中不会包含分配 CPU 的过程，这不是进程创建者的工作，而是调度器的工作。26 【正确答案】 A【试题解析】 例如当 P0 执行完语句 turn：=-1，刚好要进入临界区时， CPu 又调度 P1 执行，P 1 能够顺利进入临界区，不能满足互斥。当 P0 执行完临界区时，CPU调度 P2 执行，P 2 在 retry 循环，CPU 调度 P0 执行，P 0 继续执行，重复以上过程，会导致 P2 饥饿。27 【正确答案】

31、 D【试题解析】 本题考查并发的计算。由于本题并没有详细描述进程的执行过程，所以，是以总体效率来计算的。总体效率是指并发以后所花费的时间值与原时间值相比提高了多少。以本题的题意，我们可以计算出处理机所需时间为：2+3+12=17(min)；按处理机 60的利用率，并发所需总时间为：1760+5=3333(min)；单道运行时所需要的总时间为：10+15+20=45(min)，则系统效率提高了：(45-3333)45=26。28 【正确答案】 C【试题解析】 页式存储管理的特征是等分内存，解决了外碎片问题。段式存储管理的特征是逻辑分段，便于实现共享和保护。为了保持页式和段式上的优点，结合两种存储

32、管理方案，形成了段页式存储管理。系统为每个进程建立一张段表，为进程的每一段各建立一张页表。地址转换过程，要经过查段表、页表后才能得到最终的物理地址。故正确答案为 C。29 【正确答案】 D【试题解析】 本题考查中断的概念。30 【正确答案】 B【试题解析】 文件顺序存取就是按逻辑编号顺序存取。31 【正确答案】 D【试题解析】 文件的物理结构是指文件在外存上的存储组织形式，既与存储介质的存储性能有关，又与操作系统所采用的外存分配方法有关。因此，应选择选项D。32 【正确答案】 D【试题解析】 虽然磁盘是可共享的设备，但是在某一个时刻，能够读写访问它的进程只能是一个。微观上，进程是轮流交替使用磁

33、盘设备的，但是在某一段时一间内，可以允许多个用户或进程使用它。这里有一点区别，用户直接使用系统调用对磁盘进行读写与通过文件系统对存放在磁盘上的文件数据进行读写是不同的。前者是对设备 IO 操作，后者是对文件系统的操作。文件系统采用缓冲区等多种方式使得用户对文件的访问可以并发，然而，如果是对磁盘直接 IO 操作，当前一个操作没有撤离时，后一个操作必定要阻塞等待。33 【正确答案】 A【试题解析】 协议是对等通信节点间交换的信息的纽带，不是接口。34 【正确答案】 D【试题解析】 本题考查奈奎斯特定理的应用。这里载波有四种相位变化和两种振幅变化，也就是离散值为 8，由奈奎斯特定理公式可得：2600

34、log 28=3 600 bps，因此答案是 D。35 【正确答案】 C【试题解析】 本题考查 CSMACD 协议中冲突时间。冲突时间就是能够进行冲突检测的最长时间，其决定了最小帧的长度和最大帧碎片的长度，对最大帧的长度没有影响，因此答案是 C。36 【正确答案】 A【试题解析】 当发送一帧的时间等于信道传播延迟的 2 倍时，信道利用率是50。或者说，当发送一帧的时间等于来回路程的传播延迟时，效率将是 50。本题中，往返传播时间为 20 ms2=40 ms，发送速率是每秒 4 000 位，即发送 1 位需 025 ms。40 ms025 ms位=160 位。所以，帧大于 160 位时，采用停一

35、等协议才有至少 50的效率，答案是 A。37 【正确答案】 C【试题解析】 一个 TCP 的头部长度是 20 字节，一个 IP 头部的长度是 20 字节，再加上 60 字节的数据，一个 IP 数据报的总长度为 100 个字节，其中数据占 6038 【正确答案】 A【试题解析】 RIP 协议使用了距离一矢量路由算法。39 【正确答案】 C【试题解析】 需要建立 O 次 UDP 连接。4 次 TCP 连接。40 【正确答案】 B【试题解析】 进行递归查询时，DNS 客户机向 DNS 服务器发送请求。即使 DNS服务器没有所请求的信息，则会联系其他 DNS 服务器来提供答案或返回查询失败信息。二、综

36、合应用题41-47 小题，共 70 分。41 【正确答案】 (1)无向网如下： (2)宽度优先搜索生成树，如下： (3)按克鲁斯卡尔算法生成的一棵最小的生成树的过程42 【正确答案】 (1)基本思想：遍历链表 La 和 Lb，将其元素值进行比较，再合并成一个递增的单向链表。(2)算法的实现如下：链表结点定义为：struct nodeint value；struct node*Next：；struct node *merge(struct node*a，struct node*b)struct node *P；struct node *q；struct node *t；if(a-valueval

37、ue)比较当前指针所指值的大小P=a：q=b；elseP=b： q=a：t=P：while(q)如果 b 链表先结束，那么将 a 链表剩余结点全部合并到新链表if(p-Next=NULL)p-Next=q；break：if(q-valueNext -Value)struct node * k=q-Next；q-Next=p-Next；p=p-Next；q=k；continue；p=p-Next；return t：(3)遍历链表的时间复杂度为 O(max(m，n)，算法实现过程中使用的辅助空间为常量，空间复杂度为 O(1)。43 【正确答案】 假设虚拟地址和物理地址均为 32 位，页大小为 4

38、KB，则页内地址 12 位，其余 20 位为页号，通过查找第 43 题表，可以将虚页号映像到对应的实页号。将实页号与页内地址拼接在一起，就得到对应的物理地址。(1)虚拟地址 22433007H 中，虚页号为 22433H，其对应的实页号为 00001 H，所以对应的物理地址 00001007H。(2)虚拟地址 13385ABCH 中，虚页号为 13385 H，其对应的实页号为 99910H，所以对应的物理地址 99910ABCH。(3)虚拟地址 ABC89011H 中，虚页号为 AlBC89H，其对应的实页号为 97887H，所以对应的物理地址 97887011H。44 【正确答案】 (1)双

39、字长指令格式如下图：XX：可以指定 4 种不同的寻址方式。地址 1 和地址 2 共同表示内存中的 20 位地址。(2)基址寄存器、变址寄存器 20 位；通用寄存器 16 位。(3)由于指令码共可以指定64 个指令。因此可以令指令码为 111111，与指定寄存器的 4 位组成指令码，则一共可以产生 16 条新的指令。XX 在这种格式中为无效位。45 【正确答案】 (1)时间片轮转算法46 【正确答案】 (1)在 UNIX 三级索引结构中，要想访问A DGIK 的第7456 块，最多情况需要访问两级索引，也就是最多需要启动 7 次磁盘即可访问。(2)如果当前目录是 I，那么至少可以减少启动 4 次

40、磁盘。47 【正确答案】 (1)CIDR 中的子网号可以全 0 或全 1，但主机号不能全 0 或全 l。 因此，若将 IP 地址空间 2021181024划分为 2 个子网，且每个局域网需分配的 IP 地址个数不少于 120 个，子网号至少要占用 1 位。 由 26-21 202 7-2可知，主机号至少要占用 7 位。 由于源 IP 地址空间的网络前缀为 24 位，因此，主机号位数+子网号位数=8 位。 综上可得：主机号位数为 7，子网号位数为 1。 因此，子网的划分结果为：2021181025，20211 8112825。 (2)由于局域网 1 和局域网 2 分别与路由器 R1 的 E1、E

41、 2 接口直接相连，因此在 R1 的路由表中，目的网络为局域网 1 的转发路径是直接通过接口 E1 转发，目的网络为局域网 2 的转发路径是直接通过接口 E1 转发。由于局域网 1、2 的网络前缀均为 25 位，因此它们的子网掩码均为 255255255128。 根据题意，R 1 专门为域名服务器设定了一个特定的路由表项，因此该路由表项中的子网掩码应为255255255255。对应的下一跳转发地址是 20211822，转发接口是Ln。根据 题意，到互联网的路由实质上相当于一个默认路由，默认路由一般写作00，即目的地址为 0000，子网掩码为 0000。对应的下一跳转发地址是 20211 822，转发接口是 Ln。R 1 的路由表为：(3)局域网 1 和局域网 2 的地址可以聚合为 2021181024，而对于路由器 R2来说，通往局域网 1 和 2 的转发路径都是从 L0 接口转发，因此采用路由聚合技术后，路由器 R2 到局域网 1 和局域网 2 的路由为：