数据结构练习题（含答案）

数结构练题
题1 绪
11 单项选择题
1 数结构门研究非数值计算程序设计问题中数元素① 数信息计算机中② 组相关运算等课程
① A．操作象　　　Ｂ．计算方法　　Ｃ．逻辑结构　　Ｄ．数映象
② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法
2 数结构DS(Data Struct)形式定义DS（DR）中D① 限集合RD② 限集合
① A．算法 Ｂ．数元素 Ｃ．数操作 Ｄ．数象
② A．操作 Ｂ．映象 Ｃ．存储 Ｄ．关系
3 数结构中逻辑数结构分成
A．动态结构静态结构 Ｂ．紧凑结构非紧凑结构
Ｃ．线性结构非线性结构 Ｄ．部结构外部结构
4 算法分析目① 算法分析两方面②
① A 找出数结构合理性 B 研究算法中输入输出关系
C 分析算法效率求改进 D 分析算法易懂性文档性
② A 空间复杂性时间复杂性 B 正确性简明性
C 读性文档性 D 数复杂性程序复杂性
5 计算机算法指① 必具备输入输出② 等五特性
① A 计算方法 B 排序方法
C 解决问题限运算序列 D 调度方法
② A 行性移植性扩充性 B 行性确定性穷性
C 确定性穷性稳定性 D 易读性稳定性安全性

12 填空题（正确答案填相应空中）
1 数逻辑结构包括 三种类型树形结构图形结构合称
2 线性结构中第结点 前驱结点余结点 前驱结点结点 续结点余结点 续结点
3 树形结构中树根结点没 结点余结点 直接前驱结点叶子结点没 结点余结点直接续结点
4 图形结构中结点前驱结点数续结点数
5 线性结构中元素间存 关系树形结构中元素间存 关系图形结构中元素间存 关系
6 算法五重特性__ __ __ __ ___ _ __ __ _ ___
7 分析面算法（程序段）出语句频度 该算法时间复杂度__ __
for (i0i for (j0j A[i][j]0
8 分析面算法（程序段）出语句频度 该算法时间复杂度__ __
for (i0i for (j0 jA[i][j]0
9 分析面算法（程序段）出语句频度 该算法时间复杂度__ __
s0
for (i0i for (j0j for (k0k ss+B[i][j][k]
sums
10 分析面算法（程序段）出语句频度 该算法时间复杂度__ __
is0
while (s{ i++
s+i ss+i
}
11 分析面算法（程序段）出语句频度 该算法时间复杂度__ __
i1
while (i ii*2
13 算法设计题
1 试写算法次输出序读入三数XYZ值
2 试写算法求出n数中值写出语句频度该算法时间复杂度
题答案
11 1 C A 2 BD 3 C 4 C A 5 CB
12 1 线性结构树形结构图形结构非线性结构
2 没1没1
3 前驱1续意
4 意
5
6 穷性确定性行性输入输出
7 语句频度：n2 时间复杂度： O (n2)
8 语句频度：n (n+1)2 时间复杂度： O (n2)
9 语句频度：n3 时间复杂度： O (n3)
10 语句频度：n 时间复杂度： O (n)
11 语句频度：log2n 时间复杂度： O (log2n )




题2 线性表
21 单项选择题
1 量（批址连续存储单元）第元素存储址100元素长度2第5元素址__ __
A 110 B 108 C 100 D 120
2 线性表序存储结构种__ _存储结构链式存储结构种__ _存储结构
A．机存取 B．索引存取 C．序存取 D．散列存取
3 线性表逻辑序存储序总致种说法__ _
A 正确 B 正确
4 线性表采链式存储结构时求存中存储单元址__ _
A 必须连续 B 部分址必须连续
C 定连续 D 连续连续
5 叙述中正确__ _
A 线性表序存储结构优链表存储结构
B 线性表序存储结构适频繁插入删数元素情况
C 线性表链表存储结构适频繁插入删数元素情况
D 线性表链表存储结构优序存储结构
6 种数结构具备三基运算：插入删查找种说法__ _
A 正确 B 正确
7 带头结点单链表head空判定条件____
A head NULL B head>next NULL
C head>next head D headNULL
8 带头结点单链表head空判定条件____
A head NULL B head>next NULL
C head>next head D headNULL
9 非空循环单链表head尾结点（p指）满足____
A p>next NULL B p NULL
C p>next head D p head
10 双循环链表p指结点插入s指结点操作____
A p>rights s>leftp p>right>lefts s>rightp>right
B p>rights p>right>lefts s>leftp s>rightp>right
C s>leftp s>rightp>right p>rights p>right>lefts
D s>leftp s>rightp>right p>right>lefts p>rights
11 单链表中已知q指结点p指结点前驱结点qp间插入s结点执行____
A s>nextp>next p>nexts B p>nexts>next s>nextp
B q>nexts s>nextp C p>nexts s>nextq
12 单链表中p指结点结点p插入s指结点执行____
A s>nextp p>nexts B s>nextp>next p>nexts
C s>nextp>next ps C p>nexts s>nextp
13 单链表中删p指结点续结点执行____
A p>next p>next>next B p p>next p>next p>next>next
C p>next p>next D p p>next>next
14 具n结点单链表中查找值等x结点时查找成功情况需均较____结点
A n B n2 C (n1)2 D (n+1)2
15 具n结点序单链表中插入新结点然序时间复杂度__ __
A O(1) B O(n) C O (n2) D O (nlog2n)
16 定n元素量建立序单链表时间复杂度__ __
A O(1)） B O(n) C O (n2) D O (n*log2n)
22 填空题（正确答案填相应空中）
1 单链表做__ __链接存储表示
2 双链表中结点两指针域指____ __指___ __
3 单链表中p指结点前插入s (值e)指结点时执行操作：
qhead
while (q>nextp) qq>next
s new Node s>datae
q>next 填空
s>next 填空
4 单链表中删p指结点继结点时应执行操作：
q p>next
p>next _ ___ 填空
delete 填空
5 单链表中p指结点插入s指结点时应执行s>next__ __p>next____操作
6 具n结点单链表已知p指结点插入新结点时间复杂度__ __定值x结点插入新结点时间复杂度__ __
23 算法设计题
1设序表va中数元数递增序试写算法x插入序表适位置保持该表序性
Status Insert_SqList(SqList &vaint x)
{
if(valength+1>maxsize) return ERROR
valength++
for(ivalength1vaelem[i]>x&&i>0i)
vaelem[i+1]vaelem[i]
vaelem[i+1]x
return OK
}

2试写算法实现序表逆置利原表存储空间线性表（a1 a2… an）逆置(an an1… a1)
void reverse(int a[] int size)
{
int ijtmp
for(i0 jsize1 i {
tmpa[i]
a[i]a[j]
a[j]tmp
}
}

3 已知线性表中元素值递增序排列单链表作存储结构试写算法删表中xy元素（表中存样元素）时释放删结点空间
void del(LinkList Lelemtype aelemtype b)
{
p Lqp>next
while(qL && q>data{
pq
qq>next
}
while(qL && q>data{
rq
qq>next
free(r)
}
if(pq)
p>nextq
}

4 试写算法实现单链表逆置(求原链表进行)
void converse(NODEPTR L)
{
  NODEPTR pq
  pL>next qp>next
  L>nextNULL
  while(p)  * 前结点p头插法结点p插入头结点 *
   {
     p>nextL>next
     L>nextp
     pq
     qq>next
     }
}
题答案
21 1 B 2 A C 3 B 4 D 5 C 6 A 7 A 8 B
9 C 10 D 11B 12B 13A 14D 15B 16C
22 1 线性结表 2 前驱结点继结点
3 s p 4 q>next q
5 p>next s 6 O (1) O (n)

题3 栈队列
31 单项选择题
1 栈入栈序列abcde栈输出序列____
A edcba B decba C dceab D abcde
2 已知栈入栈序列123…n输出序列p1p2p3…pnp1npi____
A i B ni C ni+1 D 确定
3 栈结构通常采两种存储结构____
A 序存储结构链式存储结构
B 散列方式索引方式
C 链表存储结构数组
D 线性存储结构非线性存储结构
4 判定序栈ST（元素m0）空条件____
A top 0 B top 0 C top m0 D top m01
5 判定序栈ST（元素m0）栈满条件____
A top0 B top 0 C topm0 D top m01
6 栈特点____队列特点____
A 先进先出 B 先进出
7 栈顶指针HS链栈中插入s指结点时执行__ __
(带空头结点)
A HS—＞nexts
B s—＞next HS—＞next HS—＞nexts
C s—＞next HS HSs
D s—＞next HS HS HS—＞next
8 栈顶指针HS链栈中删结点时x保存删结点值执行__ __(带空头结点)
A xHS HS HS—＞next B xHS—＞data
C HS HS—＞next xHS—＞data D xHS—＞data HS HS—＞next
9 队列数入列序列1234队列出队时输出序列____
A 4321 B 1234
C 1432 D 3241
10 判定循环队列QU（元素m0）空条件____
A rear front m0 B rearfront1 m0
C front rear D front rear+1
11 判定循环队列QU（元素m0 m0 Maxsize1）满队列条件____
A ((rear front)+ Maxsize) Maxsize m0
B rearfront1 m0
C front rear
D front rear+1
12 循环队列数组A[0m1]存放元素值已知头尾指针分frontrear前队列中元素数____
A (rearfront+m)m
B rearfront+1
Crearfront1
D rearfront
13 栈队列点____
A 先进出 B 先进先出
C 允许端点处插入删元素 D 没点
32 填空题（正确答案填相应空中）
1 量栈队列____结构量____位置插入删元素栈____插入删元素队列____插入元素____删元素
2 长度n量第i元素（1≤i≤n+1）前插入元素时需移动____元素
3 长度n量中删第i元素（1≤i≤n）时需前移动____元素
4 具n单元循环队列中队满时____元素

题答案
31 1 C 2 C 3 A 4 B 5D 6 BA 7C 8 B 9 C 10 C
11 A 12 A 13C
32 1 线性栈顶队尾队首 2 ni+1 3 ni
4 n1
题6 树二叉树
61 单项选择题
1 二叉树中结点度2二叉树种特殊树种说法____
A 正确 B 错误
2 假定棵二叉树中双分支结点数15单分支结点数30叶子结点数 A．15 B．16 C．17 D．47
3 二叉树定义具3结点形状二叉树____种
A 3 B 4 C 5 D 6
4 二叉树定义具3数结点二叉树____种
A 5 B 6 C 30 D 32
5 深度5二叉树____结点
A 16 B 32 C 31 D 10
6 设高度h二叉树度0度2结点类二叉树中包含结点数少_ ___
A 2h B 2h1 C 2h+1 D h+1
7 满二叉树m树叶n结点深度h____
A nh+m B h+m2n C mh1 D n2 h1
8 棵二叉树叶结点先序中序序遍历序列中相次序____
A发生改变 B发生改变 C确定 D
9 果某二叉树前根次序遍历结果stuwv中序遍历uwtvs该二叉树序____ A uwvts B vwuts C wuvts D wutsv
10 二叉树前序遍历序列中意结点均处子女结点前面种说法____ A 正确 B 错误
11 某二叉树前序遍历结点访问序abdgcefh中序遍历结点访问序dgbaechf序遍历结点访问序____
A bdgcefha B gdbecfha C bdgaechf D gdbehfca
12 非空二叉树中序遍历序列中根结点右边____
A 右子树结点 B 右子树部分结点
C 左子树部分结点 D 左子树结点
13 图61示二叉树中序遍历序列____
A abcdgef B dfebagc C dbaefcg D defbagc
g
c
e
f
d
b
a

a
g
e
d
b
c
h
f
图62





图61
a
14 棵二叉树图62示中序遍历序列__ __
A abdgcefh B dgbaechf C gdbehfca D abcdefgh
a
15．设ab棵二叉树两结点中序遍历时ab前条件
A．ab右方 B．ab左方
C．ab祖先 D．ab子孙
16 已知某二叉树序遍历序列dabec中序遍历序列debac前序遍历序列____ A acbed B decab C deabc D cedba
17 实现意二叉树序遍历非递算法栈结构佳方案二叉树采____存储结构
A 二叉链表 B 广义表存储结构 C 三叉链表 D 序存储结构
18 图63示4棵二叉树____完全二叉树
(A) (B) (C) (D)
图63










20 线索化二叉树中t指结点没左子树充条件____
A t—＞leftNULL B t—＞ltag1
C t—＞ltag1t—＞leftNULL D
21 二叉树某种序线索化结点均指前驱续线索种说法____ A 正确 B 错误
22 二叉树二叉排序树充分必条件结点值均左孩子值右孩子值种说法____ A 正确 B 错误
23 具五层结点二叉衡树少____结点
A 10 B 12 C 15 D 17
24 树基遍历策略分先根遍历根遍历二叉树基遍历策略分先序遍历中序遍历序遍历里树转化二叉树做棵数应二叉树结____正确
A树先根遍历序列应二叉树先序遍历序列相
B树根遍历序列应二叉树序遍历序列相
C树先根遍历序列应二叉树中序遍历序列相
D
25 树适合表示____
A 序数元素 B 序数元素
C 元素间具分支层次关系数 D 元素间联系数
62 填空题（正确答案填相应空中）
1 棵树图65示回答面问题：
k1
11
k
k
k

k

k

k

2

1
4
3
5
6
7

⑴ 棵树根结点____
⑵ 棵树叶子结点____
⑶ 结点k3度____
图65 棵树
⑷ 棵树度____
⑸ 棵树深度____
⑹ 结点k3子女____
⑺ 结点k3父结点__

2 指出树二叉树三差______________
3 概念讲树二叉树两种数结构树转化二叉树基目___ _
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
e
a
f
d
g
c
j
l
h
b
图66 棵二叉树序存储数组t
4 棵二叉树结点数采序存储结构存储数组t中图66示该二叉树链接表示形式__ __
5 深度k完全二叉树少____结点____结点左右次序结点编号（1开始）编号叶子结点编号____
6 棵二叉树中度零结点数n 0度2结点数 n 2n0____
7 棵二叉树第i（i≥1）层____结点棵n（n>0）结点满二叉树____叶子____非终端结点
8 结点少树____结点少二叉树____
9 现中序遍历二叉树结果abc问____种形态二叉树遍历结果二叉树分____
10 图67示二叉树回答问题：
i
a
e
d
b
c
h
H
f
图67 棵二叉树

i
⑴ 中序遍历序列____
⑵ 前序遍历序列____
⑶ 序遍历序列____




63 简答题
1 根二叉树定义具三结点二叉树5种形态请分画出
2 假设棵 二叉树先序序列EBADCFHGIKJ中序序列ABCDEFGHIJK
g
c
e
f
d
b
a
图68 棵树
请画出该树
3 图67示二叉树回答问题：
（1）画出该二叉树中序线索二叉树
（2）画出该二叉树序线索二叉树
（3）画出该二叉树应森林
4 已知棵树图68示转化棵二叉树表示____





5 数集{4567101218}结点权值画出构造Huffman树步图示计算带权路径长度
6 棵含N结点k叉树达深度深度少
7 证明棵满k叉树叶子结点数n非叶子结点数n间满足关系
n(k1)n+1
64 算法设计题
1 编写层次序（层左右）遍历二叉树算法
2．试编写算法棵二叉树统计叶子数
3．试编写算法棵二叉树根结点变左右子树进行交换树中结点左右子树进行交换
7 假设通讯电文仅八字母(abcdefgh)组成字母电文中出现频率分007 019 002 006 032 003 021 010试八字母设计哈夫曼编码
07二进制表示形式种编码方案述实例较两种方案优缺点
8 试编写算法棵孩子兄弟链表表示树统计叶子数假设棵 二叉树先序序列EBADCFHGIKJ中序序列ABCDEFGHIJK请画出该树
题答案
61 1 B 2 B 3 C 4 C 5 C 6 A 7 D 8 A 9 C 10 A
11 D 2 A 13 B 14 B 15 B 16 D 17 C 18 C
19 B 20 B 21 B 22 B 23 B 24 A 25 C
62
1 ⑴ k1 ⑵ k2k5k7k4 ⑶ 2 ⑷ 3 ⑸ 4 ⑹ k5k6 ⑺ k1
e
aE
f
j
c
d
l
g
h
b
图69
2 树结点数少1(教材规定)二叉树结点数0
树中结点度数没限制二叉树结点度数2
树结点左右分二叉树结点左右分
3 树采孩子兄弟链表（二叉链表）做存储结构目利二叉树已算法解决树关问题
4 图69示
5 2 k1 2 k1 2 k2+1
6 n2+1
7 2 i1 2[log2n+1]1 2[log2n+1] –1
8 结点树空二叉树
9 5图610示
a
图610 树形5种
a
a
a
a
c
c
c
c
c
b
b
b
b
b
b
10 dgbaechif abdgcefhi gdbeihfca
63 1 5种 图611
E
BE
F
AE
C
D
K
G
H
I
J
图612
图611 树形5种
2 二叉树图612示





3 中序线索二叉树图613（左）示序线索二叉树图613（右）示
该二叉树转换森林图614示
图613

a
11
d
h

j

b
k

c

图 614 应森林
i

e
f





a

b

c
e
d
i
g
图 615 棵树孩子兄弟表示
4 图68树转化棵二叉树图615：








5 画出构造Huffman树图616示计算带权路径长度




6 棵含N结点k叉树达深度 hNk+1
深度 logkN+1

62
37
25
19
18
13
12
10
9
6
7
4
5
图616 Huffman树


















题7 图
71 单项选择题
1．图中顶点度数等边数____倍
A 12 B 1 C 2 D 4
2．连通图生成树
A棵 B棵棵 C定棵 D存
3．图中顶点入度等顶点出度____倍
A 12 B 1 C 2 D 4
4．n顶点图____条边
A n B n(n1) C n(n1)2 D 2n
5．具4顶点完全图____条边
A 6 B 12 C 16 D 20
6．具6顶点图少应____条边确保连通图
A 5 B 6 C 7 D 8
7．具n顶点图中连通全部顶点少需____条边
A n B n+1 C n1 D n2
8．具n顶点图采邻接矩阵表示该矩阵____
A n B (n1)2 C n1 D n2
9．具n顶点e条边图采邻接表表示表头量_①___邻接表中接点总数_②___
① A n B n+1 C n1 D n+e
② A e2 B e C2e D n+e
10．已知图图71示顶点a出发深度搜索法进行遍历
种顶点序列__①__宽度搜索法进行遍历种顶点序列
__②__
① A abecdf B ecfebd C aebcfd D aedfcb
b
a
e
c
d
f
② A abcedf B abcefd C aebcfd D acfdeb








图 71 图


11．已知图邻接表存储结构图72示
1
2
3
4
5
3
2
4
5
2
4
^
^
^
^
^









图72 图邻接表存储结构



⑴ 根图深度优先遍历算法顶点v1出发顶点序列____
A v1v2v3v5v4 B v1v2v3v4v5
C v1v3v4v5v2 D v1v4v3v5v2
⑵ 根图宽度优先遍历算法顶点v1出发顶点序列____
A v1v2v3v4v5 B v1v3v2v4v5
C v1v2v3v5v4 D v1v4v3v5v2
12．采邻接表存储图深度优先遍历算法类似二叉树____
A 先序遍历 B 中序遍历 C 序遍历 D 层遍历
13．采邻接表存储图宽度优先遍历算法类似二叉树____
A 先序遍历 B 中序遍历 C 序遍历 D 层遍历
14．判定图否存回路利拓扑排序方法外利____
A 求关键路径方法 B 求短路径Dijkstra方法
C 宽度优先遍历算法 D 深度优先遍历算法
15．关键路径事件结点网络中
A源点汇点长路径 B源点汇点短路径
C长回路 D短回路
16．面正确说法
（1）AOE网中减关键活动权值整工期相应减
（2）AOE网工程工期关键活动权
（3）关键路径活动关键活动关键活动必关键路径
A（1） B（2） C（3） D（1）（2）
17．DFS遍历环图DFS算法退栈返回时印出相应顶点输出顶点序列
A逆拓朴序 B拓朴序 C序
18．图73示拓朴排列结果序列
A125634 B516234 C123456 D521634
图73图


19．n顶点连通图包含连通分量数
A0 B1 Cn Dn+1
20．图顶点入度k1出度k2应邻接表中该顶点单链表中结点数
Ak1 Bk2 Ck1k2 Dk1+k2
21．图顶点入度k1出度k2应逆邻接表中该顶点单链表中结点数
Ak1 Bk2 Ck1k2 Dk1+k2
72 填空题（正确答案填相应饿空中）
1．n顶点连通图少____条边
2．权图G邻接矩阵A中(vivj)＜vivj＞属图G边集合应元素A[i][j]等____否等____
3．图G邻接矩阵A中A[i][j]等1A[j][i ]等____
4．已知图G邻接表图74示顶点v1出发深度限搜索序列____顶点v1出发宽度优先搜索序列____
v1
v3
v2
v4
v5
v6
v2
v5
v4
v3
v5
^
^
v6
v4
v6
v3










图74 图G邻接表


5．已知图邻接矩阵表示计算第i结点入度方法____
6．已知图邻接矩阵表示删第i结点出发边方法____
7．果含n顶点图形成环 棵生成树
8．非连通图28条边该图少 顶点
9．遍历图程实质 BFS遍历图时间复杂度 DFS遍历图时间复杂度 两者处 反映数结构差
10．图 表示法唯 表示法唯
11．图中结点前驱继关系特征
12．图G顶点度数值等 时G少条回路
13．根图存储结构进行某种次序遍历顶点序列
73 综合题
1
5
6
2
4
3
1．已知图75示图请出该图
（1）顶点入出度
（2）邻接距阵
（3）邻接表
（4）逆邻接表
（5）强连通分量


图75图


b
a
d
c
e
f
16
11
15
15
15
16
13
14
12
21
2．请克鲁斯卡尔普里姆两种算法分图76图77构造生成树：
（1）











图76


6


12


132


12


4


9


5


20


15


16


10






6



1



5



4



3



7



2
（2）






图77
3．试列出图78中全部拓扑排序序列

1
2
3
4
5
6





图78





4．请图示说明图79顶点a余顶点间短路径
5
4
3
2
2
3
3
5
6
a
b
d
f
c

e








图79


5．已知AOE网9结点：V1V2V3V4V5V6V7V8V9邻接矩阵：
(1)请画出该AOE图
(2)计算完成整计划需时间
(3)求出该AOE网关键路径
∝
6
4
5
∝
∝
∝
∝
∝
∝
∝
∝
∝
1
∝
∝
∝
∝
∝
∝
∝
∝
1
∝
∝
∝
∝
∝
∝
∝
∝
∝
2
∝
∝
∝
∝
∝
∝
∝
∝
∝
9
7
∝
∝
∝
∝
∝
∝
∝
∝
4
∝
∝
∝
∝
∝
∝
∝
∝
∝
2
∝
∝
∝
∝
∝
∝
∝
∝
4
∝
∝
∝
∝
∝
∝
∝
∝
∝


题答案
71 1 C 2B 3B 4 C 5 A 6 A 7C
8D 9 AC 10DB 11 CB 12 A 13 D 14D 15A 16A 17A 18B 19B 20B 21A
72 1n1 2 10 3 1
4v1v2v3v6v5 v4v1v2v5v4v3 v6
5求矩阵第i列非零元素
6 矩阵第i行全部置零
7n
89
9顶点查找邻接点程O（e）（e图中边数）O（e）
遍历图序DFS采栈存储访问结点BFS采队列存储访问
结点
10．邻接矩阵 邻接表
11．结点干前驱干继
12．2
13．唯

1
5
6
2
4
3
73 1








2
b
a
d
c
e

11
15
13
14
12
f
(1)．








6


12


4


9


5


10





6



1



5



4



3



7



2

（2）

3．
152364
152634
156234
561234
516234
512634
512364
W3
W7
W9
W6
W5
4
3
2
3
3
a
b
d
f
c
e
4．









5．(1)该AOE图：

(2)完成整计划需18天
(3)关键路径：（V1V2V5V7V9）（V1V2 V5V8V9）

题8 查找
81 单项选择题
1序查找法适合存储结构____线性表
A 散列存储 B 序存储链接存储
C 压缩存储 D 索引存储
2线性表进行二分查找时求线性表必须____
A 序方式存储 B 链接方式存储
C 序方式存储结点关键字序排序
D 链接方式存储结点关键字序排序
3采序查找方法查找长度n线性表时元素均查找长度____
A n B n2 C (n+1)2 D (n1)2
4采二分查找方法查找长度n线性表时元素均查找长度____
A．O（n2） B O(nlog2n) C O(n) D O(log2n)
5二分查找二叉排序树时间性____
A 相 B 相
6序表{139123241456275778295100}二分查找值82结点时____次较查找成功
A 1 B 2 C 4 D 8
7设哈希表长m14哈希函数H(key)key11表中已4结点：
addr (15)4 addr (38)5 addr (61)6 addr (84)7
二次探测散列处理突关键字49结点址____
A 8 B 3 C 5 D 9
8长度12序表二分查找法该表进行查找表元素等概率情况查找成功需均较次数____
A 3512 B 3712 C 3912 D 4312
9．静态表序查找法表头设置岗哨正确查找方式
A第0元素查找该数元素
B第1元素查找该数元素
C第n元素开始前查找该数元素
D查找序关
10．解决散列法中出现突问题常采方法
A数字分析法余法方取中法
B数字分析法余法线性探测法
C数字分析法线性探测法重散列法
D线性探测法重散列法链址法
11．采线性探测法解决突问题产生系列继散列址
A必须等原散列址
B必须等原散列址
C等原散列址
D址没具体限制
12．查找表查找程中查找数元素存该数元素插入集合中种方式适合
A静态查找表 B动态查找表
C静态查找表动态查找表 D两种表适合
13散列表均查找长度
A处理突方法关表长度关
B处理突方法关表长度关
C处理突方法关表长度关
D处理突方法关表长度关
82 填空题（正确答案填相应空中）
1序查找法均查找长度____折半查找法均查找长度____哈希表查找法采链接法处理突时均查找长度____
2种查找方法中均查找长度结点数n关查找方法____
3折半查找存储结构仅限________
4 假设序线性表A[120]进行折半查找较次查找成功结点数____较二次查找成功结点数____较三次查找成功结点数____较四次查找成功结点数____较五次查找成功结点数____均查找长度____
5 长度n线性表进行序查找时间复杂度____采折半法查找时间复杂度____
6．已知序表（121824354750628390115134）折半查找90时需进行 次查找确定成功查找47时需进行 次查找成功查找100时需进行 次查找确定成功
7．二叉排序树查找长度仅 关二叉排序树 关
8．序序列通构造棵 树变成序树构造树程序序列进行排序程
9．衡二叉排序树结点衡子
10． 法构造哈希函数肯定会发生突
11．散列函数H(key)keyp中p应取____
12．散列存储中装填子值越____值越____
83 综合练题
1 画出长度10序表进行折半查找判定树求等概率时查找成功均查找长度
4 选取哈稀函数H（k）（3k）MOD 11开放定址法处理突dii（（7k）MOD 10+1）（I123…）试010散列址空间中关键字序列（2241534630130167）造哈希表求等概率情况查找成功时均查找长度
5 已知组关键字{4938659776132744823550}画出生成二叉排序树注意边插入边衡
题答案
81 1．B 2．C 3．C 4．D 5．B 6．C 7．D 8．B
9．C 10．D 11．C 12．B 13．C

82 1 （n+1）2 ((n+1)*log2(n+1))n1 1+（装填子）
2 哈希表查找法
3 序存储结构序
4 124853．7
（题意构造棵序二叉树12结点第层1结点第二层2结点第三层4结点第四层5结点：ASL（1*1+2*2+3*4+4*5）123712）
5 O（n）O(log2n)
6．243
7．结点数n生成程
8．二叉排序树
9．011
10．直接定址
11．素数
12．存取元素时发生突性越存取元素时发生突性越
题9 排序
91 单项选择题
1 排序方法中关键字较次数记录初始排列次序关____
A 希尔排序 B 起泡排序 C 插入排序 D 选择排序
2 设1000序元素希快速度挑选出中前10元素选____排序法
A 起泡排序 B 快速排序 C 堆排序 D 基数排序
3 排序元素序列基序前提效率高排序方法____
A 插入排序 B 选择排序 C 快速排序 D 排序
4 组记录排序码（467956384084）利堆排序方法建立初始堆____
A 794656384080 B 3846 5679 4084
C 847956464038 D 845679404638
5 组记录关键码（467956384084）利快速排序方法第记录基准次划分结果____
A 384046567984 B 403846795684
C 403846567984 D 403846845679
6 组记录排序码（25481635798223403672）中含5长度2序表排序方法该序列进行趟结果____
A 16253548234079823672
B 16253548798223364072
C 16254835798223364072
D 16253548792336407282
7 排序方法中未排序序列中次取出元素已排序序列（初始时空）中元素进行较放入已排序序列正确位置方法称____
A 希尔排序 B 起泡排序 C 插入排序 D 选择排序
8 排序方法中未排序序列中挑选元素次放入已排序序列（初始时空）端方法称____
A 希尔排序 B 排序 C 插入排序 D 选择排序
9 某种排序方法线性表（ 258421471527683520）进行排序时元素序列变化情况：
⑴ 258421471527683520
⑵ 201521254727683584
⑶ 152021253527476884
⑷ 152021252735476884
采排序方法____
A 选择排序 B 希尔排序 C 排序 D 快速排序
10 述种排序方法中均查找长度____
A 插入排序 B 选择排序 C 快速排序 D 排序
11 述种排序方法中求存量____
A 插入排序 B 选择排序 C 快速排序 D 排序
12 快速排序方法____情况利发挥长处
A 排序数量太 B 排序数中含相值
C 排序数已基序 D 排序数数奇数
92 填空题 （正确答案填相应空中）
1 组记录（543896231572604583）进行直接插入排序时第7记录60插入序表时寻找插入位置需较____
2 利快速排序方法组记录（543896231572604583）进行快速排序时递调栈达深度____需递调次数____中第二次递调____组记录进行快速排序
3 堆排序快速排序排序中存储空间考虑应首先选取____方法次选取____方法选取____方法排序结果稳定性考虑应选取____方法均情况排序快考虑应选取____方法坏情况排序快节省存考虑应选取____方法
4 插入排序希尔排序选择排序快速排序堆排序排序基数排序中排序稳定____
5 插入排序希尔排序选择排序快速排序堆排序排序基数排序中均较次数少排序____需存容量____
6 堆排序快速排序中原始记录接正序反序选____原始记录序选____
7 插入选择排序中初始数基正序选____初始数基反序选____
8 n元素序列进行起泡排序时少较次数____
93 综合题
1 关键码序列（503087512061908170897275653426）例手工执行排序算法写出趟排序结束时关键码状态：
（1） 直接插入排序
（2） 希尔排序（增量d[1]5）
（3） 快速排序
（4） 堆排序
（5） 排序
（6） 基数排序
2 判序列否堆（顶堆顶堆）果调整堆（求记录交换次数少）
(1）(100864873353942576621)
(2)(12703365245648928633)
(3)(1039756386623421230520620)
(4)(0556202340382961357628100)
题答案
91 1 D 2 C 3 A 4 B 5 C 6 A 7 C 8 D 9D
10 C 11 D 12 C
92 1 5
2 2 4 （233815）
3 堆排序快速排序排序排序快速排序堆排序
4 希尔排序选择排序快速排序堆排序
5 快速排序基数排序
6 堆排序快速排序
7 插入排序选择排序
8 n1



文档香网(httpswwwxiangdangnet)户传

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