数据结构答案习题课1-9

第2章线性表,1顺位序输入n个数据元素的值，建立带表头结点的单链表-1voidCreateList(LinkList,1顺位序输入n个数据元素的值，建立带表头结点的单链表-2voidCreateList(LinkList,1顺位序输入n个数据元素的值，建立带表头结点的单链表同学实例1，请问程序正确吗？voidCreateList(LinkList,1顺位序输入n个数据元素的值，建立带表头结点的单链表同学实例2，请问程序正确吗？voidCreateList(LinkList,1顺位序输入n个数据元素的值，建立带表头结点的单链表同学实例3，请问程序正确吗？voidCreateList(LinkList,2有一个带头指针的单链表，写出在其值为x的结点之后插入m个结点的算法。-1Statusinsertm(LinkList,2有一个带头指针的单链表，写出在其值为x的结点之后插入m个结点的算法。-2Statusinsertm(LinkList/插入到p之后；returnOK；,2有一个带头指针的单链表，写出在每个其值为x的结点之后插入m个结点的算法。-3Statusinsertm(LinkListreturnOK；,3假设在长度大于1的单循环链表，既无头结点，也无头指针，S为指向链表中某个结点的指针，试设计删除结点S的直接前驱结点的算法。同学实例，请问程序正确吗？Statusdeleteprior(CirLinkList,3假设在长度大于1的单循环链表，既无头结点，也无头指针，S为指向链表中某个结点的指针，试设计删除结点S的直接前驱结点的算法。-1voiddeleteprior(LinkList/释放结点,3假设在长度大于1的单循环链表，既无头结点，也无头指针，S为指向链表中某个结点的指针，试设计删除结点S的直接前驱结点的算法。-2voiddeleteprior(LinkList,4设计实现在单链表中删除值相同的多余结点的算法。Statusdeletesame(LinkList/t从p后查找相同结点,第4章串,2设单链表中存放着n个字符，试设计算法判断字符串是否中心对称。intString(Linklist,第6章树和二叉树,1.试找出分别满足下面条件的所有二叉树（1）前序序列和中序序列相同空二叉树或仅有一个结点的二叉树或任一结点均无左子树的非空二叉树（2）中序序列和后序序列相同空二叉树或仅有一个结点的二叉树或任一结点均无右子树的非空二叉树（3）前序序列和后序序列相同空二叉树或仅有一个结点的二叉树,2.已知一棵二叉树的中序遍历序列为DBHEAFICG，后序遍历序列为DHEBIFGCA，试画出该二叉树。中序：DBHEAFICG后序：DHEBIFGCA,3.编程统计二叉树中的结点个数。intnum(BiTree*root)intnum1,num2;if(root=NULL)return(0);elseif(root-lchild=NULL,4.已知W=2,3,4,7,8,9，试构造关于W的一棵哈夫曼树，并求WPL,9,7,8,2,3,4,WPL=7*2+8*2+9*2+4*3+2*4+3*4=14+16+18+12+8+12=80,9,5,18,15,33,5把如图所示的树转化成二叉树。,6.画出和下列二叉树相应的森林。,第7章图,1请画出下图从定点A出发的广度优先生成树和深度优先生成树。,2写出下图的拓扑序列。,V2V1V3V6V5V4V2V3V1V6V5V4,3.找出下图从A到C的最短路径,(A,B,D,C),(A,B,D,C),(A,B,D),(A,B),S,E,C,D,B,Vj,17(A,B,D,E),17(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),B,i=4,i=3,i=2,i=1,从A到各终点的权值和最短路径,终点,4.试利用带洛伊德算法，写出下图相应的带权邻接矩阵的变化。,4试利用带洛伊德算法，写出下图相应的带权邻接矩阵的变化。,4试利用带洛伊德算法，写出下图相应的带权邻接矩阵的变化。,第9章查找,1.设计出在递增有序的数组A1.n中查找值为x的元素的二分查找算法。学生作业：intSearch_Bin(SSTableST,keyTypex)low=1;high=ST.length;while(low=high)mid=low+high)/2;if(x=ST.elemmid.x)returnmid;elseif(xST.elemmid.x)high=mid-1;elselow=mid+1;return0;/Serch_Bin,intBSearch(DataTypeA,KeyTypex)intlow=0,high=n-1,mid;while(lowAmid)low=mid+1;return-1;/查找失败,1.设计出在递增有序的数组A1.n中查找值为x的元素的二分查找算法。,2.已知哈希表地址空间为0.14，哈希函数为H(k)=kmod13，采用线性探查法处理冲突，将下列各数依次存入该散列表中。240,29,345,189,100,20,21,35,3,208,78,99,45,350性探测法：Hi=（H（key）+i）MODmi=1,2,k(km),189,78,350,29,208,3,100,240,345,12612112144469,20,99,35,21,45,计算余数：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，试构造一棵二叉排序树。,10,3,18,2,19,8,7,9,4.已知长度为12的表如下：Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec（1）建立相应的二叉排序树（2）建立相应的平衡二叉树,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,Apr,Aug,Dec,Nov,Feb,Jan,Sep,May,June,July,Oct,Mar,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,Jan,Feb,Mar,Apr,May,June,July,Aug,Jan,Aug,Mar,Apr,May,June,July,Feb,Sep,Oct,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,Jan,Aug,Mar,Apr,May,June,July,Feb,Oct,Sep,Nov,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,Jan,Aug,Mar,Apr,May,Feb,Oct,Sep,Nov,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,Jan,Aug,Mar,Apr,May,June,July,Feb,Oct,Sep,Nov,Dec,Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,已知长度为12的表如下，建立相应的4阶B-树：Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,Jan,FebJan,FebJanMar,AprFebJanMar,已知长度为12的表如下，建立相应的4阶B-树：Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,已知长度为12的表如下，建立相应的4阶B-树：Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec,5.对于下面3阶B树依次执行下列操作，画出每步的操作结果1）插入3002）插入703）插入304）删除150,1）插入30