2018年武汉工程大学计算机科学与工程学院835数据结构之数据结构教程考研强化五套模拟题
● 摘要
一、单项选择题
1． 已知一算术表达式的中缀表达式为a ﹣(b＋c/d)*e，其后缀形式为（ ）。 A.
B.
C.
D.
【答案】D
【解析】后缀表达式:在程序语言中，运算符位于两个操作数后面的表达式。
2． 下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写, 只有选项D 中的英文缩写均为总线标准。
3． 假定编译器规定int 和short 类型长度分别为32位和16位, 执行下列C 语言语句:
;
A.00007FFAH
B.0000FFFAH
C.FFFF7FFAH
D.FFFFFFFAH
【答案】B 。
X 和y 均为无符号数, 其中X 为16位, y 为32位, 将16位无符号数转化成32位无符【解析】
号数, 前面要补零。因为X=65530=FFFAH, 所以y=0000FFFAH。
4． 系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。
A.2
B.3
C.4
:得到y 的机器数为（ ）。
D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:
访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。
二、综合题
5． 下列关于堆(Heap)的一些问题:
(1)堆的存储表示是顺序的还是链接的？
(2)设有一个最小堆，即堆中任意结点的关键码均不大于它的左子女和右子女的关键码。其具有最大值的元素可能在什么地方？
(3)对n 个元素进行初始建堆的过程中，最多做多少次数据比较(不用大O 表示法) ？
【答案】(1)堆的存储是顺序的。
(2)最大值元素一定是叶结点，在最下两层上。
(3)在建含有n 个元素、深度为h 的堆时，其比较次数不超过4n ，推导如下:
由于第i 层上的结点数至多是，以它为根的二叉树的深度为h －i+1，则调用次筛选算法时总共进行的关键字比较次数不超过下式之值:
6． 某计算机字长16位，主存地址空间大小为128KB ，按字编址，采用单字长指令格式，指令各字段定义如下:
源操作数 目的操作数
转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下:
注:(X)表示存储器地址X 或寄存器X 的内容. 请回答下列问题:
(1)该指令系统最多可有多少条指令? 该计算机最多有多少个通用寄存器? 存储器地址寄存器(MAR)和存储器数据寄存器(MDR)至少各需要多少位？
(2)转移指令的目标地址范围是多少？
(3)若操作码0010B 表示加法操作(助记符为add) ，寄存器R4和R5的编号分别为100B 和101B ，R4的内容为1234H ，R5的内容为5678H ，地址1234H 的内容为5678H ，地址5678H 中的内容为1234H ，则汇编语句“add(R4)，(R5)+”(逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么(十六进制表示）？该指令执行后，哪些寄存器和存储单元的内容会改变? 改变后的内容是什么？
【答案】(1)指令操作码占4位，则指令系统最多可有
量为128KB ，计算机字长为16位，故主存有
需16位.
(2)由于寄存器字长为16位，所以转移指令的目标地址范围为0000H 〜FFFFH..
(3)汇编语句add(R4)，(R5)+对应的机器码为O010001100010101B ＝2315H ，该指令执行后，寄存器R5和地址为5678H 的存储单元的内容会改变，改变后的内容分别为:
(ACC)＝((R4))+((R5))＝5678H+1234H＝68ACH(R5)＝
(R5)+1＝5678H+1＝5679H
(1234H)＝(ACC)＝68ACH
7． 某主机的MAC 地址为, :IP 地址为(私有地址) 。图a 是网络拓扑, 条不同的指令；指令操作上占6个通用寄存器；主存容个存储单元，故MDR 和MAR 至少各位，寻址方式占3位，于是寄存器编号占3位，该计算机最多可以有图b 是该主机进行Web 请求的1个以太网数据帧前80个字节的十六进制及ASC Ⅱ码内容。
图a 网络拓扑
图b 以太网数据帧(前80字节)
请参考图中的数据回答以下问题。
(1)Web服务器的IP 地址是什么? 该主机的默认网关的MAC 地址是什么？
(2)该主机在构造图b 的数据帧时, 使用什么协议确定目的MAC 地址? 封装该协议请求报文的以太网帧的目的MAC 地址是什么？
(3)假设协议以持续的非流水线方式工作, 以此请求一响应时间为页面引用了5个JPEG 小图像,