2017年天津城建大学计算机学院815数据结构考研冲刺密押题
● 摘要
一、选择题
1． 假定主存地址为32位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4个字，每字32位，采用回写（WriteBack ）方式，则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k B.147K C.148K D.158K 【答案】B
【解析】Cache 和主存直接映射方式的规则为：主存储器分为若干区，每个区与缓存容量相同；每个区分为若干数据块，每个块和缓存块容量相同；主存中某块只能映象到Cache 的一个特定的块中。本题中，Cache 总共存放4K 字数据，块大小为4个字，因此cache 被分为4K/4 = 1K 个块，由10位表示。块内共16字节，所以由4位表示，于是标记位为32-10-14= 18位。所以，Cache 的每一行需要包含所存的数据4个字，每个字32位，18位标记位和一个有效位，因此总容=147K。 量为：
2． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态（系统态）的是（ ）。
A. B. 产生软中断
D. 【答案】C
【解析】A 项，除法操作出现除数为零的情况时，会产生内中断，CRJ 切换为内核态进行中断处理；B 项，直接产生中断，会切换到内核态；D 项，addr 出现非法地址，会出现中断，进而切换到内核态。
3． —
组记录的关键码为
准得到的一次划分结果为（ ）。
C.NOTRO ；寄存器R0的内容取非
把地址处的内存数据放入寄存器R0中
则利用快速排序的方法，以第一个记录为基
【答案】C
【解析】快速排序是将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分记录的关键字小。
第一次比较：46比84小，不交换； 第二次比较：40比46小，交换，此时为第三次比较：46比79小，交换，此时为第四次比较：38比46小，交换，此时为第五次比较：56比46大，交换，此时为一次划分结束。
4． 下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储 【答案】B
【解析】
空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
5． 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。
A. 打印字符 B. 主存地址 C. 设备状态 D. 控制命令 【答案】B
【解析】I/O接口的功能包括：①选址功能；②传送命令功能；③传送数据功能；④反映I/O设备工作状态功能。A 项为数据，C 项为设备状态，D 项为命令。B 项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU 和打印控制接口中的I/O端口之间交换的信息。
6． 有向带权图如题图所示，若采用迪杰斯特拉（Dijkstra ）算法求从源点a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b ，第二条最短路径的目标顶点是c ，后续得到的其余各最短路径的目标顶点依次是（ ）。
题图有向带权图
A.d , e , f
B.e , d , f C.f , d , e D.f , e , d 【答案】C 。
【解析】本题主要考查Dijkstra 算法的思想和解题步骤。题目执行算法过程中各步的状态如下表所示。
执行Dijkstra 算法过程中各步的状态表，故后续目标顶点依次为f ，d , e 。
7． 设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2, 再建立F1的硬链接文件F3, 然后删除F1。此时，F2和F3的引用计数值分别是（ ）。
A.0、1 B.1、1 C.1、2 D.2、1 【答案】B
【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目（引用计数值），这是共享的一种方法。当新文件建立时，一般默认引用计数值为1。硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1。当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件。软链接又叫符号链接，在新文件中只包含了被链接