数据结构概论.docx

数据结构概论.docx

《数据结构概论.docx》由会员分享，可在线阅读，更多相关《数据结构概论.docx（19页珍藏版）》请在冰点文库上搜索。

数据结构概论

数据结构概论

一、单项选择题（共32题）

1.下列叙述中正确的是（）。

A.算法的效率只与问题的规模有关，而与数据的存储结构无关

B.算法的时间复杂度是指执行算法所需要的计算工作量

C.数据的逻辑结构与存储结构是一一对应的

D.算法的时间复杂度与空间复杂度一定相关

答案：

B

2.下列数据结构中，属于非线性结构的是（）。

A.循环队列B.带链队列C.二叉树D.带链栈

答案：

C

3.算法分析的两个主要方面是（）。

A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

答案：

A

4.决定选取何种存储结构时，一般不需要考虑（）

A.各结点的值如何B.结点的个数

C.对数据有哪些运算D.所用编程语言实现这种结构是否方便

答案：

A

5.数据的存储结构是指（）。

A.存储在外存中的数据

B.数据所占的存储空间量

C.数据在计算机中的顺序存储方式

D.数据的逻辑结构中计算机中的表示

答案：

D

6.数据的存储结构包括顺序、链接、散列和（）4种基本类型。

A.索引B.数组C.集合D.向量

答案：

A

7.在算法中，对需要执行的每一步操作，必须给出清楚、严格的规定，这属于算法的（）。

A.正当性B.可行性C.确定性D.有穷性

答案：

C

8.算法指的是（）

A.计算机程序B.解决问题的计算方法

C.排序方法D.解决问题的有限运算序列

答案：

D

9.

k=1;

for（i=0;i

for（j=0;j

a[i][j]=k++;

上述程序段的时间复杂度为（）。

A.O（n）B.O（0）C.O（n2）D.O

（1）

答案：

C

10.执行下面程序段时，S语句的执行次数为（）。

for（inti=1;i<=n;i++）

for（intj=1;j<=i;j++）

S;

A.n（n-1）/2B.n（n+1）/2C.n2/2D.n

答案：

B

11.下列叙述中正确的是（）。

A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

C.顺序存储结构能存储有序表，链式存储结构不能存储有序表

D.链式存储结构比顺序存储结构节省存储空间

答案：

A

12.下列叙述中正确的是（）。

A.一个逻辑数据结构只能有一种存储结构

B.数据的逻辑结构属于线性结构，存储结构属于非线性结构

C.一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

D.一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

答案：

D

13.数据结构中，与所使用的计算机无关的是数据的（）结构。

A.存储B.物理C.逻辑D.物理和存储

答案：

C

14.计算机算法指的是（）。

A.计算方法B.排序方法

C.解决问题的有限运算序列D.调度方法

答案：

C

15.算法的空间复杂度是指（）。

A.算法在执行过程中所需要的计算机存储空间

B.算法所处理的数据量

C.算法程序中的语句或指令条数

D.算法在执行过程中所需要的临时工作单元数

答案：

A

16.下面程序段的时间复杂性的量级为（）。

inti=0,s1=0,s2=0;

while（i++

{

if（i%2）s1+=i;

elses2+=i;

}

A.O

（1）B.O（logn）C.O（n）D.O（n2）

答案：

C

17.下面程序段的时间复杂度为（）。

for（inti=0;i

for（intj=0;j

a[i][j]=i*j;

A.O（m2）B.O（n2）C.O（m+n）D.O（m*n）

答案：

D

18.在数据结构中，从逻辑上可以把数据结构分成（）。

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

答案：

C

19.非线性结构是数据元素之间存在一种（）。

A.一对多关系B.多对多关系

C.多对一关系D.一对一关系

答案：

B

20.下列叙述中正确的是（）。

A.一个算法的空间复杂度大，则其时间复杂度也必定大

B.一个算法的空间复杂度大，则其时间复杂度必定小

C.一个算法的时间复杂度大，则其空间复杂度必定小

D.上述3种说法都不对

答案：

D

21.在数据结构中，数据的基本单位是（）。

A.数据项B.数据元素C.数据对象D.数据文件

答案：

B

22.算法分析的目的是（）。

A.找出数据结构的合理性

B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进

D.分析算法的易懂性和文档性

答案：

C

23.下列函数中，按它们在

时的无穷大阶数，最大的是（）。

A.lognB.nlognC.2n/2D.n!

答案：

D

24.（）是信息的载体，它能够被计算机识别、存储和加工处理。

A.数据B.数据元素C.结点D.数据项

答案：

A

25.下列程序段的时间复杂度为（）。

for（i=1;i

{

y=y+1;

for（j=0;j<=（2*n）;j++）

x++;

}

A.O（n-1）B.O（2n）C.O（n2）D.O（2n+1）

答案：

C

26.下面程序段的时间复杂度为（）。

i=1;

while（i<=n）

i=i*2;

A.O

（1）B.O（n）C.O（n2）D.O（log2n）

答案：

D

27.下面程序段的时间复杂度为（）。

a=0;b=1;

for（i=2;i<=n;i++）

{

s=a+b;

b=a;

a=s;

}

A.O

（1）B.O（n）C.O（log2n）D.O（n2）

答案：

B

28.数据结构是一门研究非数值计算的程序设计问题中，计算机的（）以及它们之间的关系和运算等的学科。

A.操作对象B.计算方法C.逻辑存储D.数据映象

答案：

A

29.在数据结构中，从逻辑上可以把数据结构分成（）。

A.动态结构和静态结构B.紧凑结构和非紧凑结构

C.线性结构和非线性结构D.内部结构和外部结构

答案：

C

30.算法分析的目的是（）。

A.找出数据结构的合理性B.研究算法中输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

答案：

D

31.算法分析的两个主要方面是（）。

A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

答案：

A

32.计算机算法指的是

（1），计算机算法必须具备输入、输出和

（2）等5个特性。

算法分析的目的是（3），它的两个主要方面是（4）。

数据结构中，与所使用的计算机无关的是数据的（5）结构。

供选择的答案：

（1）A.计算方法B.排序方法

C.调度方法D.解决问题的有限运算序列

（2）A.可行性、可移植性和可扩充性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

（3）A.找出数据结构的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改进D.分析算法的易懂性和文档性

（4）A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

（5）A.存储B.物理C.逻辑D.物理和存储

答案：

DBCAC

二、填空题（共5题）

1.数据结构按逻辑结构可分为两大类，它们分别是（）和（）。

答案：

线性结构非线性结构

2.数据结构分为逻辑结构和存储结构，循环队列属于（）。

答案：

存储结构

3.问题处理方案的正确而完整的描述称为（）。

答案：

算法

4.一个算法的效率可分为（）效率和（）效率。

答案：

时间空间

5.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的（）和运算等的学科。

答案：

操作对象关系

三、简答题（共12题）

1.设有两个算法在同一机器上运行，其执行时间分别为100n2和2n，要使前者快于后者，n至少要多大？

答案：

要使100n2快于2n时，必须满足100

，可以算出n的值为15时，2n恰好大于100n2，所以至少应该是15。

2.按增长率由小至大的顺序排列下列各函数：

（2/3）n、nn、n!

、2n、lgn、nlgn,n3/2、（3/2）n。

答案：

3.设有数据结构（D,R），其中：

D={1，2，3，4，5，6，7，8}

R={（1，2），（1，7）（1，8）（2，3），（2，4），（2，7），（2，8），（3，4），（3，5），

（3，6），（4，5），（4，6）}

试画出其逻辑结构图，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点，并指出该图属于何种逻辑结构。

答案：

开始结点是指无前驱的结点，如图中满足该定义的开始结点为1;

终端结点是指无后继的结点，如图中满足该定义的开始结点为5、6、7、8;

该逻辑结构是非线性结构中的图结构。

4.计算下面程序段的时间复杂度。

i=0;s=O;

while（s

{

i++;

s+=i;

}

答案：

上述算法中的基本操作为while循环语句，设while循环执行T（n）次，则有表达式

s=1+2+…+T（n）

即：

，可得

显然有:

所以该算法的时间复杂度为

。

5.求下列算法的时间复杂度。

count=0;x=1;

while（x）

{

x*=2;

count++;

}

答案：

O（log2n）

6.指出下面算法的功能并求出其时间复杂性。

intsuml（intn）

{

intp=1,s=0;

for（inti=1;i<=n;i++）

{

p*=i;

s+=p;

}

returns;

}

答案：

计算

的值。

时间复杂性为O（n）。

7.指出下面算法的功能并求出其时间复杂性。

voidmtable（intn）

{

for（inti=1;i<=n;i++）

{

for（intj=i;j<=n;j++）

printf（"i*j=%d\t",i*j）;

printf（"\n"）;

}

}

答案：

打印出一个具有n行的乘法表，第i行

中有n-i+l个乘法项，每个乘法项为i与

的乘积。

时间复杂性为O（n2）。

8.指出下面算法的功能并求出其时间复杂性。

voidcmatrix（inta[M][N],intd）//M和N为全局整型常量

{

for（inti=0;i

for（intj=0;j

a[i][j]*=d;

}

答案：

使数组a[M][N]中的每一个元素均乘以d的值。

时间复杂性为O（M*N）。

9.设n为正整数,分析下面程序段中加下划线的语句的执行次数。

for（inti=1;i<=n;i++）

for（intj=1;j<=n;j++）

{

c[i][j]=0.0;

for（intk=1;k<=n;k++）

c[i][j]=c[i][j]+a[i][k]*b[k][j];

}

答案：

10.设n为正整数,分析下面程序段中加下划线的语句的执行次数。

x=0;y=0;

for（inti=1;i<=n;i++）

for（intj=1;j<=i;j++）

for（intk=1;k<=j;k++）

x=x+y;

答案：

11.设n为正整数,分析下面程序段中加下划线的语句的执行次数。

inti=1,j=1;

while（i<=n&&j<=n）

{

i=i+1;

j=j+i;

}

答案：

i=1时，i=2，j=j+i=1+2=2+1，

i=2时，i=3，j=j+i=（2+1）+3=3+1+2，

i=3时，i=4，j=j+i=（3+1+2）+4=4+1+2+3，

i=4时，i=5，j=j+i=（4+1+2+3）+5=5+1+2+3+4，

……

i=k时，i=k+1，j=j+i=（k+1）+（1+2+3+4+…+k），

解出满足上述不等式的k值，即为语句i=i+1的程序步数。

解之得：

（向上取整，即大于等于括号内数的最小整数）

12.设n为正整数,分析下面程序段中加下划线的语句的执行次数。

inti=1;

do

{

for（intj=1;j<=n;j++）

i=i+j;

}while（i<100+n）;

答案：

for语句每执行一次，语句i=i+j将执行n次，而i的值会增加

因此，当for语句执行k次后，i的值将变为

故最终for语句的执行次数k为满足

的最小整数k，语句i=i+j的程序步数为n*k。

即

四、应用题（共5题）

1.试编写一个函数计算n!

*2n的值，结果存放于数组A[arraySize]的第n个数组元素中，0narraySize。

若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于某一个k（0kn），使得k!

*2k>maxInt时，应按出错处理。

可有如下三种不同的出错处理方式：

（1）用printf显示错误信息及exit

（1）语句来终止执行并报告错误；

（2）用返回整数函数值0,1来实现算法，以区别是正常返回还是错误返回；

（3）在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。

试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。

【解答】

#includeconstintarraySize=100;

constintMaxInt=0x7fffffff;intcalc（intT[],intn）

{inti,value=1;if（n!

=0）

{

intedge=MaxInt/n/2;

for（i=1;i

{

value*=i*2;

if（value>edge）return0;

}

value*=n*2;

}

T[n]=value;

printf（"A[%d]=%d\n",n,T[n]）;

return1;

}

voidmain（）

{intA[arraySize];

inti;

for（i=0;i

if（!

calc（A,i））

{

printf（"failedat%d.\n",i）;

break;

}

}

2.已知数组a[n]中的元素为整型，设计算法将其划分为左右两部分，左边所有元素为偶数，右边所有元素为奇数，并要求算法的时间复杂度为O（n）。

答案：

从数组的两端向中间比较，初始化两个变量i和j，其中i=0，j=n-1。

对元素a[i]

和a[j]执行如下循环：

①若a[i]为偶数，则i=i+l，循环执行①直到a[i]为奇数转至③;

②若a[j]为奇数，则j=j-1，循环执行②直到a[j]为偶数转至③;

③若i

上述算法的C语言描述如下：

voidfu_jo（inta[],intn）

{

inti=0,j=n-1,temp;

while（i

{

while（a[i]%2==0）i++;

while（a[j]%2!

=0）j--;

if（i

{

temp=a[i];a[i]=a[j];a[j]=temp;

i++;j--;

}

}

}

上述算法使用两层循环完成了对数组的扫描过程，其中a[i]从前向后开始扫描，a[j]则从后向前开始扫描，当i>=j时扫描即停止，因此虽然是两层循环但只对数组扫描了一遍，所以，该算法的时间复杂度为O（n）。

3.算法设计：

求整型数组a[n]中的最大值和最小值，并分析该算法的时间复杂度。

答案：

算法的伪代码描述如下：

①将数组中前两个元素进行比较，较大的值存放在max变量中，较小的值存放在min变量中;

②从第三个元素开始依次取出数组中的每一个元素a[i]，执行下列操作，直到最后一个元素：

a）如果a[i]>max，则max变量中的值被a[i]替换;

b）如果a[i]

③输出最大值max，最小值min。

算法的C语言描述如下：

voidfun_maxmin（inta[],intn,intmax,intmin）

{

if（a[0]>a[1]）

{

max=a[0];min=a[1];

}

else

{

max=a[1];min=a[0];

}

for（i=2;i<=n;i++）

{

if（a[i]>max）max=a[i];

if（a[i]

}

printf（"max=%d,min=%d.",max,min）;

}

上述算法只有一层循环，共执行n-2次，所以该算法的时间复杂度为T（n）=O（n）。

4.设计一个递归算法，计算出返回1至n之间的所有整数平方的和。

答案：

intSquareSum（intn）

{

if（n==0）return0;

elsereturnn*n+SquareSum（n-1）;

}

5.裴波那契（Fibonacci）数列的定义为：

它的第一项和第二项均为1，以后各项为其前两项之和。

若裴波那契数列中的第n项用Fib（n）表示，则计算公式为：

试编写出计算Fib（n）的递归算法和非递归算法。

答案：

递归算法如下：

intFib（intn）

{

if（n==1||n==2）

return1;//递归边界条件*／

else

returnFib（n-1）+Fib（n-2）;//使用递归公式求下一项

}

非递归算法如下：

intFibl（intn）

{

intc;//c代表当前项，

inta=1,b=1;//a和b代表当前项前面的第2项和第1项，并赋初值为1

if（n==1||n==2）

return1;//边界条件

for（inti=3;i<=n;i++）

{

c=a+b;//求出当前项

a=b;//把前面第一项赋给前面第二项

b=c;//把当前项赋给前面第一项

}

returnc;//返回所求的第n项

}