开发工具:
文件大小: 352kb
下载次数: 0
上传时间: 2010-11-23
详细说明： 数据结构习题Dijkstra 1.3、将二叉树看作图，并对它作图的深度优先遍历，则与原二叉树的 结果是相同的。 A、前序遍历 B、中序遍历C、后序遍历D、层次序遍历 1.4、在关于树的以下4种叙述中，正确的是 。 A、用指针方式存储有n个结点的二叉树，至少要有n+1个指针。 B、m阶B-树中，具有k个子结点的结点，必有k-1个键值。 C、m阶B-树中，每个非叶子结点的子结点个数≥[m/2]。 D、平衡树一定是丰满树。 1.5、在最好和最坏情况下的时间复杂度均为O(nlog2n)且稳定的排序方法是 A、希尔排序 B、快速排序 C、堆排序 D、归并排序 二、解答题 2.1、对目标串 abaabcc和模式串aabc，描述根据KMP算法进行匹配的过程，包括失效函数计算。答：失效函数：-1， 0， -1， -1 目标串 abaabcc和模式串aabc的KMP算法进行匹配的过程 abaabcc aabc 首先，从目标位置0和模式位置0开始比较，至ab和aa，不等时目标位置为1， 模式位置为1。因0位置失效函数的值（ f [posP-1] ） 为-1，从目标位 置1和模式位置0开始新一轮比较。 因第一个字符( posP == 0 )就不等，目标 位置增1，目标位置2和模式位置0开始新一轮比较，直到模式位置比较至4， 匹配成功。 int fastFind ( char *s, char * pat ){ //带失效函数的KMP匹配算法 int posP = 0, posT = 0; int lengthP = strlen(pat), lengthT = strlen(s); while ( posP < lengthP && posT < lengthT ) if ( pat[posP] == s[posT] ) { posP++; posT++; //相等继续比较 } else if ( posP == 0 ) posT++; //不相等 else posP = f [posP-1]+1; if ( posP < lengthP ) return -1; else return posT - lengthP; } ...展开收缩
(系统自动生成,下载前可以参看下载内容)
下载文件列表
相关说明
- 本站资源为会员上传分享交流与学习,如有侵犯您的权益,请联系我们删除.
- 本站是交换下载平台，提供交流渠道，下载内容来自于网络，除下载问题外，其它问题请自行百度。
- 本站已设置防盗链，请勿用迅雷、QQ旋风等多线程下载软件下载资源，下载后用WinRAR最新版进行解压.
- 如果您发现内容无法下载，请稍后再次尝试；或者到消费记录里找到下载记录反馈给我们.
- 下载后发现下载的内容跟说明不相乎，请到消费记录里找到下载记录反馈给我们，经确认后退回积分.
- 如下载前有疑问，可以通过点击"提供者"的名字，查看对方的联系方式，联系对方咨询.
