1 理解数结构根概念掌握数逻辑结构存储结构差异种根操作实现
2 掌握根数处理原理方法根底够算法进行设计分析
3 够选择适宜数结构方法进行问题求解
线性表
纲求:
〔〕 线性表定义根操作
〔二〕 线性表实现
1 序存储结构
2 链式存储结构
3 线性表应
知识点:
1. 深刻理解数结构概念掌握数结构三素〞:逻辑结构物理〔存储〕结构种结构定义操作运算〞
2. 时间复杂度空间复杂度定义常计算语句频度估算算法时间复杂度
六种计算算法时间项式常关系:
O(1)
4. 序存储结构量〔维数组〕表示定标存取相应元素属机存取存储结构
5. 线性表序存储方式具体语言环境两种实现:表空间静态分配动态分配掌握序表实现插入删定位等运算算法
6. 知道某结点指针存取该元素〞链表存取需头指针开始链行链表属机存取结构理解头指针头结点首元结点元素结点差异头结点插入删等操作时算法统设立〔假设头结点第元素前插入元素删第元素时链表头指针总变化〕链表〔包括循环链表〕操作均头结点开始头结点指针具标记作头指针称链表名字链表head指链表头结点指针head理解循环链表中设置尾指针设置头指针处链表操作中应注意链意外断开〞假设某结点前插入元素删某元素必须知道该元素前驱结点指针
7. 链表局部学重点难点重点掌握种常链表特点运算:单链表循环链表双链表双循环链表生成插入删遍历链表分解等操作够设计出实现线性表运算算法
8. 时间复杂度空间复杂度角度综合拟线性表序链式两种存储结构特点适场合
结:
序表链表拟
通讨知优缺点序存储三优点:
〔1〕方法简单种高级语言中数组容易实现
〔2〕表示结点间逻辑关系增加额外存储开销
〔3〕序表具元素序号机访问特点
两缺点:
〔1〕序表中做插入删操作时均移动约表中半元素n较序表效率低
〔2〕需预先分配足够存储空间估计会导致序表部量闲置预先分配会造成溢出
链表优缺点恰序表相反
实际中样选取存储结构呢?
〔1〕基存储考虑
线性表长度存储规模难估计时宜采序表链表事先估计存储规模链表存储密度较低显然链式存储结构存储密度1
〔2〕基运算考虑
序表中序号访问ai时间性时O(1)链表中序号访问时间性O(n)果常做运算序号访问数元素显然序表优链表序表中做插入删时均移动表中半元素数元素信息量较表较长时点应视链表中作插入删然找插入位置操作拟操作角度考虑显然者优前者
〔3〕基环境考虑
序表容易实现高级语言中数组类型链表操作基指针相讲前者简单户考虑素
总两种存储结构长短选择种实际问题中素决定通常较稳定〞线性表选择序存储频繁做插入删动态性较强线性表宜选择链式存储
练题:
〔〕选择题:
1.术语数存储结构关?〔 A 〕
A.队列 B 哈希表
C 线索树 D 双链表
2算法应该〔 B 〕
A.程序 B.问题求解步骤描述
C.满足五根特性 D.AC
3数结构中计算机关数〔 C 〕
A.存储结构 B.物理结构 C.逻辑结构 D.物理结构存储结构
4 算法计算量称计算〔 B 〕
A.效率 B.复杂性 C.现实性 D.难度
5.说法正确选项〔D〕
A.数元素数根单位
B.数项数中分割标识单位
C.数假设干数元素构成
D.数项假设干数元素构成
6.连续存储设计时存储单元址〔 A 〕
A.定连续 B.定连续
C.定连续 D.局部连续局部连续
7 线性表〔 a1a2…an〕链接方式存储时访问第i位置元素时间复杂性〔 C 〕
A.O〔i〕 B.O〔1〕 C.O〔n〕 D.O〔i1〕
8 序存储线性表访问结点增加删结点时间复杂度〔 C 〕
A.O(n) O(n) B O(n) O(1)
C O(1) O(n) D O(1) O(1)
9 设单链表中结点结构〔datalink〕指针q指点指针p指结点直接前驱假设*q*p间插入结点*s应执行操作?〔 B 〕
A.s->linkp->linkp->links
B.q->linkss->linkp
C.p->links->links->linkp
D.p->linkss->linkq
10 长度n序表表尾插入新元素渐进时间复杂度〔 B 〕
A.O〔n〕 B.O〔1〕
C.O〔n2〕 D.O〔log2n〕
11 表长n序存储线性表位置插入元素概率相等时插入元素需移动元素均数〔 B 〕
A.n B n2
C (n1)2 D (n+1)2
12 循环链表优点〔 D 〕
A.需头指针
B.某结点位置容易找直接前驱结点
C.进行删操作保证链表断开
D.表中结点出发遍历整链表
〔二〕应题
1增长率排列7函数
答:
2数存储结构四种根存储方法实现做简说明?
答:四种表示方法
〔1〕序存储方式数元素序存放存储结点含元素存储位置反映数元素间逻辑关系存储密度操作〔插入删〕效率较差
〔2〕链式存储方式存储结点包含数元素信息外包含组〔少〕指针指针反映数元素间逻辑关系种方式求存储空间连续便动态操作〔插入删等〕存储空间开销〔指针〕外折半查找等
〔3〕索引存储方式数元素存储址连续存空间外尚需建立索引表索引表中索引指示存储结点存储位置〔标〕存储区间端点〔标〕兼静态动态特性
〔4〕散列存储方式通散列函数解决突方法关键字散列连续限址空间散列函数值解释成关键字元素存储址种存储方式称散列存储特点存取速度快关键字机存取序存取折半存取
3 线性表两种存储结构:序表二链表试问:
〔1〕果 n线性表时存处理程中表长度会动态变化线性表总数会动改变情况应选种存储结构? 什?
〔2〕假设线性表总数根稳定少进行插入删求快速度存取线性表中元素应采种存储结构?什?
答:
〔1〕选链式存储结构动态申请存空间受表长度〔表中元素数〕影响插入删时间复杂度O〔1〕
〔2〕选序存储结构序表机存取时间复杂度O〔1〕
〔三〕算法设计题
1.设计算法求带表头单循环链表表长
解:
int length(Linklist L)
{
int I
listnode *p
I0
PL
while (p>nextL){
pp>next
I++
}
return I
}
2单链表L写算法删重复结点
算法思路:指针p指第数结点继结点开始表结束找值相结点删p指类推p指结点时算法结束算法:
解:
void pur_LinkList(LinkList H)
{ LNode *p*q*r pH>next *p指第结点*
if(pNULL) return
while (p>next)
{qp
while (q>next) * *p继开始找重复结点*
{ if (q>next>datap>data)
{ rq>next *找重复结点r指删*r *
q>nextr>next
free(r)
} *if*
else qq>next
} *while(q>next)*
pp>next *p指继续*
} *while(p>next)*
}
该算法时间性O(n2)
3指针lalb分指两头结点单链表中首结点请编写函数完成表la中删第i元素开始len元素插入表lb中第j元素前假设lb中j1元素插表尾函数原型:
int DeleteAndInsertSub(LinkList &laLinkList &lbint iint jint len)
答:int DeleteAndInsertSub(LinkList &laLinkList &lbint iint jint len)
{
int k
LinkList pqprevs
if(i<0||j<0||len<0)
return 1
pla
k1
prevNULL
while(p&&k {
prevp
pp>next
k++
}
if(p)
return 1
qpk1
while(q&&k
qq>next
k++
}
if(q)
return 1
if(prev)
laq>next
else
prev>nextq>next
if(j1)
{
q>nextlb
lbq
}
else
{
slbk1
while(s&&k
ss>next
k++
}
if(s)
return 1
q>nexts>next
s>nextp
return 1
}
}
4.写算法带头结点单链表逆置求逆置原链表进行允许重新构造新链表
图 单链表倒置
25
∧
4525
18
76
29
L
29
∧
7625
18
45
25
L
(a)
(b)
函数原型:
void LinkList_reverse(LinkList &L)
答:void LinkList_reverse(LinkList &L)
{
LinkList pqs
pL>nextqp>nextsq>nextp>nextNULL
while(s>next)
{
q>nextppq
qsss>next
}
q>nextps>nextqL>nexts
}
5.写算法带头结点非空单链表中数域值结点移链表前面求:额外申请新链结点函数原型:
void delinsert(LinkList &L)
答:void delinsert(LinkList &L)
{
pL>next p链表工作指针
preL pre指链表中数域值结点前驱
qp q指数域值结点初始假定第结点
while(p>nextNULL)
{
if(p>next>data
data) 找新值结点
{ prep qp>next }
pp>next
}
if(qL>next) 假设值第元素结点需操作
{
pre>nextq>next 值结点链表摘
q>nextL>next q结点插链表前面
L>nextq
}
}
6.编写算法交换单链表中指针P指结点继结点HEAD该链表头指针P指该链表中某结点
答:单链表中查找结点必须头指针开始题求指针p指结点继结点交换仅求知道p结点应知道p前驱结点样p继结点交换原p结点前驱指原p结点继结点
LinkedList Exchange〔LinkedList HEADp〕
∥HEAD单链表头结点指针p链表中结点算法p指结点继结点交换
{qhead>next ∥q工作指针指链表中前处理结点
prehead ∥pre前驱结点指针指q前驱
while〔qnull && qp〕{preqqq>next} ∥未找p结点移指针
if〔p>nextnull〕printf〔p继结点\n〞〕 ∥p链表中结点继
Else ∥处理p继结点交换
{qp>next ∥暂存p继
pre>nextq ∥p前驱结点继指p继
p>nextq>next∥p继指原p继继
q>nextp ∥原p继继指针指p
}
}∥算法结束
7.线性链表第链结点指针list请写算法该链表分解两带头结点循环链表两循环链表长度分存放头结点数域中中线性表中序号偶数元素分解第循环链表中序号奇数元素分解第二循环链表中
答:算法:
void split(ListNode *List ListNode *&list1 ListNode *&list2)
{
list1(ListNode *)malloc(sizeof(ListNode ))
list2(ListNode *)malloc(sizeof(ListNode ))
plist
qlist1
rlist2
len10
len20
mark1
while (pnull)
{
if(mark1)
{
q>nextp
qq>next
len1++
mark2
}
else
{
r>nextp
rr>next
len2++
mark1
}
}
list1>datalen1
list2>datalen2
q>nextlist1
r>nextlist2
}
8 设AB两单链表表中元素递增序
试写算法AB成元素值递减序单链表C求辅助空间O(1)
答:Linklist merge(Linklist ALinklist B)
{
Linklist C
Listnode *p
Cnull
while (A&&B)
if(A>datadata)
{pA>nextA>nextCCAAp}
else
{pB>nextB>nextCCBBp}
if (A)
while(A) { pA>nextA>nextCCAAp}
else
while(B) {pB>nextB>nextCCBBp}
return C
}
二栈队列数组
纲求:
〔〕 栈队列根概念
〔二〕 栈队列序存储结构
〔三〕 栈队列链式存储结构
〔四〕 栈队列应
〔五〕 特殊矩阵压缩存储
知识点:
1. 栈队列定义相关数结构概念包括:序栈链栈循环队列链队列等栈队列存取数〔请注意包括:存取两局部〕特点
2. 掌握序栈链栈进栈退栈算法弄清栈空栈满条件注意栈端操作通常链栈设头结点
3. 中缀表达式转换成前缀缀表达式解两种表达式求值方法
4. 栈递关系递解决类问题:问题定义递数结构递问题解法递掌握典型问题算法递算法转换非递算法n阶问题fib数列问题hanoi问题解数值表达式求解括号配等问题中应栈工作原理
5. 掌握链队列实现入队出队算法注意仅剩元素链队列删元素时处理〔令队尾指针指队头〕需特注意仅设尾指针循环链队列种操作实现
6. 循环队列队空队满条件队空定义队头指针等队尾指针队满牺牲单元设标记方法里特注意取模运算掌握循环队列中入队出队算法
7. 续章节中处栈队列应二叉树遍历递非递算法图深度优先遍历等栈树层次遍历图广度优先遍历等队列方面应应重点掌握
8. 数组机器〔存〕级采序存储结构掌握数组〔二维〕行序列序存储中址计算方法
9. 特殊矩阵〔称矩阵角矩阵三角矩阵〕压缩存储标变换公式
练题:
〔〕选择题:
1 栈输入序列1 2 3 4〔 D 〕出栈序列
A 1 2 4 3 B 2 1 3 4 C 1 4 3 2 D 4 3 1 2
2 递算法必须包括〔 B 〕
A 递局部 B 终止条件递局部
C 迭代局部 D终止条件迭代局部
3 递定义递程求解非递程求解单运行时间通常递程非递程〔B〕
A.较快 B.较慢
C.相 D.答案
4 栈队列〔C〕
A.序存储线性表 B.链式存储线性表
C.限制存储线性表 D.限制存储非线性结构
5 二维数组N元素4字符〔字符占存储单元〕组成串行标i范围04列标j范围05N行存储时元素N[3][5]起始址N列存储时元素〔 B 〕起始址相
A N[2][4] B N[3][4]
C N[3][5] D N[4][4]
6 设数组A[ij]数组元素长度3字节i值18j值110数组存首址BA开始序存放列序存放时元素A[58]存储首址〔 B 〕
A BA+141 B BA+180
C BA+222 D BA+225
7 递程函数调时处理参数返回址种称〔 C 〕数结构
A.队列 B.维数组
C.栈 D 线性表
8 单链表形式队列队空条件〔 A 〕
A.F=R=nil B.F=R
C.F≠nilR=nil D.R-F=1
9 假设循环队列数组Q[0m1]作存储结构变量rear表示循环队列中队尾元素实际位置移动 rear(rear+1) Mod m 进行变量length表示前循环队列中元素数循环队列队首元素实际位置〔 C 〕
A.rearlength
B.(rearlength+m) Mod m
C.(1+rear+mlength) Mod m
D.Mlength
〔二〕应题
1〔10分〕假设准角矩阵
方式存储维数组B[4m]中:
0
1
2
3
4
k
4m-2
4m-1
写出标〔ij〕表示k转换公式
答:
i奇数时 ki+j2
i偶数时 ki+j1
合写成 ki+j(i2)1 k2(i2)+j1
2特殊矩阵稀疏矩阵种压缩存储失机存取功?什?
答:
特殊矩阵指值相元素零元素矩阵中分布定规律非零元素分配单元〔值相元素分配单元〕非零元素存储量中元素标ij该元素量中标定规律简单公式表示具机存取功
稀疏矩阵指非零元素矩阵容量相〔t<
3说采循环链表作存储结构队列循环队列认种说法?说明理
答:
种说法错误队列〔包括循环队列〕逻辑概念链表存储概念队列否循环队列取决采种存储结构根实际需循环队列采序存储结构采链式存储结构包括采循环链表作存储结构
4指出程序段功什?
(1) void demo1(seqstack *s)
{
int Iarr[64]n0
while (stackempty(s)) arr[n++]pop(s)
for(I0}
(2) void demo2(seqstack *sint m)
{
seqstack t int i
initstack(t)
while( Stackempty(s))
if(Ipop(s)m) push(tI)
while( Stackempty(t)) {
ipop(t)
push(sI)
}
}
〔三〕算法设计题
1. 试利循环队列编写求k阶斐波契序列中前n+1项〔〕算法求满足中max某约定常数循环队列容量k算法执行结束时留循环队列中元素应求k阶斐波契序列中k项
答:
void GetFib(int kint n)
{
InitQueue(Q)
for(i0kQbase[i]0
Qbase[k1]1
for(i0iprintf(d〞Qbase[i])
for(iki{
mik
sum0
for(j0jsum+Qbase[(m+j)k]
Qbase[m]sum
printf(d〞sum)
}
}
2 num符号十进制整数请写非递算法该算法输出num应r进制位数字求算法中栈采线性链表存储结构〔1解:
typedef struct node{
int data
struct node *next
}link
void trans(int numint r)
{ link *headNULL*s
int n
while (num>0)
{
nnumr
s(link *)malloc(sizeof(link))
s>datan
s>nextheadheads
numnumr
}
printf(输出r进制位数字:〞)
shead
while (sNULL)
{
printf(d〞s>data)
ss>next
}
}
三树二叉树
纲求:
〔〕 树概念
〔二〕 二叉树
1 二叉树定义特征
2 二叉树序存储结构链式存储结构
3 二叉树遍历
4 线索二叉树根概念构造
5 二叉排序树
6 衡二叉树
〔三〕 树森林
1 树存储结构
2 森林二叉树转换
3 树森林遍历
〔四〕 树应
1 等价类问题
2 哈夫曼〔Huffman〕树哈夫曼编码
知识点:
1 二叉树概念性质
〔1〕掌握树二叉树定义
〔2〕理解二叉树普通双分支树区二叉树种特殊树种特殊仅仅分支2特征重特殊处:二叉树序二叉树左右孩子交换果交换成外棵二叉树样交换二叉树原二叉树相两棵二叉树普通双分支树言具种性质
〔3〕满二叉树完全二叉树概念
〔4〕重点掌握二叉树五性质证明方法种方法推广K叉树普通二叉树五性质:第i层结点数深度k二叉树结点数n0n2+1性质n结点完全二叉树深度序存储二叉树时孩子结点父结点间换算关系〔序号i结点左孩子:2*i右孩子:2*i+1〕
2 掌握二叉树序存储结构二叉链表三叉链表存储结构优缺点适场合二叉树序存储结构二叉链表存储结构相互转换算法
3 熟练掌握二叉树先序中序序遍历算法层次遍历
二叉树先序中序序三种遍历算法划分视算法中根结点数访问序定仅熟练掌握三种遍历递算法理解执行实际步骤应该熟练掌握三种遍历非递算法
●层次遍历二叉树
void LayerOrder(Bitree T)层序遍历二叉树
{
InitQueue(Q) 建立工作队列
EnQueue(QT)
while(QueueEmpty(Q))
{
DeQueue(Qp)
visit(p)
if(p>lchild) EnQueue(Qp>lchild)
if(p>rchild) EnQueue(Qp>rchild)
}
}LayerOrder
4 遍历根底重点掌握三种根遍历算法根底实现二叉树算法
求二叉树叶子结点总数求二叉树结点总数求度1度2结点总数复制二叉树建立二叉树交换左右子树查找值n某指定结点删值n某指定结点等等
5 线索二叉树引出防止二叉树遍历时递求解递然形式拟理解消耗量存资源果递层次势必带资源耗危险二叉树线索化实质建立结点相应序列中前驱继间直接联系
线索二叉树应该掌握:线索化实质三种线索化算法线索化二叉树遍历算法根线索二叉树算法问题〔:查找某类线索二叉树中指定结点前驱继结点〕
6 二叉排序树中序遍历结果递增序序列二叉排序树形态取决元素输入序二叉排序树差情况形成单支树熟练掌握建立查找插入删算法判断某棵二叉树否二叉排序树问题递非递算法
7 衡二叉树二叉排序树优化衡二叉树左右子树深度限定:深度差绝值1掌握衡二叉树四种调整算法
8 树森林遍历两种遍历算法:先根根〔森林言称作:先序中序遍历〕二者先根根遍历二叉树中遍历算法应关系:先根遍历应二叉树先序遍历根遍历应二叉树中序遍历二叉树二叉链表分存放左右孩子树利二叉链表存储孩子兄弟〔称孩子兄弟链表〕森林利二叉链表存储孩子兄弟掌握树森林二叉树间相互转换
9 简单掌握等价类生成算法
10 哈夫曼树解决特定问题引出特殊二叉树结构前提二叉树条边赋予权值样形成二叉树权相加般说哈夫曼树形态唯理解哈夫曼编码根原理掌握基哈夫曼树生成哈夫曼编码方法
练题:
〔〕选择题:
1 棵二叉树前序遍历结果ABCDEF中序遍历结果CBAEDF序遍历结果〔 A 〕
A CBEFDA B FEDCBA
C CBEDFA D 确定
2 某二叉树序遍历序列dabec中序遍历序列debac前序遍历序列〔D〕
A.acbed B.decab
C.deabc D.cedba
3 具10叶子结点二叉树中〔 B〕度2结点
A 8 B 9
C 10 D 11
4 树中结点度等结点数加〔 C 〕
A.0 B.1
C.-1 D.2
5 设nm棵二叉树两结点中序遍历时nm前条件〔 C 〕
A nm右方 B nm祖先
C nm左方 D nm子孙
6 利逐点插入建立序列〔50724385752035456530〕应二叉排序树查找元素30进行〔 B 〕次元素间拟
A.4 B 5
C.6 D 7
7 衡二叉树中〔 C 〕
A.意结点左右子树结点数目相
B.意结点左右子树高度相
C.意结点左右子树高度差绝值1
D.存度1结点
8 元素序列〔2716753851〕构造衡二叉树首次出现衡子树根〔离插入结点衡子绝值2结点〕〔 D 〕
A.27 B.38
C.51 D 75
9 二叉树序存储中结点存储位置父结点左右子树结点位置存简单映射关系三叉链表应假设某二叉树n结点采三叉链表存储时结点数域需d字节指针域占4字节假设采序存储结点标k〔起始标1〕〔 A 〕时采序存储更节省空间
A.d<12n(kn) B d>12n(kn)
C d<12n(k+n) D d>12n(k+n)
10 常描述二叉排序树存储结构中关键字值结点〔 B 〕
A.左指针定空 B 右指针定空
C.左右指针均空 D 左右指针均空
〔二〕应题
1棵满k叉树层次遍历〔1开始全部结点进行编号〕存储维数组中试计算编号u结点第i孩子〔假设存〕标编号v结点双亲结点〔假设存〕标
答:
结点标u结点第i孩子标:
结点标v结点父母结点标:
2试求n叶结点非满完全二叉树高度
答:
完全二叉树中叶子结点数n根完全二叉树性质度2结点数n1完全二叉树中度1结点数1
具n叶子结点完全二叉树结点数n+(n1)+12n2n1〔度1结点〕
具2n(2n1)结点完全二叉树深度ëlog2(2n)û+1( ëlog2(2n1)û+1)élog2nù+1n叶结点非满完全二叉树高度élog2nù+1〔层结点数>2〕
3棵度m树中N1度1结点N2度2结点……Nm度m结点问该树中少叶子结点请写出推导程
答:设N总结点数N0叶子结点数:NN0+N1+N2+……+Nm
:N1度总数:N1N1*1+N2*2+……Nm*m
:N01+N2+2N3+……+(m1)Nm
4.七带权结点权值分378261014试叶子结点构造棵哈夫曼树计算出带权路径长度WPL
答:
WPL 3*4+7*3+8*3+2*4+6*3+10*2+14*2 131
5定字母abcde频率00901702023031设计该权值根底哈夫曼树出哈夫曼编码?均长度少?
答:
构造哈夫曼树:
c
c d e
a b
哈夫曼编码:
c(00)
d(01)
a(100)
b(101)
e(11)
均长度009*3+017*3+02*2+023*2+031*2226
6 概念讲树森林二叉树三种数结构树森林转化二叉树根目什指出树二叉树区
解:
树孩子兄弟链表表示法二叉树二叉链表表示法质样解释说树〔树森林特例森林中棵树特殊情况〕二叉树唯表示二叉树算法解决树森林中问题
树二叉树区:二叉树度2树限制二二叉树左右子树分分枝情况 必须指出左子树右子树树限制
7 果出二叉树结点前序序列中序序列否构造出二叉树假设请证明假设请出反例果出二叉树结点前序序列序序列否构造出二叉树假设请证明假设请出反例
解:
定二叉树前序序列中序序列唯确定该二叉树前序序列第元素根结点该元素二叉树中序序列分成两局部左边〔设l元素〕表示左子树假设左边元素说明左子树空右边〔设r元素〕右子树假设空右子树空根前序遍历中根—左子树—右子树〞序第二元素开始l结点序列中序序列根左边l结点序列构造左子树前序序列r元素序列中序序列根右边r元素序列构造右子树
二叉树前序序列序序列唯确定棵二叉树法确定左右子树两局部例结点左子树二叉树结点右子树二叉树前序序列相序序列相两棵二叉树
〔三〕算法设计题
1.请利栈根操作写出先序遍历二叉树非递形式算法求二叉链表作二叉树存储结构函数原型:
void PreOrder(Bitree T)
答:void PreOrder(Bitree T)
{
InitStack(S)
Push(ST)
while(StackEmpty(S))
{
while(Gettop(Sp)&&p)
{
visit(p>data)
push(Sp>lchild)
}
pop(Sp)
if(StackEmpty(S))
{
pop(Sp)
push(Sp>rchlid)
}
}
}
2.试写判定二叉树否二叉排序树递算法设二叉树二叉链表作存储结构树中结点关键字均函数原型:
int Is_BSTree〔BiTree T〕
答:int last0flag1
int Is_BSTree〔BiTree T〕
{
if(T>lchild&&flag) Is_BSTree(T>lchild)
if(T>datalastT>data
if(T>rchild&&flag) Is_BSTree(T>rchild)
return flag
}
3.假设仅包含二元运算符算术表达式链表形式存储二叉树BT中写出计算该算术表达式值算法
答:二叉树表示算术表达式根结点存储运算符假设先分求出左子树右子树表示子表达式值根根结点运算符求计算出表达式结果
typedef struct node
{
ElemType data float val
char optr 取+’ ’ *’’
struct node *lchild*rchild
}BiNode*BiTree
float PostEval(BiTree bt) 序遍历算法求二叉树表示算术表达式值
{
float lvrv
if(btnull)
{
lvPostEval(bt>lchild) 求左子树表示子表达式值
rvPostEval(bt>rchild) 求右子树表示子表达式值
switch(bt>optr)
{
case +’ valuelv+rv break
case ’ valuelvrvbreak
case *’ valuelv*rvbreak
case ’ valuelvrv
}
}
return(value)
}
4.设计算法 棵二叉链表存储二叉树root指根结点p指二叉树中结点编写算法求根结点p指结点间路径〔求输出该路径结点数〕
答:
void path(Bintree T Bintree p)
{Bintree stack[max]q
int tag[max]top0find0
qT
while ((q||top)&& find0)
{while (q)
{stack[top]q tag[top++]0
qq>lchild
}
if (top>0)
{qstack[top1]
if (tag[top1]1)
{if (qp)
{for (i0idata)
find1
}
else top
}
if (top>0&&find)
{qq>rchild
tag[top1]1
}
}
}
}
5.二叉树中结点类型BinTreeNode表示定义:
struct BinTreeNode{
char data
BinTreeNode *leftChild*rightChild
}
中data结点值域leftChild rightChild分指左右孩子结点指针域根面函数声明编写出求棵二叉树高度算法该高度函数返回参数BT初始指棵二叉树根点
int BtreeHeight〔BinTreeNode *BT〕
答:算法
int BtreeHeight(BinTreeNode * BT)
{ int h1h2h
if〔BTNULL〕h0
else{
h1 BTreeHeight〔BT->leftChild〕
h2 BTreeHeight〔BT->rightChild〕
if〔hl>h2〕hh1+1
else hh2+1
}
return h
}
6设棵二叉树二叉链表存储结构结点结构(lchild datarchild)设计算法二叉树中结点左右子树相互交换
解:
void exchange(BiTree bt)
{BiTree s
if(bt)
{sbt>lchild
bt>lchildbt>rchild
bt>rchilds
exchange(bt>lchild)
exchange(bt>rchild)}
}
7试写出复制棵二叉树算法
解:
BiTree Copy(BiTree t)复制二叉树t
{BiTree bt
if (tnull) btnull
else{
bt(BiTree)malloc(sizeof(BiNode))
bt>datat>data
bt>lchildCopy(t>lchild)
bt>rchildCopy(t>rchild)
}
return(bt)
}结束Copy
8.假设二叉树采二叉链存储结构存储试设计算法输出叶子结点根结点路径
解:
题目解析:采path数组存放路径 pathlen整数存放路径长度递模型:
f(bpathpathlen):输出path值 b叶子结点
f(bpathpathlen):b>data放入pathpathlen++ 情况
f(b>lchildpathpathlen)
f(b>rchildpathpathlen)
具体算法:
void Allpath(BTNode *bElemType path[]int pathlen)
初始调时path空pathlen0
{
int i
if (bNULL)
{ if (b>lchildNULL&& b>rchildNULL) *b叶子结点
{ printf(c根结点路径:c〞b>data b>data)
for (ipathlen1i>0i)
printf (c〞path[i])
printf (\n〞)
}
else
{ path[pathlen] b>data 前结点放入路径中
pathlen++ 路径长度增1
Allpath(b>lchildpathpathlen) 递扫描左子树
Allpath(b>rchildpathpathlen) 递扫描右子树
pathlen 环境恢复
}
}
}
9.假设二叉树采二叉链存储结构存储试设计算法输出该二叉树中第条长路径长度输出路径结点值
解:
题目解析:采path数组保存扫描前结点路径 pathlen保存扫描前结点路径长度longpath数组保存长路径 longpathlen保存长路径长度b空时表示前扫描分支已扫描完毕pathlenlongpathlen进行拟较长路径路径长度分保存longpathlongpathlen中
具体算法:
void Longpath(BTNode *bElemType path[]int pathlenElemType longpath[]int longpathlen)
{
int i
if (bNULL)
{ if (pathlen>longpathlen) 假设前路径更长路径保存longpath中
{ for (ipathlen1i>0i)
longpath[i]path[i]
longpathlenpathlen
}
}
else
{ path[pathlen] b>data 前结点放入路径中
pathlen++ 路径长度增1
Longpath(b>lchildpathpathlenlongpathlongpathlen) 递扫描左子树
Longpath(b>rchildpathpathlenlongpathlongpathlen) 递扫描右子树
pathlen 环境恢复
}
}
四图
纲求:
〔〕 图概念
〔二〕 图存储根操作
1 邻接矩阵法
2 邻接表法
〔三〕 图遍历
1 深度优先搜索
2 广度优先搜索
〔四〕 图根应复杂度分析
1 〔代价〕生成树
2 短路径
3 拓扑排序
4 关键路径
知识点:
1. 图根概念包括:图定义特点图图入度出度完全图生成树路径长度回路〔强〕连通图〔强〕连通分量等概念掌握概念相联系相关计算题根概念中完全图连通分量生成树邻接点重点
2. 图存储形式图复杂数结构序链式两种存储结构:数组表示法〔重点邻接矩阵〕邻接表逆邻接表两种存储结构图图均
3. 熟练掌握图两种遍历算法:深度遍历广度遍历深度遍历广度遍历图两种根遍历算法两算法图章重性等先序中序序遍历〞二叉树章重性
掌握图两种遍历算法应图章算法设计题常常基两种根遍历算法设计例〔强〕连通图中程次调深〔广〕度优先遍历程〔DFSBFS〕遍历全部顶点方法求出连通分量数会画出遍历中形成深〔广〕度优先生成树生成森林求长短路径问题〞判断两顶点间否存长K简单路径问题〞广度遍历深度遍历算法
4 生成树概念连通图生成树通常唯生成树边权值唯掌握生成树构造方法:PRIM算法KRUSKAL算法根两种算法思想图示法表示出求定网棵生成树程
5 拓扑排序图入度〔先〕零顶点种排序通常结果唯拓扑排序两种方法前趋顶点优先算法二继顶点优先算法换句话说种前〞排序种前〞排种排序出结果逆拓扑序〞拓扑排序深度优先遍历判断图否存环路
6 关键路径问题图章难点问题理解关键路径关键三方面:谓关键路径二早时间含义求解方法三晚时间含义求解方法简单说早时间通前〞方法求晚时间通前〞方法求解想求晚时间必须早时间已求出进行熟练掌握求解程步骤关键路径问题工程进度控制重方法具强实性理解减少关键活动时间缩短工期〞指该活动关键路径减少尚未改变关键路径前提效
7 短路径问题图章难点问题短路径问题分两种:求某点出发余点短路径二求图中顶点间短路径解决第问题DIJSKTRA算法解决第二问题FLOYD算法注意区分掌握两算法手工熟练模拟掌握求短路径问题解决应问题〔旅游景点旅游路线选择问题〕
练题:
〔〕选择题:
1 种图邻接矩阵称矩阵?〔 B 〕
A 图 B 图
C AOV网 D AOE网
2 边权值〔 A 〕时广度优先遍历算法解决单源短路径问题
A 均相等 B 均相等
C 少半相等 D 少少半相等
3 n结点图边数〔 B 〕
A.n+1 B.n(n1)2
C.n(n+1) D.2n(n+1)
4 图中顶点度数图边数〔 C 〕
A.12 B.11
C.21 D.41
5 图G(VE)中V{v1v2v3v4v5v6v7}E{}G拓扑序列〔 A 〕
A.v1v3v4v6v2v5v7 B.v1v3v2v6v4v5v7
C.v1v3v4v5v2v6v7 D.v1v2v5v3v4v6v7
6 具n顶点图中连通全部顶点少需〔 C 〕条边
A.n B n+1
C n1 D n2
7 简单图邻接矩阵称进行压缩存储假设图Gn结点邻接矩阵A[1…n1…n]压缩存储B[1…k]k值少〔 D 〕
A.n(n+1)2 B n22
C (n1)(n+1)2 D n(n1)2
分析:简单图邻接矩阵称角线元素均0压缩存储须存储三角三角〔均包括角线〕
8 图中顶点度指图中〔 C 〕
A.通该顶点简单路径数
B.通该顶点回路数
C.该顶点相邻接顶点数
D.该顶点连通顶点数
9 含n顶点e条边简单图邻接矩阵存储结构中〔 D 〕零元素
A.e
B 2e
C n2e
D n22e
10 假设采邻接矩阵存储简单图某顶点i入度等该矩阵〔 D 〕
A.第i行中值1元素数
B 值1元素数
C.第i行第i列中值1元素总数
D.第i列中值1元素数
11 假设具n结点k条边非连通图森林〔n>k〕该森林中必〔 C 〕棵树
A.k B n
C nk D n+k
12 假设G具36条边非连通图〔含回路重边〕图G少〔 B 〕顶点
A.11 B 10
C 9 D 8
〔二〕应题
1深度优先搜索遍历图示图试出A起点顶点访问序列〔顶点邻点字母序访问〕出生成树
7
C
B
A
4
11
4
7
5
6
4
8
4
5
G
F
E
D
6
1
3
5
5
6
2
4
J
I
H
答:
生成树:
A
D
H
E
F
G
B
I
J
C
3
2
1
4
4
4
7
4
5
深度优先搜索顶点访问序列:A B E D H I F C G J
2 面求连通图生成树种方法
图中边权重排序〔e1e2…em〕
i1
WHILE (剩边数 >顶点数)
BEGIN
图中删ei
假设图连通恢复ei
ii+1
END
试证明算法图原图代价生成树
答 连通图生成树包含图中全部n顶点足图连通n1条边生成树边权值生成树算法中WHILE〔剩边数>顶点数〕循环边数顶点数少1〔n1〕停止符合n顶点连通图生成树n1条边定义边权值排序删边权值边结果生成树必生成树算法中假设图连通恢复ei〞含义必须保存图连通边保证生成树否者回路者成连通分量均生成树
3 图进行遍历遍历序列导致遍历序列唯素?
答:遍历唯素:开始遍历顶点存储结构邻接表情况邻接点序
4带权连通图生成树否唯?说明什情况生成树唯?
答:带权连通图生成树唯图中附某顶点条边出现权值相边时生成树唯里说生成树唯指生成树形状唯生成树权值应该相
5 加权图G邻接矩阵:
(1) 画出该图G
(2) 试利Dijkstra算法求G中顶点a顶点间短路径出求解程
a
b
c
d
e
g
f
15
2
8
4
6
9
10
4
5
3
12
答:
〔1〕
〔2〕
终点
Dist
b
c
d
e
f
g
S
k1
15
(ab)
2
(ac)
12
(ad)
{ac}
k2
15
(ab)
12
(ad)
10
(ace)
6
(acf)
{acf}
k3
15
(ab)
11
(acfd)
10
(ace)
16
(acfg)
{acfe}
k4
15
(ab)
11
(acfd)
16
(acfg)
{acfed}
k5
15
(ab)
14
(acfdg)
{acfedg}
k6
15
(ab)
{acfedgb}
6图中顶点表示村庄边代表交通路线假设建立家医院试问建村庄村庄总体交通代价?
0
4
2
3
1
3
13
4
5
4
13
12
12
15
6
解:
该图邻接矩阵:
利Floyd算法求两顶点间短路径长度求:
A4中求村庄间少交通代价假设医院建i村庄时村庄返总交通代价示:
医院建村庄0时村庄返总交通代价12+16+4+7+13+16+4+1890
医院建村庄1时村庄返总交通代价13+29+17+20+12+11+8+5115
医院建村庄2时村庄返总交通代价16+11+12+6+16+29+12+34136
医院建村庄3时村庄返总交通代价4+8+12+3+4+17+12+2282
医院建村庄4时村庄返总交通代价18+5+34+22+7+20+6+3115
显然医院建村庄3时总体交通代价少
〔三〕算法设计题
1设计算法求图G〔采邻接表存储〕连通分量数
解法:采深度优先遍历方法算法:
void DFS(AGraph *G int v)
{
ArcNode *p
visited[v]1 置已访问标记
prinf(〞d〞v) 输出访问顶点编号
pG>adjlist[v]firstarc p指顶点v第条边终结点
while (pNULL)
{
if (visited[p>adjvex]0) 假设p>adjvex顶点未访问递访问
DFS(Gp>adjvex)
pp>nextarc p指顶点v条边终结点
}
}
int ConnNum1(AGraph *G) 求图G连通分量
{
int i num0
for (i0 in i++)
visited[i]0
for (i0 in i++)
if (visited[i]0)
{
DFS(Gi) 调DFS算法
num++
}
return(num)
}
解法二:采广度优先遍历方法算法:
void BFS(AGraph *G int v)
{
ArcNode *p
int Qu[MAXV]front0 rear0 定义循环队列初始化
int wi
for (i0 in i++) visited[i]0 访问标志数组初始化
prinf(〞2d〞v) 输出访问顶点编号
visited[v]1 置已访问标记
rear(rear+1)MAXV
Qu[rear]v v入队
while (frontrear) 假设队列空时循环
{
front(front+1)MAXV
wQu[front] 出队赋予w
pG>adjlist[w]firstarc 找顶点w邻接第顶点
while (pNULL)
{
if (visited[p>adjvex]0) 假设前邻接顶点未访问
{
printf(〞2d〞 p>adjvex) 访问相邻顶点
visited[p>adjvex]1 置该顶点已访问标志
rear(rear+1)MAXV 该顶点入队
Qu[rear] p>adjvex
}
pp>nextarc 找邻接顶点
}
}
printf(〞\n〞)
}
int ConnNum2(AGraph *G) 求图G连通分量
{
int i num0
for (i0 in i++)
visited[i]0
for (i0 in i++)
if (visited[i]0)
{
BFS(Gi) 调BFS算法
num++
}
return(num)
}
五查找
纲求:
〔〕 查找根概念
〔二〕 序查找法
〔三〕 折半查找法
〔四〕 B树
〔五〕 散列〔Hash〕表查找
〔六〕 查找算法分析应
知识点:
1. 线性表查找序表采序查找方法逐拟序表设置监视哨查找效率提高序序表采折半查找法判定树唯索引结构采索引序查找算法算法综合述两者优点较快速查找适应动态变化求注意三种查找均查找长度掌握序查找折半查找算法实现中折半查找特注意适条件递实现方法
2. B树路衡外查找树文件系统手工模拟B树插入删关键字B树增高降低会推导B树均查找长度
3. 散列表查找算法根思想:根前查找数特征记录关键字变量设计散列函数该函数关键字进行转换解释结果查址熟练掌握散列函数设计突解决方法选择突处理程描述散列表中关键字查找散列函数计算序查找折半查找闭散列法解决突情况元素删做标记物理删理想情况散列表均查找长度O(1)优查找方法
练题:
〔〕选择题:
1) 某序存储表格中90000元素已关键字值额定升序排列假定元素进行查找概率相元素关键字值皆相序查找法查找时均拟次数约〔 C 〕
A.25000 B.30000
C.45000 D.90000
2) 适折半查找表存储方式元素排列求( D )
A.链接方式存储元素序 B.链接方式存储元素序
C.序方式存储元素序 D.序方式存储元素序
3) 散列文件散列函数记录关键字值计算转化记录存放址散列函数关系选择〔 D 〕方法散列文件关键
A 散列函数 B 余法中质数
C 突处理 D 散列函数突处理
4) 存储结点含数元素存储结点均匀存放连续存储空间函数值应结点存储位置该存储方式〔 D 〕存储方式
A 序 B.链接
C.索引 D.散列
5) 果求线性表较快查找适应动态变化求采〔A 〕查找法
A.分块 B 序
C 二分 D 散列
〔二〕应题
1设散列表长度13散列函数H(K)K13定关键字序列:191423016820842755111079试画出线性探测散列解决突时构成散列表求等概率情况两种方法查找成功查找成功时均查找长度
答:
线性探测散列散列表:
0 1 2 3 4 5 6 7 8 9 10 11 12
14
1
68
27
55
19
20
84
79
23
11
10
1
2
1
4
3
1
1
3
9
1
1
3
查找成功均长度ASL112〔1*6+2*1+3*3+4*1+9〕25
查找成功均长度ASL113〔1+2+3+4……+13〕7
2.什说装填子非常接1时线性探查类似序查找什说装填子拟(方α07左右)时散列查找均查找时间O(1)
答:
α非常接1时整散列表装满线性探查法关键字义时解决突方法线性查找整表装满时类似序查找
α拟时关键字碰撞率拟般情况散列函数计算出结果够1次性找相应结点均查找时间接1
3.画出长度18序序表进行二分查找判定树指出等概率时查找成功均查找长度查找失败时需关键字拟次数
答:图:
答:请题图
等概率情况查找成功均查找长度:
ASL(1+2*2+3*4+4*8+5*3)183556
公式代约:ASL(18+1)lg(18+1)1813346
查找失败时关键字拟次树超判定树深度处5
六部排序
纲求:
〔〕 排序根概念
〔二〕 插入排序
1 直接插入排序
2 折半插入排序
〔三〕 起泡排序〔bubble sort〕
〔四〕 简单项选择择排序
〔五〕 希尔排序〔shell sort〕
〔六〕 快速排序
〔七〕 堆排序
〔八〕 二路排序〔merge sort〕
〔九〕 基数排序
〔十〕 种部排序算法拟
〔十〕 部排序算法应
知识点:
1. 插入类排序根思想假定排序文件第记录序然第二记录起次插入排序序子文件中直整文件序减少拟次数移动次数进行种改良插入排序中直接插入折半插入希尔排序直接插入次寻找折半插入折半寻找希尔排序通控制次参排序数总范围〞增量实现排序效率提高目
2. 交换类排序基相邻记录拟假设逆序进行交换起泡排序快速排序交换排序例子起换排序根底改良快速排序快速排序目前部排序法快速排序思想:中间数排数组分二快速排序处理问题规模〞概念希尔点相反快速排序先处理较规模然逐渐处理规模降低终达排序目
3. 选择类排序分:简单项选择择排序堆排序两种方法点根什规选取数简单项选择择通简单数组遍历方案确定数堆排序利堆种数结构性质通堆元素删调整等系列操作数选出放堆顶堆排序较重差性快速排序差性
4. 排序通〞种操作完成排序目然必须两者数集合实现算法思想拟简单
5. 基数排序种特殊排序方法分两种:关键字排序〔扑克牌排序〕链式排序〔整数排序〕基数排序核心思想利基数空间〞概念问题规模标准变排序程中基数排序思想进行关键字拟样出终序列序序列
6. 掌握种排序方法算法思想算法实现掌握坏均情况种排序方法性分析排序基数排序时间复杂度O(n2)排序稳定排序希尔排序快速排序堆排序等时间性排序方法稳定排序〔特注意简单项选择择排序稳定排序〕
种排序方法综合拟
〔1〕时间性
●均时间性分三类排序方法:
时间复杂度O(nlogn)方法:快速排序堆排序排序中快速排序
时间复杂度O(n2):直接插入排序起泡排序简单项选择择排序中直接插入特关键字似序记录序列尤
时间复杂度O(n)排序方法基数排序
●排记录序列关键字序序时直接插入排序起泡排序达O(n)时间复杂度快速排序言情况时时间性蜕化O(n2)应该量防止情况
●简单项选择择排序堆排序排序时间性记录序列中关键字分布改变
〔2〕空间性:指排序程中需辅助空间
●简单排序方法(包括:直接插入起泡简单项选择择)堆排序空间复杂度O(1)
●快速排序O(logn)栈需辅助空间
●排序需辅助空间空间复杂度O(n)
●链式基数排序需附设队列首尾指针空间复杂度O(rd)
〔3〕排序方法稳定性
稳定排序方法指两关键字相等记录序列中相位置排序前排序没改变
关键字记录序列进行LSD方法排序时必须采稳定排序方法
稳定排序方法举出实例说明
快速排序堆排序稳定排序方法
练题:
〔〕选择题:
1 四序列中堆〔 C 〕
A 7565301525452010 B 7565451030252015
C 7545653015252010 D 7545651025302015
2 排序算法中情况时间复杂度O(n)算法〔 D 〕
A.选择排序 B.排序
C.快速排序 D.泡排序
3 述排序算法中稳定〔 B 〕
A 直接选择排序 B.基数排序
C.快速排序 D.堆排序
4 排序算法中第趟排序完毕元素定终位置算法〔 D 〕
A.排序 B.直接插入排序
C.快速排序 D.泡排序
5 果想1024元素组成序列中前5元素〔 D 〕方法快
A.起泡排序 B.快速排序
C.堆排序 D.直接选择排序
6 面出4种排序方法中排序程中拟次数初始排序次序关〔A〕
A.选择排序法 B.插入排序法
C.快速排序法 D.堆排序法
〔二〕应题
1 堆积表示棵完全二叉树请分表达堆积二叉排序树区
答:
假设堆积表示棵完全二叉树该二叉树中意分支结点值者等孩子结点〔顶堆积例〕根结点具值二叉排序树中求左子树中结点值均根结点值右子树中结点值均等根结点值根结点定具值堆积二叉排序树回事
〔三〕算法设计题
1荷兰国旗问题:设仅红白蓝三种颜色条块组成条块序列请编写时间复杂度O(n)算法条块红白蓝序排排成荷兰国旗图案函数原型:
typedef enum{REDWHITEBLUE} color
void Flag(color a[]int n)
答:
typedef enum{REDWHITEBLUE} color
void Flag(color a[]int n)
{
i0j0kn1
while(jswitch(a[j])
{
case RED
a[i]<>a[j]
i++j++break
case WHITE:
j++break
case BLUE
a[j]<>a[k]
k
}
}
2. 述实现排序:假设序列中k长度等n序子序列利程merge进行两两长度等2n序子序列〔表示取整〕称趟排序反复调趟排序程序子序列长度n1开始成倍增加直整序列成序序列试采链表存储结构实现述排序非递算法函数原型:
void Linked_Mergesort(LinkedList &L) 链表结构排序非递算法
void Linked_Merge(LinkedList &L LNode *p Lnode *e1Lnode *e2)
链表子序列进行第子序列p>nexte1第二e1>nexte2
答:
void Linked_Mergesort(LinkedList &L)
{
for(l1lfor(pL>nexte2p p>next pe2)
{
for(i1qp inext i++qq>next)
e1q
for(i1 inext i++qq>next)
e2q 求两子序列尾指针
if(e1e2)
Linked_Merge(Lpe1e2)
}
}
void Linked_Merge(LinkedList &L LNode *p Lnode *e1Lnode *e2)
{
qp>next qr两子序列起始位置
re1>next
while(qe1>next && re2>next)
{
if(q>data < r>data)
{
p>nextq
pq
qq>next
}
else
{
p>nextr
pr
rr>next
}
}
while(qe1>next)
{
p>nextq
pq
qq>next
}
while(re2>next)
{
p>nextr
pr
rr>next
}
}
3种简单排序算法做计数排序种排序算法排序表(数组表示)进行排序排序结果存放新表中必须注意表中排序关键字互相计数排序算法针表中记录扫描排序表趟统计表中少记录关键字该记录关键字假设某记录统计出数值c记录新序表中适宜存放位置c
(1)出适计数排序数表定义
(2)编写实现计数排序算法
(3)n记录表拟次数少
(4)直接选择排序相种方法否更什
解
(1) typedef struct
{
ElemType data
KeyType key
}listtype
(2) void countsort(listtype a[]listtype b[]int n)
{
int ijcount
for(i0i{
count0
for(j0jif(a[j]keyb[count]a[i]
}
}
(3) n记录表关键字拟次数n2
(4)直接选择排序种计数排序直接选择排序拟次数n*(n1)2原进行排序〔稳定排序〕计数排序稳定排序需辅助空间O(n)
4.快速排序算法中选取界值〔称轴元素〕影响着快速排序效率界值定排序序列中元素例排序序列中元素均值作界值编写算法实现均值界值快速排序方法
解:
题目解析:保存划分第元素均值作枢轴进行普通快速排序枢轴位置存入已保存第元素假设关键字均值属左半部否属右半部
int partition (RecType r[]int lh)
{
int iljhavg0
for(iil
avgavg(hl+1)
while (i{
while (iavg) j
if (iwhile (i if (i }
if(R[i]keyelse return i1
}
void quicksort (RecType R[]int ST)
{
if (S{
kpartition (RST)
quicksart (RSk)
quicksart (Rk+1T)
}
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容,不代表《香当网》观点或立场,请自行判断内容的真实性和可靠性!
该内容是文档的文本内容,更好的格式请下载文档