问答题证明：对有向图的顶点适当地编号，可使其邻接矩阵为下三角形且主对角线为全O的充要条件是该图为无环图。
问答题线性表(a
1
，a
2
，a
3
，…，a
n
)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为x的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
(3)分别给出算法各部分的时间复杂度。
问答题有一个具有22位地址和32位字长的存储器。问：(1)该存储器能存储多少字节的信息?(2)如果存储器由512K×16位SRAM芯片组成，需要多少片?(3)需要地址多少位作芯片选择?
问答题如下图所示，有一个移动主机，原来的IP地址是160．80．40．20／16，为了移动到其他网络，它将160．80．40．26设置为了本地代理。之后它移动到了179．56．0．0／16的网络中，设置了179．56．0．1为外部代理，并且获得了新的lP地址179．56．78．69。请问：(1)如果这时候该主机和其他主机通信，对端需要把数据发给什么地址?(2)当一个160．80．40．20到达160．80．0．0／16网络后，会有主机响应该ARP请求吗?(3)本地代理需要将发送给移动主机的分组发送到哪个地址?
问答题给出折半查找的递归算法，并给出算法时间复杂度分析。
问答题CPU执行一段程序时，Cache完成存取的次数为5 000次，主存完成存取的次数为200次。已知Cache存取周期为40 ns，主存储取周期为160 ns。求： (1)Cache的命中率H。 (2)Cache-主存系统的访问效率e。 (3)平均访问时间T。
问答题判断下列序列是否为堆，若不是堆，则把它们调整为堆。 (1) (100，85，95，75，80，60，82，40，20，10，65) (2) (100，95，85，82，80，75，65，60，40，20，10) (3) (100，85，40，75，80，60，65，95，82，10，20) (4) (10，20，40，60，65，75，80，82，85，95，100)
问答题设某处理器具有五段指令流水线：IF(取指令)、ID(指令译码及取操作数)、EXE(ALU执行)、MEM(存储器访问)和WB(结果寄存器写回)。现由该处理器执行如下的指令序列：
(a)SUB R2，R1，R3；R
2
←R
1
－R
3
(b)ADD R12，R2，R5；R
12
←R
2
+R
5
(c)OR R13，R6，R2；R
13
←R
6
or R
2
(d)AND R14，R5，R2；R
14
←R
5
and R
2
(e)ADD R15，R3，R2；R
15
←R
3
+R
2
问：
(1)如果不对这些指令之间的数据相关性进行特殊处理而允许这些指令进入流水线，哪些指令将从未准备好数据的R2寄存器取到错误的操作数?
(2)假定采用将相关指令延迟到所需操作数被写回寄存器堆时执行的方式解决数据相关问题，那么处理器执行这五条指令需要占用多少时钟周期?
问答题某机字长32位，控制器采用微程序控制方式，微指令字长32位，采用水平型直接控制与字段编码控制相结合的微指令格式，共有微命令40个，其中10个微命令采用直接控制方式，30个微命令采用字段编码控制方式，共构成4个相斥类(各包含7个、15个、3个、5个微命令)。可测试的外部条件有4个(CF，ZF，SF，OF)。要求：(1)设计该微指令的具体格式。(2)控制存储器容量是多少?(3)画出微程序控制器的结构框图。
问答题在一个采用分页式虚拟存储管理的系统中，有一用户作业，它依次要访问的字地址序列是115，228，120，88，446，102，321，432，260，167。若分配给作业可使用的主存空间共300个字，作业的页面大小为100个字，且第0页已经装入主存，请回答下列问题： (1)按FIFO页面调度算法将产生多少次缺页中断?写出依次淘汰的页号。 (2)按LRU页面调度算法将产生多少次缺页中断?写出依次淘汰的页号。
问答题为什么要引入虚拟存储器的概念?
问答题双符号位的作用是什么?它只出现在什么部件中?
问答题图2．3是5位×5位不带符号的阵列乘法器逻辑电路图，其中FA是一位全加器。FA的斜线方向为进位输出，竖线方向为求和输出。虚线所围的最下面一行构成了一个行波进位加法器。试求该乘法器总的乘法时间。
问答题协议与服务有何区别?
问答题已知32位寄存器中存放的变量x的机器码为C0000004H，请问： (1)当x是无符号整数时，x的真值是多少?x/2的真值是多少?x/2存放在R1中的机器码是什么?2x的真值是多少?2x存放在R1中的机器码是什么? (2)当x是带符号整数(补码)时，x的真值是多少?x／2的真值是多少?．x／2存放在R1中的机器码是什么?2x的真值是多少?2x存放在R1中的机器码是什么?
问答题某I／O系统有四个设备：磁盘(传输速率为500000位／秒)、磁带(200000位／秒)、打印机(2000位／秒)、CRT、(1000位／秒)，试用中断方式、DMA方式组织此I／O系统。画出包括CPU部分总线控制器在内的I／O方式示意图，并略作文字说明。
问答题用快表(页表)的虚实地址转换条件，快表放在相联存储器中，其容量为8个存储单元，问：(1)当CPU按虚地址1去访问主存时主存的实地址码是多少?(2)当CPU按虚地址2去访问主存时主存的实地址码是多少?(3)当CPU按虚地址3去访问主存时主存的实地址码是多少?
问答题一盘组共11片，记录面为20面，每面上外道直径为14英寸，内道直径为10英寸，分203道。数据传输率为983040字节／秒，磁盘组转速为3600转／分。假定每个记录块记录1024字节，且系统可挂多达16台这样的磁盘，请设计适当的磁盘地址格式，并计算总存储容量。
问答题一个完整的计算机网络的定义应包含哪些内容?
问答题简述预防死锁的办法。