算法设计题
1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的
个数。
【答案】
int count=0;
void algo2(BTNode *bt){ if (bt){
if(bt->lchild || bt->rchild){ printf(bt->data);
count++;
}
algo2(bt->lchild); algo2(bt->rchild); }
}
2. 阅读下列函数arrange()
int arrange(int a[],int 1,int h,int x) {//1和h分别为数据区的下界和上界 int i,j,t；
i=1；j=h； while(i while(i { t=a[j]；a[j]=a[i]；a[i]=t；} } if(a[i] } （1）写出该函数的功能； （2）写一个调用上述函数实现下列功能的算法：对一整型数组b[n]中的元素进行重新排列，将所有负数均调 整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组 中零元素的个 数。 【答案】 （1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x 的元素均落在a[i＋1..h]上。 （2）int f(int b[],int n) 或 int f(int b[],int n) { { int p,q； int p,q； p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)； q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)； 万维试题库系统 第 1 页 return q－p； return p－q； } } 3. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。 【答案】 void algo1(LNode *h,int k,ElemType y){ q=h; P=h->next; j=1; while( p!=h && j s=(LNode *)malloc(sizeof(Lnode)); s->data=y; q->next=s; s->next=q; } 4. 二叉排序树的类型定义如下： typedef struct BSTNode {∥ 二叉排序树的结点结构 int data; ∥数据域 struct BSTNode *lchild, *rchild; ∥左、右孩子指针 }BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。 【答案】 int f34(BSTree root) { int count; BSTNode *p; p=root; if ( p && p->datalchild); return count; } 5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。（注：结点按从上往下，自左 至右次序编号） 【答案】 BTNode * Firstleaf(BTNode *bt) { InitQueue(Q); //初始化队列Q if(bt){ EnQueue(Q,bt);; while(!EmptyQueue(Q)){ DeQueue(Q,p); 万维试题库系统 第 2 页 if(!p->lchild && !p->rchild) return p; if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } } } 6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的 结点的双亲和 孩子结点。 【答案】 int algo2(char bt[],int n,int k){ if (k<1||k>n) return 0; if( k==1) printf(“ %c is a root\\n”, bt[1]); else printf(“ %c’s parent is %c\\n”, bt[k], bt[k/2]); if(2*k<=n) printf(“ %c’s lchild is %c\\n”, bt[k], bt[2*k]); else printf(“ %c is not lchild\\n”, bt[k])); if(2*k+1<=n) printf(“ %c’s rchild is %c\\n”, bt[k], bt[2*k+1]); else printf(“ %c is not rchild\\n”, bt[k])); return 1; } 7. 编写算法，将非空单链表hb插入到单链表ha的第i(0 int algo1(LNode *ha, LNode *hb,int i){ for(p=hb;p->next; p=p->next); for(j=1,q=ha;j q->next=hb->next ； free(hb); } 8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立该二叉树的二叉链表结 构。顺序表T定义如下： struct tree{ int no; /* 结点按完全二叉树的编号*/ ElEMTP data; /* 数据域 */ }T[N]; /* N为二叉树T的结点数*/ 【答案】 BTNode *creat_tree(struct tree T[N]) { BTNode *p[MAX]; t=NULL; for(i=0;i s=(BTNode *)malloc(sizeof(BTNode)); s->data=T[i].data; s->lchild=s->rchild=NULL; m=T[i].no; p[m]=s; 万维试题库系统 第 3 页 if(m==1) t=s; else { j=m/2; if(m%2==0) p[j]->lchild=s; else p[j]->rchild=s; }//slse }//for return t; }// creat_tree 9. 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。 【答案】 int algo1 (LNode *L) { if(!L->next) return 1; p=L->next; while(p->next){ if(p->data < p->next->data) p=p->next; else return 0; } return 1; } 10. 假设一线性表由Fibonacci数列的前n（n≥3）项构成，试以带表头结点的单链表作该线性表的存储结构， 设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得： 1 (n=1) f(n)= 1 (n=2) f(n-2)+f(n-1) (n≥3) 【答案】 LNode * Creatlist(LNode *h,int n){ h=(LNode *)malloc(sizeof(Lnode)); h->data=n; h->next=p=(LNode *)malloc(sizeof(Lnode)); p->next=q=(LNode *)malloc(sizeof(Lnode)); p->data= q->data=1; for(i=3;i<=n;i++){ q->next=s=(LNode *)malloc(sizeof(Lnode)); s->data=p->data+q->data; s->next=NULL; p=q;q=s; } return h; } 11. 设二叉树T采用二叉链表结构存储，数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母 的结点改为大写 字母。 【答案】 void algo2(BTNode *bt){ 万维试题库系统 第 4 页 if (bt){ if(bt->data>=’a’&& bt->data<=’z’) bt->data-=32; algo2(bt->lchild); algo2(bt->rchild); } } 12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假如表长小于k，则插在表尾。 【答案】 void Insertlist(LNode *h,int k,ElemType y) { q=h; P=h->next; j=1; while( p!=h && j q=p; p=p->next; j++; } s=(LNode *)malloc(sizeof(Lnode)); s->data=y; q->next=s; s->next=q; } 13. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素x，使得插入后的单链表仍有序。 【答案】 void algo1 (LNode *H, ElemTp x) { s=(LNode *) malloc (sizeof(LNode)); s->data=x; q=H; p=H->next; while ( p && p->data<=x ) { q=p; p=p->next; } s->next=p; q->next=s; } 14. 二叉排序树的类型定义如下： typedef struct BSTNode {∥ 二叉排序树的结点结构 int data; ∥数据域 struct BSTNode *lchild, *rchild; ∥左、右孩子指针 }BSTNode,*BSTree; 设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。 【答案】 int f34(BSTree root) 万维试题库系统 第 5 页