山西省2007年专升本招生考试试题（卷）
数据结构（C语言版）（066）
一、单项选择题（本大题共10小题，每小题2分，共20分。在每小题的四个备选答案中，只有一个答案是正确的，请把正确答案前面的字母填入下列表格内） 题号 1 2 3 4 5 6 7 8 9 10 答案
1．设栈的输入序列为12345，则不可能的输出序列是（ ） A．23415 B．54123 C．23145 D．15432
2．下面关于线性表叙述错误的是（ ）
A．采用顺序存储，必须占用一片连续的存储单元 B．采用顺序存储，便于进行插入和删除操作
C．采用链式存储，不必占用一片连续的存储单元
D．采用链式存储，便于进行插入和删除操作
3．带头结点的单链表head为空的判断条件是（）
A．head=null B．head->next=head C． head->next=null D．head!=null 4．一棵具有n个结点的完全二叉树的高是（）。
A．[log2n]+1 B．log2n+1 C．[log2n] D．[log2n]-1
5．若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点是（）
A．9 B．11 C．15 D 13
6．一个n个顶点的连通无向图，其边数至少是_____。 A．n-1 B．n C．n+1 D．2n
7．按照二叉树的定义，具有3个结点的二叉树有____种。 A．3 B．4 C．5 D．6
8．适用于二分查找的叙述正确的是（ ）
A．表必须有序，表可以顺序存储，也可链式存储 B．表必须有序且表可中数据必须是整形、实型或字符型 C．表必须有序且只能是从小到大排列 D．表必须有序且表只能顺序存储。
9．下列给出的四种排序中，（）是不稳定的 A．插入 B．起泡 C．二路 D．堆
10．某二叉树的前序和后序相同，则该二叉树一定是_____
A．空或只有一个结点 B．高度等于其结点数 C 任一结点无左孩子 D．任一结点无右孩子
二．填空题（本大题共10小题，每小题2分，共20分）
1．在n个结点的顺序表中插入一个结点需平均移动______个结点，但具体移动的次数取决于表长和位置。
2． _______是限定仅在表尾进行插入或删除操作的线性表。 3．算法应该具有零个或若干个_______。
4．假设根结点的层次数是1，具有n个结点的二叉树的最大高度是______。
5．对一棵具有n个结点的满二叉树来说，叶子结点个数是______。 6．若用n表示图中顶点的树目，则有______条边的无向图称为完全图。 7．对长度为255的表，采用分块查找，每块长度为_____。
8．以知有序表(12,18,24,36,47,50,62,83,90,115,134)，当用二分法查找47时，需——————次查找成功。
9．在数据表序是，快速排序的时间复杂度是_____。
10．堆是一种选择排序，它实质是一棵______结点的层次序列。
三．判断题（本大题共10小题，每小题2分，共20分。判断下列各题的正误，在下列表格内正确的打\"√\
1．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出的结构。
2．顺序存储方式的优点是存储密度大，且插入和删除运算效率高。 3．线性表的特点是每个元素都有一个前驱和一个后继。 4．对一棵二叉树进行层次遍历时，应该借助一个栈。 5．二叉树的遍历结果不是唯一的。
6．树中的结点和图中的顶点就是数据结构中的数据元素。 7．有向图的邻接矩阵是对称的。
8．哈希表的平均查找长度与处理冲突的方法无关。
9．在索引顺序表中，实现分块查找，在等概率的情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。 10．内部排序要求数据一定要以顺序方式存储。
四．综合应用题（本大题共5小题，每小题8分，共40分）
1．设一棵二叉树的前序、中序序列分别是：ABDFCEGH 和BFDAGEHC （1） 画出这棵二叉树
（2）．将这棵二叉树转化为对应的树（或森林）。
2．设无向图G为
（1）画出对应的邻接距阵。
（2）按Prim算法求出G的一棵最小生成树。
3．判断下列序列是否是堆？如不是调整为堆，写出过程。 （1） 100,85,,95,77,80,60,82,40,20,10,66 （2） 5,8,11,15,23,20,32,7
a 2
f 1
b 5
6 5 c 7 h 3 d 4 3 8 e 4、设一数列的输入顺序为123456，采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入栈、出栈操作的合法序列。 （1） 能否得到输出序列3251 （2） 能否得到输出序列154623
5、设计算法：统计一棵二叉树中所有叶子结点和非叶子结点的树目。
