数据结构问题解答.doc

4、若有n个元素的序列近似有序，即除掉少数K个元素后是有序序列且Kdata = pj-data) pi = pi-next;pj = pj-next; else / 失配时回溯到主串的下一个字符ps = ps-next;pi = ps;pj = t;/ 如果匹配成功返回主串中匹配的起始位置if (pj = NULL)return ps;elsereturn NULL;1分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。【参考解答】对初始状态为递增序列的表按递增顺序排序，（1）直接插入排序最省时间。因为算法此时总的比较次数为n-1，移动次数为0，为最好情况，是最省时间的。（2）快速排序最费时间。待排序列有序时，快速排序退化为冒泡排序，时间复杂度为O(n2)。而堆排序和归并排序的时间复杂度都是O(nlogn)。所以，此时快速排序最费时间。4只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（KN），列出3种速度快的方法名称与原因。【分析】总的思路是尽量避免对所有N个元素排序，从而提高算法的速度。因为对N个元素进行快速排序、堆排序或归并排序，（平均）时间复杂度均为O(pNlogN)，p为某个常数，所以，所谓速度快的方法，时间复杂度应该更低。 另外，关于方法名称，求前K个最大元素并非我们（本科阶段）通常所学的经典算法，因此所谓名称，也只能借用其他算法之名。因此，可以认为下面几种方法分别借用了（1）简单选择排序，（2）插入排序，（3）、（4）堆排序，（5）快速排序划分算法。【参考解答】几种可能的方法如下：（1）K趟简单选择排序，依次选出最大的K个元素，时间复杂度O(KN)。由于K远小于N，特别是当Kplog2N时（其中p为某个常数），该算法要比对整个序列排序的方法更快。（2）首先取K个元素，逆序排序，作为已经求得的K个极大元素的递减序列S。对其余N-K个元素，逐个与该序列的最小（最后一个）元素Sk比较，如果小于Sk则丢弃，如果大于Sk则从序列S中删除Sk，然后将该元素插入序列S合适的位置，保持整个序列逆序。K个元素排序的时间复杂度为O(KlogK) ，其余N-K个元素都至少进行一次比较，最坏情况下总共要花费O(K(N-K)的时间插入序列S中。所以总的时间复杂度为O(KlogK+K(N-K)。若K远小于N，时间复杂度近似为O(KN)。用堆代替方法（2）中的序列S，可以得到：（3）首先取K个元素，建立小顶堆H，堆顶H1为K个元素中最小元素。对其余N-K个元素，逐个与堆顶元素H1比较，若小于H1则丢弃，若大于H1，则以该元素替换H1，并执行一次筛选，将H重新调整为小顶堆。最后，可以H中得到N个元素中最大的K个元素，在已建立的堆H的基础上，对其中的K个元素逆序排序，得到最终结果。 开始时，建立K个元素的堆，时间复杂度为O(K)。对其余N-K个元素的处理，最坏情况下，除了一次比较，还包括一个从堆顶（根）到叶子的筛选过程（O(logK)），时间复杂度为O(N-K)logK)。所以，该方法总的时间复杂度为O(K+(N-K)logK)。若K远小于N，时间复杂度近似为O(NlogK)。（4）利用K趟堆排序，首先调整N个元素为大顶堆，然后输出堆顶最大元素，此后通过筛选可以依次求得其余K-1个最大元素，从而得到最大的K个元素。因为，建堆过程的比较次数不超过4N，每次筛选所需的比较次数不超过2logN，故总的时间复杂度为O(N+KlogN)。（5）利用快速排序中的划分算法，根据划分后枢轴记录的位置，舍弃不包含最大的K个元素的子序列，仅对包含最大的K个元素的子序列继续进行划分，直到该子序列足够小，最直接排序，从而得到最大的K个元素。假设在最好情况下，每次划分可以舍弃一半的元素，那么，整个划分过程所需要的比较次数为N+N/2+N/4+2KN+N/2+N/4+12N，考虑到最后要对K个最大的元素进行排序，总的比较次数不超过2N+pKlogK，其中p为某个常数。故算法在最好情况下的时间复杂度为O(N+KlogK)。但在最坏情况下，每次划分只能舍弃一个元素，比较次数达到N+(N-1)+(N-K) = N(N+1)/2-K(K+1)/2，时间复杂度为O(N2-K2)，由于K远小于N，可近似为O(N2)。不过，通过调整选取轴记录的方法（如采用“三者取中”，以及其他精心构造的方法），可以减少（甚至消除）最坏情况出现的可能性。故可以认为，该方法的平均时间复杂度为O(N+KlogK)。总结一下上面几种方法的时间复杂度：序号时间复杂度最好情况最坏情况K远小于N时K=N/2时（1）O(KN)O(KN)O(KN)O(KN)O(N2)（2）O(KlogK+K(N-K)O(KlogK+N-K)O(KlogK+K(N-K)O(KN)O(N2)（3）O(K+(N-K)logK)O(N+K)O(K+(N-K)logK)O(NlogK)O(NlogN)（4）O(N+KlogN)O(N+K)O(N+KlogN)O(N+KlogN)O(NlogN)（5）O(N+KlogK)O(N+KlogK)O(N2-K2)O(N+KlogK)O(NlogN)三、数学归纳法证明非空满K叉树的叶子结点数目为(K-1)N+1，其中N为分支结点数目【分析】思路应该是比较清楚，只要注意满K叉树的基本形式，注意到树中只有分支结点和叶子结点，其中分支结点必有K个孩子。由于满K叉树中分支结点数N是一层一层增长的，存在K倍关系，可根据树的高度归纳得出结论。但是，实际上，即便不是满K叉树，只要能够保证树中只有度为K的结点和叶子结点，也可以得到相同的结论。而此时如果用归纳法证明，就可以根据分支结点数N进行递推（每增加一个分支结点，会使叶子节点数增加K-1），这样会更自然一些。也许这才是该问题令人困惑的地方。下面，首先用归纳法证明如果K叉树只包含叶子结点和N个度为K的结点，则叶子节点有(K-1)N+1个。由于任何非空的满K叉树一定满足上述条件，所以在题目给定的条件下，结论成立。证明思路仅供参考。【参考解答】证明：首先，用归纳法证明如果一棵K叉树只包含叶子结点和N个度为K的结点，则叶子节点数为(K-1)N+1.当度为K的结点数N=0时，叶子结点数=(K-1)N+1=1，结论成立.假设度为K的结点数N=n时结论成立，即有叶子结点数=(K-1)n+1.当N=n+1时，与N=n相比，可以任选一个叶子结点扩展为度为K的分支结点，因此，叶子结点数增加了K-1个. 此时叶子结点数=(K-1)n+1+(K-1)=(K-1)(n+1)+1，结论成立。所以，一颗只包含叶子结点和N个度为K的结点的K叉树，叶子结点数为(K-1)N+1.因为，任何非空的满K叉树中只有叶子结点和度为K的分支结点，故原命题成立。即：非空满K叉树叶子结点数为(K-1)N+1.五、有一个由英文书目构成的文件（书名不定长度，以“；”为分割符）；读入该文件，对这一书目单按字典排序，将结果以文件方式存储。编程实现之。【参考解答】这个题目考的是程序设计中的文件操作、排序等内容。其中的难点是书名不定长度、书名个数不确定以及字符串排序。相比之下，跟数据结构的关系并不大，与程序设计语言的选择却密切相关。假如必须用C语言，“书名不定长度”可能会带来一点麻烦。最好是预设一个足够大（如1024）的缓冲区，读入之后再动态分配内存进行处理。毕竟是书名，不能无限长。至于书名个数有多少，这个也有些麻烦，可以用类似顺序表或链表来解决。至于排序，最好是通过指针进行排序，否则字符串的整体复制和移动是效率低下的。这样想来，是有点难度。如果可以使用C+，一方面，还可以沿用上面C语言的思路，完全当做C来用。另一方面，可以直接使用C+提供的字符串类型std:string存储字符串。一大堆字符串可以放在vector中。排序也可以直接调用STL中的sort()算法。这样，整个程序就简单一些了。如果选择Java语言，最好用Scanner读取文件内容，字符串当然用String存储，好多字符串都可以放在List中，排序算法可以用Collections.sort()。相比之下难度更小一点。C+实现：（include部分最好不要省略）#include #include #include #include #include using namespace std;int main() / 读取书目文件ifstream input(input.txt);vector titles;string item;while(getline(input, item, ;) / 以分号作为分隔符titles.push_back(item);input.close();/ 对书名排序sort(titles.begin(), titles.end();/ 结果写入文件ofstream output(output.txt);for(string it : titles)output it endl;output.close();Java实现：（import部分可以省略）import java.io.File;import java.io.IOException;import java.io.PrintStream;import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.Scanner;public class BookList public static void main(String args) throws IOException / 读取书目文件Scanner input = new Scanner(new File(input.txt);input.useDelimiter(;); / 以分号作为分隔符List list = new ArrayList();while(input.hasNext()list.add(input.next();input.close();/ 对书名排序Collections.sort(list);/ 结果写入文件PrintStream output = new PrintStream(output.txt);for(String it : list)output.println(it);output.close();C实现：（尽管做了一些简化，将插入和排序放在一起了，还是有点长）#include #include #include / 存放书目的链表typedef struct Item char *title;struct Item *next; Item, *List;/ 将一条书名插入链表中，并保持整个链表有序，返回新的头指针List OrderInsert(List list, const char *title) / 新建结点List item = malloc(sizeof(Item);item-title = malloc(strlen(title)+1);strcpy(item-title, title);/ 插入链表if(list=NULL | strcmp(item-title, list-title)next = list;list = item; else / 寻找合适的插入位置（p之后）List p = list;while(p-next & strcmp(p-next-title, item-title)next;/ 插入结点item-next = p-next;p-next = item;/ 返回表头指针return list;int main() List list = NULL;/ 存放书名列表（不带头结点的单链表）char buf1024;/ 读取书名用缓冲区int n = 0;/ 缓冲区内字符数FILE *input = NULL;/ 输入文件FILE *output = NULL;/ 输出文件List p;char c;/ 1. 读取书目文件，插入书目列表中，得到有序的书名列表/ - 1.1 打开文件input = fopen(input.txt, r);/ - 1.2 逐个读取字符，每读完一个书名，便插入列表while(c = fgetc(input) != EOF) if(c!=;) / 暂存入缓冲区，继续读取bufn+ = c; else / 读取完一个书名，在末尾添加空字符bufn = 0;n = 0; / 清空缓冲区/ 将书名插入列表list = OrderInsert(list, buf);/ - 1.2+ 如果还有未处理完的书名，则继续处理/ （因为，最后一个书名之后可能没有分号）if(n0) / 在末尾添加空字符bufn = 0;/ 将书名插入列表list = OrderInsert(list, buf);/ - 1.3 关闭文件fclose(input);/ 2. 将排序后的书名列表写入文件/ - 2.1 打开文件output = fopen(output.txt, w);/ - 2.2 逐个输出链表中的书名p = list;while(p) fprintf(output, %sn, p-title);p = p-next;/ - 2.3 关闭文件fclose(output);/ 3. 逐个释放结点，销毁链表while(list) / 取下结点List s = list;list = list-next;/ 释放结点s中书名free(s-title);/ 释放结点空间free(s);return 0;七、编写算法：树采用孩子-兄弟方式存放，结点结构为fchdata nsiblevel其中fch 表示指向第一个孩子，nsib表示指向下一个兄弟, level表示结点层次。设根结点层次为1，其它以此类推，编写一算法，将树中所有结点层次值置入相应level域，并要求由根开始逐层输出树中的各条边，边输