数据结构复习知识点

第一章：概论知识点：数据结构的基本概念：数据、数据元素、数据项等之间的区和联系。数据的逻辑结构，数据的存储结构、数据的逻辑结构和存储结构各有哪些基本类型、数据的基本逻辑结构有什么特点。我们所学的几种常见的数据结构中（顺序表、链表、队列、栈、串、树、图等），哪些是线性数据结构，哪些是非线性数据结构？算法复杂性的概念、内容和算法复杂性的计算。简单算法复杂性的判断：(1)sum=0;for(i=1;i<=n;i++)sum=sum+i;其中i=1,2,3,…,k,需频度k<=n，所以复杂性为O(n)(2)i=1;while(i<=n)i=i+2;其中i=1,3,5,…,(2k-1),需2k-1<=n，则频度k<=(n+1)/2，复杂性为O(n)(3)i=1;while(i<=n)i=i*3;其中i=1,3,32,…,3k,需3k<=n，则频度k<=log3n，复杂性为O(log3n)(4)i=1;while(i*i<=n)i++;其中i=1,2,3,…,k，需k2<=n，则频度k<=n1/2，复杂性为O(n1/2)习题：1、填空题（1）数据的逻辑结构包括：、、、；（2）存储结构包括：、、、。（3）数据结构中评价算法的两个重要指标是（4）下面程序段中带下划线的语句的执行次数的数量级是：i=1；while(i<n)i=i*2;（5）计算机执行下面的语句时，语句s的执行次数为_______。for(i=l；i<n-l；i++)for(j=n;j>=i;j--)s;（6）下面程序段的时间复杂度为________。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;2、选择题（1）算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度（2）算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B（3）计算机算法指的是（），它必须具备（）这三个特性。(1)A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A．可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性D.易读性、稳定性、安全性（4）从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构（5）以下数据结构中，哪一个是线性结构（）？A．广义表B.二叉树C.稀疏矩阵D.串（6）在下面的程序段中，对x的赋值语句的频度为（）for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1A．O(2n)B．O(n)C．O(n2)D．O(log2n)（7）程序段for(i=n;i>=1;i--)for(j=1;j<=n;j++)IFA[j]>A[j+1]THENA[j]与A[j+1]对换；其中n为正整数，则最后一行的语句频度在最坏情况下是（）A.O（n）B.O(nlogn)C.O(n3)D.O(n2)（8）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈（9）连续存储设计时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续3、问答题（1）数据元素之间的关系在计算机中有几种表示方法？各有什么特点？（2）数据的逻辑结构有哪些基本类型？（3）数据的存储结构由哪四种基本的存储方法实现？第二章：线性表知识点：线性表的基本概念和两种存储方式：顺序存储、链式存储顺序表的概念、数据结构、存储，插入、删除运算及其时间复杂度；顺序表的特点：随机存储单链表的存储、插入、删除运算特点？是否可以随机存取？访问、增加或者删除结点时的时间复杂度？单链表中插入结点和删除结点的基本步骤？头指针与头结点之间的根本区别，头结点与首元结点的关系？在链表里面，引入头结点有什么作用？有头结点、无头结点的单链表为空的条件分别是什么？有头结点：L->next==NULL，无头结点：L==NULL习题：1、选择题（1）下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示（2）下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。（3）线性表是具有n个（）的有限序列（n>0）。A3．表元素B．字符C．数据元素D．数据项E．信息项（4）链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比（5）下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B.线性表在链式存储时，查找第i个元素的时间同i的值无关C.线性表在顺序存储时，查找第i个元素的时间同i的值成正比D.线性表在顺序存储时，查找第i个元素的时间同i的值无关（6）若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。A.O(0)B.O(1)C.O(n)D.O(n2)（7）对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)（8）线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）2、填空（1）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。（2）线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。（3）在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动__1______个元素。（4）在单链表中设置头结点的作用是_______。（5）链接存储的特点是利用_______来表示数据元素之间的逻辑关系。（6）顺序存储结构是通过_______表示元素之间的关系的;链式存储结构是通过______表示元素之间的关系的。（7）对于双向链表,在两个结点之间插入一个新结点需修改的指针共_____个，单链表为______个。（8）在单链表L中，指针p所指结点有后继结点的条件是：__（9）线性结构包括______、______、_____和______。线性表的存储结构分成_____和______。3、应用题（1）线性表有两种存储结构：一是顺序表，二是链表。试问：如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（2）说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。（3）删除顺序表中所有的正数，要求移动次数小。搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。voiddels(sqlist*L){ints,i;s=0; //正数计数器for(i=0;i<L->n;i++)if(L->data[i]>0s++; //累计当前正数elseif(s>0)L->data[i-s]=l->data[i];//向前移动s位L->n=L->n-s; //调整表长}还可以删除顺序表中所有的负数、字符等，主要是删除数据的条件不一样（4）单链表算法运用，如链表合并，将两个有序表合并为一个有序表lklistpurge(lklistA,lklistB){pointerC,p,q,r;p=A->next;q=B->next;C=A;r=C; //取A头结点作C头结点while(p!=NULL&&q!=NULL){if(p->data<=q->data){r−>next=p;r=p;p=p->next;}else{r−>next=q;r=q;q=q->next;}}if(p!=NULL)r->next=p; //A表有剩余结点elser->next=q;deleteB; //释放B头结点returnC;}第三章栈、队列和串知识点：栈的定义、栈顶、栈底、运算特点（先进后出），顺序实现和链接实现及其特点，栈的应用队列的概念，队头、队尾、运算特点（后进后出），顺序实现、循环队列、链队列串的概念和串长的计算习题选择题（1）对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序（2）栈在（）中应用。A.递归调用B.子程序调用C.表达式求值D.A，Ｂ，Ｃ（3）一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分（4）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改（5）用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时()。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改（6）递归过程或函数调用时，处理参数及返回地址，要用一种称为（）的数据结构。A．队列B．多维数组C．栈D.线性表（7）栈和队列都是（）A．顺序存储的线性结构B.链式存储的非线性结构C.限制存取点的线性结构D.限制存取点的非线性结构应用题（1）名词解释：栈、队列？（2）简述顺序存储队列的假溢出的避免方法及队列满和空的条件。第4章多维数组和广义表知识点：1、多维数组的定义，对于一个多维数据，如何计算里面元素的个数？在存储多维数组时，如果已知首元素的存储地址，如何求数组里面任意元素的存储地址？（注意，行优先、列优先、元素的长度）2、广义表的概念、表长、深度、表头、表尾；广义表的取表头和取表尾操作；注意，取表头去的是原则取表尾得到的是表，会利用广义表的取表头和取表尾操作分离广义表的原子。习题：1、选择题（1）将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（）。供选择的答案：A.198B.195C.197（2）设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为()。A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-1（3）设二维数组A[1..m，1..n]（即m行n列）按行存储在数组B[1..m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为()。A.（i-1）*n+jB.（i-1）*n+j-1C.i*（j-1）D.j*m+i-1（4）数组A[0..4,-1..-3,5..7]中含有元素的个数（）。A.55B.45C.36D.16（5）广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。Head(Tail(Head(Tail(Tail(A)))))A.(g)B.(d)C.cD.d（6）广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。A.(c,d)B.c,dC.((c,d))D.d（7）广义表（（a,b,c,d））的表头是（），表尾是（）。A.aB.（）C.（a,b,c,d）D.（b,c,d）2、填空题（1）设广义表L=((),()),则head(L)是(1)___；tail(L)是(2)__；L的长度是(3)_；深度是(4)__。（2）已知广义表A=(9,7,(8,10,(99)),12)，试用求表头和表尾的操作Head()和Tail()将原子元素99从A中取出来。（3）广义表的深度是__。（4）广义表(a,(a,b),d,e,((i,j),k))的长度是，深度是_。（5）已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是_____。（6）广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是:___。第五章树形结构知识点：树的概念、根、度、兄弟、路径、叶子、孩子、双亲、高度、深度、层数；根据一棵树，能够知道它的度、根节点、叶子结点、深度等；根据树中的某个结点，可以找出它的孩子结点；二叉树的概念、性质和几种特殊形态的二叉树及其特点：斜树、满二叉树、完全二叉树二叉树的存储（顺序存储，适合完全二叉树；链式存储）二叉树的遍历及其应用（先根、中根和后根遍历）二叉树的双序列生成（先根和中根或者中根和后根生成二叉树）树和森林的概念、树和森林与二叉树的相互转换方法、以及转换的二叉树的特点，树和森林的遍历哈弗曼编码的概念和哈弗曼树的构造题目选择题（1）已知一算术表达式的中缀形式为A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE（2）设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（）A．5B．6C．7D．8（3）在下述结论中，正确的是（）①只有一个结点的二叉树的度为0;②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A．①②③B．②③④C．②④D．①④（4）设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（）A．m-nB．m-n-1C．n+1D．条件不足，无法确定（5）若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定（6）在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个A．4B．5C．6D．7（7）设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M3（8）具有10个叶结点的二叉树中有（）个度为2的结点，A．8B．9C．10D．ll（9）一棵完全二叉树上有1001个结点，其中叶子结点的个数是（）A．250B．500C．254D．505E．以上答案都不对（10）设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-1（11）有关二叉树下列说法正确的是（）A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为2（12）二叉树的第I层上最多含有结点数为（）A．2IB．2I-1-1C．2I-1D．2I-1（13）一个具有1025个结点的二叉树的高h为（）A．11B．10C．11至1025之间D．10至1024之间（14）一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+1（15）在一棵高度为k的满二叉树中，结点总数为（）A．2k-1B．2kC．2k-1D．ëlog2kû+1（16）一棵树高为K的完全二叉树至少有（）个结点A．2k–1B.2k-1–1C.2k-1D.2k（17）一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG（18）已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定（19）某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E则前序序列是：（）A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不对（20）二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是：（）A、EB、FC、GD、H填空题（1）二叉树由_(1)__，__(2)_，_(3)__三个基本单元组成。（2）具有256个结点的完全二叉树的深度为______。（3）深度为k的完全二叉树至少有___(1)___个结点，至多有___(2)____个结点。（4）深度为H的完全二叉树至少有_(1)___个结点；至多有_(2)___个结点；H和结点总数N之间的关系是(3)。（5）假设根结点的层数为１，具有ｎ个结点的二叉树的最大高度是____。（6）在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0=______（7）高度为K的完全二叉树至少有_____个叶子结点。（8）高度为8的完全二叉树至少有_____个叶子结点。（9）已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。（10）层完全二叉树至少有_____个结点，拥有100个结点的完全二叉树的最大层数为______。应用题（1）树所有结点的度数之和与结点数有何关系？与边数有何关系？二叉树（或者树中），度为0的结点数与度不为0的结点树有何关系？（2）已知一棵二叉树的对称序和后序序列如下：中序：GLDHBEIACJFK后序：LGHDIEBJKFCA出这棵二叉树，并写出该二叉树的先序序列：写出这棵二叉树的根节点、叶子节点、度为1的节点、度为2的节点(3)转换为对应的森林：（3）从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。（4）二叉树的遍历算法及其应用，如求叶子结点数、度为1的结点数、度为2的结点数，交换二叉树的左右子树、判断两棵二叉树是否等价等。第6章图知识点图的概念：有向图、无向图、完全图、连通图、强连通图、邻接点、顶点的度、出度、入度、路径图的存储：有向图和无向图的邻接矩阵存储和邻接表存储，及其特点图的深度优点遍历和广度优先遍历生成树、最小生成树，Prim和Kruskal算法有向无环图的应用：拓扑排序和关键路径（课件例题）习题1、选择题（1）图中有关路径的定义是（）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是（2）设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．0E．n2（3）一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；（4）要连通具有n个顶点的有向图，至少需要（）条边。A．n-lB．nC．n+lD．2n（5）n个结点的完全有向图含有边的数目（）。A．n*nＢ．n（n＋１）C．n／2D．n*（n－l）（6）一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。A．0B．1C．n-1D．n（7）在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。A．1/2B．2C．1D．4（8）下列哪一种图的邻接矩阵是对称矩阵？（）A．有向图B．无向图C．AOV网D．AOE网（9）下列说法不正确的是（）。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程（10）下面哪一方法可以判断出一个有向图是否有环（回路）：（）A．深度优先遍历B.拓扑排序C.求最短路径D.求关键路径（11）已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7（12）在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。A．G中有弧<Vi，Vj>B．G中有一条从Vi到Vj的路径C．G中没有弧<Vi,Vj>D．G中有一条从Vj到Vi的路径（13）关键路径是事件结点网络中（）。A．从源点到汇点的最长路径B．从源点到汇点的最短路径C．最长回路D．最短回路（14）下面关于求关键路径的说法不正确的是（）。A．求关键路径是以拓扑排序为基础的B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差D．关键活动一定位于关键路径上（15）下列关于AOE网的叙述中，不正确的是（）。A．关键活动不按期完成就会影响整个工程的完成时间B．任何一个关键活动提前完成，那么整个工程将会提前完成C．所有的关键活动提前完成，那么整个工程将会提前完成D．某些关键活动提前完成，那么整个工程将会提前完成2、填空题（1）判断一个无向图是一棵树的条件是______。（2）一个连通图的______是一个极小连通子图。（3）具有10个顶点的无向图，边的总数最多为_____。（4）若用n表示图中顶点数目，则有______条边的无向图成为完全图。（5）G是一个非连通无向图，共有28条边，则该图至少有___个顶点。（6）在有n个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要___条弧。（7）在有n个顶点的有向图中，每个顶点的度最大可达______。（8）在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的______；对于有向图来说等于该顶点的_____。（9）在有向图的邻接矩阵表示中，计算第I个顶点入度的方法是______。（10）对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为_____，邻接表的边结点个数为_____。（11）构造连通网最小生成树的两个典型算法是_____。（12）求图的最小生成树有两种算法，______算法适合于求稀疏图的最小生成树。(13)Prim（普里姆）算法适用于求_____的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求_____的网的最小生成树。三、应用题（1）1）．如果G1是一个具有n个顶点的连通无向图，那么G1最多有多少条边？G1最少有多少条边？2）．如果G2是一个具有n个顶点的强连通有向图，那么G2最多有多少条边？G2最少有多少条边？EABEABGCDF536141325（2）考虑右图：1)从顶点A出发，求它的深度优先生成树：ABGFDEC2)从顶点E出发，求它的广度优先生成树：EACFBDG3）根据普利姆(Prim)算法，求它的最小生成树并计算最小生成树的权值（3）已知一个无向图如下图所示，要求分别用Prim和Kruskal算法生成最小树并计算最小生成树的权值（假设以①为起点，试画出构造过程）。121265432010116618101459第七章排序知识点排序的基本概念。如稳定性、内排序、外排序，有序区增长法，有序度增长等。理解下面排序算法的原理、稳定性、时间复杂度、空间复杂度，最好情况、最坏情况：直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序、归并排序对于上面给的排序算法，给出一组序列，可以写出每一趟的排序结果。习题选择题（1）某内排序方法的稳定性是指()。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对（2）下面给出的四种排序法中()排序法是不稳定性排序法。A.插入B.冒泡C.二路归并D.堆（3）下列排序算法中，其中（）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序（4）若要求尽可能快地对序列进行稳定的排序，则应选（）。A．快速排序B．归并排序C．冒泡排序（5）下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。()A．选择排序法B.插入排序法C.快速排序法D.堆积排序法（6）在下列排序算法中,哪一个算法的时间复杂度与初始排序无关（）。A．直接插入排序B.气泡排序C.快速排序D.直接选择排序（7）下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序（8）下列排序算法中()排序在一趟结束后不一定能选出一个元素放在其最终位置上。A.选择