3.26④求解平方根的迭代函数定义如下；
其中，P是A的近似平方根，e是结果误差，试写出相应的递归函数算法，并消
除递归。
3.27⑤已知Ackerman函数定义如下： （1） 写出递归算法； （2） 写出非递归算法，
（3） 根据非递归算法，画出求akm（2，1）时栈的变化过程。
3.28②假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾元素结
点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
3.29②如果希望循环队列中的元素都能得到利用，则需要设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列较小而队列中每个元素占的空间较多时，哪一种方法较好）。
3.30②假设将循环队列定义为：以域变量rear和length分别指示循环队列中对尾
元素的位置和内含元素的个数，试给出此循环队列的对满条件，并写出相应的 入队列和出队列的算法（在出队列的算法中要返回对头元素）。
3.31③假设称正读和反读都相同的字符序列为“回文”，例如，‘abba’和‘abcba’
是回文，‘bcde’和‘ababa’则不是回文，试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。
3.32④试利用循环队列编写求k阶斐波那契序列中前n+1项，（f0 ，f1 ，…. fn）
的算法,要求满足: fn ≤max而fn+1>max,其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶斐波那契序列中的最后k项 fn-k+1 ，…. fn） 。
3.33③在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每一个原始表示一个待处理表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于对头和对尾作业的平均时间，则插入在对头，否则插入在对尾。
3.34③ 假设在教科书3.4.1节中图3.9所示，铁道转轨网的输入端有n节车厢：硬座、硬卧、和软卧（分别以P，H和S表示）等待调度，要求这三种车厢在输出端铁道上的 排队次序为：硬座在 前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符‘E’和‘D’表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。
第 4 章 串
基础知识题
4.1① 简述空串和空格串
4.2②对于教科书4.1节所述串的各个基本操作，讨论是否可由其他基本操作构造
而得？如何构造？
4.3① 设s=‘I AM A STUDENT’,t=’GOOD’,q=’WORKER’. 求：StrLength(s),StrLength(t),SubString(s,8,7),SubString(t,2,1), Index(s,’A’),Index(s,t),Replace(s,’STUDENT’,q), Concat(SubString(s,6,2),Concat(t,SubString(s,7,8))). 4.4①已知下列字符串
a=’THIS’ ,f=’A SAMPLE’,c=’GOOD’,d=’NE’,b=’’,
s=Concat(a,Concat(SubString(f,2,7),Concat(b,SubString(a,3,2)))), t=Replac(f,SubString(f,3,6),c),
u=Concat(SubString(c,3,1),d), g=’IS’
v=Concat(s,Concat(b,Concat(t,Concat(b,u)))),
试问： s,t,v,StrLength(s),Index(v,g),Index(u,g)各是什么？ 4.5①试问执行以下函数会产生怎样的输出结果？ Void demonstrate(){
StrAssign(s,’THIS IS A BOOK’);
Replace(s,SubString(s,3,7),)’ESE ARE’); StrAssign(t,Concat(s,’S’));
StrAssign(u,’XYXYXYXYXYXY’); StrAssign(v,SubSting(u,6,3)); StrAssign(w,’W’);
Printf(‘t=’,t,’v=’,v,’u=’,Replace(u,v,w,)); }//demonstrate
4.6②已知；s=’(XYZ)+*’,t=’(X+Z)*Y’试利用联接、求子串和置换等基本运算，将s
转化为t。
4.7②令=‘aaab’,t=’abcabaa’,u=’abcaabbabcabaacbacba’.。试分别求出它们的next
函数值和nextrval函数值。
4.8②已知主串s=‘ABADABBAABADABBADADA’， 模式串pat=‘ADABBADADA’，
写出模式串的nextval函数值，并由此画出KMP算法匹配的全过程 4.9③在以链表存储串值时，存储密度是结点大小和串长的函数假设每个字符占一个
字节，每个指针占4个字节，每个结点的大小为4的整数倍。已知串长的分布函数为f（l）且，求结点大小为4k，串长为l时的存储密度d（4k，l）（用公式表示）。
算法设计题
在编写4.10至4.14题的算法时，请采用StringType数据类型； StringType是串的一个抽象数据类型，它包含以下五种基本操作： Void StrAssign（StringType &t,StringType s）
//将s的值赋给t。s的实际参数可以是串变量或者串常量（如：‘abcd’）。 int StringCompare(StringType s,StringType t)
//比较s和t。若s>t,返回值>0，若s=t,返回值=0；若s 返回s中的元素个数，即该串的长度。 StringType Concat(StringType s,StringType t) //返回由s和t联接而成的新串 StringType SubString(StringType s,int start ,int len) //当1≤start≤ StrLength(s) 且 0≤len ≤StrLength(s)-start+1时 //返回s中第start个字符起长度为len的子串，否则返回空串。 4.10③ 编写对串求逆的递推算法。 4.11③编写算法，求得所有包含在串s中而不包含在串t中的字符（s中重复的字符 只选一个）构成的新串r，以及r中每个字符在s中第一次出现的位置。 4.12③编写一个实现串的置换操作Replace（&S，T，V）的算法。 4.13③编写算法，从串s中删除所有和串t相同的子串。 4.14④利用串的基本操作以及栈和集合的基本操作，编写“一个算术表达式的前缀 式求后缀式”的递推算法（假设前缀式不含语法错误）。 在编写4.15至4.20题的算法时，请采用教科书4.2.1节中所定义的定长顺序存储 表示，而不允许调用串的基本操作。 4.15③编写算法，实现串的基本操作StringAssign（&T,chars）. 4.16③编写算法，实现串的基本操作StrCompare（S，T）。 4.17③编写算法，实现串的基本操作Replace（&S，T，V）。 4.18③编写算法，求串s所含不同字符的总数和每种字符的个数。 4.19③在串的定长顺序存储结构上直接实现4.11题要求的算法。 4.20③编写算法，从s中删除所有和串相同的子串。 4.21④假设以结点大小为1且附设头结点的链表结构表示串，试编写实现下列六种 串的基本操作StrAssign，StrCopy，StrCopare，StrLength，Contact和SubSring的函数。 4.22④假设以块链结构表示串，试编写将串s插入到串t中某个字符之后的算法，（若 串t中不存在此字符，则将串s联接在串的末尾）。 4.23④假设以块链结构作为串的存储结构。试编写判别给定串是否是具有对称性的 算法，并要求算法的时间复杂度为O（StrLength（S））。 在编写4.24到4.26题的算法时，请采用教科书4.2.2节中所定义的堆分配存储表示 4.24③试写一算法，在串的堆存储结构上实现基本操作Concat(&T,s1.s2). 4.25③试写一算法，实现堆存储结构的串的置换操作Replace（&S，T，V）。 4.26③试写一算法，实现堆存储结构的串的插入操作StrIsert（&S，pos，T）。 4.27③当以教科书4.2.1节中定义的定长顺序结构表示串时，可如下所述改进定位 函数的算法；先将模式串t中的第一个字符和最后一个字符与主串s中相应的字符比较，在两次比较都相等之后，再依次从t的第二个字符起逐个比较，这样做可以克服算法Index（算法4.5）在模式串‘ak b’（ak 表示连续k个字符‘a’ ）在主串‘an b’（k≤n）中的定位函数时产生的弊病，试编写上述改进算法，并比较这两种算法在作Index（‘an b’，‘ak b’）运算时所需进行的字符间的比较次数。 4.28④假设以结点大小为1，（带头结点）的链表的结构表示串，则在利用next函 数值进行匹配时，在每个结点中需要设三个域：数据域chdata、指针域succ和指针域next。其中chdata域存放一个字符，succ域存放指向同一链表中后继结点的指针；next域在主串中存放指向同一链表中前驱结点的指针，在模式串中，存放指向当该结点的字符与主串中的字符不等时，模式串中下一个应进行比较的字符的next函数值为零，则其next域的值应指 向头结点，试按上述定义的结构改写模式串的next函数值的算法。 4.29④试按4.28题定义的结构改写串匹配的改写算法（KMP算法）。 4.30⑤ 假设以定长顺序存储结构表示串，试设计一个算法，求串s中出现的第一 个最长重复子串及其位置，并分析你的算法的时间复杂度。 4.31⑤假设定长顺序存储结构表示串，试设计一个算法，求串s和串t的一个最长 公共子串，并分析你的算法的时间复杂度，若要求第一个出现的最长公共子串（既它在串s和串 t的最左边的 位置上出现）和所有的最长公共子串，讨论你的算法能否实现。 第五章 数组与广义表 基础知识题 5.1①假设有二维数组A6×8 ，每个元素用相邻的6个字节存储，存储器按字节编 址。已知A的起始存储位置（基地址）为1000，计算： （1） 数组A的体积（即存储量）； （2） 数组A的最后一个元素a57 的第一个字节的地址； （3） 按行存储时，元素a14的第一个字节的地址； （4） 按行存储时，元素a47 的第一个字节的地址； 5.2①假设按低下标优先存储整数数组A9×3×5×8 时，第一个元素的字节 地址是100，每个整数占四个字节，问下列元素的存储地址是什么？ （1）a0000 （2）a1111 （3）a3125 （4）a8247 5.3①按高下标优先存储方式（以最右的下标为主序），顺序列出数组A9×3×5×8中所有元素aijkl，，为了简化表达，可以只例出（i，j，k，l）的序列。 5.4①将教科书5.3.1节中的式（5-3）改写为一个等式的形式。 5.5③设有上三角矩阵（aij）m×n ，将其上三角元素逐行存于数组B[m]中，（m充分大）使得B[k]=aij 且k=f l （i）+ f 2 （i） +c 。试推导出函数f l，f 2 和常数c （要求f l和 f 2 中 不含常数项 ） 5.6③设有三对角矩阵（aij）m×n ，将其上三角元素逐行存于数组B[3][n]中，使的元素B[u][v]= aij，试推导出从（i，j）到（u，v）的下标变换公式。 5.7③设有三对角矩阵（aij）m×n ，将其上三角元素逐行存于数组B[3n-2]中，使得B[3n-2]中，使得B[k]= aij ，求： （1） 用i ，j表示k的下标变换公式； （2） 用k表示i、j 的下标变换公式 5.8③假设一个准对矩阵 按以下方式存于一维数组B[4m]中： 0 1 2 3 4 5 6 k 4m-2 4m-1 a11 a12 a21 a22 a33 a34 a43 … aij … a2m-1,2m a2m,2m-1 a2m,2m 写出由一对下标（i，j）求k的转换公式。 5.9②已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构（二维 数组和三元组表）完成 求 运算的优缺点。 5.10②求下列广义表操作的结果： （1） GetHead【（p,h,w）】； （2） GetTail【（b,k,p,h）】； （3） GetHead【（a,b）(c,d)】； （4） GetTail【（a,b）(c,d)】； （5） GetHead【GetTail【（a,b）(c,d)】】； （6） GetTail【GetHead【（a,b）(c,d)】】； （7） GetHead【GetTail【GetHead【（a,b）(c,d)】】】； （8） GetTail【GetHead【GetTail【（a,b）(c,d)】】】； 注意：【】 是函数的符号。 5.11② 利用广义表的GetHead和GetTail 操作写出如上题的函数表达式，把原子