数据结构

  1. 数据结构是对客观事物的符号表示,如图形、声音等
  2. 数据元素是数据的基本单位
  3. 数据项是构成数据元素的不可分割的最小单位.
    一个数据元素可由若干个数据项组成,例如,一位学生的信息记录为一个数据元素,它是由学号、姓名、性别等数据项组成。
  4. 数据对象是具有相同性质的数据元素的集合。
  5. 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
    数据结构包括三方面的内容：逻辑结构、存储结构和数据的运算
    数据结构的形式定义为：数据结构是一个二元组
    Data_Structure=(D,S)
    其中：D是数据元素的有限集，S是D上（数据）关系的有限集。

题1.以下说法正确的是（）。
A.数据项是数据的基本单位 B.数据元素是数据的最小单位
C.数据结构是带结构的数据项的集合 D.数据元素可由若干数据项组成

解析:A是最小单位 B是基本单位 C是数据元素的集合

D正确

题2.数据的逻辑结构从形式上可用二元组(D,R)表示,其中R是()的有限集

A.算法 B.数据元素 c.数据项 D.数据关系

解析:D是数据元素的有限集，S是D上（数据）关系的有限集。

是数据关系的有限集
D正确

逻辑结构

逻辑结构是指数据元素之间的逻辑关系,与数据的存储无关,独立于计算机.

逻辑结构分两种，四类

线型结构：

线性表（一般线性表、栈、队列、串、数组） 一对一关系

非线性结构

非线性结构包括：集合、树形结构、图形结构（网状结构） 多对多

题1.以下数据结构中,不是线性结构的是()
A.栈 B.队列 C.串. D.二叉树

解析:二叉树属于树形结构
选D

题2.根据数据元素之间关系的不同特性,通常由四类基本结构,即:集合、线性结构、树型结构和_____结构。

解析： 逻辑结构分线性结构和非线性
非线性包括：集合、树形结构、图像结构（网状结构）
线性结构包括：线性表（一般线性表、栈、队列、串、数组）

所以填：图形或网状

选项只有两个空就填 线性 和 非线性 结构。

存储结构

  • 存储结构（物理结构）是指数据结构在计算机中的表示，它包括数据元素的表示和关系的表示。

  • 存储结构包括四种：顺序结构，链式结构,索引存储,散列存储

  • 顺序存储:把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来实现.
  • 链式存储:借助指示元素存储地址的指针来表示元素之间的逻辑关系
  • 索引存储:在存储元素信息的同时,还建立附加的索引表
  • 散列存储:根据元素的关键字直接计算出该元素的存储地址,又称哈希(hash)存储
  • 题1.在顺序存储、链式存储、索引存储、和散列存储这4种存储方式中，最基本、最常用的两种存储结构式_______________和________.

答案：顺序存储，链式存储

  • 题2.以下与数据的存储结构无关的术语是（）
    A.有序表 B.链表 C.顺序队列 D.哈希表

解析:
B属于链式存储,C属于顺序存储,D属于散列存储又称哈希存储
A:有序表是指逻辑上有序的一个线性表,仅仅描述元素之间的逻辑关系
对它进行存储的时候,既可以用顺序存储也可以用链式存储

答案:A

算法

  • 算法是对待特定问题求解步骤的一种描述,它是指令的有限序列,其中的每条指令表示一个或多个操作.此外,一个算法还具有下列5个重要特性:
  1. 有穷性。一个算法必须总是在执行有穷步后结束，且每一步都是在有穷时间内完成。
  2. 确定性。算法中每条指令必须有确切的含义，且相同的输入只能得到相同的输出。
  3. 可行性。算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
  4. 输入。一个算法有零个或多个输入。
  5. 输出。一个算法有一个或多个输出。
  • 题1.以下不属于算法特性的是（）
    A.可行性 B.输入 C.确定型 D.健壮性

解析:健壮性是设计一个”好”的算法的目标之一

答案:D

  • 通常设计一个”好”的算法应考虑达到以下目标:
  1. 正确性.算法应能够正确地求解问题.
  2. 可读性.算法能具有良好的可读性,以帮助人们理解.
  3. 健壮性.输入非法数据时,算法能适当地做出反应或进行处理,而不会莫名其妙的输出结果.
  4. 效率与低存储量需求.效率是指算法执行的时间,存储量需求是指算法执行过程中所需最大存储空间

  • 算法效率的度量是通过时间复杂度和空间复杂度来描述的.

  • 一个语句的频度是指该语句在算法中被重复执行的次数

  • 算法中所有语句的频度之和记为T(n),它是该算法问题规模n的函数,时间复杂度主要分析T(n)的数量级

  • 时间复杂度计算(重要考点)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    时间复杂度为常数时，则为O(1)
    加法规则:T(n)=T₁(n)+T₂(n)=O(f(n))+O(g(n))=O(max(f(n),g(n)))
    乘法规则:T(n)=T₁(n)×T₂(n)=O(f(n))×O(g(n))=O(f(n)×g(n))
    注意:加法和乘法规则不考虑常数


    常见的渐进时间复杂度为
    O(1)<O(㏒₂n)<O(n)<O(n㏒₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

  • 题1.算法分析的目的是()
    A.找出数据结构的合理性 B.研究算法中的输入和输出
    C.分析算法的效率以求改进 D.分析算法的易懂性

答案:C

  • 题2.若一个算法中的语句频度之和为T(n)=n+4n㏒₂n,则该算法的时间复杂度为_______________.

解析:
第一步:加法规则,保留之间最大的那个,n+4n㏒₂n 先不动
第二步:乘法规则:n的数量级就是n,时间复杂度不考虑常数,4去掉,剩下n㏒₂n
第三步:
根据常见的渐进时间复杂度为
O(1)<O(㏒₂n)<O(n)<O(n㏒₂n)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)
可得:O(n)<O(n㏒₂n)
所以把n去掉,所以答案就是O(n㏒₂n)

答案:
O(n㏒₂n)

  • 注意:做时间复杂度的题型时,不要忘记写O
  • 题3.下面两段程序的时间复杂度是()
    (1) 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    for(i=2;i<n;++i)
        ++x;
        for(j=1;j<=i-1;++j)
            a[i][j]=x;

    (2)i=1;
        while(i<=n)
            i=i*2;

A.O(n²),O(log₂n) B.O(n²),O(n²)
C.O(n),O(n) D.O(n),O(log₂n)

解析:

  • 做时间复杂度程序题时:只需看基本运算,基本运算就是指执行频度最高的那个语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
(1)
a[i][j]=x; 语句执行频度最高,只计算它的频度就可以了

for(i=2;i<n;++i)  //i从2到n,一共执行了n-1次
for(j=1;j<=i-1;++j) //由上条语句可知i=2,带入循环,j<=1
j<=1,所以j只能为1
所以a[i][j]=x; 只执行了一次
然后++i,i=3
j<=2,所以j可以是1和2
所以a[i][j]=x; 只执行了两次
n-1 i=2 j=1
    i=3 j=1,2
    ...
    i=2 j=1,2,....,n-1

求频度只需要把j的取值加起来就可以了
需用到数学公式:【（首+尾）*项数】/2
1+2+3+....n-1=(1+n-1)(n-1)/2=n(n-1)/2
求时间复杂度忽略常数,把1/2去掉,变n(n-1),加法规则保留最大值
所以(1)时间复杂度是O(n²)

(2)
(2)i=1;
    while(i<=n)
        i=i*2;

i=i*2; 是基本运算
可以设n=50
i=1 i<=50
i=2 i<=50
i=4 i<=50

由规律可知2ⁿ规律
设执行次数为t,又因为i<=n
2^t<=n
t<=log₂n    //数学公式:a^x=b x=loga(b)

所以时间复杂度:为O(log₂n)

所以答案:
A


练习题

  1. 数据结构被形式的定义为(K,R)，其中K是（ ）的有限集合，R是K上关系的有限集合。

A.算法 B.数据元素 C.数据操作 D.逻辑结构

  1. 数据元素是数据的最小单位。 （ ）

  2. 存储数据时，通常不仅需要存储各数据元素的值，而且还要存储（ ）。
    A.数据的处理方法 B.数据元素的类型
    C.数据元素之间的关系 D.数据的存储方法

  3. 逻辑上可以将数据结构分为（ ）。
    A.动态结构和静态结构 B.线性结构和非线性结构
    C.顺序结构和链式结构 D.初等结构和组合结构

  4. 按数据元素的逻辑关系来说，数据结构可分为四种：线性表、集合、树和图，其中树形结构中的数据元素之间存在“ ______”的关系。

  5. 有向图是一种非线性结构。 （ ）

  6. 以下属于逻辑结构的是（ ）。
    A.顺序表 B.哈希表 C.有序表 D.单链表

  7. 以下是4个算法的时间复杂度函数表达式，其中时间复杂度最小的（ ）。
    A.T(n)=2n³+3n²+1000 B.T(n)=n³-2000
    C.T(n)=n²㏒₂n+n² D.T(n)=n²+1000

  8. 算法是对特定问题求解步骤的一种描述，它具有____ 、____ 、可行性、输入和输出五个重要的特性。

  9. 求下列程序段的时间复杂度。
    (1) 

    1
    2
    3
    4
    for(i=0;i<=m;i++)
        for(j=0;j<n;j++)
            A[i][j]=0;

(2) 

1
2
3
y=0;
    while((y+1)*(y+1)<=n)
        y=y+1;

(3)

1
2
3
4
i=1;
while(i<=n)
    i=i*3;

答案

1.B
2.错误:数据元素是数据的基本单位,数据项是数据的最小单位
3.C
4.B
5.一对多
6.正确
7.C 一般带”顺序”,”哈希”,”链”,就是存储结构
8.D
9.有穷性,确定性
10.
(1)O(mn) //外层循环执行了m次,内层循环执行了n次则时间复杂度为O(mn)
(2)O(n^(1/2))
设循环体共执行了t次,每循环一次,循环变量y加1,最终t=y.故t²<=n
得T(n)=O(n^(1/2))
(3)O(log₃n)