下载文档原格式
第4章树一、单项选择题：1.如下图4-1所示的4棵二叉树中，不是完全二叉树。
A. B. C. D.图4-1 4棵二叉树2.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法。
A.正确B.错误3.二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法。
A.正确B.错误4.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法。
A.正确B.错误5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为。
A.2hB.2h-1C.2h+1D.h+16.如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先根遍历就是T2中结点的遍历。
A.先序B.中序C.后序D.层次序7.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是。
A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数8. 如下图4-2所示的T2是由森林T1转化而来的二叉树，那么森林T1有 个叶子结点。
A.4B.5C.6D.7图4-2 一棵二叉树9. 按照二叉树的定义，具有3个结点的二叉树有 种。
A.3 B.4 C.5 D.610. 在一非空二叉树的中序遍历序列中，根结点的右边 。
A. 只有右子树上的所有结点B.只有右子树上的部分结点C. 只有左子树上的部分结点D.只有左子树上的所有结点11. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序 。
A.不发生改变B.发生改变C.不能确定D.以上都不对12. 设n ，m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是 。
A.n 在m 右方B.n 是m 祖先C.n 在m 左方D.n 是m 子孙13. 线索二叉树是一种 结构。
A.逻辑B.逻辑和存储C.物理D.线性二、填空题：1. 有一棵树如下图4-3所示，回答下面的问题：（1）这棵树的根结点是 ；（2）这棵树的叶子结点是 ；（3）结点k3的度是；（4）这棵树的度为；（5）这棵树的深度是；（6）结点k3的孩子结点是；（7）结点k3的双亲结点是。
11． 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。
写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。
写算法，实现顺序串的基本操作 StrCompare(s,t) 。
第四章习题1. 设 s=' I AM A STUDENT , t= ' GOO D,q=' WORKER 给出下列操作的结果: StrLength(s); SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s, ' A ' ,4); StrReplace(s, ' STUDEN 'T,q); StrCat(StrCat(sub1,t), StrCat(sub2,q));2. 编写算法，实现串的基本操作 StrReplace(S,T,V) 。
3. 假设以块链结构表示串，块的大小为 1，且附设头结点。
试编写算法，实现串的下列基本操作：StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ； SubString(Sub,S,pos,len) 。
4． 叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变 量的值。
5． 已知：S=”(xyz)* ” ,T= ”(x+z)*y ”。
试利用联接、求子串和置换等操作，将 S 转换为T. 6． S 和T 是用结点大小为1的单链表存储的两个串，设计一个算法将串 S 中首次与T 匹配的子串逆 置。
7． S 是用结点大小为4的单链表存储的串，分别编写算法在第k 个字符后插入串T ,及从第k 个字符 删除 len 个字符。
第4章习题解答一、填空1.字符串是一种特殊的线性表，特殊在于它的数据元素只能是一字符,特殊在于串可以作为一个__________ 参与所需要的处理。
2.空格串是由___ 组成的串，空串是_________ 的串，因此空格串和空串不是一个概念。
3.字符串中任意多个_______ 字符所组成的子序列，被称作是这个串的“子串”，这个字符串木身则称为“主串”。
4.我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符__________ 码的比较而得到的结论。
5.设有串s=<t I am a teacher"。
该串的长度是_________ 。
6.设有三个串：sl=“Good", s2=9', s3=“bye!''。
则si、s2、s3连接后的结果串应该是7.所谓“数组”，是指〃(H>1)个具有」业L类型的数据的有序集合。
8.矩阵与通常所说的[维数组冇关。
9.所谓“特殊矩阵”,是指那些元素在矩阵小的分布具有一定规律性的矩阵；而矩阵小的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“稀疏矩阵”。
10.在一个阶方阵A中，若所有元素都有性质：= n),就称其为对称矩阵。
二、选择1 •设有两个串si和s20求s2在si中首次出现的位置的操作称为__________ oA.连接B.模式匹配C.求了串D.求串长2・有串：“①"，那么它的长度是____ oA. 0B. 1C. 2D. 33.设有串sl=“ABCDEFG'和s2=“PQRSF'。
已知:算法con(x, y)返回串x和y的连接串；subs(s, i, j)返回串s的第i个字符开始往后j个字符组成的子串；len(s)返回串s的长度。
那么，con(subs(sl, 2, len(s2)), subs(sl, len(s2), 2))的操作结果是串__________ 。
第4章广义线性表一一多维数组和广义表2005-07-14第4章广义线性表一一多维数组和广义表课后习题讲解1. 填空⑴ 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。
【解答】存取，修改，顺序存储【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。
除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。
⑵ 二维数组A中行下标从10到20,列下标从5到10,按行优先存储，每个元素占4个存储单元，A[10][5] 的存储地址是1000,则元素A[15][10]的存储地址是（）。
【解答】1140【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了（15-10）X6+个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。
⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d,每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。
【解答】d+41【分析】元素A[8][5]的前面共存储了（1+2+…+8）+5=41个元素。
⑷稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。
【解答】三元组顺序表，十字链表⑸广义表（（a）, （（（b）,c））,（d））的长度是（），深度是（），表头是（），表尾是（）。
【解答】3, 4, （a），（（（（b）,c））,（d））⑹ 已知广义表LS=（a （b, c, d）, e）,用Head和Tail函数取出LS中原子b的运算是（）。
【解答】Head(Head(Tail(LS)))2. 选择题⑴ 二维数组A 的每个元素是由6 个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9 ，则存放A 至少需要（）个字节，A 的第8 列和第5 行共占（）个字节，若A 按行优先方式存储，元素A[8][5] 的起始地址与当A 按列优先方式存储时的（）元素的起始地址一致。
第一章：概论(包括习题与答案及要点)本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。
需要达到<识记>层次的基本概念和术语有：数据、数据元素、数据项、数据结构。
特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。
数据结构的两大类逻辑结构和四种常用的存储表示方法。
需要达到<领会>层次的内容有算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。
--------------------------------------------------------------------------------对于基本概念，仔细看书就能够理解，这里简单提一下：数据就是指能够被计算机识别、存储和加工处理的信息的载体。
数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。
数据项是具有独立含义的最小标识单位。
如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。
数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。
这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。
比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。
那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。
习题四串一、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列 B．空串是由空格构成的串C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储2．串是一种特殊的线性表，其特殊性体现在（）。
A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符3．串的长度是指（）A．串中所含不同字母的个数 B．串中所含字符的个数C．串中所含不同字符的个数 D．串中所含非空格字符的个数4．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串 B．联接 C．匹配 D．求串长5．若串S=“softwa re”,其子串的个数是（）。
A．8 B．37 C．36 D．9二、填空题1．含零个字符的串称为______串。
任何串中所含______的个数称为该串的长度。
2．空格串是指__ __，其长度等于__ __。
3．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相等。
一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的______串。
4．INDEX（‘DATAST RUCTU RE’，‘STR’）=________。
5．模式串P=‘abaabc ac’的next函数值序列为________。
6．下列程序判断字符串s是否对称，对称则返回1，否则返回0；如 f("abba")返回1，f("abab")返回0；int f((1)__ ______){int i=0,j=0;while(s[j])(2)___ _____;for(j--; i<j && s[i]==s[j]; i++,j--);return((3)___ ____)}7．下列算法实现求采用顺序结构存储的串s和串t的一个最长公共子串。
串-第4章-《数据结构题集》答案解析-严蔚敏吴伟民版习题集解析部分第4章串——《数据结构题集》-严蔚敏.吴伟民版源码使⽤说明链接☛☛☛课本源码合辑链接☛☛☛习题集全解析链接☛☛☛相关测试数据下载链接☛本习题⽂档的存放⽬录：数据结构\▼配套习题解析\▼04 串⽂档中源码的存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04源码测试数据存放⽬录：数据结构\▼配套习题解析\▼04 串\▼习题测试⽂档-04\Data⼀、基础知识题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 = Replace(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, SubString(u, 6, 3));StrAssign(w, ‘W’);printf(‘t=’, t, ‘v=’, v, ‘u=’, Replace(u, v, w));}//demonstrate4.6❷已知：s = ‘(XYZ)+*’,t = ‘(X+Z)*Y’。
第4章（数组和广义表）作业参考答案一、单项选择题1.将一个A[1..100，1..100]的三对角矩阵，按行优先压缩存储到一维数组B[1‥298]中，A 中元素A[66][65]在B数组中的位置K为（C ）。
A. 198B. 197C. 195D. 1962.广义表（a,(b,c),d,e）的表头为（ A ）。
A. aB. a,(b,c)C. (a,(b,c))D. (a)3.在三对角矩阵中，非零元素的行标i和列标j的关系是（ A ）。
A. |i-j|≤1B. i>jC. i==jD. i<j4.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ D ）。
A. cB. b，cC.（b，c）D.（（b，c））5.设二维数组A[1..m,1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（ D ）。
A. j*m+i-1B. (i-1)*n+j-1C. i*(j-1)D. (i-1)*n+j6.广义表(( ),( ),( ))的深度为（ C ）。
A. 0B. 1C. 2D. 37.假设以行序为主序存储二维数组A[0..99,0..99]，设每个数据元素占2个存储单元，基地址为10，则LOC（A[4][4]）=（ C ）。
A. 1020B. 1010C. 818D. 8088.已知广义表A=((a,b),(c,d))，则head(A)等于（ A ）。
A. (a,b)B. ((a,b))C. a,bD. a9.已知一个稀疏矩阵的三元组表如下：(1，2，3)，(1，6，1)，(3，1，5)，(3，2，-1)，(4，5，4)，(5，1，-3)则其转置矩阵的三元组表中第3个三元组为（ C ）。
A. (2，3，-1)B. (3，1，5)C. (2，1，3)D. (3，2，-1)10.广义表（(b,c),d,e）的表尾为（ C ）。
数据结构第四章的习题答案数据结构第四章的习题答案在学习数据结构的过程中，习题是非常重要的一环。
通过解答习题，我们可以更好地理解和应用所学的知识。
在第四章中，我们学习了树和二叉树的相关概念和操作。
下面我将为大家提供一些第四章习题的答案，希望能帮助大家更好地掌握这一章节的内容。
1. 请给出树和二叉树的定义。
树是由n(n>=0)个结点构成的有限集合，其中有且仅有一个特定的结点称为根结点，其余的结点可以分为若干个互不相交的有限集合，每个集合本身又是一个树，称为根的子树。
二叉树是一种特殊的树结构，其中每个结点最多有两个子结点，分别称为左子结点和右子结点。
二叉树具有递归的定义，即每个结点的左子树和右子树都是二叉树。
2. 请给出树和二叉树的遍历方式。
树的遍历方式包括前序遍历、中序遍历和后序遍历。
前序遍历是先访问根结点，然后依次遍历左子树和右子树。
中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树。
后序遍历是先遍历左子树和右子树，最后访问根结点。
二叉树的遍历方式包括前序遍历、中序遍历和后序遍历。
前序遍历是先访问根结点，然后依次遍历左子树和右子树。
中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树。
后序遍历是先遍历左子树和右子树，最后访问根结点。
3. 给定一个二叉树的前序遍历序列和中序遍历序列，请构建该二叉树。
这个问题可以通过递归的方式解决。
首先，根据前序遍历序列的第一个结点确定根结点。
然后，在中序遍历序列中找到根结点的位置，该位置左边的结点为左子树的中序遍历序列，右边的结点为右子树的中序遍历序列。
接下来，分别对左子树和右子树进行递归构建。
4. 给定一个二叉树的中序遍历序列和后序遍历序列，请构建该二叉树。
和前面的问题类似，这个问题也可以通过递归的方式解决。
首先，根据后序遍历序列的最后一个结点确定根结点。
然后，在中序遍历序列中找到根结点的位置，该位置左边的结点为左子树的中序遍历序列，右边的结点为右子树的中序遍历序列。
【课后习题】第4章 串 第5章 数组和广义表网络工程2010级（ ）班 学号： 姓名：题 号 一 二 三 四 总分 得 分一、填空题（每空1分，共30分）1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。
2. 若n 为主串长度，m 为子串长度，则串的BF （朴素）匹配算法最坏的情况下需要比较字符的总次数为 ,T(n)= 。
3. 是任意串的子串；任意串S 都是S 本身的子串，除S 本身外，S 的其他子串称为S 的 。
4. 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为 。
5. 对于数组，比较适于采用 结构够进行存储。
6. 广义表的深度是指_______。
7. 将一个100100 A 的三对角矩阵，按行优先存入一维数组B[297]中，A 中元素66,66A 在B 数组中的位置k 为 。
8. 注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1<i<=n 时,j=i-1,i,i+1) 。
9. 称为空串； 称为空白串。
10. 求串T 在主串S 中首次出现的位置的操作是 ，其中 称为目标串， 称为模式。
11. 对称矩阵的下三角元素a[i,j]，存放在一维数组V 的元素V[k]中（下标都是从0开始）， 12. k 与i ，j 的关系是：k= 。
13. 在n 维数组中每个元素都受到 个条件的约束。
14. 同一数组中的各元素的长度 。
15. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。
16.稀疏矩阵中有n个非零元素，则其三元组有行。
17.求下列广义表操作的结果：18.（1）GetHead【((a,b),(c,d))】=== ;19.（2）GetHead【GetTail【((a,b),(c,d))】】=== ;20.（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;21.（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;22.广义表E=(a,(b,E)),则E的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。
【课后习题】第4章 串 第5章 数组和广义表网络工程2010级（ ）班 学号： 姓名：一、填空题（每空1分，共30分）1. 串有三种机内表示方法： 、 和 ，其中前两种属于顺序存储结构，第三种属于 。
2. 若n 为主串长度，m 为子串长度，则串的BF （朴素）匹配算法最坏的情况下需要比较字符的总次数为 ,T(n)= 。
3. 是任意串的子串；任意串S 都是S 本身的子串，除S 本身外，S 的其他子串称为S 的 。
4. 设数组a[1…50, 1…60]的基地址为1000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[32,58]的存储地址为 。
5. 对于数组，比较适于采用 结构够进行存储。
6. 广义表的深度是指_______。
7. 将一个100100 A 的三对角矩阵，按行优先存入一维数组B[297]中，A 中元素66,66A 在B 数组中的位置k 为 。
注意：a i,j 的k 为 2(i-1)+j-1,(i=1时j=1,2;1<i<=n 时,j=i-1,i,i+1) 。
8. 称为空串； 称为空白串。
9. 求串T 在主串S 中首次出现的位置的操作是 ，其中 称为目标串， 称为模式。
10. 对称矩阵的下三角元素a[i,j]，存放在一维数组V 的元素V[k]中（下标都是从0开始），k 与i ，j 的关系是：k= 。
11. 在n 维数组中每个元素都受到 个条件的约束。
12. 同一数组中的各元素的长度 。
13. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。
14. 稀疏矩阵中有n 个非零元素，则其三元组有 行。
15.求下列广义表操作的结果：（1）GetHead【((a,b),(c,d))】=== ;（2）GetHead【GetTail【((a,b),(c,d))】】=== ;（3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== ;（4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== ;16.广义表E=(a,(b,E)),则E的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。
《数据结构》第四章习题一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”）1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。
( √)2、串是一种数据对象和操作都特殊的线性表。
( √)3、只包含空白字符的串称为空串（空白串）。
( ×)4、稀疏矩阵压缩存储后，必会（不会）失去随机存取功能。
( ×)5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。
( √)6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。
（×）7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换（错的），就完成了对该矩阵的转置运算。
（×）二、单项选择题1．下面关于串的的叙述中，哪一个是不正确的？（ B ）A．串是字符的有限序列B．空串是由空格构成的串（空串是长度为零的串）C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。
A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG3、串的长度是指（ B ）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数三、填空题1、串是一种特殊的线性表，其特殊性表现在_数据元素为字符，操作集也不同__；串的两种最基本的存储方式是_顺序存储_、__ 链式存储_；两个串相等的充分必要条件是__两串的长度相等且两串中对应位置的字符也相等__。
2、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为_O(m+n)__。
数据结构习题第一章绪论数据结构是一门研究非数值计算的程序设计问题中计算机的___①__以及它们之间的__②_ 和运算等的学科。
①A.数据元素 B.计算方法 C.逻辑存储 D.数据映像②A.结构 B.关系 C.运算 D.算法算法分析的目的是___①__ ，算法分析的两个主要方面是__②___ 。
① A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求该进D.分析算法的易懂性和文档性② A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性计算机算法指的是__①__ ，它必须具备输入、输出和__②_ 等5个重要特性。
① A.计算方法 B.排序方法C.解决问题的有限运算序列D.调度方法② A.可读性、可移植性和可扩展性 B. 可读性、可移植性和有穷性C.确定性、有穷性和可行性D.易读性、稳定性和安全性数据元素是数据处理的基本单位；数据项是数据处理的_最小单位。
数据结构是研究数据的逻辑结构___和__物理结构__，并对这种结构定义相适应的运算，设计出相应的算法，分析算法的效率。
算法的效率包括时间和空间两个方面，分别称为_空间复杂度和时间复杂度。
数据的逻辑结构是指_数据元素之间的关系__；包括线性结构、树形结构和图形结构三种类型,其中树形结构和图状结构合称为__非线性结构__。
线性结构中元素之间存在_一对一___ 关系，树形结构中元素之间存在_一对多___ 关系，图状结构中元素之间存在__多对多__ 关系。
数据结构在计算机中的表示称为数据的物理（或存储）结构，数据的物理结构可以采用_顺序存储和_链式存储__两种存储方法。
顺序存储方法是把逻辑上相邻的元素存储在物理位置相邻的内存单元中；链式存储方法中元素间的关系是由__指针来表示_的。
第二章线性表链表不具备的特点是____ 。
A.可随机访问任一结点B.插入删除不需移动元素C.不必事先估计存储空间D.所需空间与其长度成正比不带头结点的单链表head 为空的判定条件是____。
4 多维数组及广义表4.1回答下列概念：三元组表、广义表、十字链表三元组表：稀疏矩阵中的非零元素三元组组成的线性表。
广义表：也称为列表（Lists）是n（n≥0）个元素a1，a2，…，a i，…，a n的有限序列，元素a i可以是原子或者是子表（子表亦是广义表）。
十字链表：稀疏矩阵（即三元组表）的一种链接存储结构。
稀疏矩阵中每个非零元素都用一个包含五个域的结点来表示，存储非零元素所在行的行号域i，存储非零元素所在列的列号域j，存储非零元素值的值域v，以及行指针域right和列指针域down，分别指向同一行中的下一个非零元素结点和同一列中的下一个非零元素结点。
4.2二维数组在采用顺序存储时，元素的排列方式有哪两种？行优先和列优先。
4.3 矩阵压缩存储的目的是什么？请写出对称阵压缩存储四种方式的地址公式。
压缩存储的目的：节省矩阵的存储空间。
将对称矩阵的下（上）三角存储在数组长度为n（n+1）/2的数组sa中，设矩阵中的某一个元素a ij在数组中的下标为k，则对称阵压缩存储四种方式下k的计算公式如下：（1）行优先顺序存储下三角i(i+1)/2+j i≥j （下三角）k=j(j+1)/2+i i＜j（上三角）（2）列优先顺序存储下三角j（2n-j+1）/2+i-j i≥j （下三角）k=i（2n-i+1）/2+j-i i＜j （上三角）（3）行优先顺序存储上三角i（2n-i+1）/2+j-i i≤j （上三角）k=j（2n-j+1）/2+i-j i＞j （下三角）（4）列优先顺序存储上三角j（j+1）/2+i i≤j （上三角）k=i（i+1）/2+j i＞j （下三角）4.4 在特殊矩阵和稀疏矩阵中，哪一种经过压缩存储后会失去随机存取的特性？稀疏矩阵。
4.5 设有一个10阶的对称矩阵A，以行优先顺序存储下三角元素，其中a00为第一元素，其存储地址为1，每个元素占一个字节，则a 85的地址为多少？若a 11为第一元素，那么a 85的地址又会是多少？若a 00为第一元素，则a 85的地址为：41 若a 11为第一元素，则a 85的地址为：324.6 请给出图4.10中稀疏矩阵A 6×7的三元组顺序表和十字链表存储结构图示。
第四章习题1. 设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’。
给出下列操作的结果：StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1);StrIndex(s,’A’,4); StrReplace(s,’STUDENT’,q);StrCat(StrCat(sub1,t), StrCat(sub2,q));2. 编写算法，实现串的基本操作StrReplace(S,T,V)。
3. 假设以块链结构表示串，块的大小为1，且附设头结点。
试编写算法，实现串的下列基本操作：StrAsign(S,chars)； StrCopy(S,T)； StrCompare(S,T)； StrLength(S)；StrCat(S,T)； SubString(Sub,S,pos,len)。
4．叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。
5．已知：S=”(xyz)*”,T=”(x+z)*y”。
试利用联接、求子串和置换等操作，将S转换为T.6．S和T是用结点大小为1的单链表存储的两个串，设计一个算法将串S中首次与T匹配的子串逆置。
7．S是用结点大小为4的单链表存储的串,分别编写算法在第k个字符后插入串T，及从第k个字符删除len个字符。
以下算法用定长顺序串：8．编写下列算法：（1）将顺序串r中所有值为ch1的字符换成ch2的字符。
（2）将顺序串r中所有字符按照相反的次序仍存放在r中。
（3）从顺序串r中删除其值等于ch的所有字符。
（4）从顺序串r1中第index 个字符起求出首次与串r2相同的子串的起始位置。
（5）从顺序串r中删除所有与串r1相同的子串。
9．写一个函数将顺序串s1中的第i个字符到第j个字符之间的字符用s2串替换。
10．写算法，实现顺序串的基本操作StrCompare(s,t)。
第4章树
一、单项选择题：
1.如下图4-1所示的4棵二叉树中，不是完全二叉树。
A. B. C. D.
图4-1 4棵二叉树
2.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说
法。
A.正确
B.错误
3.二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面，这种说法。
A.正确
B.错误
4.由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法。
A.正确
B.错误
5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至
少为。
A.2h
B.2h-1
C.2h+1
D.h+1
6.如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先根遍历就是T2中结点
的遍历。
A.先序
B.中序
C.后序
D.层次序
7.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是。
A.空或只有一个结点
B.完全二叉树
C.二叉排序树
D.高度等于其结点数
8. 如下图4-2所示的T2是由森林T1转化而来的二叉树，那么森林T1有 个叶子结点。
A.4
B.5
C.6
D.7
图4-2 一棵二叉树
9. 按照二叉树的定义，具有3个结点的二叉树有 种。
A.3 B.4 C.5 D.6
10. 在一非空二叉树的中序遍历序列中，根结点的右边 。
A. 只有右子树上的所有结点
B.只有右子树上的部分结点
C. 只有左子树上的部分结点
D.只有左子树上的所有结点
11. 任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序 。
A.不发生改变
B.发生改变
C.不能确定
D.以上都不对
12. 设n ，m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是 。
A.n 在m 右方
B.n 是m 祖先
C.n 在m 左方
D.n 是m 子孙
13. 线索二叉树是一种 结构。
A.逻辑
B.逻辑和存储
C.物理
D.线性
二、填空题：
1. 有一棵树如下图4-3所示，回答下面的问题：
（1）这棵树的根结点是 ；
（2）这棵树的叶子结点是 ；
（3）结点k3的度是；
（4）这棵树的度为；
（5）这棵树的深度是；
（6）结点k3的孩子结点是；
（7）结点k3的双亲结点是。
图4-3 一棵树
2.树和二叉树的主要差别是。
3.深度为k的完全二叉树至少有个结点，至多有个结点，若按自上而下，
从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是。
4.现有按中序遍历二叉树的结果为abc，有种不同形态的二叉树可以得到这一遍历结
果，这些二叉树分别是。
三、应用题：
1.假设二叉树采用顺序存储结构，如下图所示：
（1）画出二叉树表示；
（2）写出先序遍历、中序遍历和后序遍历的结果；
（3）画出把此二叉树还原成森林的图。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
2.试求含有n个叶子结点的完全二叉树的总结点数。
3.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，请画出这颗二叉树并给
出它的先序遍历序列。
4.设给定权集w={2,3,4,7,8,9}，试构造关于w的一棵哈夫曼树，并求其加权路径长度WPL。
5.已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，…，n m个度为m
的结点，求该树中叶子结点数。
四、算法设计题：
1.假设二叉树T用二叉链表作存储结构，设计一个算法求二叉树中指定结点的层次。
2.二叉树T采用二叉链表作存储结构，试设计一个算法计算二叉树中度为1的结点数。
3.树T采用孩子兄弟链表作存储结构，试设计一个算法计算该树的深度。
