2017年电子科技大学自动化工程学院820计算机专业基础之数据结构考研题库
● 摘要
一、选择题
1． 对于栈操作数据的原则是（ ）。
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
2． 可以用（ ）定义一个完整的数据结构。
A. 数据元素 B. 数据对象 C. 数据关系 D 抽象数据类型 【答案】D
【解析】抽象数据类型可以定义一个完整的数据结构。包括数据元素，数据元素之间的关系，以及可以进行的操作。
3． 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
A. 插入 B. 选择 C. 希尔 D. 二路归并 【答案】A
【解析】解此题需要熟知各种排序方法的基本思想。插入排序的基本思想是：假设待排序的
记录存放在数组
中，排序过程的某一中间时刻，R
被划分成两个子区间
插入到有序区
和
其中：前一个子区间是已排好序的有序区，后一个子区间则是当前未排序的部分，不妨
称其为无序区。将当前无序区的第1
个记录
第 2 页，共 50 页
中适当的位置上。使
变为新的有序区。这种方法通常称为增量法，因为它每次使有序区增加1个记录。
4． 某计算机主存地址空间大小为256MB , 按字节编址。虚拟地空间大小为4GB ，采用页式存储管理，页面大小为4KB ，TLB （快表）采用全相联映射，有4个页表项，内容如下表所示。
则对虚拟地址03FFF180H 进行虚实地址变换的结果是（ ） A.0153180H B.0035180H C.TLB 缺失 D. 缺页 【答案】A
【解析】虚拟地址为03FFF180H ，其中页号为03FFFH , 页内地址为180H ，根据题目中给出的页表项可知页标记为03FFFH 所对应的页框号为0153H , 页框号与页内地址之和即为物理地址015 3180H。
5． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令 B. 操作数
C. 握手（应答）信号 D. 中断类型号型号 【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
6． 某设备中断请求的相应和处理时间为100m ，每400ns 发出一次中断请求，中断相应所容许的最长延迟时间为50ns , 贝U 在该设备持续工作过程中CPU 用于该设备的百分比至少是（ ）
A.
B.
C.
D. 【答案】B
【解析】每400m 响应一次中断并且用100m 进行处理，所以该设备的百分比为
7． 下列关于中断
A.
中断
时间占用CPU 时间
中断响应容许的延迟时间对此没有影响，属于干扰条件。 方式和DMA 方式比较的叙述中，错误的是（ ）
第 3 页，共 50 页
时间占整个CPU 时间
方式请求的是方式请求的是CPU 处理时间，DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后，中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后
C.
中断D. 中断部设备
【答案】D
【解析】中断处理方式:在与
设备输入每个数据的过程中，由于无需CPU 干预，因而可使CPU
设备并行工作。仅当输完一个数据时，才需CPU 花费极短的时间去做些中断处理。因此中
方式下数据传送通过软件完成，方式下数据传送通过软件完成，DMA 方式下数据方式适用于所有外部设备，方式适用于所有外部设备，DMA 方式仅适用于快速外
传送由硬件完成
断申请使用的是CPU 处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下完成传送。而DMA 方式与之不同。DMA 方式：数据传输的基本单位是数据块，即在CPU 与设备之间，每次传送至少一个数据块，DMA 方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的或者相反；仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
8． 设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，储地址为1，每个元素占一个地址空间，则
A.13 B.33 C.18 D.40
【答案】B
【解析】对于对称矩阵，
的地址为（ ）。
为第一元素，其存
为了节省存储空间，为多个相同的元素只分配一个存储空间。
时，
当
时，
其
对于对称矩阵，元素下表之间的对应关系为：当
中k 相当于地址空间的标号，i 为行号，j 为列号。因为第一个元素存储地址为1，所以最后计算 的k 需要加1。所以
的存储位置为
9． 给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）
A.LRN B.NRL C.RLN
D.RNL
第 4 页，共 50 页
相关内容
相关标签