串、数组习题
一.串4.3 4.6 4.7 求next函数值
二.数组单项选择题
1 设有数组A[i][j],数组的每个元素长度为3字
节,i=1,2,…,8,j=1,2,…,10,数组从内存首地址BA开始顺序存放.当数组以列为主序存放元素时,元素A[5][8]的存储首地址为[ ]
A.BA+141
B.BA+180
C.BA+222
D.BA+225
2 以行为主序存储二维数组A[50][100],设每个数据元素占2个存储单元,基
地址为10,则LOC(A[4][4])=[ ]
A.418
B.818
C.1010
D.1020
3 设二维数组A[1..m,1..n](即m行n列)按行存储在数组B[1..m*n]中,则二
维数组元素A[i][j]在一维数组B中的下标为[ ]
A.(i-1)*n+j
B. (i-1)*n+j-1
C. i*(j-1)
D. j*m+i-1
4 数组A[0..4,1..3,5..7]中含有元素的个数为[ ]
A.55
B.45
C.36
D.16
5对稀疏矩阵进行压缩存储的目的是[ ]
A.便于进行矩阵运算
B.便于输入和输出
C.节省存储空间
D.降低运算的时间复杂度
6.设A是n*n的对称矩阵,将A的对角线及对角线上方的元素按以列为主的次
序存放在一维数组B[0..n(n+1)/2-1]中.对上述任一元素ai,j(0= A.i(i+1)/2+j B.j(j+1)/2+i C. j(j+1)/2+i-1 D. i(i+1)/2+j-1 二.判断题 1数组可看成是线性结构的一种推广,因此与线性表一样,可以对它进行插入和删除等操作 2 稀疏矩阵压缩存储后,必会失去随机存取功能 3 二维数组中的每个元素都可以看成是一个一维数组的一维数组. 三.填空题 1.数组的存储结构采用_______存储方式. 2.数组的基本运算有_____和______ 3.设数组a[50][80]的基地址为2000,每个元素占2个存储单元,若以行为主序顺序存储元素,则元素a[45][68]的存储地址为_____;若以列为主序顺序存储元素,则元素a[45][68]的存储地址为_______. 4.用一维数组B按列优先顺序存放带状矩阵A中的非0元素ai,j(0= 5.所谓稀疏矩阵,指的是_______ 6.设n行n列的上三角矩阵A已压缩到一维数组B[0..n*(n+1)/2-1]中,若按行为主序存储,则元素ai,j对应的B中存储位置为____ 7.n阶对称矩阵a满足a[i][j]=a[j][i],(i,j=1,2,…,n),用一维数组t存储时,t的长度为____,当i=j时,a[i][j]=t[______],当i>j 时,a[i][j]=t[______],当i 参考答案 单项选择题 1.B 2.B 3.B 4.B 5.C 6.B 判断题 1 错误由数组的定义可知,数组可以看作是线性结构的一种推广,但是数组不能进行插入和删除操作,只能对指定元素进行存取和修改操作 2 正确稀疏矩阵的压缩存储方法有三元组表表示法和十字链表表示法,这两种方法都不能进行随机存取 3 正确由多维数组的定义可知本命题正确 填空题 1 顺序 2 给定一组下标,存取相应的元素;给定一组下标,修改相应的数据元素中某个数据项的值 3 9336 8890 4 1 3 5 不同元素(或非0元素)的个数远少于元素总数的矩阵 6当i= 7 n(n+1)/2, i(i+1)/2+j, i(i+1)/2+j, j(j+1)/2+i 数组典型例题 一、单项选择题 [例9-1]下列操作中，( )是数组的基本运算。 A．插入B．删除C．修改D．排序 解析：数组的基本运算只有两种，一种是给定一组下标，存取相应的元素；另一种是给定一组下标，修改相应数据元素中某个数据项的值。本题答案为：C。 (例9-2) 一维数组和线性表的区别是( )。 A．前者长度固定，后者长度可变B．后者长度固定，前者长度可变 C．两者长度均固定D．两者长度均可变 解析：由数组和线性表的定义可知，数组的长度是固定的，而线性表的长度是可变的。本题答案是：A。 [例9-3]二维数组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按行存储时，元素A[8，5]前共有(8—0)×(10—1+1)+(5—1)＝84个元素。对侯选答案进行类似计算可知，本题答案为：B。 (例9-4) 有一个100×90的稀疏矩阵，有非零元素(整型)10个。设每个整型数占2个字节，则用三元组表表示该矩阵时，所需的字节数为( )。 A．60 B．66 C．18 000 D．33 解析：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行 数、列数和非零元素个数；主表用手存放非零元素三元组，每个三元组由三个域组成，分别表示该元素的行号、列号和值。本题答案为：B 。 [例9-5] 若对n 阶对称矩阵A 以行序为主序方式将其下三角形的元素(包括主对角线上的所有元素)依次存放于一维数组B[0..(n(n+1))／2—1)中，则在B 中确定a i ，j (i A ．(1) 2i i j ++ B ．(1) 2j j i -+ C ．(1) 2i i j ++ D ．(1) 2j j i ++ 解析：参考9.2.3节有关对称矩阵的内容可知，本题答案为：D 。 二、填空题 (例9-6) 三维数组A[c 1..d 1，c 2..d 2，c 3..d 3]共含有 个元素。 解析：第一维大小为d 1-c l +1，第二维大小为d 2-c 2+1，第3维大小为d 3-c 3+1，共有(d l -c 1+1)×(d 2-c 1+1)×(d 3-c 3+1)个元素。 本题答案为：(d 1-c 2+1)×(d 2-c 1+1) ×(d 3-c 3+1)。 [例9-7] 设二维数组A[-20..30，-30..19]，每个元素占用4个存储单元，存储起始地址为200。如按行优先顺序存储，则元素A[25][18]的存储地址为 ；如按列优先顺序存储，则元素A[一18][一25]的存储地址为 。 解析：当按行优先顺序存储时，元素A[25][18]的存储地址为： LOC(A[25][18])＝LOC(A[-20][-30])+((25-(-20))×(19-(-30)+1) +(18-(-30)))×4 ＝200+9192＝9392 当按列优先顺序存储时，元素A[-18][-25]的存储地址为： LOC(A[-18][-25])＝LOC(A[-20][-30])+((-25-(-30))×(30-(-20)+1) +(-18-(-20))) × 4 =2004+1028=1228 本题答案为：9392；1228。 [例9-8] 将一个10阶对称矩阵A 用压缩存储方式(以行为主序存储下三角，且a 00＝1)进行存储，设每个元素占一个地址空间，则a 85的地址为 。 解析：矩阵下标从0开始，以行为主序存储下三角，a 85前有8行，第0行1个元素，第1行2个元素，……，第7行8个元素，共计(1+8)×8／2＝36个元素，第8行中a 85前有5个元素。所以，a 85前共有36+5＝41个元素，其地址为41+l ＝42。本题答案为：42。 [例9-9] 一稀疏矩阵有8个非零元素，矩阵元素为整型。现用三元组表方式对其进行压缩存储，假设整型元素占2个存储单元，则该三元组表至少占 个存储单元。 解析：三元组表由表头和主表两部分组成。表头包括三个整型域，分别表示矩阵的行 数、列数和非零元素个数；主表用于存放非零元素三元组，每个三元组由三个域组成，分别表示该元素的行号、列号和值。表头部分占3×2＝6个存储单元，主表部分占8×3×2＝48 个存储单元，总共占6+48＝54个存储单元。本题答案为：54。 三、应用题 [例9-10] 已知A n ×n 为稀疏矩阵，试从空间和时间的角度比较采用两种不同的存储 结构二维数组和三元组表完成求1 n ii i a -=∑运算的优缺点。 解析：由题目可知，所进行的运算是计算主对角线元素之和。对于采用二维数组方法存 储的矩阵，需要n 2个存储单元，但由于可以进行随机存取，即可以随机地访问主对角线上的元素，因此时间效率比较高。采用三元组表方法存储矩阵时是压缩存储，节省了存储空间，但在算法实现上需要从头到尾扫描整个三元组表，因此时间效率相对低一些。 (例9-11) 设给定n 维数组A[c 1..d 1][c 2..d 2)…[c n ..d n )，如果A[c 1][c 2]…[c n ]的存储地址为a ，每个元素占用1个存储单元，求A[i 1][i 2]…[i n ]的存储地址。 解析：若整个数组采用按行优先顺序存储，则A[i 1][i 2]…[i n ]的存储地址为： LOC(A[i 1][i 2]…[i n ])=a+((i 1-c 1)×(d 2-c 2+1)×…×(d n -c n +1) +(i 2-c 2)×(d 3-c 3+1)×…×(d n -c n +1) +(i n -c n ))×l 若整个数组采用按列优先顺序存储，则A[i 1][i 2]…[i n ]的存储地址为： LOC(A[i 1][i 2]…[i n ])=a+((i n -c n )×(d n-1-c n-1+1)×…×(d 1-c 1+1) +(i n-1-c n-1)×(d n-2-c n-2+1)×…×(d 1-c 1+1) +(i 1-c 1))×l (例 9-12) 设上三角矩阵A n ×n ，将其上三角元素逐行存于数组B[m]中，使得B[k]＝a ij ，且k=f 1（i ）+f 2（j ）+c 。试推导出函数f 1（i ）、f 2（j ）和常数C 。 解析：由前面内容的分析可得k 和i 、j 之间的关系为： (1)2k n n =+??? 当i ≤j 时，有 2111f (1)=22n i i ??-- ??? 2f (j)=j C=0 当i>j 时，有 12f (i)=f (j)=0 (1) 2n n C += 四、算法设计题 (例9—13) 已知一个n ×n 矩阵B 按行优先顺序存储在一个一维数组A[0..n ×n 一1) 中，试给出一个算法将原矩阵转置后仍存于数组A 中。 解析：矩阵转置是将矩阵中第i 行第j 列的元素与第j 行第i 列的元素位置互换。因此， 先确定矩阵与一维数组的映射关系：b i ，j 在一维数组A 中的下标为i ×n+j ，b i ，j 在一维数组A 中的下标为j ×n+i 。具体算法如下： void trans ( datatype A[]，int n) { int i ，j ； 当i>j 时，存放常数c datatype temp； for(i=0；i for(j＝0；j { temp=A[i * n+1]； A[i * n+j]=A[j * n+i]； A[j * n+i]=temp； } } (例9-14)假设稀疏矩阵A采用三元组表表示，试编写一个算法求其转置矩阵B，要求B也用三元组表表示。 解析：三元组表表示要求按行的顺序存放，所有转置过程不能直接将行下标和列下标转换，还必须使得转置后矩阵按顺序存放。因此，首先在A中找出第一列中的所有元素(即B 中第一行)，并把它们依次存放在转置矩阵B的三元组表中；然后依次找出第二列中的所有元素，把它们依次存放在三元组表B中；最后按此方法逐列进行，直到第n列的操作完成。值得注意的是，除了各元素的行号列号需要互换外，表头部分的行数列数也应该互换。具体算法如下： void transmatrix (smatrix * A，smatrix * B) { int p，k，col； B—>m=A—>n；//B的行数为A的列数 B—>n=A—>m；//B的列数为A的行数 B—>t=A—>t；//转置前后非零元素个数不变 if(B—>t!＝0) //非0矩阵 { k=0；//B表元素计数器，作当前放置元素指针 for(col=0；col for(p＝0；p if(A—>data[p].j＝＝co1) { B—>data[k]．i=A—>data[p].j； B—>data[k].j=A—>data[p].i B—>data[k].v＝A—>data[p].v； K++ } } } 第四章串习题及答案 一、基础知识题 4.1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 4.2 假设有如下的串说明： 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))的返回值是什么? 4.3 设T[0..n-1]="adaabaabcaabaa",P[0..m-1]="aab".当用模式串匹配目标串T时,请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 二、算法设计题： 4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度,则插入不执行。 4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 4.6 以HString为存储表示,写一个求子串的算法。 4.7 一个文本串可用事先给定的字母映射表进行加密。例如,设字母映射表为： a b c d e f g h i j k l m n o p q r s t u v w x y z n g z q t c o b m u h e l k p d a w x f y i v r s j 则字符串"encrypt"被加密为"tkzwsdf".试写一算法将输入的文本串进行加密后输出；另写一算法,将输入的已加密的文本串进行解密后输出。 4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。 4.9 将NaveStrMatch改写为输出目标串中所有也模式串匹配的有效位移。 *4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S,这里S和P的长度不一定相等。 4.11 若S和T是用结点大小为1的单链表存储的两个串,试设计一个算法找出S中第一个不在T中出现的字符。 答案： 4.1 简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答：空串是指不包含任何字符的串,它的长度为零。 空白串是指包含一个或多个空格的串,空格也是字符。 串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 主串和子串是相对的,一个串中任意个连续字符组成的串就是这个串的子串,而包含子串的串就称为主串。 静态分配的顺序串是指串的存储空间是确定的,即串值空间的大小是静态的,在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间,在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定,也是顺序存储空间)。 目标串和模式串:在串匹配运算过程中,将主串称为目标串,而将需要匹配的子串称为模式串,两者是相对的。 有效位移和无效位移：在串定位运算中,模式串从目标的首位开始向右位移,每一次合法位移后如果模式串与目标中相应的字符相同,则这次位移就是有效位移(也就是从此位置开始的匹配成功),反之,若有不相同的字符存在,则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 4、2 解：(1) stchr(*s,c)函数的效用是查找字符c在串s中的位置,若找到,则返回该位置,否则返回NULL。 因此: 执行p=stchr(s1,'t');后p的值是指向字符t的位置, 也就是p==&s1[5]。 执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。 执行p=strchr(s2,'6');之后,p的返回值是NULL。 (2)strcpy函数效用是串拷贝,strcat函数的效用是串联接。所以: 在执行strcpy(s3,s1); 后,s3的值是"Stocktom,CA" 在执行strcat(s3,","); 后,s3的值变成"Stocktom,Ca," 在执行完strcat(s3,s2);后,s3的值就成了"Stocktom,Ca,March 5,1999" 第四章数组参考答案 一、选择题：1、 B 2、C 3、D 4、C 5、C 6、B 7、D 8、B 9、B 10、A 二、填空题： 1、首地址 2、按行存放 3、一个字符 4、′\0′ 5、字符数组名或字符串 6、9 0 7、6 8、j-1 str[j-1] 9、62 10、s1[i]=s2[i]; 三、改错题 1、错误语句：int a[3][ ]={2,4,6,8,10,12,14,16,18}; 正确语句：int a[ ][3]={2,4,6,8,10,12,14,16,18}; 2、错误语句：if (str[2]>string) string＝str[2]; 正确语句：if (strcmp(str[2],string)>0) strcpy(string,str[2]); 3、错误语句：char c[5]={'C','h ','i','n','a '}; 正确语句：char c[6]={'C','h ','i','n','a '};或char c[ ]={“China”}; 4、错误语句：int a[3]={3*0} ; 正确语句：int a[4]; 5、错误语句：scanf(“%d%d%d”,&a); 正确语句：for (i=0; i<3; i++) scanf(“%d”,&a[i]); 或scanf(“%d%d%d”, &a[0], &a[1], &a[2]); 四、编程题 1、用数组来处理,求解Fibonacci数列前40项：1，1，2，3，5，8，13，21…。 #include 实验四字符数组与字符串 一、实验目的 ●了解并掌握一维数组与二维数组的定义方法 ●了解并掌握一维数组与二维数组的初始化方法及元素的引用方法 ●了解并掌握字符串、字符串数组以及字符串函数的使用方法 二、实验环境 ●个人计算机一台，PIII500（或同等性能）以上CPU，128MB以上内存，500MB以 上硬盘剩余空间。 ●Windows2000、Windows XP或Win 7操作系统 ●Code::Blocks(版本12.11或近似版本，英文版) 三、实验内容 1. 冒泡排序 编写程序，实现如下功能：从键盘上输入整数n(n<=100)，再输入n个整数，以冒泡排序算法将n个整数按从小到大的顺序进行排序。 /*example-14.c*/ #include "stdio.h" int main() { int num[100], n, i, j, t; /*输入整数的数量n*/ printf("Input n(<=100):"); scanf("%d", &n); /*输入n个整数*/ printf("Input %d numbers:\n", n); for(i=0; i /*输出排序后的数据*/ printf("After sorting:\n"); for(i=0; i 实验3 串和数组的相关操作 一，实验目的 理解并掌握串的逻辑结构和定长顺序存储方式； 理解串的相关基本算法； 编程对相关算法进行验证。 理解数组的逻辑结构和顺序存储方式； 掌握对称矩阵和稀疏矩阵的压缩存储方法； 掌握稀疏矩阵的三元组顺序表表示法和快速转置运算。 二，实验内容 3.1 串的模式匹配运算 编写一个程序，实现顺序串的各种模式匹配运算，并在此基础上设计主程序完成如下功能： （1）建立目标串s=‘abcabcdabcdeabcdefabcdefg’和模式串t=‘abcdeabcdefab’；（2）采用简单模式匹配算法求t在s中的位置； （3）由模式串t求出next值和nextval值； （4）采用KMP算法求t在s中的位置； （5）采用改进的KMP算法求t在s中的位置。 3.2 数组的操作 1.建立一个n*n的对称矩阵A；用动态分配的一维数组B对矩阵A进行压缩存储，输出矩阵A和一维数组B； 2.在B中查找对称矩阵A中第row行，第col列（下标从1开始）的元素，输出该元素值； 3.建立一个稀疏矩阵C，输入其行数，列数和非零元个数，用三元组顺序表存储该矩阵，并按矩阵形式输出稀疏矩阵B； 4.对稀疏矩阵C做快速转置运算得到矩阵D，并按矩阵形式输出转置后的矩阵D。【要求】 1.矩阵元素相关信息要从终端输入； 2.在三元组顺序表中按行优先顺序存放非零元素； 3.具体的输入和输出格式不限； 4.算法要具有较好的健壮性，对错误操作要做适当处理。 三，源代码及结果截图 3.1 #include #include 第四章串 一、选择题 1．下面关于串的的叙述中，哪一个是不正确的（）【北方交通大学 2001 一、5（2分）】 A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2 若串S1=‘ABCDEFG’, S2=‘9898’ ,S3=‘###’,S4=‘012345’,执行 concat(replace(S1,substr(S1,length(S2),length(S3)),S3),substr(S4,index (S2,‘8’),length(S2))) 其结果为（）【北方交通大学 1999 一、5 （25/7分）】A．ABC###G0123 B．ABCD###2345 C．ABC###G2345 D．ABC###2345 E．ABC###G1234 F．ABCD###1234 G．ABC###01234 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（） A．求子串 B．联接 C．匹配 D．求串长 【北京邮电大学 2000 二、4（20/8分）】【西安电子科技大学 1996 一、1 （2分）】 4．已知串S=‘aaab’,其Next数组值为（）。【西安电子科技大学 1996 一、 7 （2分）】 A．0123 B．1123 C．1231 D．1211 5．串‘ababaaababaa’的next数组为（）。【中山大学 1999 一、7】A．0 B．012121111212 C．0 D．0 6．字符串‘ababaabab’的nextval 为（） A．(0,1,0,1,04,1,0,1) B．(0,1,0,1,0,2,1,0,1) C．(0,1,0,1,0,0,0,1,1) D．(0,1,0,1,0,1,0,1,1 ) 【北京邮电大学 1999 一、1（2分）】 7．模式串t=‘abcaabbcabcaabdab’，该模式串的next数组的值为（），nextval 数组的值为（）。 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 【北京邮电大学 1998 二、3 （2分）】 8．若串S=’software’,其子串的数目是（）。【西安电子科技大学 2001应用一、2（2分）】 一填空题 1)数组的元素通过索引来访问，数组Array的长度为Array.length 。 2)数组复制时，"="将一个数组的引用传递给另一个数组。 3)没有显式引用变量的数组称为匿名数组。 4)JVM将数组存储在堆(堆或栈)中。 5)数组的二分查找法运用的前提条件是数组已经。 6)矩阵或表格一般用二维数组表示。 7)如果把二维数组看成一维数组，那么数组的元素是一维数组。 8)Java中数组的下标的数据类型是int 。 9)不用下标变量就可以访问数组的方法是foreach循环。 10)数组最小的下标是0 。 11)arraycopy()的最后一个参数指明长度。 12)向方法传递数组参数时，传递的是数组的引用。 13)线性查找法的平均查找长度为。 14)数组初始化包括数组的声明，创建和初始化。 15)数组下标访问超出索引范围时抛出数组索引超出绑定异常 16)浮点型数组的默认值是0.0 f 。 17)对象型数组的默认值是null 。 18)对象类型的数组虽然被默认初始化，但是并没有调用构造函数。 19)二维数组的行的长度可以不同。 20)数组创建后其大小不能改变。 二选择题 1.下面错误的初始化语句是__D_ A. char str[]="hello"; B. char str[100]="hello"; C. char str[]={'h','e','l','l','o'}; D. char str[]={'hello'}; 2.定义了一维int型数组a[10]后，下面错误的引用是_B__ A. a[0]=1; B. a[10]=2; C. a[0]=5*2; D. a[1]=a[2]*a[0]; 3.下面的二维数组初始化语句中，正确的是_B___ A. float b[2][2]={0.1,0.2,0.3,0.4}; B. int a[][]={{1,2},{3,4}}; C. int a[2][]= {{1,2},{3,4}}; D. float a[2][2]={0}; 4.引用数组元素时，数组下标可以是_D___ A. 整型常量 B. 整型变量 C. 整型表达式 D. 以上均可 5.定义了int型二维数组a[6][7]后，数组元素a[3][4]前的数组元素个数为__B__ A. 24 B. 25 C. 18 D. 17 6.下列初始化字符数组的语句中，正确的是_C___ A. char str[5]="hello"; B. char str[]={'h','e','l','l','o','\0'}; C. char str[5]={"hi"}; D. char str[100]=""; 7.数组在Java中储存在 C 中 串和数组自测卷答案姓名班级 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 （对应严题集4.1①，简答题：简述空串和空格串的区别） 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 8. 〖00年计算机系考研题〗设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。 答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 二、单选题（每小题1分，共15分） （ B ）1.串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2.设有两个串p和q，求q在p中首次出现的位置的运算称作： Ａ．连接Ｂ．模式匹配Ｃ．求子串Ｄ．求串长 （ 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))的结果串是： 习题五数组和广义表 一、单项选择题 1．常对数组进行的两种基本操作是（） A.建立与删除 B. 索引与修改 C. 查找与修改 D. 查找与索引2．对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由( )式确定. A.Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B.Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C.Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D.Loc[i,j]=[(n+1)*i+j]*k 3．稀疏矩阵的压缩存储方法是只存储 ( ) A.非零元素 B. 三元祖（i,j, aij） C. aij D. i,j 4. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。 A. 1175 B. 1180 C. 1205 D. 1210 5. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（）。 A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 6. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。 A. j=r[j].next B. j=j+1 C. j=j->next D. j=r[j]-> next 7. 对稀疏矩阵进行压缩存储目的是（）。 A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 8. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS)) C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 9. 广义表（（a,b,c,d））的表头是（），表尾是（）。 A. a B.（） C.（a,b,c,d） D.（b,c,d） 10. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 11. 下面说法不正确的是( )。 A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构 二、填空题 1．通常采用___________存储结构来存放数组。对二维数组可有两种存储方法：一种是以___________为主序的存储方式，另一种是以___________为主序的存储方式。 2. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B 中的第8个元素是A 中的第_ _行，第_ _列的元素。 第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量？试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构？线性结构和非线性结构各有什么特点？ 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同? (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。 习题四参考答案 一、选择题 1．下面关于串的叙述中，哪一个是不正确的（ B ） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 2．串的长度是指( A ) A. 串中包含的字符个数 B. 串中包含的不同字符个数 C. 串中除空格以外的字符个数 D. 串中包含的不同字母个数 3．设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ）A．求子串 B．联接 C．模式匹 配 D．求串长 4．设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是( C )。 A. O(m) B. O(n) C. O(n + m) D. O(n×m) 5. 串也是一种线性表，只不过( A )。 A. 数据元素均为字符 B. 数据元素是子串 C. 数据元素数据类型不受限制 D. 表长受到限制 6.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第 一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 7. 有一个二维数组A[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器 按字节编址，那么这个数组占用的存储空间大小是（ D ）个字节。 A. 48 B. 96 C. 252 D. 288 8. 设有数组A[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址BA开始 以列序为主序顺序存放，则数组元素 A[5，8]的存储首地址为( B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 9. 稀疏矩阵的三元组存储表示方法( B ) A. 实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可 B. 矩阵的非零元素个数和位置在操作过程中变化不大时较有效 C. 是一种链式存储方法 D. 比十字链表更高效 10. 用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有( A )域的结点表示。 B.4 C. 3 D. 2 二、填空题 1. 一个串的任意连续字符组成的子序列称为串的子串，该串称为主串。 2．串长度为0的串称为空串，只包含空格的串称为空格串。 3. 若两个串的长度相等且对应位置上的字符也相等，则称两个串相等。 4. 寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串。 习题2参考答案 一、单项选择题 1．A 2．A 3．D 4．C 5．D 6．A 7．B 8．B 9．C 10．A 11．D 12．B 13．C 14．B 15．C 16．C 17．B 18．D 19．C 20．A 二、填空题 1．线性 2．n-i+1 3．相邻 4．前移，前，后 5．物理存储位置，链域的指针值 6．前趋，后继 7．顺序，链接 8．一定，不一定 9．线性，任何，栈顶，队尾，队头 10．单链表，双链表，非循环链表，循环链表 11．使空表和非空表统一；算法处理一致 12．O(1)，O(n) 13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇 14．2、3 15．O(1) 三、简答题 1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。 2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。 3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。 4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个 第四章串和数组 一．选择题 1．串是一种特殊的线性表，其特殊性体现在（） A．可以顺序存储B．数据元素是一个字符 C．可以链式存储D．数据元素可以是多个字符 2．串的长度是（） A．串中不同字母的个数B．串中不同字符的个数 C．串中所含字符的个数，且大于0 D．串中所含字符个数 3．若串S=”software”，其子串数目是（） A．8 B．37 C．36 D．9 4．数组A[0..5，0..6]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素A[5][5]的地址为（） A．1175 B．1180 C．1205 D．1210 5．对矩阵压缩存储是为了（） A．方便运算B．节省存储空间C．方便存储D．提高运算速度 6．一个n 阶对称矩阵，如果采用压缩存储方式，则容量为（） A．n2B．n2/2 C．n(n+1)/2 D．(n+1)2/2 7．对稀疏矩阵采用压缩存储，其缺点之一是（） 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中每一个字符出现的次数。 3．采用顺序结构存储串，编写一个算法计算制定子串在一个字符串中出现的次数，如果该子串不出现则为0。 4．如果矩阵A中存在这样一个元素A[i][j]满足条件：A[i][j]是第i行中值最小的元素，且又是第j 列中值最大的元素，则称为该矩阵的一个马鞍点。编写一个算法计算出m×n的矩阵A的所有马鞍点。 5．编写一个算法，计算一个三元组表表示的稀疏矩阵的对角线元素之和。 6．系数矩阵只存放其非零元素的行号、列号和数值，用一维数组顺序存放之，行号-1作为 第 5 章数组和广义表 一、选择 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存 储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则 a85的地址为（ B ）。 A. 13 B. 33 C. 18 D. 40 2. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到 8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以 列为主存放时，元素A[5，8]的存储首地址为(B )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 3. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设 每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ B ）。 A. 808 B. 818 C. 1010 D. 1020 4. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0 到8，列下标j的范围从0到9。从供选择的答案中选出应填入下列 关于数组存储叙述中（）内的正确答案。 （1）存放A至少需要（ E ）个字节； （2）A的第8列和第5行共占（ A ）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元 素（ B ）的起始地址一致。 供选择的答案： （1）A. 90 B. 180 C. 240 D. 270 E. 540 （2）A. 108 B. 114 C. 54 D. 60 E. 150 （3）A. A[8,5] B. A[4,9] C. A[5,8] D. A[0,9] 5. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括 主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中， 则在B中确定aij（i 第4～5章串和数组自测卷答案姓名班级 一、填空题（每空1分，共20分） 1. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 , “/”的字符定位的位置为3。 4. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。 5. 设目标T=”abccdcdccbaa”，模式P=“cdcc”，则第 6 次匹配成功。 6. 若n为主串长，m为子串长，则串的古典（朴素）匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。 7. 假设有二维数组A6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为288 B ；末尾元素A57的第一个字节地址为1282 ；若按行存储时，元素A14的第一个字节地址为(8+4)×6+1000=1072 ；若按列存储时，元素A47的第一个字节地址为(6×7＋4)×6＋1000）＝1276 。 (注：数组是从0行0列还是从1行1列计算起呢？由末单元为A57可知，是从0行0列开始！) 8.设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为8950 。 答：不考虑0行0列，利用列优先公式：LOC(a ij)=LOC(a c1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L 得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2＝8950 9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素 的行下标、列下标和元素值。 10.求下列广义表操作的结果： （1）GetHead【((a,b),(c,d))】=== (a, b) ; //头元素不必加括号 （2）GetHead【GetTail【((a,b),(c,d))】】=== (c,d) ; （3）GetHead【GetTail【GetHead【((a,b),(c,d))】】】=== b ; （4）GetTail【GetHead【GetTail【((a,b),(c,d))】】】=== （d）; 二、单选题（每小题1分，共15分） （ D ）1.串是一种特殊的线性表，其特殊性体现在： Ａ．可以顺序存储Ｂ．数据元素是一个字符 Ｃ．可以链式存储Ｄ．数据元素可以是多个字符 （ B ）2.设有两个串p和q，求q在p中首次出现的位置的运算称作： 第 5 章数组和广义表 一、选择题 为第一元素，其 1.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a 11 的地址为（）。【燕山大学 2001 一、2 存储地址为1，每个元素占一个地址空间，则a 85 （2分）】 A. 13 B. 33 C. 18 D. 40 2. 有一个二维数组A[1:6，0:7] 每个数组元素用相邻的6个字节存储，存储器按字节编址， 那么这个数组的体积是（①）个字节。假设存储数组元素A[1，0]的第一个字节的地址是0， 则存储数组A的最后一个元素的第一个字节的地址是（②）。若按行存储，则A[2，4]的第 一个字节的地址是（③）。若按列存储，则A[5，7]的第一个字节的地址是（④）。就一般情 况而言，当（⑤）时，按行存储的A[I，J]地址与按列存储的A[J，I]地址相等。供选择的 答案：【上海海运学院 1998 二、2 （5分）】 ①-④： A．12 B. 66 C. 72 D. 96 E. 114 F. 120 G. 156 H. 234 I. 276 J. 282 K. 283 L. 288 ⑤： A．行与列的上界相同 B. 行与列的下界相同 C. 行与列的上、下界都相同 D. 行的元素个数与列的元素个数相同 3. 设有数组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 【南京理工大学 1997 一、8 （2分）】 4. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存 储单元，基地址为10，则LOC[5，5]=（）。【福州大学 1998 一、10 (2分)】 A. 808 B. 818 C. 1010 D. 1020 5. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000 的内存单元中，则元素A[5，5]的地址是( )。【南京理工大学 2001 一、13 （1.5分）】 A. 1175 B. 1180 C. 1205 D. 1210 6. 有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址， 假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A的最后一个元素的第一个字 节的地址是（①）。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是（②） 和（③）。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址是（④）和（⑤）。【上海海运学院 1996 二、1 （5分）】 ①-⑤:A.28 B.44 C.76 D.92 E.108 F.116 G.132 H.176 I.184 J.188 7. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元 （即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案： 素A 6665 A. 198 B. 195 C. 197 【北京邮电大学 1998 二、5 （2分）】 8. 二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范圈 从1到10。从供选择的答案中选出应填入下列关于数组存储叙述中（）内的正确答案。（1）存放A至少需要（）个字节； （2）A的第8列和第5行共占（）个字节； （3）若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素（）的起始地第四章-串-习题及答案.doc
C语言程序设计习题参考答案第四章(数组)
(实验四)符数组与字符串
数据结构_实验3_串和数组
数据结构第四章考试题库(含答案)
第4章数组练习题
数据结构数组和串自测题答案
(完整word版)数据结构第五章数组和广义表习题及答案
第4章 数据结构与算法 习题与答案
第4章串与数组习题参考答案
习题2参考答案及数组广义表习题
第四章串和数组习题
第 5 章 数组和广义表答案
数据结构 第4—5章串和数组自测卷答案
数据结构(C语言版)第5章 数组和广义表