数据结构练习题1：基本概念

1 抽象数据类型概念分析

1.可以用（抽象数据类型）定义一个完整的数据结构。

分析：
1）抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用数据对象、数据关系和基本操作集这样的三元组来表示，从而构成一个完整的数据结构定义。

2）抽象数据类型的两个重要特征：数据抽象和数据封装。
①数据抽象：用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口。（即外界使用它的方法）
②数据封装：将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。

抽象数据类型的理解

2. 逻辑结构与存储结构概念分析

1.数据的逻辑结构独立于其存储结构。
分析：数据的逻辑结构从实际问题出发，只采用抽象表达方式，独立于存储结构，数据的存储方式有多种选择。而数据的存储结构是逻辑结构在计算机上的映射，它不能独立于逻辑结构而存在。

2.数据结构的三要素：逻辑结构、存储结构和运算。

问题：逻辑结构的存储方式有多种选择什么意思？
是指既能顺序存储又能链式存储。

3.下面属于逻辑结构的是
A 顺序表 B 哈希表 C 有序表 D 单链表

4.以下与数据的存储结构有关的术语是
A.有序表 B.线性表 C.有向图 D.顺序表

5.以下与数据的存储结构无关的术语是
A 循环队列 B 链表 C 哈希表 D 栈

逻辑结构与存储结构： 3-5 CDD

有序表、线性表、有向图既能顺序存储，又能链式存储，是逻辑结构。
顺序表、循环队列、顺序栈为顺序存储。

属于逻辑结构 = 与存储结构无关 = 既能顺序存储又能链式存储
与存储结构有关 = 只能顺序存储或只能链式存储

栈逻辑结构对应的顺序存储结构为顺序栈，对应的链式存储结构为链栈。

队列的顺序存储结构是循环队列，链式存储结构是链队列，又叫做单链表。

线性表逻辑结构对应的顺序存储结构为顺序表，对应的链式存储结构为链表。

特殊案例：
有序表是指关键字有序的线性表，仅描述元素之间的逻辑关系，既可以顺序存储（使用数组）也可以链式存储（使用指针），不受存储结构制约，由于有序受到逻辑制约，属于逻辑结构。
哈希表，是个大数组，顺序存储。

问题1：如何区分数据结构和数据类型？

数据类型的运算主要是算数运算、逻辑运算等。
而数据结构运算主要是对数据的增删改查等。
数据类型和数据结构的区别

问题2：抽象数据类型有哪些？
栈、队列、树、图、集合、映射。

问题3：哈希表是散列存储，为什么做题时不考虑这种存储方式？

6.存储数据时存储的是数据元素的值和数据元素之间的关系。

7.链式存储设计时，各个不同结点存储空间可以不连续，但结点内的存储单元地址必须连续。

结点内什么意思？ 是value值域与next域结合，称这个结点为内部。

typedef struct LNode {

int value; // value中存放结点值域，默认是int型

struct Lnode *next;//指向后继结点的指针

}LNode; // 定义单链表结点类型

上述定义了一个结构体，包括两部分，一是值域，二是指针域；每当定义一个结点都会产生这两个区域。如下图：

value	next

这个value与next域必须是挨着的，称这个结点为内部。
结点内部一定是连续的。若第一个结点占用两个地址，那么value域的起始地址是1，则指针域的地址就是2。同理若第二个结点的value地址是10，则next域就是11。

参考：链式存储设计时，链表结点内的存储单元地址是如何分布的

3.综合选择题

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、拥有足够的情报

6.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数i元素之间的这种关系称为
A 规则 B 结构 C 集合 D 运算

7.设有如下遗产继承规则:丈夫和妻子可以互相继承遗产，子女可以继承父亲和母亲的遗产，子女间不能相互继承，则表示该遗产继承关系最合适的数据结构应该是
A 树 B 图 C 线性表 D 集合

8.下面关于抽象数据类型的描述错误的是
A.数据封装 B.用例驱动
C.信息隐藏 D.使用与实现分离

9.数据结构中，与所使用的计算机无关的是数据的
A 存储结构 B 物理结构 C 逻辑结构 D 物理和存储结构

10.下列关于算法的时间复杂度陈述正确的是
A 算法的时间复杂度是指执行算法程序所需要的时间
B 算法的时间复杂度是指算法程序的长度
C 算法的时间复杂度是指算法执行过程中所需要的基本运算次数
D 算法的时间复杂度是指算法程序中的指令条数

综合选择题：1-5 BADCC 6-10 BBBCC

4.综合判断题

1…在数据元素内数据项之间也有关系，在讨论数据的逻辑结构时应考虑。 × 逻辑结构看的是数据元素之间的关系

2.同一个算法，实现语言级别越高，算法执行的效率越低。√ 级别越高，需要额外执行的条件就越多，效率也就越低。

3.集合中任何两个数据元素之间都没有逻辑关系，而且组织形式松散。√ 除同属于一个集合外，没有其他任何关系。

5.时间复杂度相关习题

O(1)<O(log2n)<O(n)<O(nlog2n)<O($n^2$)<O($n^3$)<O($2^n$)<O(n!)<O($n^n$)

1.下面时间复杂度较小的是 A

2.以下程序段中语句"m++;"的语句频度为 C

int m=0,i,j;
for(i=1;i<=n;i++)
for(j=1;j<=2*ij++)m++;

A n B n+1 C n(n+1) D $n^2$
2+4+6+…+2n = n(n+1)

3.下列函数的时间复杂度是() 。

int func(int n){
int i=0,sum=O;
while(sum<n)  sum+=++i;
return i;
}

设语句频度为f(n)

1+2+3+…+f(n)<n

(1+f(n))f(n)/2<n

解得时间复杂度为O(n^(1/2) )

a=i++，这个运算的意思是先把i的值赋予a，然后在执行i=i+1；
a=++i，这个的意思是先执行i=i+1，然后在把i的值赋予a；

4.下面说法错误的是 D
A 某算法的时间复杂度为O($n^2$)，表明该算法的执行时间与$n^2$成正比
B 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O($n^2$)算法
C 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
D 算法原地工作的含义是指不需要任何额外的辅助空间

时间复杂度：一般总是考虑在最坏情况下的时间复杂度，以保证算法的运行时间不会比它更长，即它是最坏情况下估算算法执行时间的一个上界。

算法的时间复杂度只与规模相关吗？

算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复
杂度为准的。

算法原地工作是指算法所需的辅助空间是常量。
5.下面算法将一维数组a中的n个数逆序存放到原数组中，空间复杂度为()。

for(i=0;i<n/2;i++){
t=a[i];
a[i]=a[n-i-1];
a[n-i-1]=t}

该算法仅需要借助一个变量t，与问题规模n的大小无关，所以其空间复杂度为O(1)

很值得看的理解：
时间复杂度和空间复杂度计算
时间复杂度分析（含王道绪论习题）

6.以下关系式中，错误的是 D
A f(n) =O(g(n))
B g(n) = O(f(n))
C h(n) = O($n^2$)
D h(n) = O(nlog2n)

已知f(n)=O(g(n)),则必能推出g(n)=O(f(n))

7.
A.O(1) B.O(n) C.O($n^{-1}$) D.O($n^2$)
答案选B n趋与无穷，f(n)/n为常数

8.设n是描述问题规模的非负整数，下列程序段的时间复杂度是 B

x=0;
while(n>=(x+1)*(x+1))
x=x+1;

A.O(logn) B.O($n^1/2$) C.O(n) D.O($n^2$)

9.下列程序段的时间复杂度是

int sum = 0;
for(int i=1;i<n;i*=2)for (int j=0;j<i;j++)sum++;

A.O(logn) B.O(n) C.O(nlogn) D.O($n^2$)
i = 1,2,4,8,…,$2^{k-1}$（$2^{k-1}$<n)
T = 1+2+4+8+…+$2^{k-1}$=$2^k$-1
n<T<2n，时间复杂度为O(n)

6 时间复杂度计算方法（一、二、三层循环）