2017年烟台大学计算机与控制工程学院846数据结构考研题库
● 摘要
一、选择题
1． 下列选项中，在
I.
A. 仅 I 、II B. 仅 I 、III C. 仅 II 、III D.I 、II 、III 【答案】D 。 【解析】
在
总线的数据线上传输的信息包括
接口中的命令字、状态字以及真正的数
据，而中断类型号也是通过数据线传输的。
2． 程序段
其中n 为正整数，则最后一行的语句最坏情况下的时间复杂度是（ ）。
【答案】D
【解析】这个是冒泡排序，最坏的情况下需要进行次交换，即时间复杂度是
3． 若元素a ，b , c, d, e，f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。
A.d ，c ，e ，b ，f ，a B.c ，b ，d ，a ，e ，f C.b ，c ，a ，e ，f ，d D.a ，f ，e ，d ，c ，b
【答案】D
【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A.Push , Push , Push ，Push , Pop, Pop, Push，Pop , Pop, Push , Pop ，Pop 选项B.Push , Push , Push , Pop , Pop , Push, Pop, Pop, Push, Pop , Push, Pop 选项C.Push , Push , Pop , Push , Pop , Pop, Push, Push, Pop, Push , Pop , Pop 选项D.Push , Pop , Push, Push , Push , Push, Push, Pop, Pop，Pop , Pop , Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D 所给序列为不可能得到的出栈顺序。
第 2 页，共 55 页
总线的数据线上传输的信息包括（ ）。
接口中的状态字III. 中断类型号
接口中的命令字
II.
4． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，放于
中，那么第i 行的对角元素【答案】A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存放于B 中（ ）处。
存
存放的位置为
5． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 【答案】D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
6． 站点A 、B 、C 通过CDMA 共享链路，A 、B 、C 的码片序列（chipping sequence
）分别是
和
C 收到A 发送的数据是（ ）
A.000 B.101 C.110 D.111
【答案】B
【解析】用A 的码片与信息做内积运算
7． 下列关于中断方式和DMA 方式比较的叙述中，错误的是（ ）
A.
中断
方式请求的是方式请求的是CPU 处理时间，DMA 方式请求的是总线使用权
B. 中断响应发生在一条指令执行结束后，中断响应发生在一条指令执行结束后，DMA 响应发生在一个总线事务完成后
C.
中断D. 中断部设备
【答案】D
【解析】中断处理方式:在与
设备输入每个数据的过程中，由于无需CPU 干预，因而可使CPU
设备并行工作。仅当输完一个数据时，才需CPU 花费极短的时间去做些中断处理。因此中
第 3 页，共 55 页
若C 从链路上收到的序列是则
方式下数据传送通过软件完成，方式下数据传送通过软件完成，DMA 方式下数据方式适用于所有外部设备，方式适用于所有外部设备，DMA 方式仅适用于快速外
传送由硬件完成
断申请使用的是CPU 处理时间，发生的时间是在一条指令执行结束之后，数据是在软件的控制下
完成传送。而DMA 方式与之不同。DMA 方式：数据传输的基本单位是数据块，即在CPU 与设备之间，每次传送至少一个数据块，DMA 方式每次申请的是总线的使用权，所传送的数据是从设备直接送入内存的或者相反；仅在传送一个或多个数据块的开始和结束时，才需 CPU 干预，整块数据的传送是在控制器的控制下完成的。答案D 的说法不正确。
8． 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 直接插入排序 B. 起泡排序 C. 基数排序 D. 快速排序 【答案】C
【解析】C 项，基数排序是采用分配和收集实现的，不需要进行关键字的比较。ABD 三项都依赖关键字的比较，不同的初始排列次序下元素移动的次数有很大变化，最好情况元素正序，则不用移动，最坏情况元素反序，则需要移动n （n-1） /2次（为元素个数）。
9． 下列关于管道（Pipe ）通信的叙述中，正确的是（ ）
A. —个管道可实现双向数据传输 B. 管道的容量仅受磁盘容量大小限制
C. 进程对管道进行读操作和写操作都可以被阻塞 D. —个管道只能有一个读写进程或一个写进程对其操作 【答案】C
【解析】只有写进程才能对管道写入数据，读进程对管道进行读取数据，只能半双工通信，即某一时刻只能单向传输。管道为空，则读操作被堵塞，而如果有写操作对管道进行写的话那就要堵塞了。那么C 正确
10．有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
//取x 到寄存器R1中
两个操作完成后，2的值（ ）。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C
第 4 页，共 55 页
相关内容
相关标签