2015年408真题及答案(2)

请回答下列问题：

1）写出图G的邻接矩阵A（行、列下标从0开始）。

2）求A2，矩阵A2 中位于0 行3 列元素值的含义是什么？

3）若已知具有n（n≥2）个顶点的图的邻接矩阵为B，则Bm（2≤m≤n）中非零元素的含义是什 么？

43．（13分）某16位计算机的主存按字节编码，存取单位为16位；采用16位定长指令字格式； CPU 采用单总线结构，主要部分如下图所示。图中R0～R3 为通用寄存器；T 为暂存器；SR 为移位寄存器，可实现直送（mov）、左移一位（left）和右移一位（right）3种操作，控制信号为SRop，SR的输出由信号SRout控制；ALU可实现直送A（mova）、A加B（add）、A减B（sub）、A与B（and）、A或B（or）、非A（not）、A加1（inc）7种操作，控制信号为ALUop。

请回答下列问题。

1）图中哪些寄存器是程序员可见的？为何要设置暂存器T？ 2）控制信号ALUop 和SRop 的位数至少各是多少？ 3）控制信号SRout 所控制部件的名称或作用是什么？

4）端点①～⑨中，哪些端点须连接到控制部件的输出端？

5）为完善单总线数据通路，需要在端点①～⑨中相应的端点之间添加必要的连线。写出连线的起点和终点，以正确表示数据的流动方向。

6）为什么二路选择器MUX 的一个输入端是2？ 44．（10分）题43中描述的计算机，其部分指令执行过程的控制信号如下图所示。

·6·

题图a 部分指令控制信号该机指令格式如下图所示，支持寄存器

直接和寄存器间接两种寻址方式，寻址方式位分别为0和1， 通用寄存器R0～R3 的编号分别为0、1、2 和3。

题图b 指令格式

请回答下列问题。

1）该机的指令系统最多可定义多少条指令？

2）假定inc、shl 和sub 指令的操作码分别为01H、02H 和03H，则以下指令对应的机器代码各是什么？ ①inc R1 ; R1 +1→R1 ②shl R2,R1 ; (R1) <<1→R2 ③ sub R3,(R1),R2 ; ((R1)) – (R2) →R3

3）假设寄存器X的输入和输出控制信号分别为Xin和Xout，其值为1表示有效，为0表示无效（例如，PCout=1表示PC内容送总线）；存储器控制信号为MEMop，用于控制存储器的读(read）和写(write)操作。写出题图a中标号①～⑧处的控制信号或控制信号的取值。

4）指令“sub R1,R3,(R2)”和“inc R1”的执行阶段至少各需要多少个时钟周期？

45．（9分）有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件（0

CoBegin

·7·

A{ while(TRUE){ 从A 的信箱中取出一个邮件；回答问题并提出一个新问题；将新邮件放入B 的信箱； } B{ while(TRUE){ 从B 的信箱中取出一个邮件；回答问题并提出一个新问题；将新邮件放入A 的信箱； } } } CoEnd

当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。请添加必要的信号量和P、V（或wait、signal）操作，以实现上述过程的同步。要求写出完整过程，并说明信号量的含义和初值。

46．（6分）某计算机系统按字节编址，采用二级页表的分页存储管理方式，虚拟地址格式如下所 示：

10位 10位 12位 页目录号 页表索引 页内偏移量 请回答下列问题。 1）页和页框的大小各为多少字节？进程的虚拟地址空间大小为多少页？

2）假定页目录项和页表项均占4 个字节，则进程的页目录和页表共占多少页？要求写出计算过程。 3）若某指令周期内访问的虚拟地址为0100 0000H 和0111 2048H，则进行地址转换时共访问多少个二级页表？要求说明理由。

47．（9分）某网络拓扑如图所示，其中路由器内网接口、DHCP服务器、WWW服务器与主机1 均采用静态IP 地址配置，相关地址信息见图中标注；主机2～主机N 通过DHCP 服务器动态获取IP 地址等配置信息。

请回答下列问题。

1）DHCP 服务器可为主机2～主机N 动态分配IP 地址的最大范围是什么？主机2 使用DHCP 协议获取IP 地址的过程中，发送的封装DHCP Discover

2）若主机2 的ARP 表为空，则该主机访问Internet 时，发出的第一个以太网帧的目的MAC 地址是什么？封装主机2 发往Internet 的IP 分组的以太网帧的目的MAC 地址是什么？

3）若主机1 的子网掩码和默认网关分别配置为255.255.255.0 和111.123.15.2，则该主机是否能访问WWW 服务器？是否能访问Internet？请说明理由。

·8·

2015 年计算机学科专业基础综合试题参考答案

一、单项选择题

1． A 9． C 17． B 25． D 33． D

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

二、综合应用题

41．解答：

1）算法的基本设计思想算法的核心思想是用空间换时间。使用辅助数组记录链表中已出现的数值从而只需对链表进行 一趟扫描。

因为|data|≤n，故辅助数组q 的大小为 n+1，各元素的初值均为0。依次扫描链表中的各结点，同时检查q[|data|]的值，如果为0，则保留该结点，并令q[|data|]=1；否则，将该结点从链表中删除。

2）使用C 语言描述的单链表结点的数据类型定义

typedef struct

node{ int data; struct node*link; }NODE;

Typedef NODE *PNODE;

3）算法实现

void func (PNODE h,int n) { PNODEp=h,r;

int *q,m;

q=(int*)malloc(sizeof(int)*(n+1));//申请n+1个位置的辅助空间 for(int i=0;i

*(q+i)=0;

while(p->link!=NULL)

{ m=p->link->data>0?p->link->data:-p->link->data;

//判断该结点的data是否已出现过 if(*(q+m)==0)

//首次出现 { *(q+m)=1;

//保留 p=p->link;

} else //重复出现

//删除 { r=p->link;

p->link=r->link free(r); } }

free(q); }

·9·

【评分说明】若考生设计的算法满足题目的功能要求且正确，则酌情给分。

4）参考答案所给算法的时间复杂度为O(m)，空间复杂度为O(n)。

【评分说明】若考生所估计的时间复杂度和空间复杂度与考生实现的算法一致，可给分。 42．解答：

1）图G 的邻接矩阵A 如下：

2）A如下：

2

0 行3 列的元素值3 表示从顶点0 到顶点3 之间长度为2 的路径共有3 条。

3）Bm（2≤m≤n）中位于i 行j 列（0≤i，j≤n-1）的非零元素的含义是：图中从顶点i 到顶点j 长度为m 的路径条数。

43．解答：

1）程序员可见寄存器为通用寄存器（R0～R3）和PC。因为采用了单总线结构，因此，若无暂存器T，则ALU 的A、B 端口会同时获得两个相同的数据，使数据通路不能正常工作。

【评分说明】回答通用寄存器（R0～R3），给分；回答PC，给分；部分正确，酌情给分。设置暂存器T 的原因若回答用于暂时存放端口A 的数据，则给分，其他答案，酌情给分。

2）ALU 共有7 种操作，故其操作控制信号ALUop 至少需要3 位；移位寄存器有3 种操作，其操作控制信号SRop 至少需要2 位。

3）信号SRout 所控制的部件是一个三态门，用于控制移位器与总线之间数据通路的连接与断开。 【评分说明】只要回答出三态门或者控制连接/断开，即给分。 4）端口①、②、③、⑤、⑧须连接到控制部件输出端。

【评分说明】答案包含④、⑥、⑦、⑨中任意一个，不给分；答案不全酌情给分。 5）连线1，⑥→⑨；连线2，⑦→④。

【评分说明】回答除上述连线以外的其他连线，酌情给分。

6）因为每条指令的长度为16 位，按字节编址，所以每条指令占用2 个内存单元，顺序执行时，下条指令地址为(PC)+2。MUX 的一个输入端为2，可便于执行(PC)+2 操作。

44．解答：

1）指令操作码有7 位，因此最多可定义27=128 条指令。 2）各条指令的机器代码分别如下：

·10·

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2015年408真题及答案(2)在线全文阅读。