理学江苏省计算机三级偏软课件_第1页
理学江苏省计算机三级偏软课件_第2页
理学江苏省计算机三级偏软课件_第3页
理学江苏省计算机三级偏软课件_第4页
理学江苏省计算机三级偏软课件_第5页
已阅读5页,还剩126页未读, 继续免费阅读

付费下载

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

江苏省计算机等级考试

三级偏软

考试内容

・1、计算机基础知识(14分选择)

•2、软件概念及数据结构(14分选择+8分填

空)

•3、操作系统(12分选择+4分填空)

・4、数据库知识(9分选择+6分填空)

•5、软件工程(11分选择+4分填空)

■6、网络知识(5分选择+2分填空).

•7、微机系统分析及应用(5分选择+6分填

空)二K:二

第1章考核知识要点

・1.计算机的发展概况(发展历史、计算机新

技术及相关设备)

•2.计算机的应用领域

・3.微型计算机系统的组成和主要技术指标

★4.计算机中的进位计数制(二进制、十进制、

八进制、十六进制及相互转换)

★5,带符号数的表示方法(原码、反码、补码

的表示和运算)

★6.定点数、浮点数

•7.二进制信息编码(BCD码、ASCII码、汉

字编码)

★8.算术运算和逻辑运算(定点加减法运算及

其溢出的判断、定点乘除运算、基本逻辑

运算)I「I

历年考试知识点

计算机的发展

2009年(秋)1,2微型机新技术,内存

2010年(春)1,2北桥芯片命名规则,北桥芯片性能

2010年(秋)1,2微型机新技术,内存

2011年(春)1,2微型机新技术,处理器

2011年(秋)1,2处理器,操作系统

•该知识点属必考内容,要考查当年或前年新出现的

CPU技术或总线技术

历年考试知识点

进位和计数制

2009年(秋)不同进制下数值大小比较

2010年(春)不同进制的计算

2010年(秋)不同进制下数值大小比较

2011年(春)不同进制转换

2011年(秋)不同进制下数值大小比较

•重点常考内容,主要考查不同进制转换以便不同进制下数值4

的大小比较“飞

第2章考核知识要点

•1,软件及其发展历史

•2,算法及其描述(算法特点、算法描述、算

法评价、算法效率的度量)

•3.操作系统的概念与发展

・4.编译程序和解释程序

•5.数据库系统基础1

•6.汉字处理基础知识,应用软件的范围和作

用・

•7.计算机网络基础(计算机网络的发展、因

特网基础知识、计算机网络功能)

・8.多媒体基础知识

•9.数据、数据元素和数据结构

★10.线性表(逻辑结构、顺序存储结构、运

算)

★11.栈(定义、顺序存储结构、运算、应用)

♦12.队列(概念、环形队列、应用)Q

★13.数组(概念、顺序存储结构、稀疏矩阵)

★14.线性链表(结构、运算)

★15.链栈、链队列和双向链表

・16.树

★17.二叉树(定义、性质、存储结构、遍历)

★18.图(定义、存储、遍历)

★19.线性查找、对半查找和分块查找

•20.散列查找(散列函数、冲突的处理方法)

★21.简单选择排序、插入排序和冒泡排序Q

★22.堆排序、快速排序和归并排序

重点

■数据结构

­线性表

•栈和队列

­数组

­树

•图

•查找

•排序

数据结构

•逻辑结构

•例如,2行3列的二维数组

a2a3

①%%

不同的关系构成不同的结构:

集合、线性结构、树形结构、图(网状)结构

数据结构

•逻辑结构

•线性结构:

•树形结构:

数据结构

•逻辑结构

•图结构:

数据结构

,存储结构

­数据的存储结构是数据逻辑结构在计算机存储器中的

表示(映像),又称物理结构。

•存储结构包括数据元素的表示和关系的表示。

»可页序

A链接

A索引.

A散列4

线性表

•线性表是由n(n>=0)个具有相同特性

的数据元素(结点)即,a2,a3,

an组成的有限序列。

通常记作:L=(沏,如,・・・,&□)

•n=0时称为空表;

线性表

•例1:一组实验数据(41,21,34,53,62,71,76,45)

•例2:26个大写英文字母组成的字母表(A,B,C,…,Z)

•例3:学生成绩统计表也是一个线性表。

学号姓名数学物理英语总分

1李华878867242

2王涛679583245

3张三986878244

4田勇899156236

5徐飞786583A㈤226

09年秋真题

・21.下列关于线性表元素的叙述中,正确的是

(教材P44)

-A.同一表中的元素必须相同类型,不同表中的元

素必须相同类型

-B,同一表中的元素可以不同类型,不同表中的元

素必须相同类型

同一表中的元素必须相同类型,不同表中的元

隶可以不同类型曩

-D.同一表中的元素必须不同类型,不同表中的元

素可以不同类型

线性表

•顺序存储结构

Loc(a1)ai

•用一组地址连续的内存单元依次

存放线性表的数据元第。

■

aFT

Locfa:)=Loc(a-j)+(i-1)*L

Loc(%)ai

每个元素占L个存储单元3i+l

■

3n

顺序表通过

元素的存储顺序与

映线性表元素间的逻辑关系

11年春真题

•21,设顺序结构线性表It的元素存储在

lt.e[O卜中,其中n为表长,若

1<i<n,n>2,则第i个元素的前驱元素为()

-A.lt.e[i-2]B.It.e[b1]C.It.e[i]D.It.e[i+1]

分析:线性表的第i个数据元素ai的存储位

置为LOC(ai)为:

LOC(ai)=LOC(ai)+(i-1)L

线性表

线性表的链式存储结构

-单链表

•单链表中结点:

数据域指针域

datanext

线性表

­线性表的链式存储结构

-单链表

(不带表头结点)

head------

----A李华A王放>张利-----A成惠A

ik

head->datahead->next

head=NULL,则该链表称为空表。

线性表

­线性表的链式存储结构

-单链表

(带表头结点)

head是头指针

head

线性表

线性表的链式存储结构

线性表

线性表的链式存储结构

-循环链表

线性表

线性表的链式存储结构

-循环链表

(a)头指针表示的带头结点的单循环链表

(b)仅有一个表头结点的空循环链表

(c)尾指针表示的带头结点的单循环链表

线性表

线性表的链式存储结构

-双向循环链表

head

(b)空的双向循环链表

(c)非空的双向循环链表

线性表的基本运算

­线性表的插入运算

•是指在表的第/(14/《加1)个(或符合要求的)位

置上,插入一个新的结点X,使长度为力的线性表:

(■■■,a」1)a1,a[+i,•**,an)

变成为长度为77+1的线性表:

(aji,x,马,马+1,...,)

•见教材p.45算法2-1

线性表的基本运算

•单链表的插入

•假设指针p指向单链表中某个结点,指针S指向值为X的新

待插结点。

•若将新结点S插入结点P之后,则称为后插;

•若将新结点S插到结点p之前,则称为前插。

•后插运算head

线性表的基本运算

•单链表的插入

•后插运算

(a)插入前的链表head

q—»pp->next

---->288--------->344--------।—>7788

58

(b)将新结点s插在结点p之后

•魂线性表的基本运算

•单链表的插入

•前插运算

(c)将新结点S插在结点p之前

见教材p64算法2-10

线性表的基本运算

­线性表的删除运算

•将线性表中第i个(或符合要求)的数据元素删除,

使长度为力的线性表:

(a],...,a」[jQjjQ+1,■*•,^ri)

变成为长度为77-1的线性表:

(3-|,■■■53j_-|,Qj+^ij,■•j^|-|)

•见教材p46算法2-2

r>

线性表的基本运算

•单链表的删除

qPp->next

head

283458

(a)删除前的链表

qpp->next

28345899A

(b)删除后的链表

FF

见教材p65算法2-11

顺序表和链表的比较

•线性表的优点:存储密度大,但不

便于插入和删除运算

•链表的优点:便于插入和删除运算

栈

•栈是限定仅能在表尾一端进行插入、删除

操作的线性表。

(Hp^9•••9-i?a”)

删除插入

栈

栈的特点

后进先出

栈

•栈的顺序存储结构

•利用一组地址连续的存储单元依次存放自栈底到

栈顶的数据元素,同时附设指针top指示栈顶元素

在顺序栈中的位置。

..e[max]

stack——--------

top

a

Ie栈

•顺序栈的基本运算

5____5topA5F55

4____44EtopA4E4

3____33D3D3

2____22C2CtopA2c

1____11B1B1B

0topAOA0A0A0A

topA------

-1-1-1

(a)空栈(b)A入栈(c)BCDEF入栈(d)F出栈(e)ED出栈

■

见教材p48算法2-3,算法2-4

栈

•栈的链式存储结构

・以某种形式的链表作为栈的存储结构,其组织形

式与单链表类似。

datanextdatanextdatanext

CBAA

栈顶栈底

队列

•队列又称为先进先出表(FirstInFirst

Out),简称FIFO表。

出队<----aia2・.・a„_i<------入队

~rHr

队头队尾।

队列

•队列的顺序存储结构

•顺序队列可利用一个一维数组和两个指针来实现。

•一维数组用于存储当前队列中的所有元素,两个指针

front和rear分别指向当前队列的队首元素和队尾元

素。(注意,它们并非指针变量,而是数组的下标)。

队列

•队列的顺序存储结构

•【例3.8】假设某个顺序队列Q为(A,B,C,D,

E,F),队列的长度MAXSIZE=6O

要求:给出顺序队列出队和入队时,队首指针

及队尾指针的变化情况。

队列

•队列的顺序存储结构

55

44

head—

rear->3Drear—,(D)

2C2(0

1B1(B)

0A0(A)

head->head—>

rear—>

(a)空队列(b)A,BCD入队(c)A,B,C,D出队(d)E,F入队

队列

•顺序存储的循环队列

rear

.入队时,队尾指针的操作:

》rear=(rear+1)%MAXSIZE

”出队时,队头指针的操作:

head-\/—head=(head+1)%MAXSIZE

wxv777^

指针移动方向1°MAXSIZE-I

队列

.^4

•顺序存储的循环队列

£

rear

\head

(b)元素A入队

队列

•顺序存储的循环队列

<d>循环队列为满队

队列

•顺序存储的循环队列

•在循环队列中队满和队空的条件分别为:

•队满的条件:(rear+1)%MAXSIZE==head

•队空的条件:rear==head

•入队:rear=(rear+1)%MAXSIZE

•出队:head=(head+l)%MAXSIZE

队列

•顺序存储的循环队列

•【例3.9】对于循环队列,写出队列中元素个数的公

式。

队空,BPfront=rear

Rear-front若rear>front

IRear+QueueSize-front若rear<front

<QueueSize-1若队满

(Rear+QueueSize-front)%QueueSize

书上P55例题2-25

链队列

•队列的链接存储结构

•队列的链式存储结构简称为链队列,它实际上是一个

同时带有首指针和尾指针的单链表。

•首指针指向队头结点,尾指针指向队尾结点即单链表

的最后一个结点。

11春真题

•22•设有带表头结点的链队列cq,队头指针为

cq.rear,下面队列空或队列满的判断条件,正确

的是O。其中“二二”为等于关系运算符,“&&”

为逻辑与运算符,NULL为空指针。

-A.cq.front==NULL&&cq.rear==:NULL是队歹U空的条件

-B.cq.front==NULL&&cq.rear==:NULL是队歹U满的条件

一03.什0讨二^4」四「是队列空的条件

-口3.什0讨二^4」须「是队列满的条件

数组

•一维数组人㈤,由a2,an_19aj这〃个元素组

成的,每个元素除了具有相同的类型外,还有一个确

定元素位置的下标。

•二维数组A[屈[切,由腿打个元素组成的,元素之间有

规则地排列。每个元素由值和两个能确定元素位置的

下标组成。

a11a12…aIn

_a21a22…a2n

cmxn一•••••••

••••

°mlam2••,amn

数组

•一维数组的顺序存储结构

数组下标,=123456…,n

aia2a^3a526•••aia〃

•一维数组A中第1个元素盯的存储位置的计算公式为:

Loc(a,)=Loc(a7)+(i-1)*d(1wiwn)

C++中,下标从。开始-----

<关键是计算、

V准确个数)

数组

•二维数组的两种顺序存储方式

1)以行序为主序(行优先)

第1行元素第2行元素第〃2行元素

a”♦♦♦n@21♦♦♦^2n・♦♦a加•♦•^tnn

2)以列序为主序(列优先)

第1列兀素第2列兀素第〃列兀素

___A___________,_________A___________________人_________

rV、C、

由1•・«a”?i2…a加2…@1”…a阳〃

数组

•二维数组的两种顺序存储方式

•当A[m][n]按“行优先”存储时的存储位置计算公式:

Loc(%):Loc(a00)+(nxi+j)xd

・当按"列优先“存储时的存储位置计算公式:

!_℃(%)=Loc(a00)+(mXj+i)Xd

下标从(0,0)到

11春真题

•23,设二维数组B的元素以字节数为单位,

存放在B⑼⑼~B[4][9]中。若按行优先次序

进行存储,则数组元素B[2][3]的存储地址为

146;若按列优先次序进行存储,则数组元

素B[3][2]的存储地址为126,由此可知,若按

行优先次序存储,则数组元素的存储

施址为()

-A.61B.132C.161D.222

分析:利用按行序为主序的存储地址计算公

式和按列序为主序的存储地址计算公式

数组

•稀疏矩阵

•大多数元素值都是零,只有少数的非零元素,这类矩

阵称为稀疏矩阵。

05000「0000

0-300010000

A4X5-55X4=00220

90000

27000

080000000

(a)稀疏矩阵A(b)稀疏矩阵3

数组

•稀疏矩阵的压缩存储

•三元组

(b)b->data

数组

•稀疏矩阵的转置运算(三元组表示)

01290000]00-30015

000000012000180

-300001409002400

0024000000000-7

01800000000000

1500-70000014000

000000,

^6x7

^7x6

数组

•稀疏矩阵的转置运算(三元组表示)

v

13-3a(ij户b(j,i)

1615

3112

3518

419

5424

66-7

6314

a.datab.data

考占

▲—ZJ八、、

•填空题(76)可能会考有关稀疏矩阵的转置

(8分)

•搞懂书上P61例题2・29

树

•T={A,B,C,D,E,F,G,H,I,J,K,L,M)

•A是根,其余结点可划分为3个互不相交的集合:

•T1={B,E,F,K,L},T2={C,G},

T3={D,H,I,J,M)

树

(a)只有一个根结点的树(b)一般的树

二叉树

•定义

二叉树是有限的结点集合,这个集合或者为空,或者

有一个根结点,它由两棵不相交的分别称为根的左子

树和右子树的二叉树组成。左子树和右子树同样又都

星—^昊二•叉权h.

过0

(a)空二叉树(b)仅有根(c)根和左子树(d)根和右子树(e)根和左、右子树

二叉树的5种基本形态

二叉树

一棵普通的无序树

两棵不同的二叉树

二叉树

•二叉树的顺序存储结构

数组下标012345678910H1213

数组dataABCDEFGHIJKLM

(b)二叉树的顺序存储结构

二叉树

•二叉树的顺序存储结构

•普通二叉树的顺序存储方法

(a)一棵普通二叉树(b)添加4个虚构结点后变成满二叉树

数组下标01234567

数组dataABC

(c)二叉树的顺序存储结构

二叉树

二叉树的链接存储结构

Ichilddatarchild

(a)二叉树(b)二叉链表

二叉树、

其第一个元素值为二叉树中根结点

•二叉树的遍历二一的蓼据®___________

一A"、,先序遍历序列:A,B,D,E,G,C,F

中序遍历序列:D,B,G,E,A,C,F

⑥F®后序遍历序列

⑥j以相结占的加抿侑为

其最后一个元素值为二叉树中疝府

点的数据值。r

算法见教材p73L----------------------------------)

11春真题

•25.设tO为二叉树bt中的某一结点,t1为tO的左子

树中的结点,t2为tO的右子树中的结点,则以下

说法正确的是O

-A.中序遍历bt,则t1必然在t2的前面

-B.后序遍历bt,则t1必然在t2的前面

-C.先序遍历bt,则t1必然在t2的前面

-D.后序遍历bt,t1与t2的先后次序不定।

分析:中序遍历:左根右;后序遍历:左右根;

先序遍历:根左右皿鱼I1

图

•定义

•一个图G是由两个集合3(G)和E(G)组成的,图的

二元组可定义为:

G=(V,E)

①MG)是顶点的有穷非空集合,每个顶点都可以标

上不同的字符或数字。■

②E(G)是V中顶点边的有穷集合,而边是V中顶点

的偶对。在特殊情况下,E(G)可以是空集。

图的定义

V(G1)={V1,V2,V3,V4}

E(G1)={(V1,V2),(V1,V3),(V1,V4),

(V2,V3),(V2,V4),(V3,V4)}

V(G3)={V1,V2,V3}

E(G3)={<V1,V2>,<V1,V3>,<V2,V3>,

<V3,V2>}

图的存储结构

•图的存储结构至少要保存两类信息:

1)顶点的数据

2)顶点间的关系

­两种常用的图的存储表示方法:

1)邻接矩阵

2)邻接表

11春真题

・26.在具有n个顶点、m条边的无向图邻接表

中,顶点数据域总数、链表的邻接域总数

分别为()

-A.n>mB.2n>m

-C.n>2mD.2n>2m

图的遍历

•图的遍历是指从任意指定的某个顶点(初始点)

出发,按照一定的搜索方法依次访问图中所有顶

点,且每个顶点仅被访问一次。

•根据搜索路径不同,有两种遍历方法:

深度优先搜索遍历(DFS),广度优先搜索遍历

(BFS)o

深度优先搜索的基本思想

•从顶点V1出发进行深度优先遍历下面的无向图

V1、M2、V5、V10、V6、77、V3、V12、V11、V8、V4、V9

广度优先搜索的基本思想

•对下面的无向图进行广度优先遍历,给出从顶点

S出发进行遍历的结果。

V1、V2、V3、V4、V5、V6、77、V8、79、V10、V11、V12

查找的基本概念

•查找:又称检索,就是从一个数据元素集

合中找出某个特定的数据元素。

•查找表:由同一类型的数据元素(或记录)

构成的集合。

查找的基本概念

•查找运算主要是对关键字进行比较,所以

通常用平均查找长度作为衡量一个查找算

法效率优劣的标准。

•2是查找第/个结点的概率,若每个结点的

查找概率是相等的,则平均查找长度ASL计

算公式可简记为:.

1«

ASL二二》Gd—.1

线性查找

•基本思想:在一列给定的值中进行搜

索,从一端开始逐一检查每个元素,

直到找到所需元素的过程。

・线性查找又称为顺序查找

线性查找

•算法分析

•查找成功时,最好的情况下,所查找的结点是R[〃],其比

较次数为a=i;最坏的情况下,所查找的结点是Rpi],

其比较次数为一般情况下,其比较次数为

G=n—i+1o

•因此,在等概率情况下,查找成功时顺序查找的平均查找

长度为:

/口「1口.1n(n+1)77+1

ASLseqF

』舞i=i九2

■顺序查找算法的时间复杂度为0(")。

二分查找

•基本思想:假设r[low..high]是当前查找区间,首

先确定该区间中向位置mid=(low+high)/2,然后

将给定值k与有序表居中位置的关键字r[mid].key

进行比较。

•若r[mid].key=k,则查找成功,返回该结点的位

置mid;

•若r[mid].key<k,接着只要在其右子表中继续进

行二分查找;

•若r[mid].key>k,接着只需在其左子表中继续进

行二分查找。

二分查找

【例】假设待查找的有序表有11个结点,结

点的关键字序列为:

05,13,19,21,37,56,64,75,80,88,92

若用二分法查找关键字k=21和k=85的结点,

给出其二分查找过程的示意图。

二分查找

0513192137566475808892

个个

lowmidhigh

0513192137】5675808892

个

lowmidhigh

051319L21371566475808892

竹

lowmidhigh

(a)查找k=21的过程

二分查找

392376758o88

056492

<<卜

--

恸

nH

owidl

o531.2156758o8892

A9137

<1A

——

ndhgh

li

051319213756647580【8892

仲t

lowmidhigh

(b)查找k=85的过程

分块查找

­分块查找又称索引线性查找,性能介于顺序查找

和二分查找之间。

•索引存储的方法:首先把线性表R[1.川中的结点

平均分成若干块h要求线性表是“分块有序”。

•然后,抽取各块中最大的关键字及该块在线性表

的起始位置构成一个索引表因为线性

表R是分块有序的,所以索引表是一个有序表。

分块查找

索引表

100200999关键字key

1713块首地址addr

数组R102076941100105172140200150144300250450680999780

123456789101112131415161718

分块查找

•基本思想:首先根据所给的关键字k查找索

引表,确定待查结点所在的块,然后在已

确定的那一块中顺序查找关键字为k的结点。

•因为索引表是有序表,所以可用顺序查找

或二分查找确定结点在哪一块,由于块内

无序,故只能采用顺序查找进行块内查找。

可见,分块查找是在索引表和块上进行的

查找方法。

分块查找

•算法分析:分块查找包含了两个查找过程,

整个算法的平均查找长度是两个平均查找

长度之和。

•分块查找的平均查找长度不仅与结点数n有

关,还与每块的大小s有关。

散列查找

•散列查找是将元素的关键字通过某

种函数计算出相应的函数值,作为

元素的存储位置,该函数称为散列

函数。

处理冲突的方法

・所谓处理冲突就是一旦出现冲突时,

为发生冲突的元素找到另一个空闲的

散列地址存放该元素。

•解决冲突的方法有很多,常用的方法

有:开放定址法、链地址法。

处理冲突的方法

1.开放定址法一一线性探测法

•基本思想:将散列表T[O..Z?-1]看成是一个长度

为力的环形表。若发生冲突的单元地址为d=

〃(key),则依次探测d的下一个单元地址为:办1,

d+2,…,4―1,0,1,…,d—1,小1,直到找到

一个空单元或探查到T[上1]为止。

•用线性探测法解决冲突时,下一个开放地址的计

算公式:4F

d0=H(key)

4二(%+/)%n(1</<n-1)

处理冲突的方法

•【例】已知一组关键字为(9,12,4,5,13,16,

25),假设散列表表[7]的长度由7,散列函数为

〃㈤=麽7。若用线性探测法解决冲突,给出这组关键

字所构造的散列表HT。

01234560123456

00000009412

(a)散列表初态为空(b)插入12,9,4后的散列表

01234560123456

9412513259164125

(c)插入5后的散列表(d)插入13,16,25后的散列表

•27,散列表的地址空间为散列函数为

h(k)=k%7,式中“%”为取余运算符,用线

性探测法解决冲突,探测增量为1。现将关

键码为16、8、22、44、13、15的元素依

次存入,建立散列表,则在散列表中查找

关键码为15的元素时需要进行()次探测

-A.3B.4C.5D.6

分析:依次计算各个关键字对应的散列地

址,一旦发生冲突就使用线性探测法为插

入元素寻找空闲存储单元。

内部排序

・排序就是把一组记录(元素)按照某个

域的值的递增或递减的次序重新排列的

过程。

­常用且效率较高的内排序算法有5类:

插入排序、选择排序、交换排序、归

并排序和分配排序。

插入排序

・插入排序的基本方法:每次将一个待

排序的记录按其关键字大小,插到前

面已排好的序列中的适当位置,直到

全部记录插入为止。

直接插入排序

•直接插入排序是一种最简单的排序方法。

•基本思想:把数组R[刀]中待排序的刀个元素

看成为^一个有序表和一个无序表,开始时

有序表只有一个元素R[l],而无序表中包

含有4-1个元素R[2]〜R5]。排序过程中,

每次取出无序表中第一个元素,将它插到

有序表的适当位置上,使之成为新的有序

装,这样经过4-1次插入后)无序表变成为

空表,而有序表包含有刀个元素,至此排序

完毕。一、

直接插入排序

【例】假设数组R有8个待排序的记录,它们

的关键字分别为:

(36,25,48,12,65,43,20,36)

用直接插入排序法进行排序。

直接插入排序

趟数R101

0z=l(36)【36】固481265412036

I

1i=2(25)【25361[48~|1265432036

2z=3(48)[253648】回65432036

______I

3z=4(12)[122536481画432036

4Z=5(65)[1225364865]画2036

1

5z=6(43)【122536434865】

6z=7(20)[122025364348

7z=8(36)【122025363643

直接插入排序算法

•直接插入排序算法的时间复杂度为0(4)。

•直接插入排序是稳定的排序方法。

•直接插入排序的算法简单,容易实现。当

记录数。很大时,不适合进行直接插入排序。

折半插入排序

•由于插入排序的基本操作是在一个有

序表中进行查找和插入,而“查找”

操作可利用“折半查找”来实现。

折半插入排序

【例】在序列[01141923558492]

已排好序的基础上,将元素15插入到序列

中,最后还是一个有序序列。

•初始:[01141923558492]{15}

L=14H=7(15<23H=4-

1=3)

­第一趟:坪141923558492]{15}

L=12H=3(15>14H=2+1=3)

•第二趟:[01141923558492]{15}

L=H=3(15<19H=3-1H〈L折半结束)

•结果:[0114151923558492]

交换排序

•利用交换记录位置进行排序方法称为交换

排序。

•基本思想:两两比较待排序记录的关键字,

若发现两个记录关键字的次序相反时即进

行交换)直到没有反序的记亲为止。

・两种常用的交换排序:冒泡排序和快速排

序。…,

冒泡排序

•冒泡排序的具体过程:

•把第4个记录的关键字与第4-1个记录的关键字进

行比较,如果比刀].key<r[刀-1].key,则交换两

个记录r[n]和r[z?-l]的位置,否则不交换;然后

再把第n-\个记录的关键字与第4-2个记录的关键

字进行比较;其余类推,直到第2个记录与第1个

记录的关键字比较完为止,这个过程就称为一趟

冒泡排序o一,F

冒泡排序

•在整个冒泡排序过程中,首先对刀个待排序

的记录进行第一越冒泡排序,将关键字最

小的记录上浮到数组的第一个单元r[1]中;

然后对剩下的4-1个记录进行第二趟冒泡排

序,使关键字次小的记录上浮到数组第二

个单元r[2]中;重复进行4-1趟后,轻者上

浮而重者下沉,则整个冒泡排序结束。

冒泡排序

【例】假设"=8,数组R中8个记录的关键字分别

为:

(53,36,48,36,60,17,18,41)

用冒泡法进行排序,给出排序的过程。

段

4.冒泡排序

初始关键字序列【533648纹60171841】

第一次两两比较[5336483660171841]

一

第二次两两比较【5336483660171841)

第三次两两比较【5336483660171841]

冒泡排序

第四次两两比较【5336483617601841)

第五次两两比较【5336481736601841]

第六次两两比较【5336174836601841]

不小

第七次两两比较【531736

♦♦

第一趟冒泡结果(17)[5336

1

冒泡排序

5317171717171717

3653181818181818

4836533636363636

3648365336363636

6036483653414141

1760364841534848

18186041484853

41414160606060

(0)(1)(2)(3)(4)(5)(6)(7)

.快速排序

•快速排序是一种交换排序,是对冒泡排

序的改进,是目前所有排序方法中速度

最快的一种。

•基本思想:先通过一趟排序将待排记录

分割成独立的两部分,其中一部分记录

的关键字均比另一部分记录的关键字小,

然后分别对这两部分记录继续进行排序,

以达到整个序列有关。

快速排序

【例】假设〃=8,数组R中8个记录的关键字分

别为:

(49,38,65,97,76,13,27,49)

给出其第一趟快速排序的划分过程和结果。

快速排序

画3859776132749

初始关键字

常Tj

画1

38659732749

第一次交换后

76fj

t>761L

i回

273865973t49

AI

7Tj

—1

8

L回

27376349

i

6597l

卜1

Tj

97

国6

273897763549

第二次交换后卜

A

^—J

画-

273876

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论