电大《数据结构》 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.01 n3，则该算法的时间复杂度为( C )。
A. O(n)
B. O(n2)
C. O(n3)
D. O(1)
6.多维数组实际上是由嵌套的( A )实现的。
A. 一维数组
B. 多项式
C. 三元组表
D. 简单变量
7.在一个长度为n的顺序表中删除第i个元素(OW i Wn-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;
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]中，贝U A[I][J] 在I WJ时将存放于数组B的（2n-l-1）*l/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)) ，分别写出对它进行前序、中序、按层遍历的结果。
前序：A,B,D,G,C,E,F
中序：B,G,D,A,E,C,F
按层：A,B,C,D,E,F,G
5.已知一棵二叉树的中序和后序序列如下，求该二叉树的前序序列。
中根序列：c,b,d,e,a,g,i,h,j,f
后根序列：c,e,d,b,i,j,h,g,f,a
先根序列：a,b,c,d,e,f,g,h,i,j
五、算法分析题
1.指出算法的功能并求出其时间复杂度。
void matrimult ( int a[M][N], int b[N][L], int c[M][L] )
{ //M 、N、L 均为全局整型常量
int i, j, k;
for ( i = 0; i < M; i++ )
for ( j = 0; j < L; j++ ) c[j] = 0;
for ( i = 0; i < M; i++ )
for ( j = 0; j < L; j++ )
for ( k = 0; k < N; k++ )
c[j] += a[k] * b[k][j];
}
功能为：矩阵相乘，即a[M][N] X b[N][L] T c[M][L]。
时间复杂性为：O(M X N X L)。
2.设字符串String 具有下列操作：
int Length ( ) const; // 计算字符串的长度
char getData ( k ); // 提取字符串第k 个字符的值
若字符串Tar 的值为“ a b a b c a b c a c b a b ”，Pat 的值为“ a b c a c ”时，给出算法执行后函数返回的结果。
#i nclude “ String.h ”
int unknown ( String& Tar, String& Pat ) const {
for ( int i = 0; i <= Tar.Length( ) - Pat.Length( ); i++ ) {
int j = 0;
while ( j < Pat.Length( ) )
if ( Data (i+j) == Data (j) ) j++;
else break;
if ( j == Pat.Length( ) ) return i;
}
return -1;
}
算法执行的结果是：函数返回值等于5。该算法即字符串的模式匹配。
3.设单链表结点的结构为LNode=(data,link) ，阅读下面的函数，指出它所实现的功能。int
AA(LNode *Ha)
{ //Ha 为指向带表头附加结点的单链表的表头指针
int n=0;
LNode *p=Ha->link; while(p) { n++;
p=p->link;
}
return(n);
}
算法功能：计算单链表的长度或计算单链表中结点的个数。
4.写出下列程序段的输出结果:
void main(){
stack S;
char x,y;
S.InitStack( );
x="c";y="k";
S.Push(x); S.Push("a"); S.Push(y);
S.Pop(S,x); S.Push("t"); S.Push("s"); while(!S.IsEmpty( )) { S.Pop(y); cout< cout<<Y<

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