2022年电大本科数据结构专业期末考试题库及答案

2022年年电科数结构专业期末考试题库答案
单项选择题
1．数物理结构（ D ）
A．数逻辑结构关 B．仅仅包括数元素表示
C．包括数元素间关系表示 D．包括数元素表示关系表示
2．数元素数基单位（ C ）
A．数项组成
B．少二数项组成
C．数项干数项组成
D．少数项指针类型
3．n数中选取元素（ C ）
A．基操作数元素间交换 B．算法时间复杂度O(n2)
C．算法时间复杂度O(n) D．需进行(n+1)次数元素间较
4．线性表序结构中（ C ）
A．逻辑相邻元素物理位置定相邻
B．数元素机访问
C．逻辑相邻元素物理位置相邻
D．进行数元素插入删效率较高
5．表中机访问（ D ）
A．单链表 B．双链表
C．单循环链表 D．序表
6．带头结点单链表空判断条件（ B ）（设头指针head）
A．head NULL B．head>next NULL
C．head>next head D．headNULL
7 设序存储线性表长度n删操作设删位置等概率删元素均移动元素次数（ A ）
A．(n+1)2 B．n C．2n D．ni
8．线性结构中数元素位置间存（ A ）关系
A． B．
C． D．元素直接前驱直接继
9．设top链栈栈顶指针栈中结点数域data指针域next组成设x接收栈顶元素出栈操作（ A ）
A．xtop>datatoptop>next B．toptop>nextxtop>data
C．xtop> nexttoptop> data D．top>next top xtop>data
10．设序存储线性表长度n删第i元素课算法i（ C ）时移动元素次数3
A．3 B．n2 C．n3 D．4
11．说法正确（ C ）
A．队列进先出
B．栈特点进出
C．栈删插入操作栈顶进行
D．队列删插入操作队头进行
12 说法正确（ C ）
A．栈特点进先出 B．队列特点先进先出
C．栈删操作栈底进行插入操作栈顶进行
D．队列插入操作队尾进行删操作队头进行
13．串函数StrCmp(abAaba)值（ D ）
A．1 B．0 C．abAaba D．1
14．栈进栈序列abcd栈出栈序列（ A ）
A．adbc B．bcad
C．cbad D．dcba
15．设12阶称矩阵A采压缩存储方式三角部分行序序存储维数组b中（矩阵A第元素a11数组b标1开始）矩阵A中第4行元素数组b中标i定（ A ）
A．7≤i≤10 B．11≤i≤15 C．9≤i≤14 D．6≤i≤9
16．已知图边数m该图顶点度数（ A ）
A．2m B．m C．2m+1 D．m2
17．设带头结点链队列队列中结点数域data指针域next组成frontrear分链队列头指针尾指针执行出队操作x保存出队元素值p指结点类型指针执行操作：pfront>nextxp>data 然执行（ B ）
A．frontp>next B．front>nextp>next
C．frontp D．front>next p
18．说法正确（ D ）
A．连通图G定存生成树
B．连通图G生成树中定包含G顶点
C．连通图G生成树中定包含G边
D．连通图G生成树连通
19．散列查找原理（ A ）
A．查记录关键字值该记录存储位置间建立确定应关系
B．查记录关键字序序方式存储
C．关键字值较进行查找
D．基二分查找方法
20．空串长度（ A ）
A．0 B．1 C．2 D．3
21．排序程中趟序子表中排序记录关键字放置已排序子序列适位置直全部排序止该排序算法( D )
A．选择排序 B．快速排序
C．泡排序 D．直接插入排序
22．采序查找法长度n线性表进行查找（采表尾设监视哨方法）坏情况进行（ B ）次元素间较
A．n+2 B．n C．n1 D．n2
23．设10阶称矩阵A采压缩存储方式三角部分行序序存储维数组b中（矩阵A第元素a11数组b标1开始）矩阵元素a53应维数组b数组元素（ C ）
A．b[18] B．b[8] C．b[13] D．b[10]
24．图1顶点a出发广度优先搜索法进行遍历顶点序列（ D ）
a
b
e
c
d
h
g
f
A．acebdfgh
B．aebcghdf
C．aedfbcgh
D．abecdfgh




图1

25．已知图2示图顶点a出发深度优先搜索法进行遍历种顶点序列（ D ）
A．abecdf B．acfebd C．aebcfd D．aedfcb
b
d
f
e
c
a

图2
26．棵哈夫曼树总23结点该树（ D ）叶结点（终端结点）
A．10 B．13 C．11 D．12
二填空题
1．通常数逻辑结构包括集合线性_树形__ 图状 四种类型
2．通常某城市中公交站点间线路图抽象成__图状 __结构
3．设单链表结点指针域next头指针headp指尾结点该单链表改单循环链表语句___ p>nexthead___ __
4．设单循环链表头指针head链表中结点指针域nextp指尾结点直接前驱结点删尾结点新单循环链表执行操作_______ _ p>nexthead
5．循环队列队头指针f队尾指针r___ rf _____时表明队列已空
6．链队中fr分队头队尾指针队结点指针域next插入s指结点操作___ r>nexts ___rs
7．设链栈栈顶指针hs现s指结点入栈执行操作
__ s>nexths hss
8．循环队列队头指针f队尾指针r___ r f _时表明队列空
9．链队中fr分队头队尾指针队结点指针域next插入s指结点操作__ r>nexts ___rs
10．A存储时占___2____字节
11．串两种基存储方式分_序存储__ __链式存储 __
12．棵二叉树没单分支结点6叶结点该树总___11__结点
13．棵二叉树中序编号i结点存左右孩子左右孩子编号分____2i _____2i+1___
14．二叉树递定义二叉树遍历常算法_先序 _中序_ _序_三种
15．两串相等充分必条件 串长度相等应位置字符相等
16．数存储计算机中具体体现数间逻辑结构称_物理（存储）_结构
17．棵二叉树叶结点（终端结点）数5单分支结点数2该树__11__结点
18．图3示二叉树序遍历序列 gdbeihfca
e
f
g
i
b
a
c
h
d














图3

19．根搜索方法图遍历__深度优先搜索遍历_ _广度优先搜索遍历 方法
20．二叉树二叉排序充分必条件结点值均左孩子值右孩子值种说法__错误_____(回答正确正确)
21．序表{3410143443466475789096130}折半查找法查找值90结点___4____次较查找成功
三综合题
1．（1）已知某二叉树序遍历序列debca中序遍历序列dbeac试画出该二叉树
a
b
c
e
d
（2）述二叉树结点字符分代表整数（中没相等）恰该树成棵二叉排序树试出abcde关系
答：d （3）出该树前序遍历序列
答：abdec
2．（1）组记录关键字序列{454065433595}写出利快速排序方法第记录基准趟划分结果（求出趟划分中次扫描交换 结果）
答： 45 40 65 43 35 95
35 40 65 43 35 95
35 40 65 43 65 95
35 40 43 43 65 95
35 40 43 45 65 95

（2）序列{454065433595}利直接插入排序写出逐次插入程（第元素直第六元素）
答 40 45 65 43 35 95
40 43 45 65 35 95
35 40 43 45 65 95
40
28

72
3
100
54
6

3．（1）设整数序列{4028672100354}次取出序列中数构造棵二叉排序树
（2）述二叉排序树等概率条件求成功查找均查找长度
答：ASL（1x1+2x2+3x3+4）7187
4． (1) 设查找表{514261874163}次取表中数构造棵二叉排序树


2
4
6
16
7
3
18
5
145
（2）说明通序列二叉排序树相应序列排序结果
答：中序遍历
16
42

32
52
57
67
82
102
5．（1）利筛选程序列{42826710216325752}建成堆（根堆）画出相应完全二叉树（求中间程）
初始树 堆
42
82

67
52
57
32
16
102

（2）写出述堆应完全二叉树进行中序遍历序列
答：10252428216673257
四程序填空题
1．函数a[0]a[n1]中折半查找算法查找关键字等k记录查找成功返回该记录标失败时返回1完成程序中空格
typedef struct
{ int key
……
}NODE
int Binary_Search(NODE a[]int n int k)
{
int lowmidhigh
low0
highn1
while(__low {
mid(low+high)2
if(a[mid]keyk)
return __ mid ______
else if(__a[mid]key lowmid+1
else _ highmid1_____
}
__ return 1____
}
2．函数链栈进栈操作x进栈结点数域top栈顶指针
struct node
{ ElemType data
struct node *next
}
struct node *top
void Push(ElemType x)
{
struct node *p
p(struct node*)malloc(_sizeof (struct node)___)
p>datax
__ p>nexttop ___
__ topp __
}


3．函数链队列入队操作x入队结点数域值frontrear分链队列队头队尾指针
struct node
{ ElemType data
struct node *next
}
struct node *front*rear
void InQueue(ElemType x)
{
struct node *p
p (struct node*) ___ malloc(sizeof (struct node))____
p>datax
p>nextNULL
__ rear>nextp ____
rear ___ p _____
}



期末综合练二

单项选择题
1．（ B ）性质相数元素集合数子集
A．数元素 B．数象 C．数结构 D．数项
2．种逻辑结构（ B ）
A．唯存储结构 B．存储结构
C．表示某种数元素间关系 D．三种说法均正确
3．设链表中结点NODE类型结构体变量NODE *p申请新结点p指该结点语句（ A ）
A．p(NODE *)malloc(sizeof(NODE))
B．p(*NODE)malloc(sizeof(NODE))
C．p(NODE )malloc(sizeof(p))
D．p(NODE *)malloc(sizeof(p))
4．链表具备特点（ C ）
A．机访问结点 B．占连续存储空间
C．插入删元素操作需移动元素结点 D．通标链表进行直接访问
5．设序存储线性长度n第i元素前插入新元素课算法i （ D ）时移动元素次数2
A．n2 B．n C．1 D．n1
6．数物理结构（ D ）
A．数逻辑结构关 B．仅仅包括数元素表示
C．包括数元素间关系表示 D．包括数元素表示关系表示
7．栈进栈序列1234栈出栈序列（ B ）（进出栈操作交进行）
A．3241 B．1423
C．4321 D．3214
8．线性结构中数元素位置间存（ A ）关系
A． B．
C． D．元素直接前驱直接继
9．设带头结点链队列队列中结点数域data指针域next组成frontrear分链队列头指针尾指针设p指入队新结点(该结点已赋值)入队操作（ A ）
A．rear>nextprearp B．rear>nextp p rear
C．p rear>nextrearp D．rearprear>nextp
10．表中机访问（ D ）
A．单链表 B．双链表
C．单循环链表 D．序表
11．说法正确（ C ）
A．序栈中栈满时进行进栈操作称溢
B．序栈中栈空时作出栈栈操作称溢
C．序队列中尾指针已超越队列存储空间界定队列已满
D．序队列中队列头指针尾指针均超越队列存储空间界队列已空
12．算法时间复杂度（ C ）关
A．计算机 B．计算机操作系统
C．算法身 D．数结构
13．设20阶称矩阵A采压缩存储方式三角部分行序序存储维数组中（矩阵A第元素a11数组b标1开始）矩阵元素a85维数组b中标（ D ）
A．30 B．28 C．40 D．33
14．设长度n序表删第i元素需移动元素数（ B ）
A．ni+1 B．ni C．ni1 D．i
15．深度5完全二叉树第5层4结点该树（ D ）结点
A．28 B．30 C．31 D．19
16．单链表中pq分指表中两相邻结点q指结点p指结点直接继现删q指结点语句（ C ）
A．pq>next B．p>nextq C．p>nextqànext D．q>nextNULL
17．已知图顶点度数mm定（ D ）
A．4 B．8 C．12 D．9
18．栈顶指针top链栈中删结点时变量x保存删结点值执行（ A ）
A．xtop>data toptop>next B．xtop>data
C．toptop>next xtop>data D．toptop>next xdata
19．说法正确（ D ）
A．连通图G生成树中包含回路
B．连通图G生成树连通
C．连通图G生成树定唯
D．连通图G生成树定连通包含回路
20．链队中假设fr分队头队尾指针删结点运算（ C ）
A．rf>next B．rr>next C．ff>next D．fr>next
21． n元素进行泡排序通常进行n1趟泡第j趟泡中进行（ C ）次元素间较
A．j B．j1 C．nj D．nj1
22．栈进栈序列abcde栈输出序列（ A ）（进栈出栈交进行）
A．dceab B．edcba C．decba D．abcde
23．排序程中效减少趟排序程中元素间较次数算法（ D ）
A．泡 B．选择 C．直接插入 D．折半插入
24．长度10序表折半查找该表进行查找等概率情况查找成功均较次数（ B ）
A．2610 B．2910 C．299 D．3110
25．图1顶点a出发深度优先搜索法进行遍历顶点序列（ B ）
a
b
e
c
d
f
A．aebcfd
B．abedcf
C．acebdf
D．acfbde




图1

26．排序算法中未排序序列中次取出元素已排序序列（初始空）中元素进行较（求较次数量少）然放入已排序序列正确位置方法（ C ）
A．泡 B．直接插入 C．折半插入 D．选择排序
27．棵哈夫曼树n叶子结点（终端结点）该树总（ B ）结点
A．2n2 B．2n1 C．2n D．2n+2
28．设10阶称矩阵A采压缩存储方式三角部分行序存储维数组B中（数组标1开始）矩阵中元素A85维数组B中标（ A ）
A．33 B．32 C．85 D．41
29．数（ A ）结构计算机关
A．逻辑 B．物理 C．存储 D．逻辑存储
30．图中顶点度数等边数（ D ）倍
A．3 B．25 C．15 D．2
二填空题
1．通常含章节书目录结构抽象成___树形__结构
2．栈队列操作特点分__先进出___ ___先进先出__
3．单链表中p指结点插入s指新结点链表中结点指针域next执行__ s>next p>next______p>nexts操作
4．结构中数元素存关系称____图状 （网状）__结构
5．设非空链栈栈顶指针hs进行出栈操作x保存出栈结点值栈结点指针域next执行xhs>data ___ hshs>next___ __
6．根数元素间关系特性通常分集合线性树形 图状 四类基结构
7．带头结点非空链队中fr分队头队尾指针队结点数域data指针域next进行出队操作变量x存放出队元素数值相关操作xf>data __ ff>next____ __
8．求n数元素中找中值元素设基操作元素间较较次数算法时间复杂度分________ _ n1O(n)_______
9．循环队列存储空间MaxSize8采少元素空间效判断栈空栈满队头指针front4队尾指针rear ____ 4 ____时队列空rear ___ 2 _____时队列6元素
10．稀疏矩阵存储时采__行号__ ___列号 _ __非零元__3部分信息组成三元组唯确定矩阵中非零元素
11．二叉树链式存储结构中通常结点中设置三域值域 左指针 右指针
12．棵二叉树序编号6结点（树中结点编号等深度完全二叉中应位置结点编号相）存右孩子右孩子编号___13_____
13．栈顶指针h链栈中插入s指结点时执行s>nexth__ hs __
14．链队中设fr分队头队尾指针插入s指结点操作__ r>nexts __rs (结点指针域next)
15．图2示二叉树前序遍历序列___ abdefcg __
g
f
a
b
d
e
c












图2

16．设棵深度4完全二叉树第四层5结点该树___12__结点（根结点第1层）
17．队列序存储结构中插入新队列元素时尾指针值增1删元素队列时 头 指针值增1
18．稀疏矩阵进行压缩存储矩阵中非零元素应三元组包括该元素__行标___列标____非零元素值_三项信息
19．循环队列引入目克服 假溢
20．组记录(553997221673654788)进行直接插入排序时第7记录65插入序表时寻找插入位置需较___3______次
三综合题
1．（1）设head1p1分带头结点单链表A头指针尾指针head2p2分带头结点单链表B头指针尾指针B链表接A链表head1头指针单循环链表写出中两关键赋值语句（完整程序结点链域next）
答：p1>next head2p2>next head1
（2）单链表链域next设指针p指单链表中某结点指针s指插入链表新结点现s指结点插入p指结点某学生采语句：
p>nexts s>nextp>next
样做正确？正确回答正确正确说明应改写
答：s>next p>nextp>nexts
2．
(1)234789作叶结点权构造棵哈夫曼树( 求结点左子树根结点权等右子树根结点权)出相应权重值叶结点哈夫曼编码



33

(1)

15
18


7
9
9
8



5
4



3
2

2：1110
3 1111
4：110
7：00
8：01
9：10
(2) 棵哈夫曼树n叶结点少结点？简述理？
答 2n1非叶结点数叶结点数少
3．（1）画出长度10序表进行折半查找判定树（序号12……10表示树结点）

5
2

8
4
9
6
3

10
7
1

（2）述序列进行折半查找求等概率条件成功查找均查找长度
答：ASL（1x1+2x2+3x4+4x3）102910
4．组记录关键字序列（467956384084）
（1）利快速排序方法出第记录基准次划分结果（出逐次交换元素程求升序排列）
初始序列
467956384084
407956384084
407956387984
403856387984
403856567984
403846567984

（2）述序列堆排序方法建立根堆求二叉树逐次描述建堆程

37
77

62
47
52
27
11
97
11
37

27
47
52
62
77
97
56
79
38
40
84
46
84
79
38
40
46
566
56
79
38
40
46
79
38
40
84
84
56
46
5．（1）利筛选法序列{3777629711275247}建成堆（根堆）画出相应完全二叉树
初始树 堆


（2）写出述堆应二叉树进行前序遍历序列
答：1137479777276252
6．设查找表(506075859698105110120130)
(1) 说出进行折半查找成功查找元素120需进行少次元素间较？
3次
(2) 折半查找元素95少次元素间较确定查？
4次
96
75
98
130
105
85
50
11005
120
60
（3）画出述序表进行折半查找应判定树(求数元素作树结点)









四程序填空题
1．函数直接选择排序算法a[1]a[2]…a[n]中记录进行直接选择排序完成程序中空格
typedef struct
{ int key
……
}NODE
void selsort(NODE a[]int n)
{
int ijk
NODE temp
for(i1i< __ n1___i++)
{
ki
for(ji+1j< ___ n ___j++)
if(a[j]key if(ik)
{
tempa[i]
__ a[i]a[k]___
___ a[k]temp _
}
}
}
2．尾插法建立带头结点n结点单链表程序结点中数域前次123……n完成程序中空格部分
NODE *create(n)
{NODE *head *p *q
int i
p(NODE*)malloc(sizeof(NODE))
head p qp pànextNULL *建立头结点*
for(i1 i{ p (NODE*)malloc(sizeof(NODE))
pàdatai
pànextNULL
qànext p
qp
}
return(head)
}
3．程序中序遍历二叉树递算法程序完成程序中空格部分（树结构中左右指针域分leftright数域data字符型BT指根结点）
void Inorder (struct BTreeNode *BT)
{ if(BTNULL){
Inorder(BT>left)
printf(cBT>data)
Inorder(BT>right)
}
}

期末综合练三

单项选择题
1．深度5完全二叉树20结点第5层（ C ）结点(根结点第层)
A．3 B．8 C．5 D．6
2．C语言中序存储长度3字符串需占（ A ）字节
A．4 B．3 C．6 D．12
3．已知图边数m该图顶点度数（ A ）
A．2m B．m C．2m+1 D．m2
4．串函数StrCat（ab）功进行串（ D ）
A．较 B．复制 C．赋值 D．连接
5．数结构中计算机关数（ D ）结构
A．物理 B．存储 C．逻辑物理 D．逻辑
6．棵n结点采链式存储二叉树中（ A ）指针域空
A．n+1 B．n C．n1 D．n2
7．链表具备特点（ C ）
A．机访问结点 B．占连续存储空间
C．插入删需移动元素结点 D．通标链表进行直接访问
8．设棵哈夫曼树n非叶结点该树（ B ）叶结点
A．n B．n+1 C．n1 D．2n
9．线性表（ C ）方式存储进行折半查找
A．链接 B．序 C．关键字序序 D．二叉树
10．栈顶指针top链栈中删结点时变量x保存删结点值执行（ A ）
A．xtop>data toptopànext B．xtop>data
C．toptop>next xtop>data D．toptop>next xdata
11．散列查找原理（ A ）
A．查记录关键字值该记录存储位置间建立确定应关系
B．查记录关键字序序方式存储
C．关键字值较进行查找
D．基二分查找方法
12．棵完全二叉树5层第5层六结点该树（ C ）结点
A．30 B．20 C．21 D．23
13．n元素进行泡排序某趟泡中进行（ C ）次元素间交换表明序列已排序
A．1 B．2 C．0 D．n1
14．图中顶点度数等边数（ D ）倍
A．3 B．25 C．15 D．2
15．排序程中趟序子表中排序记录关键字放置已排序子序列适位置直全部排序止该排序算法( A )
A．直接插入排序 B．快速排序
C．泡排序 D．选择排序
16．已知图1示图顶点V1出发深度优先搜索法进行遍历种顶点序列（ A ）
A．V1V2V4V8V5V3V6V7 B．V1V2V4V5V8V3V6V7
C．V1V2V4V8V3V5V6V7 D．V1V3V6V7V2V4V5V8
V6
V7
V1
V2
V3
V8
V4
V5

图1
17．组元素（6448106332582705593）进行直接插入排序时进行第7元素70插入已排序子表时找插入位置需进行（ C ）次元素间较（指排序）
A．6 B．2 C．3 D．4
18．已知图2示图顶点a出发广度优先搜索法进行遍历种顶点序列（ B ）
A．abcedf B．abcefd C．aebcfd D．acfdeb
b
d
f
e
c
a

图2
19．采序查找法长度n线性表进行查找（采表尾设监视哨方法）坏情况进行（ B ）次元素间较
A．n+2 B．n C．n1 D．n2
20．二叉排序树进行（ C ）遍历遍历序列序序列
A．层次 B．序 C．中序 D．前序
21．图3顶点a出发广度优先搜索法进行遍历顶点序列（ B ）
A．acebdgf
B．abecdgf
C．acfedgb
D．abecfdg
a
b
e
c
d
f
g







图3
22．序表{247143443476475809097120}中折半查找法查找值80时（ B ）次较查找成功
A．4 B．2 C．3 D．5
23．元素2468序次进栈该栈输出序列（ D ）（进栈出栈交进行）
A．8642 B．2468
C．4286 D．8624
24．长度9序表折半查找该表进行查找等概率情况查找成功均较次数（ B ）
A．2510 B．259 C．209 D．179
25．排序方法中未排序序列中挑选元素次放入已排序序列（初始空）端方法称（ C ）排序
A． B．插入 C．选择 D．快速
26．排序算法中未排序序列中次取出元素已排序序列（初始空）中元素进行较（求较次数量少）然放入已排序序列正确位置方法（ C ）
A．泡 B．直接插入 C．折半插入 D．选择排序
27．棵哈夫曼树总23结点该树（ D ）叶结点（终端结点）
A．10 B．13 C．11 D．12
28．组记录关键字序列（467956384084）利快速排序第关键字分割元素次划分结果（ B ）
A．403846795684 B．403846567984
C．403846845679 D．384046567984
29．队列插入操作（ B ）进行
A．队头 B．队尾 C．队头队尾 D．意指定位置


二填空题（题2分24分）
1．棵二叉树没单分支结点6叶结点该树总____11____结点
2．二叉树链式存储结构中通常结点中设置三域_值域__ 左指针
右指针
3．设棵完全二叉树高层右边叶结点编号奇数该叶节点双亲结点编号10该完全二叉树___21___结点
4．棵二叉树中序编号i结点存左右孩子左右孩子编号分____2i ____2i+1____
5．二叉树递定义二叉树遍历常算法__先序_ ___中序 _ __序_三种
6．串两种基存储方式__序存储_ __链式存储___
7．数结构中数元素存关系称___树形_____结构
8．棵2n1结点二叉树非叶结点度数2该树___N____叶结点
9．数存储计算机中具体体现数间逻辑结构称___物理（存储）_____结构
10．棵具n结点二叉树相应链式存储结构中__ n+1______指针域空
11．结构中数元素存关系称__线性__结构
12．__中序______遍历二叉排序树序序列
13．图4示二叉树序遍历序列 gdbeihfca
e
f
g
i
b
a
c
h
d













图4

14．n元素进行泡法排序通常需进行__ n1__趟泡
15．图5示二叉树先序遍历序列__ abdefcg __
g
f
a
b
d
e
c












图5

16．二叉树二叉排序充分必条件结点值均左孩子值右孩子值种说法__正确____(回答正确正确)
17．图深度优先搜索广度优先搜索序列定唯断言_正确_____(回答正确正确)
18．根搜索方法图遍历__深度优先搜索遍历_ _广度优先搜索遍历_ 两种方法
19．记录序列排序指记录某关键字排序记录序列__关键字_______排序结果唯
20．某关键字记录序列排序关键字 相等 记录排序前排序保持前关系排序算法稳定否稳定
16
42

32
52
57
67
82
102
三综合题
1．（1）利筛选程序列{42826710216325752}建成堆（根堆）画出该堆（求中间程）

（2）写出述堆应完全二叉树进行中序遍历序列
答：10252428216673257
2．设查找表(16152053647)
(1)泡法该表进行排序（求升序排列）写出趟排序程通常n元素进行泡排序进行少趟泡？第j趟进行少次元素间较？
答： (1)原序列16 15 20 53 64 7
15 16 20 53 7 64 n1趟
15 16 20 7 53 64 nj次
15 16 7 20 53 64
15 7 16 20 53 64
7 15 16 20 53 64

(2)排序序表基础画出进行折半查找应判定树(求数元素作树结点)
7
15
20
64
16
53








(3)均查找长度（1*1+2*2+3*3）6146
3．
2
4
6
16
7
3
18
5
14
(1) 设查找表{514261874163}次取表中数构造棵二叉排序树

（2）说明序列二叉排序树相应序列排序结果述二叉排序出中序遍历结果
答： 中序遍历
中序 234567141618
4．（1）设整数序列{503816821101364}次取出序列中数构造棵二叉排序树

50
38

82
13
110
64
16


（2）利述二叉排序树查找110少次元素间较成功查查找15少次元素间较知道查找失败
答： 三次四次
5．（1）定权值213345构造哈夫曼树
5
3
4
18
11
7
6
3
3
1
2












wpl145

（2）样述权值构造棵哈夫曼树两棵哈夫曼树高度分求两棵树带权路径长度

18
7
11
3
1
2
3
3
4
6
5
四程序填空题
1．函数链队列入队操作x入队结点数域值frontrear分链队列队头队尾指针
struct node
{ ElemType data
struct node *next
}
struct node *front*rear
void InQueue(ElemType x)
{
struct node *p
p (struct node*) __ malloc(sizeof (struct node))__
p>datax
p>nextNULL
__ rear>nextp ___
rear __ p ____
}
2．设线性表（610164）程序说明结构变量方法建立单链表输出链表中结点中数
#define NULL 0
void main( )
{NODE abcd*head*p
adata6
bdata10
cdata16
ddata4 *d尾结点*
head &a
anext&b
bnext&c
cnext&d
d×nextNULL *结束建表程*
phead *p工作指针准备输出链表*
do
{printf(d＼n p>data )
pp>next
}while( pNULL )
}
3．函数head头指针具头结点单链表中删第i结点
struct node
{ int data
struct node *next
}
typedef struct node NODE
int delete(NODE *headint i )
{
NODE *p*q
int j
qhead
j0
while((qNULL)&&( __ j{
__ qq>next ___
j++
}
if(qNULL)
return(0)
p __ q>next ____
__ q>next ____p>next
free(___p ____)
return(1)
}
4．程序序遍历二叉树递算法程序完成程序中空格部分（树结构中左右指针域分leftright数域data字符型BT指根结点）
void Postorder (struct BTreeNode *BT)
{ if(BTNULL){
Postorder(BT>left)
Postorder(BT>right)
printf(cBT>data)
}
}

文档香网(httpswwwxiangdangnet)户传

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