数据结构算法设计题.doc
《数据结构算法设计题.doc》由会员分享,可在线阅读,更多相关《数据结构算法设计题.doc(10页珍藏版)》请在咨信网上搜索。
1、一、算法设计题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(ij) whi
2、le(i=x)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(Lnode);s-data=y;q-next=s;s-next=q; 4. 二叉排序树的类型定义如下:typedef struct BSTNode 二叉排序树的结点结构int data; 数据域struct BSTNode *lchild, *rchild; 左、右孩子指针BSTNode,*BSTree;设计递归算法,统计一棵二叉排序树T中值小于a的结点个数。【答案】in
3、t 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); if(!p-lchild & !p-rchild) return p;
4、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 (kn) return 0;if( k=1) printf(“ %c is a rootn”, bt1);else printf(“ %cs parent is %cn”, btk, btk/2); if(2*k=n) printf(“ %cs lchild i
5、s %cn”, btk, bt2*k); else printf(“ %c is not lchildn”, btk); if(2*k+1=n) printf(“ %cs 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中,
6、试设计算法根据顺序表T建立该二叉树的二叉链表结构。顺序表T定义如下:struct tree int no; /* 结点按完全二叉树的编号*/ ElEMTP 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=
7、s; /slse /for return t; / creat_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(n3)项构成,试以带表头结点的单链表作该线性表的存储结构,设计算法建立该单链表,且将项数n存储在表头结点中。Fibonacci数列根据下式求得:
8、1 (n=1) f(n)= 1 (n=2) f(n-2)+f(n-1) (n3)【答案】 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;inext=s=(LNode *)malloc(sizeof(Lnode); s-data=p-data+q-data; s-next=NULL
9、; p=q;q=s; return h;11. 设二叉树T采用二叉链表结构存储,数据元素为字符类型。设计算法将二叉链表中所有data域为小写字母的结点改为大写字母。【答案】 void algo2(BTNode *bt) if (bt) if(bt-data=a& bt-datadata-=32; algo2(bt-lchild); algo2(bt-rchild); 12. 假设线性表以带表头结点的循环单链表表示。试设计一个算法,在线性表的第k个元素前插入新元素y。假如表长小于k,则插在表尾。【答案】void Insertlist(LNode *h,int k,ElemType y) q=h;
10、 P=h-next; j=1; while( p!=h & jnext; 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-datanext;s-next=p; q-nex
11、t=s; 14. 二叉排序树的类型定义如下: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;15. 有一带表头结点的单链表,其结点的data域的类型为字符型,编写一个算法删除该链表中的数字字符。【答案】
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 设计
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【1587****927】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【1587****927】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。