数据结构(java)复习题及答案 1绪论

一、单项选择题

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

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

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

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

A）存储B）物理0逻辑D）物理和存储

（C）3,算法分析的目的是：

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

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

（A）4.算法分析的两个主要方面是：

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

0可读性和文档性D）数据复杂性和程序复杂性

（C）5,计算机算法指的是：

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

6,数据结构是研究数据的（A）和（B）以及它们之间的相互关系，并对这种结构定

义相应的（C）,设计出相应的（D）,从而确保经过这些运算后所得到的新结构是

（E）结构类型。

供选择的答案

A.B:1.理想结构2.抽象结构3.物理结构4逻辑结构

C.D.E:1.运算2.算法3.结构4,规则5.现在的6.原来的解答：34126

7.（A）是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序加工处

理的符号的结合。

CB）是数据的基本单位，即数据结合中的个体。有时一个（B）由若干个（C）组

成，在这种情况下，称（B）为记录。（C）是数据的最小单位。

（D）是具有相同特性的数据元素的集合。

（E）是带有结构特性的数据元素的结合。

被计算机加工的数据元素不是孤立无关的，它们彼此之间普通存在着某种联系，通常将

数据元素的这种联系关系称为（G）。

算法的计算量和问题规模的联系用（H）表示。

供选择的答案：

A-F:1.数据元素2.符号3.记录4.文件5.数据6.数据项7.数据对象

8.关键字9.数据结构

G:1.规则2.集合3.结构4.运算

H:1.现实性2.难度3.复杂性4.效率

解答：5167933

二、判断题

1,数据元素是数据的最小单位。

解答：错，因为数据元素是数据的基本单位，通常它是由若干个数据项组成，数据项

才是数据的最小单位。

2,数据结构是带有结构的数据元素的结合。

解答：正确

3,数据结构、数据元素、数据项在计算机中的映像（或者表示）分别称为存储

结构、结点、数据域。

解答：正确

4,数据项是数据的基本单位。

解答：错，因为数据元素才是数据的基本单位

5,数据的逻辑结构是指各数据之间的逻辑关系，是用户按使用需要而建立的。

解答：正确

6,数据的物理结构是指数据在计算机内实际的存储形式。

解答：正确

三、简答题

1、简述下列概念：数据、数据元素、数据项、数据结构、逻辑结构、存储结构、线

性结构、非线性结构。

解答：

•数据：指能够被计算机识别、存储和加工处理的信息载体。

•数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶

点、记录。数据元素有时可以由若干数据项组成。

•数据项是不可分割的最小单位。

•数据结构：指的是数据之间的相互关系，即数据的组织形式。普通包括三个方面的内

容:数据的逻辑结构、存储结构和数据的运算。

•逻辑结构：指数据元素之间的逻辑关系。

•存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。

•线性结构：数据逻辑结构中的一类.它的特征是若结构为非空集，则该结构有且惟独

一个开始结点和一个终端结点，并且所有结点都有且惟独一个直接前趋和一个直接后

继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

•非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接

前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。

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

2100,(3/2)\(2/3)n,n,nJ5,n!,2n,Ign,mgn,n(3/2)

解答：

常见的时间复杂度按数量级递增罗列，挨次为:常数阶0(1)、对数阶0(logn)、线

性阶0(n)、线性对数阶0(nlogn)、平方阶0(n“、立方阶0(m)、k次”方阶0

(m)、指数阶0(2”

先将题中的函数分成如下几类：常数阶：2⑼对数阶：Ign

K次方阶：n°\n<3/a

指数阶(按指数由小到大排)：mA(3/2)\2\n!、n”

注意：(2/3)5由于底数小于1,所以是一个递减函数，其数量级应小于常数阶。

根据以上分析按增长率由小至大的顺序可罗列如下:

(2/3)”<2ioo<Ign<no's<n"<i*n<(3/2)“<2n<n!〈n"

n

3、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。

解答:略

4、常用的存储表示方法有哪儿种？

解答:顺序和链式，省略200字

5、设有两个算法在同一机器上运行，其执行时间分别为100/和2”，要使前者快于后

者，n至少要多大？

解答：

6、算法的时间复杂度仅与问题的规模相关吗？

解答：是

第一章作业

1.任何计算机系统的主存可以看做是一个一维数组，多维数组实际存储仍是一组连续单元。

请从数据的逻辑结构和物理结构的角度分析？

答：通过一个下标计算公式将二维数组的下标（i,j）映成一维数组的下标。例图b,下标

=4x（J—1）十I

1234167

1

2

3

4

（a）从用户的观点看数组

列I2367

行1234123412323412341234

（b）从计算机的角度按列看数组

行I24

列1234567123445671234567

（c）从计算机的角度按行看数组

2.选择解决某种问题的最佳数据结构的标准是什么？

1）算法所需要的时间；

%1程序运行时所需输入的数据总量；

%1对源程序进行编译所需的时间；

%1计算机执行每条指令所需的时间；

%!程序中的指令重复执行的次数（数据结构中讨论算法时的重点）

2）所需的存储空间量。

3.有一叠扑克脾，在计算机中存储这一叠扑克牌的内容（信息）

答：用一个结点表示一张牌，每张扑克牌的内容包括牌的正反面（0、1）、花色（梅花1、

方块2、红心3、黑桃4）、点数、名称、下一张牌

逻辑结构是线性表；存储结构可以用链

图13扑克牌的存储

表或者顺序表表示

图L2扑克牌的逻辑结构

4、语句S的执行次数(B)

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

for(j=n;j>=i;j-)

1=1执行n次

S：1=2执行n-1次

(A)n(n+2)/2(B)(n-l)(n+2)/2息Cj)执必/次牌(D)(n-l)(n+2)

⑵1=0；(A)n+(n-1)+2

1=0j0~n执行n+l

Do(

1=1,j2旅行n次

J=l；

Do{l=n,n-执行1次

j(n+l)n,

S；1

J++;+-

}while(j<=n);

I++；

}while(i<=n);

(A)(n+2)(n+l)/2(B)n(n-l)/2(C)n!(D)成

5、计算下面程序的时间复杂度

C1)for(i=1;i<=m;i++)(C)

for(j=l;jv=n;j++)

A[i][j]=i*j；

(A)0(012)(B)O(H2)(C)O(m*n)(D)

0(m+n)

(2)1=0;(A)S=1+2+n

3oooooooouX—

s=0;X为执行次数x(x+1)

while(s<=n){

I++；

x2+=0

S+=l;}

-