2018年常州大学艺术学院858数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 系统为某进程分配了4个页框, 该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7, 依据LRU 算法, 应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框, 题中访问过程中页框的变化如下:
访问页号为7的页时, 内存中存在的页的页号是:3、8、4和5, 根据LRU 定义应淘汰的是3。
2． 下列关于IP 路由器功能的描述中, 正确的是（ ）。
Ⅰ. 运行路由协议, 设置路由表; Ⅱ. 监测到拥塞时, 合理丢弃IP 分组;
Ⅲ. 对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失; Ⅳ. 根据收到的IP 分组的目的IP 地址, 将其转发到合适的输出线路上。 A. 仅Ⅲ、Ⅳ B. 仅Ⅰ、Ⅱ、Ⅲ C. 仅Ⅰ、Ⅱ、Ⅳ D. Ⅰ、Ⅱ、Ⅲ、Ⅳ 【答案】C 。
【解析】路由器的主要功能是路由和转发, 因此Ⅰ和Ⅳ是正确的, 而针对Ⅱ和Ⅲ, 可以从ICMP 协议的差错控制出发, 注意检测到拥塞时, 合理丢弃IP 分组, 并回传ICMP 源抑制报文, Ⅱ是正确的, 而Ⅲ对收到的IP 分组头进行差错校验, 确保传输的IP 分组不丢失, 差错校验是正确的, 但网络层不 保证IP 分组不丢失, 也就是不可靠的, 因此Ⅲ的说法错误, 正确的说法仅Ⅰ、Ⅱ、Ⅳ, 因此答案是C 。
3． 设有一个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。
4． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是。若, 则取值的个数是（ ）
A. B. C.
D. 无法确定
【答案】C
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。
5． 浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤. 设浮点数的阶码
7
和尾数均采用补码表示，且位数分别为5位和7位(均含2位符号位). 若有两个数X ＝2×29/32，Y
, 则可能
＝2×5/8，则用浮点加法计算X ＋Y 的最终结果是（ ）.
A.001111100010 B.001110100010 C.010000010001 D. 发生溢出
5
【答案】D
【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步.X 和Y 的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐. 因此将Y 对阶后得到：Y ＝2×5/32，然后将尾数相加，得到尾数之和为：34/32.因为这是两
7
个同号数相加，尾数大于1，则需要右规，阶码加1. 由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在
之间. 而阶码本身等于7，再加1就等于8. 因此，最终结果发生溢出.
6． 有向带权图如下图图所示, 若采用迪杰斯特拉(Dijkstta)算法求从源点a 到其他各顶点的最短路径, 则得到的第一条最短路径的目标顶点是b , 第二条最短路径的目标顶点是c , 后续得到的其佘各最短路径的目标顶点依次是（ ）。
图 有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstta 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。执行Dijkstta 算法过程中各步的状态表, 故后续目标顶点依次为f , d , e 。
7． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，A[0][0]存放于B[0]中，那么第i 行的对角元素A[i][i]存放于B 中（ ）处。
A.(i＋3)*i/2 B.(i＋1)*i/2 C.(2n﹣i ＋l)*i/2 D.(2n﹣i ﹣l)*i/2 【答案】A
【解析】A[i][i]中列标不大于行标，又A[0][0]存放在B[0]中，所以A[i][i]存放的位置为i*(i＋l)/2＋i ＋l ﹣l ＝i*(i＋3)/2。
8． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
A.(100, 80, 90, 60, 120, 110, 130)
相关内容
相关标签