《2017年南昌大学信息工程学院894数据结构[专业硕士]考研题库.doc》由会员分享，可在线阅读，更多相关《2017年南昌大学信息工程学院894数据结构[专业硕士]考研题库.doc（3页珍藏版）》请在金锄头文库上搜索。
1、2017年南昌大学信息工程学院894数据结构专业硕士考研题库一、选择题1 下列选项中会导致进程从执行态变为就绪态的事件是（ ）。A. 执行P （wait ）操作 B. 申请内存失败 C. 启动I/O设备 D. 被尚优先级进程抢占 【答案】D【解析】D 项，被高优先级进程抢占，进程会由执行态变为就绪态。ABC 三项，程序由于缺少资源而由执行态转为阻塞态。 2 稀疏矩阵一般的压缩存储方法有两种，即（ ）。A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表 【答案】C【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成
2、一个三元组（行标，列标，值）。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。 3 在有向图的邻接表存储结构中，顶点V 在链表中出现的次数是（ ）。A. 顶点V 的度 B. 顶点V 的出度 C. 顶点V 的入度 D. 依附于顶点V 的边数 【答案】B【解析】在有向图中，第j 个链表中的结点个数只是顶点Vi 的出度，为求入度，必须遍历整个邻接表。因此顶点V 在链表中出现的次数是顶点V 的出度。 4 float 类型（即IEEE754单精度浮点数格式）能表示的最大正整数是（ ）。A. B. C. D.【答案】D
3、 。【解析】IEEE754单精度浮点数尾数采用隐藏位策略的原码表示，且阶码用移码表示的浮点数。规格化的短 浮点数的真值为：故float 类型能表示的最大整数是 5循环两列放在一维数组S 为符号位，E 的取值为 f 为23位；中，endl 指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（ ）A. 队空：B. 队空：C. 队空：D. 队空：【答案】A【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件
4、还是首尾指针是否相等。 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. 修改文件控制块中的读写权
5、限D. 将文件的数据缓冲区首指针返回给用户进程 【答案】B【解析】概念8 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。 【答案】B【解析】二分查找的时间复杂度为在一个用N 个元素的有序单链表中查找具有给定关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为队满：队满：队满：modM ; 队满： 9 已知关键字序列5, 8, 12, 19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。A.3, 5，12，8, 28，20, 15，22，19 B.3, 5, 12, 19, 20, 15, 22, 8, 28 C.3, 8, 12, 5, 20, 15, 22, 28, 19 D.3, 12, 5, 8, 28, 20, 15, 22, 19【答案】A【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）?（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。 一、选择题考研试题
