1、假定从键盘上输入一批整数，依次为：78 63 45 30 91 34 –1，请写出输出结果。

# include < iostream.h> # include < stdlib.h >

consst int stackmaxsize = 30; typedef int elemtype; struct stack {

elemtype stack [stackmaxsize]; int top; };

# include “stack.h” Void main ( )

{

stack a;

initstack(a); int x; cin >>x;

while (x! = -1) { push (a, x ); cin >>x;

}

while (!stackempty (a)) cout <

}

该算法的输出结果为：

__________________________________________________________. 2、阅读以下二叉树操作算法，指出该算法的功能。 Template void BinTree ：：

unknown (BinTreeNode*t) {

BinTreeNode< Type> *p =t, *temp; if (p!=NULL) {

temp = p→leftchild;

p→leftchild = p→rightchild;

p→rightchild = temp; unknown(p→leftchild); undnown(p→rightchild);

}

}

该算法的功能是：________________________________

五、 算法填空，在画有横线的地方填写合适的内容（10分）

对顺序存储的有序表进行二分查找的递归算法 。 int Binsch( ElemType A[ ],int low ,int high,KeyType K ) {

if (low <= high)

{

int mid = 1

if ( K= = A[ mid ].key ) return mid;

else if ( K < A[mid].key) return 2 else

return 3 }

else

return 4

六、 编写算法（10分）

编写算法，将一个结点类型为Lnode的单链表按逆序链接，即若原单链表中存储元素的次序为a1，……an-1，an，则逆序链接后变为, an，an-1，……a1。

Void contrary (Lnode * & HL)

数据结构试题（答案）

一、单选题（每小题2分，共8分） 1 2 3 题 号 C D 答 案 二、填空题（每空1分，共32分） 1： 集合、线性、树、图； 2： 数据描述、操作声名；

3： （38，56，25，60，42，74）；

4： HL→next =NULL； HL=HL→next；

A 4 B 5： 前一个位置； n-1；

6： S.stack [S.top]; HS→data; 7： 5 31

8： 边结点、邻接点域、权域、链域； 9： 索引值域、开始位置域； 10： 10、3、3、B、I和J； 11： O（log2n）、O(nlog2n); 12： m 、 m - 1

三、运算题（每小题6分，共24分） 1、

划分次序 第一次 第二次 第三次 第四次 第五次 第六次 划分结果 [38 24 40] 46 [56 80 95 79] 24 [38 40] 46 [56 80 95 79] 24 38 40 46 [56 80 95 79] 24 38 40 46 56 [80 95 79] 24 38 40 46 56 79 [80 95] 24 38 40 46 56 79 80 95 2、 0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 查找成功的平均查找长度：ASL SUCC=14/10= 1.4

3、此二叉树的后序遍历结果是：EDCBIHJGFA 4、

图 邻接矩阵表示时 邻接表表示时 深度优先序列 0，1，2，8，3，4，5，6，7，9 0，4，3，8，9，5，6，7，1，2 广度优先序列 0，1，4，2，7，3，8，6，5，9 0，4，1，3，7，2，8，6，9，5 四、阅读算法，回答问题（每小题8分，共16分） 1、 1、 该算法的输入结果是：34 91 30 45 63 78

2、 2、 该算法的功能是：交换二叉树的左右子树的递归算法。 五、算法填空，在画有横线的地方填写合适的内容（10分） 1、1是：（low + high）/2;

2是： Binsch(A,low,mid–1,K); 3是： Binsch(A,mid+1,high,K); 4是： -1；

六、编写算法（10分） 根据编程情况，酌情给分。 {

Lnode *P=HL; HL=NULL; While (p!=null) {

Lnode*q=p;

P=p→next; q→next=HL; HL=q; } }