PTA第四章串、数组和广义表练习题

1、以行序优先顺序存储数组A[5][5]；假定A[0][0]的地址为1000, 每个元素占4个字节，下标变量A[4][3]的地址是____。

A.1069B.1092C.1023D.1046正确答案：B2、数组a[1．．6][1．．5] （无0行0列）以列序优先顺序存储，第一个元素a[1][1]的地址为1000，每个元素占2个存储单元，则a[3][4]的地址是____。

A.1040B.1026C.1046D.1038正确答案：A3、设有一个5行4列的矩阵A，采用行序优先存储方式，A[0][0]为第一个元素，其存储地址为1000，A[2][2]的地址为1040，则A[3][0]的地址为_________。

A.1048B.1024C.1096D.1060正确答案：A4、设有一个10行10列的矩阵A，采用行序优先存储方式，存储全部数据需要400个字节的空间。

如果A[0][0]为第一个元素，其存储地址为1000，则A[3][6]的地址为_________。

A.1036B.1144C.1014D.10565、设有一个10行10列的矩阵A，采用行序优先存储方式。

如果A[0][0]为第一个元素，其存储地址为1000，A[2][3]的存储地址为1069，则存储一个元素需要的单元数是_________。

A.4B.1C.2D.3正确答案：D6、不能够对数据元素进行随机访问的物理结构是_________。

A.三元组顺序表B.对称矩阵的压缩存储C.三对角矩阵的压缩存储D.数组的顺序存储正确答案：A7、对特殊矩阵采用压缩存储的目的主要是_________。

A.表达变得简单B.去掉矩阵中的多余元素C.对矩阵元素的存储变得简单D.减少不必要的存储空间正确答案：D8、对n*n的对称矩阵进行压缩存储，需要保存的数据元素的个数是_________。

A.nB.n(n+1)/2C.n2D.n(n+1)9、设10*10的对称矩阵下三角保存SA[1．．55]中，其中A[1][1]保存在SA[1]中，A[5][3] 保存在SA[k]中，这里k等于_________。

栈、队列、串、数组和广义表习题一、选择题1 一个栈的输入序列为1234 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 22 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，p N,若p N是n，则p i是( D )。

A. iB. n-iC. n-i+1D. 不确定3 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( B )A. 1和 5B. 2和4C. 4和2D. 5和14 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( C )。

A． 6 B. 4 C. 3 D. 25 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A．求子串 B．联接 C．匹配 D．求串长6 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。

A. 13B. 33C. 18D. 407 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( C )。

A. head(tail(LS))B. tail(head(LS))C. head(tail(head(tail(LS)))D. head(tail(tail(head(LS))))8 模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（ D ），nextval数组的值为（ F ）。

A．0 1 1 1 2 2 1 1 1 2 3 4 5 6 7 1 2 B．0 1 1 1 2 1 2 1 1 2 3 4 5 6 1 1 2 C．0 1 1 1 0 0 1 3 1 0 1 1 0 0 7 0 1 D．0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2 E．0 1 1 0 0 1 1 1 0 1 1 0 0 1 7 0 1 F．0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1二、填空题1 在作进栈运算时应先判别栈是否_(1)满_;在作退栈运算时应先判别栈是否_(2)空_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(3)n_。

1．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（ ）A ．数组的元素处在行和列两个关系中B ．数组的元素必须从左到右顺序排列C ．数组的元素之间存在次序关系D ．数组是多维结构，内存是一维结构 2．从广义表LS ＝（(p, q), r, s ）中分解出原子q 的运算是（ ） A ．tail (head (LS))B ．head (tail (head (LS)))C ．head (tail (LS))D ．tail (tail (head (LS)))3．二维数组A ［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A ［9］［7］的地址为( )A. 429B. 432C. 435D. 4384．二维数组A ［10］［20］采用按行为主序的存储方式，每个元素占4个存储单元，若A ［0］［0］的存储地址为300，则A ［10］［10］的地址为（ ）A.700B.1120C.1180D.11405．假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2836的元素是（ ）A ．R[3][3][3]B ．R[3][3][4]C ．R[4][3][5]D ．R[4][3][4]6．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（ ）A ．1207B ．1209C ．1211D ．12137．对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )A. (e,f)B. ((e,f))C. (f)D. ( )8．设有二维数组A ［n ］［n ］表示如下：⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡ 653421， 则A ［i ］［i ］（0≤i ≤n-1）的值为（ ）A ．i*(i-1)/2B.i*(i+1)/2C.(i+2)*(i+1)/2D.i 2/2 9．对广义表L=((a,b),((c,d),(e,f)))执行head(tail(head(tail(L))))操作的结果是（ ）A ．dB ．eC ．(e)D ．(e,f )10．假设按行优先顺序将一个20阶的三对角矩阵A 压缩存储在一维数组Q 中，其中Q[0]存放矩阵的第1个元素a 1,1，那么矩阵元素a 3,4在Q 中的存储位置k=_______。

已知二维数组A[3][5]，其每个元素占3个存储单元，并且A[0][0]的存储地址为1200。

求元素A[1][3]的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？【解答】按照以行序为主序存储公式：LOC(i，j)=LOC(c1，c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L在C语言中有：LOC(i，j)=LOC(0，0)+(i*(d2+1)+j)*L则：LOC(A[1][3])=1200+(1*5+3)*3=1224(按行序存储)LOC(A[1][3])=1200+(3*3+1)*3=1230(按列序存储)有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7][5]和A[5][6]的地址。

【解答】按照公式：LOC(A[7][5])=7(7-1)/2＋5 = 26LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=20设有一个二维数组A[m][n]，设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（676－2－644）/2）。

A[3][3]存放位置是692。

二维数组A[9][10]的元素都是6个字符组成的串，请回答下列问题：（1）存放A至少需要( )个字节；（2）A的第7列和第4行共占( )个字节；（3）若A按行存放，元素A[7][4]的起始地址与A按列存放时哪一个元素的起始地址一致。

【解答】按照题5.1给出的公式：（1）存放A需要9*10*6=540个字节（2）A的第7列和第行共占(9+10-1)*6=108个字节（3）LOC(A[7][4])= LOC(A[0][0])+[7*10+4]*L(按行序存储)LOC(A[i][j])= LOC(A[0][0])+[j*9+i]*L（按列序存储，0<=i<=8,0<=j<=9)所以,i=2,j=8。

第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．串是一种特殊的线性表，其特殊性体现在（）A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符2．串的长度是（）A．串中不同字母的个数B．串中不同字符的个数C．串中所含字符的个数，且大于0 D．串中所含字符个数3．若串S=”software”，其子串数目是（）A．8 B．37 C．36 D．94．数组A[0..5，0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素A[5][5]的地址为（）A．1175 B．1180 C．1205 D．12105．对矩阵压缩存储是为了（）A．方便运算B．节省存储空间C．方便存储D．提高运算速度6．一个n 阶对称矩阵，如果采用压缩存储方式，则容量为（）A．n2B．n2/2 C．n(n+1)/2 D．(n+1)2/27．对稀疏矩阵采用压缩存储，其缺点之一是（）A．无法判断矩阵有多少行多少列B．无法根据行列号查找某个矩阵元素C．无法根据行列号计算矩阵元素的存储地址D．使矩阵元素之间的逻辑关系更加复杂二．填空1．设串s1=”I am a student”，则串长为（）2．设有两个串p和q，其中q是p的子串，求子串q 在p中首次出现位置的算法称为（）3．一维数组的逻辑结构是（），存储结构是（）；对于二维或多维数组，分为按（）和（）两种不同的存储结构。

4．数组A[1..10,-2..6,2..8]以行优先顺序存储，设第一个元素的首地址为100，每个元素占3个单元的存储空间，则元素A[5][0][7]的存储地址为（）5．三维数组R[C1..D1,C2..D2,C3..D3]共含有（）个元素。

三、算法设计1．编写下列算法（假定下面所用的串均采用顺序存储方式，参数c、c1和c2均为字符型）：（1）将串S中所有其值为c1的字符换成c2的字符。

（2）将串S中所有字符逆序（3）从串S中删除其值等于c的所有字符（4）从串S中第index个字符起求出首次与字符串S1相同的子串的起始位置（5）从串S中删除重第i个字符起的j 个字符（6）从串S中删除所有与串S1相同的子串（允许调用第（4）题和第（5）题的算法）2．设计程序，计算串str中每一个字符出现的次数。

第4～5章串和数组练习题一、填空题1. 称为空串；称为空白串。

2. 设S=“A;/document/Mary.doc”，则strlen(s)= , “/”的字符定位的位置为。

4. 子串的定位运算称为串的模式匹配；称为目标串，称为模式。

5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第次匹配成功。

6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为。

7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。

已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为。

8. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存.储地址为。

9. 三元组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的、和。

10.求下列广义表操作的结果：（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))】】】=== ;二、单选题（）1. 串是一种特殊的线性表，其特殊性体现在：Ａ．可以顺序存储Ｂ．数据元素是一个字符Ｃ．可以链式存储Ｄ．数据元素可以是多个字符（）2. 设有两个串p和q，求q在p中首次出现的位置的运算称作：Ａ．连接 Ｂ．模式匹配 Ｃ．求子串 Ｄ．求串长（ ）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))的结果串是：Ａ．BCDEF Ｂ．BCDEFGＣ．BCPQRST Ｄ．BCDEFEF（ ）4. 假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为 。

【课后习题】第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的长度= ，深度= ；二、判断题（如果正确，在下表对应位置打“√”，否则打“⨯”。