数据结构(C语言第2版) 课后习题答案之第四章 串、数组和广义表

目录

第4章  串、数组和广义表

1．选择题

（1）串是一种特殊的线性表，其特殊性体现在（  ）。

（2）串下面关于串的的叙述中，（  ）是不正确的？

（3）串“ababaaababaa”的next数组为（  ）。

（4）串“ababaabab”的nextval为（  ）。

（5）串的长度是指（  ）。

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（  ）。

（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（  ）。

（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（  ）。

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

（10）A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（  ）。

（11）设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i,j]在一维数组B中的下标为（  ）。

（12）数组A[0..4,-1..-3,5..7]中含有元素的个数（  ）。

（13）广义表A=(a,b,(c,d),(e,(f,g)))，则Head(Tail(Head(Tail(Tail(A)))))的值为（  ）。

（14）广义表((a,b,c,d))的表头是（  ），表尾是（  ）。

（15）设广义表L=((a,b,c))，则L的长度和深度分别为（  ）。

二、应用题

（1）已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。

（2）设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa”

（3）数组A中，每个元素A[i,j]的长度均为32个二进位,行下标从-1到9，列下标从1到11，从首地址S开始连续存放主存储器中，主存储器字长为16位。求：

(4)请将香蕉banana用工具 H( )—Head( )，T( )—Tail( )从L中取出。

（5）写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A-Z这26个字母和0-9这10个数字）。

（6）写一个递归算法来实现字符串逆序存储，要求不另设串存储空间。

（7）编写算法，实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。

（8）已知字符串S1中存放一段英文，写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。

(9)设二维数组a[1..m, 1..n] 含有m*n 个整数。

(10)设任意n个整数存放于数组A(1:n)中，试编写算法，将所有正数排在所有负数前面（要求算法复杂性为0(n)）。

第4章  串、数组和广义表 1．选择题 （1）串是一种特殊的线性表，其特殊性体现在（  ）。

  A．可以顺序存储               B．数据元素是一个字符      

C．可以链式存储               D．数据元素可以是多个字符若

（2）串下面关于串的的叙述中，（  ）是不正确的？

A．串是字符的有限序列          B．空串是由空格构成的串

C．模式匹配是串的一种重要运算  D．串既可以采用顺序存储，也可以采用链式存储

（3）串“ababaaababaa”的next数组为（  ）。

A．012345678999   B．012121111212   C．011234223456    D．0123012322345

（4）串“ababaabab”的nextval为（  ）。

A．010104101      B．010102101      C．010100011       D．010101011

（5）串的长度是指（  ）。

A．串中所含不同字母的个数       B．串中所含字符的个数

C．串中所含不同字符的个数       D．串中所含非空格字符的个数

（6）假设以行序为主序存储二维数组A=array[1..100,1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5,5]=（  ）。

A．808            B．818             C．1010             D．1020

（7）设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5,8]的存储首地址为（  ）。

A．BA+141        B．BA+180         C．BA+222         D．BA+225

（8）设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（  ）。

A．13             B．33              C．18               D．40

（9）若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B[1..(n(n+1))/2]中，则在B中确定aij（i