《数据结构算法设计题》由会员分享，可在线阅读，更多相关《数据结构算法设计题（11页珍藏版）》请在金锄头文库上搜索。
1、 万维试题库系统 第 1 页一、算法设计题一、算法设计题1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的个数。 【答案答案】 int count=0; void algo2(BTNode *bt)if (bt)if(bt-lchild | bt-rchild) printf(bt-data);count+count+; algo2(bt-lchild);algo2(bt-rchild); 2. 阅读下列函数arrange()int arrange(int a,int 1,int h,int x)/1和h分别为数据区的下界和上界int i,j,
2、t；i=1；j=h；while(i=x)j-；while(i=x)i+；if(inext; 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 ro
3、ot)int count;BSTNode *p;p=root;if ( p return count; 5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。 （注：结点按从 上往下，自左 至右次序编号） 【答案答案】BTNodeBTNode * * Firstleaf(BTNodeFirstleaf(BTNode *bt)*bt) InitQueue(Q);InitQueue(Q); /初始化队列初始化队列Q Qif(bt)if(bt)EnQueue(Q,bt);EnQueue(Q,bt);万维试题库系统 第 3 页while(!EmptyQueue(Q)wh
4、ile(!EmptyQueue(Q)DeQueue(Q,p);DeQueue(Q,p);if(!p-lchildif(!p-lchild p;if(p-lchild)if(p-lchild) EnQueue(Q,p-lchild);EnQueue(Q,p-lchild);if(p-rchild)if(p-rchild) EnQueue(Q,p-rchild);EnQueue(Q,p-rchild); 6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型,编写算法打印出编号为k的结点的双亲和 孩子结点。 【答案答案】int algo2(char bt,int n,int
5、k)if (kn) return 0; if( k=1) printf(“ %c is a rootn”, bt1); else printf(“ %cs parent is %cn”, btk, btk/2);if(2*knext;for(p=hb;p-next; p=p-next);p=p-next);for(j=1,q=ha;jnext;q=q-next; p-next=q-next;p-next=q-next;q-next=hb-nextq-next=hb-next ；free(hb);free(hb); 8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立
6、该二叉树的二叉链表结 构。顺序表T定义如下：struct treeint no; /* 结点按完全二叉树的编号*/ElEMTP data; /* 数据域 */TN; /* N为二叉树T的结点数*/ 【答案答案】BTNodeBTNode *creat_tree(*creat_tree(struct tree TN) ) BTNodeBTNode *pMAX;*pMAX; t=NULL;t=NULL;for(i=0;idata=Ti.data;s-data=Ti.data; s-lchild=s-rchild=NULL;s-lchild=s-rchild=NULL;m=Ti.no;m=Ti.no;
7、 pm=s;pm=s;if(m=1)if(m=1) t=s;t=s;elseelse j=m/2;j=m/2;if(m%2=0)if(m%2=0) pj-lchild=s;pj-lchild=s;elseelse pj-rchild=s;pj-rchild=s;/slse/slse/for/forreturnreturn t;t;/ creat_treecreat_tree 9. 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1，否则返回0。 【答案答案】intint algo1 (LNode *L) ) if(!L-next)if(!L-next) returnreturn 1;1
8、;p=L-next;p=L-next;while(p-next)while(p-next)if(p-dataif(p-data next-data)p-next-data) p=p-next;p=p-next;elseelse returnreturn 0;0; returnreturn 1;1; 10. 假设一线性表由Fibonacci数列的前n（n3）项构成，试以带表头结点的单链表作该线性表的存储结构， 设计算法建立该单链表，且将项数n存储在表头结点中。Fibonacci数列根据下式求得：1 (n=1) f(n)= 1 (n=2)f(n-2)+f(n-1) (n3) 【答案答案】LNode
9、 * 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;inext=s=(LNode *)malloc(sizeof(Lnode);s-data=p-data+q-data; s-next=NULL;p=q;q=s;return h; 万维试题库系统 第 5 页11. 设二叉树T采用二叉链表结构存储，数据元素
10、为字符类型。设计算法将二叉链表中所有data域为小写字母 的结点改为大写 字母。 【答案答案】void algo2(BTNode *bt)if (bt)if(bt-data=aalgo2(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+; s=(LNode *)malloc(sizeof(L
11、node);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 s-next=p; q-next=s; 万维试题库系统 第 6 页14. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data;
12、 数据域struct BSTNode *lchild, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。 【答案答案】int f34(BSTree root)int count;BSTNode *p;p=root;if ( p return count; 15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。 【答案答案】void Del_digit (LNode *h) for(p=h;p-next;)q=p-next; if(q-data=0 free(q); else
13、p=q; 16. 利用栈的基本运算，编写一个算法，实现将整数转换成二进制数输出。 【答案答案】 void returnDtoO(int num) initStack(s); while(n) k=n%2; n=n/2;push(s,k); while(EmptyStack(s) pop(s,k);printf(“%d”,k); 万维试题库系统 第 7 页17. 设二叉树T采用二叉链表结构存储，数据元素为int型，试设计一个算法，若结点左孩子的data域的值大 于右孩子的data域的值，则交换其左、右子树。 【答案答案】void algo2(bitreptr bt)bitreptr x;if (bt)if (bt-lchild bt-lchild= bt-rchild;bt-rchild=x;algo2(bt-lchild);algo2(bt-rchild); 18. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树的深度。 【答案答案】 int Deep(BTNode *bt)if (bt=NULL
