数据结构试题大题编程及参考答案(6页).doc

上传人:1595****071 文档编号:37079293 上传时间:2022-08-30 格式:DOC 页数:6 大小:128KB
返回 下载 相关 举报
数据结构试题大题编程及参考答案(6页).doc_第1页
第1页 / 共6页
数据结构试题大题编程及参考答案(6页).doc_第2页
第2页 / 共6页
点击查看更多>>
资源描述

《数据结构试题大题编程及参考答案(6页).doc》由会员分享,可在线阅读,更多相关《数据结构试题大题编程及参考答案(6页).doc(6页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、-数据结构试题大题编程及参考答案-第 6 页数据结构考试题参考答案1、设顺序表L中的数据元素递增有序。试写一算法,将数据元素x插入到顺序表L的适当位置,以保持该表的有序性。解:存储结构为:typedef struct SeqList DataType *data; int MaxLen; int len;SeqList;算法如下:void insertLx(SeqList &L, DataType x) if(L.len=L.maxlen) return; int i=L.len-1;while(i=0 & xnext & p-next-data!=x) p=p-next; /找x的前驱结点p

2、;if(!p-next) return; / 若不存在结点x,则返回;q=new Lnode;q-data=y; q-next=p-next; p-next=q;3、试写一个算法,统计带头指针的单链表L的元素个数。解:存储结构如下:typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;算法如下:int length(LinkList L) int len=0;Lnode *p=L;while(p) len+; p=p-next; return len;注:如果单链表是带头结点的,则算法如下:int leng

3、th(LinkList L) int len=0;Lnode *p=L-next;while(p) len+; p=p-next; return len;4、试写一个算法,在带头结点的单链表L的第k个结点后插入一个结点x。解:存储结构如下:typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;算法如下:void insert_after_k( LinkList L, int k, ElemType x) if(k0) return; Lnode *q, *p=L;int i=0;while(p & inex

4、t; /找到第k个结点p;if(!p) return; /若不存在第k个结点,则返回;q=new Lnode; q-data=x; q-next=p-next; p-next=q;注:如果是在L的第k个结点前插入一个结点,则找第k-1个结点p,然后插入。、试写一个算法,在带头结点的单链表中删除所有的数据元素为x的结点。解:存储结构如下:typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;算法如下:void Delete_all_x(LinkList L, Elemtype x) Lnode *p, *q;

5、 p=L; while(p) if(p-next & p-next-data=x)q=p-next; p-next=q-next; delete q; else p=p-next;注意:要删除所有的值为x的结点。、假设一个单循环链表的数据域为整型,设计一个算法,求该表中所有结点的数据之和。解:存储结构如下:typedef struct LnodeElemType data; struct Lnode *next;Lnode, *LinkList;假设带头结点,且指向头结点,则算法如下:int sum_Of_Data(LinkList L) int s=0; Lnode *p=L-next;wh

6、ile(p!=L) s+=p-data; p=p-next; return s; 假设不带头结点,且指向循环链表中任何一个结点,则算法如下:int sum_of_data(LinkList L) int s=0; Lnode *p=L; if(L) s+=p-data; p=p-next; while(p!=L) s+=p-data; p=p-next; return s;注:以上两种情形,只要给出其中一种情形的解即可。、假设二叉树用二叉链表存储,设计一个算法,求二叉树的结点个数。解:存储结构如下:typedef struct bitnodeElemType data; struct bitn

7、ode *lchild, *rchild;bitnode, *bitree;算法如下:int nodes(bitree T) if(!T) return 0; else return (1+nodes(T-lchild)+nodes(T-rchild);、写一个算法,建立二叉树的二叉链表。解:存储结构如下:typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下:void creat_bitree(bitree &T) /按扩展

8、的先序序列输入结点,输入表示空。ElemType ch; cinch;if(ch=#) T=0;else T=new bitnode; T-data=ch;creat_bitree(T-lchuild);creat_bitree(T-rchild);或者写成以下算法:bitree creat_bitree(void) /按扩展的先序序列输入结点,输入表示空。bitree T;ElemType ch; cinch;if(ch=#) T=0;else T=new bitnode; T-data=ch;creat_bitree(T-lchuild);creat_bitree(T-rchild);re

9、turn T;9、假设一棵二叉树的先序序列为EBADCFHGIKJ,中序序列为ABCDEFGHIJK,请画出该二叉树,并写出后序序列。解:该二叉树如下:后序序列为:ACDBGJKIHFE。10、假设一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF,请画出该二叉树,并写出其先序序列和后序序列。解:该二叉树如下:先序序列为:ABDEGHJCFI;后序序列为:DGJHEBIFCA。11、编写一个递归算法,将用二叉链表表示的二叉树的所有结点的左、右子树交换。解:存储结构如下:typedef char ElemType;typedef struct bitnodeElemTyp

10、e data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下:void exchange(bitree &T)if(!T) return; bitree temp;temp=T-lchild;T-lchild=T-rchild;T-rchild=temp;exchange(T-lchild);exchange(T-rchild);12、试写出二叉链表表示的二叉树的先序遍历的非递归算法。解:存储结构如下:typedef char ElemType;typedef struct bitnodeElemType data; struct bitnode *lchild, *rchild;bitnode, *bitree;算法如下:void preorder(bitree T) /先序遍历,当前结点入栈。#define MaxNum 20bitree stackMaxNum;int top=0; /指向栈顶的下一位置。bitnode *p;p=T;while(p | top0)while(p) coutdata; stacktop+=p; p=p-lchild; if(top0) p=stack-top; p=p-rchild; coutendl;注:这里假设访问结点即为输出结点。若访问结点是其它操作,则换成相应的函数便可。

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 教育专区 > 单元课程

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁