1、考研计算机学科专业基础综合-1-1 及答案解析(总分：128.02，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.以下叙述不正确的是( )。（分数：2.00）A.后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B.任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈C.任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D.任何一棵二叉树都可以不用栈实现中序线索树的中序遍历2.路由器采用( )方式来发送 IP 分组。（分数：2.00）A.存储转发机制B.直通交换机制C.分组交换机制D.分组检测机制3.我们把一段时间内，只允许一个进程访问的资源，称为临界资源，
2、因此，我们可以得出以下论述，请选择一条正确的论述( )。（分数：2.00）A.对临界资源是不能实现资源共享的B.对临界资源，应采取互斥访问方式，来实现共享C.为临界资源配上相应的设备控制块后，便能被共享D.对临界资源应采取同时访问方式，来实现共享4.下列关于加法器的说法错误的是( )。（分数：2.00）A.实现 n 位的串行加法器只需 1 位全加器B.实现 n 位的并行加法器需要 n 位全加器C.影响并行加法器速度的关键因素是加法器的位数的多少D.加法器是一种组合逻辑电路5.一个 ATM 网络的源端点和目的端点之间有三个 ATM 交换机，现在要建立一条虚电路，一共需要发送( )个报文。（分数：
3、2.00）A.12B.15C.18D.216.假定系统拥有某类资源 10 个。在该系统上运行的所有作业，其对该类资源的需求量不会超过 2 个。为了提高资源利用率，我们打算对这种资源采用动态分配，但用限制系统中并发执行的作业数来防止发生死锁。你认为作业调度允许并发执行的最大作业数应是( )。（分数：2.00）A.1B.8C.9D.107.假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失(未命中)50 次，则 Cache 的命中率是( )。（分数：2.00）A.5%B.9.5%C.50%D.95%8.将 5 个字母“ooops“按此顺
4、序入栈，则有( )种不同的出栈顺序可以仍然得到“ooops”。（分数：2.00）A.1B.3C.5D.69.计算机操作系统中，若 WAIT、SIGNAL 操作的信号量 S 初值为 3，当前值为-2，则表示当前有( )个等待信号量 S 的进程。（分数：2.00）A.1B.2C.3D.010.指令流水线中出现数据相关时流水线将受阻，( )可解决数据相关问题。（分数：2.00）A.增加硬件资源B.采用旁路技术C.采用分支预测技术D.以上都可以11.分时系统中，为使多个用户能够同时与系统交互，最关键的问题是( )。（分数：2.00）A.计算机具有足够的运行速度B.内存容量应足够大C.系统能及时地接收多
5、个用户输入D.能在一短的时间内，使所有用户程序都能运行12.堆栈(软堆栈)寻址的寻址方式可看作是( )。（分数：2.00）A.寄存器寻址B.寄存器间接寻址C.基址寻址D.直接寻址13.假定有一条通带为 100kHz 的信道，每路信号的带宽为 3.2kHz，各路信号间的防护带宽为 0.8kHz。若采用频分多路复用，那么最多可以同时传输( )路信号。（分数：2.00）A.10 路B.20 路C.25 路D.40 路14.在散列表中，当装填因子非常接近 1 时，线性探测类似于( )查找（分数：2.00）A.二分B.随机C.顺序D.分块15.关于 DMA 方式和通道方式，下列说法中错误的是( )。（分
6、数：2.00）A.DMA 的数据传送全部由硬件控制，而通道方式通过执行通道程序来传送数据B.一个 DMA 控制器连接多台外设时，这些外设只能串行工作C.一个通道可连接多台外设，且可使这些外设并行工作D.DMA 控制器和通道都可以连接各种高低速设备16.驱动调度算法中，( )算法可能会随时改变移动臂的运动方向。（分数：2.00）A.电梯调度B.最短寻找时间优先C.扫描D.单向扫描17.下列四种存储器中，存取速度最快的是( )。（分数：2.00）A.DRAMB.SRAMC.掩模式 ROMD.EPROM18.如果一棵完全二叉树共有 26 个结点，则必定有( )个结点的度为 1。（分数：2.00）A.
7、0B.1C.3D.1319.有关设备管理概念的下列叙述中，( )是不正确的。（分数：2.00）A.通道是处理输入、输出的软件B.所有外围设备的启动工作都由系统统一来做C.来自通道的 I/O 中断时间由设备管理负责处理D.编制好的通道程序是存放在主存储器中的20.虚拟存储管理系统的基于程序的局部性理论，( )是指最近被访问的存储单元可能马上被访问。（分数：2.00）A.数据局部性B.空间局部性C.时间局部性D.空间全局性21.下列设备中，可以分割广播域的是( )。（分数：2.00）A.集线器B.网桥C.以太网交换机D.路由器22.设有关键字序列 F=Q，G，M，Z，A，N，P，X，H，下面( )
8、序列是从上述序列出发建堆的结果。（分数：2.00）A.A，G，H，M，N，P，Q，X，ZB.A，G，M，H，Q，N，P，X，ZC.G，M，Q，A，N，P，X，H，ZD.H，G，M，P，A，N，Q，X，Z23.对于一个文件的访问，常由( )共同限制。（分数：2.00）A.用户访问权限和文件属性B.用户访问权限和用户优先级C.优先级和文件属性D.文件属性和口令24.若数据元素序列 11，12，13，7，8，923，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。（分数：2.00）A.起泡排序B.插入排序C.选择排序D.二路归并排序25.设某进程的访问串为 1、3、
9、1、2、4，驻留集为 3 块，当访问 4 号页面时，按 LRU 页面替换算法，应淘汰( )号页面。（分数：2.00）A.1B.2C.3D.426.下列关于一地址指令的说法正确的是( )。（分数：2.00）A.可能是数据传送指令B.可能是实现单目运算的运算指令C.可能是实现双目运算的运算指令D.以上都有可能27.某 2561 位的存储芯片内部结构为 1616 的存储元矩阵，且采用“重合法”的译码驱动方式来选择存储元，则该芯片引脚中地址线的数目为( )。（分数：2.00）A.256B.32C.16D.828.使用海明码来检出并纠正一位错，当有效代码长度为 8 位时，至少需要( )位校验位。（分数：
10、2.00）A.3B.4C.5D.629.一个 UDP 用户的数据报的数据部分长为 8192 字节。那么通过以太网来传播该 UDP 数据报时，最后一个IP 分片的数据长度是( )。（分数：2.00）A.1500B.1480C.800D.60030.文件系统的主要目的是( )。（分数：2.00）A.实现对文件的按名存取B.实现虚拟存储器C.提高外围设备的输入输出速度D.用于存储系统文档31.CPU 的工作周期为 20ns，主存存取周期为 10ns，此时 DMA 接口适合采用( )方式与 CPU 共享主存。（分数：2.00）A.停止 CPU 访问主存B.周期挪用C.DMA 与 CPU 交替访存D.以
11、上无正确选项32.高度为 7 的 AVL 树最少有( )个结点。（分数：2.00）A.31B.32C.33D.3433.在使用浏览器打开某个网页时，用户输入网址后，浏览器首先要进行( )。（分数：2.00）A.域名到 IP 地址的解析B.和服务器建立 TCP 连接C.发送 UDP 分组到服务器D.发出 GET 的 HTTP 命令来获得网页内容34.设 CPU 与 I/O 设备以中断方式进行数据传送，CPU 响应中断时，该 I/O 设备接口控制器送给 CPU 的中断向量表(中断向量表存放中断向量)指针是 0800H，0800H 单元中的值为 1200H。则该 I/O 设备的中断服务程序在主存中的
12、入口地址为( )。（分数：2.00）A.0800HB.0801HC.1200HD.1201H35.为了使数据在网络中的传输延迟最小，首选的交换方式是( )。（分数：2.00）A.电路交换B.报文交换C.分组交换D.信元交换36.关于基址寻址和变址寻址，下列说法中错误的是( )。（分数：2.00）A.两者都可扩大指令的寻址范围B.两者在取操作数之前都需要对有效地址进行计算C.在程序执行过程中，基址寄存器的内容不可变，变址寄存器中的内容可变D.基址寄存器和变址寄存器的内容都由用户确定37.TCP 是采用( )来控制流量的。（分数：2.00）A.设定拥塞窗口B.TCP 首部中的接收窗口C.设定拥塞阀
13、值D.通过标志位来通知38.设有 10 阶矩阵 A，其对角线以上的元素 aij(1j10，1ij)均取值为-3，其他矩阵元素为正整数，现将矩阵 A 压缩存储放在一维数组 Fm中，则 m 为( )。（分数：2.00）A.45B.46C.55D.5639.如右图所示的有向图 G 的深度优先搜索得到的结点序列是( )。（分数：2.00）A.a b c f d e gB.a b c g f d eC.a b c d e f gD.a b c f g d e40.一棵二叉树的后序遍历序列为 DABEC，中序遍历序列为 DEBAC，则先序遍历序列为( )。（分数：2.00）A.ACBEDB.DECABC.
14、DEABCD.CEDBA二、B综合应用题/B(总题数：5，分数：48.00)设一段正文由字符集A，B，C，D，E，F中的字母组成，这 6 个字母在正文中出现的次数分别为12，18，26，6，4，34。（分数：10.00）(1).为这 6 个编码设计哈夫曼编码。（分数：2.50）_(2).设每个字节由 8 位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字节。（分数：2.50）_(3).若这段正文开始部分的二进制编码序列为：0110001001011010100，请按 1 的哈夫曼编码将其译为正文。（分数：2.50）_一个由高速缓冲存储器 Cache 与主存储器组成的二级存储系统。已
15、知主存容量为 1MB，按字节编址，缓存容量为 32KB，采用组相联方式进行地址映射与变换，主存与缓存的每一块为 64B，缓存共分 8 组。（分数：10.00）(1).写出主存与缓存的地址格式(标明各字段名称与位数)。（分数：5.00）_(2).假定 Cache 的存取周期为 20s，命中率为 0.95，希望采用 Cache 后的加速比大于 10。那么主存储器的存取速度应大于多少(访存时 CPU 同时访问 Cache 和主存，如 Cache 命中则中断主存访问)?（分数：5.00）_指令系统字长 16 位，每个地址码为 6 位，采用扩展操作码的方式，试设计 14 条二地址指令。100 条一地址指
16、令，100 条零地址指令。（分数：11.01）(1).画出操作码的扩展形式。（分数：3.67）_(2).下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的译码逻辑。 （分数：3.67）_(3).计算操作码的平均长度。（分数：3.67）_假定在一个处理机上执行的操作如下： 这些作业假定按 A、B、C、D、E 次序先后几乎同时(时间差相对时间片大小忽略不计)到达。（分数：8.01）(1).给定相应的图示来说明分别用 FCFS、RR(时间片=1)、SJF 和非抢占优先调度算法(最小优先数有最高优先权)调度这些作业的情况。（分数：2.67）_(2).分别给出采用上述
17、调度算法时每个作业的周转时间和平均周转时间。（分数：2.67）_一个客户机利用 FTP 协议从服务器上下载文件，如下图所示为整个过程中协议交换的过程，请回答如下问题：（分数：9.00）(1).该协议层图中第四层协议是什么?（分数：2.25）_(2).如果 FTP 客户端采用了 LIST 命令来获得 FTP 服务器上的文件列表，该列表采用什么端口传输?（分数：2.25）_(3).如果一个 TCP 数据包的数据部分长度为 5000 字节，那么在 IP 层需要分片吗?（分数：2.25）_(4).如果需要分片请说明需要分成几片，每片长度为多少?如果不需要分片，请说明原因。 （分数：2.25）_考研计算
18、机学科专业基础综合-1-1 答案解析(总分：128.02，做题时间：90 分钟)一、B单项选择题/B(总题数：40，分数：80.00)1.以下叙述不正确的是( )。（分数：2.00）A.后序线索二叉树是不完善的，要对它进行遍历，不需使用栈B.任何一棵二叉树的后序线索树进行后序遍历时都必须使用栈 C.任何一棵二叉树都可以不用栈实现先序线索树的先序遍历D.任何一棵二叉树都可以不用栈实现中序线索树的中序遍历解析：不需要使用栈。2.路由器采用( )方式来发送 IP 分组。（分数：2.00）A.存储转发机制 B.直通交换机制C.分组交换机制D.分组检测机制解析：路由器在向输出链路传输分组的第一个比特之前
19、，必须先接收整个分组，这种方式称为存储转发机制。3.我们把一段时间内，只允许一个进程访问的资源，称为临界资源，因此，我们可以得出以下论述，请选择一条正确的论述( )。（分数：2.00）A.对临界资源是不能实现资源共享的B.对临界资源，应采取互斥访问方式，来实现共享 C.为临界资源配上相应的设备控制块后，便能被共享D.对临界资源应采取同时访问方式，来实现共享解析：临界资源是指被多个进程共享的资源，需要互斥访问。4.下列关于加法器的说法错误的是( )。（分数：2.00）A.实现 n 位的串行加法器只需 1 位全加器B.实现 n 位的并行加法器需要 n 位全加器C.影响并行加法器速度的关键因素是加法
20、器的位数的多少 D.加法器是一种组合逻辑电路解析：n 位的并行加法器有 n 位的全加器，可同时对数据的各位相加，但低位运算所产生的进位会影响高位的运算结果，所以并行加法器的运算时间主要由进位信号的传递时间决定，而不是加法器位数的多少，选 C。5.一个 ATM 网络的源端点和目的端点之间有三个 ATM 交换机，现在要建立一条虚电路，一共需要发送( )个报文。（分数：2.00）A.12B.15 C.18D.21解析：让 SETUP 报文到达目的地需要四个跳段，除了最后一个跳段外，每个跳段都要被确认，这样就共有7 个报文。类似地，CONNECT 报文也经历 4 个跳段，并且有 4 个确认，共有 8
21、个报文。这样全部加在一起，总共需要发送 15 个报文。6.假定系统拥有某类资源 10 个。在该系统上运行的所有作业，其对该类资源的需求量不会超过 2 个。为了提高资源利用率，我们打算对这种资源采用动态分配，但用限制系统中并发执行的作业数来防止发生死锁。你认为作业调度允许并发执行的最大作业数应是( )。（分数：2.00）A.1B.8C.9 D.10解析：因为最大需求量不会超过 2 个，所以最大作业数为 9，保证不会死锁。7.假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存 1000 次，其中访问 Cache 缺失(未命中)50 次，则 Cache 的命中率是( )。（分数：
22、2.00）A.5%B.9.5%C.50%D.95% 解析：Cache 的命中率=命中次数/总访存次数=(1000-50)/1000100%=95%。8.将 5 个字母“ooops“按此顺序入栈，则有( )种不同的出栈顺序可以仍然得到“ooops”。（分数：2.00）A.1B.3C.5 D.6解析：9.计算机操作系统中，若 WAIT、SIGNAL 操作的信号量 S 初值为 3，当前值为-2，则表示当前有( )个等待信号量 S 的进程。（分数：2.00）A.1B.2 C.3D.0解析：若信号量为正则表示资源数，若为负则其绝对值表示等待的进程数。10.指令流水线中出现数据相关时流水线将受阻，( )可
23、解决数据相关问题。（分数：2.00）A.增加硬件资源B.采用旁路技术 C.采用分支预测技术D.以上都可以解析：旁路技术指不必等待某条指令的执行结果写回到寄存器后，再从寄存器取出结果，而是直接将执行结果通过专用通路送至需要该结果的地方，可用来解决流水线的数据相关问题。11.分时系统中，为使多个用户能够同时与系统交互，最关键的问题是( )。（分数：2.00）A.计算机具有足够的运行速度B.内存容量应足够大C.系统能及时地接收多个用户输入D.能在一短的时间内，使所有用户程序都能运行 解析：本题考查分时系统的特点。12.堆栈(软堆栈)寻址的寻址方式可看作是( )。（分数：2.00）A.寄存器寻址B.寄
24、存器间接寻址 C.基址寻址D.直接寻址解析：软堆栈是指厢主存空间的一部分实现的堆栈，只可对栈顶进行存取，堆栈指针 SP 本质上是一个寄存器，其中存放着操作数的有效地址，故堆栈寻址可看作是寄存器间接寻址。13.假定有一条通带为 100kHz 的信道，每路信号的带宽为 3.2kHz，各路信号间的防护带宽为 0.8kHz。若采用频分多路复用，那么最多可以同时传输( )路信号。（分数：2.00）A.10 路B.20 路C.25 路 D.40 路解析：频分复用指的是所有用户按同样的时间占用不同的带宽资源所以复用信号的路数为(100103/(3.2+0.8)103=)25 路。14.在散列表中，当装填因子
25、非常接近 1 时，线性探测类似于( )查找（分数：2.00）A.二分B.随机C.顺序 D.分块解析：由于线性探测在关键词同义时解决冲突的办法是线性的向后查找，当整个表几乎装满时，它就很类似于顺序查找了。15.关于 DMA 方式和通道方式，下列说法中错误的是( )。（分数：2.00）A.DMA 的数据传送全部由硬件控制，而通道方式通过执行通道程序来传送数据B.一个 DMA 控制器连接多台外设时，这些外设只能串行工作C.一个通道可连接多台外设，且可使这些外设并行工作D.DMA 控制器和通道都可以连接各种高低速设备 解析：通道可连接各种高低速外设，而 DMA 控制器只用于高速外设成组数据的传送，D
26、为错误选项。16.驱动调度算法中，( )算法可能会随时改变移动臂的运动方向。（分数：2.00）A.电梯调度B.最短寻找时间优先 C.扫描D.单向扫描解析：除了最短寻找时间优先之外的其余三种算法在移动到磁道的尽头前都是单向移动。17.下列四种存储器中，存取速度最快的是( )。（分数：2.00）A.DRAMB.SRAM C.掩模式 ROMD.EPROM解析：由于电容充放电以及刷新需要一定的时间，所以 DRAM 的存取速度比 SRAM 慢；掩模式 ROM 只可读，不可写入；EPROM 采用紫外线照射擦去信息，读写时间比 RAM 长得多。故选 B。18.如果一棵完全二叉树共有 26 个结点，则必定有(
27、 )个结点的度为 1。（分数：2.00）A.0B.1 C.3D.13解析：26 个结点，可知该二叉树有 5 层。由于前 4 层组成一棵满二叉树，共 15 个结点，则共有 11 个叶子结点，可知只有 1 个结点的度为 1。19.有关设备管理概念的下列叙述中，( )是不正确的。（分数：2.00）A.通道是处理输入、输出的软件 B.所有外围设备的启动工作都由系统统一来做C.来自通道的 I/O 中断时间由设备管理负责处理D.编制好的通道程序是存放在主存储器中的解析：通道是一种特殊用途的处理器。是硬件。20.虚拟存储管理系统的基于程序的局部性理论，( )是指最近被访问的存储单元可能马上被访问。（分数：2
28、.00）A.数据局部性B.空间局部性C.时间局部性 D.空间全局性解析：时间局部性是指一段时间内访问的相同的一段存储单元。21.下列设备中，可以分割广播域的是( )。（分数：2.00）A.集线器B.网桥C.以太网交换机D.路由器 解析：路由器是网络层的设备，而广播是网络层的功能，而其他三个项都属于网络层以下的设备，所以都不能分割广播域。22.设有关键字序列 F=Q，G，M，Z，A，N，P，X，H，下面( )序列是从上述序列出发建堆的结果。（分数：2.00）A.A，G，H，M，N，P，Q，X，ZB.A，G，M，H，Q，N，P，X，Z C.G，M，Q，A，N，P，X，H，ZD.H，G，M，P，A，
29、N，Q，X，Z解析：参考堆建立算法。23.对于一个文件的访问，常由( )共同限制。（分数：2.00）A.用户访问权限和文件属性 B.用户访问权限和用户优先级C.优先级和文件属性D.文件属性和口令解析：本题考查文件保护的概念。24.若数据元素序列 11，12，13，7，8，923，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是( )。（分数：2.00）A.起泡排序B.插入排序 C.选择排序D.二路归并排序解析：25.设某进程的访问串为 1、3、1、2、4，驻留集为 3 块，当访问 4 号页面时，按 LRU 页面替换算法，应淘汰( )号页面。（分数：2.00）A.1B.
30、2C.3 D.4解析：根据 LRU 算法规则淘汰 3。26.下列关于一地址指令的说法正确的是( )。（分数：2.00）A.可能是数据传送指令B.可能是实现单目运算的运算指令C.可能是实现双目运算的运算指令D.以上都有可能 解析：一地址指令可能是实现单日运算的运算指令，也可能是数据传送指令或者实现双目运算的运算指令，其中一个操作数由指令地址码给出，另一个操作数为隐含寻址，通常由累加器 AC 提供。27.某 2561 位的存储芯片内部结构为 1616 的存储元矩阵，且采用“重合法”的译码驱动方式来选择存储元，则该芯片引脚中地址线的数目为( )。（分数：2.00）A.256B.32C.16D.8 解
31、析：当采用“重合法”时，存储芯片内行、列各使用 16 根选择线便可选中 1616 矩阵中的任一位；又采用译码器时，4 根地址线即可对应 16 根选择线，故该芯片引脚中地址线数目为 4+4=8。注意，当行地址与列地址分两次传送时，可将芯片引脚中地址线数减少到 4，但题中未给出相关说明，且无对应选项，故选 D。28.使用海明码来检出并纠正一位错，当有效代码长度为 8 位时，至少需要( )位校验位。（分数：2.00）A.3B.4 C.5D.6解析：当使用海明码来检出并纠正一位错时，有效代码位数 n 和校验代码位数 k 应满足 2Kn+k+1；具体计算时，可采用“试凑法”。本题中，有效代码长度为 8，
32、易知校验位至少应大于 3 位，故取 k=4，代入公式，得：24=168+4+1=13，满足要求，故选 B。29.一个 UDP 用户的数据报的数据部分长为 8192 字节。那么通过以太网来传播该 UDP 数据报时，最后一个IP 分片的数据长度是( )。（分数：2.00）A.1500B.1480C.800 D.600解析：UDP 头部长为 8 字节，因此该 UDP 数据报总长度为 8200 字节，以太网帧的最大数据域为 1500，再减去 20 的 IP 头部，得到每个 IP 分片的最大数据域长度应该是 1480，则最后一个数据分片的长度应该是(8200-51480=)800 字节。30.文件系统的
33、主要目的是( )。（分数：2.00）A.实现对文件的按名存取 B.实现虚拟存储器C.提高外围设备的输入输出速度D.用于存储系统文档解析：本题考查文件系统的主要目的。31.CPU 的工作周期为 20ns，主存存取周期为 10ns，此时 DMA 接口适合采用( )方式与 CPU 共享主存。（分数：2.00）A.停止 CPU 访问主存B.周期挪用C.DMA 与 CPU 交替访存 D.以上无正确选项解析：由于 CPU 工作周期为主存周期的 2 倍，故可将其分为两个分周期，其中一个供 DMA 接口访存，另一个供 CPU 访存，即 DMA 与 CPU 交替访存。这样可以在不影响 CPU 效率的前提下充分利
34、用主存带宽。32.高度为 7 的 AVL 树最少有( )个结点。（分数：2.00）A.31B.32C.33 D.34解析：平衡二叉树中含有的最少结点数有如下关系： N0=0 N1=1 Nh=Nh-1+Nh-2+1 所以：N 7=33。33.在使用浏览器打开某个网页时，用户输入网址后，浏览器首先要进行( )。（分数：2.00）A.域名到 IP 地址的解析 B.和服务器建立 TCP 连接C.发送 UDP 分组到服务器D.发出 GET 的 HTTP 命令来获得网页内容解析：首先需要将域名解析成 IP 地址，才能利用 IP 地址来建立 TCP 连接，并进行之后的一系列活动。34.设 CPU 与 I/O
35、 设备以中断方式进行数据传送，CPU 响应中断时，该 I/O 设备接口控制器送给 CPU 的中断向量表(中断向量表存放中断向量)指针是 0800H，0800H 单元中的值为 1200H。则该 I/O 设备的中断服务程序在主存中的入口地址为( )。（分数：2.00）A.0800HB.0801HC.1200H D.1201H解析：中断向量即是中断服务程序的入口地址。35.为了使数据在网络中的传输延迟最小，首选的交换方式是( )。（分数：2.00）A.电路交换 B.报文交换C.分组交换D.信元交换解析：电路交换需要在传输之前建立一个固定的连接，因此其传输的延迟最短。36.关于基址寻址和变址寻址，下列
36、说法中错误的是( )。（分数：2.00）A.两者都可扩大指令的寻址范围B.两者在取操作数之前都需要对有效地址进行计算C.在程序执行过程中，基址寄存器的内容不可变，变址寄存器中的内容可变D.基址寄存器和变址寄存器的内容都由用户确定 解析：基址寄存器常用来实现多道程序，其内容一般由操作系统确定，故 D 选项错误。37.TCP 是采用( )来控制流量的。（分数：2.00）A.设定拥塞窗口B.TCP 首部中的接收窗口 C.设定拥塞阀值D.通过标志位来通知解析：TCP 首部中的接收窗口是用来标识接收方的缓冲能力的，避免快速的发送方淹没慢速的接收方。38.设有 10 阶矩阵 A，其对角线以上的元素 aij
37、(1j10，1ij)均取值为-3，其他矩阵元素为正整数，现将矩阵 A 压缩存储放在一维数组 Fm中，则 m 为( )。（分数：2.00）A.45B.46C.55D.56 解析：考察矩阵压缩存储，由于对角线以下均为-3，不与其他元素重复，可知这 45 个元素只需用一个值来表示，故该矩阵只需用(100-45)+1=56 个元素来表示。39.如右图所示的有向图 G 的深度优先搜索得到的结点序列是( )。（分数：2.00）A.a b c f d e g B.a b c g f d eC.a b c d e f gD.a b c f g d e解析：参考深度优先算法。40.一棵二叉树的后序遍历序列为 D
38、ABEC，中序遍历序列为 DEBAC，则先序遍历序列为( )。（分数：2.00）A.ACBEDB.DECABC.DEABCD.CEDBA 解析：由后序序列必定最后一个访问根结点，故 C 为根结点。在先序遍历中首先访问根结点，故可选 D。二、B综合应用题/B(总题数：5，分数：48.00)设一段正文由字符集A，B，C，D，E，F中的字母组成，这 6 个字母在正文中出现的次数分别为12，18，26，6，4，34。（分数：10.00）(1).为这 6 个编码设计哈夫曼编码。（分数：2.50）_正确答案：()解析：各个字母对应的编码为： A 011 B 00 C 10 D 0101 E 0100 F
39、11(2).设每个字节由 8 位二进制位组成，试计算按哈夫曼编码压缩存储这段正文共需多少个字节。（分数：2.50）_正确答案：()解析：共需字节数为： (2*(18+26+34)+3*12+4*(4+6)/8=232/8=29 x为第一个不小于 x 的整数(3).若这段正文开始部分的二进制编码序列为：0110001001011010100，请按 1 的哈夫曼编码将其译为正文。（分数：2.50）_正确答案：()解析：译文序列为：ABECFDB。 构造哈夫曼树如下图所示：_解析：一个由高速缓冲存储器 Cache 与主存储器组成的二级存储系统。已知主存容量为 1MB，按字节编址，缓存容量为 32KB
40、，采用组相联方式进行地址映射与变换，主存与缓存的每一块为 64B，缓存共分 8 组。（分数：10.00）(1).写出主存与缓存的地址格式(标明各字段名称与位数)。（分数：5.00）_正确答案：()解析：主存按字节编址，块大小为 64B=26B，故字块内地址 6 位；缓冲共分 8(=23)组，故组地址 3 位；Cache 地址格式如下表所示： 组地址(3 位) 字块内地址(6 位)主存容量为 1MB，故主存地址为 20 位，主存地址格式中主存字块标记位数为(20-3-6=)11 位，主存地址格式如下表所示： 主存字块标记(11 位) 组地址(3 位) 字块内地址(6 位)(2).假定 Cache
41、 的存取周期为 20s，命中率为 0.95，希望采用 Cache 后的加速比大于 10。那么主存储器的存取速度应大于多少(访存时 CPU 同时访问 Cache 和主存，如 Cache 命中则中断主存访问)?（分数：5.00）_正确答案：()解析：设主存存取周期为 T，则 Cache主存系统的平均存取时间 T1为 T1=20s0.95+T(1-0.95) 根据题意，希望 Cache 的加速比大于 10，则应满足 T10T 1，代入上式解得， T380s即要求主存储器的存取周期应大于 380s。指令系统字长 16 位，每个地址码为 6 位，采用扩展操作码的方式，试设计 14 条二地址指令。100
42、条一地址指令，100 条零地址指令。（分数：11.01）(1).画出操作码的扩展形式。（分数：3.67）_正确答案：()解析：操作码的扩展形式如下：(2).下图为指令译码逻辑图，其中只给出了二地址指令的译码逻辑，试补全一地址指令和零地址指令的译码逻辑。 （分数：3.67）_正确答案：()解析：补全后的译码逻辑图如下：(3).计算操作码的平均长度。（分数：3.67）_正确答案：()解析：操作码平均长度为 (414+10100+16100)/21412.4假定在一个处理机上执行的操作如下： 这些作业假定按 A、B、C、D、E 次序先后几乎同时(时间差相对时间片大小忽略不计)到达。（分数：8.01）(1).给定相应的图示来说明分别用 FCFS、RR(时间片=1)、SJF 和
