《数据结构答案习题课1-9》由会员分享，可在线阅读，更多相关《数据结构答案习题课1-9（54页珍藏版）》请在金锄头文库上搜索。
1、第2章 线性表,1顺位序输入n个数据元素的值，建立带表头结点的单链表-1 void CreateList(LinkList ,1顺位序输入n个数据元素的值，建立带表头结点的单链表-2 void CreateList(LinkList ,1顺位序输入n个数据元素的值，建立带表头结点的单链表同学实例1，请问程序正确吗？ void CreateList(LinkList ,1顺位序输入n个数据元素的值，建立带表头结点的单链表同学实例2，请问程序正确吗？ void CreateList(LinkList ,1顺位序输入n个数据元素的值，建立带表头结点的单链表同学实例3，请问程序正确吗？ void Cr
2、eateList(LinkList ,2有一个带头指针的单链表，写出在其值为x的结点之后插入m个结点的算法。-1 Status insertm(LinkList ,2有一个带头指针的单链表，写出在其值为x的结点之后插入m个结点的算法。-2 Status insertm(LinkList /插入到p之后 ； return OK； ,2有一个带头指针的单链表，写出在每个其值为x的结点之后插入m个结点的算法。-3 Status insertm(LinkList return OK； ,3假设在长度大于1的单循环链表，既无头结点，也无头指针，S为指向链表中某个结点的指针，试设计删除结点S的直接前驱结点
3、的算法。 同学实例，请问程序正确吗？ Status deleteprior(CirLinkList ,3假设在长度大于1的单循环链表，既无头结点，也无头指针，S为指向链表中某个结点的指针，试设计删除结点S的直接前驱结点的算法。-1 void deleteprior(LinkList /释放结点 ,3假设在长度大于1的单循环链表，既无头结点，也无头指针，S为指向链表中某个结点的指针，试设计删除结点S的直接前驱结点的算法。-2 void deleteprior(LinkList ,4设计实现在单链表中删除值相同的多余结点的算法。 Status deletesame(LinkList /t从p后查找
4、相同结点 ,第4章 串,2设单链表中存放着n个字符，试设计算法判断字符串是否中心对称。 int String(Linklist ,第6章 树和二叉树,1.试找出分别满足下面条件的所有二叉树 （1）前序序列和中序序列相同 空二叉树 或仅有一个结点的二叉树 或任一结点均无左子树的非空二叉树 （2）中序序列和后序序列相同 空二叉树 或仅有一个结点的二叉树 或任一结点均无右子树的非空二叉树 （3）前序序列和后序序列相同 空二叉树 或仅有一个结点的二叉树,2.已知一棵二叉树的中序遍历序列为DBHEAFICG，后序遍历序列为DHEBIFGCA，试画出该二叉树。 中序：DBHEAFICG 后序：DHEBIF
5、GCA,3.编程统计二叉树中的结点个数。 int num (BiTree *root) int num1, num2; if (root=NULL) return(0); else if ( 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写出下
6、图的拓扑序列。,V2V1V3V6V5V4 V2V3V1V6V5V4,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试利用带洛伊德算法，写出下图相应
7、的带权邻接矩阵的变化。,4试利用带洛伊德算法，写出下图相应的带权邻接矩阵的变化。,第9章 查找,1.设计出在递增有序的数组A1.n中查找值为x的元素的二分查找算法。 学生作业： 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 BSear
8、ch( DataType A , KeyType x ) int low=0, high=n-1, mid; while(lowAmid) 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),189,78,350,29,208,3
9、,100,240,345,1 2 6 1 2 1 1 2 1 4 4 4 6 9,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,D
10、ec （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, M
11、ay, 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, F
12、eb, 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,Feb Jan,Feb Jan Mar,Apr Feb Jan Mar,已知长度为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）插入300 2）插入70 3）插入30 4）删除150,1）插入300,260,300,2）插入70,100,50,10 40,150,60 80,260 300,50,70,200,2）插入70,2）插入70 学生作业？,3）插入30,100,10 40,150,260 300,50 70,50 70,30,100,50,30,200,70,260,4）删除150,100,150,260 300,100,50,300,200,30,70,
