当前位置: 首页 > >

数据结构复*资料考试题

概述 模块1:线性表 模块2:树型结构 模块3:图型结构 模块4:其他

概述
1.数据结构的定义 数据→数据元素→数据项

数据结构是指数据以及相互之间的联系(或 关系)。包括:
(1)数据的逻辑结构。

(2)数据的存储结构(物理结构)。
(3)施加在该数据上的运算。

概述
数据的逻辑结构是从逻辑关系上描述数据,它

与数据的存储无关,是独立于计算机的。
数据的存储结构是逻辑结构用计算机语言的实 现(亦称为映象),它是依赖于计算机语言的。 数据的运算是定义在数据的逻辑结构上的,每 种逻辑结构都有一组相应的运算。但运算的实现与 数据的存储结构有关。 程序=数据结构+算法

概述

逻辑结构主要有三大类:

(1)线性结构
(2)树形结构 (3)图形结构

概述
存储结构分为如下四种:
(1)顺序存储方法

(2)链式存储方法
(3)索引存储方法

(4)散列存储方法

概述
2. 算法
算法是对特定问题求解步骤的一种描

述,它是指令的有限序列。

概述
算法的五个重要的特性 : (1)有穷性

(2)确定性
(3)可行性

(4)有输入
(5)有输出

概述
算法的时间复杂度:是指其基本运算在算 法中重复执行的次数。

算法中基本运算次数T(n)是问题规模n的某 个函数f(n),记作:
T(n)=O(f(n)) 记号“O”读作“大O”,它表示随问题规 模n的增大算法执行时间的增长率和f(n)的增长

率相同。

例 分析以下程序段的时间复杂度。
i=1; while (i<=n) i=i*2;

解:上述算法中基本操作是语句 i=i*2 ,设其 频度为T(n),则有: 2T(n)≤n 即T(n)≤log2n=O(log2n)。 所以,该程序段的时间复杂度为O(log2n)。

概述
算法空间复杂度:是对一个算法在运行过程 中临时占用的存储空间大小的量度 。 对于空间复杂度为O(1)的算法称为原地工 作或就地工作算法。

概述
3. 算法设计方法:递归

■ 递归定义 在定义一个算法时出现调用本算法 的成分,称之为递归。

概述
■ 递归模型
由递归出口和递归体组成

例如,求二叉树所有结点个数:
f(b)=0 b=NULL

f(b)=f(b->lchild)+f(b->rchild)+1 b≠NULL

概述
■ 递归算法设计 ① 对原问题f(s)进行分析,假设出合理的 “较小问题”f(s') ; ② 假设f(s')是可解的,在此基础上确定f(s) 的解,即给出f(s)与f(s')之间的关系;

③ 确定一个特定情况(如f(1)或f(0))的 解,由此作为递归出口.

概述
b

b->lchild

b->rchild

① 假设出合理的“较小问题”: 假设左右子树的结点个数可求 ② 求出f(s)与f(s‘)之间的关系: f(b)=f(b->lchild)+f(b->rchild)+1 ③ 确定递归出口: f(NULL)=0

概述
求解算法:
int f(BTNode *b) { if (b==NULL) return(0); else

return(f(b->lchild)+f(b->rchild)+1);
}

例 设计求f(n)=1+2+...+n的递归算法 解:f(n)为前n项之和,则f(n-1)=1+2+...+(n-1) 假设f(n-1)可求,则f(n)=f(n-1)+n,所以:

f(n)=1
f(n)=f(n-1)+n

当n=1
当n>1

对应的递归算法如下:

int f(int n) { if (n==1)

return(1);
else return(f(n-1)+n)); }

模块1:线性结构

1.一般线性表
线性表:具有相同特性的数据元素的一个 有限序列。不是集合。

逻辑结构

模块1:线性结构
(1)顺序表 存储结构之一

typedef struct { ElemType elem[MaxSize]; /*存放顺序表元素*/ int length; /*存放顺序表的长度*/ } SqList;

模块1:线性结构

顺序表基本运算的实现
插入数据元素算法:元素移动的次数不仅与表

长n有关 ;插入一个元素时所需移动元素的*均次
数 n/2。*均时间复杂度为O(n)。

模块1:线性结构

删除数据元素算法:元素移动的次数也与
表长n有关 。删除一个元素时所需移动元素的 *均次数为(n-1)/2。删除算法的*均时间复杂 度为O(n)。

模块1:线性结构
(2)链表 定义单链表结点类型:
typedef struct LNode { ElemType data; struct LNode *next; } LinkList; /*指向后继结点*/

存储结构之二

模块1:线性结构

定义双链表结点类型:
typedef struct DNode { ElemType data; struct DNode *prior; struct DNode *next; } DLinkList;

/*指向前驱结点*/ /*指向后继结点*/

模块1:线性结构

■ 单链表基本运算的实现
重点:(1)头插法建表和尾插法建表算 法,它是很多算法设计的基础;(2)查找、

插入和删除操作。

模块1:线性结构

?头插法建表

该方法从一个空表开始,读取字符数组a中的字 符,生成新结点,将读取的数据存放到新结点的数据 域中,然后将新结点插入到当前链表的表头上,直到 结束为止。
采用头插法建表的算法如下:

模块1:线性结构
void CreateListF(LinkList *&L,ElemType a[],int n) { LinkList *s;int i; L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=NULL; for (i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*/ s->data=a[i]; s->next=L->next; /*将*s插在原开始结点之前,头结点之后*/ L->next=s; } }

采用头插法建立单链表的过程
第1步:建头结点

a d

c b

head



i=0 i=1 i=2 i=3

第2步:i=0,新建a结点,插入到头结点之后

head

a d



第3步:i=1,新建d结点,插入到头结点之后

head

a d



第4步:i=2,新建c结点,插入到头结点之后

head
head

c
b

a
d



第5步:i=3,新建b结点,插入到头结点之后

c

a



模块1:线性结构
? 尾插法建表

头插法建立链表虽然算法简单,但生成的链表 中结点的次序和原数组元素的顺序相反。若希望 两者次序一致,可采用尾插法建立。该方法是将 新结点插到当前链表的表尾上,为此必须增加一 个尾指针r,使其始终指向当前链表的尾结点。 采用尾插法建表的算法如下:

void CreateListR(LinkList *&L,ElemType a[],int n) { LinkList *s,*r;int i; L=(LinkList *)malloc(sizeof(LinkList)); /*创建头结点*/ L->next=NULL; r=L; /*r始终指向终端结点,开始时指向头结点*/ for (i=0;i<n;i++) { s=(LinkList *)malloc(sizeof(LinkList)); /*创建新结点*/ s->data=a[i];r->next=s; /*将*s插入*r之后*/ r=s; } r->next=NULL; /*终端结点next域置为NULL*/ }

模块1:线性结构
采用尾插法建立单链表的过程

a d

c b

i=0 i=1 i=2 i=3

head
头结点

a

d

c

b



模块1:线性结构

例 设 C={a1,b1,a2,b2,…,an,bn} 为一线性表 , 采 用带头结点的hc单链表存放,编写一个算法,将其 拆分为两个线性表,使得: A={a1,a2,…,an},B={b1,b2,…,bn}

模块1:线性结构
解: 设拆分后的两个线性表都用带头结点的单链表 存放。 先建立两个头结点 *ha和 *hb,它们用于存放拆分后 的线性表 A 和 B,ra 和 rb 分别指向这两个单链表的表尾 , 用 p 指针扫描单链表 hc, 将当前结点 *p 链到 ha 未尾 ,p 沿 next域下移一个结点,若不为空,则当前结点*p链到hb未 尾 ,p 沿 next 域下移一个结点 , 如此这样 , 直到 p 为空。最 后将两个尾结点的next域置空。 对应算法如下:

模块1:线性结构
void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) {

LinkList *p=hc->next,*ra,*rb;
ha=hc; ra=ha; /*ha的头结点利用hc的头结点*/ /*ra始终指向ha的末尾结点*/

hb=(LinkList *)malloc(sizeof(LinkList)); /*创建hb头结点*/ rb=hb; /*rb始终指向hb的末尾结点*/

模块1:线性结构
while (p!=NULL)
{ ra->next=p;ra=p; /*将*p链到ha单链表未尾*/ p=p->next;

rb->next=p;
rb=p; /*将*p链到hb单链表未尾*/ p=p->next;

}
ra->next=rb->next=NULL; /*两个尾结点的next域置空*/ }

模块1:线性结构
例 已知线性表元素递增有序,并以带头结点 的单链表作存储结构,设计一个高效算法,删除 表中所有值大于mink且小于maxk的元素(若表中

存在这样的元素)。并分析所写算法的时间复杂
度。

模块1:线性结构
解:先在单链表中找到其 data值则好大于 mink 的结点 *p ,其前驱结点为 *pre 。继续沿 next 链查 找其值大于maxk的结点,在这个过程中删除*p结 点。算法如下:
void delnode(SNode *h,ElemType maxk,ElemType mink) { SNode *p,*pre; if (maxk>=mink) { pre=h; p=pre->next;

模块1:线性结构
while (p!=NULL && p->data<=mink) { } while (p!=NULL && p->data<maxk) //删除*p { pre->next=p->next; free(p); pre=p; p=p->next;

p=pre->next;
} } }

模块1:线性结构

■ 双链表基本运算的实现 重点:插入和删除结点的算法。

模块1:线性结构

■ 循环链表基本运算的实现 重点:判断最后一个结点。

模块1:线性结构

例 某线性表最常用的操作是在最后一个结点之 后插入一个结点或删除第一个结点,故采用 存 储方式最节省运算时间。 A. 单链表
C. 双链表

B. 仅有头结点的单循环链表
D. 仅有尾指针的单循环链表

例 设计一个算法在单链表中查找元素值为e 的结点序号的算法LocateElem(L,e)。 思路:在单链表L中从头开始找第1个值域与e 相等的结点,若存在这样的结点,则返回位置,否则 返回0。
int LocateElem(LinkList *L,ElemType e) { LinkList *p=L->next;int n=1; while (p!=NULL && p->data!=e)

{

p=p->next; n++; }

if (p==NULL) return(0); else return(n); }

模块1:线性结构

解: 本题答案为D。
在有尾指针r的单循环链表中 在最后一个结点之后插入结点 *s的操作是: s->next=r->next;r->next=s;r=s。 删 除 第 一 个 结 点 的 操 作 是 : p=r->next;r>next= p->next;free(p)。 其时间复杂度均为O(1)。

模块1:线性结构

2. 栈
(1) 栈的定义 逻辑结构

栈是一种先进后出表
栈的基本运算:进栈,出栈。

例 已知一个栈的进栈序列是 1,2,3,…,n,其输出序 列是p1,p2,…,pn,若p1=n,则pi的值 。 (A) i (B) n-i

(C) n-i+1
p2=n-1, p3=n-2,

(D) 不确定

答:当p1=n时,输出序列必是n,n-1,…,3,2,1,则有:

…,
pn=1

推断出pi=n-i+1,所以本题答案为C。

模块1:线性结构
例 设 n个元素进栈序列是 1,2,3,…,n,其输出序列 是p1,p2,…,pn,若p1=3,则p2的值 。 (A) 一定是2 (B) 一定是1

(C) 不可能是1

(D) 以上都不对

答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可 能出栈 ,即为 2,也可能 4或后面的元素进栈 ,再出栈。 因此,p2可能是2,也可能是4,…,n,但一定不能是1。所 以本题答案为C。

模块1:线性结构

(2)顺序栈
typedef struct

存储结构之一

{
ElemType elem[MaxSize]; int top; } SqStack; /*栈指针*/

模块1:线性结构

? 顺序栈的4要素: 栈空条件:s.top==-1
栈满条件:s.top==MaxSize-1

进栈:top++;s.data[s.top]=e;
出栈:e=s.data[s.top];s.top—;

模块1:线性结构
(3)链栈
typedef struct linknode { ElemType data; /*数据域*/

存储结构之二

struct linknode *next; /*指针域*/ } LiStack;

模块1:线性结构
带头结点的单链表来实现(也可不带头结点)
lhead 头结点 栈顶结点 a1 a2 … 栈底结点 an



栈空条件:s->next==NULL

栈满条件:?

模块1:线性结构
3. 队列
(1) 队列的定义 队列是一种先进先出表。 队列的基本运算:进队,出队 逻辑结构

模块1:线性结构
(2) 顺序队
typedef struct { ElemType elem[MaxSize];

存储结构之一

int front,rear;/*队首和队尾指针*/
} SqQueue;

模块1:线性结构

? 环形队列的4要素:
队空:q.front==q.rear

队满:(q.rear+1)%MaxSize==q.front
进队:q.rear=(q.rear+1)%MaxSize;q.data[q.rear]=e;

出队:q.front=(q.front+1)%MaxSize;e=q.data[q.front];

模块1:线性结构
(3)链队
struct qnode /*数据结点*/ { ElemType data; struct qnode *next;

存储结构之二

} QNode;

typedef struct

/*头结点*/

{ QNode *front; QNode *rear; } LiQueue;

模块1:线性结构
4. 串
串、子串、串相等、空串、空格串 (2)顺序串 (3)链串 (4)串的模式匹配算法(不作要求)

(1)串的定义

模块1:线性结构

5. 数组和稀疏矩阵
(1) 数组的定义 相同类型数据元素、有限序列

模块1:线性结构
(2) 数组的存储结构 以数组A[c1..d1,c2..d2] 为例 以行序为主序 : LOC(ai,j)=LOC(ac1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*k 以列序为主序 LOC(ai,j)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*k

模块1:线性结构
(3)特殊矩阵的压缩存储 ■ 对称矩阵 若一个n阶方阵A[n][n]中的元素满足ai,j=aj,i(0≤i, j≤n-1),则称其为n阶对称矩阵。 A[0..n-1][0..n-1] ? B[0..n(n+1)/2] i(i+1)/2 +j k= j(j+1)/2 +i 当 i< j 时 当i≥j时

模块1:线性结构

■ 三角矩阵 采用类似的压缩方法.

模块1:线性结构
(4)稀疏矩阵 非零元素远小于元素总数。 存储结构: ■ 三元组表示

■ 十字链表表示
各种表示的基本思路。

模块1:线性结构
6. 广义表
■ 一个广义表中所含元素的个数称为它的长 GL=(a,(a),(a,b,c,d),()) 长度为4。

度.

模块1:线性结构

■ 一个广义表中括号嵌套的最大次数为它 的深度.
GL=(a,(a),(a,b,c,d),()) 深度为2。

模块1:线性结构

■ 表的第一个元素a1为广义表GL的表头, 其余部分(a2,…,ai,ai+1,…,an)为GL的表 尾. GL=(a,(a),(a,b,c,d),())
表头为a,表尾为((a),(a,b,c,d),())

模块2:树形结构 1. 树
(1)树的定义

递归定义
适合于表示层次结构的数据

模块2:树形结构

(2)树的表示法 (逻辑表示方法) ■ 树形表示法
■ 文氏图表示法

■ 凹入表示法
■ 括号表示法

模块2:树形结构

(3)树的遍历

■ 先根遍历算法
■ 后根遍历算法

模块2:树形结构

(4)树和二叉树的相互转换 ■ 树 ? 二叉树
■ 二叉树 ? 树

模块2:树形结构
2. 二叉树
(1)二叉树的定义

根、左子树、右子树
完全二叉树,满二叉树的定义

模块2:树形结构
(2)二叉树性质 性质1 非空二叉树上叶结点数等于双分支结点数 加1。即n0=n2+1. 性质 2 (i≥1)。 非空二叉树上第 i 层上至多有 2i-1 个结点

模块2:树形结构
(2)二叉树性质

性质3 高度为h的二叉树至多有2h-1个结点 (h≥1) 。
性质4 完全二叉树的性质 。 性质5 具有n个(n>0)结点的完全二叉树 的高度为?log2n+1?或?log2n?+1。

模块2:树形结构

例 将一棵有 99个结点的完全二叉树从根这一层 开始,每一层从左到右依次对结点进行编号,根结 点的编号为 1 ,则编号为 49 的结点的右孩子编号 为 。
A.98 B.99 C.50 D.不存在

答:D

模块2:树形结构

例 深度为5的二叉树至多有 个结点。 A.16 B.32 C.31 D.10

答:相同满度时满二叉树结点最多,

h=5的满二叉树结点个数=25-1=31。C。

模块2:树形结构
(3)二叉树存储结构 ■ 二叉树的顺序存储结构
A B D F C E
1 A 2 B 3 C 4 5 6 D 7 E 8 9 1 0 1 1 1 2 1 3 1 4 F

i 2i 左孩子 2i+1 右孩子

■ 二叉链存储结构
typedef struct node { ElemType data; struct node *lchild; struct node *rchild; /*数据元素*/ /*指向左孩子*/ /*指向右孩子*/

} BTNode;

A

B
左孩子

C
右孩子

模块2:树形结构
(4)二叉树的遍历

■ 先序遍历
■ 中序遍历
通常用递归算法实现

■ 后序遍历
■ 层次遍历
通常用队列来实现

模块2:树形结构
例 假设二叉树采用二叉链存储结构存储,试设计一 个算法,输出一棵给定二叉树的所有叶子结点。 解:输出一棵二叉树的所有叶子结点的递归模型 f()

如下:
f(b):不做任何事件 f(b):输出*b结点的data域 f(b):f(b->lchild);f(b->rchild) 若b=NULL 若*b为叶子结点 其他情况

模块2:树形结构
void DispLeaf(BTNode *b) 先序遍历 思想 { if (b!=NULL) { if (b->lchild==NULL && b->rchild==NULL) printf("%c ",b->data); DispLeaf(b->lchild); DispLeaf(b->rchild); } }

模块2:树形结构
例 试设计判断两棵二叉树是否相似的算法, 所谓二叉树 t1和 t2是相似的指的是 t1和 t2都是空 的二叉树;或者 t1和t2的根结点是相似的,t1的

左子树和t2的左子树是相似的且 t1的右子树与t2
的右子树是相似的。

模块2:树形结构
解 本题的递归模型如下:
true f(t1,t2)= false 若t1=t2=NULL 若t1、t2之一为NULL,另一不为NULL

f(t1->lchild,t2->lchild) && f(t1->rchild,t2->rchild)
其他情况

对应的算法如下:

模块2:树形结构
int like(BTNode *b1, BTNode *b2) 后序遍历 { 思想 int like1, like2; if (b1==NULL && b2==NULL) return 1; else if (b1==NULL || b2==NULL) return 0; else { like1=like(b1->lchild, b2->lchild); like2=like(b1->rchild, b2->rchild); return (like1 & like2); } }

模块2:树形结构
例 设计一个算法求二叉树的所有结点个数。 解: 对应的算法如下:
int nodenum(BTNode *bt)

{
if (bt!=NULL)

后序遍历 思想

return(nodenum(bt->lchild)+nodenum(bt->lchild)+1); else return(0);

}

模块2:树形结构
例 设计一个算法释放一棵二叉树bt的所有结点。 解:算法如下:
void release(BSTNode *&bt)
{ if (bt!=NULL) { release(bt->lchild); release(bt->rchild); free(bt); } } 后序遍历 思想

模块2:树形结构
(5)线索二叉树 共有2n-(n-1)=n+1个空链域 ? 线索化 线索化与某种遍历方式有关

模块2:树形结构
3. 哈夫曼树
(1) 哈夫曼树的定义 WPL最小,没有单分支结点即n1=0

模块2:树形结构

(2)哈夫曼树的构造过程

(3)哈夫曼编码的构造过程

模块3:图形结构
(1)图的基本概念 ■ 顶点的度、入度和出度 ■ 完全图 ■ 子图 ■ 路径和路径长度

■ 连通、连通图和连通分量
■ 强连通图和强连通分量 ■ 权和网

模块3:图形结构
(2)图的存储结构 ■ 邻接矩阵存储方法

■ 邻接表存储方法 掌握两种存储方法的优缺点,同一种功 能在不同存储结构上的实现算法。

模块3:图形结构
(3)图的遍历

■ 深度优先搜索遍历
离初始点越远越优先访问。
1 2 3 6 5 7

访问序列:1,2,3, 4, 5, 6, 7

4

模块3:图形结构
void DFS(ALGraph *G,int v) { ArcNode*p;Visited[v]=1; /*置已访问标记*/ printf("%d ",v); p=G->adjlist[v].firstarc; /*输出被访问顶点的编号*/

while (p!=NULL)
{ if (visited[p->adjvex]==0) DFS(G,p->adjvex); p=p->nextarc; }

}

模块3:图形结构
■ 广度优先搜索遍历 离初始点越*越优先访问。

1 2 3 6 5 7

访问序列:1,2,6, 7, 3, 5, 4

4

模块3:图形结构
void BFS(ALGraph *G,int v) { ArcNode *p; int queue[MAXV],front=0,rear=0; int visited[MAXV]; int w,i; for (i=0;i<G->n;i++) visited[i]=0; printf("%2d",v); visited[v]=1; /*置已访问标记*/ rear=(rear+1)%MAXV; queue[rear]=v; /*v进队*/

模块3:图形结构
while (front!=rear) /*若队列不空时循环*/ { front=(front+1)%MAXV; w=queue[front]; /*出队并赋给w*/ p=G->adjlist[w].firstarc; while (p!=NULL) { if (visited[p->adjvex]==0) { printf("%2d",p->adjvex); visited[p->adjvex]=1; rear=(rear+1)%MAXV; queue[rear]=p->adjvex; } p=p->nextarc; } } }

模块3:图形结构
例 试以邻接表为存储结构,分别写出基于

DFS和BPS遍历的算法来判别顶点i和顶点j(i≠j)之间
是否有路径。

解:先置全局变量visited[]为0,然后从顶点i开
始进行某种遍历,遍历之后,若visited[j]=0,说明

顶点i与顶点j之间没有路径;否则说明它们之间存
在路径。

模块3:图形结构
基于DFS遍历的算法如下: int visited[MaxVertexNum]; int DFSTrave(ALGraph *G,int i,int j) { int k;

for (k=0;k<G->n;k++) visited[k]=0;
DFS(G,i); //从顶点i开始进行深度优先遍历 if (visited[j]==0) return 0; else return 1; }

模块3:图形结构
基于BFS遍历的算法如下:

int visited[MaxVertexNum];
int DFSTrave(ALGraph *G,int i,int j) { int k; for (k=0;k<G->n;k++) visited[k]=0; BFS(G,i); //从顶点i开始进行广度优先遍历

if (visited[j]==0) return 0;
else return 1; }

模块3:图形结构
(4)最小生成树 ■ 普里姆算法

给定起始点;
算法过程;

O(n2)

模块3:图形结构

■ 克鲁斯卡尔算法 不给定起始点;

算法过程;
O(elog2e)

模块3:图形结构

(5)最短路径
■ 狄克斯特拉算法过程

■ 弗洛伊德算法过程

模块3:图形结构
(6)*伺判蚝凸丶肪
■ *伺判蛩惴

■ 求关键路径的过程

源点->汇点

源点的入度为0,汇点的出度为

模块4:其他

1. 查找
(1)线性表的查找 在顺序表上进行。方法有: ■ 顺序查找 (过程和算法)

■ 二分查找 (过程和算法)
■ 分块查找 (过程)

模块4:其他
(2) 树表的查找
▲ 二叉排序树 ■ 定义 ■ 查找(过程和算法) ■ 插入和删除(过程) 性质:二叉排序树的中序序列是一个有序序列 ? 与堆的区别

5 2 1 3 4 6 7 q 8 p 9 (a) 5 q 1 3 2 4 6 p 7 8 9 (b) 5 2 1 3 4 6 7 8 9 5 2 1 3 4 6 7 8 9 (d) 删除结点 5 1 p 2 3 (c) q p 删除结点 7 1 3 2 4 删除结点 4 1 2 3 删除结点 9 1 3 2 4

5 6 7 8

5 6 7 8 9 5 6 8 9

4 6 7 8 9

模块4:其他
▲ *衡二叉树
■ 定义

■ 查找(过程和算法)
■ 调整(过程)

模块4:其他
(3) 哈希表查找
■ 哈希函数 主要有除留余数法。 ■ 哈希冲突解决方法 主要有线性探查法、拉链法

模块4:其他
2. 内排序 ■ 插入排序

(1)直接插入排序
(2)希尔排序

■交换排序

(1)冒泡排序
(2)快速排序

■选择排序

(1)直接选择排序
(2)堆排序

■归并排序
■基数排序

例 在待排序的元素序列基本有序的前提下, 效率最高的排序方法是 。 A. 插入排序 C. 快速排序 B. 选择排序 D. 归并排序

解 插入排序是将待排序的记录插入到前面已 排好序的子区间中,即考虑已排好序的子区间。 本题答案为A。

例 快速排序在最坏情况下时间复杂度是O(n2), 比 的性能差。
A. 堆排序 B. 冒泡排序

C. 直接选择排序
解 A。

D. 直接插入排序

强调各种排序方法的比较 ? 是否需要比较 ? 排序方法的区别 ? 时间复杂度 ? 空间复杂度

模块4:其他

3. 外排序
(1)外排序的基本步骤 ■ 产生初始归并段 ■ 归并

模块4:其他
(2)磁盘排序
■ 利用选择置换算法产生初始归并段

■ 利用最佳归并树进行归并,其中用败 者树产生最小记录

模块4:其他

4. 文件
■ 文件的特点 ■ 各种类型的文件组织结构

考试题型
总分75分
单项选择题20分

问答题30分
算法设计题25分




友情链接: year2525网 工作范文网 QS-ISP 138资料网 528200 工作范文网 baothai 表格模版