2016年大连海事大学航海学院Z01数据结构复试笔试仿真模拟题
● 摘要
一、选择题
1． 已知广义表
用
【答案】C 【解析】
操作就是得到广义表中第一个的原子。
得
到得到e 。
2． 在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。
A. 顶点V 的度 B. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数 【答案】B
【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。
3． 操作系统的子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（ ）。
A. 用户级B. 用户级C. 用户级D. 用户级【答案】A 。
【解析】对于一次设备的调用，操作系统为用户准备了系统调用的接口，当用户使用设备时，首先在用户程序中发起一次系统调用，操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理，根据调用格式和形参，再转到相应的设备驱动程序去处理；大部分设备在运行时是需要时间的，所以设备驱动程序会以中断方式驱动设备，即设置好控制寄存器参数和中断向量等参数后阻塞自己；当设备准备好或所需数据到达后设备硬件发出中断，设备驱动程序唤醒，将数据按上述调用顺序逆向回传到用户程序中，或继续驱动设备执行下一条指令。 因此，
软件从
上到下分为四个层次：用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。
4． 下列给出的指令系统特点中，有利于实现指令流水线的是（ ）。
I. 指令格式规整且长度一致 II. 指令和数据按边界对齐存放
和数取出LS 中原子e 的运算是（ ）。
操作就是得到除第一个原子外剩下元得
到
得
到
素构成的表
。
软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序
III. 只有Load / Store指令才能对操作数进行存储访问 A. 仅B. 仅C. 仅 D.
【答案】D
【解析】特点I 和III 都是RISC 机的特征，而特点II 则有利于指令和数据的存放，所以以上三个特点都有利于实现指令流水线。
5． 设哈希表
长哈希函
数
再哈希法解决冲突，关键字为49的结点的地址是（ ）。
【答案】D
【解析】15，38，61，84用哈希函数为5，发生冲突，用二次探测再散列法解决冲突：
仍然发生冲突。
仍然发生冲突。
不再发生冲突。
6． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 【答案】D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
7． 串的长度是指（ ）。
A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 【答案】B
【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。
计算后得地址：4，5，6，7。49计算后
表中已有4个结点
：其余地址为空，如用二次探测
8． 现有容量为10GB 的磁盘分区，磁盘空间以簇（cluster ）为单位进行分配，簇的大小为4KB , 若采用位图法管理该分区的空闲空间，即用一位（bit ）标识一个簇是否被分配，则存放该位图所需簇的个数为（ ）
A.80 B.320 C.80K D.320K 【答案】A
【解析】磁盘的簇的个数为：
而一个簇的位示图能管理的簇的个数为：
个
所以需要簇的个数为
9． 某计算机的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。
10．下列有关接口的叙述中错误的是：（ ）
A. 状态端口和控制端口可以合用同一寄存器 B.
接口中CPU 可访问寄存器，称为
端口
端口
指令，
C. 采用独立编址方式时，【答案】D
【解析】采用统一编码方式，存储器和任何对存储器数据进行操作的指令都可用于
端口共用统一的地址空间，不需要专用的端口的数据操作。所以D 错误
端口地址和主存地址可能相同
D. 采用统一编址方式时，CPU 不能用访存指令访问
二、填空题
11．设单链表的结点结构为
为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____;
【答案】
相关内容
相关标签