2017年河北大学计算机科学与技术学院893数据结构(含C语言)(计)[专业硕士]考研导师圈点必考题汇编
● 摘要
一、选择题
1． 串是一种特殊的线性表，其特殊性体现在（ ）。
A. 数据元素是一个字符 B. 可以顺序存储
C. 数据元素可以是多个字符D. 可以链接存储 【答案】A
2． 下列选项中，在用户态执行的是（A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 【答案】A
【解析】题目是问用户态执行一能面对的是命令解释程序属于系统调用在核心态执行。只有命令解释程序属于命令接口命令操作控制。
3． 为解决计算机主机与打印机之间速度不匹配问题输出的数据依次写入该缓冲区该是（ ）。
A. 栈 B. 队列 C. 树 D. 图 【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印缓冲区具有先进先出性，则它的逻辑结构应该是队列。
）。
，可见是有关操作系统基本概念的问题。四个选项中，用户唯缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度，可以运行在用户态，接受用户的，通常设置一个打印数据缓冲区，主机将要，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应，栈具有先进后出的特性，因此打印数据
第 2 页，共 50 页
，
4． 由3个“1”和5个“0”组成的8位二进制补码，能表示的最小整数是（ ）。
A.-126 B.-125 C.-32 D.-3
【答案】B
；负数的补码和原码的转化是：【解析】能表示的最小整数一定是负数，符号位占用1个“1”
原码符号位不变，数值部分按位取反，末位加“1”。因此最小的整数的补码是“10000011”，原码为“11111101”，即
5． 要连通具有n 个顶点的有向图，至少需要（ ）条边。
A.n-1 B.n C.n+1 D.2n
【答案】B
【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边成环状的图即可，因此最少需要n 条边。
6． 从堆中删除一个元素的时间复杂度为（ ）。
【答案】B
【解析】堆中删除一个元素，需要重新调整堆，其时间复杂度为
7． 两台主机之间的数据链路层采用后退N 帧协议（GBN ）传输数据，数据传输速率为单向传播时延为270ms ，数据帧长度范围是128〜512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（ ）。
A.5 B.4 C.3 D.237
【答案】B 。
【解析】GBN 的工作原理如下图所示，本题求解的是发送一个帧到接收到这个帧的确认期间最多可以发送多少数据帧，要尽可能多发送帧，应以短的数据帧计算，注意帧的单位是字节此首先计算出发送一帧的时间
故发送一帧到收到确认为止的总时间为
这段时间总共可以发送
（帧）
，为了保证发送帧序号和确认帧序号在此期间不重复，因此帧序号的比特数至少为4, 答案为B
第 3 页，共 50 页
，需让其构16kbps ，，因
，
8． 设有一个n 行n 列的对称矩阵A ，将其下三角部分按行存放在一个一维数组B 中，存
放于
中，那么第i 行的对角元素存放于B 中（ ）处。
【答案】A
【解析】
中列标不大于行标，
又
存放在
中，
所以
存放的位置为
9． 就平均性能而言，目前最好的内排序方法是（ ）排序法。
A. 起泡 B. 希尔插入 C. 交换 D. 快速 【答案】D
【解析】快速排序的平均时间复杂度是所需要的辅助存储为虽然堆排序的时间
复杂度也是
所需要的辅助存储为
看似堆排序比快速排序的性能好，
但是需要注意
仅仅表示的是一个量级，
比如
和
的量级都为
之所以说快排
最好，是在综合考虑的情况下。
10．某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）
A.9 B.10 C.11 D.12
【答案】B
【解析】2+3+4+1 = 10
二、判断题
11．KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）
【答案】
【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息第 4 页，共 50 页
，
相关内容
相关标签