北京工业大学-数据结构-期末复习

考试题型单选：5题，共10分填空：5题，共10分简答题：5题，共45分算法阅读：15分算法设计：20分考试要求：闭卷第1章概论DS描述“按一定逻辑关系组织的数据元素的表示及相关操作数据逻辑结构：线性结构、树形结构和图形结构数据存储结构：顺序方法、链接方法、索引方法、散列方法抽象数据类型ADT算法4个特性：通用性、有效性、确定性、有穷性算法分析：T(n)、S(n)算法分析的相关概念；最差、最佳与平均情况的意义ADT的定义三元组表示ADT=(D,R,P)ADT抽象数据类型名{数据对象D:数据对象的定义数据关系R:数据关系的定义基本操作P:基本操作的定义}ADT抽象数据类型名用C++类模板的声明表示ADT数据的抽象算法的抽象ADT定义类模板类模板代表一类类，不代表具体的类类模板的定义格式:templateclassType//类型参数Type,使用时用具体数据类型代替classclassName{private:TypedataList;…public:methodName();…};C++引入模板概念，是想突出数据的逻辑结构而忽略其具体的数据类型声明、定义和使用C++类模板(2)类模板：描述了一组相关的类，它们只能通过类型来区分1、类模板声明：仅提供了类的名称和类的模板参数templateclassElem//类模板Array可接受任何类型作为参数classArray{Elem*data;intsize;//声明类模板Array的类数据public:Array(intsz);//函数成员intGetSize();};2、函数成员定义templateclassElemArrayElem::Array(intsz){size=sz;data=newElem[size];}templateclassElemintArrayElem::GetSize(){returnsize;}3、类模板的用法Arrayintint_array(100);//Array接收int作参数,//int_array为长100的int型数组对象常见上限g(n)的种类(用于比较各算法优劣)O(1)O(logn)O(n)O(nlogn)O(n2)常数阶对数线性对数乘积平方O(n3)….O(2n)O(n!)立方指数阶乘常数：g(n)=1对数：g(n)=logn线性增长：g(n)=n二阶增长：g(n)=n2g(n)=nlog(n),n=nlog(n)增长率=n2指数增长：g(n)=anTn2nnlogn2题型举例算法指的是（）。A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。A.O(n)B.O(1)C.O(m)D.O(m+n)第2章线性表清楚线性表定义、理解类定义及抽象数据类型中定义的各个基本操作含义存储形式：顺序存储结构、链式存储结构顺序存储结构的特点：1.逻辑结构与物理结构一致；2.属于随机存取方式缺点：插入\删除元素需要移动，平均约一半的元素，限制了长度变化链式存储结构的特点：1.逻辑结构与物理结构不一致；2.属于顺序存取方式2.1.2线性表的存储结构逻辑结构存储空间的映射数据存储单元建立映射关系存储单元之间关系建立映射线性表2类存储结构1.顺序存储（定长的一维数组结构、向量型顺序存储结构）为整个元素动态分配连续空间特点：逻辑相邻物理也相邻2.链式存储（变长的线性表存储结构）按需分配(插入:分配一个结点/删除:回收一结点)特点：逻辑相邻物理不一定相邻链表—单向、循环、双向不特殊说明，均带头结点(避免对空表的特殊处理)算法：（时间复杂性）在有序表中插入/删除结点给定元素位置，插入/删除相应结点注意：对循环链表操作时，尾部的判断双向链表的插入/删除结点删除结点一定要释放空间2.4线性表实现方法的比较顺序表优点存储紧凑（逻辑结构由存储相对位置体现，没使用指针，不用花费附加开销）随机访问（给定下标,常量时间可定位）链表优点不限定长度（无需事先了解线性表的长度，允许线性表的长度有很大变化）不必移动，仅需改指针即可插删（能够适应经常插入删除内部元素的情况）适用不能确定长度上限、频繁插删：用链式存储结构按位置频繁进行读取、数据域占用空间小于指针域：用顺序存储结构有序的顺序表与无序的顺序表相比，其操作优势是（）。A.删除快B.插入快C.生成快D.查找快。若对线性表进行的主要操作是按下标存取，且很少插入和删除，则应该采用的存储结构是_____；若需要频繁地对线性表进行插入和删除时，则应该采用的存储结构是。题型举例第3章栈与队列栈与队列的定义、ADT定义及基本操作。栈的应用：会跟踪递归函数执行过程深度（纵向）周游表达式求值(中缀后缀求值)队列的应用：按层周游注意：熟悉ADT的操作形式，会直接调用抽象数据类型中定义的操作算符优先关系表+-*/()#+-*/(=错)错#=左右a/(b-c)+d*e#abc-/de*+输入动作栈内容后缀表达式对应算法步骤a输出a#a1//#，入栈#/4.2(入栈#/（2b输出bab1--(，入栈#/（-4.2c输出cabc1)-出栈输出,直至(#/（abc-3.2)==(,出栈不输出#/3.2++/,/出栈输出#abc-/4.1+#，入栈#+4.2d输出dabc-/d1**+，入栈#+*4.2e输出eabc-/de1#连续出栈输出abc-/de*+5后缀表达式求值循环：依次分析输入序列：1.输入是操作数：则入栈；2.输入是运算符：则两次出栈，取操作数2和操作数1，按照运算符进行计算。将结果入栈。重复，直至遇到结束符“=”此时栈顶值就是输入表达式的值。第4章字符串(了解）基本概念存储结构（顺序、标准类）基本操作的含义第5章二叉树定义、性质、存储结构（相应的类定义）满二叉树、完全二叉树及扩充二叉树抽象数据类型定义中的基本操作含义深度周游（递归与非递归），广度周游二叉搜索树插入、删除（改进）与检索算法；必须能够跟踪执行过程；求ASL。堆概念、建堆、筛选、插、删的相关算法(过程)Huffman树构造及Huffman编码深度优先周游二叉树（递归实现）1.templateclassT2.voidBinaryTreeT::PreOrder(BinaryTreeNodeT*root)｛3.if(root!=NULL){4.Visit(root-value());//前序5.DepthOrder(root-leftchild());//访问左子树6.7.DepthOrder(root-rightchild());//访问右子树8.9.}10.｝Visit(root)//中序Visit(root)//后序451253324100906137生成二叉搜索树45,53,12,37,3,100,61,24,90,7878二叉搜索树的删除在二叉搜索树里删除结点时，不是把以这个结点为根的子树都删除掉，只是删除一个结点，并且还要保持二叉搜索树的性质。删除过程分为两种情况：没有左子树有左子树没有左子树若结点p没有左子树，则用右子树的根代替被删除的结点p。50308020908540358832503020908540358832有左子树（改进）若p(50)有左子树，则在左子树里找中序周游的最后一个结点s(40)，删除s，用s的左子树代替s，用s代替被删p这种方法可以降低二叉树的高度。50308020908540358832403080209085353288已知序列72,73,71,23,94,16,05,68建堆72最小堆的插入插入过程：插入点追加到最后，自下而上依次比较父与子，直到满足堆的定义121419241813221517262012141924182022151726131213192418202215172614插入1320131413最小堆的删除用最后结点替换被删结点，自上至下调整成堆(最后结点被删结点,只影响其子树的最小堆性质)12141924182215172620删除14142626192622261219262418221517201219222418261517205.6Huffman树及其应用外部路径长度li扩充二叉树从根到每个外部结点的路径长度之和外部路径长度最小的二叉树：是完全二叉树带权外部路径长度(weightedexternalpath)最小的二叉树：Huffman树要求给出一个具有n个外部结点的扩充二叉树每个外部结点Ki有一个wi与之对应，作为该外部结点的权此扩充二叉树的叶结点带权外部路径长度总和最小注意:不管内部结点，也不用有序特点：权越大的叶结点离根越近10niiilw35291478c3d4e523f611h8b281519294258100建树g7a下标：1101011000a:0001b:10c:1110d:1111f:01g:0000h:001与算法有关的典型例题已知一棵二叉树的前序和中序（后序和中序）遍历序列，构造对应的二叉树通过二叉树，获得对应的树与森林的相关信息深度周游与广度周游二叉树31具有n个结点的满二叉树，其叶子结点的个数为____________。(如果一棵二叉树的任何结点，或者是树叶，或者恰有两棵非空子树，则此二叉树称作满二叉树,性质3.任何一棵二叉树，n0=n2+1)某棵二叉树的前序序列为ABDEFC，中序序列为DBFEAC，则该二叉树对应的后序序列的结果为___________。五个分别带权值为9，2，5，7，12的叶子结点构造Huffman树，进行编码，并写出该树的带权外部路径长度WPL。给定关键码序列，创建二叉搜索树，并删除某个结点（按照教材中的改进算法），求ASL堆排序：给定关键码序列，建初堆。插入、删除结点后，调整为堆第6章树树与森林定义、ADT定义、基本操作树（森林）周游(深度优先、广度优先)先根次序周游森林=前序周游二叉树后根次序周游森林=中序周游二叉树树（森林）与二叉树的等价转换树与森林的链式存储结构动态“左子/右兄”二叉链表表示法森林与二叉树的等价转换森林由３部分组成：森林中第一棵树的根结点森林中第一棵树的子树森林森林中其它树构成的森林动态“左子/右兄”二叉链表表示法35DABCEFG^|B|^|C|^|D|^|E|^^|F|^|G|^^|A|^6.1.4树的周游1、深度优先周游树一.先根次序周游森林≡前序周游二叉树首棵树根；首棵树各子树；余下各树根；左子树；右子树依次从左至右对森林每棵树进行先序周游二.后根次序周游森林≡中序周游二叉树首棵树各子树；首棵树根；余下各树左子树；根；右子树依次从左至右对森林每棵树进行后序周游先序：ABCEFDGHJI后序：BEFCDAJHIGABCFEDGHJIABGHCEFIDJ带右链的先根次序表示法这种表示法与llink—rlink表示法相比，用ltag代替了llink，占用的存储单元要少些，但并不丢失信息可以从结点的次序和ltag的值完全可以推知llinkltag==0:有左子，它的llink指向该结点数组右邻ltag==1:没有左子，它的llink为空第7章图有向图/网：弧、入/出度、有向完全图无向图/网：边、度、无向完全图图的ADT定义存储结构（相邻矩阵、邻接表）及类定义图周游算法（深度、广度）最小生成树（prim)、拓扑排序、单源最短路径（必须会严格按照算法手工走给定实例）典型题目1.能够完成拓扑排序的图一定是一个_________。2.n个顶点的无向连通图至少有的边的条数是___。3.已知一个