数据结构(一)

第1章  序论
什么是数据?   
所有能输入到计算机中并能够被计算机程序处理的符号的总称,它是计算机程序加工的原料。
什么是数据元素?
数据的基本单位,在计算机程序中通常作为一个整体来进行考虑和处理。如数组中一个存储单元里面的数或者链表中一个结点。
什么是数据结构及种类?
数据元素相互之间存在的一种或多种特定关系的集合。主要研究数据逻辑结构和存储结构及其运算的实现。
数据结构的种类:
⏹集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系，如图 1.1所示。
图 1.1 集合
⏹线性结构：结构中的数据元素之间存在一个对一个的关系，如图 1.2所示。
图 1.2 线性结构
⏹树形结构：结构中的数据元素之间存在一个对多个的关系，如图 1.3所示。
图 1.3树结构
⏹图状结构或网状结构：结构中的数据元素之间存在多对多的关系，如图 1.4所示。
图 1.4 图
数据的逻辑结构
结构定义中的“关系”描述的是数据元素之间的逻辑关系,又称为逻辑结构。比如平常教学中所画的内存图,数组等为数据的逻辑结构。
数据的物理结构
数据结构在计算机中的实际表示形式称为数据的物理结构,又称为物理存储。
算法和算法分析
计算机算法是对特定问题求解步骤的描述，它是指令的有限序列。为解决某问题的算法与为该问题编写的程序含义是相同的。
常用的表示算法的语言有：自然语言、流程图、盒图、程序设计语言和伪代码。
算法的五个特性
有限性：算法必须在执行有限条指令之后结束，每条指令执行的时间也必须是有限的。
确定性：算法中每一条指令必须有确切的含义，读者和计算机在理解时不会产生二义性，并且在相同条件下，相同的输入只能得到相同的输出。
可行性：算法能把问题真正的解决。即不能是理论正确但无法在计算机上实现的算法。
输入：一个算法有零个或多个输入。
输出：一个算法有一个或多个输出。
●(2004年下)下面的程序段违反了算法的 (54) 原则。
void sam()
{
int n=2；
while(!odd(n))
n+=2；
printf(n)；
}
(54)A.有穷性  B.确定性 C.可行性 D.健壮性
解析:odd：判断是否是奇数!
算法设计的要求
数组和链表⏹正确性：算法应当满足具体问题的需求。
⏹可读性：算法应该能让人读懂，能被计算机运行。
⏹健壮性：算法应该具有容错处理能力，不容易被击垮。
⏹时间高效率与低存储量要求：效率指程序的执行时间(越短越好)，算法要占用计算机一定的存储量(越小越好)。
算法效率的度量
时间复杂度
根据不同的输入，将算法的时间复杂度分为三种情况：
(1)  最佳情况：使算法执行时间最少的输入。一般不进行算法在最佳情况下的时间复杂度分析。
(2)  最坏情况：使算法执行时间最多的输入。一般会进行算法在最坏时间复杂度的分析，因为最坏情况是在任何输入下运行时间的一个上限，而且对于某些算法来说，最坏情况是相当频繁的。
(3)  平均情况：算法的平均运行时间，可按三个步骤进行分析：将所有的输入按其执行时间分类；确定每类输入发生的概率；确定每类输入的执行时间。
(4)  时间复杂度的表示
算法时间复杂度符号O、Ω、Θ的定义分别如下。
⏹O记号：给出一个函数的渐进上界。给定一个函数g(n)，O(g(n))表示为一个函数集合的{f(n)：存在正常数c和n0，使得对所有的n≥n0，有O≤f(n)≤c·g(n)}。
⏹Ω记号：给出一个函数的渐进下界。给定一个函数g(n),Ω(g(n))表示为一个函数集合的{f(n)：存在正常数c和n0，使得对所有的n≥n0，有O≤c·g(n)≤f(n)。
⏹Θ记号：给出一个函数的渐进上界和下界，即渐进确界。给定一个函数g(n)，Θ(g(n))表示为一个函数集合{f(n)：存在正常数c1、c2和n0，使得对所有的n≥n0，有O≤c1·g(n)≤f(n)≤c2·g(n)}。
常见的时间复杂度如图 1.5所示。
图 1.5 常见时间复杂度的比较
●(2012年上)以下关于渐进符号的表示中，不正确的是 (62) 。
(62)A.n2=(n2) B.n2=O(n2) C.n2=O(n) D.n2=O(n3)
解析：等号左边为{f(n):…}中值,等号右边为O(g(n))的理解方式。
●(2004年下)下面函数中渐进时间最小的是(53)。
(53)A.T1(n)=n+nlogn　B.T2(n)=2n+nlogn  C.T3(n)=n2-logn  D.T4(n)=n+100logn
2.空间复杂度
一个算法的空间复杂度是指程序运行从开始到结束所需的存储量。主要包含算法自身实现所需要的辅助存储空间，不包含程序中原存储数据的空间。
⏹固定空间：在硬盘上的存储空间。
⏹可变空间：程序运行时占用的内存空间。
●(2007年下)关于算法与数据结构的关系，(64)是正确的。
(64)A.算法的实现依赖于数据结构的设计B.算法的效率与数据结构无关
C.数据结构越复杂，算法的效率越高D.数据结构越简单，算法的效率越高
●(2014年上)某个算法的时间复杂度递归式T(n)=T(n-l)+n，其中n为问题的规模，则该算法的渐进时间复杂度为(62)，若问题的规模增加了16倍，则运行时间增加(63)倍。
(62)A.Θ(n) B.Θ(nlgn) C.Θ(n2) D.Θ(n2lgn)
(63)A.16    B.64      C.256    D.1024
●(2006年上)设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为(59)。
A．O(lgn)  B．O(nlgn)  C．O(n)  D．O(n2)
●(2008年下)设某算法的计算时间表示为递推关系式T(n)= T(n-1)+ n(n>0)及T(0)=1，则该算法的时间复杂度为(65)。
(65)A.O(lgn)  B.O(nlgn)  C.O(n)  D.O(n2)
●(2010年上)若某算法在问题规模为n时，其基本操作的重复次数可由下式表示，则该算法的时间复杂度为(64)。
T(n)=
(64)A.O(n)  B.O(n2)  C.O(logn)  D.O(nlogn)
●(2009年下)某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d，其中，n为问题规模，a、b、c和d为常数，用O表示其渐进意义时间复杂度为(63)。
(63)A.O(n2)  B.O(n)  C.O(nlgn)  D. O(1)
●(2010年上)若对一个链表最常用的操作是在末尾插入结点和删除结点，则采用仅设尾指针的单向循环链表(不含头结点)时，(65)。
(65)A.插入和删除操作的时间复杂度都为O(1)  B.插入和删除操作的时间复杂度都为O(n)
C.插入操作的时间复杂度为O(1)，删除操作的时间复杂度为O(n)
D.插入操作的时间复杂度为O(n)，删除操作的时间复杂度为O(1)
●(2011年下)对n个元素值分别为-1、0或1的整列数组A进行升序排序的算法描述如下：统计A中-1、0和1的个数，设分别为n1、n2和n3，然后将A中的前n1个元素赋值为-1，第n1+1到n1+n2个元素赋值为0，最后n3个元素赋值为1。该算法的时间复杂度和空间复杂度分别为(64) 。
(64)A.      B.  C.          D.
●(2012年上)现要对n个实数(仅包含正实数和负实数)组成的数组A进行重新排列，使得其中所有的负实数都位于正实数之前。求解该问题的算法的伪代码如下所示，则该算法的时间和空间复杂度分别为 (65) 。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。