数据结构(Java)复习题及答案 1绪论_数据结构复习题附答案
数据结构(Java)复习题及答案 1绪论由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构复习题附答案”。
一、单项选择题
（B）1.计算机算法必须具备输入、输出和 等5个特性。A)可行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性
（C）2.数据结构中，与所使用的计算机无关的是数据的 结构； A)存储 B)物理 C)逻辑 D)物理和存储
（C）3.算法分析的目的是：
A)找出数据结构的合理性 B)研究算法中的输入和输出的关系 C)分析算法的效率以求改进 D)分析算法的易懂性和文档性
（A）4.算法分析的两个主要方面是：
A)空间复杂性和时间复杂性 B)正确性和简明性 C)可读性和文档性 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）是描述客观事物的数、字符以及所有能输入到计算机中被计算机程序加工处理的符号的结合。（B）是数据的基本单位，即数据结合中的个体。有时一个（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)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2)解答：
常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。
先将题中的函数分成如下几类： 常数阶：2100 对数阶：lgn K次方阶：n0.5、n(3/2)
指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn
注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。根据以上分析按增长率由小至大的顺序可排列如下：
(2/3)n
3、试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。解答：略
4、常用的存储表示方法有哪几种? 解答：顺序和链式，省略200字
5、设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 解答：
6、算法的时间复杂度仅与问题的规模相关吗? 解答：是
第一章 作业
1.任何计算机系统的主存可以看作是一个一维数组，多维数组实际存储仍是一组连续单元。请从数据的逻辑结构和物理结构的角度分析? 答：通过一个下标计算公式将二维数组的下标(i，j)映成一维数组的下标。例图b，下标=4×(J—l)十I
2.选择解决某种问题的最佳数据结构的标准是什么? 1）算法所需要的时间；
①程序运行时所需输入的数据总量； ②对源程序进行编译所需的时间； ③计算机执行每条指令所需的时间；
④程序中的指令重复执行的次数（数据结构中讨论算法时的重点）2）所需的存储空间量。
3.有一叠扑克脾，在计算机中存储这一叠扑克牌的内容(信息)答：用一个结点表示一张牌，每张扑克牌的内容包括牌的正反面（0、1）、花色（梅花
1、方块
2、红心
3、黑桃4）、点数、名称、下一张牌 逻辑结构是线性表；存储结构可以用链表或者顺序表表示
I=1执行n次
4、语句S的执行次数(B)
I=2执行n-1次
（1）for(i=1;i
I=n-1执行2次
for(j=n;j>=i;j--)n+(n-1)+………..2
S;(A)n(n+2)/2(B)
(n-1)(n+2)/2
(C)
n(n+1)/2(D)
(n-1)(n+2)(2)I=0;
(A)
Do{ J=I;Do{ S;
J++;
}while(j
}while(i
n(n-1)/2
(C)
n!(D)
n2
5、计算下面程序的时间复杂度（1）for(i=1;i
（C）
for(j=1;j
A[i][j]=i*j;(A)
O(m2)(B)
O(n2)
(C)
O(m*n)(D)
O(m+n)
（2）I=0;
（A）
s=0;while(s
(3)语句S的时间复杂度为O(1),(D)for(i=1;i
for(j=n;j>=i;j--)
S;(A)O(n2/2)(B)
O((n-1)(n+2)/2)
(C)
O(n2+n)(D)O(n2)
同题4（1）
S=1+2+3。。。。X=n X为执行次数
I=0，j 0~n，执行n+1次 I=1，j 1~n，执行n次 I=n，j n~n，执行1次(n+1)+………..1
x(x1)n2x2x2n0x118n2(A)
O(n)(B)O(2n)
(C)
O(n)(D)
O(n2)
6、写出下面程序的时间复杂度（1）for(i=1;i
for(j=1;j
1+（1+2）+（1+2+3）…..(1+2+….n)
答：O(n3)
(2)i=1;j=0;while(i+jj)j++;else i++;
} 答：O(n)
把（i+j）看成整体，每次递增1，频率n
