1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。
◆ 数据：指能够被计算机识别、存储和加工处理的信息载体。
◆ 数据元素：就是数据的基本单位，在某些情况下数据项组成。◆ 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。
◆ 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。
◆ 逻辑结构：指各数据元素之间的逻辑关系。
◆ 存储结构：就是数据的逻辑结构用计算机语言的实现。
◆ 线性结构：数据逻辑结构中的一类，它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。
◆ 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。
1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。
◆
例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录(有姓名，学号，成绩等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构。
那么我们怎样把这个表中的数据存储到计算机里呢? 用高级语言如何表示各结点之间的关系呢?
是用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢?
这就是存储结构的问题，我们都是从高级语言的层次来讨论这个问题的。(所以各位赶快学C语言吧)。
最后，我们有了这个表(数据结构)，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。
1.3 常用的存储表示方法有哪几种?
常用的存储表示方法有四种:
◆ 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构。
◆ 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。由此得到的存储表示称为链式存储结构。
◆ 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
◆ 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。
1.4 设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 ,
g(n)=25n^3+5000n^2 ,
h(n)=n^1.5+5000nlgn 请判断下列关系是否成立：
(1) f(n)=O(g(n))
(2) g(n)=O(f(n))
(3) h(n)=O(n^1.5)
(4) h(n)=O(nlgn)
◆ (1)成立。
◇ 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的"O"是数学符号，它的严格定义是"若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。"用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。第(1)题中两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
◆ （2）成立。
◆ （3）成立。
◆ （4）不成立。
1.5 设有两个算法在同一机器上运行，其执行时间分别为100n^2和2^n,要使前者快于后者，n至少要多大?
◆ 15
◇
最简单最笨的办法就是拿自然数去代呗。假定n取为10，则前者的值是10000，后者的值是1024,小于前者，那我们就加个5，用15代入得前者为22500，后者为32768，已经比前者大但相差不多，那我们再减个1，用14代入得，前者为19600,后者为16384，又比前者小了，所以结果得出来就是n至少要是15.
1.6 设n为正整数，利用大"O"记号，将下列程序段的执行时间表示为n的函数。
(1) i=1; k=0 while(i { k=k+10*i;i++; } ◆ T(n)=n-1 ∴ T(n)=O(n) ◇ 这个函数是按线性阶递增的 (2) i=0; k=0; do{ k=k+10*i; i++; } while(i ∴ T(n)=O(n) ◇ 这也是线性阶递增的 (3) i=1; j=0; while(i+j<=n) { if (i } ◆ T(n)=n/2 ∴ T(n)=O(n) ◇ 虽然时间函数是n/2,但其数量级仍是按线性阶递增的。 (4)x=n; // n>1 while (x>=(y+1)*(y+1)) y++; ◆ T(n)=n1/2 ∴ T(n)=O(n1/2) ◇ 最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。 (5) x=91; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; ◆ T(n)=O(1) ◇ 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有? 没。这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。 1.7 算法的时间复杂度仅与问题的规模相关吗? ◆ No,事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。 1.8 按增长率由小至大的顺序排列下列各函数： 2^100, (2/3)^n，(3/2)^n， n^n , , n! ，2^n ，lgn ,n^lgn, n^(3/2) ◇ 分析如下：2^100 是常数阶； (2/3)^n和 (3/2)^n是指数阶,其中前者是随n的增大而减小的； n^n是指数方阶；√n 是方根阶, n! 就是n(n-1)(n-2)... 就相当于n次方阶；2^n 是指数阶，lgn是对数阶 ,n^lgn是对数方阶, n^(3/2)是3/2次方阶。根据以上分析按增长率由小至大的顺序可排列如下： ◆ (2/3)^n < 2^100 < lgn < √n < n^(3/2) < n^lgn < (3/2)^n < 2^n < n! < n^n 1.9 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大"O"记号表示。例如，设 T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时， 上机题 1.随机产生n个整数，然后用一种排序算法将它们从小到大排序。基本要求：试根据对问题的分析，选择一种简单的算法和数据结构，经过逐步细化，最后用C语言编程，调试通过。至少3组不同大小的数据。 选做部分：考虑两种不同的数据结构，对每种结构选择两种不同的算法，分别完成程序的设计与实现；并对这四个程序的代价进行初步的分析比较。 2.试编一程序，用贪心法求解一般的着色问题。 判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点 .. ;.. 第一章 概论 1.数据结构描述的是按照一定逻辑关系组织起来的待处理数据元素的表示及相关操作，涉及数据的逻辑结构、存储结构和运算 2.数据的逻辑结构是从具体问题抽象出来的数学模型，反映了事物的组成结构及事物之间的逻辑关系 可以用一组数据（结点集合K ）以及这些数据之间的 一组二元关系（关系集合R ）来表示：(K, R) 结点集K 是由有限个结点组成的集合，每一个结点代表一个数据或一组有明确结构的数据 关系集R 是定义在集合K 上的一组关系，其中每个关系r （r ∈R ）都是K ×K 上的二元关系 3.数据类型 a.基本数据类型 整数类型(integer)、实数类型(real)、布尔类型(boolean)、字符类型（char ）、指针类型（pointer ） b.复合数据类型 复合类型是由基本数据类型组合而成的数据类型；复合数据类型本身，又可参与定义结构更为复杂的结点类型 4.数据结构的分类：线性结构（一对一）、树型结构（一对多）、图结构（多对多） 5.四种基本存储映射方法：顺序、链接、索引、散列 6.算法的特性：通用性、有效性、确定性、有穷性 7.算法分析：目的是从解决同一个问题的不同算法中选择比较适合的一种，或者对原始算法进行改造、加工、使其优化 8.渐进算法分析 a ．大Ο分析法：上限，表明最坏情况 b ．Ω分析法：下限，表明最好情况 c ．Θ分析法：当上限和下限相同时，表明平均情况 第二章 线性表 1.线性结构的基本特征 a.集合中必存在唯一的一个“第一元素” b.集合中必存在唯一的一个“最后元素” c.除最后元素之外，均有唯一的后继 d.除第一元素之外，均有唯一的前驱 2.线性结构的基本特点:均匀性、有序性 3.顺序表 a.主要特性：元素的类型相同；元素顺序地存储在连续存储空间中，每一个元素唯一的索引值；使用常数作为向量长度 b. 线性表中任意元素的存储位置：Loc(ki) = Loc(k0) + i * L （设每个元素需占用L 个存储单元） c. 线性表的优缺点： 优点：逻辑结构与存储结构一致；属于随机存取方式，即查找每个元素所花时间基本一样 缺点：空间难以扩充 d.检索：ASL=【Ο（1）】 e .插入：插入前检查是否满了，插入时插入处后的表需要复制【Ο（n ）】 f.删除：删除前检查是否是空的，删除时直接覆盖就行了【Ο（n ）】 4.链表 4.1单链表 a.特点：逻辑顺序与物理顺序有可能不一致；属于顺序存取的存储结构，即存取每个数据元素所花费的时间不相等 b.带头结点的怎么判定空表：head 和tail 指向单链表的头结点 c.链表的插入（q->next=p->next; p->next=q;）【Ο（n ）】 d.链表的删除（q=p->next; p->next = q->next; delete q;）【Ο（n ）】 e.不足：next 仅指向后继，不能有效找到前驱 4.2双链表 a.增加前驱指针，弥补单链表的不足 b.带头结点的怎么判定空表:head 和tail 指向单链表的头结点 c.插入：（q->next = p->next; q->prev = p; p->next = q; q->next->prev = q;） d.删除：（p->prev->next = p->next; p->next->prev = p->prev; p->prev = p->next = NULL; delete p;） 4.3顺序表和链表的比较 4.3.1主要优点 a.顺序表的主要优点 没用使用指针，不用花费附加开销；线性表元素的读访问非常简洁便利 b.链表的主要优点 无需事先了解线性表的长度；允许线性表的长度有很大变化；能够适应经常插入删除内部元素的情况 4.3.2应用场合的选择 a.不宜使用顺序表的场合 经常插入删除时，不宜使用顺序表；线性表的最大长度也是一个重要因素 b.不宜使用链表的场合 当不经常插入删除时，不应选择链表；当指针的存储开销与整个结点内容所占空间相 比其比例较大时，应该慎重选择 第三章 栈与队列 1.栈 a.栈是一种限定仅在一端进行插入和删除操作的线性表；其特点后进先出；插入：入栈（压栈）；删除：出栈（退栈）；插入、删除一端被称为栈顶（浮动），另一端称为栈底（固定）；实现分为顺序栈和链式栈两种 b.应用： 1）数制转换 while (N) { N%8入栈； N=N/8;} while (栈非空){ 出栈； 输出；} 2）括号匹配检验 不匹配情况：各类括号数量不同；嵌套关系不正确 算法： 逐一处理表达式中的每个字符ch ： ch=非括号：不做任何处理 ch=左括号：入栈 ch=右括号：if (栈空) return false else { 出栈，检查匹配情况， if (不匹配) return false } 如果结束后，栈非空，返回false 3）表达式求值 3.1中缀表达式： 计算规则：先括号内，再括号外；同层按照优先级，即先乘*、除/,后加+、减-；相同优先级依据结合律，左结合律即为先左后右 3.2后缀表达式： <表达式> ::= <项><项> + | <项> <项>－|<项> <项> ::= <因子><因子> * |<因子><因子>/|<因子> <因子> ::= <常数> ? <常数> ::= <数字>|<数字><常数> <数字> ∷= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 3.3中缀表达式转换为后缀表达式 InfixExp 为中缀表达式，PostfixExp 为后缀表达式 初始化操作数栈OP ，运算符栈OPND ；OPND.push('#'); 读取InfixExp 表达式的一项 操作数：直接输出到PostfixExp 中； 操作符： 当‘（’：入OPND; 当‘）’：OPND 此时若空，则出错；OPND 若非空，栈中元 素依次弹出，输入PostfixExpz 中，直到遇到‘（’为止；若 为‘（’，弹出即可 当‘四则运算符’：循环（当栈非空且栈顶不是‘（’&& 当前运算符优先级>栈顶运算符优先级），反复弹出栈顶运 算符并输入到PostfixExp 中，再将当前运算符压入栈 3.4后缀表达式求值 初始化操作数栈OP ； while （表达式没有处理完) { item = 读取表达式一项; 操作数：入栈OP ； 运算符：退出两个操作数， 计算，并将结果入栈} c.递归使用的场合：定义是递归的；数据结构是递归的；解决问题的方法是递归的 2.队列 a.若线性表的插入操作在一端进行，删除操作在另一端进行，则称此线性表为队列 b.循环队列判断队满对空： 队空：front==rear ；队满：(rear+1)%n==front 第五章 二叉树 1.概念 a. 一个结点的子树的个数称为度数 b.二叉树的高度定义为二叉树中层数最大的叶结点的层数加1 c.二叉树的深度定义为二叉树中层数最大的叶结点的层数 d.如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树 e.如果一颗二叉树最多只有最下面的两层结点度数可以小于2；最下面一层的结点都集中在该层最左边的位置上，则称此二叉树为完全二叉树 f.当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶组成扩充二叉树，扩充二叉树是满二叉树 外部路径长度E ：从扩充的二叉树的根到每个外部结点（新增的空树叶）的路径长度之和 内部路径长度I ：扩充的二叉树中从根到每个内部结点（原来二叉树结点）的路径长度之和 2.性质 a. 二叉树的第i 层（根为第0层，i ≥0）最多有2^i 个结点 b. 深度为k 的二叉树至多有2k+1-1个结点 c. 任何一颗二叉树，度为0的结点比度为2的结点多一个。n0 = n2 + 1 d. 满二叉树定理：非空满二叉树树叶数等于其分支结点数加1 e. 满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1 f. 有n 个结点（n>0）的完全二叉树的高度为?log2(n+1)?，深度为?log2(n+1)?? g. 对于具有n 个结点的完全二叉树，结点按层次由左到右编号，则有： 1) 如果i = 0为根结点；如果i>0，其父结点编号是 (i-1)/2 2) 当2i+1 第 1 页，共 11 页 任课教师签名： 命题教师签名： 系主任签名： 主管院长签名： 湛江师范学院2007年－2008学年度第1学期 期末考试试题A 卷 (考试时间:120分钟) 考试科目： 数据结构 请将所有答案填写在答题卡上，交卷时请将所有试卷上交 一、单选题(每小题2分，共40分) 1．下列算法的时间复杂度是（ B ）。 for ( i=0; i 6．栈的特点是（B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4，则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的 最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i 一、选择(2’×15=30’) 1.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时 间复杂度为( ) A.O(0) B.O(1) C.O(n) D.O(n2) 2.用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾 结点，则在进行删除操作时( ) A.仅修改队头指针 B.仅修改队尾指针 C.队头、队尾指针都不修改 D.队头、队尾指针都可能要修改 3.设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S，若每个元素出栈 后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是( ) A.1 B.2 C.3 D.4 4.对n(n≥2)个权值均不相同的字符构成哈夫曼树，关于该树的叙述中，错误的是( ) A.该树一定是一棵完全二叉树 B.树中一定没有度为1的结点 C.树中两个权值最小的结点一定是兄弟结点 D.树中任一非叶结点的权值一定不小于下一层任一结点的权值 5.一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是( ) A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCFEG 6.下列线索二叉树中（用虚线表示线索），符合后序线索二叉树定义的是( D) 7.下面关于二分查找的叙述正确的是( ) A.表必须有序，表可以顺序方式存储，也可以链表方式存储 B.表必须有序，且表中数据必须是整型，实型或字符型 C.表必须有序，而且只能从小到大排列 D.表必须有序，且表只能以顺序方式存储 8.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受 数据初始特性影响的是( ) A.直接插入排序 B.快速排序 C.直接选择排序 D.堆排序 9.下列关于无向连通图特性的叙述中，正确的是( ) I.所有顶点的度之和为偶数 II.边数大于顶点个数减1 一、是非题 1.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运 算三个方面。.......................( T ) 2.线性表的逻辑顺序与物理顺序总是一致的........( F ) 3.线性表中的每个结点最多只有一个前驱和一个后继。......( T ) 4.线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存 储。.......................( F ) 5.栈和队列逻辑上都是线性表。..........................( T ) 6.单链表从任何一个结点出发，都能访问到所有结点........( F ) 7.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后 一个结点。.................................................( T ) 8.在用单链表表示的链式队列中，队头在链表的链尾位置。....( F ) 9.多维数组是向量的推广。..............................( T ) 10.栈是一种先进先出的线性表。....( F ) 11.凡是递归定义的数据结构都可以用递归算法来实现它的操作。......( T ) 12.设串S的长度为n,则S的子串个数为n(n+1)/2。...........( F ) 13.一般树和二叉树的结点数目都可以为0。................( F ) 14.按中序遍历二叉树时，某结点的直接后继是它的右子树中第1个被访问的结 点。....( T ) 15.后序序列和中序序列能唯一确定一棵二叉树。....( T ) 16.对于一棵具有n个结点，其高度为h的二叉树，进行任—种次序遍历的时间复杂 度为O(n) .............( T ) 17.网络的最小代价生成树是唯一的。...( T ) 18.图的拓扑有序序列不是唯一的。...( T ) 19.进行折半搜索的表必须是顺序存储的有序表。...( T ) 二、单选题 1.算法指的是（ D ） A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列 2.线性表采用链式存储时，结点的存储地址（B ） A．必须是不连续的 B．连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 3.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（C ） A．O（1） B．O（n） C．O（m） D．O（m+n） 4.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为( B )。 A．O(n) B．O(1) C．O(n2) D．O(log2n)T 5.线性表L在( B )情况下适用于使用链式结构实现。 A.需经常修改Ｌ中的结点值 B.需不断对Ｌ进行删除插入 C.L中含有大量的结点 D.L中结点结构复杂 6.设单链表中结点的结构为(data，1ink)。已知指针q所指结点是指针p所指结点 的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作?( B ) A．s一>1ink=p一>1ink；p一>1ink＝s B．q一>1ink＝s；s一>link=p C．p一>link＝s一>1ink；s一>1ink＝p 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时， for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S； (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树，其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树，其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个，则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中，元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■ 数据结构复习重点归纳 （适于清华严版教材） 一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为：概论，线性表，栈和队列，串，多维数组和广义表，树和二叉树，图，查找，内排，外排，文件，动态存储分配。 对于绝大多数的学校而言，“外排，文件，动态存储分配”三章基本上是不考的，在大多数高校的计算机本科教学过程中，这三章也是基本上不作讲授的。所以，大家在这三章上可以不必花费过多的精力，只要知道基本的概念即可。但是，对于报考名校特别是该校又有在试卷中对这三章进行过考核的历史，那么这部分朋友就要留意这三章了。 按照以上我们给出的章节以及对后三章的介绍，数据结构的章节比重大致为：概论：内容很少，概念简单，分数大多只有几分，有的学校甚至不考。 线性表：基础章节，必考内容之一。考题多数为基本概念题，名校考题中，鲜有大型算法设计题。如果有，也是与其它章节内容相结合。 栈和队列：基础章节，容易出基本概念题，必考内容之一。而栈常与其它章节配合考查，也常与递归等概念相联系进行考查。 串：基础章节，概念较为简单。专门针对于此章的大型算法设计题很少，较常见的是根据KMP进行算法分析。 多维数组及广义表：基础章节，基于数组的算法题也是常见的，分数比例波动较大，是出题的“可选单元”或“侯补单元”。一般如果要出题，多数不会作为大题出。数组常与“查找，排序”等章节结合来作为大题考查。 树和二叉树：重点难点章节，各校必考章节。各校在此章出题的不同之处在于，是否在本章中出一到两道大的算法设计题。通过对多所学校的试卷分析，绝大多数学校在本章都曾有过出大型算法设计题的历史。 图：重点难点章节，名校尤爱考。如果作为重点来考，则多出现于分析与设计题型当中，可与树一章共同构成算法设计大题的题型设计。 查找：重点难点章节，概念较多，联系较为紧密，容易混淆。出题时可以作为分析型题目给出，在基本概念型题目中也较为常见。算法设计型题中可以数组结合来考查，也可以与树一章结合来考查。 排序：与查找一章类似，本章同属于重点难点章节，且概念更多，联系更为紧密，概念之间更容易混淆。在基本概念的考查中，尤爱考各种排序算法的优劣比较此类的题。算法设计大题中，如果作为出题，那么常与数组结合来考查。 二、数据结构各章节重点勾划： 第0章概述本章主要起到总领作用，为读者进行数据结构的学习进行了一些先期铺垫。大家主要注意以下几点：数据结构的基本概念，时间和空间复杂度的概念及度量方法，算法设计时的注意事项。本章考点不多，只要稍加注意理解即可。 第一章线性表作为线性结构的开篇章节，线性表一章在线性结构的学习乃至整个数据结构学科的学习中，其作用都是不可低估的。在这一章，第一次系统性地引入链式存储的概念，链式存储概念将是整个数据结构学科的重中之重，无论哪一章都涉及到了这个概念。 总体来说，线性表一章可供考查的重要考点有以下几个方面： 1.线性表的相关基本概念，如：前驱、后继、表长、空表、首元结点，头结点，头指针等概念。 2.线性表的结构特点，主要是指：除第一及最后一个元素外，每个结点都只有一个前趋和只有一个后继。 3.线性表的顺序存储方式及其在具体语言环境下的两种不同实现：表空间的静态分配和动态分配。静态链表与顺序表的相似及不同之处。 4.线性表的链式存储方式及以下几种常用链表的特点和运算：单链表、循环链表，双向链表，双向循环链表。其中，单链表的归并算法、循环链表的归并算法、双 向链表及双向循环链表的插入和删除算法等都是较为常见的考查方式。此外，近年来在不少学校中还多次出现要求用递归算法实现单链表输出（可能是顺序也可能是倒序）的问题。 在链表的小题型中，经常考到一些诸如：判表空的题。在不同的链表中，其判表空的方式是不一样的，请大家注意。 5.线性表的顺序存储及链式存储情况下，其不同的优缺点比较，即其各自适用的场合。单链表中设置头指针、循环链表中设置尾指针而不设置头指针以及索引存储 结构的各自好处。 第二章栈与队列栈与队列，是很多学习DS的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向DS高手的一条必由之路，。 学习此章前，你可以问一下自己是不是已经知道了以下几点： 1.栈、队列的定义及其相关数据结构的概念，包括：顺序栈，链栈，共享栈，循环队列，链队等。栈与队列存取数据（请注意包括：存和取两部分）的特点。 2.递归算法。栈与递归的关系，以及借助栈将递归转向于非递归的经典算法：n!阶乘问题，fib数列问题，hanoi问题，背包问题，二叉树的递归和非递归遍历问 题，图的深度遍历与栈的关系等。其中，涉及到树与图的问题，多半会在树与图的相关章节中进行考查。 3.栈的应用：数值表达式的求解，括号的配对等的原理，只作原理性了解，具体要求考查此为题目的算法设计题不多。 4.循环队列中判队空、队满条件，循环队列中入队与出队算法。 如果你已经对上面的几点了如指掌，栈与队列一章可以不看书了。注意，我说的是可以不看书，并不是可以不作题哦。 第三章串经历了栈一章的痛苦煎熬后，终于迎来了串一章的柳暗花明。 数据结构复习要点带答案 算法的五大特性：（有零个或多个输入）、（有一个或多个输出）、（有穷性）、（确定性）、（可行性）。 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列；算法分析的目的是（分析算法的效率以求改 进），算法分析的两个主要方面是（空间性能和时间性能）。 1.算法质量的标准：时间复杂度是测量一个算法优劣的重要标准。 时间复杂度的计算：设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（Ο(1)），若为n*log25n，则表示成数量级的形式为（Ο(nlog2n)）。 【分析】：用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2.数据、数据元素、数据项的关系：（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体 进行考虑和处理；（数据项）是数据的最小单位，（数据元素）是讨论数据结构时涉及的最小数据单位。 【分析】数据结构指的是数据元素以及数据元素之间的关系。 3.设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。 试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 4.栈的特性：栈是限定仅在表尾进行插入和删除操作的线性表，允许插入和删除的一段叫做栈顶，另一 端叫做栈底，不含任何数据元素的栈叫做空栈。（栈）可作为实现递归函数调用的一种数据结构。 【分析】递归函数的调用和返回正好符合后进先出性。 栈的特点是先进后出，即：进去的早，出来的晚！ 54321进栈，5在栈底，1在栈顶！ 出一次栈，则栈顶的1先出来，2成为新的栈顶。 ABCD入栈，D成为新的栈顶。 全部出栈：D C B A 2 3 4 5 综上，所有元素退栈顺序为：1 D C B A 2 3 4 5 5.入栈：template数据结构期末考试复习笔记
大学数据结构期末知识点重点总结(考试专用)
数据结构期末考试试题A卷(完成,不知对不对)
大连理工大学软件学院2014数据结构期末考试)
2010级数据结构期末复习题(E)
数据结构复习资料,java数据结构期末考试
数据结构期末考试试题及答案
数据结构复习重点归纳
数据结构期末复习总结超详细1
相关主题
文本预览