2016年北航911数据结构与C 语言程序设计考研选择题真题

考生注意：所有答题务必书写在考场提供的答题纸上，写在本试题单上的

答题一律无效(本题单不参与阅卷)。

一、单项选择题(本题共20分，每小题各2分)

1、若listl和list2分别为一个指向单向链表与指向双向链表的指针变量，则下列叙述中正确的是( )

A. list2比list-I占用更多的存储单元;

B. listl与list2占用相同多的存储单元

C. listl和list2应该是相同类型的指针编量

D. 双向链表比单向链表占用更多的储存单元

2、下列关于队列的叙述中，错误的是( )

A. 队列是一种插入和删除位置受到限制的特殊线性表;

B. 做删除操作时时要先判断队列是否为空，做插入操作时时要先判断队列是否为已满;

C. 采用循环链表作为储存结构的队列称为循环队列;

D. 通常情况下，循环队列比非循环队列的空间使用率要高。

3、若push和pop分别表示对堆栈操作和一次出栈操作，则将输入序列1，2, 3 转换为输出序列2, 3, 1所经过的操作依次为( )

A. push,push, pop, push, pop, pop:

B. push, pop,push, push,pop,pop

C. push,push,push pop,pop, pop;

D. push,pop,push,pop,push,pop.

4、 若某完全二叉树的第6层有24个叶结点，则该完全二叉树的结点总数最大为( )

A. 78

B. 79

C. 80

D. 81

5、若某二叉排序树的后序遍历序列为10,20, 40, 60, 50, 观则其前序遍历序列为( )

A. 30, 20, 50; 10, 40, 60

B. 30, 50, 60, 40, 20, 10

C. 10, 20, 30, 40, 50, 60

D. 30, 20, 10, 50, 40, 60

6、 下列四种图中，其对应的邻接矩阵为对称矩阵的是( )

A. 有向图;

B. 无向图;

C. AVO网;

D. AOE网.

7、下列关于带权连通图的最小生成树的叙述中，正确的是( )

A. 最小生成树的代价不一定比该图其他任何一棵生成树的代价小;

B. 若图中出现权值相同的边时，则该图的绿小生成树不是惟一的;

C. 若图中边上的权值各不相同，则该图的最小生成树是惟一，

D. 该图的最小生成树的权值之和不一定是惟一的。

8、 下列关于查找操作的ASL(平均查找长度)的叙述中，错误的是( )

A. 查找成功的ASL是指找到指定元素所需要进行的关键字比较次数的期望值

B. 查找失败的ASL是指没有找到指定元素，但找到该元素的插入位置所需要进行的关键字比较次数的期望值

C. ASL与元素在结构中的分布状况有关

D. ASL与元素的查找概率无关。

9、下列关于m阶B-树的叙述中错误的是( )

A. 根结点至少有两棵子树

B. 根结点至多有m棵子树

C. 每个分支结点至少有(m/2)棵子树

D. 所有叶节点都在同一层上

10. 下列四种排序方法中，在一趟排序结束时不一定能够确定某一元素的最终位置的是( )

A. 选择排序法

B. 泡排序法

C. 堆积排序法

D. 二路并归排序法