2018年中南林业科技大学计算机与信息工程学院802C语言与数据结构之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一元素，其存储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。
A.13
B.33
C.18
D.40
【答案】B
【解析】对于对称矩阵，为了节省存储空间，为多个相同的元素只分配一个存储空间。对于对称矩阵，元素下表之间的对应关系为:当i ＞＝j 时，k ＝i(i﹣l)/2＋j ﹣l ；当i ＜＝j 时，k ＝j(j﹣l)/2＋i ﹣l 。其中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算的k 需要加1。所以a 85的存储位置为8*(8﹣1)/2＋5＝33。
2． 下面关于哈希(Hash，杂凑) 查找的说法正确的是（ ）。
A. 哈希函数构造的越复杂越好，因为这样随机性好，冲突小
B. 除留余数法是所有哈希函数中最好的
C. 不存在特别好与坏的哈希函数，要视情况而定
D. 若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单地将该元素删去即可
【答案】C
【解析】若数据结构中存在关键字和K 值相等的记录，则必定在f(K)的存储位置上，由此，不需要进行比较便可直接取得所查记录。在此，称这个对应关系f 为哈希(Hash)函数，哈希函数的选择要视具体情况而定。
3． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A.
B.O(1)
C.O(n) D.
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为O(1)。
4． 对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
5． 设系统缓冲区和用户工作均采单, 从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90(如下图所示) 。进程从外设读入并分析2个数据块的最短时间是（ ）
图
A.200
B.295
C.300
D.390
【答案】C
【解析】数据块1从外设到用户工作区的总时间为105, 在这段时间中数据块2没有进行操作。在数据块1进行分析处理时, 数据块2从外设到用户工作区的总时间为105, 这段时间是并行的。再加上数据块2进行处理的时间90, 总共是300, 故答案为C 。
6． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP 地址
D. 根据IP 地址查询域名
【答案】A 。
【解析】ARP 协议是网络层协议, 因此只能和传输层和数据链路层有关系, 从这一点出发, 域名是应用层的范畴, 选项C 和D 是不正确的, 根据MAC 地址查询IP 地址是RARP 协议的功能, 因此进而得出正确答案是A 。
7． 某计算机有五级中断
的顺序为
A.11110
B.01101
C.00011
D.01010
【答案】D , 则, 中断屏蔽字为表示对级中断进行
屏蔽。若中断响应优先级从高到低的顺序是, 且要求中断处理优先级从高到低的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。【解析】由于L 2的中断处理优先级下降, 屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放, 所以相应位应该为“0”, 即为01010。
8． 对于100Mbps 的以太网交换机, 当输出端口无排队直通(
太网帧(不包括前导码) 时, 引入的转发延迟至少是（ ） A. B. C. D.
【答案】B
【解析】直通交换方式是指以太网交换机可以在各端口间交换数据。它在输入端口检测到一个数据包时, 检查该包的包头, 获取包的目的地址, 启动内部的动态查找表转换成相应的输出端口, 在输入与输出交叉处接通, 把数据包直通到相应的端口, 实现交换功能。通常情况下, 直通交换方式只检查数据包的包头即前14个字节, 由于不需要考虑前导码, 只需要检测目的地址的6B , 所以最短的传输延迟是。
9． 假定一台计算机的显示存储器用DRAM 芯片实现, 若要求显示分辨率为1600x1200, 颜色深度
为24位, 帧频为85Hz , 显存总带宽的50%用来刷新屏幕, 则需要的显存总带宽至少约为（ ）。
A.245Mbps
B.979Mbps
C.1958Mbps
D.7834Mbps
【答案】D
【解析】显存的容量＝分辨率×色深，带宽＝分辨率×色深×帧频，考虑到的时间用来刷新屏幕，故显存总带宽应加倍. 所以需要的显存总带宽至少约为:1600×l200×24×85×2＝7834Mbps.
10．假设某计算机按字编址, Cache 有4个行, Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空, 采用2路组相联映射方式和LRU 替换算法, 当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4, 8时, 命中Cache 的次数是（ ）。
A.1
B.2
C.3
D.4
) 方式转发一个以