书名：数据结构（C语言描述）（慕课版）

主编：范翠香 罗作民

副主编：宋昕 李晔

啊啊啊啊啊为什么这么快就要期末考了TAT

得知期末手写代码的一瞬间  : ) → ；(

期末复习用，题目手打，答案来自老师：）

爱来自你理曲江校区 ；）

一、客观习题

        1.

                对于二维数组a，行下标由1到50、列下标由1到80，若该数组的起始位置为2000且每个元素占两个存储单元，并以行为主序顺序存储，则元素a[45][68]的存储地址为（C）9174 

                a[45][68] = [(45-1)*80 + (68-1)]*2 + 2000 = 7174 + 2000 = 9174

        2.

                设有一个10阶下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个元素占1字节空间，则A[5][4]地址与A[0][0]的地址之差为（B）19

                *

                * *

                * * *

                * * * *

                * * * *   

                想象一下（

        3.

                下面说法不正确的是（A）广义表的表头总是一个广义表

                 广义表是一种非连续性的数据结构，是线性表的一种推广

                表头可以是原子元素/表元素

                （B）广义表的表尾总是一个广义表   √

                （C）广义表难以用顺序结构存储      √                                     

                （D）广义表可以是一个多层次结构   √

        4.

               若串S="software"，其子串的个数是（B）37

                首先，子串必须连续，它们可以是字符串的任意一部分，包括整个字符串本身。

                对于一个长度为n的字符串，它的子串个数为n*(n+1)/2。  n = 8

                所以，对于串S="software"，它的子串个数为7*(7+1)/2 = 28。

                注意：这个公式不包括空字符串作为子串。如果包括空字符串，则子串个数为n*(n+1)/2 + 1= 37

        5.

                已知模式串为“aaab”，其next数组取值为（A）-1， 0， 1， 2

        6.

                设串s1=“ABCDEFG", s2="12345",用字符数组从下标0开始存储，函数strcat(s, t) 返回串s和串t的连接串，strsub(s, i, j)返回串s中从下标i开始的由连续j个字符组成的子串，strlen(s)返回串s的长度，则strcat(strsub(s1, 2, strlen(2)), strsub(s1, strlen(s2), 2))的结果是（D）CDEFGFG        

                首先，让我们逐步解析表达式 strcat(strsub(s1, 2, strlen(s2)), strsub(s1, strlen(s2), 2)) 的结果。

1. 首先，我们需要计算 strsub(s1, 2, strlen(s2))。根据给定的函数 strsub(s, i, j) 的定义，它将返回串 s 中从下标 i 开始的连续 j 个字符组成的子串。

   • 对于 s1=“ABCDEFG" 和 s2="12345"，我们有 strlen(s2) 的结果为 5。
   • 因此， strsub(s1, 2, strlen(s2)) 将返回字符串 CDEFG。

2. 然后，我们需要计算 strsub(s1, strlen(s2), 2)。根据函数 strsub(s, i, j) 的定义，它将返回串 s 中从下标 i 开始的连续 j 个字符组成的子串。

   • 对于 s1=“ABCDEFG" 和 s2="12345"，我们有 strlen(s2) 的结果为 5。
   • 因此， strsub(s1, strlen(s2), 2) 将返回字符串 EF。

3. 最后，我们需要将两个子串连接起来，即 strcat(strsub(s1, 2, strlen(s2)), strsub(s1, strlen(s2), 2))。

   • 根据给定的函数 strcat(s, t) 的定义，它将返回串 s 和串 t 的连接串。
   • 根据前面的计算结果，我们将连接子串 CDEFG 和子串 EF。
   • 因此， strcat(strsub(s1, 2, strlen(s2)), strsub(s1, strlen(s2), 2)) 的结果将是字符串 CDEFGEF。

                因此，strcat(strsub(s1, 2, strlen(s2)), strsub(s1, strlen(s2), 2)) 的结果是 CDEFGEF。

        7.

                二维数组A中的每个元素均是由10个字符组成的串，其行下标i=0，1，...，8，列下标j=1,2，...，10.若A按行先存储，元素A[8, 5]的起始地址与当数组A按列先存储时的元素（B）A[3, 10]的起始地址相同

                A[8][5]=8*10+5 = 85

                A[k, b]

                9*k+b=85   →k=9，b=4（按行先存储）→A[3][10]（按列先存储）

        8.

                广义表A=（a, b, (c, d), (e, (f, g)))，则Head（Tail（Head（Tail（Tail（A）））））的值为（D）d

        根据广义表A=（a, b, (c, d), (e, (f, g))），其中：

• Head(A) = a是A的第一个元素。
• Tail(A) = (b, (c, d), (e, (f, g)))是A去除第一个元素后的剩余部分。

        所以，Tail(Tail(A)) = ((c, d), (e, (f, g)))。

        再进一步计算：Head(Tail(Tail(A))) = (c, d)是Tail(Tail(A))的第一个元素。

        最后，计算：Head(Tail(Head(Tail(Tail(A))))) = d是Head(Tail(Tail(A)))的第一个元素。

        因此，Head(Tail(Head(Tail(Tail(A)))))的值为d。

        9.

                设广义表L=((a, b, c))，则L的长度和深度分别是（C）1和2

        给定广义表L=((a, b, c))，我们可以计算其长度和深度如下：

• 长度（Length）：广义表的长度是指其包含的元素数量。在这种情况下，L包含了1个元素（a,b,c），因此其长度为1。

• 深度（Depth）：广义表的深度是指嵌套的层数。在这种情况下，L的深度为2，因为它有两层嵌套。

        所以，广义表L的长度为1，深度为2。

        10.

                有一个50阶的三对角矩阵M，其元素mi, j（1<= i <= 50，1 <= j <= 50）按行优先顺序压缩存入下标从0开始的一维数组N中，元素m14,9在数组N中的下标是（B）98

        三对角矩阵是一种特殊的方阵，只有主对角线及其相邻的两条对角线上的元素非零，其余元素都为零。根据您的要求，我们可以构造一个50阶的三对角矩阵M。

        三对角矩阵M的形式如下：

[ a1  c1   0   0   0  ...  0   0   0 ]
[ b1  a2  c2   0   0  ...  0   0   0 ]
[ 0   b2  a3  c3   0  ...  0   0   0 ]
[ 0   0   b3  a4  c4  ...  0   0   0 ]
[ 0   0   0   b4  a5  ...  0   0   0 ]
[            ...            ]
[ 0   0   0   0   0  ... bn-1 an cn-1 ]
[ 0   0   0   0   0  ...  0  bn   an ]

        其中，a1, a2, ..., an 表示主对角线上的元素，b1, b2, ..., bn-1 表示上方对角线上的元素（即主对角线的上一条对角线），c1, c2, ..., cn-1 表示下方对角线上的元素（即主对角线的下一条对角线）。

        对于这样的三对角矩阵，我们可以将其压缩为一维数组，以便更高效地存储和处理。

        然后我就不懂了orz

        11.

                设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（C）模式匹配

        12.

                二维数组A的元素均是由6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放数组A至少需要（B）480字节

                （但是gpt给的答案是540.。迷惑了

        13.

                多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为（D）数组是多维结构，内存是一维结构

        14.

                对稀疏矩阵采用压缩存储，其缺点之一是（C）无法根据行、列号直接访问矩阵中的元素

        15.

                在KMP模式匹配算法中用next数组存放模式串的部分匹配信息，当模式串位置j处字符与目标串位置i处字符比较时，两个字符相等，则j的位移方式是（B）j=i+1

        

二、简答题

        1.

                为什么数组极少使用链式存储结构？

                因为数组使用链式结构存储时不仅需要额外占用更多的存储空间，而且不再具有随机存取特征，使得相关操作更加复杂。

        2.

                数组A中，每个元素的长度均为32位，行下标从-1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位，求

                （1）存放该数组需要多少个单元？

                （2） 存放数组第四列所有元素至少需要多少个单元？

                （3）数组按行优先存放时，元素A[7,4]的起始地址是多少？

                （4）数组按列优先存放时，元素A[4,7]的起始地址是多少？

                每个元素占32个二进制位，主存字长16位，因此每个元素占2个字长，行下标可平移至1到11。

                1) 242。该数组包括的元素个数总计为：(9-(-1)+1)*(11-1+1)=121，因为每个元素占2个字长，存放该数组所需单元总计为121*2=242个。

                2) 22.第4列包括的元素个数总计为：(9-(-1)+1)=11，每个元素占2个字长。因此，存放第4列所有元素至少需要单元为11*2=22个。

                3) S+182。LOC=S+((7-(-1))*(11-1+1)+(4-1))*2= S+182。

                4) S+142。LOC=S+((7-1)*(9-(-1)+1)+(4-(-1)))*2= S+142。

        3.

                字符串右旋转就是把字符串后面的若干个字符移动到字符串的前面。例如，”waterbottle“是”erbottlewat“右旋转（右移动3位）而来的。给定两个字符串s1和s2，请问：只通过子串判断和串连接两个操作可以判断s2是否为s1右旋转的结果吗？

        可以。假设s1=”erbottlewat”=xy(x=”erbottle”，y=”wat”)，则s2=”waterbottle”=yx。yx肯定是xyxy的子串，即s2=yx一定是xyxy= s1 s2的子串。因此，如果isSubString(s2，Concat(s1，s2))为真，则s2是s1旋转而来的，否则s2不是s1旋转而来的。

三、算法设计题

        1.

                编写一个算法，统计在输入字符串中各个不同字符出现的频度（字符串中的合法字符为26个英文字母和0~9这10个数字）

void Count()
{ //统计输入字符串中数字字符和字母字符的个数
  for(i=0;i<36;i++) num[i]=0;               //初始化
  while((ch=getchar())!=’\0’)               //依次读入字符进行判断
if(’0’<=ch<=’9’)                     //数字字符
 {
   i=ch-48;
   num[i]++;
}
else if(‘A’<=ch<=’Z’)                //字母字符
 {
   i=ch-65+10;
   num[i]++;
}
  for(i=0;i<10;i++)                      //输出数字字符的个数
printf(“%d数字i的个数”,num[i]);
  for(i=10;i<36;i++)                     //输出字母字符的个数
    printf(“%d字母字符i的个数”,num[i]);
}

        2.

                编写一个递归算法来实现字符串逆序存储，要求不另设串存储空间

#include <stdio.h>
void Inverse(char A[])
{ //递归实现字符串的逆序存储
  static int i=0;         //静态变量记录字符数组的下标
  char ch;
  ch=getchar();
  if(ch!=’\n’)           //’.’是字符串输入结束标志
{
  Inverse(A);     //递归
  A[i++]=ch;     //递归返回后存储字符串
}
  A[i]=’\0’;          //字符串最后加上结尾标记
}

int main()
{
  char a[50];
  Inverse(a);
  puts(a);
  return 0;
}

        3.

              设任意n个整数存放于数组A[n]中，编写一个算法，将所有正数排在所有负数前面，这里要求算法的时间复杂度为O(n)

void Partition(int A[],int n)
{ //数组A中存储n个整数，将A中所有正数排在所有负数的前面
  while(low<high)
{
  while(low<high&&A[low]>0)
    low++;
  while(low<high&&A[high]<0)
    high--;
  if(low<high)             //交换A[low]与A[high]
    {
      t=A[low];
      A[low++]=A[high];
      A[high--]=t;
}
}
}