1.几个最初等的基本概念？
·数据：是用于描述客观事物的数值或字符，它在计算机中就是指所有能输入到计算机中并被计算机程序所处理的符号的总称。
eg：整数，实数，字符串等都是数据。
·数据元素：也称为结点，它是数据的基本单位，在计算机程序中通常作为一个整体进行处理；一个数据元素可由若干个数据项组成。
·数据项： 是数据的不可分割的最小单位；
eg：学生记录就是一个数据元素，这个数据元素由学好、性别、姓名等数据项组成。
·数据对象：数据对象是性质相同的数据元素的集合，是数据的一个子集。
eg：大写字母就是一个数据对象，大写字母数据对象是集合。
2.什么是数据结构？数据结构是研究什么的？
·数据结构的定义：数据结构是指相互之间存在某种关系的数据元素的集合。
·数据结构的研究方向：数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。
主要有三个方面的内容：
对数据的运算和操作，即算法；
数据的逻辑结构；算法的设计取决于数据的逻辑结构
数据的物理存储结构；算法的实现取决于数据的物理存储结构。
3.数据结构的形式化定义
数据结构是一个二元组，如数据结构ds=（d，r）
其中，d是数据元素的有限集合，r是定义在d上的关系的有限集合。
eg：有如下数据，即一个矩阵：
其对应的二元组表示为：b=（d，r）
d= r=
r1表示行关系，r2表示列关系
它们各自定义如下：
r1= r2=
4.数据结构的逻辑结构是什么？它有哪些分类？
·数据结构的逻辑结构：
数据结构的逻辑结构描述的是数据元素之间的逻辑关系，它与数据的存储结构无关，同一逻辑结构可以对应多种存储结构
·逻辑结构的分类：
①线性结构
该结构中的结点之间存在一一对应关系，开始结点与结尾结点是唯一的，其余的结点都有且仅有一个前导与一个后继。
eg：线性表
②非线性结构
该结构中的结点之间存在一对多或者多对多的对应关系
eg：树型结构、图型结构。
5.数据结构的物理结构是什么？常见的数据存储方法有哪些？
·数据的物理结构：
数据的物理结构也叫存储结构，是数据的逻辑结构在计算机中的表示（也叫映像）。它包括数据元素的表示和数据关系的表示。当数据元素是由若干数据项组成时，对数据项的表示就称之为数据域。
·数据的存储方法：
数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储和非顺序存储。对应的两种不同的存储结构分别是顺序存储结构和链式存储结构。
顺序存储是借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系；非顺序存储是借助指针来表示数据元素之间的存储关系；指针是用来指示数据元素的存储地址的。
·数据结构的四种存储方法：
（1）顺序存储方法
该方法是把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。此种结构通常是借助数组类型来描述的。
（2）链式存储方法
该方法结点间的逻辑关系是由附加的指针字段表示的，并不要求逻辑上相邻的结点在物理位置上也相邻。此种结构通常是借助指针类型来描述的。
（3）索引存储方法
该方法在建立结点信息的同时，也建立了附加的索引表，索引表中的每一项称之为索引项，索引项的一般形式是：（关键字，地址）。
关键字标识唯一一个结点，地址作为指向结点的指针。
此种结构可以提高数据查找的速度。
（4）哈希存储方法
即散列存储方法，该方法根据结点的关键字通过哈希函数直接计算出该结点的存储地址。此种结构本质上是顺序存储的扩展。
6.数据的运算与存储结构的关系？
·数据的运算：一个数据结构所包含的数据运算的种类和数目以及每个运算中的参数数目及类型，都应该依据该数据结构的实际用途和需要来量身定做。它们只有在一定的数据结构上具体实现后才具有真实的意义。
因此数据结构运算的实现和执行效率都与存储结构有关。
7.什么是数据类型？
·数据类型：数据类型是一个值的集合以及定义在这个值集上的一组操作的总称。
eg：c语言中，int是一种整型数据类型，其值集为某个区间上的整数（16位机上为-32768～32767），而定义在这个值集上的操作有+、-等运算。
8.什么是抽象数据类型（adt）？
·抽象数据类型（adt）：抽象数据类型是指一个数学模型以及定义在该数据模型上的一组操作。
adt通常由用户自定义，adt由基本数据类型组成，并且包括一组相关的操作。
其特征是使用与实现分离，可以实现封装和信息隐藏，即在adt设计时，可以把类型的声明与实现分离开来。
9.什么是算法？算法有什么特性？
·算法：算法是指对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令都表示一个或多个操作。
·算法的特性：
①有穷性：对于任意一组合法的输入值，在有穷时间内执行有穷步骤后一定可以结束。
②确定性：对于每种情况下所应执行的操作，在算法中都要有明确的规定，使算法的执行者或阅读者能够明确该算法的含义及其是如何执行的，并且在任何条件下，算法都只有一条执行路径。
③可行性：算法中的所有操作都必须在有限次数内完成，并且可以通过已经实现的基本操作进行运算。
④有输入：算法必须有输入量，没有输入的算法是不存在的。
⑤有输出：一个算法对信息加工后必须要产生一个结果。
ps：算法与程序不同，程序可以不满足有穷性，eg：windows操作系统在用户未操作之前将一直处于等待的循环中，直到出现新的用户操作为止。这个等待过程就是无穷的。
由于一般的程序都不会出现这种情况，因此多数情况下对算法和程序并不严格区分。
10.一个好的算法应该满足哪些要求？
①正确性：要求设计的算法能够正确的执行预先规定的功能和性能要求。
②可执行性：要求设计的算法能够方便的使用，此特性也称用户友好性。
③可读性：要求设计的算法应该易于理解，其逻辑必须是简单、清晰、有结构化的。
④健壮性：要求设计的算法有很好的容错性，能提供异常处理，不会因一些异常情况而中断甚至崩溃。
⑤高效率与低存储：要求所设计的算法的执行时间越短越好，而该算法在执行过程中所需要占用的存储空间越小越好。
11.什么是算法的时间复杂度？
·算法的时间复杂度：算法中的基本操作的循环次数是待解决问题规模n的某个函数f（n），算法的时间量度记作：
t（n）=o（f（n））
它表示随着问题规模n的增大，算法执行时间的增长率与f（n）的增长率相同。称之为算法的渐进时间复杂度，简称时间复杂度。
特别的，所说的时间复杂度通常是指最坏情况下的时间复杂度，即分析最坏情况估算算法执行时间的上界。
影响程序运行时间的因素是多方面的，如机器的运行速度，编译程序产生的目标**的质量，程序的输入等。我们把一个程序运行的时间定义为函数t（n）。n是该程序输入数据的规模，而不是某一个具体的输入，t（n）的单位是不确定的，一般将其看做在一台特定计算机上执行的指令条数。
当讨论一个程序的运行时间t（n）时，需要关注的不是t（n）的具体数值，而是它的增长率。我们称函数f（n）为t（n）增长率的上界，是指存在一个常数c和整数n。，当n>=n。
时，t（n）==c*g(n),记为：
t（n）=ωg（n））。
eg：设函数t（n）=3*n^3+2*n^2,证明：t（n）=o（n^3），t（n）=ωn^3）；
证明：采用数学归纳法证明
取n。=0，c=5，则，当n>=0时，有：3*n^3+2*n^2=<5*n^3
另取c=1，则对于n=0,1,2,..有：t（n）>=c*n^3
我们还可以证明函数3^n不是o（2^n）,即3^n≠o（2^n）。用反证法，假设3^n=o（2^n），则存在常数c和n,当n>=n。时，3^n==（3/2）^n可以大雨任意大的正数，因而这样的常数c不存在。
一个程序运行时间的增长率将最终决定该程序在计算机上能解决多大规模的问题。因此我们说一个运行时间为o（n^2）的程序较之运行时间为o（n^3）的程序有更好的时间复杂性。至于常数因子通常忽略不计。
12.如何分析一个程序的时间复杂度？
·首先，针对程度基本成分s的执行时间t（s）引入如下记号：
◇t（~x）为取变量或常量x之值所消耗的时间，相当于汇编语言中取数并送给一个寄存器加载的这段时间。
◇t（.v）为取变量v的地址之值所消耗的时间，凡是地址在编译阶段已经分配完的，其t（.v）=0。
◇t（=）为赋值操作所消耗的时间，相当于保存一个数所消耗的时间。
◇t（θ）执行运算操作θ所消耗的时间。eg:t(+)t(-)及t(*)和t(/)等。
◇t（call/return）执行函数调用与函数返回所消耗的时间。
◇t（par）将参数par传递给函数所消耗的时间。
·其次，计算复合结构的增长率可用加法规则和乘法规则：
◇设t1(n)=o(f(n)),t2(n)=o(g(n)),则
①加法规则
设t1(n)和t2(n)是程序段p1和p2的运行时间，则执行p1之后紧接着执行p2的运行时间t1(n)+t2(n)是o(max)。
即： t1(n)+t2(n)=o(max)
②乘法规则
t1(n)·t2(n)=o(f(n)·g(n))
·再次，一般来说，分析程序的时间复杂性是分块进行的：
①先求出程序中各语句、各模块的运行时间；
②再求整个程序的运行时间；
13.怎样具体分析一个程序中的各种语句及模块的时间复杂度？(part1)
⑴表达式和赋值语句
◇设表达式的语法格式：
exp∷=常数|变量|f-name(e1,…,em)|(exp θ exp)
其中第三项为函数调用，f-name是函数名，e1,…,em是实在参数，用加法规则可计算时间如下：
t(v=exp)=t(.v)+t(=)t(exp)
t(exp θ exp)=t(exp)+t(θ)t(exp)
t(f-name(e1,…,em))=t(call/return)+m*t(par)+t(f-body)
eg:分析表达式c=a+b的执行时间得：
t(c=a+b)=t(.c)+t(=)t(~a)+t(+)t(~b)
对应于c=a+b的汇编程序为：
load a in r1
load b in r2
add r2 to r1
load .c in r2/*取变量c的地址放入r2*/
store r1 in r2 indirect/*间接存数*/
或者是 load a in r1
add b to r2
store r1 in c /*此处可认为t(.c)=t(~b)=0,*/
由此例可见，具体机器细节、寄存器分配策略、编译与优化等，都给计算准确的执行时间带来极大困难，因此通常是对高级语言程序直接分析，不得已时才分析其对应的汇编程序。
对高级语言的分析不必如汇编般细致，往往忽略许多复杂、次要的因素而注重分析时间的增长率。根据这种想法，每个赋值语句或读/写语句的运行时间通常取o(1)(表示增长率是常数)，但如果赋值语句右部表达式exp中含有函数调用，那么则要考虑计算函数值所消耗的时间。
⑵语句序列
◇一个语句序列s1.…,sk的运行时间由加法规则确定，为序列中消耗最多的语句的运行时间：
t(s1.…,sk)=max
⑶条件语句
◇t(if(b)s1 else s2)=t(b)+t(else)+max
其中t(b)是条件b的测试时间；t(else)是条件语句内部的控制流动时间，通常取：t(b)+t(else)=o(1)。
根据上式显然有：
◇t(if(b)s)=o(1)+t(s)
⑷switch语句
◇设s是如下语句
switch(e)
case e1:s1;
case ek:sk;
default :sm
k 则t(s)=t(e) +t(ei) +max
i=1 通常取：
k t(e) +t(ei)=o(1)i=1
数据结构基础
内容简介。本书是最经典数据结构教材的最新版本，国内外大多数的同类教材都是以本书为蓝本编写而来的。本书用c作为描述语言，全面而生动地介绍了数据结构的有关知识，如数组 栈 队列 链表 树和图，以及构成所有软件基础的排序散列技术。此外，本书还介绍了各种高级或特殊数据结构，如优先级队列 高效二叉查找树 多路...
数据结构基础
文件输入输出。include include using namespace std int main file fin,fout fin fopen rscanf d x fscanf stdin,d x fout fopen w fprintf d x frpintf stdout,d x in...
数据结构基础
读万卷书，行万里路 刘彝 所属课程名称 数据结构基础。英文名称 fundamentals of data structure 所属课程编号 0901202 面向专业 计算机及电类专业。课程总学时 64 实验学时 32 课程学分 4.5 一。实验目的。通过上机实验，使学生深刻理解基础数据结构和算法的概...