自考数据结构历年考题综合

200610
1结点存储址关键字间存某种映射关系称种存储结构( )
A序存储结构 B链式存储结构
C索引存储结构 D散列存储结构
2长度n序表第i(1≤i≤n+1)位置插入元素元素移动次数( )
Ani+1 Bni
Ci Di1
3表首尾两端进行插入操作线性表宜采存储结构( )
A序表 B头指针表示单循环链表
C尾指针表示单循环链表 D单链表
4进栈序列abc通入出栈操作abc排列数( )
A4 B5 C6 D7
5．棵16结点完全二叉树层编号编号7结点X双亲结点右孩子结点编号分（　　　）
A．214 B．215
C．314 D．315
6．设5阶三角矩阵A［1515］现三角中元素列优先序存放堆数组B［115］中已知B［1］址100元素占2存储单元A［34］址（　　　）
A．116 B．118
C．120 D．122
7．带权连通图生成树（　　　）
A．棵棵 B．棵
C．定棵 D．存
8．列关图遍历说法中正确（　　　）
A．连通图深度优先搜索递程
B．图广度优先搜索中邻接点寻找具先进先出特征
C．非连通图深度优先搜索法
D．图遍历求顶点仅访问次
9．某算法空间花费s(n)2n+n100+nlog2n+n101空间复杂度（ ）
A． O(nlog2n) B O(n100) C O(n101) D O(2n)
10 单链表中存储密度定（ ）
A． 05 B 等1 C 01 D 1
11．序栈中删元素少移动（ ）元素
A． 0 B 1 C n2 D n
12．空串（ ）
A． 包含空格符串 B 长度0串
C 包含空格符串 D 含字母串
13．采三元组表存储稀疏矩阵（ ）
A． 节省存取时间 B 节省存储空间
C 提高矩阵元素访问速度 D 提高矩阵运算性
14．高度h二叉树（ ）节点
A． 2h1 B 2h C 2h1 D 2h1+1
15．N顶点e条边权图邻接矩阵中非零元素（ ）
A． n B ne C e D e+n
16．直接选择排序情况时间复杂度（ ）
A． O(n) B O(nlog2n) C O(1) D O(n2)
17．N结点m阶B树少包含（ ）关键字
A．(m1)*n B n C (「m2」1)*(n1)+1 D n*「m2」1)
18．散列文件中桶记录应具（ ）
A．相关键字 B 相散列值
C 相某属性值 D 相存取频率
19．坏情况查找成功时二叉排序树均查找长度（　　　）
A．序表均查找长度 B．序表均查找长度
C．序表均查找长度相 D．法序表均查找长度较
20．散列表中散列址引起堆积现象（　　　）
A．义词间发生突引起
B．非义词间发生突引起
C．义词间非义词间发生突引起
D．散列表溢出引起
二填空题（空15分计15分）
21．ALV树种衡二叉排序树树中结点( )
22．VSAM文件控制区间中记录存储方式( )
23．单链表存储密度（ ）序表存储密度
24．设SQ循环队列存储数组D[M]中SQ入队操作队尾指针rear修改（ ）
25．长度n串s1长度2n串s2较运算时间复杂度（ ）
26．广义表(((abc)def))长度（ ）
27．N（n>0）节点哈夫曼树恰含（ ）度1节点
28．深度n二叉树少（ ）结点
29．N（n>0）顶点连通图少（ ）条边
30．N（n>0）记录进行泡排序少交换（ ）记录
三简答题（题5分计30分）
31．出面森林应二叉树二叉树续序列（图1）


32．棵树3度节点1002度节点200该树叶子节点少该树少度1节点？
33．设广义表A A(((ab)x)((a)(b))(c(d(y))))写出Ay广义表A操作序列
34．画出普里姆算法构造面示带权图生成树示意图

35．写出列快排序列序列进行两次划分程结果
37 26 51 48 77 69 82 21 17 13 21 39 55 18
36．画出面5阶B树插入关键字37结果
四理解设计题（题5分计15分）
37．设某带头结头单链表结点结构说明：
typedef struct nodel { int data struct nodel*next }node
试设计算法：void copy(node*head l　node*head 2)head 1头指针单链表复制带头结点head2头指针单链表中（5分）
38 阅读列算法回答列问题：
(1)该算法采种策略进行排序
(2)算法中R[n+1]作什
typedef struct { KeyType key infoType otherinfo } nodeType
typedef nodeType SqList［MAXLEN］
void sort(SqList Rint n) { nMAXLEN1
int ki
for(kn1k>1k)
if(R[k]key>R[k+1]key) {
R[n+1]R[k]
for(ik+1R[i]key R[i1]R[n+1]
}}
39．面函数BinInsert功线性表R前n元素实现二分法插入排序请空缺处填入适语句够正确工作
TYPEDEF STRUCT NODE { INT KEY * OTHER INFO * } NODE
TYPEDEF NODE SEQLIST[100]

VOID BININSERT(SEQLIST RINT N)
{ INT LOWUPMIDIJ
NODE T
FOR(I0I { _____(1)________________
LOW0 __________(2)_____________
WHILE(LOW { MID(LOW+UP)2
IF(R[MID]KEYTKEY) {_________(3)__________ BREAK}
IF(TKEY }
FOR(JIJ>LOWJ) R[J]R[J1]
_________(6)_____________
}
}
五算法实现题（10分）
40假设二叉树T采定义存储结构：
typedef struct node { DataType data struct node *lchild*rchild*parent }PBinTree
中结点lchild域rchild域已分填指左右孩子结点指针parent域中值空指针(拟作指双亲结点指针域)请编写递算法该存储结构中结点parent域值修改成指双亲结点指针

2006
．单项选择题
1D 2B 3C 4B 5D 6C 7B 8D 9D 10D
11A 12B 13B 14A 15C 16A 17C 18B 19C 20B
二填空题
21左右子树树高差绝值1 23 24sq>rear(sq>rear+1) m 25O(n) 261 270
28 n 29 n 30 0
三简答题
31
G F E D C B J I K H A
32n0n2+2n3+1
200+2*100+1
401
33Tail(Head(Tail(Head(Tail(Tail(A)))))(y)
34

3518 26 21 13 17 21 3782 69 77 48 39 55 51
36

四阅读理解题
37边遍历边申请新结点链接head2序列中
38直接插入排序
哨兵避免边界检测提高程序运行效率
39tR[i] upi1
lowmid+1 upmid1 lowmid+1
R[low]t

2002
1．某算法空间花费s(n)2n+n100+nlog2n+n101空间复杂度（ ）
A． O(nlog2n) B O(n100) C O(n101) D O(2n)
2．单链表中存储密度定（ ）
A． 05 B 等1 C 01 D 1
3．序栈中删元素少移动（ ）元素
A． 0 B 1 C n2 D n
4．空串（ ）
A． 包含空格符串 B 长度0串
C 包含空格符串 D 含字母串
5．采三元组表存储稀疏矩阵（ ）
A． 节省存取时间 B 节省存储空间
C 提高矩阵元素访问速度 D 提高矩阵运算性
6．高度h二叉树（ ）节点
A． 2h1 B 2h C 2h1 D 2h1+1
7．N顶点e条边权图邻接矩阵中非零元素（ ）
A． n B ne C e D e+n
8．直接选择排序情况时间复杂度（ ）
A． O(n) B O(nlog2n) C O(1) D O(n2)
9．N结点m阶B树少包含（ ）关键字
A．(m1)*n B n C (「m2」1)*(n1)+1 D n*「m2」1)
10．散列文件中桶记录应具（ ）
A．相关键字 B 相散列值
C 相某属性值 D 相存取频率
11．某算法时间花费T(n)005n2+100n+10该算法时间复杂度（ ）
12．单链表存储密度（ ）序表存储密度
13．设SQ循环队列存储数组D[M]中SQ入队操作队尾指针rear修改（ ）
14．长度n串s1长度2n串s2较运算时间复杂度（ ）
15．广义表(((abc)def))长度（ ）
16．N（n>0）节点哈夫曼树恰含（ ）度1节点
17．深度n二叉树少（ ）结点
18．N（n>0）顶点连通图少（ ）条边
19．N（n>0）记录进行泡排序少交换（ ）记录
20．倒排文件倒排表项包含（ ）记录址
21．出面森林应二叉树二叉树续序列（图1）
22．棵树3度节点1002度节点200该树叶子节点少该树少度1节点？
23．设广义表A A(((ab)x)((a)(b))(c(d(y))))写出Ay广义表A操作序列
24．设程序：
int f(int a[]int nint key)
{ int i
for (i0i if(a[i]key) return i
return 1
}
keya[j](j012…n1)中概率2(j+1)keya中概率2n查找Key时均较Key次数少该算法时间复杂度少？
25．画出普里姆算法构造面示带权图生成树示意图


四理解题（题6分计12分）
26．指出面函数GV功返回值含义中Tab存储稀疏矩阵A非零元素长度LEN三元组表
#INCLUDE
TYPEDEF STRUCT {INT ROWCOLVAL} TRITUPLENODE

INT GV(INT IINT JINT LENTRITUPLENODE TAB[])
{ INT K
FOR(K0 K IF(TAB[K]ROWI && TAB[K]COLJ) RETURN TAB[K]VAL
RETURN 0
}
27．设P1P2两单链表元素递增序指出面函数F功
TYPEDEF INT DATATYPE
TYPEDEF STRUCT NODE {DATATYPE DATA STRUCT NODE * NEXT} LISTNODE
TYPEDEF LISTNODE * LINKLIST
LINKLIST F(LINKLIST P1 LINKLIST P2)
{ LINKLIST HNULL P
WHILE(P1&&P2)
{ IF(P1>DATADATA) { PP1 P1P1>NEXT }
ELSE { PP2 P2P2>NEXT}
P>NEXTH HP
}
WHILE(P1) { PP1 P1P1>NEXT P>NEXTH HP}
WHILE(P2) { PP2 P2P2>NEXT P>NEXTH HP}
RETURN H
}
五填充题（题18分）
28．面函数BinInsert功线性表R前n元素实现二分法插入排序请空缺处填入适语句够正确工作
TYPEDEF STRUCT NODE { INT KEY * OTHER INFO * } NODE
TYPEDEF NODE SEQLIST[100]

VOID BININSERT(SEQLIST RINT N)
{ INT LOWUPMIDIJ
NODE T
FOR(I0I { _____(1)________________
LOW0 __________(2)_____________
WHILE(LOW { MID(LOW+UP)2
IF(R[MID]KEYTKEY) {_________(3)__________ BREAK}
IF(TKEY }
FOR(JIJ>LOWJ) R[J]R[J1]
_________(6)_____________
}
}
2002D
单项选择题
1D 2D 3A 4B 5B 6A 7C 8D 9C 10B
二填空题(题2分30分)
11 O(n2)12 13．rear(rear+1) m 14 O(n)15 1 16 017 n18 n 19 0 20 次关键字
三简答题
21（见图）序序列GFEDCBJIKHA
22叶结点401度1结点意
24均较次数1*2(0+1)+2*2(1+1)+……+n*2((n1)+1)+n*2n
22(n1)n*2n
时间复杂度：O(1)
25见图

四理解题
26三元组表Tab中查找稀疏矩阵中元素A[IJ]值值作函数返回值
27两递增序单链表合递减序单链表
五填充题
tR[i] upi1 lowmid+1
upmid1 lowmid+1 R[low]t
200210
单项选择题(题15题题2分30分)题列出四选项中选项符合题目求请正确选项前字母填题括号
1结点存储址关键字间存某种映射关系称种存储结构( )
A序存储结构 B链式存储结构
C索引存储结构 D散列存储结构
2长度n序表第i(1≤i≤n+1)位置插入元素元素移动次数( )
Ani+1 Bni
Ci Di1
3表首尾两端进行插入操作线性表宜采存储结构( )
A序表 B头指针表示单循环链表
C尾指针表示单循环链表 D单链表
4进栈序列abc通入出栈操作abc排列数( )
A4 B5 C6 D7
5查找某特定单词文中出现位置应串运算( )
A插入 B删 C串联接 D子串定位
6已知函数Sub(sij)功返回串s中第i字符起长度j子串函数Scopy(st)功复制串ts字符串S″SCIENCESTUDY″调函数Scopy(PSub(S17))( )
AP″SCIENCE″ BP″STUDY″
CS″SCIENCE″ DS″STUDY″
7三维数组A[4][5][6]行优先存储方法存储存中元素占2存储单元数组中第元素存储址120元素A［３］[4][5]存储址( )
A356 B358 C360 D362
8右图示广义表种( )
A线性表
B纯表
C结点享表
D递表

9列陈述中正确( )
A二叉树度2序树
B二叉树中结点孩子时左右分
C二叉树中必度2结点
D二叉树中两棵子树左右分
10n顶点完全图中含边数目( )
An1 Bn Cn(n1)2 Dn(n1)
11已知图右示顶点a出发进行深度优先偏历DFS序列( )
Aa d b e f c Ba d c e f b Ca d c b f e Da d e f c b
12坏情况时间复杂度均O(nlogn)稳定排序方法( )
A快速排序 B堆排序 C排序 D基数排序
13生成右图示二叉排序树关键字序列( )
A4 5 3 1 2
B4 2 5 3 1
C4 5 2 1 3
D4 2 3 1 5

14ALV树种衡二叉排序树树中结点( )
A左右子树高度均相 B左右子树高度差绝值超1
C左子树高度均右子树高度 D左子树高度均右子树高度
15VSAM文件控制区间中记录存储方式( )
A序序 B序序
C序链接 D序链接
二填空题(题10题题2分 两空格空格1分20分)
16算法中语句频度T(n)3720n+4nlogn算法时间复杂度________
17图示链表中指针p指结点插入数域值相继ab两结点列两语句实现该操作次________________







18假设SX分表示进栈退栈操作输入序列abcde进行系列栈操作SSXSXSSXXX输出序列________
19串S″I am a worker″长度________
20假设10阶三角矩阵A列优序压缩存储维数组C中C数组应________
21n结点线索二叉链表中________线索指针
22采邻接矩阵结构存储具n顶点图该图进行广度优先遍历算法时间复杂度________
23关键字序列(528063444891)进行趟快速排序结果________
2410000结点构成二叉排序树等概率查找假设查找成功时均查找长度值达________
25找出工资低1500元职称副教授工资低2000元职称教授记录查询条件________
三解答题(题4题题5分20分)
26已知6行5列稀疏矩阵中非零元值分：9041762854658矩阵中列号次：1451245带行表三元组表作存储结构时行表RowTab中值次002235请写出该稀疏矩阵(注：矩阵元素行列标均1开始)
27已知树T先序遍历序列ABCDEFGHIJKL序遍历序列CBEFDJIKLHGA请画出树T
28关键字序列(7287612394160558)进行堆排序关键字递减次序排列请写出排序程中初始堆前三趟序列状态
初始堆：________ 第1趟：________
第2趟：________ 第3趟：________
29关键字序列(0712151827324192)中二分查找法查找定值92相等关键字请写出查找程中次定值92较关键字
四算法阅读题(题4题题5分20分)
30函数中h带头结点双循环链表头指针
(1)说明程序功(2)链表中结点数分16(包括头结点)时请写出程序中while循环体执行次数

int f(DListNode *h)
{
DListNode *p*q
int j1
ph>next
qh>prior
while(pq && p>priorq)
if(p>dataq>data)
{
pp>next
qq>prior
}
else j0
return j
}

31设栈S(1234567)中7栈顶元素请写出调algo(&s)栈S状态
void algo(Stack *S)
{int i0
Queue Q Stack T
InitQueue(&Q)InitStack(&T)
while (StackEmpty(S))
{
if((ii)0)Push(&TPop(&S))
else EnQueue(&QPop(&S))
}
while(QueueEmpty(Q))
Push(&SDeQueue(&Q))
while(StackEmpty(T))
Push(&SPop(&T))}
32已知带权图邻接矩阵表示邻接表表示形式说明分：

#define MaxNum 50图顶点数
#define INFINITY INT_MAX INT_MAX整数表示∞
typedef struct{
char vexs[MaxNum]字符类型顶点表
int edges[MaxNum][MaxMum]权值整型邻接矩阵
int ne图中前顶点数边数
}MGraph邻接矩阵结构描述
typedef struct node {
int adjvex邻接点域
int weight边权值
struct node *next链指针域
} EdgeNode边表结点结构描述
typedef struct {
char vertex顶点域
EdgeNode * firstedge边表头指针
} VertexNode 顶点表结点结构描述
typedef struct {
VertexNode adjlist[MaxNum]邻接表
int ne图中前顶点数边数
} ALGraph邻接表结构描述

列算法根带权图邻接矩阵存储结构G1建立该图邻接表存储结构G2请填入合适容成完整算法

void convertM(MGraph *G1ALGraph *G2)
{ int ij
EdgeNode * p
G2>nG1>n
G2>eG1>e
for(i0ini++)
{
G2>adjlist[i]vertexG1>vexs[i]
G2>adjlist[i]firstedge (1)
}
for (i0ini++)
for (j0jnj++)
if(G1>edges[i][j] { p(EdgeNode *) malloc(sizeof(EdgeNode))
p>weight (2)
p>adjvexj
p>nextG2>adjlist[i]firstedge
(3)
}}
33阅读列算法回答列问题：
(1)该算法采种策略进行排序
(2)算法中R[n+1]作什
Typedef struct {
KeyType key
infoType otherinfo
} nodeType
typedef nodeType SqList［MAXLEN］
void sort(SqList Rint n)
{
nMAXLEN1
int ki
for(kn1k>1k)
if(R[k]key>R[k+1]key)
{
R[n+1]R[k]
for(ik+1R[i]key R[i1]R[i]
R[i1]R[n+1]
}
}

五算法设计题(题10分)
34假设二叉树T采定义存储结构：
typedef struct node {
DataType data
struct node *lchild*rchild*parent
}PBinTree
中结点lchild域rchild域已分填指左右孩子结点指针parent域中值空指针(拟作指双亲结点指针域)请编写递算法该存储结构中结点parent域值修改成指双亲结点指针





90


41










76
28
54






65
8
．单项选择题
1D 2A 3A 4B 5D
6A 7A 8C 9D 10D
11A 12B 13A 14B 15D
二填空题
16 O(nlogn) 17b>nextp>next p>nexts
18bceda 1914
2046　 21n+1
22O（n²）　 23 484482638091
24 (10000+1)2
25 职称副教授and工资<1500 or职称教授and and工资<2000
三简答题
26
27树序序列等价二叉树中序遍历序列先等价二叉树然转化相应树

28 　初始堆：0523165894726187第趟：1623615894728705
第二趟：2358618794721605 第三趟：5872618794231605
29．18 32 41 92
四算法阅读题
30(1) 检查循环链表中头结点两端应位置处结点值否称相等
(2) 结点数1时循环次数0次
结点数0时循环次数3次

31 7 5 3 1 2 4 6 （7栈顶）
32(1)NULL
(2)G1>edges[i][j]
(3)G2>adjlist[i]firstedgep
33(1)右侧进行直接插入排序
(2)R[n+1]作哨兵

五算法设计题
34BintreeNode *pre preNULL
void xiugai(BinTree *T)
{ if(T)
{ xiugai ((*T) >lchild)
(*T)>parentpre
pre(*T)
xiugai ((*T) >rchild)
}}

200310
1．列说法正确（　　　）
A．数数元素基单位
B．数元素数项中分割标识单位
C．数干数元素构成
D．数项干数元素构成
2．数结构基务（　　　）
A．逻辑结构存储结构设计 B．数结构运算实现
C．数结构评价选择 D．数结构设计实现
3．具n结点序单链表中插入新结点插入然序该操作时间复杂性量级（　　　）
A．O（1） B．O（n）
C．O（nlog2n） D．O(n2)
4．序存储线性表（a1a2…an）结点前插入新结点时需移动结点均次数（　　　）
A．n B．n2
C．n+1 D．(n+1)2
5．列树U′剪枝运算DELETE（U′x2）（　　　）

6．棵16结点完全二叉树层编号编号7结点X双亲结点右孩子结点编号分（　　　）
A．214 B．215
C．314 D．315
7．设5阶三角矩阵A［1515］现三角中元素列优先序存放堆数组B［115］中已知B［1］址100元素占2存储单元A［34］址（　　　）
A．116 B．118
C．120 D．122
8．带权连通图生成树（　　　）
A．棵棵 B．棵
C．定棵 D．存
9．列关图遍历说法中正确（　　　）
A．连通图深度优先搜索递程
B．图广度优先搜索中邻接点寻找具先进先出特征
C．非连通图深度优先搜索法
D．图遍历求顶点仅访问次
10．坏情况查找成功时二叉排序树均查找长度（　　　）
A．序表均查找长度 B．序表均查找长度
C．序表均查找长度相 D．法序表均查找长度较
11．闭散列表中散列址引起堆积现象（　　　）
A．义词间发生突引起
B．非义词间发生突引起
C．义词间非义词间发生突引起
D．散列表溢出引起
12．外存设备观点存取操作基单位（　　　）
A．逻辑记录 B．数元素
C．文件 D．物理记录
13．文件进行检索操作时次第记录开始文件（　　　）
A．序文件 B．索引文件
C．序索引文件 D．散列文件
14．组记录键值（46741853142040388665）利堆排序方法建立初始堆（　　　）
A．（14183846654020538674）
B．（14381846652040 538674）
C．（14182038404653657486）
D．（14862038404653657418）
15．序列（228619491230653518）进行趟排序结果：（181219224930653586）认排序方法（　　　）
A．选择排序 B．泡排序
C．快速排序 D．插入排序

二填空题（题13题空2分26分）
请题空格中填正确答案错填填均分
16．表示逻辑关系存储结构四种方式序存储方式链式存储方式_______________散列存储方式
prior
data

next
17．设某非空双链表结点形式　 删指针q指结点需执行述语句段：q>prior>next＝q>next _______________
18．图示设输入元素序ABCD通栈变换输出端种排列输出序列第元素D输出序列_______________

19．队列中允许进行删端________________
20．设棵二叉树中度2结点数10该树叶子数________________
21．图示二叉树根遍历输出序列________________

22．具n顶点完全图弧数________________
23．查找表数结构线性表树型结构等逻辑结构________________
24．长度L序表采设置岗哨方式序查找查找成功查找长度________________
25．开散列表查找某元素时通常分两步进行首先必须计算该键值散列址然址指针指________________中查找该结点
26．文件检索序存取________________关键字存取三种方式
27．排序n记录中取记录该记录键值作标准记录分两组第组中记录键值均等该键值第二组中记录键值均该键值然该记录排两组中间分成两组分述方法直记录排适位置止种排序方法称________________
28．组记录关键字（543896231572604583）进行泡排序时整泡排序程中需进行________________趟完成

三应题（题5题30分）
29．设序队列sq容量5初始状态时sqfrontsqrear0画出做完列操作队列头尾指针状态变化情况入队请简述理停止（6分）
（1） deb入队
（2） de出队
（3） ij入队
（4） b出队
（5） nop入队
30．已知图G邻接矩阵假设行元素访问时必须右左请写出V0开始深度优先搜索序列（4分）

31．画出列二叉树二叉链表表示图（6分）
　　　　　　　　　　　　　　
32．二分查找法长度10序表进行查找填写查找元素需较次数（8分）
元素标
1
2
3
4
5
6
7
8
9
10
较次数










33．已知序列（10184361219158）请出采二路排序法该序列进行升序排序时趟结果（6分）
四设计题（题2题14分）
34．设某带头结头单链表结点结构说明：
typedef struct nodel
{
int data
struct nodel*next
}node
试设计算法：void copy(node*head l　node*head 2)head 1头指针单链表复制带头结点head2头指针单链表中（6分）
35．修改泡排序法实现双泡排序双泡排序指第次记录放表尾第二次记录放表头反复进行试编写修改算法：void dbubble(int a[]int n)（8分）
单项选择题
1C 2B 3B 4D 5C6D 7A 8A 9C 10C 11B 12D 13A 14B 15C
二填空题
16．索引存储方式 17 q>next>priorq>prior 18 D C B A 19 队首
20 11 21 D B F H G E C A 22 N（N1） 24 L+1 25链表中
26 机存取 27快排序 287
三应题：
29图形略提示序表队列般循环结构否着出队入队次数增定会出现队尾益出序表情况
30V0 V2 V4 V3 V1
32较次数序： 3234134234
33第趟：（10 8） （3 4） （6 12） （1 9） （8 15）
第二趟：（3 4 8 10） （1 6 9 12） （8 15）
趟末尾入剩余组结果：
（3 4 8 10） （1 6 8 9 12 15）
第三趟：（1 3 4 6 8 9 10 12 15
四设计题：
34void copy(node * head1 *head2)
{ node *p *q *r
phead1>next
if(pNULL) { printf(Error) return}
while(p)
{ q(node *)malloc(sizeof(node))
q>datap>data q>nextNULL
if(head2NULL)
{ head2q r2q}
else
{ r2>nextq r2q}}
}

200410
1．数结构中数逻辑结构分成（　　　）
A．部结构外部结构 B．线性结构非线性结构
C．紧凑结构非紧揍结构 D．动态结构静态结构
2．单链表存储结构线性表中数元素间逻辑关系（　　　）
A．数元素相邻址表示 B．数元素表中序号表示
C．指继元素指针表示 D．数元素值表示
3．设p指单链表中结点s指插入结点述程序段功（　　　）
　　　　　s > next p > next p > next s
t p > data p > data s > data s >data t
A．结点*p结点*s数域互换
B．p指结点元素前插入元素
C．p指结点元素插入元素
D．结点*p前插入结点*s
4．栈队列（　　　）
A．限制存取位置线性结构 B．序存储线性结构
C．链式存储线性结构 D．限制存取位置非线性结构
5．数组s[0n1]两栈s1s2存储空间仅s[0n1]全满时栈进行进栈操作两栈分配空间佳方案：s1s2栈顶指针初值分（　　　）
A．1n+1 B．1n2
C．－1n D．－1n+1
6．执行列程序段串X值（　　　）
S〞abcdefgh〞 T〞xyzw〞
substr (XS2strlen(T))
substr (YS stelen(T)2)
strcat (XY)
A．〞cdefgh〞 B．〞cdxyzw〞
C．〞cdefxy〞 D．〞cdefef〞
7．维数组行优先序列优先序两种存储方式（　　　）
A．数组元素处行列两关系中 B．数组元素必须左右序排列
C．数组元素间存次序关系 D．数组维结构存维结构
8．广义表LS＝（(p q) r s）中分解出原子q运算（　　　）
A．tail (head (LS)) B．head (tail (head (LS)))
C．head (tail (LS)) D．tail (tail (head (LS)))
9．具n叶子结点严格二叉树中结点总数（　　　）
A．2n+1 B．2n
C．2n1 D．2n2
10．图条边称（　　　）
A．vi邻接vj B．vj邻接vi
C．vivj相互邻接 D．vivj相邻接
11．带权连通图G中权值边定包含G（　　　）
A．生成树中 B．深度优先生成树中
C．广度优先生成树中 D．深度优先生成森林中
12．二叉排序树中插入新结点时树中存插入结点关键字相结点新结点关键字根结点关键字新结点成（　　　）
A．左子树叶子结点 B．左子树分支结点
C．右子树叶子结点 D．右子树分支结点
13．希尔排序增量序列必须（　　　）
A．递增 B．机
C．递减 D．非递减
14．果排序程中次均排序记录关键字加入前面已序子表中适位置该排序方法称（　　　）
A．插入排序 B．排序
C．泡排序 D．堆排序
15．设置溢出区文件（　　　）
A．索引非序文件 B．ISAM文件
C．VSAM文件 D．序文件
二填空题（题10题题2分20分）
请题空格中填正确答案错填填均分
16．列程序段时间复杂度________________
　　product 1
　　for (i ni>0 i)
　　　for (j i+1 j　　　　product *j
17．已知指针p指单链表中某结点语句p > next p > next > next作________________
18．假设元素abcd序次进栈出栈序列中第元素c出栈序列________________出栈序列________________
19．链串结点中指针占4字节字符占1字节结点2链串存储密度________________



20．右图表示广义表________________
21．棵满三叉树中含121结点该
树深度________________
22．邻接矩阵表示图邻接矩阵
　第i行中非零元素数顶点vi________________
23．希进行8趟排序便4800元素中找出中值8元素求排序程中进行关键字较次数少应该选________________排序方法
24．含20关键字3阶B树（2－3树）查找关键字需访问___________次外存
25．文件两类操作________________________________
三解答题（题4题题5分20分）
26．设栈S1入栈序列1 2 3 4（数字13元素）出栈序列3142通增设栈S2实现例图中箭头指示次栈S1S2便序列3 1 4 2

果H1H2分表示栈S1S2进栈操作P1P2分表示两栈出栈操作3 1 4 2操作步骤
　　H1H1H1P1H2P2P1H2P1H2P2H1P1H2P2P2
　　　请仿例写出利两栈1 2 3 44 1 3 2操作步骤
27．已知树右图示
　（1）写出该树序序列
（2）画出该树转换二叉树


28．关键字（1733314048）构造长度7散列表设散列函数h(key)key7开放定址法解决突探查序列
　hi (h(key) + i(key5+1))7 0≤i≤6
（1）画出构造散列表
（2）求出等概率情况查找成功时均查找长度
29．已知R［18］中元素次（1259206312427）写出算法MergeSortDC　R进行顶二路排序程中前5次调函数Merge(R low mid high)时参数 low mid high值
void MergeSortDC (int R[] int low int mid int high )
{
int mid
if (low {
mid (low +high)2
MergeSortDC (R low mid)
MergeSortDC (R mid+1 high)
Merge (R low mid high)
}
} MergeSortDC
　（1）第次调时参数值
　（2）第二次调时参数值
（3）第三次调时参数值
（4）第四次调时参数值
（5）第五次调时参数值
四算法阅读题（题4题题5分20分）
30．列函数功带头结点单链表作存储结构两递增序表（表中存值相数元素）进行操作：Lb表中存La表中存结点插入La中中LaLb分两链表头指针请空缺处填入合适容成完整算法
　
void union (LinkList La LinkList Lb)
{
算法功Lb表中存La表中存结点插入La表中
LinkList pre La q
LinkList pa La > next
LinkList pb Lb > next
free (Lb)
while (pa && pd)
{
if (pa > data data)
{ pre pa pa pa > next}
else if (pa > data > pb >data)
{
(1)
pre pb
pb pb > next
(2)
}
else
{
q pb pb pb > next free (q)
}
}
if (pb)
(3)
}

31．已知串存储结构动态存储分配序串阅读列算法回答问题：
（1）写出执行函数调 strc (s r)返回结果中s〃aba〃 r〃abababa〃
（2）简述函数strc功
int strc (HString * sub HString * str)
{
int i0 j k count 0
while (i < str > length – sub > length +1)
{
ji k0
while (k <sub>length && str > ch[j] sub > ch[k] )
{
j++ k++
}
if (k sub > length)
{count ++ ijsub > length +1}
else i++
}
return count
}
32．列函数MDFSForest功采邻接矩阵作存储结构图进行深度优先搜索遍历输出深度优先生成森林中条边请空缺处填入合适容成完整算法

　#define MaxMun 20 图顶点数
　typedef struct {
char vexs [MaxNum] 字符类型顶点表
int edges [MaxNum][MaxNum] 邻接矩阵
int n e 图顶点数边数
　}MGraph 图邻接矩阵结构描述
　typedef enum {FALSE TRUE} Boolean
　Boolean visited [MaxNum]

void MDFSTree (MGraph *G int i)
void MDFSForest (MGraph *G)
{
int i k
for (i0 i n i++)
visited [i] (1)
for (k 0 k n k++)
　if (visited [k]) MDFSTree (Gk)
　}
　void MDFSTree (MGraph *G int i)
{
int j
visited [i]TRUE
for (j0 j n j++)
{
if ( (2) )
{
printf (〃〃G > vexs [i] G > vexs [j])
(3)
}
}
　｝

　
33．已知整形数组L［18］中元素次（98576321）阅读列函数写出执行函数调　sort(L 8)时L进行头两趟（pass分01）处理结果
　Void sort (int R[]int n)
{
　 int pass 0 k exchange x
　 do {
　 kpass2+1
　 exchange 0
　 while (k　 {
　 　if (R[k]>R[k+1])
　 　{
　 x R[k] R[k] R[k+1] R[k+1] x
　 exchange 1
}
K+2
}
　pass ++
}while (exchange 1|| pass <1)
}
第趟（pass 0）
第二趟（pass 1）
五算法设计题（题10分）
34．已知二叉排序树中结点关键字整数设计递算法递增序性输出树中等定值x结点函数参数返回输出结点数假设二叉链表存储结构结点结构：
　　
lchild
key
rchild
单项选择题
1B 2C 3B 4A 5C6D 7D 8B 9C 10B11A 12B 13C 14A 15B
二填空题
16．O(n2) 17 删p指示结点面结点
18 ：c b a dc d b ac b d a：c a b dc d a bc a d b
19 333 20 递表21 5 22 出度23 堆排序 24425检索更新
三解答题：
26 H1 H1 H1 H1 P1 H2 P2
P1 H2 P1 H2 P1 H2 P2
P2 H1 P2
P1 H2 P2
27EBJKFGHICDA 见图
28（1+1+3+2+4）521
31


17
48
33
40
注：找17需1次较找33需1次较找31需3次较找40需2次较找48需4次较
29(1) R148 (2) R124 (3) R568
(4) R112 (5) R334
四算法阅读题：
30pre>nextpb pre>nextpa pre>nextpb
30函数返回结果：3 返回sub子串字符串str中出现次数
32 false
G>edges[i][j]0 && visited[j]
MDFSTree(Gj)
33奇偶排序算法
第趟：8 9 5 7 3 6 1 2第二趟：8 5 9 3 7 1 6 2
五算法题目：
假设BinNode图示结点类型BinTree指树根指针类型
int tongji(Bintree T DataType x)
{ int count1count2count
if (T)
{
count1tongji(T>lchildx)
if(T>data>x) { printf(T>data) count1}
count2tongji(T>rchildx)
} return count+count1+count2
else return 0
}
写成面形式：首先定义全局变量count赋初值0
int count0
void tongji(Bintree T DataType x)
{ if (T)
{
tongji(T>lchildx)
if(T>data>x) { printf(T>data) count++}
tongji(T>rchildx)
}
}
20041B
1．列数组织形式中（　　　）结点意邻接
A．集合 B．树形结构
C．线性结构 D．图状结构
2．设某二维数组A［1n1n］该数组中序查找法查找元素时间复杂性量级（　　　）
A．O（log2n） B．O(n)
C．O(nlog2n) D．O(n2)
3．线性表列存储结构中读取元素花费时间少（　　　）
A．单链表 B．双链表
C．循环链表 D．序表
4．头指针p单链表中元素原单链表相反次序存放列算法段中空白处应
qNULL
while (pNULL)
{
（　　　）
}
pq
A．rq qp pp > next q > nextr
B．qp rq pp > next q > nextr
C．rq pp > next qp q > nextr
D．qp pp > next rq q > nextr
5．数组通常具两种基运算（　　　）
A．创建删 B．索引修改
C．读写 D．排序查找
6．根结点外树结点（　　　）
A．意孩子意双亲
B．意孩子双亲
C．孩子意双亲
D．孩子双亲
7．具100结点二叉树中二叉链表存储指针域部分指结点左右孩子余（　　　）指针域空
A．50 B．99
C．100 D．101
8．邻接表图种（　　　）
A．序存储结构 B．链式存储结构
C．索引存储结构 D．散列存储结构
9．果图G必须进行二次广度优先搜索访问顶点列说法中正确（　　　）
A．G肯定完全图 B．G定连通图
C．G中定回路 D．G2连通分量
10．构造棵具n结点二叉排序树坏情况深度会超（　　　）
A．n2 B．n
C．(n+1)2 D．n+1
11．二分查找法取中间位置元素键值查找值说明查找值位中间值前面次查找区间原开始位置（　　　）
A．该中间位置 B．该中间位置－1
C．该中间位置＋1 D．该中间位置／2
12．散列文件（　　　）
A．机存取 B．索引存取
C．关键字存取 D．直接存取
13．检索序文件记录概率相设文件占页块数n关键字存取时均访问外存次数（　　　）
A．n2 B．n
C．n4 D．log n
14．列关键码序列中属堆（　　　）
A．（153022935271） B．（157130229352）
C．（155222933071） D．（933052221571）
15．已知10数元素（54281634736295602643）该数列排序趟泡排序序列（　　　）
A．16283454736260264395
B．28163454627360264395
C．28163454626073264395
D．16283454626073264395
二填空题（题13题题2分26分）
请题空格中填正确答案错填填均分
16．列程序段时间复杂性量级_____________
for (i1i for (j1 j tt+1
17．序存储线性表（a1a2…an）中第i (1≤i≤n)元素前插入元素需移动_____________元素
18．栈序实现中栈满进栈操作列算法片断实现：
_____________
sq > data[sq > top]x
19．链队列实际时带头指针尾指针单链表尾指针指该单链表_____________
20．设k结点哈夫曼算法构造哈夫曼树程中第i次合时已找权结点x权次结点yT［x］wt表示结点x权值已知T［x］wtm　T［y］wtn合成新二叉树新根结点权值赋值语句_____________
21．列树中结点H祖先_____________

22．顶点数n边数n(n1)2图称_____________
23．动态查找表开散列表通常采_____________解决突问题
24．10元素序表采二分查找需较3次方找应键值该元素序表中位置______________
25．查找表逻辑结构线性结构树型结构等相根区______________
26．文件基运算包括______________修改两类
27．排序方法中次记录插入序子序列中第i(i≥1)遍整理时r1r2…ri1已排序子序列取出第i元素ri已排序子序列里ri找合适位置插该位置种排序方法称___________
28．快速排序法排序数_____________情况利发挥长处
三应题（题5题30分）
29．图示输入元素ABC栈输出端输出序列ABC求出栈输入端输入序列（5分）

30．分写出列二叉树先根中根根遍历序列（6分）
　　　　
31．已知图G邻接表请写出顶点V2开始深度优先搜索序列（4分）

32．设闭散列表容量7（散列址空间06）定表（3036475234）散列函数H（k）k mod 6采线性探测法解决突求：（7分）
（1）构造散列表
（2）求查找数34需较次数
33．已知序列（5038751261908170897275653462）请出采快速排序法作升序排序时趟结果（8分）
四设计题（题2题14分）
34．设某头指针head单链表结点结构说明：（6分）
typedef struct node1
{
int data
struct node1*next
}node
试设计算法void change (node*head)该单链表中元素原单链表相反次序重新存放第结点变成结点第二结点变倒数第二结点等等
35．编写算法　void DisplayQueue ()产生50300～600间机整数（调次MyRand()产生符合条件机整数）产生数奇数入队列偶数队首取出数求：（8分）
　（1）队列链表实现
　（2）产生数显示次相应操作队列前状态
　（3）需定义函数int MyRand()
　（4）显示队列调函数　void DisOne (QueptrTp lq)需定义
　（5）设链队列定义：

　typedef struct linked_queue
{int data
struct linked_queue*next
}LqueueTp
typedef struct queueptr
{ LqueueTp *front *rear
}QueptrTp
QueptrTp lq



单项选择题
1D 2D 3D 4A 5C6B 7D 8B 9B 10B11B 12A 13A 14A 15B
二填空题
16．O(n2) 17 ni+1
18 sq>top++
19 结点 20 T[k+i]wtm+n
21 F B A 22 完全图
23 拉链法 241 3 6 9
25强调关键字查找更新 26检索
27直接插入排序 28序
三解答题：
29A in A out B in B out C in C out
C in B in A in A out B out C out
A in A out C in B in B out C out
B in A in A out B out C in C out
C in A in A out B in B out C out
30先序：A B C E D F G H
中序：C E B D G F H A
序：E C G H F D B A
31V2 V5 V3 V1 V4
32
30
36

47
52
34


较2次
四设计题：
34（略）提示：扫描原表原表结点头插法插入新表
200410
1．列式子中增长率序正确排列（）
A n12 n 2n n32 B n32 2n nlogn 2100
C 2n log(n) nlog(n) n32 D 2100 log(n) 2n nn
2．单链表中结点*p插入结点*s应执行语句（）
A s>nextp>next p>nexts B p>nexts s>nextp>next
C p>nexts>next s>nextp D s>nextp p>nexts>next
3．O(1)时间复杂度实现两循环链表头尾相接应两循环链表设置指针分指（）
A 头结点 B 尾结点
C 第元素结点 D 表头结点表尾结点
4．栈两种存储结构分（）
A 序存储结构链式存储结构 B 序存储结构散列存储结构
C 链式存储结构索引存储结构 D 链式存储结构散列存储结构
5．已知循环队列存储控件数组data[21]前队列头指针尾指针值分83该队列前长度（）
A 5 B 6
C 16 D 17
6．已知定义链串结点中字符占字节指针占4字节该结点存储密度()
typedef struct node { char data[8] struct node * next} LinkStrNode
A 14 B 12
C 23 D 34
7．应简单匹配算法串s BDBABDABDAB子串t BDA进行模式匹配匹配成功时进行字符较总次数（）
A 7 B 9
C 10 D 12
8．二维数组A[20][10]采列优先存储方法元素占两存储单元第元素首址200元素A[8][9]存储址（）
A 574 B 576
C 578 D 580
9．广义表L((ab)cd)进行操作tail(head(L))结果（）
A （cd） B (d)
C b D (b)
10．已知颗树前序序列ABCDEF序序列CEDFBA该树进行层次遍历序列（）
A ABCDEF B ABCEFD
C ABFCDE D ABCDFE
11．含n顶点e条弧图邻接矩阵存储结构计算该图中某顶点出度时间复杂度（）
A O(n) B O(e)
C O(n+e) D O(n2)
12．关键字序列（122334455667788991）中二分查找关键字458912结点时需进行较次数分（）
A 443 B 433
C 344 D 334
13．列排序算法中坏时间复杂度相排序方法（）
A 泡排序 B 直接选择排序
C 堆排序 D 排序
14．已知含10结点二叉排序树颗完全二叉树该二叉树等概率情况查找成功均查找长度（）
A 10 B 29
C 34 D 55
15．列种文件中进行序查找文件（）
A 序文件 B 索引文件
C 散列文件 D 重表文件
第二部分 非选择题
二填空题（题2分计20分）
16．抽象数类型指数逻辑结构相关（）
17．已知结点数1单循环链表中指针p指表中某结点列程序段执行结束时指针q指结点*p（）结点
qp while (q>nextp) qq>next
18．假设SX分表示进栈出栈操作输入序列ABC输出序列BCA操作序列SSXSXXa*b+cdab*cd+操作序列（）
19．文编辑程序中查找特定单词文中出现位置利串（）运算
20．假设行优先序n阶5角矩阵矩阵压缩存储维数组Q中数组Q少（）
21．含100结点完全二叉树中叶子结点数（）
22．图中顶点a顶点b存（）称ab间连通
23．果排序程改变（）间相次序称该排序方法稳定
24．索引序查找适宜（）序表进行查找
25．文件检索操作检索条件分列四种询问简单询问范围询问函数询问（）询问
三解答题（题5分计20分）
26．画出图示二叉树中序线索链表存储表示

27．已知图G(VE)中：
V{abcde}
E{(ab)(bd)(cb)(cd)(de)(ea)(ec)}
画出图G然画出图G邻接表
28．已知顶二路排序算法示算法关键字序列(552873913764198246)进行排序列出算法执行程中前5次调Merge函数进行关键字序列
void MergeSortDC(Seqlist R int low int high)
{ int mid
if(lowMergeSortDC(Rlowmid) MergeSortDC(Rmid+1high)
Merge(Rlowmidhigh)
}
}
29．元素插入先次序构成二叉排序树种形态请画出4棵含123456六元素1深度4二叉排序树
四算法阅读题（题5分计20分）
30．L带头结点循环链表函数f30功删L中数域data值c结点结点组建成新带头结点循环链表头指针作函数返回值请空白处填写适容
LinkList f30(LinkList Lint c)
{ LinkList Lcppre
preL
p(①) Lc(LinkList)Malloc(sizeof(ListNode)) Lc>nextLc
while(PL)
if(p>data>c) { pre>nextp>next ( ②) Lc>nextp ppre>next }
else { prep ( ③ ) }
return Lc
}
31．设栈S(1234567)中7栈顶元素
写出调f31(&S)S 简述函数f31中第循环语句功
void f31(Stack *S)
{ Queue Q Stack T int i0
InitQueue(&Q) InitStack(&T)
while( StackEmpty(S))
if((ii)0) Push(&T Pop(S))
else EnQueue(&Q Pop(S))
while( StackEmpty(&T)) Push(S Pop(&T))
while( QueueEmpty(&T)) Push(S DeQueue(&Q))
32．图邻接矩阵表示描述：
#define MaxNum 20
typedef struct {char vexs[MaxNum]
int edges[MaxNum][MaxNum] int ne } Mgraph
阅读列算法回答问题：
(1)列图G邻接矩阵写出函数调f32(&G3)返回值
(2)简述函数f32功
(3)写出函数f32时间复杂度
int f32(Mgraph *G int i)
{ int d0 j
for (j0 jn j++)
{ if(G>edges[i][j]) d++ if (G>edges[j][i]) d++ }
return d }

33．阅读列算法回答问题：
(1)设数组L[18]初值（43712258）写出执行函数调f33(L8)L[18]中元素值
(3)简述函数f33功
void f33(int R[]int n)
{ int xR[1]
int low1 highn
while(low { while (low0) high
if(low{ R[low++]R[high]
while (lowR[high]R[low]
}
} R[low]x
}
五算法设计题（题5分计20分）
34．假设二叉链表作二叉树存储结构结点结构：
lchild
data
Rchild
定函数f34原型编写求二叉树T中叶子结点层次层次函数中参数level函数执行程中T前指结点层次初值1*lmin*lmax分叶子结点层次层次初值均0
void f34(BinTree T int level int *lmin int *lmax)

单项选择题
1D
2A
3B
4A
5D
6C
7C
8B
9D
10D
11A
12B
13D
14B
15C
二填空题
16．操作 17 直接前驱节点
18 SXSSXXSSXSSXXX 19 匹配
20 5×n6 2150 (度1结点n0n2+1)
22 路径 23 相关键字记录
24 分块序 24布尔询问
27．

28．28 37 55 73 91 19 64 82 46
29．

四算法阅读题：
30L>next p>nextLc pp>next
31（栈顶栈底次：2 4 6 7 5 3 1）
32(1) 3
(2)求出顶点I出度入度（求顶点I相邻接边数目邻接顶点I边数目）
(3)O(n)
33－8 －3 －2 －1 4 2 5 7
五算法设计题：
34题采递算法解决基思路：递算法前序遍历二叉树遇叶子结点时果层号层号尚未数值前叶子层号层号层号果层号层号已赋数值应思路处理：果前叶子层号原层号前叶子层号层号果前叶子层号原层号前叶子层号层号细化算法：
Void f34(BinTree T int level int *lmin int *lmax)
{ if (T)
{ if(T>lchildNULL && T>rchildNULL)
if(*lmin0&&*lmax0) { *lminlevel *lmaxlevel }
else { if(level < *lmin) *lminlevel
if(level > *lmax) *lmaxlevel
}
else { f34(T>lchild level++ lmin lmax)
f34(T>rchild level++ lmin lmax)
}
}
200510
1 数结构形式定义二元组(KR)中K数元素限集合RK( )
　　A 操作限集合 　　　B 映象限集合
　　C 类型限集合 　　　D 关系限集合
2 长度n序表中删第i元素(1≤i≤n)时元素移动次数( )
　　A ni+1 　　　　　　　 B I
　　C i+1 　　　　　　　　 D nI
3 带头结点单链表头指针head该链表空判定条件( )
　　A headNULL 　　　　　B head>nextNULL
　　C headNULL　　　　　 D head>nexthead
4 引起循环队列队头位置发生变化操作( )
　　A 出队　　　　　　　　 B 入队
　　C 取队头元素 　　　　　D 取队尾元素
5 进栈序列123456进栈出栈穿插进行出现出栈序列( )
　　A 243156　　 B 324165
　　C 432156 　　D 235164
6 字符串通常采两种存储方式( )
　　A 散列存储索引存储 　B 索引存储链式存储
　　C 序存储链式存储 　D 散列存储序存储
7 设串长n模式串长m(m≤n)匹配失败情况朴素匹配算法进行效位移次数( )
　　A m 　　　　　　　　　　B nm
　　C nm+1　　　　　　　　 D n
8 二维数组A［12］［18］采列优先存储方法元素占3存储单元第1元素址150元素A［9］［7］址( )
　　A 429　　　　　　　　　 B 432
　　C 435 　　　　　　　　　D 438
9 广义表L((ab)(cd)(ef))执行操作tail(tail(L))结果( )
　　A (ef) 　　　　　　　　B ((ef))
　　C (f) 　　　　　　　　　D ( )
10 列图示序存储结构表示二叉树( )

11 n顶点强连通图中少含( )
　A n1条边　　　　　 　B n条边
C n(n1)2条边　　　　D n(n1)条边
12 关键字序列(5623789288671934)进行增量3趟希尔排序结果　( 　)
　　A (1923563478678892) 　B 2356786688921934)
　　C (1923345667788892)　 D (1923675634789288)
13 9阶B树中插入关键字引起结点分裂该结点插入前含关键字数( )
　A 4 　　　　　　　　　　　B 5
　C 8 　　　　　　　　　　　D 9
14 关键字集合构造棵二叉排序树( )
　　A 形态定相均查找长度相
　　B 形态定相均查找长度定相
　　C 形态均相均查找长度定相
　　D 形态均相均查找长度相
15 ISAM文件VSAM文件区( )
　　A 前者索引序文件者索引非序文件
　　B 前者进行序存取者进行机存取
　　C 前者建立静态索引结构者建立动态索引结构
　　D 前者存储介质磁盘者存储介质磁盘
二填空题(题10题空2分20分)
16 数逻辑结构计算机存储器表示称数____________
17 删双循环链表中*p前驱结点(存)应执行语句____________
18 栈溢指____________时进行出栈操作
19 已知substr(silen)函数功返回串s中第i字符开始长度len子串strlen(s)函数功返回串s长度s″ABCDEFGHIJK″t″ABCD″执行运算substr(sstrlen(t) strlen(t))返回值____________
20 广义表LS(a1a2a3……an)中第1元素余元素构成广义表称LS____________
21 已知完全二叉树T第5层7结点该树____________叶子结点
22 图中顶点v终点边数目称v____________
23 关键字取值范围实数集合时法进行箱排序____________排序
24 产生突现象两关键字称该散列函数____________
25 假设散列文件中桶存放m记录桶溢出含义需插入新记录时该桶中____________
三解答题(题4题题5分20分)
26 假设数组seqn［m］存放循环队列元素设变量rearquelen分指示循环队列中队尾元素位置元素数
(1)写出队满条件表达式
(2)写出队空条件表达式
(3)设m40rear13quelen19求队头元素位置
(4)写出般情况队头元素位置表达式
27 已知棵二叉树中序序列ABCDEFG层序序列BAFEGCD请画出该二叉树
28 画出图示图强连通分量

29 7关键字进行快速排序情况仅需进行10次关键字较
(1)假设关键字集合{1234567}试举出达述结果初始关键字序列
(2)举序列进行快速排序写出排序程
四算法阅读题(题4题题5分20分)
30 阅读列算法回答问题：
　(1)设序表L(3711142051)写出执行f30(&L15)L
　(2)设序表L(4710142051)写出执行f30(&L10)L
　(3)简述算法功
　void f30(SeqList*L DataType x)
　{
　　int i 0 j
　　while (ilength && x>L>data［i］)i++
　if(ilength && xL>data［i］)
　　　{
　　for(ji+1jlengthj++)
　　L>data［j1］L>data［j］
　　L>length
}
　　 else
　　　　{for(jL>lengthj>ij)
　　L>data［j］L>data［j1］
　　L>data［i］x
　　L>length++
　}
}
31 已知图邻接表表示形式说明：
　　#define MaxNum 50 图顶点数
　　typedef struct node {
　　int adjvex 邻接点域
　　struct node *next 链指针域
　　} EdgeNode 边表结点结构描述
　　typedef struct {
　　char vertex 顶点域
　　EdgeNode *firstedge 边表头指针
　　} VertexNode 顶点表结点结构描述
　　typedef struct {
　　VertexNode adjlist［MaxNum］ 邻接表
　　int n e 图中前顶点数边数
　　} ALGraph 邻接表结构描述
　列算法输出图G深度优先生成树(森林)边阅读算法空缺处填入合适容成完整算法
　　typedef enum {FALSE TRUE} Boolean
　　Boolean visited［MaxNum］
　　void DFSForest(ALGraph *G){
　　int i
　　for(i0ini++)
　　visited［i］___________________(1)
　　for(i0ini++) if (visited［i］) DFSTree(Gi)
　　}
　　void DFSTree(ALGraph *G int i) {
　　EdgeNode *p
　　visited［i］TRUE
　　pG>adjlist［i］ firstedge
　　while(pNULL){
　　if(visited［p>adjvex］){
　　printf(″″G>adjlist［i］ vertex
　　G>adjlist［p>adjvex］ vertex)
　　_______________(2)
　　}
　　_______________(3)
　　}
　　}
32 阅读列算法回答问题：
　　(1)假设数组L［8］{30516427}写出执行函数调f32(L8)L
　　(2)写出述函数调程中进行元素交换操作总次数
　　void f32(int R［］int n){
　　int it
　　for (i0i　　while (R［i］i){
　　tR［R［i］］
　　R［R［i］］R［i］
　　R［i］t
　　}
　　}
　33 已知带头结点单链表中关键字整数提高查找效率需改建采拉链法处理突散列表设散列表长度m散列函数Hash(key)keym链表结点结构：
请空缺处填入适容成完整算法

　void f33 (LinkList L LinkList H［］ int m)
　　{带头结点单链表L生成散列表H散列表生成原链表存
　　int ij 　LinkList pq
　　for (i0i　　H［i］_____________(1)
　　pL>next
　　while(p)
　　{
　　qp>next
　　jp>keym
　　_________________(2)
　　H［j］p
　　_________________(3)
　　}
　　free(L)
　　}

五算法设计题(题10分)
　34 假设带双亲指针二叉链表作二叉树存储结构结点结构类型说明示
typedef char DataType
typedef struct node {
DataType data
struct node *lchild *rchild 左右孩子指针
struct node *parent 指双亲指针
} BinTNode
typedef BinTNode *BinTree
px指非空二叉树中某结点指针助该结构求px指结点二叉树中序序列中继
(1)继情况简叙述实现求继操作方法
(2)编写算法求px指结点中序序列继算法语句中加注注释
单项选择题
1B
2D
3A
4A
5D
6C
7C
8A
9B
10A
11B
12D
13C
14B
15C
二填空题
16．存储结构
17 qp>prior q>prior>nextp
p>priorq>prior free(q)
18 栈空 19 DEFG
20 求表尾操作 21 11
22 入度 23 基数
24 义词 25已m义词记录
三解答题：
26．（1）Q>quelenm
(2) Q>quelen0
(3) 1319+4032
(4) Q>rearQ>quelen+m) m
27．

28．3：a bce dfg
29．
知道n关键序列进行趟快速排序进行n1次较
基准n1关键字较里情况求做partition时候次正序列分7 1 + 2 * ( 3 1 ) 10满足求2趟快速排序算法结束列举出序列应该：
(1)4 1 3 2 6 5 7 4 1 3 7 6 5 2 4 5 3 7 6 1 2 4 1 3 5 6 2 7 等等
四算法阅读题：
30(1) L(371114152051)
(2) L(47142051)
(3) 序表L中查找数x   果找删x
    果没找适位置插入x保证插入L然序
31(1) FALSE 初始化未访问
(2) DSFTree( G p>adjvex ) 相邻结点继续深度搜索
(3) p p>next 找未访问邻结点
32(1) L { 0 1 2 3 4 5 6 7 } (2)5次
33(1) NULL              初始化
(2) p>next H[ j ] 面句完成头插法
(3) p q           继续遍历L
五算法设计题：
(1)
a)果*px 右孩子右子树左点中序序列中继
b)果*px 右孩子*px开始回溯祖先结点找第1身份左孩子结点
果找该结点父结点*px中序序列中继果找结点*px没直接继
(2) BinTNode * fintNext( BinTNode * px )
{
BinTNode *q *qp
  if( px> rchild ) *px 右孩子
{ qpx>rchild
while(q>lchild) qq>lchild 寻找右孩子左点
return q 返回找结点
  } else
  { q px qpq>parent
while( qp ) 未回溯根结点
{
if( qp>lchild q ) return qp 果qqp左孩子找面述结点
else { q qp qpq>parent } 否继续回溯
}
  return NULL 未找
}
}
200510B
1描述数处理变化程正确次序应(      )
A处理求基运算运算算法
B处理求算法基运算运算
C基运算运算处理求算法
D算法处理求基运算运算
2运算类型角度考虑属引型运算(      )
A插入删       B删修改
C查找读取       D查找删
3长度n序表中插入结点结点移动次数(      )
A少0n     B少1n
C少0n+1    D少1n+1
4单链表中p指结点q指结点前驱结点结点pq间插入结点s正确操作(      )
As>nextqp>nexts>next
Bp>nextqp>nexts
Cs>nextp>nextp>nexts
Ds>nextq>nextp>nexts>next
5串数字5678入栈输出序列(      )
A5678       B8765
C8756       D5687
6FORTRAN语言数组元素存放方式通常采(      )
A行存储结构     B列存储结构
C行列存储结构    D行列存储结构
7树n结点穷集合(      )
A树结点数0时称该树空树
B树少含根结点空
C树少含根结点叶子结点
D树少含根结点两叶子结点
8深度k二叉树(      )
A2k叶子       B2k1叶子
C2k1叶子       D2k11叶子
9具10顶点完全图应具(      )
A20条弧       B50条弧
C90条弧       D100条弧
10V1出发题10图广度优先搜索遍历种顶点序列(      )
AV1V2V3V5V4V6 BV1V2V3V5V6V4
CV1V5V2V3V6V4 DV1V3V6V4V5V2

11适静态查找方法( )
A二分查找二叉排序树查找 B二分查找索引序表查找
C二叉排序树查找索引序表查找 D二叉排序树查找散列法查找
12采二分查找法前取中间位置MID元素值查找值表明查元素表半部分次查找起始位置通常应( )
AMID2位置开始 BMID位置开始
CMID1位置开始 DMID+1位置开始
13磁盘种广泛外部存储设备磁盘存取操作( )
A序方式 B机方式
C序方式机方式 D方式取决具体机器
14排序序列中记录数较少基序时适合排序方法( )
A直接插入排序法 B快速排序法
C堆排序法 D排序法
15序列（269023531634693922）进行趟排序结果（221623265334693990）该排序方法( )
A插入排序 B泡排序
C快速排序 D选择排序
二填空题(题13题题2分26分)
请题空格中填正确答案错填填均分
16算法通常分程序伪语言算法__________三种类型
17时间复杂性描述量级中某算法达__________量级该算法通常计算
18序表执行删操作删算法均时间复杂性__________
19head表示循环链表头指针t表示尾结点头指针head尾结点t间关系表示__________
20通常队列中允许删端称__________
21二维数组A［5］［6］采列序存储方式元素占3存储单元A［0］［0］存储址100A［4］［3］存储址__________
22树数结构中常采孩子链表表示法__________三种存储结构表示
23某二叉树中度1结点数4度2结点数6该树叶子结点数__________
24n顶点生成树边数__________
25具n元素数序列采二分查找法n值较时均查找长度__________
26解决散列引起突方案中__________法介开散列表闭散列表间种方法
27关键字文件指时__________两部分建立索引文件组织形式
28排序通常分部排序外部排序中部排序指排序整程中数全部存放计算机__________中
三应题(题5题题6分30分)
29图示二叉树分写出先根遍历中根遍历根遍历结点访问序列
30设散列函数H(Key)Key 11散列表长度11（散列址空间0…10）定表（SUNMONTUEWEDTHUFRISAT）中取单词第字母英语字母表中序号键值K构造散列表线性探测法解决关址突请画出散列表

31请出图邻接矩阵邻接表表示


32已知组键值序列（3244386553422957）试采堆排序法该组序列作升序排序出建立初始堆第次输出堆元素筛选调整堆
  33已知组键值序列（13121617151411）试采二路排序法该组序列作升序排序出趟排序结果
四设计题(题2题题7分14分)
 34循环单链表长度1p指链表中某结点指针试编写算法删p结点前驱结点
 35二叉树二叉链表表示试编写算法计算棵二叉树叶子总数（采递算法描述）
单项选择题
1B
2C
3A
4C
5C
6B
7A
8C
9C
10B
11A
12D
13C
14A
15C
二填空题
16．非形式算法语言 17 指数
18 O(n) 19 t>nexthead
20队首（队头）结点 21157
22 双亲表示法 孩子兄弟链表法
23 7 24 n1
25 Log2n 26公溢出区法
27 关键字次关键字 28存
三应题：
29．先根遍历：ABDEFC
中根遍历：BFEDAC
根遍历：FEDBCA
30．
0 1 2 3 4 5 6 7 8 9 10
SAT
WED
MON



FRI

SUN
TUE
THU
31．邻接矩阵邻接表：
32．（考试中建议画成完全二叉树形式）
初始建堆序： 65 57 42 44 53 38 29 32
进行次输出调整：57 53 42 44 32 38 29 65
33排序：
13 12 16 17 15 14 11
12 13 16 17 14 15 11
12 13 16 17 11 14 15
11 12 13 14 15 16 17

四算法设计题：
34题基思路：先找结点p直接前驱直接前驱结点标记qp直接前驱结点标记s然通修改指针s链表中删释放结点s
void f34(LinkList L ListNode *p)
{ListNode *q *s
qp
while(q>next>next p) qq>next 查找结点p前驱前驱
sq>next p直接前驱标记s
q>nexts>next
free(s) 释放结点s占空间
}
35题基思路：首先定义公变量count赋予初值0然递遍历二叉树次遇度0结点（叶子结点）时计数器Count值加1算法：
int count0
void f35(BinTree T)
{ if (T)
{ if(T>lchildNULL && T>rchildNULL) count++
else { f35(T>lchild) f35(T>rchild) }
}
}
QG20031
1面程序段时间复杂度( )
for(i0i for(j1j A[i][j]0
AO(n) BO(m+n+1) CO(m+n) DO(m*n)
2单链表中指针p指元素x结点实现删x继语句( )
App>next Bp>nextp>next>next
Cp>nextp Dpp>next>next
3头指针head表长1单循环链表中指针p指表中某结点p>next>next

head( )
Ap指头结点 Bp指尾结点
C*p直接继头结点 D*P直接继尾结点
4判定带头结点链队列空条件( )
AQfrontNULL BQrearNULL
CQfrontQrear DQfrontQrear
5设两串TP求PT中首次出现位置串运算称作( )
A联接 B求子串 C字符定位 D子串定位
6广义表A(a(b)()(cde))长度( )
A4 B5 C6 D7
7棵含18结点二叉树高度少( )
A3 B4 C5 D6
8已知二叉树先序序列ABDECF中序序列DBEAFC序序列( )
ADEBAFC BDEFBCA CDEBCFA DDEBFCA
9图中顶点度指图中( )
A通该顶点简单路径数 B该顶点相邻接顶点数
C通该顶点回路数 D该顶点连通顶点数
10已知图示顶点a出发进行广度优先遍历序列( )
Aa c e f b d
Ba c b d f e
Ca c b d e f
Da c d b f e





11列排序方法中均时间性O(nlogn)空间性( )
A快速排序 B堆排序 C排序 D基数排序
12已知组关键字{25483672798223401635}中相邻两序子序列子序列进行趟两两结果( )
A{25364872234079821635}
B{25364872162340798235}
C{25364872162335407982}
D{16232535364048727982}
13设序存储线性表123元素分块查找求等分成3块索引表采序查找确定块确定块中进行序查找查找概率相等情况分块查找成功时均查找长度( )
A21 B23 C41 D62
14索引非序文件特点( )
A文件序索引表序 B文件序索引表序
C文件序索引表序 D文件序索引表序
15倒排文件优点( )
A便进行插入删运算 B便进行文件恢复
C便进行关键字查询 D节省存储空间
二填空题(题10题题2分两空格空格1分20分)
16抽象数类型特点________________________封装起现实信息隐藏
17序表中删元素时表中删元素元素均需____________位置
18队列中允许进行插入操作端称____________允许进行删操作端称____________
19图两栈享量空间top1top分指两栈顶元素指针栈满判定条件____________

20设S1goodS2 S3bookS1S2S3次联接结果____________
21假设三维数组A[10][9][8]行优先序存储元素占3存储单元首址100元素A[9][8][7]存储址____________
22已知棵含n结点树中度k分支结点度0叶子结点该树中含叶子结点数目____________
23够成功完全拓扑排序图定____________
24果排序前关键字序列已接正序逆序堆排序快速排序两者中选____________较适
25假设哈希表表长m哈希函数H(key)线性探查法解决突探查址序列形式表达____________
三解答题(题4题题5分20分)
26假设通信电文字符集{abcdef}名字符电文中出现频度分：3451223818试6字符设计哈夫曼编码请先画出构造哈夫曼树(求树中左孩子结点权值右孩子结点权值)然分写出字符应编码
27已知图示顶点abcdef序存放邻接表顶点表中请画出该图邻接表邻接表进行深度优先遍历时顶点序列acbefd进行广度优先遍历时顶点序列acbdfe

28已知两4×5稀疏矩阵三元组表分：
0
1
4
16

0
1
1
32
1
2
2
18

1
2
2
－22
2
3
4
－25

2
2
5
69
3
4
2
28

3
3
4
25





4
4
2
51

请画出两稀疏矩阵三元组表
29空树起次插入关键字4089015629512235632构造棵二叉排序树
(1)画出该二叉排序树
(2)画出删该树中元素值90结点二叉排序树
四算法阅读题(题4题题5分20分)
30图示利循环量空间实现两队列类型Queue2定义：
typedef struct {
DataType data[MaxSize]
int front[2]length[2]
} Queue2



i01front[i]length[i]分第i队列头指针长度域请空缺处填入合适容实现第i循环队列入队操作
int EnQueue(Queue2*Qint iDataType x)
{第i队列满元素x入队列返回1否返回0
if(i<0||i>1)return 0
if( (1) )
return 0
Q>data[ (2) ]x
Q>length[ (3) ]++
return 1
}
(1)
(2)
(3)
31某二叉树线索链表存储结构图(b)示中p指根结点指针图(a)结点结构阅读列算法回答问题：
(1)写出执行函数调f(p)输出结果
(2)简述函数f功
void f(BinThrTree t)
{
while(t)
{
printf(t>data)
if(t>lchild)
tt>lchild
else
tt>rchild
}
}
(1)
(2)
32列函数FindCycle(Gi)功采邻接表作存储结构图G利深度优先搜索策略寻找条顶点vi简单回路数组cycle_path保存搜索程中形成回路cycle_path[k]j(j≥0)表示回路中顶点vk顶点vj请空缺处填入合适容成完整算法
vertex
firstedge
已知邻接表顶点表结点结构：　　　　　　　　　　　　　　　　

adjvex
next
边表结点EdgeNode结构：　　　　　　　　　　　　　　
　　　　　　　　
int cycle_path[MaxNum]
int FindCycle(ALGraph*Gint i)
{回路存返回1否返回0
int j
for(j0jnj++)cycle_path[j]1
return DFSPath(Gii)
}
int DFSPath(ALGraph*Gint jint i)
{
EdgeNode *p
int cycled0
for(pG>adjlist[j]firstedgep&&cycledpp>next)
{
cycle_path[j]p>adjvex
if( (1 ) )cycled1已找回路
else
if(cycle_path[p>adjvex]1)cycled (2)
}
return (3)
}
(1)
(2)
(3)
33阅读列函数algo回答问题
(1)假设整型数组A[18]中元素次(38917426)执行函数调algo(A8)时外层while循环体执行少次函数返回值少
(2)简述函数algo(Ln)功
int algo(int L[]intn)
{
int i0js1tn
while (i(n+1)2)
{
int xL[s]
isjt
while(i {
while(ix)j
L[i]L[j]
while(i L[j]L[i]
}
L[i]x
if(i<(n+1)2)si+1
else ti1
}
if(i0)return 0
else return L[i]
}
五算法设计题(题10分)
34假设带头结点单循环链表作非递减序线性表存储结构请设计时间复杂度O(n)算法删表中数值相余元素释放结点空间例：
(7101021304242425170)
算法操作变
(7102130425170)
．单项选择题
1D 2B 3D 4A 5D
6A 7C 8D 9B 10C
11B 12A 13B 14A 15C
二填空题
16 数类型数运算　17 前移动
18 队尾队首 19top1top21
20 good book 21(9×(9×8)+8×8+7)×3+1002257
22(n1)k(k1)+1 　23环图
24堆排序　　　　 25（H（key）+i）m
三简答题
26
编码：
a 0 f 10 c 110 b 1110 e 1111
27

0
A


2


1


3
1
B


5






2
C


5


4



3
D


2






4
E


5






5
F


3

















28
1
1
32
1
4
16
2
2
－4
2
5
69
3
4
0
4
2
79

29


四算法阅读题
30 (1) Q>length[0]+Q>length[1] Maxsize
(2) Q>front[i]+ Q>length[i]+1
(3) i
31(1) 利前序线索化继指针实现线索二叉树前序遍历
(2) 题目输出：A B D F C E G H
32(1)p>adjvex i
(2)DFSpath(Gp>adjvexi)
(3)cycled
33(1) 函数返回值：4序列：2 1 3 4 6 7 8 9 外层循环执行5次
(2)函数功序序列划分首关键字界两序列左边序列关键字3右边序列关键字3
五算法设计题
34思路：遍历链表时记录前两结点果结点值前结点值相删结点
20061
1．根数元素关键字直接计算出该元素存储址存储方法（　　　）
A．序存储方法  B．链式存储方法
C．索引存储方法  D．散列存储方法
2．述程序段中语句①频度（　　　）
s0
for(i1ifor(j0j①     s+j
A． (m+1)(m1)2   B． m(m1)2
C． (m+2)(m1)2   D． m(m+1)2
3．求单链表中前结点继前驱时间复杂度分（　　　）
A．O（n）O（1）  B．O（1）O（1）
C．O（1）O（n）  D．O(n)O（n）
4．非空单循环链表头指针head尾指针rear列条件成立（　　　）
A．rear>next head  B．rear>next>next head
C．head>next rear  D．head>next>next rear
5．允许表达式种括号混合嵌套检查表达式中括号否正确配算法通常选辅助结构（　　　）
A．栈  B．线性表
C．队列  D．二叉排序树
6．已知串s″ADBADABBAAB″模式串t″ADAB″应朴素串匹配算法进行模式匹配程中效位移次数（　　　）
A．2  B．3
C．4  D．5
7．串s″Data Structure″中长度3子串数目（　　　）
A．9          B．11
C．12          D．14
8．假设行优先序存储三维数组R[6][9][6]中元素R[0][0][0]址2100元素占4存储单元存储址2836元素（　　　）
A．R[3][3][3]         B．R[3][3][4]
C．R[4][3][5]         D．R[4][3][4]
9．第层外满二叉树中层结点数层结点数（　　　）
A．12倍         B．1倍
C．2倍          D．3倍
10．含n顶点e条边图采邻接矩阵表示空间复杂度（　　　）
A．O（n）         B．O(e)
C．O(n+e)         D．O(n2)
11．果求连通图中某顶点根高度生成树应采（　　　）
A．深度优先搜索算法       B．广度优先搜索算法
C．求生成树prim算法     D．拓扑排序算法
12．快速排序坏情况时间复杂度（　　　）
A．O(n2log2n)        B．O(n2)
C．O(nlog2n)         D．O(log2n)
13．进行二分查找线性表必须（　　　）
A．序方式存储元素关键字序
B．链式方式存储元素关键字序
C．序方式存储元素关键字分块序
D．链式方式存储元素关键字分块序
14．均查找长度达关键字集合{051121253740416284}构建二叉排序树时第插入关键字应（　　　）
A．05          B．37 C．41          D．62
15．ISAM文件周期性整理空出（　　　）
A．磁道索引         B．柱面索引
C．柱面基区        D．柱面溢出区
二填空题（题10题题2分20分）
请题空格中填正确答案错填填均分
16．数类型值否分解通常分_________两种类型
17．队列修改_________原进行
18．两串相等充分必条件两串长度相等_________
19．数组采序存储方式表示通常数组进行_________操作
20．广义表取表头head取表尾tail运算广义表LS(bc(f)((d)))中分解出原子c操作_________
21．结点数20二叉树达期高度_________
22．带权连通图生成树权该生成树_________
23．谓排序指排序算法辅助空间复杂度_________排序方法
24．5阶B树根结点少含_________关键字
25．索引文件中索引表指示记录关键字_________间应关系
三解答题（题4题题5分20分）
26．假设序表示双亲结点孩子结点条边已知树中边集合{}请回答列问题：
（1）结点根结点？
（2）结点叶子结点？
（3）结点k祖先？
（4）结点j兄弟？
（5）树深度少？
27．已知图G深度优先生成森林广度优先生成森林请写出该图深度优先遍历序列广度优先遍历序列

28．两长度均n序表A（a1a2…an）B（b1b2…bn）(ai≠bj
1≤ij≤n)序表C（c1 c2…c2n）时需进行元素较次数少达n达2n1
（1）假设序表C（245679）试举出两组AB例子程中进行元素较次数分达少
（2）写出般情况需进行元素较次数分达少时AB中元素应满足条件
29．列关键字序列（33254859367246076520）构造表长19散列表假设散列函数h(key)key13开放址法解决突探查序列dh(key)d+12d12d+2 2d2 2d+32d32…等等
（1）画出该散列表
（2）计算该散列表装填子α
（3）求出等概率情况查找成功均查找长度ASL
四算法阅读题（题4题题5分20分）
30．已知head带头结点单循环链表头指针链表中数元素次（a1a2a3a4…an）A指空序表指针阅读程序段回答问题：
（1）写出执行列程序段序表A中数元素
（2）简叙述该程序段功
if(head>nexthead)
{ phead>next
A>length0
while(p>nexthead)
{
pp>next
A>data[A>length ++]p>data
if(p>nexthead)pp>next
}
}
31．已知链串存储结构描述：
#define NodeSize  4
typedef struct Node {
char data [NodeSize]
struct  Node * next
} * LinkStr
阅读列算法回答问题：
（1）t1t2串值分″Chinese″″China″时写出f31(t1t2)返回值
（2）t1t2串值分″Japan″″Japanese″时写出f31(t1t2)返回值
（3）t1t2串值″string″时写出f31(t1t2)返回值
（4）简述函数f31功
inf f31(LinkStr t1LinkStr t2)
{串值′′结束符
int i
while (1){
for (i0iif (t1>data[i] ′′&&t2>data[i] ′′return 0
if(t1>data[i] ′′))return –1
if(t2>data[i] ′′)}return 1
if(t1>data[i]>t2>data[i]return 1
if(t1>data[i]data[i]return –1
}
t1t1>next
t2t2>next
}
}
32．设二叉树采二叉链表存储结构结点数域data字符类型阅读列算法回答问题：
（1）图示二叉树写出执行函数f32输出结果
（2）简述函数f32功











void  f32(BinTree T)
{  Stack s   定义栈s
BinTree pq
if (T NULL) return
InitStack(&s)
pT
do  {
while (p){ Push(&sp)
if (p>lchild)pp>lchildelse pp>rchild}
while (Stack Empty(s)&&qStackTop(s)&&q>rchild p){
pPop(&s)
printf(″c″p>data)
}
if(StackEmpty(s)){ qStackTop(s)pq>rchild }
} while ( Stack Empty(S))
}
33．已知图邻接表表示形式说明：
#define Max Num         50         图顶点数
typedef struct node {
int adjvex                               邻接点域
struct node * next                         链指针域
}EdgeNode    边表结点结构描述
typedef struct {
char vertex                            顶点域
EdgeNode  *firstedge                    边表头指针
}VertexNode 顶点表结点结构描述
typedef struct{
Vertex Node adjlist [MaxNum]    邻接表
int ne                        图中前顶点数边数
}ALGraph  邻接表结构描述
  列函数f33图G中删vi弧头边请空缺处填入合适容成完整算法
void f33 (ALGraph * G int i)
{  int j
EdgeNode * p *q
for  (j0jnj + +){
pG>adjlist [j]firstedge
while(          (1)             { qp      pp>next }
if(pNULL) {
  if (p G>adjlist[j]firstedge) q>nextp>next
else(          (2)           
free(p)
G>e(          (3)           
}
}
}
五算法设计题（题10分）
34．带头结点循环链表L中结点数元素整型值递增序存放定两整数aba单项选择题
1D
2C
3C
4A
5A
6B
7C
8B
9C
10D
11B
12B
13A
14B
15D
二填空题
16．简单类型复杂类型 17 先进先出
18 应字符相等 19 增加减少数组元素数
20 head(tail(LS)) 2120
22 路径长度 23 O(1)
24 1 25记录
三解答题：
26．（1）a
(2) b d h i j f k
(3) c a
(4) i (5) 4
27．a c f e b d g a c e f b d g
28．(1) 较次数少： A{2 4 5} B{6 7 9}
较次数：A{2 5 7} B{ 4 6 9}
(2) 较次数少时应该满足：an 数两序序列中均匀分布合时需交式两序列中取数
29．（略）
四算法阅读题：
30
a2
a4
a6
a8
a10
…



链表中位置偶数结点数存储序表中
311 －1 0
较两字符串
32D B F G E C A 序遍历二叉树
33程序功删结点vi入边填空：
p && p>data i
G>adjlist[j]firstedgep>next
G>e
五算法设计题：
34题解决方法两种：（1）扫描整单循环链表果发现结点值ab间删该结点满足条件结点逐删(2)扫描链表标记出满足条件段子链表然段子链表删两种方法时间复杂度相方法2中需逐释放删结点里方法（1）具体算法：
void f34(LinkList L int a int b)
{ListNode *p *q

pL
while(p>next L) 扫描整链表
{ qp>next q指p直接继
if(q>data>a && q>data { p>next q>next 修改指针删结点q
free(q) 释放q值
}
pp>next 检查结点
}
}

文档香网(httpswwwxiangdangnet)户传

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