20、对于队列，只能在__队尾___插入元素，在___队头____删除元素。 三、 应用题（共4小题，每小题8分，共32分） 21、对图1所示的树

（1） 结点A的度是_____3______。 （2） 树的度是______3_____。

（3） 画出其转换成相应二叉树的树形 A

/ | \\ B C D

/ \\ / \\ E F G H /

I

解答：一般树转换成二叉树步骤：

将父亲管理儿子方式改为 父亲管理大儿子，

大儿子管理二儿子（二儿子变成大儿子的右孩子）

二儿子管理三儿子（三儿子变成二儿子的右孩子）

A ABEFCDGIH 前

/ EFBCIGHDA 中 B

/ \\ FEIHGDCBA后 E C \\ \\ F D

/ G / \\ I H

22、已知参加排序的正整数序列是：90、70、180、30、520、40、60、80、50、130。以第一个元素90作为基准元素，根据快速排序算法，写出完成第一趟划分后序列重新排列的情况。

60、70、50、30、80、40、90、520、180、130

23、一次输入如下序列中的各个整数，构造其相应的二叉搜索树，只需要画出最后生成的二叉搜索树的树形。整数序列是180、160、250、300、170、120、125、290、380。

180

/ \\ 160 250 / \\ \\ 120 170 300

\\ / \\

125 290 380

24、用Prim算法求图2所示的无向带权连通图的最小生成树。要求依次画出从顶点1出发的最小生成树的生成过程。

1 \\ 4 1 / \\ 2 3— 4 1 / \\ 2 4 1 / \\ 2 3— 4 / 5

四、 算法设计（共2小题，第25小题10分，第26小题12分，共22分） 25、二叉树以二叉表为存储结构，结点结构的定义如下，请写出一个求二叉树中叶子结点个数的算法。

typedef struct btnode *btlink; struct btnode{

TreeItem element; btlink left; btlink right; }Btnode

解答：与05年考题不一样

int f(指向树根的指针){//f()计算树中叶子节点的个数 if(指向树根的指针==NULL)return 0;

x=f(指向树根的左孩子指针); //左子树中叶节点数； y= f(指向树根的右孩子指针);//右子树中叶节点数； if(root->left==NULL&&root->right==NULL)return 1;

else return x+y; /*或者

if( x==0&&y==0)return 1; else return x+y;*/ }

int f ( btlink root ){//f()计算树中叶子节点的个数 if(root==NULL)return 0;

x=f(root->left); //左子树中叶节点数； y= f(root->right);//右子树中叶节点数； if(x==0&&y==0)return 1; else return x+y; }

T(n)=1+T(n1)+T(n2) n1+n2=n

=1+1+T(n11)+T(n12)+1+T(n21)+T(n22) n1=n11+n12 n2=n21+n22

25、二叉树以二叉表为存储结构，结点结构的定义如下，请写出一个求二叉树的高度算法。 解答：

int h(指向树根的指针){//f()计算树高度 if(指向树根的指针==NULL)return 0;

x=h(指向树根的左孩子指针); //左子树高度； y= h(指向树根的右孩子指针);//右子树高度； if(x>y)return x+1; else return y+1;

//return (x>y?x:y) +1; }

26、阅读下列程序，它是在已知的数组a中查找数值为x的元素，如果存在则输出“found”，否则输出“not found”。试问它是什么方法实现的？并请完善程序。

用__________查找法。 #define N 10

void bs(int a[],int x){ int l,r,m; l=0;r=N-1;

m=___(l+r)/2______;

while((_____l<=r_______) && (x!=a[m]) ){ if(x>a[m]) l=_____m+1______; else r=m-1; m=(l+r)/2; }

if(___l<=r____)

printf(\ else

printf(\}

main(){

int a[N]={10,20,30,40,50,60,70,80,90,100}; int x;

printf(\ scanf(\ bs(____a, x_______); }

05专升本数据结构考题

一、单选题：（每题2分，共24分）

1、双向链表的一个结点有( B )个指针。 A、1 B、2 C、0 D、3

2、在n个结点的顺序表中，算法的时间复杂度都是O(1)的操作是( A )。 A、访问第i个结点(1≤i≤n)和求第i个结点的直接前趋(2≤i≤n) B、在第i个结点后插入一个新结点(1≤i≤n) C、删除第i个结点(1≤i≤n) D、将n个结点从小到大排序

3、在队列中存取数据的原则是( A )。 A、先进先出 B、后进后出? C、先进后出 D、不进不出

4、在栈中，出栈操作的时间复杂度为( A )。 A、O(1) B、O(logn) C、O(n) D、O(n*n)

5、设长度为n的链队列用单循环链表表示，若只设头指针，则人队操作的时间复杂度为( C )。 A、O(1) B、0(logn) C、0(n) D、O(n*n)

6、如果二叉树的叶结点数为n0，则具有双分支的结点数n2等于( D )。 A、nO+l B、n0 C、2*n0 D、n0-1

7、一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用( B )遍历方式就可以得到这棵二叉树所有结点的递增序列。 A、先根 B、中根