软考辅导数据结构与算法

数据结构与算法软考辅导数据结构与算法概述算法知识点复习模拟练习考点分析主要内容数据结构知识点复习考点分析数据结构与算法基础常用数据结构：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①②③④

…

bp

a

…①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;①p->prior->next=p->next;②p->next->prior=p->prior;

a

b

c②①……插入：删除：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)/2

B．n/2

C．(n-1)/2

D．1第一部分线性表真题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;第一部分线性表真题200711●对于n（n≥0）个元素构成的线性序列L，在（60）时适合采用链式存储结构。（60）A.需要频繁修改Ｌ中元素的值B.需要频繁地对Ｌ进行随机查找C.需要频繁地对Ｌ进行删除和插入操作D.要求L存储密度高第一部分线性表真题2009.11●单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是(60)。(60)A．若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)B．在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C．加入头结点后，代表链表的头指针不因为链表为空而改变D．加入头结点后，在链表中进行查找运算的时间复杂度为O(1)分值：0~1分（每年）分数比重：0%~10%重要知识点：

1、栈的结构特点

2、队列的结构特点

3、双端队列与循环队列第二部分栈、队列栈特点：后进先出的线性表双向栈：使两个栈共享一维数组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第二部分栈、队列真题200705●输入受限的双端队列是指元素只能从队列的一端输入、但可以从队列的两端输出，如下图所示。若有8、1、4、2依次进入输入受限的双端队列，则得不到输出序列（57）。（57）A.2、8、1、4

B.1、4、8、2

C.4、2、1、8

D.2、1、4、8第二部分栈、队列真题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第二部分栈、队列真题200905●下面关于栈和队列的叙述，错误的是（60）。（60）A.栈和队列都是操作受限的线性表

B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)C.若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高

D.利用两个栈可以模拟一个队列的操作，反之亦可第二部分栈、队列真题200911●对于长度为m（m>1）的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是（61）。(61)A．若入栈和入队的序列相同，则出栈序列和出队序列可能相同B．若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C．入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是l:n(n≥1)D．入栈序列与出栈序列关系为1:1，而入队序列与出队序列关系是l:n(n≥1)第二部分栈、队列真题201011●设循环队列Q的定义中有rear和len两个域变量,其中rear表示队尾元素的指针,len表示队列的长度,如下图所示(队列长度为3,队头元素为e)。设队列的存储空间容量为M,则队头元素的指针为(57)。(57)A.(Q.rear+Q.len-1)B.(Q.rear+Q.len-1+M)%MC.(Q.rear-Q.len+1)D.(Q.rear-Q.len+1+M)%M第二部分栈、队列分值：0~1分（每年）分数比重：0%~10%重要知识点：

1、数组的地址计算

2、数组的压缩存储

3、广义表的表示

4、广义表的表头、表尾第三部分数组与广义表

数组特点：

1.数组中的数据元素具有相同的数据类型。

2.数组是一种随机存取结构，只要给定一组下标，就可以访问与其对应的数组元素。

3.数组中的元素个数是固定的。基本操作——存取、修改对于数组A，一旦给定其维数n及各维长度bi（1≤i≤n），则该数组中元素的个数和元素之间的关系就不再发生变化了，既不可以对数组做插入和删除操作，也不涉及移动元素操作。第三部分数组与广义表

多维数组和广义表是对线性表的扩展——线性表中的数据元素本身又是一个多层次的线性表。数组的地址计算第三部分数组与广义表

Loc[aij]

=

Loc[a00]+(

n

i

+

j

)

size

a00a02a03a0j…a0,n-1

a10a11a12a1j…a1,n-1a20a21a22a2j…a2,n-1A[m][n]=…………ai,0ai,1……aij……am-1,0am-1,1am-1,2……am-1,n-1Loc[aij]=Loc[a00]+(mj+i)size行序为主序：列序为主序：a11a21a22......aij......ann

Loc[i

,

j]=123......n*(n+1)/2

a11

a12a13……a1n

a21a22a23……a2n

a31a32a33

……a3nA=…………

an1an2an3……annLoc[i,j]={Loc[1,1]+i(i-1)/2+j-1当i≥j时Loc[1,1]+j(j-1)/2+i-1当i<j时

对于对称矩阵，因其元素满足aij=aji，我们可以为每一对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将n2个元素压缩到n(n+1)/2个空间中。一维数组A中对应的下标为：数组的压缩存储第三部分数组与广义表

对称矩阵：aij=aji带状矩阵：在矩阵A中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。特点:

i=1,j=1,2;当

1<i<n，j=i-1,i,i+1i=n,j=n-1,n;时，即|i-j|≤1，aij非零，其他元素均为零。

An×n=a11a12a21a22a23a32a33a34a43a44a45

………ann-1ann0元素0元素数组的压缩存储第三部分数组与广义表

1.确定存储该矩阵所需的一维向量空间的大小：三对角带状矩阵中除第一行和最后一行只有两个元素外，其余各行均有3个非零元素。由此可得到一维向量所需的空间大小为：3n-2。2.确定非零元素在一维数组空间中的位置：Loc[i,j]=Loc[1,1]+3×(i-1)-1+j-i+1=Loc[1,1]+2(i-1)+j-13.矩阵中元素aij

在一维数组A中对应的下标为：

k=2(i-1)+j-1(1≤i,j≤n，|i-j|≤1)j-i-101aij在第i行中的位置123第i行中aij前面非零元素个数012数组的压缩存储第三部分数组与广义表

rowcolvalue该非零元素所在的行号该非零元素所在的列号该非零元素的值数组的压缩存储第三部分数组与广义表

稀疏矩阵：三元组存储十字链表M6×7=012900000000000-3000014000240000018000001500-7000121213931-3361452184324611564-7data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]数组的压缩存储第三部分数组与广义表

稀疏矩阵：十字链表-30050-100800711314522-138^^^^^347^^11、A=()2、B=(e)3、C=(a,(b,c,d))4、D=(A,A,())5、E=(A,B,C)6、F=(a,F)表示广义表A是一个空表，其长度为0表示广义表B长度为1，只有一个原子项e表示广义表C长度为2，两个元素分别为原子项a和子表(b,c,d)。表示广义表D长度为3，三个元素都是广义表，分别为A、A和()。表示广义表E长度为3，三个元素A、B、C都是广义表，代入值以后E=((),(e),(a,(b,c,d)))。表示广义表F长度为2，两个元素分别是原子项a和子表F。这是一个递归表，相当于无穷广义表F=（a,F）=(a,(a,(a,…,)))。广义表的表示第三部分数组与广义表

广义表的长度定义为最外层包含元素个数。广义表的深度定义为所含括弧的重数;“原子结点”的深度为0;“空表”的深度为1。广义表的表头、表尾第三部分数组与广义表

任何一个非空广义表GL=(d1,d2,…,dn)均可分解为

表头Head(GL)=d1

和表尾Tail(GL)=(d2,…,dn)例如:D=(E,F)=((a,(b,c))，F)Head(D)=ETail(D)=(F)Head(E)=aTail(E)=((b,c))Head(((b,c)))=(b,c)Tail(((b,c)))=()Head((b,c))=bTail((b,c))=(c)Head((c))=cTail((c))=()真题200511●简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点。若无向图G有n个节点，其邻接矩阵为A[1..n,1..n],且压缩存储在B[1..k]中，则k的值至少为(40)。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[(41)]中。（40）A.n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/2(41)A.18B.19C.20D.21第三部分数组与广义表

真题201005第三部分数组与广义表

真题200905●设L为广义表，将head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=((x,y,z),a,(u,t,w))，则从L中取出原子项y的运算是（62）（62）A.head(tail(tail(L)))B.tail(head(head(L)))C.head(tail(head(L)))D.tail(tail(head(L)))第三部分数组与广义表

分值：1~17分（每年）分数比重：2%~20%重要知识点：

1、树和二叉树的定义

2、二叉树的重要性质

3、二叉树的遍历、线索二叉树

4、树与二叉树的转换

5、二叉树的应用——哈夫曼树第四部分树与二叉树

树和二叉树的定义树的概念和逻辑特点：

1、有且仅有一个结点没有前驱结点,该结点为树的根结点。

2、除了根结点外,每个结点有且仅有一个直接前驱结点。

3、包括根结点在内，每个结点可以有多个后继结点。二叉树的概念和逻辑特点

1、每个结点的度都不大于2；2、每个结点的孩子结点次序不能任意颠倒。第四部分树与二叉树

相关术语：结点、结点的度、叶子结点、分支结点、结点的层次、结点的层序编号、树的度、树的高度（深度）、双亲结点、孩子结点、兄弟结点、堂兄弟结点、子孙结点、祖先结点。完全二叉树、满二叉树。二叉树的重要性质性质1：在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。性质3：对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1。性质4：具有n个结点的完全二叉树深度为log2n+1

。性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意的序号为i的结点有：(1)若i=1,则i无双亲结点若i>1,则i的双亲结点为i/2

(2)若2*i>n,则i无左孩子若2*i≤n,则i结点的左孩子结点为2*i(3)若2*i+1>n,则i无右孩子若2*i+1≤n,则i的右孩子结点为2*i+1第四部分树与二叉树

二叉树的遍历第四部分树与二叉树

ABCDKFGIJEH前序遍历序列:

A,B,D,K,J,G,C,F,I,E,H中序遍历序列:

D,B,G,J,K,A,F,I,E,C,H后序遍历序列:

D,G,J,K,B,E,I,F,H,C,A按层次遍历序列:

A,B,C,D,K,F,H,J,I,G,E例：已知结点的先序序列和中序序列先序序列：ABDEJCFIG中序序列：DBJEAFICG

则可按上述分解求得整棵二叉树。

ADCIFGJBE第四部分树与二叉树

例：已知结点的中序序列和后序序列中序序列：ABCEFGHD后序序列：ABFHGEDC

则可按上述分解求得整棵二叉树。CADGEHFB线索二叉树第四部分树与二叉树

一.什么是线索二叉树二.线索二叉树的构造

利用二叉链表中空的指针域指出结点在遍历序列中的直接前驱和直接后继;这些指向前驱和后继的指针称为线索,加了线索的二叉树称为线索二叉树.利用结点的空的左指针域存放该结点的直接前驱的地址,空的右指针域存放该结点直接后继的地址;而非空的指针域仍然存放结点的左孩子或右孩子的地址.注：每棵二叉树都可以构造先序、中序和后序三种线索二叉树。树、森林与二叉树的转换第四部分树与二叉树

树转换成二叉树：

1、树中所有相邻兄弟之间加一条连线。2、对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。森林转换为二叉树的方法为：1、将森林中的每棵树转换成相应的二叉树。2、第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，即为由森林转换得到的二叉树。ABECDFGHABCDEFIJGH带权路径长度：

设二叉树有n个带权值的叶子结点，定义从二叉树的根结点到二叉树中所有叶子结点的路径长度li与相应叶子结点权值wi的乘积之和称作该二叉树的带权路径长度。TWPL(T)=72+52+23+43+92=6075249ACBIGFDEHWPL=哈夫曼树第四部分树与二叉树

52310515782511110000(011)(010)(10)(11)(00)字符：staec

字符出现的次数：38752c:010s:011e:00a:10t:11哈夫曼编码第四部分树与二叉树

真题200505●表达式a*(b+c)-d的后缀表达形式为___(39)___。（39）A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd●若二叉树的先序遍历序列为ABDECF，中序遍历序列DBEAFC，则其后序遍历序列为__(40)___。（40）A.DEBAFCB.DEFBCAC.DEBCFAD.DEBFCA第四部分树与二叉树

真题201005●若用n个权值构造一棵最优二叉树（哈夫曼树），则该二叉树的结点总数为___(59)___。(38)A.2nB.2n-1C.2n+1D.2n1●在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n个结点，采用三叉链表存储时，每个结点的数据域需要d个字节，每个指针域占用4个字节，若采用顺序存储，则最后一个结点下标为k（起始下标为1）,那么___(39)___时采用顺序存储更节省空间。(39)A.d<12n/(k-n)B.d>12n/(k-n)C.d<12n/(k+n)D.d>12n/(k+n)第四部分树与二叉树

真题200605●与逆波兰式ab+-c*d-对应的中缀表达式是（45）。（45）A．a-b-c*d

B．-(a+b)*c-d

C．-a+b*c-d

D．(a+b)*(-c-d)●为便于存储和处理一般树结构形式的信息，常采用孩子ˉ兄弟表示法将其转换成二叉树（左子关系表示父子、右子关系表示兄弟），与下图所示的树对应的二叉树是（53）。（53）第四部分树与二叉树

真题200612●“X=(A+B)×(C-D/E)”的后缀式表示为（20）（20）A.XAB+CDE/-×=B.XAB+C-DE/×=C.XAB+CDE-/×=D.XAB+CD-E/×=200705●已知某二叉树的中序序列为CBDAEFI、先序序列为ABCDEFI，则该二叉树的高度为（58）。（58）A.2B.3C.4D.5第四部分树与二叉树

真题200705●由权值为29、12、15、6、23的五个叶子结点构造的哈夫曼树为（64），其带权路径长度为（65）。第四部分树与二叉树

真题200805●若将某有序树T转换为二叉树T1，则T中结点的后(根)序序列就是T1中结点的__(59)__遍历序列。例如，下图(a)所示的有序树转化为二叉树后如图(b)所示。(59)A.先序B.中序C.后序D.层序

第四部分树与二叉树

真题201011●下面关于哈夫曼树的叙述中,正确的是(58)。(58)A.哈夫曼树一定是完全二叉树

B.哈夫曼树一定是平衡二叉树

C.哈夫曼树中权值最小的两个结点互为兄弟结点D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点●已知一棵度为3的树(一个结点的度是指其子树的数目,树的度是指该树中所有结点的度的最大值)中有5个度为1的结点,4个度为2的结点,2个度为3的结点,那么,该树中的叶子结点数目为(61)。(61)A.10 B.9C.8D.7第四部分树与二叉树

真题200905●下面关于二叉树的叙述，正确的是（61）。（61）A.完全二叉树的高度h与其结点数n之间存在确定的关系B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构C.完全二叉树中一定不存在度为1的结点D.完全二叉树中必定有偶数个叶子结点201105●在（59）中，任意一个结点的左右字数的高度之差的绝对值不超过1.(59)A.完全二叉树B.二叉排序树C.线索二叉树D.最优二叉树第四部分树与二叉树

真题200911●已知一个二叉树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为（57）。对于任意一棵二叉树，叙述错误的是（58）。（57）A．②、③、①、⑤、④B．①、②、③、④、⑤C．②、④、⑤、③、①D．④、⑤、③、②、①（58）A．由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列B．由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列C．由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列D．由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列第四部分树与二叉树

分值：0~5分（每年）分数比重：6%重要知识点：

1、图的基本概念和存储结构

2、图的遍历

3、拓扑排序和最小生成树

4、关键路径

5、最短路径第五部分图

图的基本概念和存储结构图的基本概念：无向图、有向图、无向完全图、有向完全图、稀疏图、稠密图、子图、有向图与无向图的顶点的度、网、回路和环、路径长度、简单路径、简单回路、连通图、连通分量、强连通图、强连通分量。图的存储结构邻接矩阵(数组)表示法；邻接表；十字链表；第五部分图

BACDG1BADEG2C图的遍历深度优先搜索：是指按照深度方向搜索，它类似于树的先根遍历。广度优先搜索：是指按照广度方向搜索，它类似于树的按层次遍历。第五部分图

v1v2v3v4v5v6v7v8v9v1v2v4v7v9v5v3v6v8BAEDCABCDEv1v2v3v4v5v9v6v8v7ABCED拓扑排序拓扑排序将一个有向图中的所有结点排成一个序列，使得图中所有结点应存在的前驱和后继关系都能在队列中体现（前驱在前，后继在后）。过程⑴从AOV网中选择一个没有前驱的顶点并且输出；⑵从AOV网中删去该顶点并且删去所有以该顶点为尾的弧；⑶重复上述两步，直到全部顶点都被输出;第五部分图

C1C2C3C4C6C5C7拓扑序列：C1,C2,C3,C4,C5,C6,C7

最小生成树概念生成树是连通图上的一个极小连通子图。最小生成树是一个连通网中所有生成树中各边权值之和最小的生成树。最小生成树的算法：

1、普里姆算法2、克鲁斯卡尔算法第五部分图

abdcef6155542663abdcef15342abdcef1532554关键路径概念从源点到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫关键活动。关键路径的求法：

⑴事件的最早发生时间ve[k]⑵事件的最迟发生时间vl[k]

⑶活动的最早开始时间e[i]⑷活动的最晚开始时间l[i]第五部分图

v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4第五部分图

v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4ve[k]v2v7v6v5v4v1v3v9v8064577161418a2a7a6a5a4a1a3a9a8e[i]000645777a10a111614第五部分图

v2v1v3v4v5v8v6v7v9a1=6a4=1a7=9a10=2a11=4a8=7a9=4a5=1a6=2a3=5a2=4l[i]10778663201614a2a7a6a5a4a1a3a9a8a10a11v2v7v6v5v4v1v3v9v8vl[k]1814161078660最短路径分类1、求图中的一个结点到其他结点的最短路径。2、求图中任意两点间的最短路径。最短路径的求法：

⑴迪杰斯特拉(Dijkstra)算法⑵Floyd算法第五部分图

BAEDC105030101002060S={A,B,D,C,E}A→B:(A,B)10A→C:(A,D,C)50A→D:(A,D)30A→E:(A,D,C,E)60BAEDC105030101002060最短路径分类1、求图中的一个结点到其他结点的最短路径。2、求图中任意两点间的最短路径。最短路径的求法：

⑴迪杰斯特拉(Dijkstra)算法⑵Floyd算法第五部分图

abd53863c122真题201105●设一个包含N个顶点，E条边的简单无向图采用邻接矩阵存储结构，则该矩阵中的非零元素数目为（60）（60）A.N

B.E

C.2E

D.N+E200505●一个具有n(n>0)个顶点的连通无向图至少有(49)条边。（49）A.n+1

B.n

C.n+2

D.n-1第五部分图

真题200511●在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图中，从A到J的关键路径是(16)，关键路径长度是(17)，从E开始的活动启动的最早时间是(18)。

(16)A.ABEGJ

B.ADFHJ

C.ACFGJ

D.ADFIJ(17)A.22

B.49

C.19

D.35(18)A.10

B.12

C.13

D.15第五部分图

真题200511●简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有n个节点。若无向图G有n个节点，其邻接矩阵为A[1..n,1..n],且压缩存储在B[1..k]中，则k的值至少为____(40)____。若按行压缩存储对称矩阵的上三角元素，则当n等于10时，边(V6，V3)的信息存储在B[___(41)___]中。(40)A.n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/2(41)A.18B.19C.20D.21第五部分图

真题200605●(59)是右图的合法拓扑序列。

(59)A.654321B.123456C.563421D.564213第五部分图

真题200611●求单源点最短路径的迪杰斯特拉（Dijkstra）算法是按（57）的顺序求源点到各顶点的最短路径的。（57）A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增第五部分图

真题200705●某工程计划如下图所示，各个作业所需的天数如下表所示，设该工程从第0天开工，则该工程的最短工期是（59）天，作业J最迟应在第（60）天开工。第五部分图

真题200711●拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定（57）。（57）A.包含回路B.是强连通图C.是完全图D.是有向树200805●设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为__(60)__，其中非零元素数目为__(61)__。(60)A.E2B.N2C.N2-E2D.N2+E2(61)A.NB.N+EC.ED.N–E第五部分图

真题200811●（59）的邻接矩阵是一个对称矩阵。（59）A.无向图B.AOV网C.AOE网D.有向图●具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为（63）。（63）A.O(n2)B.O(e2)C.O(n*e)D.O(n+e)第五部分图

真题200905●下面关于图（网）的叙述，正确的是（58）。（58）A.连通无向网的最小生成树中，顶点数恰好比边数多1B.若有向图是强连通的，则其边数至少是顶点数的2倍C.可以采用AOV网估算工程的工期D.关键路径是AOE网中源点至汇点的最短路径第五部分图

分值：5~15分（每年）分数比重：10%重要知识点：

1、静态表查找——顺序查找、折半查找

2、动态表查找——二叉排序树、平衡二叉树3、哈希表

4、插入类排序5、交换类排序6、选择类排序7、分配类排序第六部分排序与查找

查找基本概念：静态查找：不涉及插入和删除操作的查找。动态查找：涉及插入和删除操作的查找。平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为：其中：n：问题规模，查找集合中的记录个数；pi：查找第i个记录的概率；ci：查找第i个记录所需的关键码的比较次数。第六部分排序与查找

静态查找顺序查找：从线性表的一端向另一端逐个将关键码与给定值进行比较，若相等，则查找成功，给出该记录在表中的位置；若整个表检测完仍未找到与给定值相等的关键码，则查找失败，给出失败信息。折半查找：在有序表中，取中间元素作为比较对象1、若给定值与中间记录的关键字相等，则查找成功；2、若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找。3、不断重复上述过程，直到查找成功，或所查找的区域无记录(low>high)，查找失败。

前提：线性表中的记录必须按关键字有序；必须采用顺序存储。第六部分排序与查找

动态查找——二叉排序树定义：一棵二叉树中，每一个结点的左子树上的结点都比它小，右子树上的结点都比它大。这种二叉树称为二叉排序树。二叉排序树的查找：从根结点开始比较，如果比根结点的值小，则到根结点的左子树上去查找；比根结点大，到根结点的右子树上去查找；与根结点相等，说明查找成功。依此类推，直到所要查找的结点为空，说明查找失败。二叉排序树的构造：将二叉排序树初始化为一棵空树，然后按照顺序逐个读入元素，每读入一个元素，就建立一个新的结点插入到当前已生成的二叉排序树中，即调用上述二叉排序树的插入算法将新结点插入。直到所有结点插入完成，二叉排序树就构造完成了。注：若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。第六部分排序与查找

动态查找——二叉排序树结论：对同样一组数据元素，如果输入的顺序不同，则所建的二叉树形态也不同。特点：

1、一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;

2、每次插入的新结点都是二叉排序树上新的叶子结点;

3、找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；

4、在左子树/右子树的查找过程与在整棵树上查找过程相同；

5、新插入的结点没有破坏原有结点之间的关系。第六部分排序与查找

练习：关键字的输入顺序为：45,24,53,12,28,90，和24,53,90,12,28,45，分别构造二叉排序树动态查找——二叉排序树的删除1.

若结点p是叶子，则直接删除结点p；2.若p结点只有左子树，或只有右子树，则因为该结点只有左子树或只有右子树，也就是说，其后继只有一个分支。删除该结点时，只要将被删除结点的唯一后继（左子树或右子树）直接链接到被删除结点的位置即可。3.若结点p的左右子树均不空：首先找到p结点在中序序列中的直接前驱s结点，然后用s结点的值，替代p结点的值，再将s结点删除,因为s的右指针一定为空，所以只要把s的左孩子链接到s结点本身的位置即可。第六部分排序与查找

动态查找——平衡二叉树平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：⑴根结点的左子树和右子树的深度最多相差1;⑵根结点的左子树和右子树也都是平衡二叉树。平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。在平衡二叉树中，结点的平衡因子可以是1，0，-1。最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子绝对值大于1的祖先结点为根的子树。第六部分排序与查找

动态查找——平衡二叉树的构造基本思想：在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入新结点而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。1.LL型：由于在A的左子树根结点B的左子树上插入结点，A的平衡因子由1变为2。2.RR型：由于在A的右子树根结点B的右子树上插入结点，A的平衡因子由-1变为-2。3.LR型：由于在A的左子树根结点B的右子树上插入结点，A的平衡因子由1变为2。4.RL型：由于在A的右子树根结点B的左子树上插入结点，A的平衡因子由1变为2。第六部分排序与查找

动态查找——平衡二叉树的构造第六部分排序与查找

LL型RR型第六部分排序与查找

LR型RR型动态查找——平衡二叉树依次输入表(30,15,28,20,24,10,12,68,35,50,46,55)中的元素，生成一棵二叉排序树

(1)试画出生成之后的二叉排序树;(2)假定每个元素的查找概率相等，试计算该二叉排序树的平均查找长度；(3)画出由这组元素所构造的平衡二叉树。第六部分排序与查找

哈希表定义：在元素的关键字k和元素的存储位置p之间建立一个对应关系H，使得p=H(k)，H称为哈希函数。创建哈希表时，把关键字为k的元素直接存入地址为H(k)的单元；以后当查找关键字为k的元素时，再利用哈希函数计算出该元素的存储位置p=H(k)，从而达到按关键字直接存取元素的目的。这种查找的方法称为哈希法。哈希函数设计原则：⑴计算简单。哈希函数不应该有很大的计算量，否则会降低查找效率。⑵函数值即哈希地址分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。第六部分排序与查找

哈希表冲突：对于两个不同关键码ki≠kj，有H(ki)＝H(kj)，即两个不同的记录需要存放在同一个存储位置。哈希函数冲突的处理方法：

1、开放定址法(再散列法)：线性探测再散列、二次探测再散列；

2、再哈希法：同时构造多个不同的哈希函数，当哈希地址发生冲突时，再用其他哈希函数来计算地址，直到冲突不再产生。

3、链地址法：将所有哈希地址为i的元素构成一个单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在这个链中进行。4、建立公共溢出区法：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

第六部分排序与查找

哈希表装填因子：哈希法中影响关键字比较次数的因素有三个：哈希函数、处理冲突的方法以及哈希表的装填因子。哈希表的装填因子α的定义如下：α可描述哈希表的装满程度。α越小，发生冲突的可能性越小；α越大，发生冲突的可能性也越大。第六部分排序与查找

α＝哈希表中元素个数哈希表的长度基本概念内部排序：整个排序过程完全在内存中进行，称为内部排序。外部排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。排序的稳定性：相同关键字的相对位置关系在排序过程中没有发生变化者，则称所用的排序方法是稳定的；反之，则称为不稳定的。第六部分排序与查找

插入类排序直接插入排序：每次将一个待排序的记录按其关键码的大小插入到一个已经排好序的有序序列中，直到全部记录排好序为止。折半插入排序：以折半查找和直接插入排序两种方法结合起来实现排序；希尔排序：根据不同的间距di将元素分成组，在各组内进行直接插入排序，di的值是由大到小，最后为1，即将所有元素放在一组里进行排序第六部分排序与查找

第六部分排序与查找

直接插入4674165314264038866527341467416531426403886652734216467453142640388665273431646537414264038866527344141646537426403886652734514162646537440388665273461416264046537438866527347141626384046537486652734814162638404653748665273491416263840465365748627341014162627384046536574863411141626273438404653657486希尔排序467416531426403886652734126341653142740388665467422614164034275338746546863141626273438404653657486交换类排序冒泡排序：快速排序：第六部分排序与查找

快速排序4674165314264038866527341342716381426404686655374226271614343840467465538631416262734384046536574864141626273438404653657486选择类排序：简单选择排序、堆排序第六部分排序与查找

简单选择4674165314264038866527341147416534626403886652734214167453462640388665273431416265346744038866527344141626274674403886655334514162627347440388665534661416262734384074866553467141626273438407486655346814162627343840468665537491416262734384046536586741014162627343840465365867411141626273438404653657486演示归并排序基本思想：将两个或两个以上有序表合并成一个新的有序表。假设初始序列含有n个记录，首先将这n个记录看成n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2个长度为2的有序子序列；在此基础上，再进行两两归并，如此重复，直至得到一个长度为n的有序序列为止。第六部分排序与查找

(19)(13)(05)(27)(01)(26)(31)(16)

(13,19)(05,27)(01,26)(16,31)

(05,13,19,27)(01,16,26,31)

(01,05,13,16,19,26,27,31)分配类排序基本思想：设待排序的数据元素关键字是m位d进制整数（不足m位的关键字在高位补0），设置d个桶，分别编号为0,1,2,…,d-1。1、首先按关键字最低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；

2、再对一次基数排序得到的序列按关键字次低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。第六部分排序与查找

分配类排序基本思想：设待排序的数据元素关键字是m位d进制整数（不足m位的关键字在高位补0），设置d个桶，分别编号为0,1,2,…,d-1。1、首先按关键字最低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；

2、再对一次基数排序得到的序列按关键字次低位的数值依次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。第六部分排序与查找

数据元素的关键字序列为{710,342,045,686,006,841,429,134,068,264}8411342231342644045568600667068871004299放置7101429213438413420454526406867686800609006710429134841342045264068686收集后的新序列:放置1341264234234294568667107841800604506809006045068134264342429686710841收集后的新序列:放置710841342134264045686006068429收集后的新序列:(a)第一趟基数排序

(b)第二趟基数排序

(c)第三趟基数排序排序方法最好情况平均时间最坏情况稳定性直接插入O(n)O(n2)O(n2)√简单选择O(n2)O(n2)O(n2)√冒泡O(n)O(n2)O(n2)√快速O(nlog2n)O(nlog2n)O(n2)×堆排序O(nlog2n)O(nlog2n)O(nlog2n)×归并O(nlog2n)O(nlog2n)O(nlog2n)√基数O(d(n+rd))O(d(n+rd))O(d(n+rd))√第六部分排序与查找

各种排序方法性