数据结构第四五六七章作业答案
数据结构第四、五、六、七章作业答案
第四章和第五章
一、填空题
1.不包含任何字符（长度为0）的字符串称为空字符串；由一个或多个空格（仅空格
字符）组成的字符串称为空白字符串。
2.设s=“a;/document/mary.doc”，则strlen(s)=20,“/”的位置为3。
3.子串的定位操作称为串模式匹配；匹配的主字符串称为目标字符串，子字符串称为
模式。
字符串长度17模式串长度
4、串的存储方式有顺序存储、堆分配存储和块链存储
5.有一个二维数组a[0:8,1:5]，每个数组元素用四个相邻字节存储，内存用字节寻址。假设存储阵列元素a[0,
1]的地址为100，如果以主行顺序存储，则a[3,5]的地址为176，[5,3]的地址为208。如果按列存储，[7,1]的地址为128，[2,4]的地址为216。
6、设数组a[1…60,1…70]的基地址为2048，每个元素占2个存储单元，若以列序为
主序顺序存储，则元素a[32,58]的存储地址为8950。7、三元素组表中的每个结点对应于
稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的行下标、列下标和元
素值。8、二维数组a[10][20]采用列序为主方式存储，每个元素占10个存储单元，且
a[0][0]的存储地址是2000，则a[6][12]的地址是3260
9.已知二维数组a[20][10]按行顺序存储，每个元素占2个存储单元，a[10][5]的存
储地址为1000，则a[18][9]的存储地址为116810。已知二维数组a[10][20]按行顺序存储，每个元素占2个存储单元，a[0][0]的存储地址为1024，则a[6][18]的地址为130011，两个字符串相等。充要条件是长度相等，相应位置的字符相同。
12、二维数组a[10][20]采用列序为主方式存储，每个元素占一个存储单元，并且
a[0][0]的存储地址是200，则a[6][12]的地址是200+（12*10+6）=326。
二、单选题
1、串是一种特殊的线性表，其特殊性体现在（b）ａ．可以顺序存储ｂ．数据元素是
一个字符ｃ．可以链式存储ｄ．数据元素可以是多个字符
2.有两个字符串P和Q。查P中Q的第一个位置的操作称为（b）A.连接b.模式匹
配C.查子字符串D.查字符串长度
3.设串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）
ａ．bcdefｂ．bcdefgｃ．bcpqrstｄ．bcdefef4。假设包含60行70列的二维数组
a[1…60,1…70]按主顺序存储，其基址为10000，每个元素占2个存储单元，则第32行和第58列中元素a[32,58]的存储地址为（a）。（第0行和第0列中没有元素）
ａ．16902ｂ．16904ｃ．14454ｄ．答案a,b,c均不对5、下面关于串的的叙述中，（b）是不正确的。
a、字符串是一个有限的字符序列。B.空字符串是由空格组成的字符串。模式匹配是字符串的一项重要操作。D.字符串可以按顺序或链式存储
6.设矩阵a是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组b[1,n(n-1)/2]中，对下三角部分中任一元素ai,j(i≤j)，在一维数组b 中下标k的值是(b)
a1,1aa2，12，2？A.安，1安，2？安，n a、 i（i-1）/2+j-1b、i
（i-1）/2+jc、i（i+1）/2+j-1d、i（i+1）/2+j
7.有一个二维数组a，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是a个字节。假设存储数组元素a[1,0]的第一个字节的地址是0，则存储数组a的最后一个元素的第一个字节的地址是b。若按行存储，则a[2,4]的第一个字节的地址是c。若按列存储，则a[5,7]的第一个字节的地址是d。
备选答案：a~d：① 12② 66③ 72④ 96⑤ 114⑥ 120⑦ 156⑧ 234⑨ 276⑩ 答案：ABCD=12,10,3,9
8、以下关于广义表的叙述中，正确的是（a）a)广义表是由0个或多个单元素或子表构成的有限序列b)广义表至少有一个元素是子表
c）通用表不能递归定义（d）通用表不能为空
9、设a是n*n的对称矩阵，将a的对角线及对角线上方的元素以列为主的次序存放在一维数组(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在b中的位置为(b)。
a、 i（i-l）/2+jb。j（j-l）/2+ic。j（j-l）/2+i-1d。i（i-l）/2+j-1
10.设a[n，n]是对称矩阵，将其下三角（包括对角线）以行序存储到一维数组t[n （n+1）/2]中，则：任意一个上三角元素a[i][j]所对应t[k]的下标k是（b）。
a、 i（i-1）/2+jb。j（j-1）/2+ic。i（j-i）/2+1d。j（i-1）/2+1
11、常对数组进行的两种基本操作是（c）。a．建立与删除
b、索引和修改
c．查和修改
d、搜索和索引
12、就一般情况而言，当（c）时，按行存储的a[i，j]地址与按列存储的a[j，i]地址相等。
a、行和列的上限相同。B.行和列的下限相同。C.行和列的上限和下限相同。D.行和列中的元素数量相同
13、二维数组m的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放m至少需要（d①）个字节；m的第8列和第5行共占（②b）个字节。①a．90
b、 180
c．240
d、 540
②a．108
b、 114
c．54
d、 60
14、数组a中，每个元素a的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址sa开始连续存放在存储器内，存放该数组至少需要的单元数是（c）。a．80
b、一百
c．240
d、 270
15、数组a中，每个元素a的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址sa开始连续存放在存储器内，该数组按行存放时，元素a[8][5]的起始地址为（c）a．sa+141（c）
a、 o（n）
b．o(log2n)
c、 o（1）
d．o(n2)
17、
b．sa+144
c、 sa+222
d．sa+225
16.如果一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为
三、判断题
1. (√) 子字符串是由主字符串中的任何连续字符组成的序列。
2、（√）广义表(((a),b),c)的表头是((a),b)，表尾是(c)。
3、（×）数组元素的
下标值越大，存取时间越长
4.数组是线性结构的推广，所以像线性表一样，它可以被插入、删除和其他操作。（×）
⒋（×）设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。⒌（√）二维数组是其数据元素为线性表的线性表。
6.（W）如果使用三重压缩技术存储稀疏矩阵，则只要交换每个元素的行下标和列下标，矩阵的转置就完成了。
7、(w)若一个广义表的表头为空表，则此广义表亦为空表。8、(w)用一维数组存储二
叉树时，总是以前序遍历存储节点。
9.当使用堆分配存储字符串时，字符串仍然存储在一组具有连续地址的存储单元中，
但存储空间是在程序执行期间通过动态分配获得的。（√）
四、问答题

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。