数据结构（C语言版）（第2版）课后习题答案

data 出队访问结点
if(p>lchild && p>rchild ||p>lchild && p>rchild)num++
度1结点
if(p>lchild) QueueIn(Qp>lchild) 非空左子女入队
if(p>rchild) QueueIn(Qp>rchild) 非空右子女入队
} while(QueueEmpty(Q))
}if(bt)
return(num)
}返回度1结点数

（7）求意二叉树中第条长路径长度输出路径结点值
[题目分析]序遍历栈中保留前结点祖先信息变量保存栈高栈顶指针退栈时栈顶指针高保存高栈顶指针值时该栈倒入辅助栈中辅助栈始终保存长路径长度结点直序遍历完毕辅助栈中容求
[算法描述]
void LongestPath(BiTree bt)求二叉树中第条长路径长度
{BiTree pbtl[]s[]
l s栈元素二叉树结点指针l中保留前长路径中结点
int itop0tag[]longest0
while(p || top>0)
{while(p) {s[++top]ptag[top]0 pp>Lc} 左分枝
if(tag[top]1) 前结点右分枝已遍历
{if(s[top]>Lc && s[top]>Rc) 叶子结点时查路径长度
if(top>longest)
{for(i1i保留前长路径l栈记住高栈顶指针退栈
}
else if(top>0) {tag[top]1 ps[top]Rc} 右子分枝
}while(pnull||top>0)
}结束LongestPath

（8）输出二叉树中叶子结点根结点路径
[题目分析]采先序遍历递方法找叶子结点*b时*b叶子结点尚未添加path中输出路径时需输出b>data值
[算法描述]
void AllPath(BTNode *bElemType path[]int pathlen)
{int i
if (bNULL)
{if (b>lchildNULL && b>rchildNULL) *b叶子结点
{cout << << b>data << 根结点路径 << b>data
for (ipathlen1i>0i)
cout << endl
}
else
{path[pathlen]b>data 前结点放入路径中
pathlen++ 路径长度增1
AllPath(b>lchildpathpathlen) 递扫描左子树
AllPath(b>rchildpathpathlen) 递扫描右子树
pathlen 恢复环境
}
} if (bNULL)
}算法结束



第6章 图

1．选择题
（1）图中顶点度数等图边数（ ）倍
A．12 B．1 C．2 D．4
答案：C
（2）图中顶点入度等顶点出度（ ）倍
A．12 B．1 C．2 D．4
答案：B
解释：图顶点入度等顶点出度
（3）具n顶点图（ ）条边
A．n B．n(n1) C．n(n+1) D．n2
答案：B
解释：图边方分n顶点中选取2顶点序排列结果n(n1)
（4）n顶点连通图邻接距阵表示时该距阵少（ ）非零元素
A．n B．2(n1) C．n2 D．n2
答案：B
（5）G非连通图28条边该图少（ ）顶点
A．7 B．8 C．9 D．10
答案：C
解释：8顶点图8*7228条边添加点构成非连通图少9顶点
（6）图意顶点出发进行次深度优先搜索访问图中顶点该图定（ ）图
A．非连通 B．连通 C．强连通 D．
答案：B
解释：该图意顶点出发顶点路径该图连通图
（7）面（　）算法适合构造稠密图G生成树
A． Prim算法 B．Kruskal算法 C．Floyd算法 D．Dijkstra算法
答案：A
解释：Prim算法适合构造稠密图G生成树Kruskal算法适合构造稀疏图G生成树
（8）邻接表表示图进行广度优先遍历时通常助（ ）实现算法
A．栈 B 队列 C 树 D．图
答案：B
解释：广度优先遍历通常助队列实现算法深度优先遍历通常助栈实现算法
（9）邻接表表示图进行深度优先遍历时通常助（ ）实现算法
A．栈 B 队列 C 树 D．图
答案：A
解释：广度优先遍历通常助队列实现算法深度优先遍历通常助栈实现算法
（10）深度优先遍历类似二叉树（ ）
A．先序遍历 B．中序遍历 C．序遍历 D．层次遍历
答案：A
（11）广度优先遍历类似二叉树（ ）
A．先序遍历 B．中序遍历 C．序遍历 D．层次遍历
答案：D
（12）图BFS生成树树高DFS生成树树高（ ）
A． B．相等 C．相等 D．相等
答案：C
解释：特殊图顶点图BFS生成树树高DFS生成树树高相等般图根图BFS生成树DFS树算法思想BFS生成树树高DFS生成树树高
（13）已知图邻接矩阵图630示顶点v0出发深度优先遍历结果（ ）

  图630 邻接矩阵
（14）已知图邻接表图631示顶点v0出发广度优先遍历结果（ ）深度优先遍历结果（ ）

图631 邻接表
A．0 1 3 2 B．0 2 3 1 C．0 3 2 1 D．0 1 2 3
答案：DD
（15）面（ ）方法判断出图否环
A．深度优先遍历 B．拓扑排序 C．求短路径 D．求关键路径
答案：B
2．应题
（1）已知图632示图请出：
① 顶点入度出度
② 邻接矩阵
③ 邻接表
④ 逆邻接表

  图632 图 图633 网
答案：

（2）已知图633示网请出：
① 邻接矩阵
② 邻接表
③ 生成树
答案：




① ③








②

a
→
b
4
→
c
3












b
→
a
4
→
c
5
→
d
5
→
e
9






c
→
a
3
→
b
5
→
d
5
→
h
5






d
→
b
5
→
c
5
→
e
7
→
f
6
→
g
5
→
h
4
e
→
b
9
→
d
7
→
f
3









f
→
d
6
→
e
3
→
g
2









g
→
d
5
→
f
2
→
h
6










（3）已知图邻接矩阵图634示试分画出顶点1出发进行遍历深度优先生成树广度优先生成树
图628 邻接矩阵







（4）网图635示试迪杰斯特拉算法求出顶点a顶点间短路径完成表69

  图634 邻接矩阵 图635 网
表69
D
终点
i1
i2
i3
i4
i5
i6
b
15
(ab)
15
(ab)
15
(ab)
15
(ab)
15
(ab)
15
(ab)
c
2
(ac)





d
12
(ad)
12
(ad)
11
(acfd)
11
(acfd)


e
∞

10
(ace)
10
(ace)



f
∞

6
(acf)




g
∞

∞

16
(acfg)
16
(acfg)
14
(acfdg)

S
终点集
{ac}
{acf}
{acfe}
{acfed}
{acfedg}
{acfedgb}

（5）试图636示AOE网：
① 求工程早什时间结束
② 求活动早开始时间迟开始时间
③ 确定活动关键活动

图636 AOE网




答案：拓扑序序计算顶点早开始时间Ve迟允许开始时间Vl然计算活动早开始时间e迟允许开始时间l根l e 0 确定关键活动确定关键路径


1 ¶
2 ¸
3 ·
4 ¹
5 º
6 »
Ve
0
19
15
29
38
43
Vl
0
19
15
37
38
43


<1 2>
<1 3>
<3 2>
<2 4>
<2 5>
<3 5>
<4 6>
<5 6>
e
0
0
15
19
19
15
29
38
l
17
0
15
27
19
27
37
38
e
17
0
0
8
0
12
8
0
工程早完成时间43关键路径<1 3><3 2><2 5><5 6>

3．算法设计题
（1）分邻接矩阵邻接表作存储结构实现图基操作：
① 增加新顶点vInsertVex(G v)
② 删顶点v相关边DeleteVex(G v)
③ 增加条边InsertArc(G v w)
④ 删条边DeleteArc(G v w)
[算法描述]
假设图G权图邻接矩阵作存储结构四算法分：
① 增加新顶点v
Status Insert_Vex(MGraph &G char v)邻接矩阵表示图G插入顶点v
{
if(Gvexnum+1)>MAX_VERTEX_NUM return INFEASIBLE
Gvexs[++Gvexnum]v
return OK
}Insert_Vex

② 删顶点v相关边
Status Delete_Vex(MGraph &Gchar v)邻接矩阵表示图G删顶点v
{
nGvexnum
if((mLocateVex(Gv))<0) return ERROR
Gvexs[m]<>Gvexs[n] 删顶点交换顶点
for(i0i{
Garcs[m]Garcs[n]
Garcs[m]Garcs[n] 边关系交换
}
Garcs[m][m]adj0
Gvexnum
return OK
}Delete_Vex
分析果删顶点交换顶点话算法会较复杂伴着量元素移动时间复杂度会增加

③ 增加条边
Status Insert_Arc(MGraph &Gchar vchar w)邻接矩阵表示图G插入边(vw)
{
if((iLocateVex(Gv))<0) return ERROR
if((jLocateVex(Gw))<0) return ERROR
if(ij) return ERROR
if(Garcs[j]adj)
{
Garcs[j]adj1
Garcnum++
}
return OK
}Insert_Arc

④ 删条边
Status Delete_Arc(MGraph &Gchar vchar w)邻接矩阵表示图G删边(vw)
{
if((iLocateVex(Gv))<0) return ERROR
if((jLocateVex(Gw))<0) return ERROR
if(Garcs[j]adj)
{
Garcs[j]adj0
Garcnum
}
return OK
}Delete_Arc

邻接表作存储结构题出Insert_Arc算法余算法类似
Status Insert_Arc(ALGraph &Gchar vchar w)邻接表表示图G插入边(vw)
{
if((iLocateVex(Gv))<0) return ERROR
if((jLocateVex(Gw))<0) return ERROR
pnew ArcNode
p>adjvexjp>nextarcNULL
if(Gverticesfirstarc) Gverticesfirstarcp
else
{
for(qGverticesfirstarcq>q>nextarcqq>nextarc)
if(q>adjvexj) return ERROR 边已存
q>nextarcp
}
Garcnum++
return OK
}Insert_Arc

（2）连通图采邻接表作存储结构设计算法实现顶点v出发深度优先遍历非递程
[算法描述]
Void DFSn(Graph Gint v)
{ 第v顶点出发非递实现深度优先遍历图G
Stack s
SetEmpty(s)
Push(sv)
While(StackEmpty(s))
{ 栈空时第v顶点连通分量已遍历完
Pop(sk)
If(visited[k])
{ visited[k]TRUE
VisitFunc(k) 访问第k顶点
第k顶点邻接点进栈
for(wFirstAdjVex(Gk)wwNextAdjVex(Gkw))
{
if(visited[w]&&wGetTop(s)) Push(sw) 图中环时wGetTop(s)
}
}
}

（3）设计算法求图G中距离顶点v短路径长度顶点设v达余顶点
[题目分析]
利Dijkstra算法求v0顶点短路径分保存数组D[i]中然求出D[i]中值数组标m
[算法描述]
int ShortestPath_MAX(AMGraph G int v0){
Dijkstra算法求距离顶点v0短路径长度顶点m
nGvexnum nG中顶点数
for(v 0 v S[v] false S初始空集
D[v] Garcs[v0][v] v0终点短路径长度初始化
if(D[v]< MaxInt) Path [v]v0 果v0v间弧v前驱置v0
else Path [v]1 果v0v间弧v前驱置1
}for
S[v0]true v0加入S
D[v0]0 源点源点距离0
*开始循环次求v0某顶点v短路径v加S集*
for(i1i min MaxInt
for(w0w if(S[w]&&D[w] {vw minD[w]} 选择条前短路径终点v
S[v]true v加入S
for(w0w if(S[w]&&(D[v]+Garcs[v][w] D[w]D[v]+Garcs[v][w] 更新D[w]
Path [w]v 更改w前驱v
}if
}for
*短路径求解完毕设距离顶点v0短路径长度顶点m *
MaxD[0]
m0
for(i1i if(Maxreturn m
}
（4）试基图深度优先搜索策略写算法判邻接表方式存储图中否存顶点vi顶点vj路径（i≠j）
[题目分析]
引入变量level控制递进行层数
[算法描述]
int visited[MAXSIZE] 指示顶点否前路径
int level＝1递进行层数
int exist_path_DFS(ALGraph Gint iint j)深度优先判断图G中顶点i顶点j
否路径返回1否返回0
{
if(ij) return 1 ij
else
{
visited[i]1
for(pGvertices[i]firstarcppp>nextarclevel)
{ level++
kp>adjvex
if(visited[k]&&exist_path(kj)) return 1i游顶点j路径
}for
}else
if (level1) return 0
}exist_path_DFS
（5）采邻接表存储结构编写算法判图中意定两顶点间否存条长度k简单路径
[算法描述]
int visited[MAXSIZE]
int exist_path_len(ALGraph Gint iint jint k)
判断邻接表方式存储图G顶点ij否存长度k简单路径
{if(ij&&k0) return 1 找条路径长度符合求
else if(k>0)
{visited[i]1
for(pGvertices[i]firstarcppp>nextarc)
{lp>adjvex
if(visited[l])
if(exist_path_len(Gljk1)) return 1 剩余路径长度减
}for
visited[i]0 题允许访问结点出现条路径中
}else
return 0 没找
}exist_path_len

























第7章 查找
1．选择题
（1）n元素表做序查找时查找元素概率相均查找长度（ ）
A．(n1)2 B． n2 C．(n+1)2 D．n
答案：C
解释：总查找次数N1+2+3+…+nn(n+1)2均查找长度Nn(n+1)2
（2）适折半查找表存储方式元素排列求（ ）
A．链接方式存储元素序 B．链接方式存储元素序
C．序方式存储元素序 D．序方式存储元素序
答案：D
解释：折半查找求线性表必须采序存储结构表中元素关键字序排列
（3）果求线性表较快查找适应动态变化求采( )查找法
A．序查找 B．折半查找
C．分块查找 D．哈希查找
答案：C
解释：分块查找优点：表中插入删数元素时找该元素应块该块进行插入删运算块序插入删较容易需进行量移动果线性表快速查找常动态变化采分块查找
（4）折半查找序表（4610122030507088100）查找表中元素58次表中（ ）较查找结果失败
A．20703050 B．30887050
C．2050 D．308850
答案：A
解释：表中10元素第次取ë(1+10)2û5第五元素20较5820取ë(6+10)2û8第八元素70较次类推3050较终查找失败
（5）22记录序表作折半查找查找失败时少需较（ ）次关键字
A．3 B．4 C．5 D．6
答案：B
解释：22记录序表折半查找判定树深度 ëlog222û + 15该判定树满二叉树查找失败时较5次少较4次
（6）折半搜索二叉排序树时间性（ ）
A．相 B．完全
C．时相 D．数量级O(log2n)
答案：C
（7）分列序列构造二叉排序树三序列构造结果（ ）
A．（10080 90 60 120110130）
B．（10012011013080 60 90）
C．（10060 80 90 120110130）
D．(10080 60 90 120130110)
答案：C
解释：ABCD四选项构造二叉排序树100根易知ABD三序列中第100关键字80100左孩子80C选项中100左孩子60选C
（8）衡二叉树中插入结点造成衡设低衡结点A已知A左孩子衡子0右孩子衡子1应作（ ）型调整衡
A．LL B．LR C．RL D．RR
答案：C
（9）列关m阶B树说法错误（ ）
A．根结点m棵子树
B．叶子层次
C．非叶结点少m2 (m偶数)m2+1（m奇数）棵子树
D．根结点中数序
答案：D
（10）面关BB+树叙述中正确（ ）
A．B树B+树衡叉树 B．B树B+树文件索引结构
C．B树B+树效支持序检索 D．B树B+树效支持机检索
答案：C
（11）m阶B树棵（ ）
A．m叉排序树 B．m叉衡排序树
C．m1叉衡排序树 D．m+1叉衡排序树
答案：B
（12）面关哈希查找说法正确（ ）
A．哈希函数构造越复杂越样机性突
B．留余数法哈希函数中
C．存特坏哈希函数视情况定
D．哈希表均查找长度时记录总数关
答案：C
（13）面关哈希查找说法正确（ ）
A．采链址法处理突时查找元素时间相
B．采链址法处理突时插入规定总链首插入元素时间相
C．链址法处理突会引起二次聚集现象
D．链址法处理突适合表长确定情况
答案：A
解释：义词构成单链表中查找该单链表表中元素消耗时间
（14）设哈希表长14哈希函数H(key)key11表中已数关键字15386184四现关键字49元素加表中二次探测法解决突放入位置（ ）
A．8 B．3 C．5 D．9
答案：D
解释：关键字15放入位置4关键字38放入位置5关键字61放入位置6关键字84放入位置7添加关键字49计算址5突二次探测法解决突新址6突二次探测法解决突新址4突二次探测法解决突新址9突关键字49放入位置9
（15）采线性探测法处理突探测位置查找成功情况探测位置关键字 ( )
A．定义词 B．定义词
C．定义词 D．相
答案：A
解释：探测关键字处理关键字突程中放入该位置

2．应题
（1）假定序表：（34572430425463728795）进行折半查找试回答列问题：
① 画出描述折半查找程判定树
② 查找元素54需次元素较？
③ 查找元素90需次元素较？
④ 假定元素查找概率相等求查找成功时均查找长度
答案：
①先画出判定树（注：midë(1+12)2û6）：
30
5 63
3 7 42 87
4 24 54 72 95
②查找元素54需次30 63 42 54 元素较
③查找元素90需次30 6387 95元素较
④求ASL前需统计元素查找次数判定树前3层查找1＋2×2＋4×317次
层未满8×45×420次
ASL＝112（17＋20）＝3712≈308

（2）棵空二叉排序树中次插入关键字序列1271711162139214请画出二叉排序树
答案：
12
7 17
2 11 16 21
4 9 13
验算方法： 中序遍历应排序结果：2479111213161721

（3）已知示长度12表：（Jan Feb Mar Apr May June July Aug Sep Oct Nov Dec）
① 试表中元素序次插入棵初始空二叉排序树画出插入完成二叉排序树求等概率情况查找成功均查找长度
② 表中元素先进行排序构成序表求等概率情况序表进行折半查找时查找成功均查找长度
③ 表中元素序构造棵衡二叉排序树求等概率情况查找成功均查找长度
答案：

（4）图731示3阶B树次执行列操作画出步操作结果
① 插入90 ② 插入25 ③ 插入45 ④ 删60

图731 3阶B树






（5）设哈希表址范围0～17哈希函数：H（key）key16线性探测法处理突输入关键字序列：（1024321731304647406349）构造哈希表试回答列问题：
① 画出哈希表示意图
② 查找关键字63需次关键字进行较？
③ 查找关键字60需次关键字较？
④ 假定关键字查找概率相等求查找成功时均查找长度
答案：
①画表：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49




24
40
10



30
31
46
47
②查找63首先H(63)631615号单元容较6331较 匹配
然移4647321763相较6次
③查找60首先H(60)601612号单元容较12号单元空（应空标记）应较次
④黑色数元素较1次6次
红色元素相统计移位位数63需6次49需3次40需2次46需3次47需3次
ASL111（6＋2＋3×3+6）＝2311

（6）设组关键字（901231455208427）采哈希函数：H（key）key 7 表长10开放址法二次探测法处理突求：该关键字序列构造哈希表计算查找成功均查找长度
答案：
散列址
0
1
2
3
4
5
6
7
8
9
关键字
14
1
9
23
84
27
55
20
 
 
较次数
1
1
1
2
3
4
1
2
 
 
均查找长度：ASLsucc（1+1+1+2+3+4+1+2）8158
关键字27例：H（27）2776（突） H1（6+1）107（突）
H2（6+22）100（突） H3（6+33）105 较4次

（7）设哈希函数H（K）3 K mod 11哈希址空间0～10关键字序列（321349243821412）述两种解决突方法构造哈希表分求出等概率查找成功时查找失败时均查找长度ASLsuccASLunsucc
① 线性探测法
② 链址法
答案：
①
散列址
0
1
2
3
4
5
6
7
8
9
10
关键字
 
4
 
12
49
38
13
24
32
21
 
较次数
 
1
 
1
1
2
1
2
1
2
 
ASLsucc （1+1+1+2+1+2+1+2）8118
ASLunsucc（1+2+1+8+7+6+5+4+3+2+1）114011

②

ASLsucc （1*5+2*3）8118
ASLunsucc（1+2+1+2+3+1+3+1+3+1+1）111911

3．算法设计题
（1）试写出折半查找递算法
[算法描述]
int BinSrch（rectype r[ ]int klowhigh）
长n序表中查找关键字k查找成功返回k位置查找失败返回0
{if（low≤high） lowhigh分序表界界
{mid（low+high）2
if（r[mid]keyk）return （mid）
else if（r[mid]key>k）return （BinSrch（rkmid+1high））
else return （BinSrch（rklowmid1））
}
else return （0）查找失败
}算法结束
（2）试写判定二叉树否二叉排序树算法
[题目分析] 根二叉排序树中序遍历结点值增序性质遍历中前遍历结点前驱结点值较出结设全局指针变量pre（初值null）全局变量flag初值true非二叉排序树置flagfalse
[算法描述]
#define true 1
#define false 0
typedef struct node
{datatype data struct node *lchild*rchild} *BTree
void JudgeBST（BTree Tint flag）
判断二叉树否二叉排序树算法结束调程序中flag出结
{ if（Tnull && flag）
{ Judgebst（T>lchildflag） 中序遍历左子树
if（prenull）preT 中序遍历第结点必判断
else if（pre>datadata）preT前驱指针指前结点
else{flagflase} 完全二叉树
Judgebst （T>rchildflag） 中序遍历右子树
}JudgeBST算法结束

（3）已知二叉排序树采二叉链表存储结构根结点指针T链结点结构（lchilddatarchild）中lchildrchild分指该结点左右孩子指针data域存放结点数信息请写出递算法输出二叉排序树中数值>x结点数求先找第满足条件结点次输出满足条件结点
[题目分析]题算法题样中序遍历二叉树访问根结点处判断结点值否≥x输出记住第≥x值结点指针里出算法利二叉排序树性质果根结点值>x左分枝中 void Print（BSTree t）
中序输出t根二叉排序树结点
{if（t）{Print（t>lchild）
Cout< Print（t>rchild）
}
}
void PrintAllx(BSTree bstdatatype x）
二叉排序树bst中查找值≥x结点输出
{pbst
if（p）
{while（p && p>datarchild右分枝找第值≥x结点
bstp bst指结点值≥x结点树根
if（p）
{fp pp>lchild 找第值 while（p && p>data≥x）左分枝找第值 {fppp>lchild } fp双亲结点指针指第值≥x结点
if(p) f>lchildnull 双亲找第值Print(bst)输出bst根子树
}while
}层if（p）
}第层if（p）
}PrintAllx

（4）已知二叉树T结点形式（llingdatacountrlink）树中查找值X结点找记数（count）加1否作新结点插入树中插入二叉排序树写出非递算法
[算法描述]
void SearchBST(BiTree &Tint target){
BiTree sqf 数值target新建结点s
snew BiTNode
s>dataxtarget
s>datacount0
s>lchilds>rchildNULL

if(T){
Ts
return
} 果该树空跳出该函数
fNULL
qT
while (q){
if (q>dataxtarget){
q>datacount++
return
} 果找该值计数加
fq
if (q>datax>target) 果查找值目标值该树左孩子
qq>lchild
else 否右孩子
qq>rchild
} 新结点插入树中
if(f>datax>target)
f>lchilds
else
f>rchilds
}
（5）假设棵衡二叉树结点表明衡子b试设计算法求衡二叉树高度
[题目分析] 二叉树结点已标明衡子b根结点开始记树层次根结点层次1层层次加1直层数叶子结点衡二叉树高度结点衡子b0时选左右分枝查找b0左（b1时）右（b1时）查找
[算法描述]
int Height（BSTree t）
求衡二叉树t高度
{level0pt
while（p）
{level++ 树高度增1
if（p>bf<0）pp>rchildbf1 右分枝
bf衡子二叉树t结点域篇幅限没写出存储定义
else pp>lchild bf>0 左分枝
}while
return （level）衡二叉树高度
} 算法结束

（6）分写出散列表中插入删关键字K记录算法设散列函数H解决突方法链址法
[算法描述]
bool insert(){
int data
cin>>data
int anthash(data)
LinkList pHT[ant] 初始化散列表
while (p>next){
if(p>next>datadata)
return false
pp>next
} 找插入位置
LinkList s
snew LNode
s>datadata
s>nextp>next
p>nexts 插入该结点
return true
}

bool deletes(){
int data
cin>>data
int anthash(data)
LinkList pHT[ant] 初始化散列表
while (p>next){
if(p>next>datadata){
LinkList sp>next
p>nexts>next
delete s 删该结点
return true
} 找删位置
pp>next 遍历结点
}
return false
}




第8章 排序
1．选择题
（1）未排序序列中次取出元素已排序序列中元素进行较放入已排序序列正确位置方法种排序方法称（ ）
A．排序 B．泡排序 C．插入排序 D．选择排序
答案：C
（2）未排序序列中挑选元素次放入已排序序列（初始时空）端方法称（ ）
A．排序 B．泡排序 C．插入排序 D．选择排序
答案：D
（3）n关键字进行泡排序列（ ）情况较次数
A．排列 B．排列
C．元素序 D．元素基序
答案：B
解释：关键字进行泡排序关键字逆序时较次数
（4）n排序码进行泡排序元素序情况较次数（ ）
A．n+1 B．n C．n1 D．n(n1)2
答案：D
解释：较次数时第次较n1次第二次较n2次……次较1次(n1)+(n2)+…+1 n(n1)2
（5）快速排序列（ ）情况易发挥长处
A．排序数中含相排序码
B．排序数已基序
C．排序数完全序
D．排序数中值值相差悬殊
答案：C
解释：B选项快速排序坏情况
（6）n关键字作快速排序坏情况算法时间复杂度（ ）
A．O(n) B．O(n2) C．O(nlog2n) D．O(n3)
答案：B
解释：快速排序均时间复杂度O(nlog2n)坏情况关键字基排序情况时间复杂度O(n2)
（7）组记录排序码（46 7956384084）利快速排序方法第记录基准次划分结果（ ）
A．384046567984 B．403846795684
C．403846567984 D．403846845679
答案：C
（8）列关键字序列中（ ）堆
A．167231239453 B．942331721653
C．165323943172 D．162353319472
答案：D
解释：D选项根堆
（9）堆种（ ）排序
A．插入 B．选择 C．交换 D．
答案：B
（10）堆形状棵（ ）
A．二叉排序树 B．满二叉树 C．完全二叉树 D．衡二叉树
答案：C
（11）组记录排序码（467956384084）利堆排序方法建立初始堆（ ）
A．794656384084 B．847956384046
C．847956464038 D．845679404638
答案：B
（12）述种排序方法中求存（ ）
A．希尔排序 B．快速排序 C．排序 D．堆排序
答案：C
解释：堆排序希尔排序空间复杂度O(1)快速排序空间复杂度O(log2n)排序空间复杂度O(n)
（13）述种排序方法中（ ）稳定排序方法
A．希尔排序 B．快速排序 C．排序 D．堆排序
答案：C
解释：稳定排序希尔排序简单选择排序快速排序堆排序稳定排序直接插入排序折半插入排序泡排序排序基数排序
（14）数表中10000元素果仅求求出中10元素采( )算法节省时间
A．泡排序 B．快速排序 C．简单选择排序 D．堆排序
答案：D
（15）列排序算法中（ ）保证趟排序少元素放终位置
A．希尔排序 B．快速排序 C．泡排序 D．堆排序
答案：A
解释：快速排序趟排序作枢轴元素放终位置泡排序趟排序元素放终位置堆排序趟排序元素放终位置
2．应题
（1）设排序关键字序列{1221630281016*20618}试分写出排序方法趟排序结束关键字序列状态
① 直接插入排序
② 折半插入排序
③ 希尔排序（增量选取531）
④ 泡排序
⑤ 快速排序
⑥ 简单选择排序
⑦ 堆排序
⑧ 二路排序
答案：
①直接插入排序
[2 12] 16 30 28 10 16* 20 6 18
[2 12 16] 30 28 10 16* 20 6 18
[2 12 16 30] 28 10 16* 20 6 18
[2 12 16 28 30] 10 16* 20 6 18
[2 10 12 16 28 30] 16* 20 6 18
[2 10 12 16 16* 28 30] 20 6 18
[2 10 12 16 16* 20 28 30] 6 18
[2 6 10 12 16 16* 20 28 30] 18
[2 6 10 12 16 16* 18 20 28 30]

② 折半插入排序 排序程①

③ 希尔排序（增量选取531）
10 2 16 6 18 12 16* 20 30 28 （增量选取5）
6 2 12 10 18 16 16* 20 30 28 （增量选取3）
2 6 10 12 16 16* 18 20 28 30 （增量选取1）

④ 泡排序
2 12 16 28 10 16* 20 6 18 [30]
2 12 16 10 16* 20 6 18 [28 30]
2 12 10 16 16* 6 18 [20 28 30]
2 10 12 16 6 16* [18 20 28 30]
2 10 12 6 16 [16* 18 20 28 30]
2 10 6 12 [16 16* 18 20 28 30]
2 6 10 [12 16 16* 18 20 28 30]
2 6 10 12 16 16* 18 20 28 30]

⑤ 快速排序
12 [6 2 10] 12 [28 30 16* 20 16 18]
6 [2] 6 [10] 12 [28 30 16* 20 16 18 ]
28 2 6 10 12 [18 16 16* 20 ] 28 [30 ]
18 2 6 10 12 [16* 16] 18 [20] 28 30
16* 2 6 10 12 16* [16] 18 20 28 30
左子序列递深度1右子序列递深度3

⑥ 简单选择排序
2 [12 16 30 28 10 16* 20 6 18]
2 6 [16 30 28 10 16* 20 12 18]
2 6 10 [30 28 16 16* 20 12 18]
2 6 10 12 [28 16 16* 20 30 18]
2 6 10 12 16 [28 16* 20 30 18]
2 6 10 12 16 16* [28 20 30 18]
2 6 10 12 16 16* 18 [20 30 28]
2 6 10 12 16 16* 18 20 [28 30]
2 6 10 12 16 16* 18 20 28 [30]


⑧ 二路排序
2 12 16 30 10 28 16 * 20 6 18
2 12 16 30 10 16* 20 28 6 18
2 10 12 16 16* 20 28 30 6 18
2 6 10 12 16 16* 18 20 28 30

（2）出关键字序列｛3211565746287331333463｝试链式基数排序方法列出趟分配收集程
答案：
低位优先法 →321→156→57→46→28→7→331→33→34→63
分配 [0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
321 33 34 156 57 28
331 63 46 7
收集 →321→331→33→63→34→156→46→57→7→28
（3）输入文件（101511961371311719100552093050690）k6时置换选择算法写出建立初始败者树生成初始段
答案：
初始败者树   
2

5

71

4

0

3

1

3

1

61

1

19

1

51

1

101

1

1

 
 
 









初始段：R131931516171100101
R2917192030505590
R36

3．算法设计题
（1）试单链表存储结构实现简单选择排序算法
[算法描述]：
void LinkedListSelectSort(LinkedList head)
算法趟找出关键字结点数前结点进行交换交换指针须记
前结点结点前驱指针
phead>next
while(pnull)
{qp>next rp 设r指关键字结点指针
while (qnull)
{if(q>datadata) rq
qq>next
}
if(rp) r>data<>p>data
pp>next
}

（2）n记录存储带头结点双链表中现双泡排序法升序进行排序请写出种排序算法（注：双泡排序相邻两趟排序相反方泡）
[算法描述]：
typedef struct node
{ ElemType data
struct node *prior*next
}node*DLinkedList
void TwoWayBubbleSort(DLinkedList la)
存储带头结点双链表la中元素进行双起泡排序
{int exchange1 设标记
DLinkedList ptemptail
headla 双链表头算法程中起泡开始结点
tailnull 双链表尾算法程中起泡开始结点
while (exchange)
{phead>next p工作指针指前结点
exchange0 假定趟交换
while (p>nexttail) （右）起泡趟元素沉底
if (p>data>p>next>data) 交换两结点指针涉6条链
{tempp>next exchange1交换
p>nexttemp>nexttemp>next>priorp 先结点链表摘
temp>nextp p>prior>nexttemp temp插p结点前
temp>priorp>prior p>priortemp
}
else pp>next 交换指针移
tailp 准备起泡
ptail>prior
while (exchange && p>priorhead)
（左）起泡趟元素出
if (p>data

prior>data) 交换两结点指针涉6条链
{tempp>prior exchange1 交换
p>priortemp>priortemp>prior>nextp
先temp结点链表摘
temp>priorp p>next>priortemp temp插p结点（右）
temp>nextp>next p>nexttemp
}
else pp>prior 交换指针前移
headp 准备起泡
} while (exchange)
} 算法结束

（3）设序放置n桶桶中装粒砾石粒砾石颜色红白蓝求重新安排砾石红色砾石前白色砾石居中蓝色砾石居重新安排时粒砾石颜色次允许交换操作调整砾石位置
[题目分析]利快速排序思想解决求粒砾石颜色次设3指针ijk分指红色白色砾石位置处理前元素kn开始右左搜索该元素兰色元素动指针左移（k1）前元素红色砾石分i>j（时尚没白色砾石）i方便处理三种砾石颜色整数123表示
[算法描述]：
void QkSort(rectype r[]int n) {
r含n元素线性表元素具红白兰色砾石序存储结构存储
算法排序红色砾石前白色居中兰色
int i1j1kntemp
while (kj){
while (r[k]key3) k 前元素兰色砾石指针左移
if (r[k]key1) 前元素红色砾石
if (i>j){tempr[k]r[k]r[i]r[i]temp i++}
左侧红色砾石交换r[k]r[i]
else {tempr[j]r[j]r[i]r[i]temp j++
左侧已红色白色砾石先交换白色砾石位
tempr[k]r[k]r[i]r[i]temp i++
白色砾石（i指）定砾石（j指）
} 交换r[k]r[i]红色砾石入位
if (r[k]key2)
if (i 左侧已白色砾石交换r[k]r[j]
else { tempr[k]r[k]r[i]r[i]temp ji+1}
ij分指红白色砾石位置
}while
if (r[k]2) j++ * 处理粒砾石
else if (r[k]1) { tempr[j]r[j]r[i]r[i]temp i++ j++ }
红白兰色砾石数分 i1jinj+1
}结束QkSor算法
[算法讨]j（面指白色）作工作指针r[1j1]作红色r[jk1]白色r[kn]兰色j1开始查r[j]白色jj+1r[j]红色交换r[j]r[i]jj+1ii+1r[j]兰色交换r[j]r[k]kk1算法进行j>k止
算法片段：
int i1j1kn
while(j if (r[j]1) 前元素红色
{tempr[i] r[i]r[j] r[j]temp i++j++ }
else if (r[j]2) j++ 前元素白色
else (r[j]3 前元素兰色
{tempr[j] r[j]r[k] r[k]temp k }
两种算法出正确选择变量（指针）重性

（4）编写算法n关键字取整数值记录序列进行整理关键字负值记录排关键字非负值记录前求：
① 采序存储结构记录辅助存储空间
② 算法时间复杂度O(n)
[算法描述]
void process (int A[n]){
low 0
high n1
while ( lowwhile (lowlow++
while (low0)
high++
if (lowxA[low]
A[low]A[high]
A[high]x
low++
high
}
}
return
}

（5）助快速排序算法思想组序记录中查找定关键字值等key记录设组记录存放数组r[ln]中查找成功输出该记录r数组中位置值否显示not find信息请简说明算法思想编写算法
[题目分析]查记录作枢轴先前次较枢轴前直查找成功返回位置失败返回0止
[算法描述]
int index (RecType R[]int lhdatatype key)
{int iljh
while (i { while (ikey) j
if (R[j]keykey) return j
while (i if (R[i]keykey) return i
}
cout< }index

（6）种简单排序算法做计数排序种排序算法排序表进行排序排序结果存放新表中必须注意表中排序关键字互相计数排序算法针表中记录扫描排序表趟统计表中少记录关键字该记录关键字假设针某记录统计出计数值c记录新序表中合适存放位置c
① 出适计数排序序表定义
② 编写实现计数排序算法
③ n记录表关键字较次数少？
④ 简单选择排序相较种方法否更？什？
[算法描述]
① typedef struct
{int key
datatype info
}RecType
② void CountSort(RecType a[]b[]int n)
计数排序算法a中记录排序放入b中
{for(i0i{for(j0cnt0jif(a[j]keyb[cnt]a[i]
}
}Count_Sort
③ n记录表关键码较n2次
④ 简单选择排序算法算法简单选择排序较次数n(n1)2交换记录空间种方法较次数n2需数组空间
[算法讨]题目求针表中记录扫描排序表趟较次数n2次限制意两记录间应该进行次较算法中较语句改：
for(i0ifor(i0i for(ji+1j if(a[i]key
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档