数据结构习题4

第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的双亲结点是。

第4章数组和广义表【例4-1】二维数组A的每一个元素是由6个字符组成的串，其行下标i=0，1，…，8，列下标j=1，2，…，10。

若A以行为主序存储元素，A[8][5]的物理地址与当A按列为主序存储时的元素（）的物理地址相同。

设每个字符占一个字节。

A．A[8][5] B．A[3][10] C．A[5][8] D．A[0][9]解：二维数A是一个9行10列的矩阵，即A[9][10]。

按行存储时，A[8][5]是第85个元素存储的元素。

而按列存储时，第85个存储的元素是A[3][10]。

即正确答案为B。

【例4-2】若对n阶对称矩阵A以行序为主序方式将其下三角形的元素（包括主对角线上所有元素）依次存放于一维数组B[n（n+1）/2]中，则在B中确定的位置k的关系为（）。

A．jii+-2)1(*B．ijj+-2)1(*C．jii++2)1(*D．ijj++2)1(*解：如果a ij按行存储，那么它的前面有i-1行，其有元素个数为：1+2+3+…+（i-1）=i（i-1）/2。

同时它又是所在行的第j列，因此它排列的顺序还得加上j，一维数组B[n(n+1)/2]中的位置k与其下标的关系是：jii+-2)1(*。

因此答案为A。

【例4-3】已知n阶下三角矩阵A，按照压缩存储的思想，可以将其主对角线以下所有元素（包括主对角线上元素）依次存放于一维数组B中。

请写出从第一列开始以列序为主序分配方式时在B中确定元素a ij的存放位置的公式。

解：如果a ij按列存储，那么它的前面有j-1列，共有元素：n+(n-1)+(n-2)+ …+[n-(j-2)]=(j-1)*n-2)1)(2(--jj而它又是所在列的第i行，因此在它前的元素个数还得加上i。

因此它在一维数组B中的存储顺序为：(j-1)*n-2)1)(2(--jj+i【例4-4】已知广义表L=((x,y,z),a,(u,t,w))，从L表中取出的原子项ASCII码最大的运算是（）。

第 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)×6+5个元素，每个元素占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按列优先方式存储时的（）元素的起始地址一致。

第四章一、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

答：●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。

●串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。

●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

二、假设有如下的串说明：char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;(1)在执行如下的每个语句后p的值是什么?p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');(2)在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);(3)调用函数strcmp(s1,s2)的返回值是什么?(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?(5)调用函数stlen(strcat(s1,s2))的返回值是什么?解：(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第四章）1、多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( )。

A、数组的元素处在行和列两个关系中B、数组的元素必须从左到右顺序排列C、数组的元素之间存在次序关系D、数组是多维结构，内存是一维结构2、串的长度是（）A、串中不同字母的个数B、串中不同字符的个数C、串中所含字符的个数D、串中所含字符的个数，且大于03、串与普通的线性表相比较，它的特殊性体现在（）。

A、顺序的存储结构B、链式存储结构C、数据元素是一个字符D、数据元素任意4、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1……n(n+1)/2]中，则在B中确定aij(i<j)的位置k的关系为( )。

A、i*(i-1)/2+jB、j*(j-1)/2+iC、i*(i+1)/2+jD、j*(i+1)/2+i5、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。

A、60B、66C、18000D、336、若6行8列的数组以列序为主序顺序存储,基地址为1000,每个元素占2个存储单元,则第5行第3列的元素(假定无第0行第0列)的地址是()。

A、 1086B、 1032C、 1068D、答案A,B,C都不对7、下面的说法中,不正确的是(）A、数组是一种线性结构B、数组是一种定长的线性结构C、除了插入与删除操作外，数组的基本操作还有存取修改、检索和排序等D、数组的基本操作有存取、修改、检索和排序等，没有插入与删除操作8、设有一个n*n的对称矩A,将其下三角部分按行存放在一维数组B中，而A[0][0]存放于B[0]中，那么第i行对角线元素A[i][i]存放于B中( ) 处。

A、(i+3)i/2B、(i+1)i/2C、(2n-i+1)i/2D、(2n-i-1)i/29、设模式T=“abcabc”，则该模式的next值为（）A、{-1,0,0,1,2,3}B、{-1,0,0,0,1,2}C、{-1,0,0,1,1,2}D、{-1,0,0,0,2,3}10、下面()不属于特殊矩阵。

习题41.填空题（1）已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为（___________)。

答案：129(2)4个结点可构成（___________)棵不同形态的二叉树。

答案:12(3）设树的度为5，其中度为1～5的结点数分别为6、5、4、3、2个,则该树共有（___________）个叶子。

答案：31(4）在结点个数为n(n〉1）的各棵普通树中，高度最小的树的高度是(___________），它有（___________）个叶子结点，（___________）个分支结点。

高度最大的树的高度是（___________）,它有（___________）个叶子结点，（___________）个分支结点。

答案：2 n—1 1 n 1 n-1（5）深度为k的二叉树，至多有（___________）个结点。

答案:2k-1（6）有n个结点并且其高度为n的二叉树的数目是（___________）。

答案:2n—1(7）设只包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为（___________)，最小结点数为（___________）。

答案：2k-1 k（8）将一棵有100个结点的完全二叉树按层编号，则编号为49的结点为X，其双亲PARENT（X）的编号为(）.答案：24（9）已知一棵完全二叉树中共有768个结点，则该树中共有（___________)个叶子结点。

答案：384（10）已知一棵完全二叉树的第8层有8个结点，则其叶子结点数是(___________）.答案：68（11）深度为8（根的层次号为1)的满二叉树有（___________)个叶子结点。

答案：128（12）一棵二叉树的前序遍历是FCABED,中序遍历是ACBFED，则后序遍历是（___________）.答案：ABCDEF（13）某二叉树结点的中序遍历序列为ABCDEFG，后序遍历序列为BDCAFGE，则该二叉树结点的前序遍历序列为(___________）,该二叉树对应的树林包括（___________)棵树。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

习题一、单项选择题1.空串与空格字符组成的串的区别在于（）。

A.没有区别B.两串的长度不相等C.两串的长度相等D.两串包含的字符不相同2.一个子串在包含它的主串中的位置是指（）。

A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位置3.下面的说法中，只有（）是正确的。

A.字符串的长度是指串中包含的字母的个数B.字符串的长度是指串中包含的不同字符的个数C.若T包含在S中，则T一定是S的一个子串D.一个字符串不能说是其自身的一个子串4.两个字符串相等的条件是（）。

A.两串的长度相等B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同5. 若SUBSTR（S，i，k）表示求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=“Beijing＆Nanjing”，SUBSTR（S，4，5）=（）。

A.“ijing”B.“jing＆”C.“ingNa”D.“ing＆N”6. 若INDEX（S，T）表示求T在S中的位置的操作，则对于S=“Beijing＆Nanjing”，T=“jing”，INDEX（S，T）=（）。

A.2B.3C.4D.57. 若REPLACE（S，S1，S2）表示用字符串S2替换字符串S中的子串S1的操作，则对于S=“Beijing＆Nanj ing”，S1=“Beijing”，S2=“Shanghai”，REPLACE（S，S1，S2）=（）。

A.“Nanjing＆Shanghai”B.“Nanjing＆Nanjing”C.“ShanghaiNanjing”D.“Shanghai＆Nanjing”8. 在长度为n的字符串S的第i个位置插入另外一个字符串，i的合法值应该是（）。

A.i＞0B. i≤nC.1≤i≤nD.1≤i≤n+19.字符串采用结点大小为1的链表作为其存储结构，是指（）。

数据结构(第二版)习题答案第4章第4章字符串、数组和特殊矩阵4.1稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。

4.2设有一个10 × 10的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存储其下三角阵，假设其起始元素 a00的地址为 1，每个数据元素占 2个字节，则 a65的地址为（ 53 ）。

4.3若串S =“software”，其子串的数目为（ 36 ）。

4.4常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。

4.5 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空间）。

4.6对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素 aij，若它满足（|i-j|>b），则 aij = 0。

4.7字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。

4.8试编写一个函数，实现在顺序存储方式下字符串的 strcompare （S1，S2）运算。

【答】：#include <stdio.h>#include <string.h>#define MAXSIZE 100typedef struct{char str[MAXSIZE];int length;}seqstring;/* 函数 strcompare()的功能是：当 s1>s2时返回 1，当 s1==s2时返回 0，当 s1<s2时返回-1*/int strcompare(seqstring s1,seqstring s2){ int i,m=0,len;len=s1.length<s2.length ?s1.length:s2.length;for(i=0;i<=len;i++)if(s1.str[i]>s2.str[i]){m=1;break;}else if(s1.str[i]<s2.str[i]){m=-1;break;}return m;}int main(){ seqstring s1,s2;int i,m;printf("input char to s1:\n");gets(s1.str);s1.length=strlen(s1.str);printf("input char to s2:\n");gets(s2.str);s2.length=strlen(s2.str);m=strcompare(s1,s2);if(m==1) printf("s1>s2\n");else if(m==-1) printf("s2>s1\n");else if(m==0) printf("s1=s2\n");}4.9试编写一个函数，实现在顺序存储方式下字符串的replace（S，T1，T2）运算。