第4章习题解答
一、填空
1．字符串是一种特殊的线性表，特殊在于它的数据元素只能是 字符 ，特殊在于串可以作为一个 整体 参与所需要的处理。
    2．空格串是由 空格 组成的串，空串是 不含任何字符 的串，因此空格串和空串不是一个概念。
    3．字符串中任意多个 连续 字符所组成的子序列，被称作是这个串的“子串”，这个字符串本身则称为“主串”。
while语句都可以用for改写    4．我们说两个字符串相等，在计算机内部实际上是通过对相应位置上字符 ASCII 码的比较而得到的结论。
    5．设有串s=“I am a teacher”。该串的长度是 14 。
    6．设有三个串：s1=“Good”，s2=“Ф”，s3=“bye!”。则s1、s2、s3连接后的结果串应该是 “G
ood bye! ” 。
    7．所谓“数组”，是指n（n>1)个具有 相同 类型的数据的有序集合。
    8．矩阵与通常所说的 二维 数组有关。
    9．所谓“ 特殊矩阵 ”，是指那些元素在矩阵中的分布具有一定规律性的矩阵；而矩阵中的零元素个数远远多于非零元素的个数，但非零元素的分布却没有规律，这样的矩阵被称为“ 稀疏矩阵 ”。
    10．在一个n阶方阵A中，若所有元素都有性质：aij = aji (1≤i, j≤ n)，就称其为 对称 矩阵。
二、选择
1．设有两个串s1和s2。求s2在s1中首次出现的位置的操作称为 B 。
        A．连接        B．模式匹配        C．求子串        D．求串长
2．有串：“Ф”，那么它的长度是 B 。
        A．0        B．1        C．2        D．3
    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))的操作结果是串 D 。
        A．BCDEF        B．BCDEFG        C．BCPQRST        D．BCDEFEF
    4．设有一个8阶的对称矩阵A，采用以行优先的方式压缩存储。a11为第1个元素，其存储地址为1，每个元素占一个地址空间。试问元素a85的地址是 A 。
        A．33        B．30        C．13        D．23
    5．一个m*m的对称矩阵，如果以行优先的方式压缩存入内存。那么所需存储区的容量应该是 C 。
        A．m*(m-1)/2    B．m*m/2      C．m*(m+1)/2        D．(m+1)*(m+1)/2
    6．二维数组M的每个元素含4个字符（每个字符占用一个存储单元），行下标i从1变到5，
列下标j从1变到6。那么按行顺序存储时元素M[4][6]的起始地址与M按列顺序存储时元素 B 的起始地址相同。
        A．M[3][5]        B．M[4][5]        C．M[4][6]        D．M[5][5]
    7．二维数组M中的每个元素占用3个存储单元，行下标i从1变到8，列下标j从1变到10。现从首地址为SA的存储区开始存放A。那么该数组以行优先存放时，元素A[8][5]的起始地址应该是 C 。
        A．SA+141        B．SA+180        C．SA+222        D．SA+225
    8．设有一个5阶上三角矩阵A，将其元素按列优先顺序存放在一维数组B中。已知每个元素占用2个存储单元，B[1]的地址是100。那么A[3][4]的地址是 A 。
        A．116        B．118        C．120        D．122
（分析：把一个上三角矩阵按列优先顺序存放在一个一维数组B中，元素的顺序是：
                    a11a12a22a13……
A[3,4]的地址=100+a34前面的元素个数*2
            =100+（前3列的个数+本列a34前面的个数）*2
            =100+（（1+2+3）+2）*2=116
）
三、问答
1．为什么可以把二维数组视为是一种线性结构？
    答：实际上，二维数组是一种较为复杂的数据结构，数据元素之间的关系并不是线性的。不过，如果我们把它看作是其每个元素为一维数组的一个一维数组，那么就可以把二维数组视为是线性表的一种推广（因为一维数组即是线性表），因此可以说它的数据元素间的逻辑关系呈现出的是一种线性结构。
2．图4-34（a）所示为一个特殊矩阵A5 5，这种形式的矩阵被称作是“带状矩阵”，因为它的非零元素都分布在以主对角线为中心的一个带状区域里，其他位置上的元素全部为0。可以
以行优先的方式，将其压缩存储到一个一维数组里，如图4-34（b）所示。试出元素下标i、j与存储序号k间的对应关系。
图4-34  带状矩阵
    答：压缩存储元素下标i、j与存储序号k间的对应关系是：
                k = 2*i + j – 2
3．一个稀疏矩阵如图4-35所示。试问，它对应的三元组表是什么？
图4-35  稀疏矩阵示例
    答：它所对应的三元组表如下。
四、应用
    1．请将算法4-1改为用while循环来实现。
    答：改写的算法4-1可以是如下所示。
Concat_St(St1, St2)
{
  char St3[maxsize];        /* 创建一个新的顺序串为空 */
  St3_len=0;
  if (St1_len+St2_len>maxsize+1)    /* 新串放不下两个串 */
  {
    printf(“两串长度之和超长！”);
    return(NULL);
  }
  else
  {
    i=1；
    while (i<=St1_len)
    {
      St3[i]=St1[i];
      i++;
}
j=1;
while (j<= St2_len)
{
      St3[j+St1_len]=St2[j];
      j++;
}
St3_Len=St1_len+St2_len;
St3[St3_len+1]= “\0”;
return(St3);
}
}
2．算法4-2也可以这样来描述，直接核对相应位置上的字符是否相同，然后再分别情况做出判断：一是有不相同的字符出现，一是有一个字符串比另一个字符串长，最后则是两个串完全相等。按照这样的设计，改写算法4-2。
    答：按照这样的设计，算法4-2的描述如下。
Equal_St(St1, St2)
{
  i=1;
  while (St1[i] != “\0”)        /* 两串进行比较 */
  {
      if (St1[i] == St2[i])    /* 相等，继续比较 */
        i++;
      else                /* 不等，强制退出 */
        black;
    }
    if (St1[i] != St2[i])        /* 比较是由于相应位置上的字符不同而结束 */
      return (0);
    else
    {
      if (St1[i] != “\0” || St2[i] != “\0”)    /* 比较是由于长度不同而结束 */
        return (0);
      else
        return (1);
    }
}
3．算法：
Trans_St(St，ch1，ch2)
{
    i=1；
    While(St[i]！="\0")
    {
        if(St[i]==ch1)
          St[i]==ch2；
        i++；
    }
}
是通过while循环来实现将顺序串St中所有的字符ch1改为字符ch2的。请改写成用for循环来实现相同的功能。
    答：用for 循环改写的算法如下。
Trans_St(St, ch1, ch2)
{
  for (i=1; i<=St_len; i++)
    if (St[i] == ch1)
      St[i] = ch2;
}
    4．编写一个算法，将顺序串St中所有的大写字母全部换成小写字母。(提示：大写英文字母A~Z对应的ASCII码为65~90，小写英文字母a~z对应的ASCII码为97~122，在大写字母的ASCII码上加32，就是对应小写字母的ASCII码)
    答：算法编写如下。
Catosm_St(St)
{
  for (i=1; i<=St_len; i++)
    if ((A<=St[i])&&(St[i]<=Z))
      St[i]=St[i]+32;
}
    5．已知顺序串St，编写一个算法，将其中第i个字符开始连续的j个字符删除。（提示：先要判断所给参数是否合理，然后通过将第i+j开始往后的字符全部移动j个位置，完成删除的功能）
    答：算法编写如下。
Moveij(St, i, j)
{
  if (i+j<=St_len)
  {
    for (k=i+j; k<=St_len; k++)    /* 将i+j开始往后的所有字符前移j个位置 */
      St[k-j]=St[k];
    St_len=St_len-j;            /* 修改St的长度 */
    St[St_len]= “\0”;            /* 安放新的串结束符 */
}
else
printf (“参数不合理，无法进行删除！”); 
}
6．在算法4-12的最后，为了释放被删结点使用的存储空间，先做了操作：
    ptr->Next = NULL;   
把由指针ptr指向的最后一个要释放空间的结点的Next域设置为NULL，然后通过while循环完成释放。其实，由于知道要释放空间的结点共有m个，因此可以取消这一操作，改用for循环通过m来控制释放空间的结点个数。请试着按照这一思路改写那一小段算法。
    答：改写一小段算法如下。
for (j=1; j<=m; j++)
{
  ptr=rtr;
  rtr=rtr->Next;
  free(ptr);
}
    7．编写一个算法，功能是复制一个链串。
    答：复制一个完整的链串，是一件比较容易的事情。其算法起名为Copy_Lt()，参数为Lt1。具体编写如下。
Copy_Lt(Lt1)
{
ptr=Lt1_h;
rtr=malloc(size);
rtr->Data=ptr->Data;
Lt2_h=rtr;
ptr=ptr->Next;
while (ptr != NULL)
{
  qtr=malloc(size);
  qtr->Data=ptr->Data;
  rtr->Next=qtr;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。