Question

十万火急，，求助大家帮忙做《数据结构》试题！！！！

一选择题
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个非叶子结点，则树中共有多少结点，对给定的一组权重值建立的棵哈夫叭一否一定唯一。

Answer 1

你在考电大的数据结构？哇哈哈 和我一样啊 ~~
程序填空：
以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的

结构指针p（查找成功p指向查到的树结点，不成功p指向为NULL）完成程序中的空格。

typedef struct Bnode
{
int key;
struct Bnode *left;
struct Bnode *right;
}Bnode;
Bnode *Bsearch(Bnode *bt,int k)
/*bt用于接收二叉顺序树的根结点的指针，k用于接收要查找的关键字*/
{
Bnode *p;
if (bt==(1)________)
return(bt);
p=bt;
while(p->key!=(2)________)
{
if(k<p->key)
(3)_________;
else(4)_________;
if(p==NULL) break;
}
Return(5)________;
}

以下函数为链队列的出队操作（链队列中带有头结点），出队结点的数据域的值由x返回，front、rear分

别是链队列的队头、队尾指针。
struct node
{
ElemType data;
struct node *next;
};
struct node *front,*rear;
ElemType OutQueue()
{
ElemType x;
if((1)________)
{
printf("队列下溢错误！\n");
exit(1);
}
else
{
struct node *p=front->next;
x=p->data;
front->next=(2)_________;
if(p->next==NULL) rear=front;
free(p);
(3)________________;
}
}

Answer 2

4.D 5.C 7.B 8.B 9.D 10.A 11.B 12.A 13.A 15.A
1．图状 （或网状）
2. p->next= =head;
3．hs=s；
4．r->next=s；r=s；
5．3；5
6．2
7．10
8．深度优先；广度优先
9．图状（或网状）
10． 2n-1
11．顺序存储 链式存储
12．关键字相等的记录
三、1、（2）edbca
（3）e=1,a=2,d=3,c=4,b=5

2、（2）5，6，7，8，9，10，17，18，19，21

Answer 3

由于太急了，，刚刚自己发的没看到，担天明天的考试，急得我后来又重发了几次，，请大家见谅，多多帮忙啊，，明天就要交卷 了，，，谢！！！！！

Answer 4

我也是