《数据结构答案习题课19》由会员分享，可在线阅读，更多相关《数据结构答案习题课19（54页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表1 1顺位序输入顺位序输入n n个数据元素的值，建立带表头结点个数据元素的值，建立带表头结点的单链表的单链表-1-1void void CreateList(LinkListCreateList(LinkList &L , &L ,intint n) n) L=(L=(LinkList)malloc(sizeof(LNodeLinkList)malloc(sizeof(LNode);); L-next=NULL; /L-next=NULL; /建立带表头结点的单链表建立带表头结点的单链表 LEndLEnd=L; =L; / /设置链表尾标志设置链表尾标志 for(i=1; i=n
2、; i+) /for(i=1; inext=NULL; p-next=NULL; / /生成新结点生成新结点scanf(&pscanf(&p-data); /-data); /输入元素值输入元素值LEndLEnd-next=p; /-next=p; /插入到表尾插入到表尾LEndLEnd=p;=p; 1 1顺位序输入顺位序输入n n个数据元素的值，建立带表头结点个数据元素的值，建立带表头结点的单链表的单链表-2-2void void CreateList(LinkListCreateList(LinkList &L , &L ,intint n) n) L=(L=(LinkList)mallo
3、c(sizeof(LNodeLinkList)malloc(sizeof(LNode);); L-next=NULL; /L-next=NULL; /建立带表头结点的单链表建立带表头结点的单链表 LEndLEnd=L; =L; / /设置链表尾标志设置链表尾标志 for(i=1; i=n; i+) /for(i=1; idata); /-data); /输入元素值输入元素值LEndLEnd-next=p; /-next=p; /插入到表尾插入到表尾LEndLEnd=p;=p; p-next=NULL;p-next=NULL; 1 1顺位序输入顺位序输入n n个数据元素的值，建立带表头结点个数据
4、元素的值，建立带表头结点的单链表的单链表同学实例同学实例1 1，请问程序正确吗？，请问程序正确吗？void void CreateList(LinkListCreateList(LinkList &L , &L ,intint n) n) L=(L=(LinkList)malloc(sizeof(LNodeLinkList)malloc(sizeof(LNode);); L-next=NULL; L-next=NULL; for(i=1; i=n; i+)for(i=1; idata); -data); p-next=L-next;p-next=L-next; L-next=p; L-next
5、=p; L=L-next;L=L-next; 1 1顺位序输入顺位序输入n n个数据元素的值，建立带表头结点个数据元素的值，建立带表头结点的单链表的单链表同学实例同学实例2 2，请问程序正确吗？，请问程序正确吗？void void CreateList(LinkListCreateList(LinkList &L , &L ,intint n) n) L=(L=(LinkList)malloc(sizeof(LNodeLinkList)malloc(sizeof(LNode);); L-next=NULL; L-next=NULL; for(i=1; i=n; i+)for(i=1; idat
6、a); -data); L-next=p;L-next=p; p-next=null; p-next=null; 1 1顺位序输入顺位序输入n n个数据元素的值，建立带表头结点个数据元素的值，建立带表头结点的单链表的单链表同学实例同学实例3 3，请问程序正确吗？，请问程序正确吗？void void CreateList(LinkListCreateList(LinkList &L , &L ,intint n) n) L=(L=(LinkList)malloc(sizeof(LNodeLinkList)malloc(sizeof(LNode);); L-next=NULL; L-next=NU
7、LL; for(i=1; i=n; i+)for(i=1; idata); -data); L-next=p;L-next=p; p-next=L-next; p-next=L-next; 2有一个带头指针的单链表，写出在其值为有一个带头指针的单链表，写出在其值为x的结点之后插的结点之后插入入m个结点的算法。个结点的算法。-1Status insertm(LinkList &head, int x, int m) LNode *p=head-next,*q=*s=NULL; while(p!=NULL & p-data!=x) p=p-next; /结点定位结点定位 if(p=NULL) ex
8、it(ERROR); /没有找到结点没有找到结点 else q=p-next; /保留断点保留断点 for(int i=1; idata); /新结点赋值新结点赋值 p-next=s; /插入到插入到p之后之后 p=s; /p后移一个结点后移一个结点 p-next=q; /连接断点连接断点 return OK;2有一个带头指针的单链表，写出在其值为有一个带头指针的单链表，写出在其值为x的结点之后插的结点之后插入入m个结点的算法。个结点的算法。-2Status insertm(LinkList &head, int x, int m) LNode *p=head-next,*s=NULL; wh
9、ile(p!=NULL & p-data!=x) p=p-next; /结点定位结点定位 if(p=NULL) exit（ERROR）; /没有找到结点没有找到结点 else for(int i=1; idata); /新结点赋值新结点赋值 s-next=p-next; p-next=s; /插入到插入到p之后之后 ； return OK；2有一个带头指针的单链表，写出在有一个带头指针的单链表，写出在每个每个其值为其值为x的结点之的结点之后插入后插入m个结点的算法。个结点的算法。-3Status insertm(LinkList &head, int x, int m) LNode *p=he
10、ad-next,*s=*q=NULL; while(p!=NULL) if (p-data!=x) p=p-next; /结点定位结点定位 else q=p-next; for(int i=1; idata); /新结点赋值新结点赋值 s-next=p-next; p-next=s; /插入到插入到p之后之后 p=q; return OK；3假设在长度大于假设在长度大于1的单循环链表，既无头结点，也无的单循环链表，既无头结点，也无头指针，头指针，S为指向链表中某个结点的指针，试设计删除结为指向链表中某个结点的指针，试设计删除结点点S的直接前驱结点的算法。的直接前驱结点的算法。 同学实例，请问程
11、序正确吗？同学实例，请问程序正确吗？Status deleteprior(CirLinkList &s) p-next=s; if (p) e=p-data; m-next=p; m-next=s; free(q); return OK; return Error;3假设在长度大于假设在长度大于1的单循环链表，既无头结点，也无的单循环链表，既无头结点，也无头指针，头指针，S为指向链表中某个结点的指针，试设计删除结为指向链表中某个结点的指针，试设计删除结点点S的直接前驱结点的算法。的直接前驱结点的算法。-1void deleteprior(LinkList &s) LNode *q=*r=s;
12、while(q-next!=s) q=q-next; /定位定位s前驱结点前驱结点qr=q; while(r-next!=q) r=r-next; /定位定位q前驱结点前驱结点rr-next=s; /删除结点删除结点 free(q); /释放结点释放结点3假设在长度大于假设在长度大于1的单循环链表，既无头结点，也无的单循环链表，既无头结点，也无头指针，头指针，S为指向链表中某个结点的指针，试设计删除结为指向链表中某个结点的指针，试设计删除结点点S的直接前驱结点的算法。的直接前驱结点的算法。-2void deleteprior(LinkList &s) LNode *q=*r=s; while(
13、q-next-next!=s) q=q-next; /定位定位s前驱结点的前驱结点前驱结点的前驱结点qr=q-next; q-next=s;free(r); 4设计实现在单链表中删除值相同的多余结点的算法。设计实现在单链表中删除值相同的多余结点的算法。Status deletesame(LinkList &head) t=p=head-next; while(p!=NULL) /用用p循环链表循环链表 s=t;/ 定义定义s为删除结点的前驱为删除结点的前驱 t=t-next; /定义定义t为值相同结点为值相同结点 while(t!=NULL) /删除所有与删除所有与p同的结点同的结点t if(
14、t-data!=p-data) /t值不同值不同 s=t; t=t-next; /t后移后移 else if(t-data=p-data) /t值相同值相同 s-next=t-next; free(t); /删除删除t t=s-next; p=p-next; /p后移后移 t=p; /t从从p后查找相同结点后查找相同结点 第4章 串2设单链表中存放着设单链表中存放着n个字符，试设计算法判断字符串是否个字符，试设计算法判断字符串是否中心对称。中心对称。int String(Linklist &h, int n) int top=1,pd=1; /定义为对称定义为对称 LNode *p=h; St
15、ack s; for(int i=1;idata; p=p-next; top+ ; if(n%2!=0) p=p-next; top-;/总数为奇数总数为奇数 while(p!=NULL & pd=1) if(p-data=stop) /后半段与栈内比较后半段与栈内比较 p=p-next; top-; /出栈出栈 else pd=0; /不对称不对称 return(pd);第第6章章 树和二叉树树和二叉树1.试找出分别满足下面条件的所有二叉树试找出分别满足下面条件的所有二叉树（1）前序序列和中序序列相同）前序序列和中序序列相同 空二叉树 或仅有一个结点的二叉树 或任一结点均无左子树的非空二叉
16、树（2）中序序列和后序序列相同）中序序列和后序序列相同 空二叉树 或仅有一个结点的二叉树 或任一结点均无右子树的非空二叉树（3）前序序列和后序序列相同）前序序列和后序序列相同 空二叉树 或仅有一个结点的二叉树2.已已 知知 一一 棵棵 二二 叉叉 树树 的的 中中 序序 遍遍 历历 序序 列列 为为DBHEAFICG，后后序序遍遍历历序序列列为为DHEBIFGCA，试画出该二叉树。，试画出该二叉树。中序：中序：DBHEAFICG后序：后序：DHEBIFGCAABCDFEGHI3.编程统计二叉树中的结点个数编程统计二叉树中的结点个数。int num (BiTree *root)int num1,
17、 num2;if (root=NULL) return(0);else if ( root-lchild=NULL &root-rchild=NULL)return(1);else num1=num(root-lchild);num2=num(root-rchild); return (num1+num2+1);4.已知已知W=2,3,4,7,8,9，试构造关于，试构造关于W的一棵的一棵哈夫曼树，并求哈夫曼树，并求WPL978234WPL=7*2+8*2+9*2+4*3+2*4+3*4=14+16+18+12+8+12=80951815335把如图所示的树转化成二叉树。把如图所示的树转化成二叉
18、树。 6.画出和下列二叉树相应的森林。画出和下列二叉树相应的森林。 第第7章章 图图1请请画画出出下下图图从从定定点点A出出发发的的广广度度优优先先生生成成树和深度优先生成树。树和深度优先生成树。ABECFD深度优先深度优先2：BCFDEAADBCFE广度优先：广度优先：深度优先深度优先1：ABCFED2写出下图的拓扑序列。写出下图的拓扑序列。V5V2V1V3V4V6V2V1V3V6V5V4V2V3V1V6V5V43.找出下图从A到C的最短路径 105522218BCDEA(A, B, D, C)(A, B, D, C)(A, B, D)(A, B)SECDBVj17(A, B, D, E)1
19、7(A, B, D, E)E-15(A, B, D)D-17(A, B, D, C)18(A, C)18(A, C)C-10(A, B)Bi=4i=3i=2i=1从A到各终点的权值和最短路径终点105522218BCDEA4. 试利用带洛伊德算法，写出下图相应的带权邻接矩阵的变化。 4试试利利用用带带洛洛伊伊德德算算法法，写写出出下下图图相相应应的的带带权邻接矩阵的变化。权邻接矩阵的变化。 4试试利利用用带带洛洛伊伊德德算算法法，写写出出下下图图相相应应的的带带权邻接矩阵的变化。权邻接矩阵的变化。 第第9章章 查找查找1.设计出在递增有序的数组A1.n中查找值为x的元素的二分查找算法。学生作业
20、：int Search_Bin(SSTable ST, keyType x) low=1; high=ST.length; while (low=high) mid= low+high)/2; if (x=ST.elemmid.x) return mid; else if (x ST.elemmid.x) high=mid-1; else low=mid+1; return 0; /Serch_Bin int BSearch( DataType A , KeyType x )int low=0, high=n-1, mid;while(low=high)mid=(low+high)/2;if(
21、x=Amid) return mid; /查找成功else if(xAmid) low=mid+1;return -1;/查找失败 1.设计出在递增有序的数组A1.n中查找值为x的元素的二分查找算法。2.已知哈希表地址空间为0.14，哈希函数为H(k)=k mod 13，采用线性探查法处理冲突，将下列各数依次存入该散列表中。 240,29,345,189,100,20,21,35,3,208,78,99,45,350 性探测法：Hi=（H（key）+ i）MOD m i=1,2,k(km)18978 350 292083100240 3451 2 6 1 2 1 1 2 1 4 4 4 6 9
22、2099352145计算余数：计算余数：240(6), 29(3), 345(7), 189(7), 100(9), 20(7), 21(8), 35(9), 3(3), 208(0), 78(0), 99(8), 45(6), 350(12) 3.对于给定结点的关键字的集合K=10, 18, 3, 8, 19, 2, 7, 9，试构造一棵二叉排序树。103182198794.已知长度为12的表如下：Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec（1）建立相应的二叉排序树（2）建立相应的平衡二叉树 Jan, Feb, Mar, Apr, Ma
23、y, June, July, Aug, Sep, Oct, Nov, DecAprAugDecNovFebJanSepMayJuneJulyOctMarJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanFebMarAprMayJuneJulyAugAugAprFebAugAprFebJanAugMarAprMayJuneJulyFebSepOctJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanAugMarAprMayJuneJulyFebOc
24、tSepNovJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanAugMarAprMayJuneJulyFebOctSepNovJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DecJanAugMarAprMayJuneJulyFebOctSepNovDecJan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec已知长度为已知长度为12的表如下，建立相应的的表如下，建立相应的4阶阶B-树：树
25、： Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecJanFeb JanFeb Jan MarApr Feb Jan Mar AprJan Mar FebAprJanFeb JuneMar May AprJan Mar MayFebAprJan June Mar MayFeb已知长度为已知长度为12的表如下，建立相应的的表如下，建立相应的4阶阶B-树：树： Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecAprJanFeb JuneMar May AprJan JulyFeb JuneMar M
26、ay Apr AugJan JulyFeb JuneMar May Apr AugJan JulyFeb JuneMar May Sep Apr AugJan JulyFeb JuneMar May Oct Sep Apr AugJan JulyFeb June MayMarOct Sep 已知长度为已知长度为12的表如下，建立相应的的表如下，建立相应的4阶阶B-树：树： Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,DecApr AugJan JulyFeb June MayMarOct Sep Apr Aug Jan JulyFeb June
27、MayMar Nov Oct Sep Apr Aug Dec Jan JulyFeb June MayMar Nov Oct Sep 5. 对于下面3阶B树依次执行下列操作，画出每步的操作结果 1）插入300 2）插入70 3）插入30 4）删除150 1005020010 4015026060 801）插入3001005020010 4015026060 802603002）插入701005010 4015060 80260 300507060802002）插入702）插入70 学生作业？3）插入3010010 40150260 30050 70 50 7030 10050302007060802604）删除150100150260 300 10050104060803002003070
