2015年高级语言程序设计考研真题答案及解析

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

1、以下数据结构属于非线性结构的是（ ）。

A、链表

B、栈

C、队列

D、二叉树

2、以下对线性表描述错误的是（ ）。

A、顺序表是随机存储结构、存储的时间复杂度为O(1)

B、链表是顺序存储结构，存储的时间复杂度为O(n)

C、顺序表的插入和删除可能要移动大量的元素

D、链表的插入和删除可能要移动大量的元素

3、已知p为指向带头结点的单链表的头指针，以下表达式说明该单链表为空的是（ ）。

A、

B、

C、

D、

4、设堆栈S和队列Q的初始状态为空，元素1，2，3，4，5，6依次入栈，一个元素退栈后即进入队列。若这6个元素出队列的顺序是3，2，6，5，4，1，则栈S的容量至少应该是（ ）。

A、2

B、3

C、4

D、5

5、若从二叉树的根结点出发到达任一叶子结点的路径上所经过的结点序列按其关键字有序，则该二叉树一定是（ ）。

A、二叉排序树

B、哈夫曼树

C、B-树

D、堆

6、已知在一棵度为3的树中，有4个度为1的结点，3个度为2的结点，2个度为3的结点，那么该树中有叶子节点个数（ ）。

A、8

B、9

C、10

D、11

7、某哈弗曼树的结点总数为2n-1，若用二叉链表作为存储结构，则该哈夫曼树中一共有多少个空指针域（ ）。

A、2n-1

B、2n

C、2n+1

D、4n

8、n个顶点组成的有向图至少需要多少条弧才能构成强连通图（ ）。

A、n

B、2n

C、n(n-1)

D、n-1

9、设用邻接矩阵M来表示有向图G的存储结构，那么有向图G的第i个顶点的入度为（ ）。

A、第i行非0元素的个数

B、第i列非0元素的个数

C、第i行非0元素的个数除以2

D、第i列非0元素的个数除以2