《数据结构》复习题及参考答案.pdfVIP

《数据结构》复习题及参考答案--第1页

《数据结构》复习题及参考答案

数据结构包括数据的逻辑结构数据的存储结构和数据的运算这三个方面的内容。

数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。

数据的存储结构可用四种基本的存储方法表示，它们分别是顺序链式索引散列。

数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。

非线性结构是数据元素之间存在一种：（B）

A、一对多关系B、多对多关系C、多对一关系D、一对一关系

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

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

算法分析的目的是（C）

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

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

计算机算法指的是（C）

A、计算方法B、排序方法C、解决问题的有限运算序列D、调度方法

计算机算法必须具备输入、输出和（B）等5个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性

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

数据结构和数据类型两个概念之间有区别吗？

简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元

素，而且还在其上定义了一组操作。

分析下面各程序段的时间复杂度：

for(i=0;in;i++)

for(j=0;jm;j++)

A[i][j]=0;

~0020

O（m*n）

`002101A2

分析下面各程序段的时间复杂度：

s=0;

fori=0;in;i++)

for(j=0;jn;j++)

s+=B[i][j];

sum=s;

~0021

2

O（n）

`002201A2

分析下面各程序段的时间复杂度：

x=0;

for(i=1;in;i++)

for(j=1;j=n-i;j++)

x++;

~0022

2

因为x++共执行了n-1+n-2+……＋1=n(n-1)/2，所以执行时间为O（n）

`002301A2

分析下面各程序段的时间复杂度：

i=1;

while(i=n)

i=i*3;

~0023

O（logn）

3

在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。

《数据结构》复习题及参考答案--第1页

《数据结构》复习题及参考答案--第2页

~0025

表中一半表长和该元素在表中的位置

`002603C1

判定一个栈ST（最多元素为m0