山西省2007年专升本招生考试试题
山西省2007年专升本招生考试试题(卷) 数据结构(C语言版)(066)
一、单项选择题(本大题共10小题，每小题2分，共20分。在每小题的四个备选
答案
八年级地理上册填图题岩土工程勘察试题省略号的作用及举例应急救援安全知识车间5s试题及答案
中，只有一个答案是正确的，请把正确答案前面的字母填入下列
表格
关于规范使用各类表格的通知入职表格免费下载关于主播时间做一个表格详细英语字母大小写表格下载简历表格模板下载
内) 题号 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为
b d 1 5 3 8
a 5 c 4 e 7 2 6 3 f h
(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
4、设一数列的输入顺序为123456，采用堆栈结构，并以A和D分别表示入栈和出栈操作，试问通过入栈、出栈操作的合法序列。
(1) 能否得到输出序列325641
(2) 能否得到输出序列154623
5、
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
算法:统计一棵二叉树中所有叶子结点和非叶子结点的树目。
浙公网安备 33021202002483