已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
正确答案：模式串t的next和nextval值如下： j 1 2 3 4 5 6 7 8 9 10 11 12 t串
A.b c
A.a b b
A.b c
A.b next[j] 0 1 1 1 2 2 3 1 2 3 4 5 nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5
相关答案
- 1.设目标为t=“abcaabbabcabaacbacba”，模式为p=“abcabaa” ① 计算模式p的naxtval函数值； ② 不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
- 2.已知字符串S1中存放一段英文，写出算法format（s1，s2，s3，n），将其按给定的长度n格式化成两端对齐的字符串S2， 其多余的字符送S3。
- 3.数组A中，每个元素A[i，j]的长度均为32个二进位，行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求： ① 存放该数组所需多少单元？ ② 存放数组第4列所有元素至少需多少单元？ ③ 数组按行存放时，元素A[7，4]的起始地址是多少？ ④ 数组按列存放时，元素A[4，7]的起始地址是多少？
- 4.编写算法，实现下面函数的功能。函数void insert（char*s，char*t，int pos）将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）
- 5.求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
- 6.写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。
- 7.二维数组S，行下标i从0到7，列下标j从0 到9，每个元素占3个字节，若从首地址S开始以列序为主序将元素连续存放在存储器内，则元素S [4][7]的起始地址为（）。
- 8.交换二叉树每个结点的左孩子和右孩子。
- 9.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。
- 10.用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目。
热门答案
- 1.采用邻接表存储结构，编写一个算法，判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。
- 2.一个连通图采用邻接表作为存储结构，设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。
- 3.判别两棵树是否相等。
- 4.设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。
- 5.设任意n个整数存放于数组A（1：n）中，试编写算法，将所有正数排在所有负数前面（要求算法复杂度为0（n））。
- 6.对连通图进行深度优先遍历可以访问到该图中的所有顶点。
- 7.输出二叉树中从每个叶子结点到根结点的路径。
- 8.试写一个判别给定二叉树是否为二叉排序树的算法。
- 9.设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点，设v可达其余各个顶点。
- 10.以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。