设串长为n，模式串长为m，则KMP算法所需的附加空间为（ ）。
A. O(m)
B. O(n)
C. O(m*n)
D. O(nlog2m)
因为KMP算法涉及到next数组的存储，next数组是基于模式串长度计算的。
设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=’Beijing&Nanjing’，SUBSTR(S,4,5)=（ ）。
A. ‘ijing’
B. ‘jing&’
C. ‘ingNa’
D. ‘ing&N’
substr(S,i,k)：从第i个开始，取k个
设广义表L=((a，b，c))，则L的长度和深度分别为（ ）。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
广义表的长度，看最外层共有几个逗号，长度为：逗号+1
如(a,b,c)的长度就是3
(a,(b,(c)))的长度为2
深度的化看有几层括号
广义表((a),a)的表尾是（ ）。
A. a
B. (a)
C. ()
D. ((a))
常对数组进行两种基本操作是（ ）。
A. 建立和删除
B. 索引和修改
C. 查找和修改
D. 查找与索引
数组A[0…5,0…6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是（ ）。
A. 1175
B. 1180
C. 1205
D. 1210
（6 * 5 + 5）* 5
（总列数 * 当前列 + 当前行）* 元素占的空间？
1. 数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[8][5]的起始地址为（ ）
A. SA+141
B. SA+144
C. SA+222
D. SA+225
[(8-1) * 10 + 5] * 3 = 225
起始地址：225 - 3 = 222
二维数组为a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是______。
A. 1000
B. 860
C. 1140
D. 1200
X + ( 3 * 10 + 5 ) * 4 = 1000
x = 860
2. 设二维数组A[1…m，1…n]按行存储在数组B中，则二维数组元素A[i，j]在一维数组B中的下标为（ ）
A. n(i-1)+j*
B. n*(i-1)-j-1
C. i*(j-1)
D. i*m+i-1
3. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主进行存储，a[1]为第一元素，其存储地址为1，每个元素占一个地址空间，则a8 ，5的地址是()。
A.13
B.33
C. 18
D. 40
数组下标从1开始，只存储其下三角形元素，在a85的前面有7行，第1行有1个元素，第2行有2个元素，...第7行有7个元素，这府共有(1+7)x7/2= 28个元素,在第8行中，a8，5的前面有4个元素，所以a85前有28 +4=32个元素，其地址为33。
4. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，1,… 8，列下标j=1，2, … 10。设每个字符占一个字节。若A按行先存储，元素A[8，5]的起始地址与当A按列先存储时起始地址相同的元素是()。
A. A[8，5]
B. B. A[3， 10]
C. A[5，8]
D. A[0，9]
元素A[8，5]的起始地址与当A按列先存储时的A[i,元素的起始地址相同，即8x10+5-1=G-1)x9+i,将四个答案代入可得正确答案。
5. 已知有一维数组A[0… mxn- 1]，若要对应为m行n列的矩阵，则下面的对应关系()， 可将元素A[k](0Sk< mxn)表示成矩阵的第i行、第j列的元素(0Si<m0Sj<n)。
A.i=ko,j=k%m
B.i≈km，j=k96m
C.i=kn,j=ke%an
D.i=km，j=K%n
矩阵每一行有n个元素，则第:+1行、第:+1例的元素=ij在A中是第xi+j+1个元素，对应的下标k=nxi+j(因为下标从0开始)。反过来:i=kn,j=keom 4
1. 设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储A11为第一个元素，其存储地址为1，每个元素占一个地址空间，则A85地址为（）
A.23
B.33
C.18
D.40
2. 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个结点，其邻接矩阵为A[1…n, 1…n,. ]，且压缩存储在B[…k]，则的值至少为()。
A. n(n+1)/2
B. n2/2
C. (n- 1)(n+1)/2
D. n(n-1)/2
简单无向图的邻接矩阵是对称的，且对角线元素均是0，故压缩存储只需存储上三角或下三角(均不包括对角线)即可。故有(上三角形式): k= (n-1)+ (n-2)+ ..+1+0=n2- (1+2+ ...+ n) =n(n- 1)/2。
3. A[N，N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]q中，则对任上三角元素A[i]][j]对应T[k]的下标是()。
A.i(i-1)/2+j
B.j(j-1)2+i
C.i(j-1)/2+1
D.j(i-1)/2+1
1.B
2. 设有10阶矩阵A，其对角线以上的元素aij( 1Sjs10,1<i<j)均取值为一3，其他矩阵元素为正整数，现将矩阵A压缩存储放在一维数组F[m]中，则m为()
A.45
B.40
C.55
D.56
题目中对角线以下均为-3，不与其他元素重复，可知这45个元素只需用一个值来表示，故该矩阵只需用(100-45)+1=56个元素来表示。
1.
2. B
1. 稀疏矩阵的常见压缩存储方法有（ ）两种。
A. 二维数组和三维数组
B. 三元组和散列表
C. 三元组和十字链表
D. 散列表和十字链表
有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是：
每个元素要用行号，列号，元素值来表示，在用三元组表示稀疏矩阵，还要三个成员来记住，矩阵的行数列数，总的元素数，所以所需的字节数是10*（1+1+1）* 2+3 * 2 = 66。
1. m行n列的稀疏矩阵采用十字链表表示时，其中循环单链表的个数为______。
A. m+1
B. n+1
C. m+n+1
D. MAX{m,n}+1
1. 假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（ ）。
B
1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是____
Loc(A[0][0])+(i*N+j)*k
2. 广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是______
(x,y,z)
3. 现有一个稀疏矩阵，请给出它的三元组表。
采用稀疏矩阵的三元组表形式进行压缩存储，若要完成对三元组表进行转置，只要将行和列对换，这种说法（ ）。
A. 正确 B. 错误 C. 无法确定 D. 以上均不对
三元组转置：行列互换，然后再按行排序。
设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为（ ）。
A. 13
B. 33
C. 18
D. 40
按行存储是下三角，按列存储是上三角
下三角存储方式使用公式 (i*(i-1))/2 +J
得8*7/2+5=33
一个n阶对称矩阵A采用压缩存储方式，将其下三角+主对角部分元素按行优先存储到一维数组B中，则B中元素个数是______。
A. n
B. n2
C. n(n+1)/2
D. n(n+1)/2+1
一个n阶对称矩阵A[1…10，1…10]采用压缩存储方式，将其下三角+主对角部分元素按行优先存储到一维数组B[0…m]中，则A[8][5]元素在B中的位置k是______。
A. 32
B. 37
C. 45文章来源：https://www.toymoban.com/news/detail-753231.html
D. 60文章来源地址https://www.toymoban.com/news/detail-753231.html
why?
一个n阶对称矩阵A[1…10，1…10]采用压缩存储方式，将其上三角+主对角部分元素按行优先存储到一维数组B[0…m]中，则A[5][8]元素在B中的位置k是______。
A. 10
B. 37
C. 45
D. 60
why?
一个n阶（n>1）三对角矩阵A按行优先顺序压缩存放在一维数组B中，则B中的元素个数是______。
D???why?
一个n阶对称矩阵A[1…n，1…n]采用压缩存储方式，将其下三角+主对角部分元素按行优先存储到一维数组B[1…m]中，则A[i][j]（i≥j）元素在B中的位置k是______。
A. j(j-1)/2+i
B. j(j-1)/2+i-1
C. i(i-1)/2+j
D. i(i-1)/2+j-1
有一个三维数组A[-2…2][-4…5][2…6]，其中元素个数是（ ）。
A. 60
B. 250
C. 144
D. 396
二维数组为a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素，a[0][0]的存储地址为860，则a[3][5]的存储地址是______。
A. 1000
B. 860
C. 1140
D. 1200
二维数组为a[6][10]，每个数组元素占用4个存储单元，若按行优先顺序存放的数组元素a[3][5]的存储地址为1000，则a[0][0]的存储地址是______。
A. 872
B. 860
C. 868
D. 864
当用一个数组data[0…n-1]存放栈中元素时，栈底最好______。
A. 设置在data[0]处
B. 设置在data[n-1]处
C. 设置在data[0]或data[n-1]处
D. 设置在data数组的任何位置
设二维数组a[m][n]，每个数组元素占用k个存储单元，第一个数组元素的存储地址是LOC(a[0][0])，求按列优先顺序存放的数组元素a[i][j]（0≤i≤m-1，0≤j≤n-1）的存储地址为（ ）。
A. LOC(a[0][0])+[(i-1)×n+j-1]×k
B. LOC(a[0][0])+[i×n+j]×k
C. LOC(a[0][0])+[j×m+i]×k
D. LOC(a[0][0])+[(j-1)×m+i-1]×k
设二维数组a[1…5][1…8]，若按行优先的顺序存放数组的元素，则a[4][6]元素的前面有（ ）个元素。
A. 6
B. 28
C. 29
D. 40
设二维数组a[1…5][1…8]，若按列优先的顺序存放数组的元素，则a[4][6]元素的前面有（ ）个元素。
A. 6
B. 28
C. 29
D. 40
设二维数组a[1…5][1…8]，若按行优先的顺序存放数组的元素，则a[4][6]元素的前面有（ ）个元素。
A. 6
B. 28
C. 29
D. 40
在二维数组中，每个数组元素同时处于（ ）个向量中。
A. 0
B. 1
C. 2
D. n
一个n阶对称矩阵A[1…10，1…10]采用压缩存储方式，将其上三角+主对角部分元素按行优先存储到一维数组B[0…m]中，则A[5][8]元素在B中的位置k是______。
A. 10
B. 37
C. 45
D. 60
到了这里，关于基础习题-串 - 数组 - 广义表 - 矩阵-03的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
