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、中根