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

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

1、一组记录的关键字为{20，14，23，7，59，65，27，55，11，10，24，79}，用链地址法构造散列表，散列函数为H(key)=keyMOD13，散列地址为7的链中有（ ）个记录。

A、2

B、3

C、4

D、5

2、对于一个线性表要求存储结构能反映数据之间的逻辑关系，又能够进行比较快速的插入和删除，应该采用的存储方式为（ ）。

A、顺序存储方式

B、链式存储方式

C、散列存储方式

D、索引存储方式

3、以下算法中加下划线语句的执行次数是（ ）。int n,i,j,count=0;for(i=0;i<n;++) for(j=i;j<n;j++) count++;

A、

B、

C、

D、

4、对长度为n的有序单链表，若查找每个元素的概率相等，则顺序查找表中任一元素查找成功的平均查找长度为（ ）。

A、n/2

B、(n+1)/2

C、(n-1)/2

D、n/4

5、只能在顺序存储结构上进行的查找方法是（ ）。

A、顺序查找法

B、折半查找法

C、散列查找法

D、二分查找树

6、当采用分块查找时，数据的组织方式为（ ）。

A、数据分成若干块，每块内数据有序

B、数据分成若干块，每块中的数据个数需相同

C、数据分成若干块，每块内数据有序，每块内最大（或最小的数据元素组成索引块

D、数据分成若干块，块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据元素组成索引块。

7、一组记录的关键码为（14，12，13，16，15，11），则利用快速排序的方法，以第一个记录为基准，从小到大得到的一次划分结果为（ ）。

A、（11，12，13，14，15，16）

B、（12，11，13，14，15，16）

C、（12，13，11，14，16，15）

D、（11，12，13，14，16，15）

8、一棵哈夫曼树共有315个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A、315

B、157

C、158

D、314

9、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（ ）。

A、3

B、2

C、4

D、5

10、表达式A*(B+C)/(D-E+F)的后缀表达式是（ ）。

A、A*B+C/D-E+F

B、AB*C+D/E-F+

C、ABC+*DE-F+/

D、ABCDED*+/-+

1、试题答案：B

试题解析：

画出该散列表如下：

由上述散列表可知，散列地址为7的链中记录总数为3，故本题选B。

2、试题答案：B

试题解析：

对于A，顺序表的插入和删除需要移动元素，其时间复杂度为O(n)，因此A错误。对于B，链式存储能够反映线性表数据元素之间“一对一”的线性关系，同时链表插入和删除元素时仅需要修改指针指向，不需要移动元素，其时间复杂度为O(1)，因此B正确。对于C，散列表的地址之间可能造成冲突，其插入和删除操作没有链表方便，因此C错误。对于D，索引表的分块内部通常采用顺序存储，其插入和删除操作同样需要移动元素，因此D错误。故本题选B。

3、试题答案：D

试题解析：

当i=0时，执行n次；当i=1时，执行n-1次；…；当i=n-1时，执行1次。因此总的执行次数=1+2+3+…+n= n(n+1)/2，故本题选D。

4、试题答案：B

试题解析：

在单链表中采用顺序查找时，需要从头开始遍历链表进行查找。因此单链表第i个元素的查找长度为i，则平均查找长度=(1+2+3+…+n)/n=(n+1)/2，故本题选B。

5、试题答案：B

试题解析：

对于A，顺序查找法既适用于顺序表又适用于链表，因此A错误。折半查找表仅适用于顺序有序表，折半查找法只能在顺序存储结构上进行查找，因此B正确。对于C，散列查找适用于散列存储结构，因此C错误。对于D，二分查找树通常采用二叉链表存储，因此D错误。故本题选B。

6、试题答案：D

试题解析：

分块查找是折半查找和顺序查找的一种改进方法，分块查找由于只要求索引表是有序的，对块内元素没有排序要求，因此A、C错误。分块查找的块内数据个数不必相同，因此B错误。故本题选D。

7、试题答案：A

试题解析：

快速排序通过多次的比较和交换来实现排序，以基准元素为中心，进行一趟快速排序，将待排序表分成两个子表，对左右子表各选取一个基准值进行划分，直到所有子表的长度为最小单位。一趟快速排序算法的过程为：
① 设置两个变量i、j，排序开始的时候：i=0、j=N-1（N为待划分的数组长度）；
② 以第一个数组元素作为关键数据，赋值给key（基准值），即key=A[0]；
③ 从j开始向前搜索，找到第一个小于key的值A[j]，将A[j]和A[i]的值进行交换；
④ 从i开始向后搜索，找到第一个大于key的值A[i]，将A[i]和A[j]的值交换。
⑤ 重复③、④步，直到i==j。故本题选A。

8、试题答案：C

试题解析：

对任何一棵二叉树，若终端结点为n0，度为2的结点为n2，则n0=n2+1。根据哈夫曼树的构造方法可知哈夫曼树中仅有度为0和度为2的结点，且哈夫曼树的每个叶子结点代表一个待编码的字符，根据上述性质可得n=n0+n2=n0+n0-1=315，2*n0-1=315，n0=158，故本题选C。

9、试题答案：C

试题解析：

前序遍历二叉树先访问根结点，再遍历左子树，最后遍历右子树。中序遍历二叉树先遍历左子树，再访问根结点，最后遍历右子树。后序遍历二叉树先遍历左子树，再遍历右子树，最后访问根结点。根据后序序列可知树的根结点为E，根据中序序列可知ABCD是E的左子树，FG是E的右子树，故本题选C。

10、试题答案：C

试题解析：

本题可以采用加括号的方法解答。① 根据运算的先后顺序为中缀表达式加上括号：((A*(B+C))/((D-E)+F))；② 把运算符移到对应的括号外面：((A(BC)+)*((DE)-F)+)/；③ 将括号去除后的后缀表达式：ABC+*DE-F+/。故本题选C。