[数组和广义表](5)题集_1

21
[ 数据结构 ] [ 数组和广义表 ]

1、假设有二维数组A(6×8)，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置(基地址)为1000，计算：

  1. 数组A的体积(即存储量)
  2. 数组A的最后一个元素a[5][7]的第一个字节的地址
  3. 按行存储时，元素a[1][4]的第一个字节的地址
  4. 按列存储时，元素a[4][7]的第一个字节的地址

一个元素6个字节，起始地址为1000，在内存寄存器里边，因为存储地址连续分配，则末地址为1000+686=1288，答案为：

  1. 体积为686=288
  2. 最后一个元素的第一个字节的地址为末地址减去一个元素占用的字节为：1282
  3. 按行存储时，元素a[1][4]的第一个字节的地址为：一行有八个元素，到达第一行的时候，地址到达1000+6*8=1048，又走了四个元素则1048+4*6=1072
  4. 按列存储时，元素a[4][7]的第一个字节的地址为：一列存储了四个元素，到达第七列的时候应该为：1000+(6*7+4)*6=1276

2、假设按低下标优先存储整数数组A(935*8)时，第一个元素的字节地址是100，每个整数占四个字节，问下列元素的存储地址是什么？

(1)、a(0000) (2)、a(1111) (3)、a(3125) (4)、a(8247)

  • 我们可以知道，起始地址就是首元素的起始地址，每个元素占4个字节的话，通过计算我们可以得知，有9个三维，每个三维又包含3个二维，而每个二维又包含着5个一维，每个一纬数组中有8个元素
  • a(0000)=100
  • a(1111)=(1358+158+18+1)*4=776
  • a(3125)=(3358+158+28+5)*4=1784
  • a(8247)=(8358+258+48+7)*4=4416

3、假设按低下标优先存储方式(以最右的下标为主序)，顺序列出数组A[2][2][3][3]中所有的元素a(i,j,k,l),为了简化表达，可以只列出(i,j,k,l)的序列

这题就是下标的下到上来，又从左往右来存放，如果映射到寄存器里面，就是从前往的序列，拿二维数组做个图示为：

img从高下标开始枚举

0000、1000、0100、1100、0010、1010、0110、1110、0020、1020、0120、1120、0001、1001、0101、1101、0011、1011、0111、1111、0021、1021、0121、1121、0002、1002、0102、1102、0012、1012、0112、1112、0022、1022、0122、1122

4、将书本中对称矩阵的压缩公式改为一个等式

公式：（矩阵起点0<=i<n），压缩数组起点为0开始

  • j(j+1)/2+i 当i<j时
  • i(i+1)/2+j 当i>=j时候

我们从上述公式可以发现，前面分式的变量均为MAX(i,j)，而后的遍历均为MIN(i,j)，则可转换成等式如下：

  • a(a+1)/2+b 其中a=MAX(i,j) b=MIN(i,j)

当然，按书上的公式下三角存储矩阵起始点为1的话，对应公式为i(i-1)+j-1,可以推理出上三角和等式，本人习惯于从0开始，则在这不做废话

5、设有上三角矩阵a(ij)(n*n),将其三条对角线上的元素逐行存于数组B[m]中(m充分大)，使得B[k]=a(i,j),且k=f1(i)+f2(j)+c，试推导出函数f1和f2和常数c(要求f1和f2中不含常数项)

其实三角矩阵的公式可由对称矩阵得来，只不过它多了一个空间存储常数项目，以下是三角矩阵的示意图

img

我们可压缩成n(n+1)/2+1个空间内，则可推理出关于k与ij的方程如下(压缩数组对应Matrix内的位置)：

  • k=j(j+1)/2+i 当i<=j时
  • k=n(n+1)/2+1 当i>j时

上述矩阵起始位置为0，下三角矩阵同理，只需把限制互换即可

从上述可推理出本题的答案：

  • k=ni-(n-j)-i(i-1)/2-1 (i<=j)
  • f(i)=(n+1/2)i-1/2i²
  • f(j)=j
  • c=-(n-1)

5.6、设有三对角矩阵a(ij)n*n，将其三条对角线上的元素存于数组B[3][n]中，使得元素B[u][v]=a(ij)，试推导出从(i,j)到(u,v)的下标变换公式

既然是三对角矩阵，就是对角线和对角线上下相邻的对角线上的元素，图示如下：

img

从上图可知，除了上限和下限为两个元素外，其他都为3个元素，则压缩空间可为：3n-2

又由题得知，我们存放的是在一个拥有3行n列的数组中，则应该如下所示：

img

从上我们可以很轻易的发现规律得到ij关于uv的方程，上对角线(黄色)i比j小一，对角线(红色)i与j相等，下对角线(蓝色)i比j大一，则得到：

  • u=(i-j)+1
  • v=Min(i,j)

7、设有三对角矩阵(aij)n*n，将其三条对角线上的元素存于数组B[3n-2]中，使得B[k]=a(i,j)求

  • 用i,j表示k的下标变换公式
  • 用k表示i，j的下标变换公式

我们还是用第一张图来看，可以得到：

  • k=i+j+i
  • i=(k+1)DIV3+1 (0<=k<=3n-1)
  • j=k+1-2(i-1)=k+1-2(kDIV3)

8、假设一个准对角矩阵：

img

写出一对下标(i,j)求k的转化公式。

  • i为奇数时k=i+j-2
  • i为偶数时k=i+j-1
  • 合并成一个公式，可写成：
  • k=i+j-(i%2)-1

9、已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存储结构(二维数组和三元组表)完成ai到an的求和运算优缺点

求和只对非零元素起作用，所以若使用二维数组，我们必须将整个二维数组全部遍历一遍，才能得到所有非零元素求和的结果，时间和空间都为(m*n)

若采用三元组结构，则在tu<mu * nu的时候，时间和空间只等于非零元的个数，若在tu等价于mu * nu的时候，则与二维数组存储 相同

10、求下列广义表操作的结果：

  1. GetHead【(p,h,w)】
  2. GetTail【(b,k,p,h)】
  3. GetHead【((a,b),(c,d))】
  4. GetTail【((a,b),(c,d))】
  5. GetHead【GetTail【((a,b),(c,d))】】
  6. GetTail【GetHead【((a,b),(c,d))】】
  7. GetHead【GetTail【GetHead【((a,b),(c,d))】】】
  8. GetTail【GetHead【GetTail【((a,b),(c,d))】】】

我们来复习一下，广义表的表头在书写形式串里可视作逗号前的那一个结点，它可以是原子，也可以是lists，表尾是除去表头的那一部分，它肯定是一个lists，有一个特殊的情况，空表无表头，也无表尾。

按上述思路，这题答案如下所示：

  1. 只有一层括号，里面若干个原子，则取得first逗号前的结点，为原子结点p
  2. 如上题，p后面的一部分组成的子表为表尾：(k,p,h)
  3. 有两层括号，代表有两个子表，则表头为：(a,b)
  4. 有两层括号，代表有两个子表，则表尾为：((c,d))
  5. 取到表尾为((c,d))再取得表头为:(c,d)
  6. 取到表头为：(a,b),再取到表尾为：(b)
  7. 取到表头为：(a,b)，再取得表尾:(b)最后再取到表头：b
  8. 取到表尾为：((c,d))，再取到表头为：(c,d)，最后取得表尾为(d)

11、利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子banana分别从下列广义表中分离出来。

  • L= (apple，pear ,banana ,orange);
  • L2= ((apple ，pear)，(banana ,orange));
  • L3= (((apple),( pear), (banana), (orange)));
  • L4= (apple, (pear), (( (banana)),(((orange)));
  • L5= ((((apple))),((pear))，(banana) ,orange);
  • L6= ((((apple)，pear) ,banana ) ,orange);
  • L7= (apple, ( pear，((banana ) ,orange));

依旧是书写形式串的操作，与上一题类同，答案如下：

  • GetHead(GetTail(GetTail(L)))
  • GetHead(GetHead(GetTail(L2)))
  • GetHead(GetHead(GetTail(GetTail(GetHead(L3)))))
  • GetHead(GetHead(GetHead(GetTail(GetTail(L4)))))
  • GetHead(GetHead(GetTail(GetTail(L5))))
  • GetHead(GetTail(GetHead(L6)))
  • GetHead(GetHead(GetTail(GetHead(GetTail(L6)))))

依旧牢记，表尾必定是lists，所以若在表尾取得原子，则至少要进行一次GetHead

12、按头尾链所示结点结构，画出下列广义表的存储结构图,并求它的深度。

(1) ((( ))，a, ((b,c), ( ), d), (((e))))
(2) ((((a)， b)), ((( )，d), (e, f)))

又到了画图时候了，这题的复习点在于：书写形式串，深度就为它的括号数值

img（1）

img（2）

13、已知以下各图为广义表的存储结构图，其结点结构和12题相同，写出各图表示的广义表

img(1)头尾链存储结构

对应的书写形式串为：((x,(y)),(((( ))),( ),(z)))

img

对应书写形式串为：(((a,b,( )),( )),(a,(b)),( ));

14、已知等差数列的第一项为a1，公差为d，试写出该数列前n项的和S(n)(n>=0)的递归定义

这是到数学题，直接套用公式即可：

img

  • S(n)=a1 当n==1时
  • S(n-1)+a1+(n-1)d 当n>1时

15、写出给定幂集的递归定义：

用P(A)表示A的幂集，定义谓词baset(X)表示X是一个集合，则：

P（A）=

  • {空集}

    • 当|A|=0时

  • P(A-{a})UI(P(A-{a}),a)

    • 当|A|不等于0时
  • 其中a属于A且I(X,y)={(x|∃x0)(x0属于X ∧ beset(x0) ∧ x=x0U{y})}

img采用大佬博客中的题解

16、试利用C语言中的增量运算“++”和减量运算“--”写出两个非负整数a和b相加的递归定义：

从题目描述中我们可以知道：a和b均为非负数，则在a+b的时候可定义为：a++，b--，则答案为：

  • Add(a,b)=a 当b==0时
  • Add(a,b)=a++,b-- 当b>0时

17、已知顺序表L含有n个整数，试分别以函数形式写出下列运算的递归算法：

  1. 求表中的最大整数；
  2. 求表中的最小整数；
  3. 求表中n个整数之和；
  4. 求表中n个整数之积；
  5. 求表中n个整数的平均值。

我们知道，递归可以保留当前函数的状态而进入下一层函数执行操作，这与栈的特性相对应，很多算法也运用到了这种记忆化的编程思想，而恰好，递归的代码简介，我们只需要把大的问题分解成尽量小的问题然后求解，找到问题的相同点即可。

求线性表的最大值，这儿可以看看各排序算法，无非就是在两个值之间进行比较，则我们可以把这个大的问题分解成相邻两值比较，取大值进行下一轮比较，则我们可以使用递归Stack的特性来记录当前结点的值，然后到尾端后再依次回溯比较，最后返回到最上层的就是该线性表中的最大值。

第五小有点不同，难点在于数学理论上：我们如何让最底层递归结束后还保持则与上一层相加之和呢？只有达到这点才能在返回到最上层的操作中求和除以总长度得到平均值，我们则需要在最下层中除以的值返回到上一层中再乘起来

我们可以知道，我们由总长度作为初始条件递归下去，使用链式存储的话，长度递减，而结点是从前往后，当然由于是线性表，涉及到总和长度并不需要考虑方向， 则：

假设线性表为1 2 3，长度为 3 的话，到达最底层结点的时候，长度递减为1.元素值为3，由于后继没有结点，则返回上一层，我们需要在上一层的操作中去乘以这一层的长度，才能让总和不改变，3的这一层长度为1，则到达上一层的时候，长度为2.原子为2,则可视作：2+（（2-1） 3）=5。这里还看不出什么，我们除以这一层的长度为2.25，返回上一层，对应元素为1，长度为3，这里需要将返回值乘3-1(之前的长度)得到2.252+3=8、

1-5小题测试代码如下所示：

#define MAXARRAYSIZE 30
#define OK 1
#define ERROR 0
#define _CRT_SECURE_NO_WARNINGS

typedef int Status;

#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
    int data;
    struct LNode* next;
}LNode;

typedef struct
{
    LNode* L;
    int leng;
}List;

Status CreateList(LNode**, int n);//创建一个线性表

Status MaxElemList(LNode* L, int n);//求线性表的最大值
Status MinElemList(LNode* L, int n);//求线性表的最小值
Status TotalElemList(LNode* L, int n);//求线性表元素之和
Status MulElemList(LNode* L, int n);//求线性表元素之积
float AverageList(LNode* L, int n);
int main()
{
    List L;
    printf("请输入线性表长度：");
    scanf("%d", &L.leng);
    CreateList(&(L.L), L.leng);

    system("pause");

    printf("%d\n", MaxElemList(L.L, L.leng));
    printf("%d\n", MinElemList(L.L, L.leng));
    printf("%d\n", TotalElemList(L.L, L.leng));
    printf("%d\n", MulElemList(L.L, L.leng));
    printf("%f\n", AverageList(L.L, L.leng));
    system("pause");
    return 0;
}
Status CreateList(LNode** L, int n)
{
    if (n == 0)
        return OK;
    if(!((*L)=(LNode*)malloc(sizeof(LNode))))return ERROR;
    scanf("%d", &(*L)->data);
    CreateList(&(*L)->next, --n);
}
int MaxElemList(LNode* L, int n)
{
    int max, tmp = 0;
    max = L->data;
    if (n > 1)
        tmp = MaxElemList(L->next, --n);
    if (tmp > max)
        max = tmp;
    return max;
}
int MinElemList(LNode* L, int n)
{
    int min, tmp = 0;
    min = L->data;
    if (n > 1)
        tmp = MaxElemList(L->next, --n);
    if (tmp < min)
        min = tmp;
    return min;
}
int TotalElemList(LNode* L, int n)
{
    int total, tmp = 0;
    total = L->data;
    if (n > 1)
        tmp = TotalElemList(L->next, --n);
    total += tmp;
    return total;
}
int MulElemList(LNode* L, int n)
{
    int mul, tmp = 1;
    mul = L->data;
    if (n > 1)
        tmp = MulElemList(L->next, --n);
    mul *= tmp;
    return mul;
}

float AverageList(LNode* L, int n)
{
    float avg = L->data;
    if (n > 1)
        avg = (avg + (((float)(n- 1)) * AverageList(L->next, --n))) / n;//两数之和除以多少就要乘以多少，才能得到最终的和除以最终的长度
    return avg;
}

从这题很明了的感受到递归的魅力！它可以保存之前的状态，到达最小子问题的时候，再逐步往上推(回溯)，从而得到最优解！

本文链接：

https://nullcode.fun/36.html
1 + 5 =
快来做第一个评论的人吧~