《数据结构算法设计题》由会员分享，可在线阅读，更多相关《数据结构算法设计题（10页珍藏版）》请在金锄头文库上搜索。
1、一、算法设计题1. 设二叉树bt采用二叉链表结构存储。试设计一个算法输出二叉树中所有非叶子结点，并求出非叶子结点的 个数。【答案】int count=0;void algo2(BTNode *bt)if (bt)if(bt-lchild | bt-rchild)pri ntf(bt-data);count+;algo2(b t-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(ij)while(i=x
2、)j一一； while(i=x)i+; if(ij) t=aj; aj=ai; ai= t; if(ainext; j=1;while( p!=h & jnext; j+;s=(LNode *)malloc(sizeof(L node);s-data=y;q-next=s;s-next=q;4. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct BSTNode *lchild, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法，统计一棵二叉排序树T中值小于a的结点个数。【答案】int
3、f34(BSTree root)int count;BSTNode *p;p=root;if ( p & p-datalchild);return count;5. 设二叉树T采用二叉链表结构存储，试设计算法求出二叉树中离根最近的第一个叶子结点。(注：结点按从 上往下，自左至右次序编号)【答案】BTNode * Firstleaf(BTNode *bt) InitQueue(Q); 初始化队列Qif(bt)EnQueue(Q,bt);while(!EmptyQueue(Q)DeQueue(Q,p);if(!p-lchild & !p-rchild) return p;if(p-lchild)
4、EnQueue(Q,p-lchild);if(p-rchild) EnQueue(Q,p-rchild);6. 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组中，结点为字符类型编写算法打印出编号为k的 结点的双亲和孩子结点。【答案】int algo2(char bt,int n,int k)if (kn) return 0;if( k=1) printf( “ %c is a rootn” , bt1);else printf( “ %c s parent is %cn” , btk, btk/2); if(2*k=n) printf (“ cs lchild is %cn” , btk
5、, bt2*k); else printf( “ %c is not lchildn” , btk);if(2*k+1=n) printf( “ %c s rchild is %cn”，btk, bt2*k+1);else printf( “ %c is not rchildn” , btk);return 1;7. 编写算法，将非空单链表hb插入到单链表ha的第i(0next; p=p-next);for(j=1,q=ha;jnext;p-next=q-next;q_next=hb_next ;free(hb);8. 设二叉树T已按完全二叉树的形式存储在顺序表T中，试设计算法根据顺序表T建立
6、该二叉树的二叉链表结 构。顺序表T定义如下：struct treeint no;/*结点按完全二叉树的编号*/EIEMTP data; /* 数据域 */TN;/* N为二叉树T的结点数*/【答案】BTNode *creat_tree(struct tree TN) BTNode *pMAX;t=NULL;for(i=0;idata=Ti.data; s_lchild=s_rchild=NULL; m=Ti.no; pm=s;if(m=1) t=s;else j=m/2;if(m%2=0) pj_lchild=s;else pj_rchild=s;/slse/forreturn t;/ cre
7、at_tree9. 编写算法判断带表头结点的单链表L是否是递增的。若递增返回1,否则返回0。【答案】int algo1 (LNode *L)if(!L_next) return 1; p=L_next;while(p-next)if(p-data 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
8、$3)【答案】LNode * Creatlist(LNode *h,int n)h=(LNode *)malloc(sizeof(L node);h-data=n;h-n ext=p=(LNode *)malloc(sizeof(Lnode);p-next=q=(LNode *)malloc(sizeof(L node);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;11. 设二叉树T采用二叉链表结构存储，数
9、据元素为字符类型。设计算法将二叉链表中所有data域为小写字母 的结点改为大写字母。【答案】void algo2(BTNode *bt)if (bt) if(bt-data= a & bt-datadata-=32;algo2(b t-lchild);algo2(b t-rchild);12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法，在线性表的第k个元素前插入新元素y。假 如表长小于k，则插在表尾。【答案】void In sertlist(LNode *h,int k,ElemType y)q=h; P=h-next; j=1;while( p!=h & jnext; j+;s
10、=(LNode *)malloc(sizeof(Lnode);s-data=y;q-next=s;s-next=q;13. 有一带表头结点的单链表，其结点的元素值以非递减有序排列，编写一个算法在该链表中插入一个元素 使得插入后的单链表仍有序。【答案】void algo1 (LNode *H, ElemTp x)s=(LNode *) malloc (sizeof(LNode);s-data=x;q=H; p=H-next;while ( p & p-datanext;s-next=p; q-next=s;14. 二叉排序树的类型定义如下：typedef struct BSTNode 二叉排序树
11、的结点结构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;15. 有一带表头结点的单链表，其结点的data域的类型为字符型，编写一个算法删除该链表中的数字字符。【答案】void Del_digit (LNode *h)for(p=h;p-n ext;)q=p-next; if(q-data= O & q-data nex t=q -nex t;free(q); else 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);
