综合题

共150分。

1、什么是数据的逻辑结构和物理结构?各有几种分类?

2、函数Random(n)需花费常数时间，请分析下面程序段的时间复杂度T(n)。

    i=1;

    while(i＜=n) { cout＜＜ Random(); i=i*5};

3、在下面数组a中链接存储着一个线性表，其表头“指针”为head==0，可用空闲空间表第一个元素的“指针”av==6；

    (1)请完善该线性表的逻辑关系图：

    请分别画出以下操作之后的线性表逻辑关系图及数组内容：

&nbs ……此处隐藏11716个字…… IZE]; //创建稀疏矩阵

    int matB[MAXSIZE][MAXSIZE];

    int matC[MAXSIZE][MAXSIZE];

    trimat_to_mat(int A[][3], matA); //将三元组A和B转换为二维矩阵

    trimat_to_mat(int B[][3], matA);

    add_mat(matC,matA,matB,A[0][1],A[0][2]);

    create_trimat(matC,A[0][1],A[0][2],C);

    }//void add_trimat

[解析] 由于只有两个矩阵的行数和列数均相等才能够相加，本题假设题干中的两个三元组均是由m行n列的稀疏矩阵转换而来的，则本题的算法思想为：

    ① 首先将两个三元组分别转换为两个稀疏矩阵A和B；

    ② 将两个稀疏矩阵进行相加后得到矩阵C。

    ③ 将矩阵C转换成三元组。