软件设计师培训-数据结构与算法

数据结构与算法概述算法知识点复习模拟练习考点分析主要内容数据结构知识点复习考点分析数据结构与算法基础常用数据结构：57%数据结构基础与线性表：7树和二叉树：14图：11算法基础：43%算法的描述与分析常用数值计算算法常用非数值计算算法排序算法查找算法数据结构与算法概述数据结构的概念：数据结构研究的内容：数据结构的主要逻辑结构数据结构：(DataStructure)数据结构是带“结构”的数据元素的集合。“结构”即指数据元素之间存在的联系。所以数据结构又可以定义为有联系的数据元素的集合。数据结构主要研究几种常用的数据结构的逻辑特点、存储结构的实现、常用的操作的具体实现方法、各种结构的具体应用等问题。线性结构：线性表、栈、队列、数组、广义表非线性结构：树、图常用的排序算法、查找算法、数值计算、字符串处理、数据压缩算法、递归算法、图的相关算法算法第一部分线性表分值：0~1分（每年）分数比重：0%~10%重要知识点：1、顺序表的结构特点2、单链表的结构特点3、双向链表的插入删除4、循环链表的结构特点第一部分线性表顺序表特点：利用物理存储位置的相邻关系反应元素之间的次序关系优点：1.无需为表示结点间的逻辑关系而增加额外的存储空间；2.可方便地随机存取表中的任一元素。缺点：1.插入或删除运算不方便，需要移动大量的结点，其效率较低；2.需要预先确定顺序表的最大表长，由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配。因此当表长变化较大时，难以确定合适的存储规模。第一部分线性表单链表lista1d1a2d2a3d3a4d4∧物理状态逻辑状态d2d1d3d4a2a3a4a1d3d4∧d2…优点：1.链表动态存储分配的结构，能有效利用存储空间；。2.插入或删除时只需要修改指针，而不需要进行大量元素的移动。缺点：1.必需为表示结点间的逻辑关系而增加额外的存储空间；2.不能随机存取、访问数据元素。特点：单链表中逻辑上相邻的数据元素在物理上不一定相邻。数据元素之间的逻辑关系通过链指针间接地反映出来。第一部分线性表双向链表特点：双向链表中查找某结点的直接前驱结点和直接后继结点的运算的时间复杂度均为O(1)es①②③④…bpa…①s-prior=p-prior;②p-prior-next=s;③s-next=p;④p-prior=s;①p-prior-next=p-next;②p-next-prior=p-prior;abc②①……插入：删除：p第一部分线性表循环链表循环链表(CircularLinkedList)：链表中最后一个结点的指针域指向整个链表的头结点，从而使链表形成一个首尾相接的环形链表。特点：从链表尾部到链表头部比较方便。从表中任一结点出发均可找到表中其它结点。判空：表尾判断：La1…LanL-next==L;p-next==L;reara1aiai-1…an…采用尾指针的循环单链表开始结点的存储位置：rear-next-next终端结点的存储位置：rear第一部分线性表真题200505●循环链表的主要优点是(38)（38）A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链200605●给定—个有n个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一个元素平均需要移动（54）个元素。（54）A．(n+1)/2B．n/2C．(n-1)/2D．1DC第一部分线性表真题200611●某双向链表中的结点如下图所示，删除t所指结点的操作为（54）。(54)A.t-prior-next=t-next;t-next-prior=t-prior;B.t-prior-prior=t-prior;t-next-next=t-next;C.t-prior-next=t-prior;t-next-prior=t-next;D.t-prior-prior=t-next;t-next-prior=t-prior;A第一部分线性表真题200711●对于n（n≥0）个元素构成的线性序列L，在（60）时适合采用链式存储结构。（60）A.需要频繁修改Ｌ中元素的值B.需要频繁地对Ｌ进行随机查找C.需要频繁地对Ｌ进行删除和插入操作D.要求L存储密度高C第一部分线性表真题2009.11●单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是(60)。(60)A．若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)B．在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C．加入头结点后，代表链表的头指针不因为链表为空而改变D．加入头结点后，在链表中进行查找运算的时间复杂度为O(1)B分值：0~1分（每年）分数比重：0%~10%重要知识点：1、栈的结构特点2、队列的结构特点3、双端队列与循环队列4、串的存储结构、基本操作和模式匹配第二部分栈、队列和字符串栈特点：后进先出的线性表双向栈：使两个栈共享一维数组S[MAXNUM]，利用栈的“栈底位置不变，栈顶位置动态变化”的特性，将两个栈底分别设为0和MAXNUM-1，而它们的栈顶都往中间方向延伸的栈称为双向栈。在一端进行插入和删除操作的线性表。栈顶：允许插入和删除的一端。栈底：不允许插入和删除的一端。a1a2a3an-1an…入栈出栈栈顶元素栈底元素概念：第二部分栈、队列和字符串自由区0MAXNUM-1lefttoprighttop队列特点：先进先出的线性表队列是只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。队尾(rear)：允许插入的一端叫做队尾。队头(front)：允许删除的一端叫做队头。第二部分栈、队列和字符串a1a2a3…an-1an入队列出队列队尾元素队头元素概念：循环队列特点：1、循环队列只针对顺序队列而言2、入队rear=(rear+1)%MAXSIZE;3、出队front=(front+1)%MAXSIZE;4、判队满：front==(rear+1)%MAXSIZE5、判队空：rear==front6、元素个数：(rear-front+MAXSIZE)%MAXSIZE(采用少用一个存储单元的方法区分队空和队满)第二部分栈、队列和字符串7012a2front345a6a5a4a3rear6把顺序队列所使用的存储空间臆造成一个逻辑上首尾相连的循环队列。双端队列分类：1、输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入）；2、输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除）。3、限定双端队列从某个端点插入的元素只能从该端点删除，则双端队列就蜕变为两个栈底相邻接的栈了。第二部分栈、队列和字符串想象自己在邮局里排队,当最终轮到自己时,邮局工作人员要求填写一张表格,于是自己站在旁边填表,工作人员为队列中下一个人服务.在填表后,工作人员将继续为自己服务,实质上自己又回到了队列的前端.有时可能会排在一个队列后面,随即因嫌队伍太长而离去.a1a2aia0an-1端1端2串的存储结构第二部分栈、队列和字符串（1）定长顺序串：按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区（2）堆串：可用函数malloc（）和函数free（）完成动态存储管（3）块链串：用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。例：串值为abcdef的结点大小为4的链串块链串注意事项：①为了提高存储密度，可使每个结点存放多个字符。②当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。③会给串的连接操作带来一定的方便，对模式匹配操作不方便。④虽然提高结点的大小使得存储密度增大，，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。abcdef##∧S串的基本操作——难掌握的部分第二部分栈、队列和字符串（1）串比较：StrCompare(S,T)若ST，则返回值0；若ST，则返回值0；若ST，则返回值0。例如：StrCompare(‘data’,‘state’)0、StrCompare(‘cat’,‘case’)0（2）串联接：Concat(&T,S1,S2)用T返回由S1和S2联接而成的新串。例如：Concate(T,‘man’,‘kind’)求得T=‘mankind’（3）求子串:SubString(&Sub,S,pos,len)用Sub返回串S的第pos个字符起长度为len的子串。例如：SubString(sub,‘commander’,4,3)求得sub=‘man’；（4）串定位：Index(S,T,pos)若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。假设S=‘abcaabcaaabc’,T=‘bca’Index(S,T,1)=2；Index(S,T,3)=6；（5）串替换：Replace(&S,T,V)用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串假设S=‘abcaabcaaabca’，T=‘bca’，若V=‘x’，则经置换后得到S=‘axaxaax’串的模式匹配第二部分栈、队列和字符串（1）BF算法：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，从主串S的第二个字符开始和模式T的第一个字符进行比较；重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。（2）KMP算法：从主串S的第一个字符开始和模式T的第一个字符进行比较，若相等，则继续比较两者的后续字符；否则，主串当前位置字符和模式T的上次匹配失败的字符的next数组值所对应的字符开始进行比较；重复上述过程，直到T中的字符全部比较完毕，则说明本趟匹配成功；或S中字符全部比较完，则说明匹配失败。串的模式匹配第二部分栈、队列和字符串KMP算法的重点（1）next数组：（2）nextval数组：0102010422nextval[j]0112123422next[j]abacabaaadT串12345678910j真题200705●输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列（57）。（57）A.2、8、1、4B.1、4、8、2C.4、2、1、8D.2、1、4、8第二部分栈、队列和字符串D真题200711●设栈S和队列Q的初始状态为空，元素按照a、b、c、d、e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c、d、b、a、e，则元素的出栈顺序是（58），栈S的容量至少为（59）。（58）A.a、b、c、d、eB.e、d、c、b、aC.c、d、b、a、eD.e、a、b、d、c（59）A.2B.3C.4D.5第二部分栈、队列和字符串CB真题200905●下面关于栈和队列的叙述，错误的是（60）。（60）A.栈和队列都是操作受限的线性表B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)C.若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高D.利用两个栈可以模拟一个队列的操作，反之亦可第二部分栈、队列和字符串D真题200911●对于长度为m（m1）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是（61）。(61)A．若入栈和入队的序列相同，则出栈序列和出队序列可能相同B．若入栈和入队的序列相同，则出栈序列和出队序列可以互