内容发布更新时间 : 2024/12/25 1:41:25星期一 下面是文章的全部内容请认真阅读。

电大《数据结构》2020-2021期末试题及答案

一、单项选择题

1. 一个数组元素a 与( A )的表示等价。 A. *(a+i) B. a+i C. *a+i D. &a+I

2．执行下面程序段时，执行S语句的次数为( D )。 for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) S;

A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2

3. 当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( B )，以节省参数值的传输时间和存储参数的空间。

A. 基本类型 B. 引用型 C. 指针型 D. 常值引用型

4. 输出一个二维数组b[m][n]中所有元素值的时间复杂度为( D )。 A. O(n) B. O(m+n) C. O(n2) D. O(m*n)

5. 某算法仅含程序段1和程序段2，程序段1的执行次数3n2，程序段2的执行次数为0.01n3，则该算法的时间复杂度为（ C ）。 A. O(n) B. O(n2) C. O(n3) D. O(1) 6. 多维数组实际上是由嵌套的（ A ）实现的。

A. 一维数组 B. 多项式 C. 三元组表 D. 简单变量

7. 在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需要从前向后依次前移（ C ）个元素。

A. n-i B. n-i+1 C. n-i-1 D. i

8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ A ）。 A. O(n) B. O(n/2) C. O(1) D. O(n2)

9. 设有一个n′n的对称矩阵A，将其上三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么第i行的对角元素A存放于B中（ C ）处。 A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2 10. 不带头结点的单链表first为空的判定条件是（ A ）。 A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL;

11. 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（ D ）。

A.s->link=p; p->link=s; B. p->link=s; s->link=p; C.s->link=p->link; p=s; D. s->link=p->link; p->link=s;

12. 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（ D ）。 A.s = rear; rear = rear->link; delete s; B.rear = rear->link; delete rear; C.rear = rear->link->link; delete rear;

D.s = rear->link->link; rear->link->link = s->link; delete s; 二、填空题

1. 数据结构包括逻辑结构、(存储结构)和数据的运算三个方面。 2. 基本数据类型是计算机已经实现了的(数据结构)。 3. 面向对象的特征应包括对象、类、(继承)、消息通信。

4. 模板类是一种数据抽象，它把(数据类型)当作参数，可以实现类的复用。

5. 在程序运行过程中不能扩充的数组是(静态)分配的数组。这种数组在声明它时必须指定它的大小。

6. 若设一个n′n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[j]的存储地址为(LOC(0,0)+(i*n+j)*d)。

7. 将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的(2n-I-1)*I/2+J)位置。 8. 若设串S = “documentHash.doc\\0”，则该字符串S的长度为(16)。

9. 在链表中进行插入和（删除）操作的效率比在顺序存储结构中进行相同操作的效率高。 10. 单链表中逻辑上相邻的结点而在物理位置上（不一定）相邻。

11. 若设L是指向带表头的单链表, 语句 L->link=L->link->link的作用是（删除）单链表中的第一个结点。 三、判断题（对/错）

1. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。错 2. 只有用面向对象的计算机语言才能描述数据结构算法。错

3. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型

和存储空间大小，由编译程序在编译时进行分配。错

4. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。对 5. 用字符数组存储长度为n的字符串，数组长度至少为n+1。对 6. 在线性链表中删除中间的结点时，只需将被删结点释放。错

7. 链式栈与顺序栈相比, 一个明显的优点是通常不会出现栈满的情况。对

8. 在使用后缀表示实现计算器类时用到一个栈的实例, 它的作用是暂存运算器对象。对 四、运算题

1. 对于一个n′n的矩阵A的任意矩阵元素a[j]，按行存储时和按列存储时的地址之差是多少。（设两种存储时的开始存储地址均为LOC(0, 0)，元素所占存储单元数均为d） 按行存储时与按列存储时，计算A[j]地址的公式分别为 LOC( i, j ) = LOC(0, 0) + ( i*n + j ) * d 及LOC’( i, j ) = LOC(0, 0) + ( j*n + i) * d 两者相减，得

LOC(i,j) – LOC’(i,j) = LOC(0,0)+(i*n+j)*d–LOC(0,0)–(j*n+i)*d =(i-j)*(n-1)*d

2. 设有一个10′10的矩阵A，将其下三角部分按行存放在一个一维数组B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。 根据题意，矩阵A中当元素下标I与J满足I≥J时， 任意元素A[I][J]在一维数组B中的存放位置为 I * (I + 1) / 2 + J， 因此，A[8][5]在数组B中位置为 8 * (8 + 1) / 2 + 5 = 41。

3. 设有一个二维数组A[11][6]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是1000，每个数组元素占4个存储字，则A[8][4]的地址在什么地方。

对于二维数组，若第一、第二维的元素个数为m和n，每个元素所占存储字数为d，首地址为LOC(0, 0)，则对于任一数组元素A[j]，它的存储地址为： LOC(i, j) = LOC(0, 0) + (i * n + j) * d

根据题意，LOC(8, 4) = LOC(0, 0) + (8 * 6 + 4) * 4 = 1000 + 52 * 4 = 1208。 4. 假定一棵二叉树的广义表表示为A(B(,D(G)),C(E,F))，分别写出对它进行前序、中序、按层遍历的结果。