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

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

1、在数据结构中，从逻辑上可以把数据结构分成（ ）。

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

2、对顺序存储的线性表，设其长度为n，在任何位置上删除操作都是等概率的，则删除一个元素大约要移动表中元素的个数是（ ）。

A、n/2

B、(n+1)/2

C、n-1

D、(n-1)/2

3、以下的叙述中，正确的是（ ）。

A、线性表的顺序存储结构优于链式存储结构

B、二维数组是其数据元素为线性表的线性表

C、栈的操作方式是先进先出

D、队列的操作方式是先进后出

4、在表达式中进行括号匹配检验时，采用（ ）数据结构最佳。

A、线性表的顺序存储结构

B、栈

C、线性表的链式存储结构

D、队列

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

A、Q.front=maxsize

B、Q.rear=Q.front

C、Q.rear=maxsize

D、(Q.rear+1)%maxsize=Q.front

6、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）。

A、s->next=p->next; p->next=s;

B、p->next=s->next; s->next=p;

C、q->next=s; s->next=p;

D、p->next=s; s->next=q;

7、AOE网是一种（ ）。

A、有向图

B、无向图

C、无向无环图

D、有向无环图

8、先将整个待排序元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的），分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（ ）。

A、快速排序

B、起泡排序

C、直接选择排序

D、希尔排序

9、采用折半查找方法进行查找，数据文件应为（ ），且限于（ ）。

A、随机表 顺序存储结构

B、有序表 链式存储结构

C、有序表 顺序存储结构

D、随机表 链式存储结构

1、试题答案：C

试题解析：

题干已说明从逻辑上划分数据结构，因此考查数据结构的逻辑结构，A、B、D均不属于数据结构的逻辑结构。数据结构包括数据的逻辑结构和数据的物理结构两个层次。数据的逻辑结构是对数据之间关系的描述，通常有四种基本类型：
① 线性结构：数据元素之间存在“一对一”的线性关系的数据结构；
② 树形结构：数据元素之间存在“一对多”的树形关系的数据结构；
③ 图状或网状结构：数据元素之间存在“多对多”的网络关系的数据结构。
④ 纯集合结构：指数据元素之间除了“同属一个集合”之外，别无其他关系。
其中树形结构、图状或网状结构、纯集合结构均属于非线性结构，故本题选C。

2、试题答案：D

试题解析：

顺序表的删除操作是指在删除第i个元素，需要将第i+1至第n个元素依次向前移动一位，共需移动元素的个数为n-i，平均要移动的元素个数=[0+1+2+…+(n-1)]/n=(n-1)/2。故本题选D。

3、试题答案：B

试题解析：

对于A，线性表的两种存储结构各有优缺点，没有一种存储结构优于另一种存储结构的说法，因此A错误。对于B，可以将二维数组理解成n个一维数组，因此B正确。对于C，栈的操作具有“后进先出”的特性，因此C错误。对于D，队列的操作具有“先进先出”的特性，因此D错误。故本题选B。

4、试题答案：B

试题解析：

括号匹配检验是典型的栈的应用。利用栈实现的过程描述如下：
若遇到左括号则入栈，若遇到右括号则将栈顶元素出栈，并检查出栈元素是否为与左括号匹配的右括号；若不匹配，返回false。若均匹配且栈最终为空，则返回true。故本题选B。

5、试题答案：B

试题解析：

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

6、试题答案：C

试题解析：

画出该单链表插入的图示如下：

由上图可知，C选项符合图示的操作，故本题选C。  

7、试题答案：D

试题解析：

AOE网是一个带权的有向无环图，在图中，用顶点代表事件，用有向边表示活动，边上的权值表示活动的持续时间。故本题选D。

8、试题答案：D

试题解析：

希尔排序又称“缩小增量”的排序，属于插入排序的一种。希尔排序的基本思想是先将整个待排序列分割成若干子序列，对子序列分别进行插入排序，待整个序列中的记录基本有序之后，再对整个序列进行一次插入排序。题干描述符合希尔排序的基本思想，故本题选D。

9、试题答案：C

试题解析：

折半查找是针对顺序有序表设计的。有序线性表的折半查找从线性表的中间元素开始查找。若中间元素正好是待查找的元素，则查找成功，搜索结束；若中间元素小于待查找的元素，则从线性表大于中间元素的半边中搜索；若中间元素大于待查找的元素，则从线性表小于中间元素的半边中搜索。如果在某一步骤待查找区间元素为空，则代表查找失败。故本题选C。