复习提纲：算法与数据结构

1、1、算法的概念是为了解决某类问题而规定的一个有限长的操作序列。特性：有穷性确定性可行性输入输出评价标准：正确性可读性健壮性高效性2、算法的复杂度：算法计算量所需资源的大小时间复杂度：T(n)=O(f(n),他表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的时间复杂度空间复杂度：S(n)=O(f(n)，算法所需空间的度量。3、数据结构中的逻辑结构分为：线性和非线性结构4、线性表的两种存储方式：顺序存储和链式存储的特点及比较。顺序存储：指用一组地址连续的存储单元依次存储线性表的数据元素 链式存储：用一组任意的存储单元存储线性表的数据元素。5、线性表的特点存在唯一的一个

2、被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个之外，结构中的每一个数据元素均只有一个前驱除最后一个之外，结构中的每一个数据元素均只有一个后继6、在长度为n的顺序表中的第i个位置处插入一个元素，需要移动多少个元 素？n-i+17、理解算法：线性表La和Lb，将两个表合并成一个新的线性表并存于La中。8、带头结点的单链表和不带头结点的单链表为空的条件分别是？带头结点的 循环单链表为空的条件是？带头结点的单链表为空的条件：没有下一个节点L-next=NULL不带头结点的单链表为空的条件：L=NULL循环单链表为空的条件：head-next=head带头结点的循环单链表为

3、空的条件是9、在单链表中插入结点的算法中，指针如何修改。P3410、理解单链表中插入新结点的算法p3411、理解双向链表中插入新结点的算法p4012、理解栈和队列的操作特点：先进后出，先进先出。已知进栈顺序，求可 能的出栈顺序。链栈相对于顺序栈的优点是什么？链栈在入栈前不需要判断栈是否为满，只需要为入栈元素动态分配一个节点 空间13、理解算法：执行进栈操作，则先要判断栈S是否为满，若不满再将记录 栈顶的下标变量top加1，再将进栈元素放进栈顶位置上。P5914、循环单链表的特点：尾指针的next指向头结点15、循环队列中进行插入和删除操作后，其头尾指针如何变化？根据循环队 列的容量及头尾指针，

4、求循环队列中元素的个数。插入：Q.rear=(Q.rear+1)%MAXQSIZE /尾指针加 1删除：Q.front=(Q.front+1)%MAXQSIZE /头指针加 1元素个数：(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE16、用那种数据结构来实现括号匹配的算法？17、已知二维数组的行数和列数，及每个元素需要的存储单元数，求其需要 的存储容量。18、特殊矩阵进行压缩存储的目的是为了节约存储空间19、对称矩阵的压缩存储，求某元素的存储地址。P10120、稀疏矩阵的压缩存储方法一般有三元组法和十字链表法21、求某广义表的表尾p103取出的表尾为除去表头之外，由其余元

5、素构成的表22、字串的定义，子串定位函数index(s1,s2)的理解串中任意个连续的字符组成的子序列称为该串的字串23、已知树的孩子链表，求树及其带双亲的孩子链表24、二叉树的常用性质的应用：性质1-性质425、已知完全二叉树中的结点个数，求叶子结点的个数26、算法设计：求二叉树中度分别为0、1、2的结点个数27、已知二叉树的中序遍历序列和后序遍历序列，或已知二叉树的中序遍历 序列和前序遍历序列，求二叉树的形态28、哈夫曼树的特点，哈夫曼树的应用：给出权值，求哈夫曼树及哈夫曼编 码。29、根据图的邻接矩阵存储，求某顶点的入度和出度。30、已知图的顶点和边，求该图的深度优先遍历31、连通图的特

6、点：n个顶点至少有多少条边？32、根据图的邻接表求邻接矩阵，根据邻接矩阵求深度优先遍历。33、折半查找的条件：顺序存储，且本身有序。并理解折半查找的过程34、散列查找的查找过程:如何根据散列函数构造散列表，解决冲突的方法？ 求散列查找的平均查找长度。35、排序中的稳定性是指：关键字值相同的记录，其相对位置在排序后不发 生变化。36、掌握冒泡排序的排序过程及算法实现。37、插入类排序的特点38、根据一组关键字序列，构造二叉排序树，并求平均情况下的平均查找长 度。39、已知一组关键字序列，求基数排序每趟的排序过程。40、给出一段代码，对其进行时间复杂度的分析。（关键语句的执行次数，和 n的数量级的

7、关系）1、计算机算法主要是指（C ）。计算方法排序方法解决问题的有限运算序列数据的调度方法1、关于逻辑结构，以下说法错误的是（D ）逻辑结构与数据元素本身的形式，内容无关逻辑结构与数据元素本身的相对位置无关逻辑结构与所含数据元素的个数无关逻辑结构与数据元素的存储有关，是不能独立于计算机的2、树形结构的特点是，一个结点可以有（B ）A.多个直接前驱B.多个直接后继C.多个前驱D.一个后继2、数据结构从逻辑上分为（C)。A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.逻辑结构与非逻辑结构3、以下关于线性表说法正确的是(D )。每个元素都有一个前驱和一个后继线性表至少有一个元

8、素线性表中的元素必须按由大到小排序除首尾元素之外，其他元素都仅有一个直接前驱和一个直接后继3、设栈的入栈序列是a,b,c,d, e则不可能的出栈序列是（C ）。e,d,c,b,aB. d,e,c,b,aC. d,c,e,a,bD. a,b,c,d,e4、设栈的入栈序列是1,2,3,4，则不可能的出栈序列是（D ）。1,2,4,3B. 2,1,3,4C. 1,4,3,2D. 4,3,1,24、判定循环队列Q （元素最多为m个，队头指针为front，对尾指针rear）为空 的条件是（C ）。rear-front=mC. rear二front4、判定循环队列Q （元素最多为m个， 的条件是（D ）。

9、rear-front=mC. front二rear%m4、栈和队列的共同点是（C）rear-front-1=mD. front=(rear+1)%m队头指针为front,队尾指针rear)为满rear-front-1=mD. front=(rear+1)%mB.都是先进先出都是先进后出只允许在端点处插入和删除元素D.没有共同点4、表达式a*（b+c）-d的后缀表达式为（B）A. abcd*+-B. abc+*d-abc*+d-D. +*abcd5、线性表在链式存储中各结点之间的地址（D ）A.必须全部地址连续B.部分地址必须连续C.不能连续D.连续与否无要求5、不带头结点的单链表Head为空的

10、判定条件是（A ）。A. Head=NULLB. Head-next=NULLC. Head-next=HeadD. Head!=NULL6、在单链表中，若要在p所指向的结点之后插入一个新的结点，则需要相继修改（B）个指针域的值。A. 1 B. 2 C. 3 D. 46、在单链表中，若P所指结点不是最后结点，在P之后插入、所指结点，则执 行（B ）。A. S-next=P; P-next=s;C. S-next=P-next;P=S;7、链栈相较于顺序栈而言，优点为A-插入操作更简单C.不会出现栈空的情况8、数组的两种常用基本操作是（A.建立与删除C.查找和修改8、一维数组与线性表的区别是（S

11、-next=P-next; P-next=S;P-next=S; S-next=P;（B ）。通常不会出现栈满的情况删除操作更方便）索引与修改D.查找与索引A ）。A.前者长度固定，后者长度可变可变 C.两者长度都固定可变B.后者长度固定，前者长度D.两者长度均9、数组A中，行下标i为07,列下标j为09,每个元素占用3个字节长度，从首地址PA开始连续连续存放数组A中元素于存储器，则至少需要的单元数是（D )。A. 80B. 100C. 270D. 24010、设广义表L=（A,B,C）,则L的长度和深度分别为（CA. 3,1B. 3,2C. 1,2D. 1,110、对稀疏矩阵进行压缩存储的目

12、的是（C )。11、11、A.便于进行矩阵运算C.节省存储空间B.D.便于输入输出降低运算的时间复杂度C语言中 bcd321ABCD 的子串可以是（DA.abcdB.321AB串的长度是指（B ）A.串中所含不同字母的个数）。C. abcABC D. 21AB B.串中所含字符的个数串中所含不同字符的个数串中所含非空格字符的个数12、深度为4的二叉树最多有（C个结点A. 8B. 16C. 15D. 1712、A.a,c,b,e,dB. d,e,c,a,bC.d,e,a,b,cD. c,e,d,b,a已知某二叉树的后序遍历序列为d,a,b,e,c，中序遍历序列为d,e,b,a,c,则其先序遍历序

13、列为（12、对n（nN2 ）个权值均不相同的字符构成哈夫曼树，则该树表述错误的是(A )。该树一定是一棵完全二叉树树中没有度为1的结点树中两个权值最小的结点一定是兄弟结点树中任一非叶节点的权值一定不小于下一层任一结点的权值13、连通具有n个顶点的无向图至少需要（D ）条边。A. nB.n+1C. n/2D. n-113、设无向图G=(V,E)中含7个顶点，则在图G在任何情况下都是联通的，则至少需要的边数为(C)。A. 6B.14C. 16D. 1814、散列函数值应按(C )取其值域的每一个值。A.最大概率B.最小概率C.同等概率D.平均概率14、排序方法的稳定性是指(D )。排序算法能在规定

14、时间内完成排序排序算法能得到确定的结果排序算法不允许有相同关键字的元素对于关键字值相同的记录，其相对位置在排序后不发生变化15、在有序表3,9,14,27,39,44,56,68,71,85,90中，用折半查找法查找关键值 码27,所需关键码的比较次数为(B )。A. 2B.3C. 4D.515、冒泡排序的时间复杂度为(B )A. O(n)B. O(n2)C. O(log n) D. O(nlog n)22二、填空题(10小题，每小题2分，共20分)1、算法计算量的资源大小称之为计算的复杂性。1、一般而言，树形结构中元素之间存在1： n的对应比例关系2、当利用长度为n的数组顺序存储一个栈时，假

15、设用top=0表示栈空，则向这个栈插入一个元素时，首先应执行top=top+1来修改top指针。2、循环队列用数组Am(下标从0至m-1)存放其元素值，已知其头尾指针分别为front,rear，则当前队列中元素的个数是 (rear-font+m) %m。3、在以Head为表头指针的带有头结点的循环单链表中，判断循环链表为空的条 件为 Head-next=Head 。3、在带有头结点的单链表L中(头指针为Head)，指向第1个元素结点的指针 是 Head-next4、一个n*n的对称矩阵以行为主序放入内存，其容量为n*(n+1)/24、稀疏矩阵的压缩存储方法一般有三元组法和十字链表法。5、广义表

16、的深度是指表中所含 括号的层数。6、设 si=Hello ”,s2=”，s3=laochen”，则 s1,s2,s3 连后的结 果是 Hello laochen 。6、设 si=xiaochen ,s2= ,s3= nihao ”，则 s1,s2,s3 连后的结 果是 xiaochen nihao 。7、下列程序段的时间复杂度为_O(n)。i=s=0；whilei(in)(i+；s+=i;8、二叉树第i (iNl)层上最多有2i-i个结点。8、深度为k (kNl)的二叉树最多有2k-i个结点。9、一棵有n个顶点的生成树有且仅有_n-1条边。9、设有向图G有n个顶点，采用邻接矩阵作为存储结构，则

17、该矩阵中含有壁 个数据元素。10、高度为5 (叶子层除外)的三阶B树至少有 个结点。10、假设n个关键字均有相同的Hash函数值，若用线性探测再散列方法将 这n个关键字映射存储到Hash表中时，则共需n*(n-1)/2次探测三、算法应用题(3小题，每小题5分，共15分)1、设线性表La和Lb，将两个表合并成一个新的线性表并存于La中，请在下划线处补充正确的代码。(5分)Void union(&Linear_list La, &Linear_list Lb)(La_len=Linear_ListLength(La);Lb_len=Linear_ListLength(Lb);/ 求线性表的长度Fo

18、r(i=1;iLb_len;i+)GetElem(Lb,i,e);/取 Lb中第i个元素赋值给eIf(!LocateElem(La,e)ListInsert(La,+La_len,e);1、若要删除线性表L中的第i个结点元素，请在下划线处补充正确的代码。(5 分)Void Delete(Linear_list &L, int i, int &n) (/n 为线性表的实际长度If(in) return ERROR;For(j=i;jtop= MAXLEN-1 );(MAXLEN-1)return 0; ( printf(栈满!);/标记位为0，栈满不能else进栈栈不为满 s-top=s-top+1;s-datas-top=x;3、设计算法：交换二叉树每个结点的左孩子和右孩子。请补充完整下列函数的 函数体。提示：如果某结点左右子树为空，返回，否则交换该结点左右孩子，然 后递归交换左右子树。（8分）voi