数据结构作业.ppt

数据结构 教材 数据结构 C语言版 严蔚敏吴伟民编著清华大学出版社 计算机科学与技术学院 第二章作业 补充作业 写出按正位序建立一个单链表的算法 2 3在什么情况下用顺序表比链表好 2 11设顺序表va中的数据元素递增有序 试写一算法 将x插入到顺序表的适当位置上 以保持该表的有序性 第三章作业 2 写出检验括号匹配的算法 补充作业 1 设将整数1 2 3 4依次进栈 但只要出栈时栈非空 则可将出栈操作按任何次序夹入其中 请回答下有问题 1 若入栈次序为push 1 pop push 2 push 3 pop pop push 4 pop 则出栈的数字序列为什么 2 请分析1 2 3 4的24种排列中 哪些序列可以通过相应的入出栈得到 3 12写出以下程序段的输出结果 队列中的元素类型QElemType为char Voidmain QueueQ InitQueue Q Charx e y c EnQueue Q h EnQueue Q r EnQueue Q y DeQueue Q x EnQueue Q x DeQueue Q x EnQueue Q a While QueueEmpty Q DeQueue Q y Printf y Printf x 第四章作业 4 3设s IAMASTUDENT t GOOD q WORKER 求 1 StrLength s StrLength t 2 SubString s 8 7 SubString t 2 1 3 Index s A Index s t 4 Replace s STUDENT q 5 Concat SubString s 6 2 Concat t SubString s 7 8 4 7令s aaab t abcabaa u abcaabbabcabaacbacba 试分别求出它们的next函数值和nextval函数值 第五章作业 5 1假设有二维数组A6 8 每个元素用相邻的6个字节存储 存储器按字节编址 已知A的起始存储位置 基地址 为1000 计算 1 数组A的体积 即存储量 2 数组A的最后一个元素a57的第一个字节的地址 3 按行存储时 元素a14的第一个字节的地址 4 按列存储时 元素a47的第一个字节的地址 5 10求下列广义表操作的结果 1 GetHead p h w 4 GetTail a b c d 5 GetHead GetTail a b c d 5 12按教科书5 5节中图5 8所示结点结构 画出下列广义表的存储结构图 并求它的深度 1 a b c d e 2 a b d e f 第六章作业 6 1已知一棵树边的集合为 请画出这棵树 并回答下列问题 1 哪个是根结点 2 哪些是叶子结点 3 哪个是结点G的双亲 4 哪些是结点G的祖先 5 哪些是结点G的子孙 6 哪些是结点E的子孙 7 哪些是结点E的兄弟 哪些是结点F的兄弟 8 结点B和N的层次号分别是什么 9 树的深度是多少 10 以结点C为根的子树的深度是多少 6 3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态 6 12对题6 3所得各种形状的二叉树 分别写出前序 中序和后序遍历的序列 6 15请对如图所示二叉树进行后序线索化 为每个空指针建立相应的前驱或后继线索 6 17阅读下列算法 若有错 则改征之 BiTreeInSucc BiTreeq 已知q是指向中序线索二叉树上某个结点的指针 本函数返回指向 q的后继的指针 r q rchild if r rtag while r rtag r r rchild returnr InSucc 6 19分别画出和下列树对应的各个二叉树 6 21画出和下列二叉树相应的森林 6 22对于6 19题中给出的各树分别求出以下遍历序列 1 先根序列 2 后根序列 补充作业 设权W 10 5 12 7 4 2 建立一棵哈夫曼树 按左子树根结点的权小于等于右子根的权的次序构造 画出建树过程 并求出其带权路径长度WPL 6 27假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列ABCDEFGHIJK 请画出该二叉树 第七章作业 7 7 7 9 7 10 7 11 7 13补充作业 请根据给出的邻接表 画出对应图 并写出从C点开始深度和广度优先遍历序列 画出相应的生成树 7 7对给出如下的无向带权图 1 写出它的邻接矩阵 并按普里姆斯算法求其最小生成树 2 写出它的邻接表 并按克鲁斯卡尔算法求其最小生成树 7 9试列出下图中全部可能的拓扑有序序列 并指出应用7 5 1节中算法求得的是哪一个序列 注意 应先确定其存储结构 7 10对于下图所示的AOE网络 计算各活动弧的e ai 和l aj 函数值 各时间 顶点 的ve vi 和vl vj 函数值 列出各条关键路径 7 11试利用Dijkstra算法求右图中从顶点a到其它各顶点间的最短路径 写出执行算法过程中各步的状态 第九章作业 9 99 19补充作业 在顺序表 2 5 7 10 14 15 18 23 35 41 52 中 1 用顺序查找关键字为23的记录需做次关键码比较 用折半查找需做次关键码比较 2 用顺序查找关键字为12的记录需做次关键码比较 用折半查找需做次关键码比较 9 9已知如下所示长度为12的表 Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec 1 试按表中元素的的顺序依次插入一棵初始为空的二叉排序树 画出插入完成之后的二叉排序树 并求其在等概率的情况下查找成功的ASL 2 若对表中元素先进行排序构成有序表 求在等概率的情况下对此有序表进行折半查找时查找成功的ASL 3 按表中元素顺序构造一棵平衡二叉树 并求其在等概率的情况先查找成功的ASL 9 19选取哈希函数H k 3k MOD11 用开放定址法处理冲突 di i 7k MOD10 1 i 1 2 3 试在0 10的散列地址空间中对关键字序列 22 41 53 46 30 13 01 67 构造哈希表 并求等概率情况下查找成功时的平均查找长度 第十章作业 10 110 310 12 10 1以关键码序列 503 087 512 061 908 170 897 275 653 426 为例 手工执行以下排序算法 写出每一趟排序结束时的关键码状态 1 直接插入排序 2 希尔排序 增量d 1 5 3 快速排序 4 堆排序 5 归并排序 6 基数排序 1 设关键字序列为 96 83 40 11 67 25 写出用下列算法排序时 第一趟结束时的状态 1 希尔排序 d1 3 2 快速排序 3 归并排序 4 堆排序 10 3试问在10 1题所列各种排序方法中 哪些是稳