（1）当算法中需要使用多个栈时，可以采用不同的存储结构来实现。试为这多个栈设计三种存储结构（语言

描述，不需要写代码）并说明这三种方案各自的优缺点；（10分）（2）已知主串S=‘abcaabbabcabaacbacba’,模式串T=‘bcabaa’,计算模式串T的 next 函数值、改进的nextval函数值以及匹配成功时的字符比较次数（利用改进的nextval值），最后分析KMP算法的时间效率（假设主串长m，模式串长n）并说明KMP算法相比朴素的模式匹配算法效率高的原因。（10分）

提问人：网友wyspgbj 发布时间：2022-01-07

参考答案

抱歉！暂无答案，正在努力更新中……

如搜索结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装简答题APP，拍照搜题省时又省心！

更多“（1）当算法中需要使用多个栈时，可以采用不同的存储结构来实现…”相关的问题

第1题

（1）对下图所示的AOE网，求其关键路径，要求给出每个事件和活动的求解过程并写出关键路径；（10分）

（2）已知一组关键字为（16,26,41,38,44,15,68,12,06,51），用链地址法解决冲突。假设装填因子 a不超过0.8，散列函数的形式为 H（K）=K MOD P，试构造出合适的散列函数并写出建好的散列表，计算出等概率情况下查找成功和查找失败的平均查找长度。（10分）

点击查看答案

第2题

（1）已知广义表（（a）,（（）,ｂ）,（（（ｅ）））），画出其表头表尾存储结构图，求出该广义表的表长和表深，并利用取表头和取表尾的操作分离出原子b；（10分）10分）（2）已知一棵二叉树的中序遍历结点排列为ABDICHGEF，后序遍历结点排列为 AICDBEFGH，画出该二叉树、该二叉树的中序线索树以及该二叉树对应的森林。（10分）

点击查看答案

第3题

（1）对关键字序列{9，4，3，8，10，7，6，5}，试画出得到的二叉排序树以及二叉平衡树；（10分）（2）对关键字序列{9，4，3，8，10，7，6，5}，试画出构造的初始小顶堆，并写出快速排序第一趟划分后的序列以及增量为2的一趟希尔排序结果。（10分）

点击查看答案

第4题

设有两个整数集合A和B。请设计一个尽可能高效的算法（算法时间复杂度不高于O(nlogn)），建立集合C，该集合中仅包含存在于集合A或集合B中的元素，两个集合中都含有的元素不包含在集合C中。要求：（1）描述算法的基本设计思想（3分）（2）根据设计思想，采用类C语言描述算法，关键之处给出简要注释。（7分）

点击查看答案

第5题

已知一个具有n个顶点的无向图G，用邻接矩阵存储。试写一个递归算法，判断图G中是否包含一条长度为k的简单路径。要求：（1）描述算法的基本设计思想（3分）（2）根据设计思想，采用类C语言描述算法，关键之处给出简要注释。（7分）

点击查看答案

第6题

（1）已知以邻接矩阵存储的有向网如下图所示，画出该有向网的邻接矩阵，求顶点V1到其它各个顶点的最短路径，给出计算过程和结果；（10分）

（2）设有一组记录的关键字分别为{9,01,23,10,6,20,84,34}，采用哈希函数H（key）=2 key mod 11构建哈希表，哈希表的表长为11，用开放定址法的二次探测再散列方法Hi=(H(key)+di) mod 11 解决冲突。画出所构造的哈希表，并计算等概率情况下查找成功时和查找不成功时的平均查找长度。（10分）

点击查看答案

第7题

（1）当三叉树中只有度为3和0的结点时，证明n3=(n0-1)/2，其中n3是度为3的结点数，n0是度为0的结点数；（10分）（2）已知与树T对应的二叉树如下图所示，其二叉链表存储结构为： typedef struct CSNode{ Elem data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree; 写出树T的所有从树根到叶子的路径，并给出判断叶子结点的条件。（10分）

点击查看答案

第8题

（1）对关键字序列(45, 24, 90, 53, 3, 12,37, 50, 61, 100 )，试画出由该组关键字构建的最终的二叉排序树、二叉平衡树和3阶B-树；（10分）（2）用堆排序方法将无序序列（47，36，63，94，76，13，26，48）按降序排列。请给出建立初始堆的过程，以及进行逐次筛选直到整个序列为有序的过程。（10分）

点击查看答案

第9题

已知一个带有表头结点的非空单链表，结点结构为： data link 假设该链表中data域中存放的是整数，且只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，输出链表中所有间隔为k（k为正整数）的两个结点元素的和。要求：（1）给出算法的基本设计思想（3分）（2）根据设计思想，采用类C语言描述算法，关键之处给出简要注释。（7分）

点击查看答案

第10题

设有一棵二叉链表表示的二叉树，每个结点用数字进行编号，编写函数实现寻找两个不同结点的最近祖先结点功能。例如在下图所示的二叉树中，结点4是结点16和7的最近共同祖先；结点8是结点6和13的最近共同祖先；结点4是结点4和12的最近共同祖先（结点本身也是该结点的祖先结点）。要求：（1）描述算法的基本设计思想（3分）（2）根据设计思想，采用类C语言描述算法，关键之处给出简要注释。（7分）