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

电大《数据结构》2020-2021期末试题及答案一、单项选择题

1.一个数组元素a与(A)的表示等价。

A.*(a+i)B.a+iC.*a+iD.&a+I

2．执行下面程序段时，执行S语句的次数为(D)。

for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)S;

A.n2B.n2/2C.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-iB.n-i+1C.n-i-1D.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/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(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;deletes;

B.rear=rear->link;deleterear;

C.rear=rear->link->link;deleterear;

D.s=rear->link->link;rear->link->link=s->link;deletes;

二、填空题

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))，分别写出对它进行前序、中序、按层遍历的结果。

前序：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.指出算法的功能并求出其时间复杂度。

voidmatrimult(inta[M][N],intb[N][L],intc[M][L])

{//M、N、L均为全局整型常量

inti,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]×b[N][L]→c[M][L]。

时间复杂性为：O(M×N×L)。

2.设字符串String具有下列操作：

intLength()const;//计算字符串的长度

chargetData(k);//提取字符串第k个字符的值

若字符串Tar的值为“ababcabcacbab”，Pat的值为“abcac”时，给出算法执行后函数返回的结果。

#include“String.h”

intunknown(String&Tar,String&Pat)const{

for(inti=0;i<=Tar.Length()–Pat.Length();i++){

intj=0;

while(j<Pat.Length())

if(Tar.getData(i+j)==Pat.getData(j))j++;

elsebreak;

if(j==Pat.Length())returni;

}

return-1;

}

算法执行的结果是：函数返回值等于5。该算法即字符串的模式匹配。

3.设单链表结点的结构为LNode=(data,link)，阅读下面的函数，指出它所实现的功能。

intAA(LNode*Ha)

{//Ha为指向带表头附加结点的单链表的表头指针

intn=0;

LNode*p=Ha->link;

while(p){

n++;

p=p->link;

}

return(n);

}

算法功能：计算单链表的长度或计算单链表中结点的个数。

4.写出下列程序段的输出结果:

voidmain(){

stackS;

charx,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<

}//main

运行结果：stack

六、算法设计题

1.设有两个整数类型的顺序表A（有m个元素）和B（有n个元素），其元素均以升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以升序排列（表中允许元素重复）。

函数的原型如下所示。原型中的参数表给出参加运算的三个顺序表A、B与C。从C中得到执行结果。函数中用到顺序表的4个公有函数：

Length()求表的当前长度；

maxLength()求表的最大允许长度；

getData(intk)提取第k个元素的值；

setData(intk,intval)修改第k个元素的值为val。

template

voidmerge(SeqList&A,SeqList&B,SeqList&C);

答：

template

voidmerge(SeqList&A,SeqList&B,SeqList&C){

intm=A.Length(),n=B.Length(),mpn=m+n;

if(mpn>C.maxLength()){

cerr<<“合并后表的长度超出表C的最大允许长度”<<ENDL;

exit(1);

}

inti=0,j=0,k=0,av=A.getData(i),bv=B.getData(j);

while(i

if(av<=bv){C.setData(k++,av);av=A.getData(++i);}

if(av>=bv){C.setData(k++,bv);bv=B.getData(++j);}

}

if(i<M)

while(kelse

while(k}

2.假定在一个带表头结点的单链表L中所有结点的值按递增顺序排列，试补充下面函数，功能是删除表L中所有其值大于等于min，同时小于等于max的结点。

voidrangeDelete(ListNode*L,ElemTypemin,ElemTypemax)

{

ListNode*q=L,*p=L->link;

}

答：

while(p!=NULL){

if(p->data>=min&&p->data<=max){

q->link=p->link;deletep;p=q->link;

}

else{q=p;p=p->link;}

}

3.请分别写出在循环队列上进行插入和删除操作的算法。

循环队列定义如下：

structCyclicQueue{

ElemTypeelem[M];//M为已定义过的整型常量，表示队列长度

intrear,front;//rear指向队尾元素后一个位置，front指向队头元素

inttag;

/