当前位置:首页 >> 政史地 >> 软考辅导——数据结构与算法

软考辅导——数据结构与算法


L/O/G/O 软考辅导

数据结构与算法

主要内容

考点分析

数据结构与算法概述
数据结构知识点复习 算法知识点复习 模拟练习

考点分析
常用数据结构:57%
?数据结构基础与线性表:7 ?树和二叉树:14 ?图:11

/>数据结构与 算法基础

算法基础:43%
?算法的描述与分析 ?常用数值计算算法 ?常用非数值计算算法 ?排序算法 ?查找算法

数据结构与算法概述
?数据结构的概念: 数据结构: (Data Structure) 数据结构是带―结构‖的数 据元素的集合。―结构‖即指 数据元素之间存在的联系。 所以数据结构又可以定义为有联系的数据元素的集合。 ?数据结构研究的内容: 数据结构主要研究几种常用的数据结构的逻辑特点、 存储结构的实现、常用的操作的具体实现方法、各种 结构的具体应用等问题。 ?数据结构的主要逻辑结构 线性结构:线性表、栈、队列、数组、广义表 非线性结构:树、图 ?算法 常用的排序算法、查找算法、数值计算、字符串处理、 数据压缩算法、递归算法、图的相关算法

第一部分 线性表
?分值:0 ~ 1分 (每年) ?分数比重:0% ~ 10% ?重要知识点: 1、顺序表的结构特点 2、单链表的结构特点 3、双向链表的插入删除 4、循环链表的结构特点

第一部分 线性表
?顺序表

?特点: 利用物理存储位臵的相邻关系反应元素之间的次序关系 ?优点: 1.无需为表示结点间的逻辑关系而增加额外的存储空间; 2.可方便地随机存取表中的任一元素。 ?缺点: 1.插入或删除运算不方便,需要移动大量的结点,其效率较低; 2.需要预先确定顺序表的最大表长,由于顺序表要求占用连续的存储 空间,存储分配只能预先进行静态分配。因此当表长变化较大时, 难以确定合适的存储规模。

第一部分 线性表
?单链表
物理状态 逻辑状态 list a2 d2 d1 a1 d2 a2 d3

a1
d1

d
2

a4 d4 d4 a4 ∧



a3 d3

d4 …

d3 a3

?优点: 1.链表动态存储分配的结构,能有效利用存储空间;。 2. 插入或删除时只需要修改指针,而不需要进行大量元素的移动。 ?缺点: 1.必需为表示结点间的逻辑关系而增加额外的存储空间; 2.不能随机存取、访问数据元素。

?特点:单链表中逻 辑上相邻的数据元素 在物理上不一定相邻。 数据元素之间的逻辑 关系通过链指针间接 地反映出来。

第一部分 线性表
?双向链表
?特点:双向链表中查找某结点的直接前驱结点和直接后继结点的运算的 时间复杂度均为O(1) ?插 入 a : ② ① p b … ③ ① s->prior = p->prior; ② p->prior->next = s; ③ s->next = p; ④ p->prior = s;




e

s
?删除: ①

p b ② c … ① p->prior->next = p->next; ② p->next->prior = p->prior;



a

第一部分 线性表
?循环链表
?循环链表(Circular Linked List):链表中最后一个结点的指针域指向整 个链表的头结点,从而使链表形成一个首尾相接的环形链表。 ?特点:从链表尾部到链表头部比较方便。从表中任一结点出发均可找到 表中其它结点。
?判空:

L

L->next= = L;

?表尾判断: L
?采用尾指针的循环单链表

a1



an

p->next == L;

rear a1



ai-1

ai



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. 需要频繁修改L中元素的值 B. 需要频繁地对L进行随机查找 C. 需要频繁地对L进行删除和插入操作 D. 要求L存储密度高

第一部分 线性表
?真题
?2009.11 ● 单向链表中往往含有一个头结点,该结点不存储数据元素,一般 令链表的头指针指向该结点,而该结点指针域的值为第一个元素结 点的指针。以下关于单链表头结点的叙述中,错误的是(60)。 (60)A.若在头结点中存入链表长度值,则求链表长度运算的时间 复杂度为O(1) B.在链表的任何一个元素前后进行插入和删除操作可用一致 的方式进行处理 C.加入头结点后,代表链表的头指针不因为链表为空而改变 D.加入头结点后,在链表中进行查找运算的时间复杂度为 O(1)

第二部分 栈、队列和字符串
?分值:0 ~ 1分 (每年) ?分数比重:0% ~ 10% ?重要知识点: 1、栈的结构特点 2、队列的结构特点 3、双端队列与循环队列 4、串的存储结构、基本操作和模式匹配

第二部分 栈、队列和字符串
?栈
?概念: 在一端进行插入和删除操作的线性表。 栈顶:允许插入和删除的一端。 栈底:不允许插入和删除的一端。
出栈 栈顶元素 入栈 an an-1 … a3

?特点: a2 后进先出的线性表 栈底元素 a1 ?双向栈: 使两个栈共享一维数组S[MAXNUM],利用栈的“栈底位臵不变, 栈顶位臵动态变化”的特性,将两个栈底分别设为0 和 MAXNUM-1,而 它们的栈顶都往中间方向延伸的栈称为双向栈。
0 lefttop righttop MAXNUM-1

自由区

第二部分 栈、队列和字符串
?队列
?概念: 队列是只能在表的一端进行插入操作,在表的另 一端进行删除操作的线性表。 队尾(rear):允许插入的一端叫做队尾。

队头(front):允许删除的一端叫做队头。
?特点: 先进先出的线性表 入队列

出队列

a1

a2

a3 …

an-1

an

队头元素

队尾元素

第二部分 栈、队列和字符串
?循环队列
把顺序队列所使用的存储空间臆造成一个逻 辑上首尾相连的循环队列。 ?特点: 5 6 7 rear 0

a6 a5
a4

1、循环队列只针对顺序队列而言
2、入队 rear=(rear+1)%MAXSIZE; 3、出队 front=(front+1)%MAXSIZE;

4

a3 a2
3 2

1 front

4、判队满: front==(rear+1)%MAXSIZE
5、判队空: rear==front 6、元素个数:(rear-front+MAXSIZE)%MAXSIZE

(采用少用一个存储单元的方法区分队空和队满)

第二部分 栈、队列和字符串
?双端队列
想象自己在邮局里排队,当最终轮到自己时,邮局工作人员要求填 写一张表格,于是自己站在旁边填表,工作人员为队列中下一个人服务. 在填表后,工作人员将继续为自己服务,实质上自己又回到了队列的前 端.有时可能会排在一个队列后面,随即因嫌队伍太长而离去. 端1
a0 a1 a2 ai an-1 端2

?分类: 1、 输出受限的双端队列(即一个端点允许插入和删除,另一个端点只 允许插入); 2、 输入受限的双端队列(即一个端点允许插入和删除,另一个端点只 允许删除)。 3、限定双端队列从某个端点插入的元素只能从该端点删除,则双端队 列就蜕变为两个栈底相邻接的栈了。

第二部分 栈、队列和字符串
?串的存储结构
(1)定长顺序串:按照预定义的大小,为每个定义的串变量分配一 个固定长度的存储区 (2)堆串:可用函数malloc()和函数free()完成动态存储管 (3)块链串:用链表存储时,通常一个结点中存放的不是一个字符, 而是一个子串。 例:串值为"abcdef"的结点大小为4的链串 S

a b c d

e

f # # ∧

块链串注意事项: ①为了提高存储密度,可使每个结点存放多个字符。 ②当结点大小大于1时,串的长度不一定正好是结点大小的整数倍, 因此要用特殊字符来填充最后一个结点,以表示串的终结。 ③会给串的连接操作带来一定的方便,对模式匹配操作不方便。 ④虽然提高结点的大小使得存储密度增大,,但是做插入、删除运 算时,可能会引起大量字符的移动,给运算带来不便。

第二部分 栈、队列和字符串
?串的基本操作——难掌握的部分
(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数组:

j T串 next[j] nextval[j]

1 2 3 4 5 6 7 8 9 10 a b a c a b a a a d 0 1 1 2 1 2 3 4 2 2 0 1 0 2 0 1 0 4 2 2

第二部分 栈、队列和字符串
?真题 ?200705 ●输入受限的双端队列是指元素只能从队列的一端输入、 但可以从队列的两端输出,如下图所示。若有 8、1、4、 2 依次进入输入受限的双端队列,则得不到输出序列 (57)。

(57) A. 2、8、1、4 C. 4、2、1、8

B. 1、4、8、2 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、e C. c、d、b、a、e (59)A. 2 B. 3 C. 4

B. e、d、c、b、a D. e、a、b、d、c D. 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)

第二部分 栈、队列和字符串
?真题 ?200911 ● 字符串采用链表存储方式时,每个结点存储多个 字符有助于提高存储密度。若采用结点大小相同的链 表存储串,则串比较、求子串、串连接、串替换等串 的基本运算中,(62)。

(62)A.进行串的比较运算最不方便 B.进行求子串运算最不方便 C.进行串连接最不方便 D.进行串替换最不方便

第三部分 数组与广义表
?分值:0 ~ 1分 (每年) ?分数比重:0% ~ 10% ?重要知识点: 1、数组的地址计算 2、数组的压缩存储 3、广义表的表示 4、广义表的表头、表尾

第三部分 数组与广义表
?数组
多维数组和广义表是对线性表的扩展——线性表中的 数据元素本身又是一个多层次的线性表。 ?特点: 1.数组中的数据元素具有相同的数据类型。 2.数组是一种随机存取结构,只要给定一组下标,就可以访问与 其对应的数组元素。 3.数组中的元素个数是固定的。

?基本操作——存取、修改 对于数组A,一旦给定其维数 n 及各维长度bi(1≤i≤n),则该数 组中元素的个数和元素之间的关系就不再发生变化了,既不可以对 数组做插入和删除操作,也不涉及移动元素操作。

第三部分 数组与广义表
?数组的地址计算 a00 a02 a03 a0j a10 a11 a12 a1j a20 a21 a22 a2j …… ai,0 ai,1 … … aij …… am-1,0 am-1,1 am-1,2 … … a0,n-1 … a1,n-1 … a2,n-1 ……

A[m][n] =

… am-1,n-1

行序为主序: Loc[aij] = Loc[a00] + ( n ? i + j ) ? size 列序为主序: Loc[aij] = Loc[a00] + ( m ? j + i )? size

第三部分 数组与广义表
?数组的压缩存储
对称矩阵:aij=aji a11 a12 a13 … … a21 a22 a23 … … a31 a32 a33 … … A= …… …… an1 an2 an3 … … a22
3

a1n a2n a3n ann ann
n*(n+1)/2

a11
Loc[i , j]= 1

a21
2

... ...
... ...

aij

... ...

对于对称矩阵,因其元素满足aij=aji,我们可以为每一对相等的 元素分配一个存储空间,即只存下三角(或上三角)矩阵,从而将 n2个元素压缩到n(n+1)/2个空间中。 Loc[ i , j ]=

{ Loc[1,1] + j?(j-1)/2 + i -1

Loc[1,1] + i?(i-1)/2 + j -1 当i≥j时 当i < j时
? j ? (j ? 1)/2 ? i ? 1, i ? j k?? ?i ? (i ? 1)/2 ? j ? 1, i ? j

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

第三部分 数组与广义表
?数组的压缩存储
带状矩阵:在矩阵A中,所有的非零元素都集中在以主对角线为中心的带状 区域中。最常见的是三对角带状矩阵。
a11 a12 a21 a22 a23 a33 a43 a34 a44 a45 … … …

0元素

An×n =

a32

0元素
特点:

ann-1 ann



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

第三部分 数组与广义表
?数组的压缩存储
1. 确定存储该矩阵所需的一维向量空间的大小: 三对角带状矩阵中除第一行和最后一行只有两个元素外,其余各 行均有3个非零元素。由此可得到一维向量所需的空间大小为:3n-2。 j-i aij在第i 行中的位臵 第i 行中aij前面非零元素个数 -1 1 0 0 2 1 1 3 2

2. 确定非零元素在一维数组空间中的位置: Loc[i , j] = Loc[1,1]+3×( i-1 )-1+j-i+1= Loc[1,1]+2( i-1 )+j-1

3. 矩阵中元素aij 在一维数组A中对应的下标为:
k=2(i-1)+j-1 ( 1≤i , j≤n,| i - j |≤1)

第三部分 数组与广义表
?数组的压缩存储
该非零元 素所在的 行号 该非零元 素所在的 列号 row data[0] data[1] data[2] data[3] data[4] data[5] data[6] data[7] data[8] col

该非零元 素的值

稀疏矩阵:三元组存储 十字链表

value

0 12 9 0 0 0 0 0 0 0 0 0 0 0 M6×7=

1 1 3

2 3 1

12 9 -3 14 24 18 15 -7

-3 0 0 0 0 14 0
0 0 24 0 0 0 0 0 18 0 0 0 0 0

3
4 5 6 6

6 3 2
1 4

15 0 0 -7 0 0 0

第三部分 数组与广义表
?数组的压缩存储
稀疏矩阵: 十字链表

-3 0 0 5 0 -1 0 0 8 0 0 7
1 1 3 2 2 -1 ^ ^ 31 8 ^

^ 1 4 5 ^

3 4 7 ^ ^

第三部分 数组与广义表
?广义表的表示
1、A = ( ) 2、B = ( e ) 表示广义表A是一个空表,其长度为0 表示广义表B长度为1,只有一个原子项e

3、C = ( a, ( b , c , d ) )

表示广义表C长度为2,两个元素分别为原子项a 和子表(b , c , d)。
4、D = ( A , A , ( ) ) 表示广义表D长度为3,三个元素都是广义表,分别为A、A 和( )。

5、E = ( A , B , C )
表示广义表E长度为3,三个元素A、B、C都是广义表,代入值以后 E=( ( ) , (e) , ( a, ( b , c , d ) ) )。 6、F = ( a , F ) 表示广义表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 ) = E Head( E ) = a Head( ( b, c) ) = b Head( ( c ) ) = c Tail( D ) = ( F ) Tail( E ) = ( ( b, c) ) Tail( ( b, c) ) = ( c ) Tail( ( c ) ) = ( )

Head( (( b, c)) ) = ( b, c) Tail( (( b, 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)/2 B.n2/2 C.(n-1)(n+1)/2 D.n(n-1)/2 ( 41)A.18 B.19 C.20 D.21

? 解析:具有n个结点的简单无向图的邻接矩阵是对称矩阵。 对称矩阵关于主对角线对称,因此只需存储上三角或下三 角部分即可。比如,我们只存储上三角中的元素aij,其特 点是j≤i且1≤i≤n,对于上三角中的元素aij,它和对应的aij 相等,因此当访问的元素在上三角时,直接去访问和它对 应的下三角元素即可。这样,原米需要n*n个存储单元, 现在只需要n(n+1)/2个存储单元了,由于简单无向图中没 有自环,因此主对角线的元素无须存储,因此至少需要 n(n-1)/2个存储单元。若按行压缩存储对称矩阵的上三角 元素,则第1行需存储n-1个元素,第二行存储n-2个元素, 第i行需存储n-i个元素,元素aij(1≤i≤n-1且i<j≤n)存储在 B[(i-1)n-i(i-1)/2+j-i]中,当n为10,与边(V6,V3)对应的矩阵 元素为a3.6,即其信息存储在B[20]中。

第三部分 数组与广义表
?真题 ?200611 ● 对于二维数组 a[0..4,1..5],设每个元素占 1 个存储单元, 且以列为主序存储,则元素 a[2,2]相对于数组空间起始地 址的偏移量是 (55)。 (55)A. 5 B. 7 C. 10 D. 15

?200812 ● 广义表中的元素可以是原子,也可以是表,因此广义 表的适用存储结构是(61)。 (61)A. 链表 B. 静态数组 C. 动态数组 D. 散列表

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

?200905 ● 设 L 为广义表,将 head(L)定义为取非空广义表的第一 个元素,tail(L)定义为取非空广义表除第一个元素外剩余 元素构成的广义表。若广义表L=((x,y,z),a,(u,t,w)),则从L 中取出原子项y的运算是 (62) (62) A. head(tail(tail(L))) C. head(tail(head(L))) B. tail(head(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

第四部分 树与二叉树
?二叉树的遍历
A B D J K F I
E

C H

前序遍历序列: 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

G

第四部分 树与二叉树
例:已知结点的先序序列和中序序列 先序序列:A B D E J C F I G 中序序列:D B J E A F I C G 则可按上述分解求得整棵二叉树。 例:已知结点的中序序列和后序序列 中序序列:A B C E F G H D 后序序列:A B F H G E D C 则可按上述分解求得整棵二叉树。
C B A D

A
B D J E C

E
G

F I

G

F

H

第四部分 树与二叉树
?线索二叉树 一.什么是线索二叉树

利用二叉链表中空的指针域指出结点在遍历序列 中的直接前驱和直接后继;这些指向前驱和后继的指针 称为线索, 加了线索的二叉树称为线索二叉树.
二.线索二叉树的构造

利用结点的空的左指针域存放该结点的直接前驱的地 址,空的右指针域存放该结点直接后继的地址; 而非空的 指针域仍然存放结点的左孩子或右孩子的地址.
注:每棵二叉树都可以构造先序、中序和后序三种线索二叉树。

第四部分 树与二叉树
?树、森林与二叉树的转换
?树转换成二叉树: 1、树中所有相邻兄弟之间加一条连线。 2、对树中的每个结点,只保留其与第一个 孩子结点之间的连线,删去其与其它孩子结 点之间的连线。 ?森林转换为二叉树的方法为: 1、将森林中的每棵树转换成相应的二叉树。 2、第一棵二叉树不动,从第二棵二叉树开 始,依次把后一棵二叉树的根结点作为前一 棵二叉树根结点的右孩子,当所有二叉树连 B 在一起后,即为由森林转换得到的二叉树。 A C D E G H I E A

B
F

C
G H

D

F

J

第四部分 树与二叉树
?哈夫曼树

?带权路径长度:
设二叉树有n个带权值的叶子结点,定 义从二叉树的根结点到二叉树中所有叶子 结点的路径长度li与相应叶子结点权值wi的 乘积之和称作该二叉树的带权路径长度。 T

A C E
5

B F

WPL =

? w ?l
i ?1 i

n

D
7

G
9

i

H
2

I
4

WPL(T) =7?2+5?2+2?3+4?3+9?2 = 60

第四部分 树与二叉树
?哈夫曼编码

字符:
字符出现的次数:

s t a e c
3 8 7 5 2

25
0 1

c: 010 s: 011

10
0 1

15

1 0 5 8 7 5 1 (10) (11) (00) 0 2 3 (010) (011)

e: 00
a: 10

t: 11

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

第四部分 树与二叉树
?真题
?200511
●已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA,则该二 叉树的后序序列为___(38)___。

(38) A. BCDEAF

B. ABDCEF

C. DBACEF

D. DABECF

●在二叉树的顺序存储中,每个结点的存储位臵与其父结点、左右子树 结点的位臵都存在一个简单的映射关系,因此可与三叉链表对应。若某

二叉树共有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)采
用三叉链表存储二叉树时,每个结点需要占用d+4*3个字节,n个结点则需要 n(d+12)。若顺序存储最后一个结点的下标为k,则共需kd个字节。显然,

第四部分 树与二叉树
?真题
?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/-×= C. XAB+CDE-/×= ?200705 ●已知某二叉树的中序序列为 CBDAEFI、先序序列为 ABCDEFI,则该二叉树的高度为(58)。 (58)A. 2 B. 3 C. 4 D. 5 B. XAB+C-DE /×= D. XAB+CD-E/×=

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

第四部分 树与二叉树
?真题
?200805

● 若将某有序树 T 转换为二叉树 T1,则 T 中结点的后(根)序序列就 是 T1 中结点的 __(59)__ 遍历序列。例如,下图(a)所示的有序树转化 为二叉树后如图(b)所示。

(59) A. 先序

B. 中序

C. 后序

D. 层序

第四部分 树与二叉树
?真题
?200811 ● 一个具有m个结点的二叉树,其二叉链表结点(左、右孩子指针分 别用left和right表示)中的空指针总数必定为 (57) 个。为形成中序 (先序、后序)线索二叉树,现对该二叉链表所有结点进行如下操作: 若结点p的左孩子指针为空,则将该左指针改为指向p在中序(先序、 后序)遍历序列的前驱结点;若 p 的右孩子指针为空,则将该右指针 改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指 向中序(先序、后序)线索二叉树中的某结点,则(58)。

(57)A. m+2

B. m+1

C. m

D. m-1

(58)A. s->right指向的结点一定是s所指结点的直接后继结点 B. s->left指向的结点一定是s所指结点的直接前驱结点

C. 从s所指结点出发的right链可能构成环
D. s所指结点的left和right指针一定指向不同的结点

第四部分 树与二叉树
?真题 ?200905 ●下面关于二叉树的叙述,正确的是 (61) 。 (61)A. 完全二叉树的高度h与其结点数n之间存在确定 的关系 B. 在二叉树的顺序存储和链式存储结构中,完全

二叉树更适合采用链式存储结构
C. 完全二叉树中一定不存在度为1的结点 D. 完全二叉树中必定有偶数个叶子结点

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

第五部分 图
?分值:0 ~ 5分 (每年)

?分数比重:6%
?重要知识点:

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

3、拓扑排序和最小生成树
4、关键路径

5、最短路径

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

A

G1

B

A

G2

B

C
C D D E

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

v5 v2 v4 v9 v7

v1 v3 A C B

v8
v6

E

D

v1 v2 v4 v7 v9 v 5 v3 v6 v8 v1 v2 v3 v4 v5 v9 v 6 v8 v7

ABC D E ABCED

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

C1 C4 C7 拓扑序列:

C2
C6

C 1 , C 2 , C 3 , C 4 , C5 , C 6 , C 7

第五部分 图
?最小生成树
?概念 生成树是连通图上的一个极小连通子图。最小生成树是一个连通 网中所有生成树中各边权值之和最小的生成树。 ?最小生成树的算法: 1、普里姆算法 2、克鲁斯卡尔算法

6

a
1 5 6

a 5 b 3 e

a d 4 f 2 b 3 e 5 1 c 5 4 f

b
3

c
6

5
4

5

1 c

5 d 2

d
2

e

f

第五部分 图
?关键路径
?概念 从源点到汇点的最长路径的长度即为完成整个工程任务所需的时 间,该路径叫做关键路径。关键路径上的活动叫关键活动。 ?关键路径的求法: ⑴ 事件的最早发生时间 ve[k] ⑵ 事件的最迟发生时间 vl[k] ⑶ 活动的最早开始时间 e[i] ⑷ 活动的最晚开始时间 l[i]

v2 a4=1 a1=6 v1
a2=4

v5 v3 a5=1

a7=9
a8=7

v7

a10=2
v9

a3=5

v8 a11=4
a9=4

v4 a6=2 v6

第五部分 图
v2 a4=1 a1=6 v1
a2=4

v5
v3 a5=1

a7=9
a8=7

v7

a10=2
v9

a3=5

v8 a11=4 a9=4
v5 7 v6 v7 v8 14 v9 18

v4 a6=2 v6
v1 v2 6 v3 4 v4 5

ve[k]

0

7 a7
7

16 a8
7

a1 e[i]
0

a2
0

a3 0

a4 6

a5
4

a6
5

a9
7

a10

a11
14

16

第五部分 图
v2 a4=1
a1=6 v1 a2=4

v5
v3 a5=1

a7=9
a8=7

v7

a10=2
v9

a3=5
v1

v8 a11=4 a9=4
v5 v6 v7 v8 v9

v4 a6=2 v6
v2 v3 v4

vl[k]
l[i]

0 a1 0

6 a2
2

6 a3
3

8 a4
6

7 10 16 14 18 a5 a6 a7 a8 a9 a10 a11
6 8 7 7 10 16 14

第五部分 图
?最短路径
?分类 1、求图中的一个结点到其他结点的最短路径。 2、求图中任意两点间的最短路径。 ?最短路径的求法: ⑴ 迪杰斯特拉(Dijkstra)算法 ⑵ Floyd算法 B B 50

10
A 30 100 E 60 10

10 C
20 S={A, B, D, C, E} A→B:(A, B)10 A→C:(A, D, C)50 A→D: (A, D)30 A→E: (A, D, C, E)60 A 30 100 E 60 10

50

C
20 D

D

第五部分 图
?最短路径
?分类 1、求图中的一个结点到其他结点的最短路径。 2、求图中任意两点间的最短路径。 ?最短路径的求法: ⑴ 迪杰斯特拉(Dijkstra)算法 ⑵ Floyd算法

5 6

a
8 2 3

3

b
1

d c
2

第五部分 图
?真题 ?200505

●无向图中一个顶点的度是指图中___(41)___。 (41) A.通过该顶点的简单路径数 B.通过该顶点的回路数 C.与该顶点相邻的顶点数 D.与该顶点连通的顶点数 ●一个具有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)/2 C.(n-1)(n+1)/2 B. n2/2 D.n(n-1)/2

(41) A. 18

B. 19

C. 20

D. 21

第五部分 图
?真题 ?200605

● 拓扑序列是无环有向图中所有项点的一个线性序列, 图中任意路径中的各个顶点在该图的拓扑序列中保持先 后关系,(52)为下图所示有向图的一个拓扑序列。

(52)A.1 2 3 4 5 6 7 C.5 1 2 6 3 4 7

B.1 5 2 6 3 7 4 D.5 1 2 3 7 6 4

第五部分 图
?真题

?200611

● 求单源点最短路径的迪杰斯特拉(Dijkstra)算法 是按 (57) 的顺序求源点到各顶点的最短路径的。 (57)A. 路径长度递减
C. 顶点编号递减

B. 路径长度递增
D. 顶点编号递增

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

第五部分 图
?真题
?200711 ● 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程,若 在有向图中从顶点vi到vj有一条路径,则在该线性序列中,顶点vi必 然在顶点vj之前。因此,若不能得到全部顶点的拓扑排序序列,则说 明该有向图一定(57) 。

(57)A. 包含回路
?200805

B. 是强连通图 C. 是完全图 D. 是有向树

● 设一个包含N个顶点、 E条边的简单有向图采用邻接矩阵存储结 构(矩阵元素A[i][j]等于1/0分别表示顶点i与顶点j之间有/无弧),则该 矩阵的元素数目为 __(60)__ ,其中非零元素数目为 __(61)__ 。 (60)A. E2 (61)A. N B. N2 B. N+E C. N2 -E2 C. E D. N2+E2 D. 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. 连通无向网的最小生成树中,顶点数恰好比边 数多1

B. 若有向图是强连通的,则其边数至少是顶点数
的2倍 C. 可以采用AOV 网估算工程的工期

D. 关键路径是AOE 网中源点至汇点的最短路径

第五部分 图
?真题 ?200911 ● 邻接矩阵和邻接表是图(网)的两种基本存储结构,对于具 有n个顶点、e条边的图,(59)。 (59)A.进行深度优先遍历运算所消耗的时间与采用哪一种 存储结构无关 B.进行广度优先遍历运算所消耗的时间与采用哪一种 存储结构无关 C.采用邻接表表示图时,查找所有顶点的邻接顶点的 时间复杂度为O(n*e) D.采用邻接矩阵表示图时,查找所有顶点的邻接顶点 的时间复杂度为O(n2)

第六部分 排序与查找
?分值:5 ~ 15分 (每年)
?分数比重:10% ?重要知识点: 1、静态表查找——顺序查找、折半查找 2、动态表查找——二叉排序树、平衡二叉树

3、哈希表
4、插入类排序 5、交换类排序

6、选择类排序
7、分配类排序

第六部分 排序与查找
?查找
?基本概念:

静态查找 :不涉及插入和删除操作的查找 。
动态查找 :涉及插入和删除操作的查找。 平均查找长度:将查找算法进行的关键码的比较次数的数学期望 值定义为平均查找长度。计算公式为:

其中:n :问题规模,查找集合中的记录个数; pi :查找第i个记录的概率; ci :查找第i个记录所需的关键码的比较次数。

第六部分 排序与查找
?静态查找
?顺序查找:从线性表的一端向另一端逐个将关键码与给定值进行比较, 若相等,则查找成功,给出该记录在表中的位臵;若整个表检测完仍未 找到与给定值相等的关键码,则查找失败,给出失败信息。

?折半查找:在有序表中,取中间元素作为比较对象
1、若给定值与中间记录的关键字相等,则查找成功; 2、若给定值小于中间记录的关键字,则在中间记录的左半区继续查找;

若给定值大于中间记录的关键字,则在中间记录的右半区继续查找。
3、不断重复上述过程,直到查找成功,或所查找的区域无记录 (low>high),查找失败。

前提:线性表中的记录必须按关键字有序;必须采用顺序存储。

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

第六部分 排序与查找
?动态查找——二叉排序树 练习:关键字的输入顺序为:45, 24 , 53 , 12 , 28 , 90,和 24, 53, 90, 12, 28, 45 ,分别构造二叉排序树
?结论:对同样一组数据元素,如果输入的顺序不同,则所建的二叉树

形态也不同。
?特点: 1、一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;

2、每次插入的新结点都是二叉排序树上新的叶子结点;
3、找到插入位臵后,不必移动其它结点,仅需修改某个结点的指针; 4、在左子树/右子树的查找过程与在整棵树上查找过程相同; 5、新插入的结点没有破坏原有结点之间的关系。

第六部分 排序与查找
?动态查找——二叉排序树的删除 ?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,即将 所有元素放在一组里进行排序

第六部分 排序与查找
直接插入 1 2 3 4 5 6 7 8 9 10 11 希尔排序 1 2 3 46 46 16 16 14 14 14 14 14 14 14 14 46 26 26 14 74 74 46 46 16 16 16 16 16 16 16 16 74 34 14 16 16 16 74 53 46 26 26 26 26 26 26 26 16 16 16 26 53 53 53 74 53 46 40 38 38 38 27 27 53 53 40 27 14 14 14 14 74 53 46 40 40 40 38 34 14 14 34 34 26 26 26 26 26 74 53 46 46 46 40 38 26 27 27 38 40 40 40 40 40 40 74 53 53 53 46 40 40 40 53 40 38 38 38 38 38 38 38 74 74 65 53 46 38 38 38 46 86 86 86 86 86 86 86 86 86 74 65 53 86 86 74 53 65 65 65 65 65 65 65 65 65 86 74 65 65 65 65 65 27 27 27 27 27 27 27 27 27 27 86 74 27 46 46 74 34 34 34 34 34 34 34 34 34 34 34 86 34 74 86 86

第六部分 排序与查找
? 交换类排序 ?冒泡排序: ?快速排序:

快速排序 1 2 3

46 34 26 14

74 27 27 16

16 16 16 26

53 38 14 27

14 14 34 34

26 26 38 38

40 40 40 40

38 46 46 46

86 86 74 53

65 65 65 65

27 53 53 74

34 74 86 86

4

14

16

26

27

34

38

40

46

53

65

74

86

第六部分 排序与查找
? 选择类排序 :简单选择排序、堆排序
简单选择 46 74 16 53 14 26 40 38 86

演示
65 27 34

1
2 3 4 5 6 7

14
14 14 14 14 14 14

74
16 16 16 16 16 16

16
74 26 26 26 26 26

53
53 53 27 27 27 27

46
46 46 46 34 34 34

26
26 74 74 74 38 38

40
40 40 40 40 40 40

38
38 38 38 38 74 74

86
86 86 86 86 86 86

65
65 65 65 65 65 65

27
27 27 53 53 53 53

34
34 34 34 46 46 46

8
9 10 11

14
14 14 14

16
16 16 16

26
26 26 26

27
27 27 27

34
34 34 34

38
38 38 38

40
40 40 40

46
46 46 46

86
53 53 53

65
65 65 65

53
86 86 74

74
74 74 86

第六部分 排序与查找
?归并排序
?基本思想:将两个或两个以上有序表合并成一个新的有序表。假设初
始序列含有n个记录,首先将这n个记录看成n个有序的子序列,每个 子序列的长度为1,然后两两归并,得到 ? n/2?个长度为2的有序子

序列;在此基础上,再进行两两归并,如此重复,直至得到一个长度
为n的有序序列为止。

(19)

(13)

(05)

(27)

(01)

(26)

(31)

(16)

(13,19) (05,13,19,27)

(05,27)

(01,26)

(16,31)

(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}

放臵

710 0

841 1 710

342 2 841 342

3
134

264 134 4 264 045

045 5 686

006 686 6 006 068

7
429

068 8

429 9

收集后的新序列:

(a)第一趟基数排序

放臵

006 0

710 1
006

429 2
710 429

134 3
134

045 342 841 4 841 342

5 045

068 264 6
264 068

7 686

686 8

9

收集后的新序列:

(b)第二趟基数排序 068 045 006 0

放臵

134 1 006

264 2 045 068

342 3 134

429 4 264 342

5 429

686 6 686 710

710 7 841

841 8

9

收集后的新序列:

(c)第三趟基数排序

第六部分 排序与查找
?各种排序方法性能比较
排序方法 直接插入 简单选择 最好情况 平均时间 最坏情况 稳定性

O(n) O(n2)

O(n2) O(n2)

O(n2) O(n2)

冒泡
快速 堆排序 归并 基数

O(n)
O(nlog2n) O(nlog2n) O(nlog2n)

O(n2)
O(nlog2n) O(nlog2n) O(nlog2n)

O(n2)
O(n2) O(nlog2n) O(nlog2n)

O(d(n+rd)) O(d(n+rd)) O(d(n+rd))

√ X √ × × √ √

第六部分 排序与查找
?真题
?200505 ● 利用逐点插入建立序列(50,72,43,,85,75,20,35,45,65,30)对应的二叉 排序树以后,查找元素30要进行_____(42)____次元素间的比较。

(42)A. 4

B.5

C. 6

D.7

●在常用的描述二叉排序树的存储结构中,关键字值最大的结点 ___(48)____。

(48)A.左指针一定为空
B.左右指针均为空

B.右指针一定为空
D.左右指针均不为空

●以比较为基础的排序算法在最坏情况下的计算时间下界为__(55)___。

(55)A.O(n)

B.O(n2)

C.O(log2n)

D.O(nlog2n)

第六部分 排序与查找
?真题
?200511

●在11个元素的有序表A[1..11]中进行折半查找( )查找元素A[11]时, 被比较的元素的下标依次是___(44)___。
(44) A.6,8,10,11 B.6,9,10,11 C.6,7,9,11 D.6,8,9,11

●由元素序列(27,16,75,38,51)构造平衡二叉树,则首次出现的最小不 平衡子树的根(即离插入结点最近且平衡因子的绝对值为2的结点)为 ____(46)____。
(46) A.27 B.38 C.51 D.75

●若排序前后关键字相同的两个元素相对位臵不变,则称该排序方法 是稳定的。___(47)__排序是稳定的。 (47) A.归并 B.快速 C.希尔 D.堆

第六部分 排序与查找
?真题 ?200605 ● 在平衡二叉树中,(55) 。

(55)A.任意结点的左、右子树结点数目相同
B.任意结点的左、右子树高度相同 C.任意结点的左右子树高度之差的绝对值不大于1

D.不存在度为1的结点
● (60) 在其最好情况下的算法时间复杂度为O(n)。 (60)A.插入排序 C.快速排序 B.归并排序 D.堆排序

第六部分 排序与查找
?真题
?200611 ● 结点数目为 n 的二叉查找树(二叉排序树)的最小高度为 (52) 、 最大高度为(53)。 (52)A. n (53)A. n B. n/2 B. n/2 C. [log2n] C. [log2n] D. [log2(n+1)] D. 「log2(n+1) ?

● 对于n个元素的关键字序列{k1 , k 2 ,..., k n } ,当且仅当满足关系 称 其为小根堆,反之则为大根堆。以下序列中,(56) 不符合堆的定义。 56)A.(4,10,15,72,39,23,18) B.(58,27,36,12,8,23,9)

C.(4,10,18,72,39,23,15)

D.(58,36,27,12,8,23,9)

第六部分 排序与查找
?真题
?200705 ●下图所示平衡二叉树(树中任一结点的左右子树高度之差不超过 1)中,结点 A的右子树 AR 高度为 h,结点 B 的左子树 BL 高度为 h,结点 C 的左子树 CL、右子树 CR 高度都为 h-1。若在 CR 中插 入一个结点并使得 CR 的高度增加 1,则该二叉树 (61) 。 (61)A. 以 B 为根的子二叉树变为不平衡

B. 以 C 为根的子二叉树变为不平衡
C. 以 A 为根的子二叉树变为不平衡 D. 仍然是平衡二叉树
由于平衡二叉树中任一结点的左右子树高度之差不超过1,因此,若在CR中插入一个 结点并使得CR的高度增加1,则结点C的左右子树高度之差为-1,同时以C为根的子 树高度增加了1,所以结点B的左右子树高度之差变为-1。如此一来,A的左子树的高 度为h+2、右子树的高度为h,根据定义,以A为根的子二叉树变为不平衡。

第六部分 排序与查找
?真题
?200705

●对 n 个元素的数组进行 (63) ,其平均时间复杂度和最坏情况 下的时间复杂度都是 O(nlogn)。
(63)A. 希尔排序 ?200711 B. 快速排序 C. 堆排序 D. 选择排序

● 对于二叉查找树(Binary Search Tree),若其左子树非空,则左子 树上所有结点的值均小于根结点的值;若其右子树非空,则右子树上 所有结点的值均大于根结点的值;左、右子树本身就是两棵二叉查找 树。因此,对任意一棵二叉查找树进行 (61) 遍历可以得到一个结 点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算,最 坏情况下的算法复杂度为 (62) 。
(61) A. 先序 B. 中序 C. 后序 D. 层序

(62) A. O(n2) B.O(nlog2n)

C. O(log2n)

D. O(n)

第六部分 排序与查找
?真题
?200805 ● 若总是以待排序列的第一个元素作为基准元素进行快速排序,那么 最好情况下的时间复杂度为 c。

?200811 ● 将一个无序序列中的元素依次插入到一棵(60),并进行中序遍历, 可得到一个有序序列。 (60)A. 完全二叉树 B. 最小生成树 C. 二叉排序树 D. 最优二叉树 ● 某一维数组中依次存放了数据元素12,23,30,38,41,52,54,76,85,在用 折半(二分)查找方法(向上取整)查找元素54时,所经历“比较” 运算的数据元素依次为(62)。 (62)A. 41, 52, 54 B. 41, 76, 54 C. 41, 76, 52, 54 D. 41, 30, 76, 54

第六部分 排序与查找
?真题
?200905 ●下面关于查找运算及查找表的叙述,错误的是 (57) 。 (57)A. 哈希表可以动态创建 B. 二叉排序树属于动态查找表 C. 二分查找要求查找表采用顺序存储结构或循环链表结构 D. 顺序查找方法既适用于顺序存储结构,也适用于链表结构 ●下面关于二叉排序树的叙述,错误的是 (59) 。 (59)A. 对二叉排序树进行中序遍历,必定得到结点关键字的有序序列 B. 依据关键字无序的序列建立二叉排序树,也可能构造出单支树

C. 若构造二叉排序树时进行平衡化处理,则根结点的左子树结点
数与右子树结点数的差值一定不超过1 D. 若构造二叉排序树时进行平衡化处理,则根结点的左子树高度

与右子树高度的差值一定不超过1

第六部分 排序与查找
?真题
?200911

● 以下关于快速排序算法的描述中,错误的是(64)。在快速排序 过程中,需要设立基准元素并划分序列来进行排序。若序列由元素 {12,25,30,45,52,67,85}构成,则初始排列为(65)时,排序效率最 高(令序列的第一个元素为基准元素)。 (64)A.快速排序算法是不稳定的排序算法
B.快速排序算法在最坏情况下的时间复杂度为O(nlgn) C.快速排序算法是一种分治算法

D.当输入数据基本有序时,快速排序算法具有最坏情况下的
时间复杂度 (65)A.45,12,30,25,67,52,85 C.12,25,30,45,52,67,85 B.85,67,52,45,30,25,12 D.45,12,25,30,85,67,52

第七部分 算法
?分值:2 ~ 16分 (每年)

?分数比重:22%
?重要知识点:

1、时间复杂度
2、穷举法、迭代法、递推法、递归法、

分治法、动态规划法、回溯法、贪心法
分支限界法

第七部分 算法
? 蛮力法(穷举法)
?蛮力法(brute force method):也称穷举法(enumerate)法,是蛮力策 略的一种表现形式。它是根据问题中的条件将可能的情况一一列举 出来,逐一尝试从中找出满足问题条件的解。但有时一一列举出的 情况数目很大,如果超过了我们所能忍受的范围,则需要进一步考 虑,排除一些明显不合理的情况,尽可能减少问题可能解的列举数 目。 ?用蛮力法解决问题,通常从两个方面进行算法设计: 1、找出穷举范围:分析问题所涉及的各种情况。 2、找出约束条件:分析问题的解需要满足的条件,并用逻辑表 达式表示。 ?应用:顺序查找、简单选择排序、冒泡排序、0/1背包、哈密顿回路、 旅行家问题。最近点对和凸包问题。

第七部分 算法
? 迭代法
?蛮力法(brute force method):也称穷举法(enumerate)法,是蛮力策

略的一种表现形式。它是根据问题中的条件将可能的情况一一列举
应用:顺序查找、简单选择排序、冒泡排序

第七部分 算法
? 递推法
?蛮力法(brute force method):也称穷举法(enumerate)法,是蛮力策

略的一种表现形式。它是根据问题中的条件将可能的情况一一列举
应用:顺序查找、简单选择排序、冒泡排序

第七部分 算法
? 递归法
?蛮力法(brute force method):也称穷举法(enumerate)法,是蛮力策

略的一种表现形式。它是根据问题中的条件将可能的情况一一列举
应用:顺序查找、简单选择排序、冒泡排序

第七部分 算法
? 分治法
?思想:将一个难以直接解决的大问题,划分成一些规模较小的子问

题,以便各个击破,分而治之。
1、分解:将要求解的原问题划分成k个较小规模的子问题,对这 k个子问题分别求解。如果子问题的规模仍然不够小,则再将每个子

问题划分为k个规模更小的子问题,如此分解下去,直到问题规模足
够小,很容易求出其解为止; 2、合并:再将子问题的解合并为一个更大规模的问题的解,自底

向上逐步求出原问题的解。
?应用:大整数乘法、矩阵乘法、归并排序、快速排序、循环赛日程 安排、最近点对问题、凸包问题

第七部分 算法
? 动态规划法
?思想:在求解问题中,对于每一步决策,列出各种可能的局部解,再 依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一 步都经过筛选,以每一步都是最优解来保证全局是最优解,这种求解 方法称为动态规划法。 1、约束条件:有n个输入,它的解由这n个输入的一个子集组成,这 个子集必须满足某些事先给定的条件,这些条件称为约束条件。 2、可 行 解:满足约束条件的解称为问题的可行解。 3、目标函数:满足约束条件的可行解可能不只一个,为了衡量这些 可行解的优劣,事先给出一定的标准,这些标准通常以函数的形式给 出,这些标准函数称为目标函数。 4、最优化问题:使目标函数取得极值(极大或极小)的可行解称为 最优解,这类问题就称为最优化问题。

?应用:矩阵连乘、多段图的最短路径、最长公共子序列、最优二叉排 序树。

第七部分 算法
? 回溯法
?思想:回溯法也叫试探法,它是一种系统的搜索问题解的方法。回溯 法的基本思想:从一条路往前走,能走得通就继续走,走不通就退回 最近的交叉路口继续走下一条路. 初始时,令解向量X为空,然后,从根结点出发,选择S1的第一个 元素作为解向量X的第一个分量,即x1= a11,如果X=(x1)是问题的部分 解,则继续扩展解向量X,选择S2的第一个元素作为解向量X的第2个 分量,否则,选择S1的下一个元素作为解向量X的第一个分量,即x1= a12。依此类推,一般情况下,如果X=(x1, x2, …, xi)是问题的部分解, 则选择Si+1的第一个元素作为解向量X的第i+1个分量时,有下面三种 情况: 1、如果X=(x1, x2, …, xi+1)是问题的最终解,则输出这个解。如果问题 只希望得到一个解,则结束搜索,否则继续搜索其他解;

第七部分 算法
? 回溯法
2、如果X=(x1, x2, …, xi+1)是问题的部分解,则继续构造解向量的下一 个分量; 3、如果X=(x1, x2, …, xi+1)既不是问题的部分解也不是问题的最终解, 则存在下面两种情况: ① 如果xi+1= ai+1k不是集合Si+1的最后一个元素,则令x i+1= a i+1k+1, 即选择S i+1的下一个元素作为解向量X的第i+1个分量; ②如果x i+1= a i+1k是集合S i+1的最后一个元素,就回溯到X=(x1, x2, …, x i),选择Si的下一个元素作为解向量X的第i个分量,假设xi= a ik,如 果aik不是集合Si的最后一个元素,则令xi= aik+1;否则,就继续回溯到 X=(x1, x2, …, x i-1);

?应用:图的着色、哈密顿回路、八皇后问题、批处理作业调度。

第七部分 算法
? 贪心法
?思想:从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快 的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算 法停止。 实现该算法的过程: 从问题的某一初始解出发; while 能朝给定总目标前进一步 do 求出可行解的一个解元素; 由所有解元素组合成问题的一个可行解; ? 该算法存在问题: 1. 不能保证求得的最后解是最佳的; 2. 不能用来求最大或最小解问题; 3. 只能求满足某些约束条件的可行解的范围。

?应用:最小生成树、背包问题、旅行家问题、图的着色、活动安排问 题、多机调度问题。

第七部分 算法
? 分支限界法
?思想:在求解问题中,对于每一步决策,列出各种可能的局部解,再 依据某种判定条件,舍弃那些肯定不能得到最优解的局部解,在每一 步都经过筛选,以每一步都是最优解来保证全局是最优解,这种求解 方法称为动态规划法。 ?应用:矩阵连乘、多段图的最短路径、最长公共子序列、最优二叉排 序树。

第七部分 算法
?真题
?200505

●为在状态空间树中__(53)___,可以利用LC-检索(Least Cost Search)快速找到一个答案结点。在进行LC-检索时,为避免算法过 分偏向于作纵深检查,应该___(54)____。 (53)A.找出任一个答案结点
C.找出最优的答案结点

B.找出所有的答案结点
D.进行遍历

(54)A.使用精确的成本函数c(.)来作LC-检索

B.使用广度优先检索
C.使用深度优先检索 D.在成本估计函数ê (.)中考虑根结点到当前结点的成本(距离)

第七部分 算法
?真题
?200505

●利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest path problem)时,设有向图G=<V,E>共有n个结点,结点编 号1~n,设C是G的成本邻接矩阵,用Dk(i,j)即为图G中结点i到j并 且不经过编号比k还大的结点的最短路径的长度(Dk(i,j)即为图G中 结点i到j的最短路径长度),则求解该问题的递推关系式为 ___(56)___。
(56)A. Dk (i,j)=Dk-1(i,j)+C(i,j)

B. Dk (i,j)=min{Dk-1(i,j),Dk-1(i,j)+C(i,j)}
C. Dk (i,j)=Dk-1(i,k)+Dk-1(k,j) D. Dk (i,j)=min{Dk-1(i,j),Dk-1(i,k)+Dk-1(k,j)}

第七部分 算法
?真题
?200511 ●设求解某问题的递归算法如下: 求解该算法的计算时间时,仅考虑算法Move所做的计算为主要计算,且 Move为常数级算法。则算法F的计算时间T(n)的递推关系式为 ____(53)____;设算法Move的计算时间为k,当n=4时,算法F的计算时 间为___(54)___。 (53)A.T(n)=T(n-1)+1 C.T(n)=2T(n-1)+1 (54) A. 14k C.16k B.T(n)=2T(n-1) D.T(n)=2T(n+1)+1 B . 15k D.17k

第七部分 算法
?真题
?200511 ●利用贪心法求解0/1背包问题时,___(55)___能够确保获得最优解。用 动态规划方法求解0/1背包问题时,将“用前i个物品来装容量是X的背 包”的0/1背包问题记为KNAP(1,i,X),设fi(X)是KNAP(1,i,X)最优解的效 益值,第j个物品的重量和放入背包后取得效益值分别为Wj和pj(j=1~n)。 则依次求解f0(X)、f1(X)、...、fn(X)的过程中使用的递推关系式为 ___(56)___。 (55)A.优先选取重量最小的物品 C.优先选取单位重量效益最大的物品 B.优先选取效益最大的物品 D.没有任何准则

(56)A.fi(X)=min{fi-1(X),fi-1(X)+pi}

B.fi(X)=max{fi-1(X),fi-1(X-Wi)+pi}

C.fi(X)=min{fi-1(X-Wi),fi-1(X-Wi)+pi} D.fi(X)=max{fi-1(X-Wi),fi-1(X)+pi}

第七部分 算法
?真题
?200611

● (58) 算法策略与递归技术的联系最弱。
(58)A. 动态规划 B. 贪心 C. 回溯 D. 分治

● 对于具有 n 个元素的一个数据序列,若只需得到其中第 k 个元素之 前的部分排序, 最好采用 (59) ,使用分治(Divide and Conquer) 策略的是 (60) 算法。
(59)A. 希尔排序 (60)A. 冒泡排序 B. 直接插入排序 C. 快速排序 B. 插入排序 C. 快速排序 D. 堆排序 D. 堆排序

第七部分 算法
?真题
?200705 ●设商店有 10 元、5 元、2 元和 1 元的零币,每种零币的数量充足。售 货员给顾客找零钱时,零币的数量越少越好。例如给顾客找零 29 元: 先选 2 张 10 元币,然后选择 1张 5 元币,再选择两张 2 元币。以上的找 零钱方法采用了(62) 策略。 (62)A. 分治 ?200711 ● 迪杰斯特拉(Dijkstra)算法按照路径长度递增的方式求解单源点最短 路径问题,该算法运用了(63) 算法策略。 (63)A. 贪心 B. 分而治之 C. 动态规划 D. 试探+回溯 B. 贪心 C. 动态规划 D. 回溯

第七部分 算法
?真题
200711 ● 关于算法与数据结构的关系,(64) 是正确的。

(64)A. 算法的实现依赖于数据结构的设计
B. 算法的效率与数据结构无关 C. 数据结构越复杂,算法的效率越高

D. 数据结构越简单,算法的效率越高
● 若一个问题既可以用迭代方式也可以用递归方式求解,则(65) 方 法具有更高的时空效率。 (65)A. 迭代 C. 先递归后迭代 B. 递归 D. 先迭代后递归

第七部分 算法
?真题
?200805
● 一个算法是对某类给定问题求解过程的精确描述,算法中描述的操作 都可以通过将已经实现的基本操作执行有限次来实现,这句话说明算法 具有 __(62)__ 特性。 (62)A. 有穷性 B. 可行性 C. 确定性 D. 健壮性 ● 斐波那契数列为:

用递归算法求解F(5)时需要执行 __(63)__ 次―+‖运算,该方法采用 的算法策略是 __(64)__ 。

(63)A.5
(64)A. 动态规划

B.6
B. 分治

C.7
C. 回溯

D.8
D. 分支限界

第七部分 算法
?真题
?200811
● 给定一组长度为n的无序序列,将其存储在一维数组a[0..n-1]中。现 采用如下方法找出其中的最大元素和最小元素:比较 a[0]和 a[n-1],若 a[0]较大,则将二者的值进行交换;再比较a[1]和a[n-2],若a[1]较大, 则交换二者的值;然后依次比较a[2]和a[n-3]、a[3]和 a[n-4]、…,使得 每一对元素中的较小者被交换到低下标端。重复上述方法,在数组的前 n/2 个元素中查找最小元素,在后n/2个元素查找最大元素,从而得到整 个序列的最小元素和最大元素。上述方法采用的算法设计策略是(64)。 (64)A. 动态规划法 B. 贪心法 C. 分治法 D. 回溯法

● 设某算法的计算时间表示为递推关系式T(n)= T(n-1) + n (n>0) 及 T(0)=1,则该算法的时间复杂度为(65)。 (65)A.O(lgn) B. O(n lgn) C.O(n) D. O(n2)

第七部分 算法
?真题
?200905 ● 现有16枚外形相同的硬币,其中有一枚比真币的重量轻的假币,若 采用分治法找出这枚假币,至少比较 (63) 次才能够找出该假币。

(63)A. 3

B. 4

C. 5

D. 6

● 以下的算法设计方法中, (64) 以获取问题最优解为目标。

(64)A. 回溯方法 B. 分治法

C. 动态规划 D. 递推

● 归并排序采用的算法设计方法属于(65) 。 (65)A. 归纳法 B. 分治法 C. 贪心法 D. 回溯方法

第七部分 算法
?真题
?200911 ● 某算法的时间复杂度表达式为T(n)=an2+bnlgn+cn+d,其 中,n为问题的规模,a、b、c和d为常数,用O表示其渐近时 间复杂度为(63)。 (63)A.O(n2)

B.O(n)
C.O(n1gn) D.O(1)

L/O/G/O

Thank You!


更多相关文档:

数据结构与算法试题

数据结构与算法试题 一、 单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A C 内部结构与外部结构 线性结构与非线性结构 B D 静态结构与动态...

数据结构和算法部分经典例子

数据结构和算法部分经典例子_IT/计算机_专业资料。只能作为参考!数据结构和算法部分经典例子 一、迭代法 迭代法是用于求方程或方程组近似根的一种常用的算法设计方法...

第1章 数据结构与算法

软考辅导——数据结构与算... 134页 免费 数据结构与算法 (2) 10页 免费如...存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称...

第1章 数据结构与算法

软考辅导——数据结构与算... 134页 免费 数据结构与算法 (4) 14页 免费 数据结构与算法 (2) 10页 免费 8、模块 62页 1财富值如要投诉违规内容,请到百度...

第1章 数据结构与算法

软考辅导——数据结构与算... 134页 免费 8、模块 62页 1财富值 外贸知识通俗教程 37页 免费 数据结构与算法 (4) 14页 免费 数据结构与算法 (2) 10页 ...

软考-数据结构复习题2

软考-数据结构复习题2_计算机软件及应用_IT/计算机_专业资料。软考-数据结构 1. 二叉树有哪几种基本形态? 画图说明之。 空树 仅有根结点的二叉树 右子树为空...

数据结构与算法1-5单元练习题及答案

数据结构与算法1-5单元练习题及答案_IT认证_资格考试/认证_教育专区。单元练习 1 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳ )(√)(1)...

数据结构与算法离线作业 答案

数据结构与算法离线作业 答案_计算机软件及应用_IT/计算机_专业资料。浙大pet数据结构作业答案浙江大学远程教育学院 《数据结构与算法》课程离线作业姓名: 年级: 陈翠...

软考中的数据结构知识-前3章。

软考基础知识专题九:数据... 25页 免费 软考辅导——数据结构与算... 134页...(共 15 分) 试题一 阅读以下说明和算法, ,完善算法并回答问题,将解答写在...

数据结构与算法设计知识点

数据结构与算法设计知识点试题类型:本课程为考试科目 (闭卷笔试) , 试题类型包括: 概念填空题 (10 %) , 是非判断题 (10 %) , 单项选择题(40 %) ,算法...
更多相关标签:
软考 数据结构 | 数据结构与算法 | 数据结构与算法分析 | java数据结构和算法 | 数据结构与算法 pdf | c 数据结构与算法 | 数据结构和算法 | 数据结构与算法 java |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com