一选择题
4，一个栈的进栈序列是efgh，则栈的不可以的出栈序列是（）（进出栈操作可以交替进行）
A，hgfe
B，gfeh
C，fgeh
D，ehfg
5,设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针next组成，设用x接收栈顶元素，则取栈顶元素的操作为（）
A，top->data= x
B，top=top->next
C，x=to->data
D，x=top->data;top=top->next
7,char *p
p=StrCat("ABD","ADC");
Printf("%s",p)
的显示结果为（）
A，-1
B，ABDABC
C，AB
D，1
8深度为5的满二叉树至多有（）个结点（根结点为第一层）
A，40
B，31
C，34
D，35
9，已知一个图的所有顶的度数之和为m,则该图的边数为（）
A，2m
B，m
C，2m+1
D，m/2
10,以下说法不正确的是（）
A，连通图G的生成树一定是唯一的
B，连通图G一定存在生成树
C，连通图G的成生树中一定要包含G的所有顶点
D，连通图G的生成树一定是连通而且不包含回路
11，有序表为{1，2，4，6，10，18，20，32}，用课本中折半查找算法查找值18，经（）次比较后成功查到。
A，3
B，2
C，4
D，5
12，在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是（）
A，冒泡
B，选择
C，直接插入
D，折半插入
13，用折半查找法，对长度为12的有序的线性表进行查找，最坏情况下要进行（）次元素间的比较。
A，4
B，3
C，5
D，6
15，一棵哈夫曼树总共有25个结点，该树共有（）个非叶结点（非终端结点）
A，12
B，13
C，14
D，15
二填空题
2，设有一个单向循环链表，结点的指针域为next,头指针为head,指针p指向表中某结点，若逻辑表达式 的结果为真，则p所指结点为尾结点。
3，设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作s->next=hs; .
4,在一个链队中，f和r分别为队头和队尾指针，队结点的指针域为next，s指向一个要入队的结点，则入队操作为 ； 。
5，循环队列的最大存储空间为MaxSize=6,采用少用一个元素空间以有效地判断栈空或满，若队头指针front=4,当队尾指针rear= 时队满，队列中共有 个元素。
7，一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中对应位置上结点的编号相同），若它存在左孩子，则左孩子的编号为 。
8，根据搜索方法的不同，图的遍历有 、 两种方法。
9，结构中的数据元素存在多对多的关系称为 结构。
10，一棵有n个叶结点的二叉树，其每一个非叶结点的度数都 为2，则该树共有 结点。
11，串的两种最基本的存储方式分别是 和 。
12，按某关键字对记录序列排序，若关键字 的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定 的。
三，综合题
1，（1）已知某二叉树的先序遍历序列是aeedb，中序遍历序列是eadcb，试画二叉树
（2）给出上述二叉树的后序遍历序列
（3）若上述二叉树的各个结点的字符分别是1，2，3，4，5，并恰好使该树成为一棵二叉排序树，试问a、b、c、d、e的值各为多少？
2，（1）给定数列{8，17，5，9，21，10，7，19，6}，依次取序列中的数构造一棵二叉排序树。
（2）对上述二叉树给了中序遍历得到的序列。
3，（1）以给定权重值1，2，12，13，20，25为结叶点，建立一棵哈夫曼数。
（2）若哈夫曼树有n个非叶子结点，则树中共有多少结点，对给定的一组权重值建立的棵哈夫叭一否一定唯一。
今天多亏有大家的帮助，才让我完成了一门C语言的考试，希望大家帮我把这数据结构做一做，，十分感谢，虽然分数用得差不多了，但我会在今后几天里努力挣分，回报大家对我的帮助，，明天是最后一天交卷了，，我不想门门功课都 重考，，谢谢大家的帮忙~~~