数据结构教程李春葆第5章(第4版)—课后答案
- 格式：pdf
- 大小：379.43 KB
- 文档页数：4
文档推荐
-
数据结构教程李春葆第4版知识点习题答案页数:233
-
数据结构教程李春葆课后答案第5章递归页数:5
-
数据结构教程李春葆课后答案第9章查找页数:9
-
数据结构教程李春葆课后答案第10章内排序页数:7
-
数据结构教程李春葆课后答案第7章树和二叉树页数:11
下载文档原格式
合集下载
数据结构教程李春葆课后答案第5章递归
9. 设有一个不带表头结点的单链表 L，设计两个递归算法，maxnode(L)返回单链表 L
4
数据结构教程学习指导
中最大结点值，minnodel(L)返回单链表 L 中最小结点值。 解：对应的递归算法如下：
ElemType maxnode(LinkNode *L) { ElemType max; if (L->next==NULL) return L->data; max=maxnode(L->next); if (max>L->data) return max; else return L->data; } ElemType minnode(LinkNode *L) { ElemType min; if (L->next==NULL) return L->data; min=minnode(L->next); if (min>L->data) return L->data; else return min; }
b:5 b:4 b:3 b:2 a:1 c:2 c:3 c:4 c:5
2. 已知 A[0..n-1]为整数数组，设计一个递归算法求这 n 个元素的平均值。 解：设avg(A，i)返回A[0..i]共i+1个元素的平均值，则递归模型如下：
avg(A，i)=A[0] avg(A，i)=(avg(A，i-1)*i+A[i])/(i+1) 当i=0 其他情况
第 5 章 递归 return i-1; else return -1; }
5
#include "sqstring.cpp" //顺序串的基本运算算法 findpat(SqString s,SqString t) { int i=0,j=0,k; while (i<s.length && j<t.length) { if (t.data[j]=='*') { k=findpat(SubStr(s,i+2,s.length-i-1),SubStr(t,j+2,t.length-j-1)); j++; if (k>-1) return i-1; else return -1; } else if (s.data[i]==t.data[j]) { i++; j++; } else { i=i-j+1; j=0; } } if (j>=t.length)
李春葆《数据结构教程》(第4版)模拟试题及详解(一)(圣才出品)
第四部分模拟试题李春葆《数据结构教程》（第4版）模拟试题及详解（一）一、单项选择题（每小题2分，共20分）1．队列的特点是（）。
A．先进后出B．先进先出C．任意位置进出D．前面都不正确【答案】B2．有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（）遍分配与收集。
A．nB．dC．rD．n-d【答案】B【解析】基数排序是按组成关键字的各位值进行分配收集而完成的。
3．在二叉树节点的先序序列、中序序列和后序序列中，所有叶子节点的先后顺序（）。
A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同【答案】B【解析】无论是哪种遍历方式，遍历叶子节点时，都是先访问左子树，后访问右子树。
4．限定在一端加入和删除元素的线性表称为（）。
A．双向链表B．单向链表C．栈D．队列【答案】C【解析】根据栈后进先出的特性，可见栈都在一端对元素进行操作。
5．设内存工作区可容纳8个记录，初始文件共有64个关键字不同的记录，且已按关键字递减排列，如用置换．选择排序产生初始归并段，最长初始归并段所含记录数是（）。
A．6B．7C．8D．9【答案】C【解析】对于置换选择排序，输入的文件是以关键字降序排列时，所得的初始归并段的最大长度为工作区的大小。
当输入的文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段。
6．设森林F对应的二叉树为B，它有m个节点，B的根为p，p的右子树上的节点个数为n，森林F中第一棵树的节点个数是（）。
A．m-n-1B．n+lC．m-n+1D．m-n【答案】D7．设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（）。
A．12B．13C．14D．15【答案】C【解析】k一路平衡归并，归并趟数公式s=[1og k m]，m指归并段数，s指趟数。
要三遍完成遍历，那就看两遍完成排序的需遍历的最小数。
把s=2和m=198带入公式，可知两遍完成排序时k最小为15，所以k<15。
李春葆《数据结构教程》(第4版)笔记和课后习题详解(第8~10章)【圣才出品】
李春葆《数据结构教程》（第4版）笔记和课后习题详解第8章图8.1复习笔记一、图的基本概念1．图的定义图都是由顶点和边构成的。
采用形式化的定义，图G由两个集合V和E组成，记为G ＝（V，E），其中V是顶点的有限集合，记为V（G），E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E（G）。
抽象数据类型图的定义如下：2．图的基本术语（1）端点和邻接点在一个无向图中，若存在一条边（i，j），则称顶点i和顶点j为该边的两个端点，并称它们互为邻接点，即顶点i是顶点j的一个邻接点，顶点j也是顶点i的一个邻接点。
（2）顶点的度、入度和出度①度在无向图中，某顶点所具有的边的数目称为该顶点的度。
②入度在有向图中，顶点i的度又分为入度和出度，以顶点i为终点的入边的数目，称为该顶点的入度。
③出度以顶点i为起点的出边的数目，称为该顶点的出度。
一个顶点的入度与出度的和为该顶点的度。
（3）完全图若无向图中每两个顶点之间都存在一条边，或有向图中每两个顶点之间都存在着方向相反的两条边，则称此图为完全图。
（4）稠密图和稀疏图①稠密图当一个图接近完全图时，称为稠密图。
②稀疏图当一个图含有较少的边数（即当e＜＜n（n-1））时，则称为稀疏图。
（5）子图设有两个图G＝（V，E）和G′＝（V′，E′），若V′是V的子集，即V′≤V，且E′是E的子集，即E′≤E，则称G′是G的子图。
（6）路径和路径长度①路径在一个图G＝（V，E）中，从顶点i到顶点j的一条路径是一个顶点序列（i，i1，i2，…，i m），若此图G是无向图，则边（i，i1），（i1，i2），…，（i m－1，i m），（i m，j）属于E（G）；若此图是有向图，N<i，i1>，<i1，i2>，…，<i m－1，i m>，<i m，j>属于E（G）。
②路径长度路径长度是指一条路径上经过的边的数目。
（7）回路或环若一条路径上的开始点与结束点为同一个顶点，则称此路径为回路或环。
数据结构教程李春葆第4版知识点习题答案
第1章绪论知识点归纳一、数据结构概述1.数据结构的定义（1）基本概念数据是描述客观事物的数和字符的集合，是计算机能操作的对象的总称，也是计算机处理信息的某种特定的符号表示形式。
（2）相关术语① 数据元素数据元素又称元素、节点、顶点、记录等。
数据元素是数据的基本单位。
有时候，一个数据元素可以由若干个数据项组成。
② 数据项数据项又称字段或域，它是具有独立含义的最小数据单位。
③ 数据对象数据对象是性质相同的数据元素的集合，它是数据的子集。
（3）数据结构的内容① 数据元素之间的逻辑关系，即数据的逻辑结构，它是数据结构在用户面前呈现的形式。
② 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，又称数据的物理结构。
③ 施加在数据上的操作，即数据的运算。
（4）逻辑结构数据的逻辑结构是从逻辑关系（主要是指数据元素的相邻关系）上描述数据的，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
（5）存储结构数据的存储结构是逻辑结构用计算机语言的实现或在计算机中的表示（又称映像），也就是逻辑结构在计算机中的存储方式，它是依赖于计算机语言的。
一般只在高级语言（例如C／C++语言）的层次上讨论存储结构。
数据的运算最终需在对应的存储结构上用算法实现。
总之，数据结构是一门讨论“描述现实世界实体的数学模型（通常为非数值计算）及其之上的运算在计算机中如何表示和实现”的学科。
（6）数据结构的表示对于一种数据结构，其逻辑结构总是惟一的，但它可能对应多种存储结构，并且在不同的存储结构中，同一运算的实现过程可能不同。
描述数据结构通常采用二元组表示：B=（D，R）其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R组成，即：D={d i | 1≤i≤n，n≥0}R={r j | 1≤j≤m，m≥0}其中d i表示集合D中的第i个数据元素（或节点），n为D中数据元素的个数，特别地，若n=0，则D 是一个空集。
部分习题参考答案(数据结构 李春葆)
void Insert(DLinkList *&ha, DLinkList *&hb,int i) { DLinkList *p=ha->next,*q;
int lena=1,j=0; while (p->next!=ha)//求出ha的长度lena { lena++;
p=p->next; }
if (i==0) //将hb的所有数据结点插入到ha的头结点和第1个数据结点之间
{ p=hb->prior;
//p指向hb的最后一个结点/
p->next=ha->next;
//将*p链到ha的第1个数据结点前面
ha->next->prior=p;
ha->next=hb->next;
hb->next->prior=ha;
//将ha头结点与hb的第1个数据结点链起
来
}
else if (i<lena)
q->next->prior=q;
p->next=q;q->prior=p;
q=p->prior;
//q重指向*p的前趋节点
}
return true;
}
}
2.5 设ha=(a1,a2,…,an)和hb=(b1,b2, …,bm) 是两个带头结点的循环单链表，编写将 这两个表合并为带头结点的循环单链表hc的算法。
else
//找到的情况
{ p->freq++;
//频度增1
q=p->prior;
//*q为p前驱节点
while (q!=h && q->freq<p->freq)
int lena=1,j=0; while (p->next!=ha)//求出ha的长度lena { lena++;
p=p->next; }
if (i==0) //将hb的所有数据结点插入到ha的头结点和第1个数据结点之间
{ p=hb->prior;
//p指向hb的最后一个结点/
p->next=ha->next;
//将*p链到ha的第1个数据结点前面
ha->next->prior=p;
ha->next=hb->next;
hb->next->prior=ha;
//将ha头结点与hb的第1个数据结点链起
来
}
else if (i<lena)
q->next->prior=q;
p->next=q;q->prior=p;
q=p->prior;
//q重指向*p的前趋节点
}
return true;
}
}
2.5 设ha=(a1,a2,…,an)和hb=(b1,b2, …,bm) 是两个带头结点的循环单链表，编写将 这两个表合并为带头结点的循环单链表hc的算法。
else
//找到的情况
{ p->freq++;
//频度增1
q=p->prior;
//*q为p前驱节点
while (q!=h && q->freq<p->freq)
李春葆《数据结构教程》(第4版)课后习题-串(圣才出品)
第4章串1．采用顺序结构存储串，编写一个实现串通配符匹配的算法pattern______index（），其中的通配符只有“？”，它可以和任一字符匹配成功，例如，pattern______index（″? re″，″there are″）返回的结果是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数组（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。
李春葆《数据结构教程》(C++语言描述)配套题库【课后习题】(串)
{
i=ch-'A'+10;
num[i]++;
}
}
（2）设计一个算法，将一个链串 S 中的所有子串”abc”删除。 答： String deleteabc(String S) {
String t=’abc’; String nstr; int i=0,j=0,k=0;
6 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
（2）以下______是“abcd32lABCD”串的子串。 A．abcd B．B21AB C．”abcABC” D．“21AB” 【答案】D 【解析】串需要用引号引起来，没有引号的只是字符的罗列而不是串，因此 AB 项错误； 由在一个串中由任意连续的字符组成的子序列称为该串的子串可知，C 项中字符串并不包含
②对于模式串 t（t=t0t1…tm-1），求 next 数组时，next[i]在什么条件下取-1。 答：当 i=0 时，即 next[0]=-1。
（4）设目标串为 s=“abcaabbcaaabababaabca”，模式串为 p=“babab”。 ①计算模式 P 的 答：-1,0,1,2,0。 ②不写算法，只画出利用 KMP 算法进行模式匹配时的每一趟的匹配过程。
二、问答题 （1）若 s1 和 s2 为串，给出使 s1//s2=s2//s1 成立的所有可能的条件（其中，“//” 表示两个串连接的运算符）。 答：①s1 和 s2 之中至少有一个为空串 ②s1 和 s2 的值相等 ③s1 和 s2 之中某一个串可由另一个串经过重复得到。
3 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
1 / 11
圣才电子书 十万种考研考证电子书、题库视频学习平台
数据结构(李春葆)习题与解析
数据结构(李春葆)习题与解析编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构(李春葆)习题与解析）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为数据结构(李春葆)习题与解析的全部内容。
数据结构（C语言篇）―习题与解析（修订版）清华大学出版社一、绪论选择题1.数据结构是一门研究非数值计算的程序设计问题计算机的以及它们之间的和运算等的学科.1 A.数据元素 B。
计算方法C。
逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2。
数据结构被形式地定义为（K， R)，其中K是的有限集，R是K 上的有限集。
1A。
算法 B。
数据元素C。
数据操作 D.逻辑结构2A。
操作 B。
映像C。
存储D。
关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C。
线性结构和非线性结构 D。
内部结构和外部结构4.线性结构的顺序存储结构是一种A的存储结构，线性表的链式存储结构是一种B的存储结构。
A.随机存取 B。
顺序存取 C.索引存取 D.散列存取5。
算法分析的目的是C，算法分析的两个主要方面是AB。
1 A.找出数据结构的合理性 B。
研究算法中的输入和输出的关系C。
分析算法的效率以求改进 D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.正确性和简单性C。
可读性和文档性 D.数据复杂性和程序复杂性6.计算机算法指的是C，它必须具备输入、输出和B等5个特性。
1 A.计算方法 B。
排序方法C。
解决问题的有限运算序列D.调度方法2 A.可执行性、可移植性和可扩充性B。
可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法B。
李春葆《数据结构教程》(第4版)课后习题-第一章至第十二章(圣才出品)
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n=O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。
李春葆《数据结构教程》(第4版)课后习题-绪论(圣才出品)
第二部分课后习题第1章绪论1．简述数据与数据元素的关系与区别。
答：凡是能被计算机存储、加工的对象统称为数据，数据是一个集合。
数据元素是数据的基本单位，是数据的个体。
数据与元素之间的关系是元素与集合之间的关系。
2．数据结构和数据类型有什么区别？答：数据结构是互相之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。
而数据类型是一个值的集合和定义在这个集合上的一组运算的总称，如C语言中的int数据类型是由-32768~32767（16位机）的整数和+、-、*、/、%等运算符组成。
3．设3个表示算法频度的函数f、g和h分别为：f（n）=100n3+n2+1000g（n）=25n3+5000n2h（n）=n1.5+5000nlog2n求它们对应的时间复杂度。
答：f（n）=100n3+n2+1000=O（n3），g（n）=25n3+5000n2=O（n3），当n→∞时，√n>log2n，所以h（n）=n1.5+5000nlog2n= O（n1.5）。
4．用C／C++语言描述下列算法，并给出算法的时间复杂度。
（1）求一个n阶方阵的所有元素之和。
（2）对于输入的任意三个整数，将它们按从小到大的顺序输出。
（3）对于输入的任意n个整数，输出其中的最大和最小元素。
答：（1）算法如下：本算法的时间复杂度为O（n2）。
（2）算法如下：本算法的时间复杂度为O（1）。
（3）算法如下：本算法的时间复杂度为O（n）。
5．设n为正整数，给出下列各种算法关于n的时间复杂度。
（1）（2）（3）答：（1）设while循环语句执行次数为T（n），则：（2）算法中的基本运算语句是if（b[k]>b[j]）k=j，其执行次数T（n）为：（3）设while循环语句执行次数为T（n），则：则6．有以下递归算法用于对数组a[i．．j]的元素进行归并排序：求mergesort（a，0，n－1）的时间复杂度。