2015年操作系统考研真题答案及解析

本文提供2015年操作系统考研真题答案及解析，以下为具体内容

1、下面叙述中正确的是（ ）。

A、 一个逻辑数据结构只能有一种存储结构

B、 数据的逻辑结构属于线性结构，存储结构属于非线性结构

C、 一个逻辑数据结构可有多种存储结构，各种存储结构不影响数据处理效率

D、 一个逻辑数据结构可有多种存储结构，各种存储结构影响数据处理效率

2、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是（ ）。

A、 单链表

B、 仅有头指针的单循环链袭

C、 双链表

D、 仅有尾指针的单循环链表

3、某双向链表中的结点如下所示，删除t所指示的结点的操作为（ ）。

A、 t->prior->next=t >next; t ->next- >prior=t->prior

B、 t->prior->prior=t->prior; t->next >next=t->next

C、 t->prior->next=t- >prior; t->next- >prior =t ->next

D、 t >prior- >prior =t->next; t->next->prior=t->prior

4、非空的单循环链表的头指针为head，尾指计为rear，则下列条件成立的是（ ）

A、 rear->next==head

B、 rear->next->next==head

C、 head->next==rear

D、 head->next->next= =rear

5、对于栈，操作数据的原则是（ ）

A、 先进先出

B、 后进先出

C、 后进后出

D、 不分顺序

6、对稀疏矩阵进行压缩存储的目的是（ ）。

A、 便于进行矩阵运算

B、 便于输入和榆出

C、 节省存储空间

D、 降低运算的时间复杂度

7、对广义表L=((e, b)，(c, d)，(e, f)) 执行操作tail (tail (L))的结果是（ ）。

A、 (e，f)

B、 ((e. f))

C、 (f)

D、 ( )

8、对一颗有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为（ ）。

A、 24

B、 25

C、 98

D、 99

9、在有n个结点的哈夫曼树中，其结点总数为（ ）。

A、 不确定

B、 2n

C、 2n+1

D、 2n-1

1、试题答案：D

试题解析：

【考点】本题考查逻辑结构与存储结构。
【解析】A. 一种数据的逻辑结构根据需要可以表示成多种存储结构，例如栈根据不同的存储方式分为链栈和顺序栈。故A叙述不正确。B. 数据的逻辑结构分为线性结构和非线性结构。故B叙述不正确。C. D. 存储结构是会影响数据处理操作的，例如在队列的队头插入一个元素，使用顺序队列的时间复杂度为O(n)，而使用链式队列的时间复杂度为O(1)。故本题选D。

2、试题答案：D

试题解析：

【考点】本题考查线性表的插入和删除操作。
【解析】链表有尾指针可以直接找到最后一个元素，在其后面插入一个元素的时间复杂度为O(1)。单循环链表中尾结点所指结点的next指针域指向第一个元素，删除第一个元素的时间复杂度为O(1)。故本题选D。

3、试题答案：A

试题解析：

【考点】本题考查双向链表的删除操作
【解析】双向链表删除某一结点的示意图如下所示：

① t->prior->next=t >next; ② t ->next- >prior=t->prior
由上面的示意图可知，删除t所指示的结点的操作为t->prior->next=t >next; t ->next- >prior=t->prior。故本题选A。

4、试题答案：A

试题解析：

【考点】本题考查非空单循环。
【解析】头指针为head，尾指计为rear的非空单循环链表如下所示，由此可rear->next==head成立。故本题选A。

5、试题答案：B

试题解析：

【考点】本题考查栈的特点。
【解析】栈是一种只能从表的一端存取数据且遵循 "后进先出" 原则的线性存储结构。故本题选B。

6、试题答案：C

试题解析：

【考点】本题考查稀疏矩阵压缩存储的目的。
【解析】对矩阵进行压缩不能简化矩阵运算，对输入输出也不能提供便利，而降低运算的时间复杂度主要与算法有关，一般对矩阵压缩后其运算的复杂度会增加。故A、B、D错误。对稀疏矩阵进行压缩存储目的是节省存储空间。本题选C。

7、试题答案：B

试题解析：

【考点】本题考查广义表的tail操作。
【解析】tail (L)=( (c, d)，(e, f))；tail (tail (L))=( (e, f))。故本题选B。

8、试题答案：A

试题解析：

【考点】本题考查完全二叉树性质。
【解析】对于一颗完全二叉树而言，若某一结点编号为i，则其父结点、左孩子和右孩子结点编号如下所示：

本题中i=49，则其父结点编号为⌊i/2⌋=49/2=24。故本题选A。

9、试题答案：D

试题解析：

【考点】本题考查哈夫曼树创建过程中结点的生成。
【解析】在创建哈夫曼树时，每次需要选取两个权值最小的结点生成一个新的结点。若总共有n个结点，则会进行n-1轮两两组合，共生成n-1个新的结点，因此哈夫曼树的结点总数=n+(n-1)=2n-1。故本题选D。