2016年高级语言程序设计考研真题答案及解析（二）

本文提供2016年高级语言程序设计考研真题答案及解析，以下为具体内容

1、下面关于线性表的叙述错误的是（ ）。

A、线性表采用顺序存储必须占用一片连续的存储空间

B、线性表采用链式存储不必占用一片连续的存储空间

C、线性表采用链式存储便于插入和删除操作的实现

D、线性表采用顺序存储便于插入和删除操作的实现

2、顺序存储结构的优势是（）。

A、利于插入操作

B、利于删除操作

C、利于顺序访问

D、利于随机访问

3、算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，为了使得算法中的每一条指令有确切的含义，算法应该具有（）。

A、有穷性

B、可行性

C、确定性

D、正确性

4、在长度为n的线性表中插入一个元素，假定在线性表的任何位置上插入元素是等概率的，则插入一个元素大约需要移动线性表中元素的个数是（）。

A、(n-1)/2

B、n/2

C、(n+1)/2

D、n+1

5、在下列单链表中，已知p为单链表存储结构中指向结点a的指针，q为单链表存储结构中指向结点x的指针，删除结点x的操作为（ ）。

A、p->next=q->next; q=p->next; e=q->data; free(q);

B、q=p->next; p->next=q->next; free(q); e=q->data;

C、e=q->data; q=p->next; p->next=q->next; free(q);

D、q=p->next; p->next=q->next; e=q->data; free(q);

7、循环队列的最大容量为MAXSIZE，队尾指针是rear，对头指针是front，则队满的条件是（）。

A、(Q.rear+1) mod MAXSIZE==Q.front;

B、(Q.rear) mod MAXSIZE==Q.front;

C、(Q.rear-1) mod MAXSIZE==Q.front;

D、(Q.rear) mod (MAXSIZE-1)==Q.front;

1、试题答案：D

试题解析：

【考点】本题考查顺序表和链表的特点。
【解析】采用顺序存储结构的线性表进行插入和删除操作时，可能需要移动大量元素，不便于插入和删除操作的实现，所以选项D说法错误。故本题选D。

2、试题答案：D

试题解析：

线性表有两种存储结构，一种为顺序存储，一种为链式存储。
（1）顺序存储用一组连续的存储单元依次存储线性表中的数据元素。其特点如下：
① 是一种随机存取的结构；
② 初始时需要为顺序表分配一个预定义大小的空间；
③ 插入和删除操作均需要移动元素。
（2）链式存储用一组任意的存储单元存储线性表的数据元素，存储单元可以是连续的也可以是不连续的。其特点如下：
① 非随机存取结构，线性链表的存取需要从头指针开始；
② 插入和删除元素仅需修改指针不需要移动元素。
对于A和B，是链式存储的优势，顺序存储中插入和删除均需要移动元素，因此A、B错误。对于C，顺序存储和链式存储均可以采用随机访问，因此C错误。对于D，顺序存储支持随机访问，而链式存储不支持，故本题选D。

3、试题答案：C

试题解析：

算法的5个特性分别为：
（1）有穷性：对于任意一组合法的输入值，在执行有穷步骤后一定能结束，即算法中的操作步骤有限且每个步骤都能在有限的时间内完成。
（2）确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的执行者或者阅读者都能明确其含义以及如何执行。并且在任何条件下，算法都只有一条执行路径。
（3）可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现。
（4）输入：作为算法加工对象的量值，通常体现为算法的一组变量。有些输入量需要在算法执行的过程中输入，而有的算法表面上可以没有输入，实际上输入已经嵌入算法之中。
（5）输出：它是一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果。这种确定关系即为算法的功能。题干的描述符合算法的确定性，故本题选C。

4、试题答案：B

试题解析：

由题干描述可知，该线性表是一个顺序表。顺序表的插入操作是指在第i-1个元素和第i个元素之间插入一个数据元素，使长度为n的线性表长度变为n+1，需要将第n到i的元素向后移动一位，共需移动元素的个数为n-i+1，插入一个元素平均要移动的元素个数为n/2，故本题选B。

5、试题答案：D

试题解析：

对于A，若先执行q=p->next;再执行free(q);则释放的不再是结点x，因此A错误。对于B，应当先执行e=q->data;再执行free(q);，因此B错误。对于C，应当先改变指针的指向，再由e返回其值，因此C错误。对于D，操作正确，故本题选D。

7、试题答案：A

试题解析：

将顺序队列首尾相接成环状空间即为循环队列。在循环队列中，队头指针指向头元素，队尾指针指向尾元素的下一个位置。若循环队列中存放n个元素，则rear==front，此时无法判断是队空的条件还是队满的条件。为了区分这两者，规定循环队列中当元素个数为n-1个时，判定队列已满。队列已满的条件为队头指针front在队尾指针rear的下一个位置上，因此最大容量为s的循环队列，队满条件为(rear+1)%s==front；队空条件为rear==front。故本题选A。