2017年国防科学技术大学信息系统与管理学院852数据结构考研题库
● 摘要
一、选择题
1． 下列选项中，不能构成折半查找中关键字比较序列的是（ ）。
A.500，200，450，180 B.500，450，200，180 C.180，500，200，450 D.180，200，500，450 【答案】A
【解析】折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A 项错误，第三次比较的关键字为450，说明待查关键字位于200〜450间，所以第四次比较时不会遇到关键字180。
2． 下列有关RAM 和ROM 的叙述中，正确的是（ ）。
I.RAM 是易失性存储器，ROM 是非易失性存储器 II.RAM 和ROM 都采用随机存取方式进行信息访问 III.RAM 和ROM 都可用作Cache IV .RAM 和ROM 都需要进行刷新 A. 仅I 和II B. 仅II 和III C. 仅 I 、II 和IV D. 仅II 、III 和IV 【答案】A
RAM 中的内容断电后即丢失ROM 中的内容断电后不会丢失，，【解析】（易失性）（非易失性），区别在同时RAM 和ROM 都采用随机存取方式（即CPU 对任何一个存储单元的存取时间相同）于RAM 可读可写，ROM 只读不写。而ROM 显然不可用作Cache , 也不需要刷新，所以III 和IV 的叙述都是错误的。
3． 某主机的IP 地址为180.80.77.55, 子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。
A.180.80.76.0 B.180.80.76.255 C.180.80.77.255 D.180.80.79.255 【答案】D 。
【解析】IPv4地址中的特殊地址，直接广播地址，也就是把主机位全部设置为1，这里77的
二进制是01001101, 子网掩码252的二进制是11111100，由此可以看到77的前6位作为子网位，后四位作为主机位，由此可以知道 其广播地址是180.80.01001111.255，也就是180.80.79.255，因此答案是D 。
4． 某计算机的Cache 共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache 组号是（ ）。
A.0 B.2 C.4 D.6
【答案】C
【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K=ImodQ（K 代表Cache 的组号，I 代表主存的块号，Q 代表Cache 的组数）来计算Cache 的组号。由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4, Cache 共有16，故Cache 有8组，按照上面的公式可以计算得到块，采用2路组相联映射方式（即每组2块）Cache 的组号=4mod8=4。
5． 已知有向图G=（V ，E ），其中
G 的拓扑序列是
（ ）。
【答案】A
【解析】设G=（V ，E ）是一个具有n 个顶点的有向图，V 中顶点序列
能被称
，则在序列中顶点Vi 为拓扑序列的条件：若
必须排在顶点Vj 之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
6． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）
A.
B.
C.
D. 【答案】D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
7． —个非空广义表的表尾（ ）。
A. 不能是子表 B. 只能是子表
C. 只能是原子 D. 是原子或子表 【答案】B
【解析】广义表的定义是一个递归定义，当广义表非空时，称第一个元素是它的表头，称其余元素构成的表称为它的表尾。因此一个非空广义表的表尾只能是子表。
8． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A.
B.
C.
D. 【答案】C
9． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。 A.P1, P2, P3, P4 B.P1, P3, P2, P4 C.P1, P4, P3, P2 D 不存在 【答案】D
【解析】典型的死锁避免算法，银行家算法的应用。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到，经过P1, P4的运行以后，可用资源是2, 2，1，而 P2, P3所需资源分别是1，3, 2和1，3，1。所以剩余资源已经不够P2或P3的分配，亦即找不到能够安全运行的序 列，因此此时是处于不安全状态，所以不存在这样的安全序列。