李春葆数据结构教程第4版习题答案Word文档下载推荐.docx
《李春葆数据结构教程第4版习题答案Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《李春葆数据结构教程第4版习题答案Word文档下载推荐.docx（68页珍藏版）》请在冰点文库上搜索。
求mergesort（a，0，n－1）的时间复杂度。
其中，merge（a，i，j，m）用于两个有序子序列
a[i．．m]和a[m+l．．j]的合并，是一个非递归函数，它的时间复杂度为O（合并的元素个数）。
设mergesort（a，0，n-1）的执行次数为T（n），分析得到以下递归关系：
O（n）为merge（）所需的时间，设为cn（c为常量）。
因此：
由于
趋近于1，则k=log2n。
所以
上机实验题1
实验题1设计一个程序expl-1.cpp，输出所有小于等于n（n为一个大于2的正整数）的素数。
要求：
（1）每行输出10个素数；
（2）尽可能采用较优的算法。
’
实验题2编写一个程序expl-2.cpp，计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。
实验题3编写一个程序expl-3.cpp，判断一个字符串是否为“回文”（顺读和倒读都一样的字符串称为“回文”），并分析算法的时间复杂度。
2章答案
1.叙述线性表两种存储结构各自的主要特点。
线性表的两种存储结构分别是顺序存储结构和链式存储结构。
顺序存储结构的主要特点如下：
（1）节点中只有自身的数据域，没有指针域。
因此，顺序存储结构的存储密度大，存储空间利用率高；
（2）可以通过序号直接访问任何数据元素，即可以随机存取；
（3）插入和删除操作会引起大量元素的移动。
链式存储结构的主要特点如下：
（1）节点中除自身的数据域还有表示关联信息的指针域。
因此链式存储结构比顺序存储结构的存储密度小，存储空间利用率较低；
（2）在逻辑上相邻的节点在物理上不比相邻，因此不可以随机存取，只能顺序存取；
（3）插入和删除操作方便灵活。
不必移动节点，只需修改节点中的指针域即可。
2.设计一个算法，将x插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上，并保持线性表的有序性。
通过比较在顺序表L中找到插入x的位置i，将该位置及后面的元素后移一个位置，将x插入到位置i中，最后将L的长度增1。
对应的算法如下：
3.假设一个顺序表L中所有元素为整数，设计一个算法调整该顺序表，使其中所有小于零的元素放在所有大于等于零的元素的前面。
i、j分别置初值为0和L．1ength-1，当i<
j时循环：
i从前向后扫描顺序表L，找大于等于0的元素，j从后向前扫描顺序表L，找小于0的元素，当i<
j时将两元素交换。
4.设计一个算法，将一个带头节点的数据域依次为a1，a2，…，an（n≥3）的单链表的所有节点逆置，即第一个节点的数据域变为an，……，最后一个节点的数据域变为a1。
用P指针扫描单链表，将当前节点*P采用头插法插入到新建的单链表中。
5.设有一个带头节点的单链表L，节点的结构为（data，next），data为整数元素，next为后继节点的指针。
设计一个算法，按递减次序输出该单链表中各节点的数据元素，并释放节点所占的存储空间，并要求算法的空间复杂度为O
（1）
6.设有一个双链表h，每个节点中除有prior、data和next三个域外，还有一个访问频度域freq，在链
表被启用之前，其值均初始化为零。
每当进行LocateNode（h，x）运算时，令元素值为x的节点中freq域的值加1，并调整表中节点的次序，使其按访问频度的递减顺序排列，以便使频繁访问的节点总是靠近表头。
试写一个符合上述要求的LocateNode运算的算法。
在DLinkList类型的定义中添加intfreq域，将该域初始化为0。
在每次查找到一个节点*p时，将其freq域增l，再与它前面的一个节点*q进行比较，若*p节点的freq域值较大，则两者交换，如此找一个合适的位置。
7.设ha=（a1，a2，…，an）和hb=（b1，b2，…，bn）是两个带头节点的循环单链表，编写将这两个表合并为带头节点的循环单链表hc的算法。
先找到ha的最后一个节点*p，将ha的最后一个节点的next指向hb的第一个数据节点，再找到hb的最后一个节点*p，将其构成循环单链表。
8.设非空线性表ha和hb都用带头节点的循环双链表表示。
设计一个算法Insert（ha，hb，i），其功能是：
i=0时，将线性表hb插入到线性表ha的前面；
当i>
0时，将线性表hb插入到线性表ha中第i个节点的后面；
当i大于等于线性表ha的长度时，将线性表hb插入到线性表ha的后面。
利用带头节点的循环双链表的特点设计的算法如下：
9.用带头节点的单链表表示整数集合，完成以下算法并分析时间复杂度：
（1）设计一个算法求两个集合A和B的并运算，即C=AUB。
要求不破坏原有的单链表A和B。
（2）假设集合中的元素按递增排列，设计一个高效算法求两个集合A和B的并运算，即C=AUB。
（1）先将ha单链表中所有节点复制到hc中，然后扫描单链表hb，将其中所有不属于ha的节点复制到hc中。
本算法的时间复杂度为O（mn），其中m、n为单链表ha和hb中的节点个数。
（2）算法中可以利用单链表中节点值的有序性来提高运行效率。
本算法的时间复杂度为O（m+n），其中m、n为单链表ha和hb中的节点个数。
10.用带头节点的单链表表示整数集合，完成以下算法并分析时间复杂度：
（1）设计一个算法求两个集合A和B的差运算，即C=A-B。
要求算法的空间复杂度为O
（1），并释放单链表A和B中不需要的节点。
（2）假设集合中的元素按递增排列，设计一个高效算法求两个集合A和B的差运算，即C=A-B。
（1）将ha单链表中所有在hb中出现的节点删除，最后将hb中所有节点删除。
（2）算法中可以利用单链表中节点值的有序性来提高运行效率，并且一边比较一边将不需要的节点删除。
上机实验题2
实验题1编写一个程序al902-1.cpp，实现顺序表的各种基本运算（假设顺序表的元素类型为char），并在此基础上设计一个程序exp2-1.cpp，完成如下功能：
（1）初始化顺序表L；
（2）采用尾插法依次插入元素a，b，c，d，e；
（3）输出顺序表L；
（4）输出顺序表L长度；
（5）判断顺序表L是否为空；
（6）输出顺序表L的第3个元素；
（7）输出元素a的位置；
（8）在第4个元素位置上插入元素f；
（9）输出顺序表L；
（10）删除L的第3个元素；
（11）输出顺序表L；
（12）释放顺序表L。
实验题2编写一个程序a1902-2.cpp，实现单链表的各种基本运算（假设单链表的元素类型为
char），并在此基础上设计一个程序exp2-2.cpp，完成如下功能：
（1）初始化单链表h；
（3）输出单链表h；
（4）输出单链表h长度；
（5）判断单链表h是否为空；
（6）输出单链表h的第3个元素；
（9）输出单链表h；
（11）输出单链表h；
（12）释放单链表h。
实验题3编写一个程序a1902-3.cpp，实现双链表的各种基本运算（假设双链表的元素类型为
char），并在此基础上设计一个程序exp2-3.cpp，完成如下功能：
（1）初始化双链表h；
（3）输出双链表h；
（4）输出双链表h长度；
（5）判断双链表h是否为空；
（6）输出双链表h的第3个元素；
（9）输出双链表h；
（11）输出双链表h；
（12）释放双链表h。
实验题4编写一个程序a1902-4.cpp，实现循环单链表的各种基本运算（假设循环单链表的元素类型为char），并在此基础上设计一个程序exp2-4.cpp，完成如下功能：
（1）初始化循环单链表h；
（3）输出循环单链表h；
（4）输出循环单链表h长度；
（5）判断循环单链表h是否为空；
（6）输出循环单链表h的第3个元素；
（9）输出循环单链表h；
（11）输出循环单链表h；
（12）释放循环单链表h。
实验题5编写一个程序a1902-5.cpp，实现循环双单链表的各种基本运算（假设循环双链表的元素类型为char），并在此基础上设计一个程序exp2-5.cpp，完成如下功能：
（1）初始化循环双链表h；
（3）输出循环双链表h；
（4）输出循环双链表h长度；
（5）判断循环双链表h是否为空；
（6）输出循环双链表h的第3个元素；
（9）输出循环双链表h；
（11）输出循环双链表h；
（12）释放循环双链表h。
实验题6编写一个程序exp2-6.cpp，采用单链表表示集合（集合中不存在重复的元素），利用例2．7的算法将其按递增方式排序，构成有序单链表。
并求这样的两个集合的并、交和差。
实验题7编写一个程序exp2-7.cpp，用单链表存储一元多项式，并实现两个多项式的相加运算。
3章答案
1.有5个元素，其进栈次序为：
A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？
要使C第一个且D第二个出栈，应该是A进栈，B进栈，C进栈，C出栈，D进栈，D出栈，之后可以有以下几种情况：
（1）B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE；
（2）B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA；
（3）E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。
所以可能的次序有：
CDBAE、CDBEA、CDEBA。
2.假设以I和O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。
（1）下面所示的序列中哪些是合法的？
A．IOIIOIOOB．IOOIOIIOC．IIIOIOIOD．IIIOOIOO
（2）通过对
（1）的分析，写出一个算法判定所给的操作序列是否合法。
若合法则返回1；
否则返回
0。
（假设被判定的操作序列已存入一维数组中）。
（1）A、D均合法，而B、C不合法。
因为在B中，先进栈一次，立即出栈三次，这会造成栈下溢。
在C中共进栈五次，出栈三次，栈的终态不为空。
（2）本题使用一个链栈来判断操作序列是否合法，其中A为存放操作序列的字符数组，n为该数组的元素个数（这里的ElemType类型设定为char）。
对应算法如下：
3.假设表达式中允许包含三种括号：
圆括号、方括号和大括号。
编写一个算法判断表达式中的括号是否正确配对。
设置一个栈st，扫描表达式exp，遇到“（”、“[”或“{”，则将其进栈；
遇到“）”，若栈顶
是“（”则继续处理，否则以不配对返回0；
遇到“]”则继续处理，否则以不配对返回0；
遇到“{”则继续处理，否则以不配对返回false。
在exp扫描完毕，若栈不空，则以不配对返回false；
否则以括号配对返回true。
本题算法如下：
4.设从键盘输入一个整数序列a1，a2，…，an，试编程实现：
当ai>
0时，ai进队，当ai<
0时，将队首元素出队，当ai＝0时，输入结束。
要求将队列处理成环形队列，进队和出队操作单独编写算法，并在异常情况时（如队满）打印错误信息。
先建立一个环形队列qu，用while循环接受用户输入，若输入值大于0，将该数入队；
若小于
0，出队一个元素并输出它；
若等于零则退出循环。
5.编写一个算法，将一个环形队列（容量为n，元素下标从1到n）的元素倒置。
例如，图3-
18（a）中为倒置前的队列（n＝10），图3-18（b）中为倒置后的队列。
图3-18环形队列
使用一个栈起到过渡的作用。
先将sq队列中的元素出队并将其进栈ss直到队列空为止；
然后初始化队列，将sq—>
front和sq—>
rear均置为0；
再出栈元素并将其入队列直到栈空为止。
算法如下：
6.输入n（由用户输入）个10以内的数，每输入i（0≤i≤9），就把它插入到第i号队列中。
最后把10
个队中非空队列，按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。
建立一个队列首节点指针数组QH和队列尾节点指针数组QT，先将它们所有元素置为NULL。
对于输入的x，采用尾插法将其连到QT[x]之后。
最后将它们整个连接起来，对应算法如下：
上机实验题3
实验题1编写一个程序algo3-1.cpp，实现顺序栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序exp3-1.cpp，完成如下功能：
（1）初始化栈s；
（2）判断栈s是否非空；
（3）依次进栈元素a，b，c，d，e
（4）判断栈s是否非空；
（5）输出栈长度；
（6）输出从栈顶到栈底元素；
（7）输出出栈序列；
（8）判断栈s是否非空；
（9）释放栈。
实验题2编写一个程序algo3-2.cpp，实现链栈（假设栈中元素类型为char）的各种基本运算，并在此基础上设计一个程序exp3-2.cpp，完成如下功能：
（1）初始化链栈s；
（2）判断链栈s是否非空；
（3）依次进链栈元素a，b，c，d，e
（4）判断链栈s是否非空；
（5）输出链栈长度；
（7）输出出链栈序列；
（8）判断链栈s是否非空；
（9）释放链栈。
实验题3编写一个程序algo3-3.cpp，实现顺序环形队列的各种基本运算（假设队列中元素类型为
char），并在此基础上设计一个程序exp3-3.cpp，完成如下功能：
（1）初始化队列q；
（2）判断队列q是否非空；
（3）依次进队元素a，b，c；
（4）出队一个元素，并输出该元素；
（5）输出队列q的元素个数；
（6）依次进队列元素d，e，f；
（7）输出队列q的元素个数；
（8）输出出队序列；
（9）释放队列。
实验题4编写一个程序algo3-4.cpp，实现链队的各种基本运算（假设队列中元素类型为char），并在此基础上设计一个程序exp3-4.cpp，完成如下功能：
（1）初始化链队q；
（2）判断链队q是否非空；
（5）输出链队q的元素个数；
（6）依次进链队元素d，e，f；
（7）输出链队q的元素个数；
（9）释放链队。
实验题5编写一个求解迷宫问题的程序exp3-5.cpp，要求输出图3-23所示的迷宫的所有路径，并求最短路径长度及最短路径。
图3-23迷宫示意图
实验题6编写一个程序exp3-6.cpp，求解皇后问题：
在n×
n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。
（1）皇后的个数n由用户输入，其值不能超过20，输出所有的解。
（2）采用类似于栈求解迷宫问题的方法。
实验题7编写一个程序exp3-7.cpp，反映病人到医院看病，排队看医生的情况。
在病人排队过程中，主要重复两件事：
（1）病人到达诊室，将病历本交给护士，排到等待队列中候诊。
（2）护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。
要求模拟病人等待就诊这一过程。
程序采用菜单方式，其选项及功能说明如下：
（1）排队—输入排队病人的病历号，加人到病人排队队列中；
（2）就诊—病人排队队列中最前面的病人就诊，并将其从队列中删除；
（3）查看排队—从队首到队尾列出所有的排队病人的病历号；
（4）不再排队，余下依次就诊—从队首到队尾列出所有的排队病人的病历号，并退出运行；
（5）下班—退出运行。
实验题8设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆车，则后来的汽车只能在门外的便道即候车场上等候，一旦有车开走，则排在便道上的第一辆车即可开入；
当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开
停车场时必须按它停留的时间长短交纳费用。
整个停车场的示意图如图3-24所示。
试为停车场编制按上述要求进行管理的模拟程序exp3-8.cpp。
图3-24停车场示意图
4章答案
1.采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern_index（），其中的通配符只有“？
”，它可以和任一字符匹配成功，例如，pattern_index（″?
re″，″thereare″）返回的结果是2。
本题的基础是Brute—Force模式匹配算法，只是增加了“？
”的处理功能。
2.有两个串s1和s2，设计一个算法求这样一个串，该串中的字符是s1和s2中的公共字符。
扫描s1，对于当前字符s1.data[i]，若在s2中，则将其加入到串s3中。
最后返回s3串。
对应的算法如下：
3.设目标为t=’abcaabbabcabaacbacba’，模式p=’abcabaa’。
（1）计算模式P的nextval函数值。
（2）不写算法，只画出利用KMP算法进行模式匹配时的每一趟匹配过程。
（1）先计算next数组，在此基础上求nextval数组，如表4-1所示。
表4-1计算next数组和nextval数组
j
1
2
3
4
5
p
a
b
c
next[j]
-1
nextval[j]
（2）采用KMP算法求子串位置的过程如下（开始时i=0，j=0）：
第1趟匹配：
此时i=4，j=4，匹配失败，而nextval[4]=0，则i=4，j=nextval[4]=0，即：
第2趟匹配：
此时i=6，j=2，匹配失败，而nextval[2]=0，则i=6，j=nextval[2]=0，即：
第3趟匹配：
此时i=6，j=0，匹配失败，而nextval[0]=-1，则i=6，j=nextval[0]=-1。
因j=-1，执行i=i+1=7，
j=j+1=0，即：
第4趟匹配：
此时i=14，j=7，匹配成功，返回v=i-t．1ength=14-7=7。
上机实验题4
实验题1编写一个程序algo4-1.cpp，实现顺序串的各种基本运算，并在此基础上设计一个程序exp4-1.cpp完成如下功能：
（1）建立串s=″abcdefghefghijklmn″和串sl=″xyz″；
（2）输出串s；
（3）输出串s的长度；
（4）在串s的第9个字符位置插入串s1而产生串s2；
（5）输出串s2；
（6）删除串s第2个字符开始的5个字符而产生串s2；
（7）输出串s2；
（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2；
（9）输出串s2；
（10）提取串s的第2个字符开始的10个字符而产生串s3；
（11）输出串s3；
（12）将串s1和串s2连接起来而产生串s4；
（13）输出串s4。
实验题2编写一个程序algo4-2.cpp，实现链串的各种基本运算，并在此基础上设计一个程序exp4-2.cpp，完成如下功能：
（10）提取串ｓ的第2个字符开始的10个字符而产生串s3；
实验题3编写一个程序exp4-3.cpp，实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：
（1）建立目标串S="
abcabcdabcdeabcdefabcdefg"
和模式串t="
abcdeabcdefab"
；
（2）采用简单匹配算法求t在s中的位置；
（3）对模式串t求next数组值和nextval数组值；
（4）采用KMP算法求t在s中的位置；
（5）采用修正后的KMP算法求t在s中的位置。
实验题4一个文本串可用事先给定的字母映射表进行加密
升级会员 