数据结构串、数组和广义表练习题及答案

 

一 选择题

1．下面关于串的的叙述中，哪一个是不正确的？（B ）

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)))，其结果为（E ）

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中首次出现的位置的算法称为（C ）。

A．求子串             B．联接       C．匹配           D．求串长

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

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

5. 对稀疏矩阵进行压缩存储目的是（ C ）。

A．便于进行矩阵运算     B．便于输入和输出   C．节省存储空间     D．降低运算的时间复杂度

6. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D ）。

Head(Tail(Head(Tail(Tail(A)))))

A. (g)     B. (d)   C. c      D. d

7. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ C ）。

A. 1和1     B. 1和3   C. 1和2      D. 2和3

 

二、判断题

1．串是一种数据对象和操作都特殊的线性表。（√ ）

2. 稀疏矩阵压缩存储后，必会失去随机存取功能。（√ ）

3. 数组是同类型值的集合。（× ）

4. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ × ）

5. 一个稀疏矩阵Am*n采用三元组形式表示， 若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am*n的转置运算。（× ）

6. 二维以上的数组其实是一种特殊的广义表。（ √ ）

7. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。（× ）

 

三、填空 

1．空格串是指由空格字符（ASCII值32）所组成的字符串 ，其长度等于空格个数。

2．组成串的数据元素只能是 字符。

3．一个字符串中任意个连续的字符组成的子序列称为该串的子串 。

4. 数组的存储结构采用顺序存储结构存储方式。

5. 所谓稀疏矩阵指的是非零元很少(t＜＜m*n)且分布没有规律。

6. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: head(tail(tail(head(tail(head(A))))))。

 

四、应用题

1．名词解释：串

答：串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。 

 

2．描述以下概念的区别：空格串与空串。

答：空格是一个字符，其ASCII码值是32。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。 

 

3. 特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能？为什么？

答：特殊矩阵指值相同的元素或零元素在矩阵中的分布有一定规律，因此可以对非零元素分配单元（对值相同元素只分配一个单元），将非零元素存储在向量中，元素的下标i和j和该元素在向量中的下标有一定规律，可以用简单公式表示，仍具有随机存取功能。而稀疏矩阵是指非零元素和矩阵容量相比很小（t＜＜m*n），且分布没有规律。用十字链表作存储结构自然失去了随机存取的功能。即使用三元组表的顺序存储结构，存取下标为i和j的元素时，要扫描三元组表，下标不同的元素，存取时间也不同，最好情况下存取时间为O(1)，最差情况下是O(n)，因此也失去了随机存取的功能。 

 

4. 试叙述一维数组与有序表的异同。

答：一维数组属于特殊的顺序表，和有序表的差别主要在于有序表中元素按值排序（非递增或非递减），而一维数组中元素没有按元素值排列顺序的要求。 

 

5. 一个n╳n的对称矩阵，如果以行或列为主序存入内存，则其容量为多少？

答：n(n+1)/2（压缩存储） 或n2（不采用压缩存储） 

 

五、算法设计题

1．设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是,输出子串所在位置（第一个字符）,否则输出0.（注：用程序实现）

答：[题目分析]判断字符串t是否是字符串s的子串，称为串的模式匹配，其基本思想是对串s和t各设一个指针i和j，i的值域是0..m-n，j的值域是0..n-1。初始值i和j均为0。模式匹配从s0和t0开始，若s0=t0，则i和j指针增加1，若在某个位置si!=tj，则主串指针i回溯到i=i-j+1，j仍从0开始，进行下一轮的比较，直到匹配成功（j>n-1），返回子串在主串的位置（i-j）。否则，当i>m-n则为匹配失败。

    int index(char s[],t[],int m,n)

    //字符串s和t用一维数组存储，其长度分别为m和n。本算法求字符串t在字符串s中的第一次出现，如是，输出子串在s中的位置，否则输出0。

    {int i=0,j=0;

    while (i<=m-n && j<=n-1)

         if (s[i]==t[j]){i++;j++;} //对应字符相等，指针后移。

         else {i=i-j+1;j=0;} //对应字符不相等，I回溯，j仍为0。

    if(i<=m-n && j==n) {printf(“t在s串中位置是%d”,i-n+1);return(i-n+1);}//匹配成功

        else return(0); //匹配失败

    }//算法index结束

    main ()//主函数

     {char s[],t[]; int m,n,i;

      scanf(“%d%d”,&m,&n); //输入两字符串的长度

      scanf(“%s”,s); //输入主串

      scanf(“%s”,t); //输入子串

      i=index(s,t,m,n);

    }//程序结束

    [程序讨论]因用C语言实现，一维数组的下标从0开始，m-1是主串最后一个字符的下标，n-1是t串的最后一个字符的下标。若匹配成功，最佳情况是s串的第0到第n-1个字符与t匹配，时间复杂度为o（n）；匹配成功的最差情况是，每次均在t的最后一个字符才失败，直到s串的第m-n个字符成功，其时间复杂度为o（（m-n）*n），即o（m*n）。失败的情况是s串的第m-n个字符比t串某字符比较失败，时间复杂度为o（m*n）。之所以串s的指针i最大到m-n，是因为在m-n之后,所剩子串长度已经小于子串长度n，故不必再去比较。算法中未讨论输入错误（如s串长小于t串长）。     另外，根据子串的定义，返回值i-n+1是子串在主串中的位置，子串在主串中的下标是i-n。