数结构试卷（） 1
数结构试卷（二） 4
数结构试卷（三） 6
数结构试卷（四） 8
数结构试卷（五） 11
数结构试卷（六） 14
数结构试卷（七） 16
数结构试卷（八） 18
数结构试卷（九） 20
数结构试卷（十） 23
数结构试卷（）参考答案 26
数结构试卷（二）参考答案 27
数结构试卷（三）参考答案 28
数结构试卷（四）参考答案 30
数结构试卷（五）参考答案 32
数结构试卷（六）参考答案 33
数结构试卷（七）参考答案 36
数结构试卷（八）参考答案 37
数结构试卷（九）参考答案 38
数结构试卷（十）参考答案 39
数结构试卷（）
单选题（题 2 分20分）
1 栈队列特点( )
A允许端点处插入删元素
B先进出
C先进先出
D没点
2 链接方式存储队列进行插入运算时( )
A 仅修改头指针 B 头尾指针修改
C 仅修改尾指针 D头尾指针修改
3 数结构中非线性结构？( )
A 队列 B 栈 C 线性表 D 二叉树
4 设二维数组A[m][n]假设A[0][0]存放位置644(10)A[2][2]存放位置676(10)元素占空间问A[3][3](10)存放什位置？脚注(10)表示10进制表示
A．688 B．678 C．692 D．696
5 树适合表示( )
A序数元素 B序数元素
C元素间具分支层次关系数 D元素间联系数
6 二叉树第k层结点数( )
A．2k1 B2K+1 C2K1 D 2k1
7 18元素序表存放维数组A[19]中第元素放A[1]中现进行二分查找查找A［3］较序列标次( )
A 123 B 9523
C 953 D 9423
8 n记录文件进行快速排序需辅助存储空间致
A O（1） B O（n） C O（1og2n） D O（n2）
9 线性表（734552564462010）进行散列存储时选H（K）K 9作散列函数散列址1元素（ ）
A．1 B．2 C．3 D．4
10 设6结点图该图少应( )条边确保连通图
A5 B6 C7 D8
二填空题（空1分26分）
1 通常四方面评价算法质量：____________________________________
2 算法时间复杂度(n3+n2log2n+14n)n2数量级表示________
3 假定棵树广义表表示A（CD（EFG）H（IJ））树中含结点数_ _________树深度___________树度_________
4 缀算式9 2 3 + 10 2 值__________中缀算式（3+4X）2Y3应缀算式_______________________________
5 链表存储棵二叉树时结点数域外指左孩子右孩子两指针种存储结构中n结点二叉树________指针域中________指针域存放址________________指针空指针
6 具n顶点e条边图图应邻接表中含边结点分_______________
7 AOV网种___________________图
8 具n顶点完全图中包含________条边具n顶点完全图中包含________条边
9 假定线性表(122374556340)Key 4条件进行划分余数元素成子表四子表分________________________________________________________________________________________________
10 棵B_树插入元素程中终引起树根结点分裂新树原树高度___________
11 堆排序程中分支结点进行筛运算时间复杂度________整堆排序程时间复杂度________
12 快速排序堆排序排序中_________排序稳定
三计算题（题 6 分24分）
1 数组A中链接存储线性表表头指针A [0]next试写出该线性表
A 0 1 2 3 4 5 6 7
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
2 请画出图邻接矩阵邻接表
3 已知图顶点集V边集E分：V{1234567}
E{(12)3(13)5(14)8(25)10(23)6(34)15
(35)12(36)9(46)4(47)20(56)18(67)25}
克鲁斯卡尔算法生成树试写出生成树中次条边
4 画出根堆中加入数4 2 5 8 3时加入数堆变化
四阅读算法（题7分14分）
1 LinkList mynote(LinkList L)
{L带头结点单链表头指针
if(L&&L>next){
qLLL－>nextpL
S1： while(p－>next) pp－>next
S2： p－>nextqq－>nextNULL
}
return L
}
请回答列问题：
（1）说明语句S1功
（2）说明语句组S2功
（3）设链表表示线性表（a1a2 …an）写出算法执行返回值表示线性表
2 void ABC(BTNode * BT)
{
if BT {
ABC (BT>left)
ABC (BT>right)
cout<data<<＇ ＇
}
}
该算法功：
五算法填空（8分）
二叉搜索树查找——递算法
bool Find(BTreeNode* BSTElemType& item)
{
if (BSTNULL)
return false 查找失败
else {
if (itemBST>data){
itemBST>data查找成功
return ___________}
else if(itemdata)
return Find(______________item)
else return Find(_______________item)
}if
}
六编写算法（8分）
统计出单链表HL中结点值等定值X结点数
int CountX(LNode* HLElemType x)
数结构试卷（二）
选择题(24分)
1．面关线性表叙述错误（ ）
(A) 线性表采序存储必须占片连续存储空间
(B) 线性表采链式存储必占片连续存储空间
(C) 线性表采链式存储便插入删操作实现
(D) 线性表采序存储便插入删操作实现
2．设哈夫曼树中叶子结点总数m二叉链表作存储结构该哈夫曼树中总（ ）空指针域
(A) 2m1 (B) 2m (C) 2m+1 (D) 4m
3．设序循环队列Q[0：M1]头指针尾指针分FR头指针F总指队头元素前位置尾指针R总指队尾元素前位置该循环队列中元素数（ ）
(A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M
4．设某棵二叉树中序遍历序列ABCD前序遍历序列CABD序遍历该二叉树序列（ ）
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5．设某完全图中n顶点该完全图中（ ）条边
(A) n(n1)2 (B) n(n1) (C) n2 (D) n21
6．设某棵二叉树中2000结点该二叉树高度（ ）
(A) 9 (B) 10 (C) 11 (D) 12
7．设某图中n顶点该图应邻接表中（ ）表头结点
(A) n1 (B) n (C) n+1 (D) 2n1
8．设组初始记录关键字序列(52638)第记录关键字5基准进行趟快速排序结果（ ）
(A) 23586 (B) 32586
(C) 32568 (D) 23658
二填空题(24分)
1 效应HASH查找技术必须解决两问题______________________________________________
2 面程序段功实现数x进栈求划线处填正确语句
typedef struct {int s[100] int top} sqstack
void push(sqstack &stackint x)
{
if (stacktopm1) printf(overflow)
else {_____________________________________}
}
3 中序遍历二叉排序树序列___________序列（填序序）
4 快速排序坏时间复杂度___________均时间复杂度__________
5 设某棵二叉树中度数0结点数N0度数1结点数N1该二叉树中度数2结点数_________采二叉链表作该二叉树存储结构该二叉树中_______空指针域
6 设某图中顶点数边数分ne顶点度数de_______
7 设组初始记录关键字序列(5563443875803156)利筛选法建立初始堆___________________________
8． 已知图邻接表存储结构：顶点1出发DFS遍历输出序列
BFS遍历输出序列
三应题(36分)
1． 设组初始记录关键字序列(458048402278)分出第4趟简单选择排序第4趟直接插入排序结果
2． 设指针变量p指双链表中结点A指针变量q指插入结点B求出结点A面插入结点B操作序列（设双链表中结点两指针域分llinkrlink）
3． 设组序记录关键字序列(131824354750628390)查找方法二分查找求计算出查找关键字62时较次数计算出查找成功时均查找长度
4． 设棵树T中边集合{(AB)(AC)(AD)(BE)(CF)(CG)}求孩子兄弟表示法（二叉链表）表示出该树存储结构该树转化成应二叉树
5． 设图G求出普里姆算法构造生成树走边集合
6． 设组初始记录关键字(458048402278)求构造棵二叉排序树出构造程
四算法设计题(16分)
1． 设组初始记录关键字序列（K1K2…Kn）求设计算法够O(n)时间复杂度线性表划分成两部分中左半部分关键字均Ki右半部分关键字均等Ki
2． 设两集合A集合B求设计生成集合CA∩B算法中集合ABC链式存储结构表示
数结构试卷（三）
选择题(题1分20分)
1．设某数结构二元组形式表示A(DR)D{010203040506070809}R{r}r{<0102><0103><0104><0205><0206><0307><0308><0309>}数结构A（ ）
(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构
2．面程序时间复杂（ ）
for（i1s0 i (A) O(n) (B) O(n2) (C) O(n3) (D) O(n4)
3．设指针变量p指单链表中结点A删单链表中结点A需修改指针操作序列（ ）
(A) qp>nextp>dataq>datap>nextq>nextfree(q)
(B) qp>nextq>datap>datap>nextq>nextfree(q)
(C) qp>nextp>nextq>nextfree(q)
(D) qp>nextp>dataq>datafree(q)
4．设n排序记录关键字堆排序中需（ ）辅助记录单元
(A) 1 (B) n (C) nlog2n (D) n2
5．设组初始关键字记录关键字(2015141821364010)20基准记录趟快速排序结束结果( )
(A) 1015141820364021
(B) 1015141820403621
(C) 101514201840362l
(D) 1510141820364021
6．设二叉排序树中n结点二叉排序树均均查找长度（ ）
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7．设图G中n顶点e条边应邻接表中表头结点表结点数分（ ）
(A) ne (B) en (C) 2ne (D) n2e
8 设某强连通图中n顶点该强连通图中少（ ）条边
(A) n(n1) (B) n+1 (C) n (D) n(n+1)
9．设5000排序记录关键字果需快方法选出中10记录关键字列（ ）方法达目
(A) 快速排序 (B) 堆排序 (C) 排序 (D) 插入排序
10列四种排序中（ ）空间复杂度
(A) 插入排序 (B) 泡排序 (C) 堆排序 (D) 排序
二填空殖(空1分 20分)
1 数物理结构包括___________________________两种情况
2 设棵完全二叉树中500结点该二叉树深度__________二叉链表作该完全二叉树存储结构___________空指针域
3 设输入序列123栈作___________种输出序列
4 设图G邻接矩阵A[n][n]作存储结构该邻接矩阵中第i行元素等顶点i________第i列元素等顶点i________
5 设哈夫曼树中n结点该哈夫曼树中________度数1结点
6 设图G中n顶点e条边顶点入度数ded关系_________
7 __________遍历二叉排序树中结点递增关键字序列（填先序中序序）
8 设查找表中100元素果二分法查找方法查找数元素X需较________次断定数元素X否查找表中
9 序存储结构栈链式存储结构栈入栈出栈操作时间复杂度均____________
10 设n结点完全二叉树果左右1开始序编号第i结点双亲结点编号____________右孩子结点编号___________
11 设组初始记录关键字(7273712394165)记录关键字72基准趟快速排序结果___________________________
12 设图G中边集合E{<12><23><14><42><43>}该图种拓扑序列____________________
13 列算法实现序散列表中查找值x关键字请划线处填正确语句
struct record{int key int others}
int hashsqsearch(struct record hashtable[ ]int k)
{
int ij jik p
while (hashtable[j]keyk&&hashtable[j]flag0){j(____) m if (ij) return(1)}
if (_______________________ ) return(j) else return(1)
}
14 列算法实现二叉排序树查找关键值k请划线处填正确语句
typedef struct node{int key struct node *lchild struct node *rchild}bitree
bitree *bstsearch(bitree *t int k)
{
if (t0 ) return(0)else while (t0)
if (t>keyk)_____________ else if (t>key>k) tt>lchild else_____________
}
三计算题(题10分30分)
1已知二叉树前序遍历序列AEFBGCDHIKJ中序遍历序列EFAGBCHKIJD画出二叉树画出序线索二叉树
2．已知散列线性表（3615406322）散列维址空间[06]假定选散列函数H（K） K mod 7发生突采线性探查法处理试：
（1）计算出元素散列址图中填写出散列表：
` 0 1 2 3 4 5 6
（2）求出查找元素概率相等情况均查找长度
3．已知序列（10184361219188）请快速排序写出趟排序结果
四算法设计题(题15分30分)
1． 设计单链表中删值相余结点算法
2． 设计求结点x二叉树中双亲结点算法
数结构试卷（四）
选择题(题1分 20分)
1．设维数组中n数组元素读取第i数组元素均时间复杂度（ ）
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
2．设棵二叉树深度k该二叉树中（ ）结点
(A) 2k1 (B) 2k (C) 2k1 (D) 2k1
3．设某图中n顶点e条边该图中顶点入度（ ）
(A) n (B) e (C) 2n (D) 2e
4．二叉排序树中插入结点时间复杂度（ ）
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
5．设某图邻接表中n表头结点m表结点该图中（ ）条边
(A) n (B) n1 (C) m (D) m1
6．设组初始记录关键字序列(345253674924627)基数排序需进行（ ）趟分配回收初始关键字序列变成序序列
(A) 3 (B) 4 (C) 5 (D) 8
7．设链表作栈存储结构退栈操作（ ）
(A) 必须判栈否满 (B) 必须判栈否空
(C) 判栈元素类型 (D) 栈作判
8．列四种排序中（ ）空间复杂度
(A) 快速排序 (B) 泡排序 (C) 希尔排序 (D) 堆
9．设某二叉树中度数0结点数N0度数1结点数Nl度数2结点数N2列等式成立（ ）
(A) N0N1+1 (B) N0Nl+N2 (C) N0N2+1 (D) N02N1+l
10设序序表中n数元素利二分查找法查找数元素X较次数超（ ）
(A) log2n+1 (B) log2n1 (C) log2n (D) log2(n+1)
二填空题(空1分 20分)
1． 设n序记录关键字直接插入排序时间复杂度________快速排序均时间复杂度_________
2． 设指针变量p指双循环链表中结点X删结点X需执行语句序列_________________________________________________________（设结点中两指针域分llinkrlink）
3． 根初始关键字序列(1922013810)建立二叉排序树高度____________
4． 深度k完全二叉树中少____________结点
5． 设初始记录关键字序列(K1K2…Kn)筛选法思想建堆必须第______元素开始进行筛选
6． 设哈夫曼树中99结点该树中_________叶子结点采二叉链表作存储结构该树中_____空指针域
7． 设序循环队列中M存储单元该循环队列中够存储________队列元素前实际存储________________队列元素（设头指针F指前队头元素前位置尾指针指前队尾元素位置）
8． 设序线性表中n数元素第i位置插入数元素需移动表中_______数元素删第i位置数元素需移动表中_______元素
9． 设组初始记录关键字序列(201822163019)20中轴趟快速排序结果______________________________
10． 设组初始记录关键字序列(201822163019)根初始关键字序列建成初始堆________________________
11． 设某图G中n顶点邻接矩阵A作该图存储结构顶点i顶点j互邻接点条件______________________
12． 设图应邻接矩阵AA中第i非0元素数_________第i列非0元素数（填等）
13． 设前序遍历某二叉树序列ABCD中序遍历该二叉树序列BADC序遍历该二叉树序列_____________
14． 设散列函数H(k)k mod p解决突方法链址法求列算法划线处填正确语句完成散列表hashtalbe中查找关键字值等k结点成功时返回指关键字指针成功时返回标志0
typedef struct node {int key struct node *next} lklist
void createlkhash(lklist *hashtable[ ])
{
int ik lklist *s
for(i0ifor(i0i{
s(lklist *)malloc(sizeof(lklist)) s>keya[i]
ka[i] p s>nexthashtable[k]_______________________
}
}
三计算题(题10分30分)
1画出广义表LS(( ) (e) (a (b c d )))头尾链表存储结构
2图示森林：
(1) 求树（a）先根序列根序列
(2) 求森林先序序列中序序列
（3）森林转换相应二叉树
3设散列表址范围[ 09 ]散列函数H（key） （key 2 +2）MOD 9采链表处理突请画出元素74536289次插入散列表存储结构
四算法设计题(题10分30分)
1． 设单链表中仅三类字符数元素(写字母数字字符)求利原单链表中结点空间设计出三单链表算法单链表包含类字符
2 设计链式存储结构交换二叉树中结点左右子树算法
3 链式存储结构建立棵二叉排序树
数结构试卷（五）
选择题(20分)
1．数单位（ ）
(A) 数项 (B) 数类型 (C) 数元素 (D) 数变量
2．设组初始记录关键字序列(5040952015706045)增量d4趟希尔排序结束前4条记录关键字（ ）
(A) 40502095 (B) 15406020
(C) 15204045 (D) 45401520
3．设组初始记录关键字序列(25501535808520403670)中含5长度2序子表排序方法该记录关键字序列进行趟结果（ ）
(A) 15253550204080853670
(B) 15253550802085407036
(C) 15253550808520364070
(D) 15253550802036407085
4．函数substr(DATASTRUCTURE59)返回值（ ）
(A) STRUCTURE (B) DATA
(C) ASTRUCTUR (D) DATASTRUCTURE
5．设序单链表中n结点现求插入新结点单链表然保持序该操作时间复杂度（ ）
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)
6．设棵m叉树中度数0结点数N0度数1结点数Nl……度数m结点数NmN0（ ）
(A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m1)Nm
(C) N2+2N3+3N4+……+(m1)Nm (D) 2Nl+3N2+……+(m+1)Nm
7．设序表中1000元素二分查找查找元素X需较（ ）次
(A) 25 (B) 10 (C) 7 (D) 1
8．设连通图G中边集E{(ab)(ae)(ac)(be)(ed)(df)(fc)}顶点a出发种深度优先遍历顶点序列（ ）
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
9．设输入序列123……n栈作输出序列第元素n输出序列中第i输出元素（ ）
(A) ni (B) n1i (C) n+1i (D) 确定
10 设组初始记录关键字序列(458055404285)第记录关键字45基准趟快速排序结果（ ）
(A) 404245558083 (B) 424045808588
(C) 424045558085 (D) 424045855580
二填空题(20分)
1 设序享栈S[0：n1]中第栈项指针top1初值1第二栈顶指针top2初值n判断享栈满条件____________________
2 图邻接表中序存储结构存储表头结点优点____________________
3 设n阶三角矩阵A果行序三角矩阵中元素（包括角线元素）存放n(n+1)连续存储单元中A[i][j]A[0][0]间_______数元素
4 栈插入删栈栈顶进行进栈元素必定先出栈栈称__________表队列插入删运算分队列两端进行先进队列元素必定先出队列队列称_________表
5 设棵完全二叉树序存储结构中存储数元素ABCDEF该二叉树前序遍历序列___________中序遍历序列___________序遍历序列___________
6 设棵完全二叉树128结点该完全二叉树深度__________________叶子结点
7 设图G存储结构邻接矩阵A表示A中第i行中非零元素数等顶点i________第i列中非零元素数等顶点i__________
8 设组初始记录关键字序列(k1k2……kn)堆i12…n2言满足条件_______________________________
9 面程序段功实现泡排序算法请划线处填正确语句
void bubble(int r[n])
{
for(i1i{
for(exchange0j0 j<_____________j++)
if (r[j]>r[j+1]){tempr[j+1]______________r[j]tempexchange1}
if (exchange0) return
}
}
10 面程序段功实现二分查找算法请划线处填正确语句
struct record{int key int others}
int bisearch(struct record r[ ] int k)
{
int low0midhighn1
while(low{
________________________________
if(r[mid]keyk) return(mid+1) else if(____________) highmid1else lowmid+1
}
return(0)
}
三应题(32分)
1 设某棵二叉树中序遍历序列DBEAC前序遍历序列ABDEC求出该二叉树序遍历序列
2 设图G（右图示）出该图生成树边集合计算生成树边权值
3 设组初始记录关键字序列(15171822355160)求计算出成功查找时均查找长度
4 设散列表长度8散列函数H(k)k mod 7初始记录关键字序列(25318271368)求分计算出线性探测法链址法作解决突方法均查找长度
四算法设计题(28分)
1． 设计判断两二叉树否相算法
2． 设计两序单链表合排序算法
数结构试卷（六）
选择题(30分)
1． 设组权值集合W{23456}该权值集合构造哈夫曼树中带权路径长度（ ）
(A) 20 (B) 30 (C) 40 (D) 45
2．执行趟快速排序够序列（ ）
(A) [4112344527] 55 [7263]
(B) [45341241] 55 [726327]
(C) [6312344527] 55 [4172]
(D) [12274541] 55 [346372]
3．设条单链表头指针变量head该链表没头结点判空条件（ ）
(A) head0 (B) head>next0
(C) head>nexthead (D) head0
4．时间复杂度受数初始状态影响恒O(nlog2n)（ ）
(A) 堆排序 (B) 泡排序 (C) 希尔排序 (D) 快速排序
5．设二叉树先序遍历序列序遍历序列正相反该二叉树满足条件（ ）
(A) 空结点 (B) 高度等结点数
(C) 结点左孩子 (D) 结点右孩子
6．趟排序结束定够选出元素放终位置（ ）
(A) 堆排序 (B) 泡排序 (C) 快速排序 (D) 希尔排序
7．设某棵三叉树中40结点该三叉树高度（ ）
(A) 3 (B) 4 (C) 5 (D) 6
8．序查找序线性表中链式线性表中时间复杂度（ ）
(A) O(n) (B) O(n2) (C) O(n12) (D) O(1og2n)
9．二路排序时间复杂度（ ）
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10 深度k完全二叉树中少（ ）结点
(A) 2k11 (B) 2k1 (C) 2k1+1 (D) 2k1
11设指针变量front表示链式队列队头指针指针变量rear表示链式队列队尾指针指针变量s指入队列结点X入队列操作序列（ ）
(A) front>nextsfronts (B) s>nextrearrears
(C) rear>nextsrears (D) s>nextfrontfronts
12设某图中n顶点e条边建立该图邻接表时间复杂度（ ）
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13设某哈夫曼树中199结点该哈夫曼树中（ ）叶子结点
(A) 99 (B) 100 (C) 101 (D) 102
14设二叉排序树n结点二叉排序树查找结点均时间复杂度（ ）
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15设邻接矩阵A表示图G存储结构图G中顶点i入度（ ）
(A) 第i行非0元素数 (B) 第i列非0元素数
(C) 第i行0元素数 (D) 第i列0元素数
二判断题(20分)
1．调次深度优先遍历访问图中顶点（ ）
2．分块查找均查找长度仅索引表长度关块长度关（ ）
3．泡排序初始关键字序列逆序情况执行交换次数（ ）
4．满二叉树定完全二叉树完全二叉树定满二叉树（ ）
5．设棵二叉树先序序列序序列够唯确定出该二叉树形状（ ）
6．层次遍历初始堆序序列（ ）
7．设棵树T转化成二叉树BT二叉树BT中定没右子树（ ）
8．线性表序存储结构链式存储结构更（ ）
9．中序遍历二叉排序树序序列（ ）
10快速排序排序算法中均性种排序（ ）
三填空题(30分)
1．for(i1t1s0i2．设指针变量p指单链表中结点A指针变量s指插入新结点X进行插入操作语句序列__________________________（设结点指针域next）
3．设图G二元组形式表示G （DR）D{12345}R{r}r{<12><24><45><13><32><35>}出该图种拓扑排序序列__________
4．设图G中n顶点该图中顶点度数_________
5．设二叉树中度数0结点数50度数1结点数30该二叉树中总_______结点数
6．设FR分表示序循环队列头指针尾指针判断该循环队列空条件_____________________
7．设二叉树中结点两指针域分lchildrchild判断指针变量p指结点叶子结点条件_____________________________________________
8．简单选择排序直接插入排序算法均时间复杂度___________
9．快速排序算法空间复杂度均情况__________坏情况__________
10散列表中解决突两种方法__________________________
四算法设计题(20分)
１． 设计序序表中实现二分查找算法
２． 设计判断二叉树否二叉排序树算法
３． 链式存储结构设计直接插入排序算法
数结构试卷（七）
选择题(30分)
1．设某图n顶点该图邻接表中（ ）表头结点
(A) 2n (B) n (C) n2 (D) n(n1)
2．设图G中n顶点该图生成树（ ）条边
(A) n (B) n1 (C) 2n (D) 2n1
3．设组初始记录关键字序列(608055404285)第关键字45基准趟快速排序结果（ ）
(A) 404260558085 (B) 424555608580
(C) 424055608085 (D) 424060855580
4．（ ）二叉排序树序序列
(A) 先序遍历 (B) 中序遍历 (C) 序遍历 (D) 层次遍历
5．设左右序1开始完全二叉树进行序编号编号i结点左孩子结点编号（ ）
(A) 2i+1 (B) 2i (C) i2 (D) 2i1
6．程序段si0do {ii+1 ss+i}while(i (A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(n32)
7．设带头结点单循环链表头指针变量head判空条件（ ）
(A) head0 (B) head>next0
(C) head>nexthead (D) head0
8．设某棵二叉树高度10该二叉树叶子结点（ ）
(A) 20 (B) 256 (C) 512 (D) 1024
9．设组初始记录关键字序列(131824354750628390115134)利二分法查找关键字90需较关键字数（ ）
(A) 1 (B) 2 (C) 3 (D) 4
10设指针变量top指前链式栈栈顶删栈顶元素操作序列（ ）
(A) toptop+1 (B) toptop1
(C) top>nexttop (D) toptop>next
二判断题(20分)
1．入队列操作入栈操作序存储结构需考虑溢出情况（ ）
2．二叉排序树中插入结点该结点定成叶子结点（ ）
3．设某堆中n结点该堆中插入新结点时间复杂度O(log2n)（ ）
4．完全二叉树中叶子结点两层中出现（ ）
5．哈夫曼树中没度数1结点（ ）
6．连通图进行深度优先遍历访问该图中顶点（ ）
7．先序遍历棵二叉排序树结点序列定序序列（ ）
8．树转化成二叉树该二叉树右子树定空（ ）
9．线性表中元素前驱元素继元素（ ）
10带权图生成树唯（ ）
三填空题(30分)
1 设指针变量p指双链表中结点A指针变量s指插入结点X结点A面插入结点X操作序列_________ps>rightp>right__________s p>right>lefts（设结点中两指针域分leftright）
2 设完全图中n顶点该完全图中________条条设完全图中n顶点该完全图中________条边
3 设关键字序列(KlK2…Kn)筛选法建初始堆必须第______元素开始进行筛选
4 解决散列表突两种方法__________________________________
5 设棵三叉树中50度数0结点21度数2结点该二叉树中度数3结点数______
6 高度h完全二叉树中少________结点________结点
7 设组初始关键字序列(243512271826)第3趟直接插入排序结束结果__________________________________
8 设组初始关键字序列(243512271826)第3趟简单选择排序结束结果__________________________________
9 设棵二叉树前序序列ABC______________种二叉树种序列
10 面程序段功实现趟快速排序请划线处填正确语句
struct record {int keydatatype others}
void quickpass(struct record r[] int s int t int &i)
{
int jt struct record xr[s] is
while(i{
while (ixkey) jj1 if (i while (____________________) ii+1 if (i }
_________________
}
四算法设计题(20分)
1 设计链式结构实现简单选择排序算法
2 设计序存储结构实现求子串算法
3 设计求结点二叉排序树中层次算法
数结构试卷（八）
选择题(30分)
1 字符串长度指（ ）
(A) 串中字符数 (B) 串中字母数
(C) 串中含字符数 (D) 串中数字数
2 建立长度n序单链表时间复杂度（ ）
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
3 两字符串相等充条件（ ）
(A) 两字符串长度相等 (B) 两字符串中应位置字符相等
(C) 时具备(A)(B)两条件 (D) 答案
4 设某散列表长度100散列函数H(k)k PP通常情况选择（ ）
(A) 99 (B) 97 (C) 91 (D) 93
5 二叉排序树中插入关键字值均时间复杂度（ ）
(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)
6 设序序表A[114]中14元素采二分法查找元素A[4]程中较元素序( )
(A) A[1]A[2]A[3]A[4] (B) A[1]A[14]A[7]A[4]
(C) A[7]A[3]A[5]A[4] (D) A[7]A[5] A[3]A[4]
7 设棵完全二叉树中65结点该完全二叉树深度（ ）
(A) 8 (B) 7 (C) 6 (D) 5
8 设棵三叉树中2度数1结点2度数2结点2度数3结点该三叉链权中（ ）度数0结点
(A) 5 (B) 6 (C) 7 (D) 8
9 设图G中边集合E{(ab)(ae)(ac)(be)(ed)(df)(fc)}顶点a出发进行深度优先遍历种顶点序列（ ）
(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc
10 队列种（ ）线性表
(A) 先进先出 (B) 先进出 (C) 插入 (D) 删
二判断题(20分)
1 果两关键字值等哈希函数值相等称两关键字义词（ ）
2 设初始记录关键字基序快速排序算法时间复杂度O(nlog2n)（ ）
3 分块查找基思想首先索引表中进行查找便确定定关键字存块号然相应块进行序查找（ ）
4 二维数组维数组均特殊线性结构（ ）
5 二叉排序树中插入结点需较次数该二叉树高度（ ）
6 果某图邻接表中第i条单链表空第i顶点出度零（ ）
7 非空双循环链表中结点前驱指针均空（ ）
8 线性表采序存储结构链式存储结构删值X结点时间复杂度均O(n)（ ）
9 图深度优先遍历算法中需设置标志数组便区分图中顶点否访问（ ）
10 稀疏矩阵压缩存储三元组表表示稀疏矩阵中非0元素（ ）
三填空题(30分)
1． 设组初始记录关键字序列(4938659776132750)d4增量趟希尔排序结束结果_____________________________
2． 面程序段功实现二叉排序树中插入新结点请划线处填正确容
typedef struct node{int datastruct node *lchildstruct node *rchild}bitree
void bstinsert(bitree *&tint k)
{
if (t0 ) {____________________________t>datakt>lchildt>rchild0}
else if (t>data>k) bstinsert(t>lchildk)else__________________________
}
3． 设指针变量p指单链表中结点A指针变量s指插入结点X结点A面插入结点X需执行语句序列：s>nextp>next _________________
4． 设指针变量head指双链表中头结点指针变量p指双链表中第结点指针变量p指针变量head间关系p_________head__________（设结点中两指针域分llinkrlink）
5． 设某棵二叉树中序遍历序列ABCD序遍历序列BADC前序遍历序列__________
6． 完全二叉树中第5层少__________结点_________结点
7． 设图中存边应邻接矩阵A中数组元素A[i][j]值等____________
8． 设组初始记录关键字序列(4938659776132750)第4趟直接选择排序结束结果_____________________________
9． 设连通图G中n顶点e条边应生成树___________条边
10． 设组初始记录关键字序列(50162368947073)调整成初始堆需16___________相互交换
四算法设计题(20分)
1 设计链式存储结构统计二叉树中结点数算法
2 设计算法图邻接矩阵转应邻接表算法
数结构试卷（九）
选择题(30分)
1．列程序段时间复杂度（ ）
for(i0 ifor(i0 i (A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n)
2．设序线性表中n数元素删表中第i元素需移动（ ）元素
(A) ni (B) n+l i (C) n1i (D) i
3．设FT1T2T3三棵树组成森林F应二叉树BT1T2T3结点数分N1N2N3二叉树B根结点左子树结点数（ ）
(A) N11 (B) N21 (C) N2+N3 (D) N1+N3
4．利直接插入排序法思想建立序线性表时间复杂度（ ）
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
5．设指针变量p指双链表中结点A指针变量s指插入结点X结点A面插入结点X操作序列（ ）
(A) p>rights s>leftp p>right>lefts s>rightp>right
(B) s>leftps>rightp>rightp>rights p>right>lefts
(C) p>rights p>right>lefts s>leftp s>rightp>right
(D) s>leftps>rightp>rightp>right>lefts p>rights
6．列种排序算法中均时间复杂度O(n2)（ ）
(A) 快速排序 (B) 堆排序 (C) 排序 (D) 泡排序
7．设输入序列123…n栈作输出序列中第元素n输出序列中第i输出元素（ ）
(A) ni (B) n1i (C) n+l i (D) 确定
8．设散列表中m存储单元散列函数H(key) key pp选择（ ）
(A) 等m奇数 (B) 等m素数
(C) 等m偶数 (D) 等m合数
9．设棵度数3树中度数3结点数2度数2结点数1度数1结点数2度数0结点数（ ）
(A) 4 (B) 5 (C) 6 (D) 7
10设完全图中n顶点该完全图中（ ）条边
(A) n(n1)2 (B) n(n1) (C) n(n+1)2 (D) (n1)2
11设序表长度n序查找均较次数（ ）
(A) n (B) n2 (C) (n+1)2 (D) (n1)2
12设序表中元素(13182435475062)中利二分法查找值24元素需（ ）次较
(A) 1 (B) 2 (C) 3 (D) 4
13设序线性表长度30分成5块块6元素果采分块查找均查找长度（ ）
(A) 6 (B) 11 (C) 5 (D) 65
14设环图G中边集合E{<12><23><34><14>}列属该图G种拓扑排序序列（ ）
(A) 1234 (B) 2341 (C) 1423 (D) 1243
15设组初始记录关键字序列(34764518265492)组记录关键字生成二叉排序树深度（ ）
(A) 4 (B) 5 (C) 6 (D) 7
二填空题(30分)
1． 设指针p指单链表中结点A指针s指插入结点X结点A前面插入结点X时操作序列：
1) s>next___________2) p>nexts3) tp>data
4) p>data___________5) s>datat
2． 设某棵完全二叉树中100结点该二叉树中______________叶子结点
3． 设某序循环队列中m元素规定队头指针F指队头元素前位置队尾指针R指队尾元素前位置该循环队列中存储_______队列元素
4． 组初始关键字序列（405095201570604510）进行泡排序第趟需进行相邻记录较次数__________整排序程中需进行__________趟排序完成
5． 堆排序快速排序中果均情况排序速度快角度考虑应选择_________排序果节省存储空间角度考虑选择________排序
6． 设组初始记录关键字序列(20124231181428)根记录关键字构造二叉排序树均查找长度_______________________________
7． 设棵二叉树中序遍历序列BDCA序遍历序列DBAC棵二叉树前序序列____________________
8． 设通信电文仅8字母组成字母电文中出现频率分719263232110根频率作权值构造哈夫曼树棵哈夫曼树高度________________
9． 设组记录关键字序列(80703365245648)筛选法建成初始堆_______________________
10． 设图G（右图示）生成树边权值_________________
三判断题(20分)
1． 图邻接表逆邻接表中表结点数定相等( )
2． 链表进行插入删操作时必移动链表中结点( )
3． 子串ABC串AABCABCD中位置2( )
4． 叶子结点某二叉树中序遍历序列结点必该二叉树先序遍历序列中结点( )
5． 希尔排序算法时间复杂度O(n2)( )
6． 邻接矩阵作图存储结构时占存储空间图中顶点数关图中边数关( )
7． 中序遍历棵二叉排序树序序列( )
8． 入栈操作入队列操作链式存储结构实现时需考虑栈溢出情况( )
9． 序表查找指序存储结构进行查找（ ）
10． 堆完全二叉树完全二叉树定堆（ ）
五算法设计题(20分)
1． 设计计算二叉树中结点值算法
2． 设计奇数移偶数前算法
3． 设计判断单链表中元素否递增算法
数结构试卷（十）
选择题(24分)
1．列程序段时间复杂度（ ）
i0s0 while (s (A) O(n12) (B) O(n13) (C) O(n) (D) O(n2)
2．设某链表中常操作链表尾部插入删元素选列（ ）存储方式节省运算时间
(A) 单链表 (B) 单循环链表
(C) 双链表 (D) 双循环链表
3．设指针q指单链表中结点A指针p指单链表中结点A继结点B指针s指插入结点X结点A结点B插入结点X操作序列（ ）
(A) s>nextp>nextp>nexts (B) q>nexts s>nextp
(C) p>nexts>nexts>nextp (D) p>nextss>nextq
4．设输入序列123456通栈作输出序列（ ）
(A) 534612 (B) 325641
(C) 312546 (D) 154623
5．设10阶三角矩阵A（包括角线）左右序存储连续55存储单元中数组元素占1字节存储空间A[5][4]址A[0][0]址差（ ）
(A) 10 (B) 19 (C) 28 (D) 55
6．设棵m叉树中N1度数1结点N2度数2结点……Nm度数m结点该树中（ ）叶子结点
(A) (B) (C) (D)
7 二叉排序树中左子树结点值均（ ）根结点值
(A) < (B) > (C) (D)
8 设组权值集合W(153142691617)求根权值集合构造棵哈夫曼树棵哈夫曼树带权路径长度（ ）
(A) 129 (B) 219 (C) 189 (D) 229
9 设n关键字具相Hash函数值线性探测法n关键字映射HASH表中需做（ ）次线性探测
(A) n2 (B) n(n+1) (C) n(n+1)2 (D) n(n1)2
10设某棵二叉树中度数0度数2结点度数0结点数n棵二叉中（ ）结点
(A) 2n (B) n+l (C) 2n1 (D) 2n+l
11设组初始记录关键字长度8（ ）趟插入排序序序列
(A) 6 (B) 7 (C) 8 (D) 9
12设组初始记录关键字序列(QHCYPAMSRDFX)字母升序第趟泡排序结束结果（ ）
(A) FHCDPAMQRSYX
(B) PACSQDFXRHMY
(C) ADCRFQMSYPHX
(D) HCQPAMSRDFXY
二填空题(48分中两题6分)
1 设需5记录关键字进行排序少需较_____________次需较_____________次
2 快速排序算法均时间复杂度____________直接插入排序算法均时间复杂度___________
3 设二叉排序树高度h该树中查找关键字key需较_________次
4 设长度20序表中进行二分查找较次查找成功结点数_________较两次查找成功结点数_________
5 设棵m叉树脂结点数n重链表表示存储结构该树中_________空指针域
6 设指针变量p指单链表中结点A删结点A语句序列：
qp>nextp>dataq>datap>next___________feee(q)
7 数结构逻辑划分三种基类型：________________________________
8 设图G中n顶点e条边邻接矩阵作图存储结构进行深度优先广度优先遍历时时间复杂度_________邻接表作图存储结构进行深度优先广度优先遍历时间复杂度_________
9 设散列表长度8散列函数H(k)k 7线性探测法解决突根组初始关键字序列(81516223032)构造出散列表均查找长度________
10 设组初始关键字序列(38659776132710)第3趟泡排序结束结果_____________________
11 设组初始关键字序列(38659776132710)第3趟简单选择排序结果______________________
12 设图G中边集合E{<12><23><14><45><53><46><65>}该图拓扑序列_________________________
13 面程序段功建立二叉树算法请划线处填正确容
typedef struct node{int datastruct node *lchild________________}bitree
void createbitree(bitree *&bt)
{
scanf(c&ch)
if(ch＇#＇) ___________else
{ bt(bitree*)malloc(sizeof(bitree)) bt>datach ________createbitree(bt>rchild)}
}
14 面程序段功利尾部插入方法建立单链表算法请划线处填正确容
typedef struct node {int data struct node *next} lklist
void lklistcreate(_____________ *&head )
{
for (i1i{
p(lklist *)malloc(sizeof(lklist))scanf(d&(p>data))p>next0
if(i1)headqpelse {q>nextp____________}
}
}
三算法设计题(22分)
1． 设计链式存储结构合排序算法
2． 设计二叉排序树查找结点X算法
3． 设关键字序列(k1k2…kn1)堆设计算法关键字序列(k1k2…kn1x)调整堆
数结构试卷（）参考答案
选择题（题2分20分）
1A 2D 3D 4C 5C 6D 7D 8C 9D 10A
二填空题（空1分26分）
1 正确性 易读性 强壮性 高效率
2 O(n)
3 9 3 3
4 1 3 4 X * + 2 Y * 3
5 2n n1 n+1
6 e 2e
7 回路
8 n(n1)2 n(n1)
9 （1240） （ ） （74） （235563）
10 增加1
11 O(log2n) O(nlog2n)
12
三计算题（题6分24分）
1 线性表：（785040603490）
2 邻接矩阵：
邻接表图11示：
图11
3 克鲁斯卡尔算法生成树：
(12)3 (46)4 (13)5 (14)8 (25)10 (47)20
4 见图12
4
4
4
4
4
2
2
2
5
5
2
8
5
2
8
3
4
5
2
8
4
3
图12
四 读算法（题7分14分）
1 （1）查询链表尾结点
（2）第结点链接链表尾部作新尾结点
（3）返回线性表（a2a3…ana1）
2 递序遍历链式存储二叉树
五 法填空（空2分8 分）
true BST>left BST>right
六 编写算法（8分）
int CountX(LNode* HLElemType x)
{ int i0 LNode* pHLi计数器
while(pNULL)
{ if (P>datax) i++
pp>next
}while 出循环时i中值x结点数
return i
}CountX
数结构试卷（二）参考答案
选择题
1D 2B 3C 4A 5A 6C 7B 8C
二填空题
1 构造HASH函数确定解决突方法
2 stacktop++stacks[stacktop]x
3 序
4 O(n2)O(nlog2n)
5 N012N0+N1
6 d2
7 (3138545675805563)
8 (13452)(13245)
三应题
1 (224045488078)(404548802278)
2 q>llinkp q>rlinkp>rlink p>rlink>llinkq p>rlinkq
3 2ASL91*1+2*2+3*4+4*2)259
4 树链式存储结构略二叉树略
5 E{(13)(12)(35)(56)(64)}
6 略
四算法设计题
1 设组初始记录关键字序列（K1K2…Kn）求设计算法够O(n)时间复杂度线性表划分成两部分中左半部分关键字均Ki右半部分关键字均等Ki
void quickpass(int r[] int s int t)
{
int is jt xr[s]
while(iwhile (ix) jj1 if (i while (i }
r[i]x
}
2 设两集合A集合B求设计生成集合CA∩B算法中集合ABC链式存储结构表示
typedef struct node {int data struct node *next}lklist
void intersection(lklist *halklist *hblklist *&hc)
{
lklist *p*q*t
for(phahc0p0pp>next)
{ for(qhbq0qq>next) if (q>datap>data) break
if(q0){ t(lklist *)malloc(sizeof(lklist)) t>datap>datat>nexthc hct}
}
}
数结构试卷（三）参考答案
选择题
1B 2B 3A 4A 5A
6B 7D 8C 9B 10D
第3题分析：首先指针变量q指结点A继结点B然结点B值复制结点A中删结点B
第9题分析：9快速排序排序插入排序必须等整排序结束够求出10数堆排序需初始堆基础进行10次筛选次筛选时间复杂度O(log2n)
二填空题
1 序存储结构链式存储结构
2 9501
3 5
4 出度入度
5 0
6 ed
7 中序
8 7
9 O(1)
10 i22i+1
11 (5167123729473)
12 (1432)
13 j+1hashtable[j]keyk
14 return(t)tt>rchild
第8题分析：二分查找程棵二叉树描述该二叉树称二叉判定树序表进行二分查找时查找长度超二叉判定树高度1+log2n
三计算题
1．
2H(36)36 mod 71 H１(22)(1+1) mod 72 …突
H(15)15 mod 71…突 H2(22)(2+1) mod 73
H１(15)(1+1) mod 72
H(40)40 mod 75
H(63)63 mod 70
H(22)22 mod 71 …突
（1） 0 1 2 3 4 5 6
63
36
15
22
40
（2）ASL
3(894361)10(121818)
(1643)8(9)1012(1818)
1(346)89101218(18)
13(46)8910121818
13 468910121818
四算法设计题
1 设计单链表中删值相余结点算法
typedef int datatype
typedef struct node {datatype data struct node *next}lklist
void delredundant(lklist *&head)
{
lklist *p*q*s
for(pheadp0pp>next)
{
for(qp>nextsqq0 )
if (q>datap>data) {s>nextq>next free(q)qs>next}
else {sqqq>next}
}
}
2 设计求结点x二叉树中双亲结点算法
typedef struct node {datatype data struct node *lchild*rchild} bitree
bitree *q[20] int r0f0flag0
void preorder(bitree *bt char x)
{
if (bt0 && flag0)
if (bt>datax) { flag1 return}
else {r(r+1) 20 q[r]bt preorder(bt>lchildx) preorder(bt>rchildx) }
}
void parent(bitree *btchar x)
{
int i
preorder(btx)
for(if+1 ilchild>datax || q[i]>rchild>data) break
if (flag0) printf(not found x＼n)
else if (idata) else printf(not parent)
}
数结构试卷（四）参考答案
选择题
1．C 2．D 3．D 4．B 5．C
6．A 7．B 8．A 9．C 10．A
二填空题
1 O(n2)O(nlog2n)
2 p>llink>rlinkp>rlink p>rlink>llinkp>rlink
3 3
4 2k1
5 n2
6 5051
7 m1(RF+M)M
8 n+1ini
9 (191816203022)
10 (161819203222)
11 A[i][j]1
12 等
13 BDCA
14 hashtable[i]0hashtable[k]s
三计算题
1．
2．
(1) ABCDEF BDEFCA(2) ABCDEFGHIJK BDEFCAIJKHG林转换相应二叉树
3．H(4)H(5)0H(3)H(6)H(9)2H(8)3H(2)H(7)6
四算法设计题
1 设单链表中仅三类字符数元素(写字母数字字符)求利原单链表中结点空间设计出三单链表算法单链表包含类字符
typedef char datatype
typedef struct node {datatype data struct node *next}lklist
void split(lklist *headlklist *&halklist *&hblklist *&hc)
{
lklist *p ha0hb0hc0
for(pheadp0phead)
{
headp>next p>next0
if (p>data>＇A＇ && p>data<＇Z＇) {p>nextha hap}
else if (p>data>＇0＇ && p>data<＇9＇) {p>nexthb hbp} else {p>nexthc hcp}
}
}
2 设计链式存储结构交换二叉树中结点左右子树算法
typedef struct node {int data struct node *lchild*rchild} bitree
void swapbitree(bitree *bt)
{
bitree *p
if(bt0) return
swapbitree(bt>lchild) swapbitree(bt>rchild)
pbt>lchild bt>lchildbt>rchild bt>rchildp
}
3 链式存储结构建立棵二叉排序树
#define n 10
typedef struct node{int key struct node *lchild*rchild}bitree
void bstinsert(bitree *&btint key)
{
if (bt0){bt(bitree *)malloc(sizeof(bitree)) bt>keykeybt>lchildbt>rchild0}
else if (bt>key>key) bstinsert(bt>lchildkey) else bstinsert(bt>rchildkey)
}
void createbsttree(bitree *&bt)
{
int i
for(i1i}
数结构试卷（五）参考答案
选择题
1．A 2．B 3．A 4．A 5．D
6．B 7．B 8．B 9．C 10．C
二填空题
1 top1+1top2
2 机访问顶点简单链表
3 i(i+1)2+j1
4 FILOFIFO
5 ABDECFDBEAFCDEBFCA
6 864
7 出度入度
8 ki9 nir[j+1]r[j]
10 mid(low+high)2r[mid]key>k
三应题
2 DEBCA
3 E{(15)(52)(53)(34)}W10
4 ASL(1*1+2*2+3*4)7177
5 ASL176ASL243
四算法设计题
1 设计判断两二叉树否相算法
typedef struct node {datatype data struct node *lchild*rchild} bitree
int judgebitree(bitree *bt1bitree *bt2)
{
if (bt10 && bt20) return(1)
else if (bt10 || bt20 ||bt1>databt2>data) return(0)
else return(judgebitree(bt1>lchildbt2>lchild)*judgebitree(bt1>rchildbt2>rchild))
}
2 设计两序单链表合排序算法
void mergelklist(lklist *halklist *hblklist *&hc)
{
lklist *shc0
while(ha0 && hb0)
if(ha>datadata){if(s0) hcsha else {s>nextha sha}haha>next}
else {if(s0) hcshb else {s>nexthb shb}hbhb>next}
if(ha0) s>nexthb else s>nextha
}
数结构试卷（六）参考答案
选择题
1．D 2．A 3．A 4．A 5．D
6．D 7．B 8．A 9．C 10．B
11．C 12．A 13．B 14．D 15．B
二判断题
1．错 2． 3． 4． 5．错
6．错 7． 8．错 9． 10．
三填空题
1 O(n)
2 s>nextp>next p>nexts
3 (13245)
4 n1
5 129
6 FR
7 p>lchild0&&p>rchild0
8 O(n2)
9 O(nlog2n) O(n)
10 开放定址法链址法
四算法设计题
1 设计序序表中实现二分查找算法
struct record {int key int others}
int bisearch(struct record r[ ] int k)
{
int low0midhighn1
while(low{
mid(low+high)2
if(r[mid]keyk) return(mid+1) else if(r[mid]key>k) highmid1 else lowmid+1
}
return(0)
}
2 设计判断二叉树否二叉排序树算法
int minnum32768flag1
typedef struct node{int key struct node *lchild*rchild}bitree
void inorder(bitree *bt)
{
if (bt0) {inorder(bt>lchild) if(minnum>bt>key)flag0 minnumbt>keyinorder(bt>rchild)}
}
3 链式存储结构设计直接插入排序算法
void straightinsertsort(lklist *&head)
{
lklist *s*p*q int t
if (head0 || head>next0) return
else for(qheadphead>nextp0pq>next)
{
for(sheadsq>nextss>next) if (s>data>p>data) break
if(sq>next)qp
else{q>nextp>next p>nexts>next s>nextp tp>datap>datas>datas>datat}
}
}
数结构试卷（七）参考答案
选择题
1．B 2．B 3．C 4．B 5．B
6．A 7．C 8．C 9．B 10．D
二判断题
1． 2． 3． 4． 5．
6． 7． 8．错 9．错 10．错
三填空题
1 s>leftpp>right
2 n(n1)n(n1)2
3 n2
4 开放定址法链址法
5 14
6 2h12h1
7 (122435271826)
8 (121824273526)
9 5
10 i
四算法设计题
1 设计链式结构实现简单选择排序算法
void simpleselectsorlklist(lklist *&head)
{
lklist *p*q*s int mint
if(head0 ||head>next0) return
for(qhead q0qq>next)
{
minq>data sq
for(pq>next p0pp>next) if(min>p>data){minp>data sp}
if(sq){ts>data s>dataq>data q>datat}
}
}
2 设计序存储结构实现求子串算法
void substring(char s[ ] long start long count char t[ ])
{
long ijlengthstrlen(s)
if (start<1 || start>length) printf(The copy position is wrong)
else if (start+count1>length) printf(Too characters to be copied)
else { for(istart1j0 i}
3 设计求结点二叉排序树中层次算法
int lev0
typedef struct node{int key struct node *lchild*rchild}bitree
void level(bitree *btint x)
{
if (bt0)
{lev++ if (bt>keyx) return else if (bt>key>x) level(bt>lchildx) else level(bt>rchildx)}
}
数结构试卷（八）参考答案
选择题
1．C 2．C 3．C 4．B 5．B
6．C 7．B 8．C 9．A 10．A
二判断题
1． 2．错 3． 4．错 5．错
6． 7． 8． 9． 10．
三填空题
1 (4913275076386597)
2 t(bitree *)malloc(sizeof(bitree))bstinsert(t>rchildk)
3 p>nexts
4 head>rlinkp>llink
5 CABD
6 116
7 0
8 (1327385076496597)
9 n1
10 50
四算法设计题
1 设计链式存储结构统计二叉树中结点数算法
void countnode(bitree *btint &count)
{
if(bt0)
{count++ countnode(bt>lchildcount) countnode(bt>rchildcount)}
}
2 设计算法图邻接矩阵转应邻接表算法
typedef struct {int vertex[m] int edge[m][m]}gadjmatrix
typedef struct node1{int infoint adjvertex struct node1 *nextarc}glinklistnode
typedef struct node2{int vertexinfoglinklistnode *firstarc}glinkheadnode
void adjmatrixtoadjlist(gadjmatrix g1[ ]glinkheadnode g2[ ])
{
int ij glinklistnode *p
for(i0ifor(i0iif (g1edge[i][j]1)
{
p(glinklistnode *)malloc(sizeof(glinklistnode))p>adjvertexj
p>nextarcg[i]firstarc g[i]firstarcp
p(glinklistnode *)malloc(sizeof(glinklistnode))p>adjvertexi
p>nextarcg[j]firstarc g[j]firstarcp
}
}
数结构试卷（九）参考答案
选择题
1．A 2．A 3．A 4．C 5．D
6．D 7．C 8．B 9．C 10．A
11．C 12．C 13．D 14．A 15．A
二填空题
1 p>nexts>data
2 50
3 m1
4 68
5 快速堆
6 197
7 CBDA
8 6
9 (24653380705648)
10 8
三判断题
1．错 2． 3． 4． 5．错
6．错 7． 8． 9．错 10．
四算法设计题
1． 设计计算二叉树中结点值算法
void sum(bitree *btint &s)
{
if(bt0) {ss+bt>data sum(bt>lchilds) sum(bt>rchilds)}
}
2． 设计奇数移偶数前算法
void quickpass(int r[] int s int t)
{
int isjtxr[s]
while(i{
while (i while (i }
r[i]x
}
3． 设计判断单链表中元素否递增算法
int isriselk(lklist *head)
{
if(head0||head>next0) return(1)else
for(qheadphead>next p0 qppp>next)if(q>data>p>data) return(0)
return(1)
}
数结构试卷（十）参考答案
选择题
1．A 2．D 3．B 4．B 5．B 6．D
7．A 8．D 9．D 10．C 11．B 12．D
二填空题
1 410
2 O(nlog2n)O(n2)
3 n
4 12
5 n(m1)+1
6 q>next
7 线性结构树型结构图型结构
8 O(n2) O(n+e)
9 83
10 (38132710657697)
11 (10132776659738)
12 124653
13 struct node *rchildbt0createbitree(bt>lchild)
14 lklistqp
三算法设计题
1 设计链式存储结构合排序算法
void mergelklist(lklist *halklist *hblklist *&hc)
{
lklist *shc0
while(ha0 && hb0)
if(ha>datadata){if(s0) hcsha else {s>nextha sha}haha>next}
else {if(s0) hcshb else {s>nexthb shb}hbhb>next}
if(ha0) s>nexthb else s>nextha
}
2 设计二叉排序树查找结点X算法
bitree *bstsearch1(bitree *t int key)
{
bitree *pt
while(p0) if (p>keykey) return(p)else if (p>key>key)pp>lchild else pp>rchild
return(0)
}
3 设关键字序列(k1k2…kn1)堆设计算法关键字序列(k1k2…kn1x)调整堆
void adjustheap(int r[ ]int n)
{
int jnij2tempr[j1]
while (i>1) if (temp>r[i1])break else{r[j1]r[i1] ji ii2}
r[j1]temp
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档
数结构试卷（二） 4
数结构试卷（三） 6
数结构试卷（四） 8
数结构试卷（五） 11
数结构试卷（六） 14
数结构试卷（七） 16
数结构试卷（八） 18
数结构试卷（九） 20
数结构试卷（十） 23
数结构试卷（）参考答案 26
数结构试卷（二）参考答案 27
数结构试卷（三）参考答案 28
数结构试卷（四）参考答案 30
数结构试卷（五）参考答案 32
数结构试卷（六）参考答案 33
数结构试卷（七）参考答案 36
数结构试卷（八）参考答案 37
数结构试卷（九）参考答案 38
数结构试卷（十）参考答案 39
数结构试卷（）
单选题（题 2 分20分）
1 栈队列特点( )
A允许端点处插入删元素
B先进出
C先进先出
D没点
2 链接方式存储队列进行插入运算时( )
A 仅修改头指针 B 头尾指针修改
C 仅修改尾指针 D头尾指针修改
3 数结构中非线性结构？( )
A 队列 B 栈 C 线性表 D 二叉树
4 设二维数组A[m][n]假设A[0][0]存放位置644(10)A[2][2]存放位置676(10)元素占空间问A[3][3](10)存放什位置？脚注(10)表示10进制表示
A．688 B．678 C．692 D．696
5 树适合表示( )
A序数元素 B序数元素
C元素间具分支层次关系数 D元素间联系数
6 二叉树第k层结点数( )
A．2k1 B2K+1 C2K1 D 2k1
7 18元素序表存放维数组A[19]中第元素放A[1]中现进行二分查找查找A［3］较序列标次( )
A 123 B 9523
C 953 D 9423
8 n记录文件进行快速排序需辅助存储空间致
A O（1） B O（n） C O（1og2n） D O（n2）
9 线性表（734552564462010）进行散列存储时选H（K）K 9作散列函数散列址1元素（ ）
A．1 B．2 C．3 D．4
10 设6结点图该图少应( )条边确保连通图
A5 B6 C7 D8
二填空题（空1分26分）
1 通常四方面评价算法质量：____________________________________
2 算法时间复杂度(n3+n2log2n+14n)n2数量级表示________
3 假定棵树广义表表示A（CD（EFG）H（IJ））树中含结点数_ _________树深度___________树度_________
4 缀算式9 2 3 + 10 2 值__________中缀算式（3+4X）2Y3应缀算式_______________________________
5 链表存储棵二叉树时结点数域外指左孩子右孩子两指针种存储结构中n结点二叉树________指针域中________指针域存放址________________指针空指针
6 具n顶点e条边图图应邻接表中含边结点分_______________
7 AOV网种___________________图
8 具n顶点完全图中包含________条边具n顶点完全图中包含________条边
9 假定线性表(122374556340)Key 4条件进行划分余数元素成子表四子表分________________________________________________________________________________________________
10 棵B_树插入元素程中终引起树根结点分裂新树原树高度___________
11 堆排序程中分支结点进行筛运算时间复杂度________整堆排序程时间复杂度________
12 快速排序堆排序排序中_________排序稳定
三计算题（题 6 分24分）
1 数组A中链接存储线性表表头指针A [0]next试写出该线性表
A 0 1 2 3 4 5 6 7
data
60
50
78
90
34
40
next
3
5
7
2
0
4
1
2 请画出图邻接矩阵邻接表
3 已知图顶点集V边集E分：V{1234567}
E{(12)3(13)5(14)8(25)10(23)6(34)15
(35)12(36)9(46)4(47)20(56)18(67)25}
克鲁斯卡尔算法生成树试写出生成树中次条边
4 画出根堆中加入数4 2 5 8 3时加入数堆变化
四阅读算法（题7分14分）
1 LinkList mynote(LinkList L)
{L带头结点单链表头指针
if(L&&L>next){
qLLL－>nextpL
S1： while(p－>next) pp－>next
S2： p－>nextqq－>nextNULL
}
return L
}
请回答列问题：
（1）说明语句S1功
（2）说明语句组S2功
（3）设链表表示线性表（a1a2 …an）写出算法执行返回值表示线性表
2 void ABC(BTNode * BT)
{
if BT {
ABC (BT>left)
ABC (BT>right)
cout<
}
}
该算法功：
五算法填空（8分）
二叉搜索树查找——递算法
bool Find(BTreeNode* BSTElemType& item)
{
if (BSTNULL)
return false 查找失败
else {
if (itemBST>data){
itemBST>data查找成功
return ___________}
else if(item
return Find(______________item)
else return Find(_______________item)
}if
}
六编写算法（8分）
统计出单链表HL中结点值等定值X结点数
int CountX(LNode* HLElemType x)
数结构试卷（二）
选择题(24分)
1．面关线性表叙述错误（ ）
(A) 线性表采序存储必须占片连续存储空间
(B) 线性表采链式存储必占片连续存储空间
(C) 线性表采链式存储便插入删操作实现
(D) 线性表采序存储便插入删操作实现
2．设哈夫曼树中叶子结点总数m二叉链表作存储结构该哈夫曼树中总（ ）空指针域
(A) 2m1 (B) 2m (C) 2m+1 (D) 4m
3．设序循环队列Q[0：M1]头指针尾指针分FR头指针F总指队头元素前位置尾指针R总指队尾元素前位置该循环队列中元素数（ ）
(A) RF (B) FR (C) (RF+M)％M (D) (FR+M)％M
4．设某棵二叉树中序遍历序列ABCD前序遍历序列CABD序遍历该二叉树序列（ ）
(A) BADC (B) BCDA (C) CDAB (D) CBDA
5．设某完全图中n顶点该完全图中（ ）条边
(A) n(n1)2 (B) n(n1) (C) n2 (D) n21
6．设某棵二叉树中2000结点该二叉树高度（ ）
(A) 9 (B) 10 (C) 11 (D) 12
7．设某图中n顶点该图应邻接表中（ ）表头结点
(A) n1 (B) n (C) n+1 (D) 2n1
8．设组初始记录关键字序列(52638)第记录关键字5基准进行趟快速排序结果（ ）
(A) 23586 (B) 32586
(C) 32568 (D) 23658
二填空题(24分)
1 效应HASH查找技术必须解决两问题______________________________________________
2 面程序段功实现数x进栈求划线处填正确语句
typedef struct {int s[100] int top} sqstack
void push(sqstack &stackint x)
{
if (stacktopm1) printf(overflow)
else {_____________________________________}
}
3 中序遍历二叉排序树序列___________序列（填序序）
4 快速排序坏时间复杂度___________均时间复杂度__________
5 设某棵二叉树中度数0结点数N0度数1结点数N1该二叉树中度数2结点数_________采二叉链表作该二叉树存储结构该二叉树中_______空指针域
6 设某图中顶点数边数分ne顶点度数de_______
7 设组初始记录关键字序列(5563443875803156)利筛选法建立初始堆___________________________
8． 已知图邻接表存储结构：顶点1出发DFS遍历输出序列
BFS遍历输出序列
三应题(36分)
1． 设组初始记录关键字序列(458048402278)分出第4趟简单选择排序第4趟直接插入排序结果
2． 设指针变量p指双链表中结点A指针变量q指插入结点B求出结点A面插入结点B操作序列（设双链表中结点两指针域分llinkrlink）
3． 设组序记录关键字序列(131824354750628390)查找方法二分查找求计算出查找关键字62时较次数计算出查找成功时均查找长度
4． 设棵树T中边集合{(AB)(AC)(AD)(BE)(CF)(CG)}求孩子兄弟表示法（二叉链表）表示出该树存储结构该树转化成应二叉树
5． 设图G求出普里姆算法构造生成树走边集合
6． 设组初始记录关键字(458048402278)求构造棵二叉排序树出构造程
四算法设计题(16分)
1． 设组初始记录关键字序列（K1K2…Kn）求设计算法够O(n)时间复杂度线性表划分成两部分中左半部分关键字均Ki右半部分关键字均等Ki
2． 设两集合A集合B求设计生成集合CA∩B算法中集合ABC链式存储结构表示
数结构试卷（三）
选择题(题1分20分)
1．设某数结构二元组形式表示A(DR)D{010203040506070809}R{r}r{<0102><0103><0104><0205><0206><0307><0308><0309>}数结构A（ ）
(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构
2．面程序时间复杂（ ）
for（i1s0 i
3．设指针变量p指单链表中结点A删单链表中结点A需修改指针操作序列（ ）
(A) qp>nextp>dataq>datap>nextq>nextfree(q)
(B) qp>nextq>datap>datap>nextq>nextfree(q)
(C) qp>nextp>nextq>nextfree(q)
(D) qp>nextp>dataq>datafree(q)
4．设n排序记录关键字堆排序中需（ ）辅助记录单元
(A) 1 (B) n (C) nlog2n (D) n2
5．设组初始关键字记录关键字(2015141821364010)20基准记录趟快速排序结束结果( )
(A) 1015141820364021
(B) 1015141820403621
(C) 101514201840362l
(D) 1510141820364021
6．设二叉排序树中n结点二叉排序树均均查找长度（ ）
(A) O(1) (B) O(log2n) (C) (D) O(n2)
7．设图G中n顶点e条边应邻接表中表头结点表结点数分（ ）
(A) ne (B) en (C) 2ne (D) n2e
8 设某强连通图中n顶点该强连通图中少（ ）条边
(A) n(n1) (B) n+1 (C) n (D) n(n+1)
9．设5000排序记录关键字果需快方法选出中10记录关键字列（ ）方法达目
(A) 快速排序 (B) 堆排序 (C) 排序 (D) 插入排序
10列四种排序中（ ）空间复杂度
(A) 插入排序 (B) 泡排序 (C) 堆排序 (D) 排序
二填空殖(空1分 20分)
1 数物理结构包括___________________________两种情况
2 设棵完全二叉树中500结点该二叉树深度__________二叉链表作该完全二叉树存储结构___________空指针域
3 设输入序列123栈作___________种输出序列
4 设图G邻接矩阵A[n][n]作存储结构该邻接矩阵中第i行元素等顶点i________第i列元素等顶点i________
5 设哈夫曼树中n结点该哈夫曼树中________度数1结点
6 设图G中n顶点e条边顶点入度数ded关系_________
7 __________遍历二叉排序树中结点递增关键字序列（填先序中序序）
8 设查找表中100元素果二分法查找方法查找数元素X需较________次断定数元素X否查找表中
9 序存储结构栈链式存储结构栈入栈出栈操作时间复杂度均____________
10 设n结点完全二叉树果左右1开始序编号第i结点双亲结点编号____________右孩子结点编号___________
11 设组初始记录关键字(7273712394165)记录关键字72基准趟快速排序结果___________________________
12 设图G中边集合E{<12><23><14><42><43>}该图种拓扑序列____________________
13 列算法实现序散列表中查找值x关键字请划线处填正确语句
struct record{int key int others}
int hashsqsearch(struct record hashtable[ ]int k)
{
int ij jik p
while (hashtable[j]keyk&&hashtable[j]flag0){j(____) m if (ij) return(1)}
if (_______________________ ) return(j) else return(1)
}
14 列算法实现二叉排序树查找关键值k请划线处填正确语句
typedef struct node{int key struct node *lchild struct node *rchild}bitree
bitree *bstsearch(bitree *t int k)
{
if (t0 ) return(0)else while (t0)
if (t>keyk)_____________ else if (t>key>k) tt>lchild else_____________
}
三计算题(题10分30分)
1已知二叉树前序遍历序列AEFBGCDHIKJ中序遍历序列EFAGBCHKIJD画出二叉树画出序线索二叉树
2．已知散列线性表（3615406322）散列维址空间[06]假定选散列函数H（K） K mod 7发生突采线性探查法处理试：
（1）计算出元素散列址图中填写出散列表：
` 0 1 2 3 4 5 6
（2）求出查找元素概率相等情况均查找长度
3．已知序列（10184361219188）请快速排序写出趟排序结果
四算法设计题(题15分30分)
1． 设计单链表中删值相余结点算法
2． 设计求结点x二叉树中双亲结点算法
数结构试卷（四）
选择题(题1分 20分)
1．设维数组中n数组元素读取第i数组元素均时间复杂度（ ）
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
2．设棵二叉树深度k该二叉树中（ ）结点
(A) 2k1 (B) 2k (C) 2k1 (D) 2k1
3．设某图中n顶点e条边该图中顶点入度（ ）
(A) n (B) e (C) 2n (D) 2e
4．二叉排序树中插入结点时间复杂度（ ）
(A) O(1) (B) O(n) (C) O(log2n) (D) O(n2)
5．设某图邻接表中n表头结点m表结点该图中（ ）条边
(A) n (B) n1 (C) m (D) m1
6．设组初始记录关键字序列(345253674924627)基数排序需进行（ ）趟分配回收初始关键字序列变成序序列
(A) 3 (B) 4 (C) 5 (D) 8
7．设链表作栈存储结构退栈操作（ ）
(A) 必须判栈否满 (B) 必须判栈否空
(C) 判栈元素类型 (D) 栈作判
8．列四种排序中（ ）空间复杂度
(A) 快速排序 (B) 泡排序 (C) 希尔排序 (D) 堆
9．设某二叉树中度数0结点数N0度数1结点数Nl度数2结点数N2列等式成立（ ）
(A) N0N1+1 (B) N0Nl+N2 (C) N0N2+1 (D) N02N1+l
10设序序表中n数元素利二分查找法查找数元素X较次数超（ ）
(A) log2n+1 (B) log2n1 (C) log2n (D) log2(n+1)
二填空题(空1分 20分)
1． 设n序记录关键字直接插入排序时间复杂度________快速排序均时间复杂度_________
2． 设指针变量p指双循环链表中结点X删结点X需执行语句序列_________________________________________________________（设结点中两指针域分llinkrlink）
3． 根初始关键字序列(1922013810)建立二叉排序树高度____________
4． 深度k完全二叉树中少____________结点
5． 设初始记录关键字序列(K1K2…Kn)筛选法思想建堆必须第______元素开始进行筛选
6． 设哈夫曼树中99结点该树中_________叶子结点采二叉链表作存储结构该树中_____空指针域
7． 设序循环队列中M存储单元该循环队列中够存储________队列元素前实际存储________________队列元素（设头指针F指前队头元素前位置尾指针指前队尾元素位置）
8． 设序线性表中n数元素第i位置插入数元素需移动表中_______数元素删第i位置数元素需移动表中_______元素
9． 设组初始记录关键字序列(201822163019)20中轴趟快速排序结果______________________________
10． 设组初始记录关键字序列(201822163019)根初始关键字序列建成初始堆________________________
11． 设某图G中n顶点邻接矩阵A作该图存储结构顶点i顶点j互邻接点条件______________________
12． 设图应邻接矩阵AA中第i非0元素数_________第i列非0元素数（填等）
13． 设前序遍历某二叉树序列ABCD中序遍历该二叉树序列BADC序遍历该二叉树序列_____________
14． 设散列函数H(k)k mod p解决突方法链址法求列算法划线处填正确语句完成散列表hashtalbe中查找关键字值等k结点成功时返回指关键字指针成功时返回标志0
typedef struct node {int key struct node *next} lklist
void createlkhash(lklist *hashtable[ ])
{
int ik lklist *s
for(i0i
s(lklist *)malloc(sizeof(lklist)) s>keya[i]
ka[i] p s>nexthashtable[k]_______________________
}
}
三计算题(题10分30分)
1画出广义表LS(( ) (e) (a (b c d )))头尾链表存储结构
2图示森林：
(1) 求树（a）先根序列根序列
(2) 求森林先序序列中序序列
（3）森林转换相应二叉树
3设散列表址范围[ 09 ]散列函数H（key） （key 2 +2）MOD 9采链表处理突请画出元素74536289次插入散列表存储结构
四算法设计题(题10分30分)
1． 设单链表中仅三类字符数元素(写字母数字字符)求利原单链表中结点空间设计出三单链表算法单链表包含类字符
2 设计链式存储结构交换二叉树中结点左右子树算法
3 链式存储结构建立棵二叉排序树
数结构试卷（五）
选择题(20分)
1．数单位（ ）
(A) 数项 (B) 数类型 (C) 数元素 (D) 数变量
2．设组初始记录关键字序列(5040952015706045)增量d4趟希尔排序结束前4条记录关键字（ ）
(A) 40502095 (B) 15406020
(C) 15204045 (D) 45401520
3．设组初始记录关键字序列(25501535808520403670)中含5长度2序子表排序方法该记录关键字序列进行趟结果（ ）
(A) 15253550204080853670
(B) 15253550802085407036
(C) 15253550808520364070
(D) 15253550802036407085
4．函数substr(DATASTRUCTURE59)返回值（ ）
(A) STRUCTURE (B) DATA
(C) ASTRUCTUR (D) DATASTRUCTURE
5．设序单链表中n结点现求插入新结点单链表然保持序该操作时间复杂度（ ）
(A) O(log2n) (B) O(1) (C) O(n2) (D) O(n)
6．设棵m叉树中度数0结点数N0度数1结点数Nl……度数m结点数NmN0（ ）
(A) Nl+N2+……+Nm (B) l+N2+2N3+3N4+……+(m1)Nm
(C) N2+2N3+3N4+……+(m1)Nm (D) 2Nl+3N2+……+(m+1)Nm
7．设序表中1000元素二分查找查找元素X需较（ ）次
(A) 25 (B) 10 (C) 7 (D) 1
8．设连通图G中边集E{(ab)(ae)(ac)(be)(ed)(df)(fc)}顶点a出发种深度优先遍历顶点序列（ ）
(A) abedfc (B) acfebd (C) aebdfc (D) aedfcb
9．设输入序列123……n栈作输出序列第元素n输出序列中第i输出元素（ ）
(A) ni (B) n1i (C) n+1i (D) 确定
10 设组初始记录关键字序列(458055404285)第记录关键字45基准趟快速排序结果（ ）
(A) 404245558083 (B) 424045808588
(C) 424045558085 (D) 424045855580
二填空题(20分)
1 设序享栈S[0：n1]中第栈项指针top1初值1第二栈顶指针top2初值n判断享栈满条件____________________
2 图邻接表中序存储结构存储表头结点优点____________________
3 设n阶三角矩阵A果行序三角矩阵中元素（包括角线元素）存放n(n+1)连续存储单元中A[i][j]A[0][0]间_______数元素
4 栈插入删栈栈顶进行进栈元素必定先出栈栈称__________表队列插入删运算分队列两端进行先进队列元素必定先出队列队列称_________表
5 设棵完全二叉树序存储结构中存储数元素ABCDEF该二叉树前序遍历序列___________中序遍历序列___________序遍历序列___________
6 设棵完全二叉树128结点该完全二叉树深度__________________叶子结点
7 设图G存储结构邻接矩阵A表示A中第i行中非零元素数等顶点i________第i列中非零元素数等顶点i__________
8 设组初始记录关键字序列(k1k2……kn)堆i12…n2言满足条件_______________________________
9 面程序段功实现泡排序算法请划线处填正确语句
void bubble(int r[n])
{
for(i1i
for(exchange0j0 j<_____________j++)
if (r[j]>r[j+1]){tempr[j+1]______________r[j]tempexchange1}
if (exchange0) return
}
}
10 面程序段功实现二分查找算法请划线处填正确语句
struct record{int key int others}
int bisearch(struct record r[ ] int k)
{
int low0midhighn1
while(low
________________________________
if(r[mid]keyk) return(mid+1) else if(____________) highmid1else lowmid+1
}
return(0)
}
三应题(32分)
1 设某棵二叉树中序遍历序列DBEAC前序遍历序列ABDEC求出该二叉树序遍历序列
2 设图G（右图示）出该图生成树边集合计算生成树边权值
3 设组初始记录关键字序列(15171822355160)求计算出成功查找时均查找长度
4 设散列表长度8散列函数H(k)k mod 7初始记录关键字序列(25318271368)求分计算出线性探测法链址法作解决突方法均查找长度
四算法设计题(28分)
1． 设计判断两二叉树否相算法
2． 设计两序单链表合排序算法
数结构试卷（六）
选择题(30分)
1． 设组权值集合W{23456}该权值集合构造哈夫曼树中带权路径长度（ ）
(A) 20 (B) 30 (C) 40 (D) 45
2．执行趟快速排序够序列（ ）
(A) [4112344527] 55 [7263]
(B) [45341241] 55 [726327]
(C) [6312344527] 55 [4172]
(D) [12274541] 55 [346372]
3．设条单链表头指针变量head该链表没头结点判空条件（ ）
(A) head0 (B) head>next0
(C) head>nexthead (D) head0
4．时间复杂度受数初始状态影响恒O(nlog2n)（ ）
(A) 堆排序 (B) 泡排序 (C) 希尔排序 (D) 快速排序
5．设二叉树先序遍历序列序遍历序列正相反该二叉树满足条件（ ）
(A) 空结点 (B) 高度等结点数
(C) 结点左孩子 (D) 结点右孩子
6．趟排序结束定够选出元素放终位置（ ）
(A) 堆排序 (B) 泡排序 (C) 快速排序 (D) 希尔排序
7．设某棵三叉树中40结点该三叉树高度（ ）
(A) 3 (B) 4 (C) 5 (D) 6
8．序查找序线性表中链式线性表中时间复杂度（ ）
(A) O(n) (B) O(n2) (C) O(n12) (D) O(1og2n)
9．二路排序时间复杂度（ ）
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
10 深度k完全二叉树中少（ ）结点
(A) 2k11 (B) 2k1 (C) 2k1+1 (D) 2k1
11设指针变量front表示链式队列队头指针指针变量rear表示链式队列队尾指针指针变量s指入队列结点X入队列操作序列（ ）
(A) front>nextsfronts (B) s>nextrearrears
(C) rear>nextsrears (D) s>nextfrontfronts
12设某图中n顶点e条边建立该图邻接表时间复杂度（ ）
(A) O(n+e) (B) O(n2) (C) O(ne) (D) O(n3)
13设某哈夫曼树中199结点该哈夫曼树中（ ）叶子结点
(A) 99 (B) 100 (C) 101 (D) 102
14设二叉排序树n结点二叉排序树查找结点均时间复杂度（ ）
(A) O(n) (B) O(n2) (C) O(nlog2n) (D) O(1og2n)
15设邻接矩阵A表示图G存储结构图G中顶点i入度（ ）
(A) 第i行非0元素数 (B) 第i列非0元素数
(C) 第i行0元素数 (D) 第i列0元素数
二判断题(20分)
1．调次深度优先遍历访问图中顶点（ ）
2．分块查找均查找长度仅索引表长度关块长度关（ ）
3．泡排序初始关键字序列逆序情况执行交换次数（ ）
4．满二叉树定完全二叉树完全二叉树定满二叉树（ ）
5．设棵二叉树先序序列序序列够唯确定出该二叉树形状（ ）
6．层次遍历初始堆序序列（ ）
7．设棵树T转化成二叉树BT二叉树BT中定没右子树（ ）
8．线性表序存储结构链式存储结构更（ ）
9．中序遍历二叉排序树序序列（ ）
10快速排序排序算法中均性种排序（ ）
三填空题(30分)
1．for(i1t1s0i
3．设图G二元组形式表示G （DR）D{12345}R{r}r{<12><24><45><13><32><35>}出该图种拓扑排序序列__________
4．设图G中n顶点该图中顶点度数_________
5．设二叉树中度数0结点数50度数1结点数30该二叉树中总_______结点数
6．设FR分表示序循环队列头指针尾指针判断该循环队列空条件_____________________
7．设二叉树中结点两指针域分lchildrchild判断指针变量p指结点叶子结点条件_____________________________________________
8．简单选择排序直接插入排序算法均时间复杂度___________
9．快速排序算法空间复杂度均情况__________坏情况__________
10散列表中解决突两种方法__________________________
四算法设计题(20分)
１． 设计序序表中实现二分查找算法
２． 设计判断二叉树否二叉排序树算法
３． 链式存储结构设计直接插入排序算法
数结构试卷（七）
选择题(30分)
1．设某图n顶点该图邻接表中（ ）表头结点
(A) 2n (B) n (C) n2 (D) n(n1)
2．设图G中n顶点该图生成树（ ）条边
(A) n (B) n1 (C) 2n (D) 2n1
3．设组初始记录关键字序列(608055404285)第关键字45基准趟快速排序结果（ ）
(A) 404260558085 (B) 424555608580
(C) 424055608085 (D) 424060855580
4．（ ）二叉排序树序序列
(A) 先序遍历 (B) 中序遍历 (C) 序遍历 (D) 层次遍历
5．设左右序1开始完全二叉树进行序编号编号i结点左孩子结点编号（ ）
(A) 2i+1 (B) 2i (C) i2 (D) 2i1
6．程序段si0do {ii+1 ss+i}while(i
7．设带头结点单循环链表头指针变量head判空条件（ ）
(A) head0 (B) head>next0
(C) head>nexthead (D) head0
8．设某棵二叉树高度10该二叉树叶子结点（ ）
(A) 20 (B) 256 (C) 512 (D) 1024
9．设组初始记录关键字序列(131824354750628390115134)利二分法查找关键字90需较关键字数（ ）
(A) 1 (B) 2 (C) 3 (D) 4
10设指针变量top指前链式栈栈顶删栈顶元素操作序列（ ）
(A) toptop+1 (B) toptop1
(C) top>nexttop (D) toptop>next
二判断题(20分)
1．入队列操作入栈操作序存储结构需考虑溢出情况（ ）
2．二叉排序树中插入结点该结点定成叶子结点（ ）
3．设某堆中n结点该堆中插入新结点时间复杂度O(log2n)（ ）
4．完全二叉树中叶子结点两层中出现（ ）
5．哈夫曼树中没度数1结点（ ）
6．连通图进行深度优先遍历访问该图中顶点（ ）
7．先序遍历棵二叉排序树结点序列定序序列（ ）
8．树转化成二叉树该二叉树右子树定空（ ）
9．线性表中元素前驱元素继元素（ ）
10带权图生成树唯（ ）
三填空题(30分)
1 设指针变量p指双链表中结点A指针变量s指插入结点X结点A面插入结点X操作序列_________ps>rightp>right__________s p>right>lefts（设结点中两指针域分leftright）
2 设完全图中n顶点该完全图中________条条设完全图中n顶点该完全图中________条边
3 设关键字序列(KlK2…Kn)筛选法建初始堆必须第______元素开始进行筛选
4 解决散列表突两种方法__________________________________
5 设棵三叉树中50度数0结点21度数2结点该二叉树中度数3结点数______
6 高度h完全二叉树中少________结点________结点
7 设组初始关键字序列(243512271826)第3趟直接插入排序结束结果__________________________________
8 设组初始关键字序列(243512271826)第3趟简单选择排序结束结果__________________________________
9 设棵二叉树前序序列ABC______________种二叉树种序列
10 面程序段功实现趟快速排序请划线处填正确语句
struct record {int keydatatype others}
void quickpass(struct record r[] int s int t int &i)
{
int jt struct record xr[s] is
while(i
while (i
_________________
}
四算法设计题(20分)
1 设计链式结构实现简单选择排序算法
2 设计序存储结构实现求子串算法
3 设计求结点二叉排序树中层次算法
数结构试卷（八）
选择题(30分)
1 字符串长度指（ ）
(A) 串中字符数 (B) 串中字母数
(C) 串中含字符数 (D) 串中数字数
2 建立长度n序单链表时间复杂度（ ）
(A) O(n) (B) O(1) (C) O(n2) (D) O(log2n)
3 两字符串相等充条件（ ）
(A) 两字符串长度相等 (B) 两字符串中应位置字符相等
(C) 时具备(A)(B)两条件 (D) 答案
4 设某散列表长度100散列函数H(k)k PP通常情况选择（ ）
(A) 99 (B) 97 (C) 91 (D) 93
5 二叉排序树中插入关键字值均时间复杂度（ ）
(A) O(n) (B) O(1og2n) (C) O(nlog2n) (D) O(n2)
6 设序序表A[114]中14元素采二分法查找元素A[4]程中较元素序( )
(A) A[1]A[2]A[3]A[4] (B) A[1]A[14]A[7]A[4]
(C) A[7]A[3]A[5]A[4] (D) A[7]A[5] A[3]A[4]
7 设棵完全二叉树中65结点该完全二叉树深度（ ）
(A) 8 (B) 7 (C) 6 (D) 5
8 设棵三叉树中2度数1结点2度数2结点2度数3结点该三叉链权中（ ）度数0结点
(A) 5 (B) 6 (C) 7 (D) 8
9 设图G中边集合E{(ab)(ae)(ac)(be)(ed)(df)(fc)}顶点a出发进行深度优先遍历种顶点序列（ ）
(A) aedfcb (B) acfebd (C) aebcfd (D) aedfbc
10 队列种（ ）线性表
(A) 先进先出 (B) 先进出 (C) 插入 (D) 删
二判断题(20分)
1 果两关键字值等哈希函数值相等称两关键字义词（ ）
2 设初始记录关键字基序快速排序算法时间复杂度O(nlog2n)（ ）
3 分块查找基思想首先索引表中进行查找便确定定关键字存块号然相应块进行序查找（ ）
4 二维数组维数组均特殊线性结构（ ）
5 二叉排序树中插入结点需较次数该二叉树高度（ ）
6 果某图邻接表中第i条单链表空第i顶点出度零（ ）
7 非空双循环链表中结点前驱指针均空（ ）
8 线性表采序存储结构链式存储结构删值X结点时间复杂度均O(n)（ ）
9 图深度优先遍历算法中需设置标志数组便区分图中顶点否访问（ ）
10 稀疏矩阵压缩存储三元组表表示稀疏矩阵中非0元素（ ）
三填空题(30分)
1． 设组初始记录关键字序列(4938659776132750)d4增量趟希尔排序结束结果_____________________________
2． 面程序段功实现二叉排序树中插入新结点请划线处填正确容
typedef struct node{int datastruct node *lchildstruct node *rchild}bitree
void bstinsert(bitree *&tint k)
{
if (t0 ) {____________________________t>datakt>lchildt>rchild0}
else if (t>data>k) bstinsert(t>lchildk)else__________________________
}
3． 设指针变量p指单链表中结点A指针变量s指插入结点X结点A面插入结点X需执行语句序列：s>nextp>next _________________
4． 设指针变量head指双链表中头结点指针变量p指双链表中第结点指针变量p指针变量head间关系p_________head__________（设结点中两指针域分llinkrlink）
5． 设某棵二叉树中序遍历序列ABCD序遍历序列BADC前序遍历序列__________
6． 完全二叉树中第5层少__________结点_________结点
7． 设图中存边
8． 设组初始记录关键字序列(4938659776132750)第4趟直接选择排序结束结果_____________________________
9． 设连通图G中n顶点e条边应生成树___________条边
10． 设组初始记录关键字序列(50162368947073)调整成初始堆需16___________相互交换
四算法设计题(20分)
1 设计链式存储结构统计二叉树中结点数算法
2 设计算法图邻接矩阵转应邻接表算法
数结构试卷（九）
选择题(30分)
1．列程序段时间复杂度（ ）
for(i0 i
2．设序线性表中n数元素删表中第i元素需移动（ ）元素
(A) ni (B) n+l i (C) n1i (D) i
3．设FT1T2T3三棵树组成森林F应二叉树BT1T2T3结点数分N1N2N3二叉树B根结点左子树结点数（ ）
(A) N11 (B) N21 (C) N2+N3 (D) N1+N3
4．利直接插入排序法思想建立序线性表时间复杂度（ ）
(A) O(n) (B) O(nlog2n) (C) O(n2) (D) O(1og2n)
5．设指针变量p指双链表中结点A指针变量s指插入结点X结点A面插入结点X操作序列（ ）
(A) p>rights s>leftp p>right>lefts s>rightp>right
(B) s>leftps>rightp>rightp>rights p>right>lefts
(C) p>rights p>right>lefts s>leftp s>rightp>right
(D) s>leftps>rightp>rightp>right>lefts p>rights
6．列种排序算法中均时间复杂度O(n2)（ ）
(A) 快速排序 (B) 堆排序 (C) 排序 (D) 泡排序
7．设输入序列123…n栈作输出序列中第元素n输出序列中第i输出元素（ ）
(A) ni (B) n1i (C) n+l i (D) 确定
8．设散列表中m存储单元散列函数H(key) key pp选择（ ）
(A) 等m奇数 (B) 等m素数
(C) 等m偶数 (D) 等m合数
9．设棵度数3树中度数3结点数2度数2结点数1度数1结点数2度数0结点数（ ）
(A) 4 (B) 5 (C) 6 (D) 7
10设完全图中n顶点该完全图中（ ）条边
(A) n(n1)2 (B) n(n1) (C) n(n+1)2 (D) (n1)2
11设序表长度n序查找均较次数（ ）
(A) n (B) n2 (C) (n+1)2 (D) (n1)2
12设序表中元素(13182435475062)中利二分法查找值24元素需（ ）次较
(A) 1 (B) 2 (C) 3 (D) 4
13设序线性表长度30分成5块块6元素果采分块查找均查找长度（ ）
(A) 6 (B) 11 (C) 5 (D) 65
14设环图G中边集合E{<12><23><34><14>}列属该图G种拓扑排序序列（ ）
(A) 1234 (B) 2341 (C) 1423 (D) 1243
15设组初始记录关键字序列(34764518265492)组记录关键字生成二叉排序树深度（ ）
(A) 4 (B) 5 (C) 6 (D) 7
二填空题(30分)
1． 设指针p指单链表中结点A指针s指插入结点X结点A前面插入结点X时操作序列：
1) s>next___________2) p>nexts3) tp>data
4) p>data___________5) s>datat
2． 设某棵完全二叉树中100结点该二叉树中______________叶子结点
3． 设某序循环队列中m元素规定队头指针F指队头元素前位置队尾指针R指队尾元素前位置该循环队列中存储_______队列元素
4． 组初始关键字序列（405095201570604510）进行泡排序第趟需进行相邻记录较次数__________整排序程中需进行__________趟排序完成
5． 堆排序快速排序中果均情况排序速度快角度考虑应选择_________排序果节省存储空间角度考虑选择________排序
6． 设组初始记录关键字序列(20124231181428)根记录关键字构造二叉排序树均查找长度_______________________________
7． 设棵二叉树中序遍历序列BDCA序遍历序列DBAC棵二叉树前序序列____________________
8． 设通信电文仅8字母组成字母电文中出现频率分719263232110根频率作权值构造哈夫曼树棵哈夫曼树高度________________
9． 设组记录关键字序列(80703365245648)筛选法建成初始堆_______________________
10． 设图G（右图示）生成树边权值_________________
三判断题(20分)
1． 图邻接表逆邻接表中表结点数定相等( )
2． 链表进行插入删操作时必移动链表中结点( )
3． 子串ABC串AABCABCD中位置2( )
4． 叶子结点某二叉树中序遍历序列结点必该二叉树先序遍历序列中结点( )
5． 希尔排序算法时间复杂度O(n2)( )
6． 邻接矩阵作图存储结构时占存储空间图中顶点数关图中边数关( )
7． 中序遍历棵二叉排序树序序列( )
8． 入栈操作入队列操作链式存储结构实现时需考虑栈溢出情况( )
9． 序表查找指序存储结构进行查找（ ）
10． 堆完全二叉树完全二叉树定堆（ ）
五算法设计题(20分)
1． 设计计算二叉树中结点值算法
2． 设计奇数移偶数前算法
3． 设计判断单链表中元素否递增算法
数结构试卷（十）
选择题(24分)
1．列程序段时间复杂度（ ）
i0s0 while (s
2．设某链表中常操作链表尾部插入删元素选列（ ）存储方式节省运算时间
(A) 单链表 (B) 单循环链表
(C) 双链表 (D) 双循环链表
3．设指针q指单链表中结点A指针p指单链表中结点A继结点B指针s指插入结点X结点A结点B插入结点X操作序列（ ）
(A) s>nextp>nextp>nexts (B) q>nexts s>nextp
(C) p>nexts>nexts>nextp (D) p>nextss>nextq
4．设输入序列123456通栈作输出序列（ ）
(A) 534612 (B) 325641
(C) 312546 (D) 154623
5．设10阶三角矩阵A（包括角线）左右序存储连续55存储单元中数组元素占1字节存储空间A[5][4]址A[0][0]址差（ ）
(A) 10 (B) 19 (C) 28 (D) 55
6．设棵m叉树中N1度数1结点N2度数2结点……Nm度数m结点该树中（ ）叶子结点
(A) (B) (C) (D)
7 二叉排序树中左子树结点值均（ ）根结点值
(A) < (B) > (C) (D)
8 设组权值集合W(153142691617)求根权值集合构造棵哈夫曼树棵哈夫曼树带权路径长度（ ）
(A) 129 (B) 219 (C) 189 (D) 229
9 设n关键字具相Hash函数值线性探测法n关键字映射HASH表中需做（ ）次线性探测
(A) n2 (B) n(n+1) (C) n(n+1)2 (D) n(n1)2
10设某棵二叉树中度数0度数2结点度数0结点数n棵二叉中（ ）结点
(A) 2n (B) n+l (C) 2n1 (D) 2n+l
11设组初始记录关键字长度8（ ）趟插入排序序序列
(A) 6 (B) 7 (C) 8 (D) 9
12设组初始记录关键字序列(QHCYPAMSRDFX)字母升序第趟泡排序结束结果（ ）
(A) FHCDPAMQRSYX
(B) PACSQDFXRHMY
(C) ADCRFQMSYPHX
(D) HCQPAMSRDFXY
二填空题(48分中两题6分)
1 设需5记录关键字进行排序少需较_____________次需较_____________次
2 快速排序算法均时间复杂度____________直接插入排序算法均时间复杂度___________
3 设二叉排序树高度h该树中查找关键字key需较_________次
4 设长度20序表中进行二分查找较次查找成功结点数_________较两次查找成功结点数_________
5 设棵m叉树脂结点数n重链表表示存储结构该树中_________空指针域
6 设指针变量p指单链表中结点A删结点A语句序列：
qp>nextp>dataq>datap>next___________feee(q)
7 数结构逻辑划分三种基类型：________________________________
8 设图G中n顶点e条边邻接矩阵作图存储结构进行深度优先广度优先遍历时时间复杂度_________邻接表作图存储结构进行深度优先广度优先遍历时间复杂度_________
9 设散列表长度8散列函数H(k)k 7线性探测法解决突根组初始关键字序列(81516223032)构造出散列表均查找长度________
10 设组初始关键字序列(38659776132710)第3趟泡排序结束结果_____________________
11 设组初始关键字序列(38659776132710)第3趟简单选择排序结果______________________
12 设图G中边集合E{<12><23><14><45><53><46><65>}该图拓扑序列_________________________
13 面程序段功建立二叉树算法请划线处填正确容
typedef struct node{int datastruct node *lchild________________}bitree
void createbitree(bitree *&bt)
{
scanf(c&ch)
if(ch＇#＇) ___________else
{ bt(bitree*)malloc(sizeof(bitree)) bt>datach ________createbitree(bt>rchild)}
}
14 面程序段功利尾部插入方法建立单链表算法请划线处填正确容
typedef struct node {int data struct node *next} lklist
void lklistcreate(_____________ *&head )
{
for (i1i
p(lklist *)malloc(sizeof(lklist))scanf(d&(p>data))p>next0
if(i1)headqpelse {q>nextp____________}
}
}
三算法设计题(22分)
1． 设计链式存储结构合排序算法
2． 设计二叉排序树查找结点X算法
3． 设关键字序列(k1k2…kn1)堆设计算法关键字序列(k1k2…kn1x)调整堆
数结构试卷（）参考答案
选择题（题2分20分）
1A 2D 3D 4C 5C 6D 7D 8C 9D 10A
二填空题（空1分26分）
1 正确性 易读性 强壮性 高效率
2 O(n)
3 9 3 3
4 1 3 4 X * + 2 Y * 3
5 2n n1 n+1
6 e 2e
7 回路
8 n(n1)2 n(n1)
9 （1240） （ ） （74） （235563）
10 增加1
11 O(log2n) O(nlog2n)
12
三计算题（题6分24分）
1 线性表：（785040603490）
2 邻接矩阵：
邻接表图11示：
图11
3 克鲁斯卡尔算法生成树：
(12)3 (46)4 (13)5 (14)8 (25)10 (47)20
4 见图12
4
4
4
4
4
2
2
2
5
5
2
8
5
2
8
3
4
5
2
8
4
3
图12
四 读算法（题7分14分）
1 （1）查询链表尾结点
（2）第结点链接链表尾部作新尾结点
（3）返回线性表（a2a3…ana1）
2 递序遍历链式存储二叉树
五 法填空（空2分8 分）
true BST>left BST>right
六 编写算法（8分）
int CountX(LNode* HLElemType x)
{ int i0 LNode* pHLi计数器
while(pNULL)
{ if (P>datax) i++
pp>next
}while 出循环时i中值x结点数
return i
}CountX
数结构试卷（二）参考答案
选择题
1D 2B 3C 4A 5A 6C 7B 8C
二填空题
1 构造HASH函数确定解决突方法
2 stacktop++stacks[stacktop]x
3 序
4 O(n2)O(nlog2n)
5 N012N0+N1
6 d2
7 (3138545675805563)
8 (13452)(13245)
三应题
1 (224045488078)(404548802278)
2 q>llinkp q>rlinkp>rlink p>rlink>llinkq p>rlinkq
3 2ASL91*1+2*2+3*4+4*2)259
4 树链式存储结构略二叉树略
5 E{(13)(12)(35)(56)(64)}
6 略
四算法设计题
1 设组初始记录关键字序列（K1K2…Kn）求设计算法够O(n)时间复杂度线性表划分成两部分中左半部分关键字均Ki右半部分关键字均等Ki
void quickpass(int r[] int s int t)
{
int is jt xr[s]
while(i
r[i]x
}
2 设两集合A集合B求设计生成集合CA∩B算法中集合ABC链式存储结构表示
typedef struct node {int data struct node *next}lklist
void intersection(lklist *halklist *hblklist *&hc)
{
lklist *p*q*t
for(phahc0p0pp>next)
{ for(qhbq0qq>next) if (q>datap>data) break
if(q0){ t(lklist *)malloc(sizeof(lklist)) t>datap>datat>nexthc hct}
}
}
数结构试卷（三）参考答案
选择题
1B 2B 3A 4A 5A
6B 7D 8C 9B 10D
第3题分析：首先指针变量q指结点A继结点B然结点B值复制结点A中删结点B
第9题分析：9快速排序排序插入排序必须等整排序结束够求出10数堆排序需初始堆基础进行10次筛选次筛选时间复杂度O(log2n)
二填空题
1 序存储结构链式存储结构
2 9501
3 5
4 出度入度
5 0
6 ed
7 中序
8 7
9 O(1)
10 i22i+1
11 (5167123729473)
12 (1432)
13 j+1hashtable[j]keyk
14 return(t)tt>rchild
第8题分析：二分查找程棵二叉树描述该二叉树称二叉判定树序表进行二分查找时查找长度超二叉判定树高度1+log2n
三计算题
1．
2H(36)36 mod 71 H１(22)(1+1) mod 72 …突
H(15)15 mod 71…突 H2(22)(2+1) mod 73
H１(15)(1+1) mod 72
H(40)40 mod 75
H(63)63 mod 70
H(22)22 mod 71 …突
（1） 0 1 2 3 4 5 6
63
36
15
22
40
（2）ASL
3(894361)10(121818)
(1643)8(9)1012(1818)
1(346)89101218(18)
13(46)8910121818
13 468910121818
四算法设计题
1 设计单链表中删值相余结点算法
typedef int datatype
typedef struct node {datatype data struct node *next}lklist
void delredundant(lklist *&head)
{
lklist *p*q*s
for(pheadp0pp>next)
{
for(qp>nextsqq0 )
if (q>datap>data) {s>nextq>next free(q)qs>next}
else {sqqq>next}
}
}
2 设计求结点x二叉树中双亲结点算法
typedef struct node {datatype data struct node *lchild*rchild} bitree
bitree *q[20] int r0f0flag0
void preorder(bitree *bt char x)
{
if (bt0 && flag0)
if (bt>datax) { flag1 return}
else {r(r+1) 20 q[r]bt preorder(bt>lchildx) preorder(bt>rchildx) }
}
void parent(bitree *btchar x)
{
int i
preorder(btx)
for(if+1 i
if (flag0) printf(not found x＼n)
else if (i
}
数结构试卷（四）参考答案
选择题
1．C 2．D 3．D 4．B 5．C
6．A 7．B 8．A 9．C 10．A
二填空题
1 O(n2)O(nlog2n)
2 p>llink>rlinkp>rlink p>rlink>llinkp>rlink
3 3
4 2k1
5 n2
6 5051
7 m1(RF+M)M
8 n+1ini
9 (191816203022)
10 (161819203222)
11 A[i][j]1
12 等
13 BDCA
14 hashtable[i]0hashtable[k]s
三计算题
1．
2．
(1) ABCDEF BDEFCA(2) ABCDEFGHIJK BDEFCAIJKHG林转换相应二叉树
3．H(4)H(5)0H(3)H(6)H(9)2H(8)3H(2)H(7)6
四算法设计题
1 设单链表中仅三类字符数元素(写字母数字字符)求利原单链表中结点空间设计出三单链表算法单链表包含类字符
typedef char datatype
typedef struct node {datatype data struct node *next}lklist
void split(lklist *headlklist *&halklist *&hblklist *&hc)
{
lklist *p ha0hb0hc0
for(pheadp0phead)
{
headp>next p>next0
if (p>data>＇A＇ && p>data<＇Z＇) {p>nextha hap}
else if (p>data>＇0＇ && p>data<＇9＇) {p>nexthb hbp} else {p>nexthc hcp}
}
}
2 设计链式存储结构交换二叉树中结点左右子树算法
typedef struct node {int data struct node *lchild*rchild} bitree
void swapbitree(bitree *bt)
{
bitree *p
if(bt0) return
swapbitree(bt>lchild) swapbitree(bt>rchild)
pbt>lchild bt>lchildbt>rchild bt>rchildp
}
3 链式存储结构建立棵二叉排序树
#define n 10
typedef struct node{int key struct node *lchild*rchild}bitree
void bstinsert(bitree *&btint key)
{
if (bt0){bt(bitree *)malloc(sizeof(bitree)) bt>keykeybt>lchildbt>rchild0}
else if (bt>key>key) bstinsert(bt>lchildkey) else bstinsert(bt>rchildkey)
}
void createbsttree(bitree *&bt)
{
int i
for(i1i
数结构试卷（五）参考答案
选择题
1．A 2．B 3．A 4．A 5．D
6．B 7．B 8．B 9．C 10．C
二填空题
1 top1+1top2
2 机访问顶点简单链表
3 i(i+1)2+j1
4 FILOFIFO
5 ABDECFDBEAFCDEBFCA
6 864
7 出度入度
8 ki
10 mid(low+high)2r[mid]key>k
三应题
2 DEBCA
3 E{(15)(52)(53)(34)}W10
4 ASL(1*1+2*2+3*4)7177
5 ASL176ASL243
四算法设计题
1 设计判断两二叉树否相算法
typedef struct node {datatype data struct node *lchild*rchild} bitree
int judgebitree(bitree *bt1bitree *bt2)
{
if (bt10 && bt20) return(1)
else if (bt10 || bt20 ||bt1>databt2>data) return(0)
else return(judgebitree(bt1>lchildbt2>lchild)*judgebitree(bt1>rchildbt2>rchild))
}
2 设计两序单链表合排序算法
void mergelklist(lklist *halklist *hblklist *&hc)
{
lklist *shc0
while(ha0 && hb0)
if(ha>data
else {if(s0) hcshb else {s>nexthb shb}hbhb>next}
if(ha0) s>nexthb else s>nextha
}
数结构试卷（六）参考答案
选择题
1．D 2．A 3．A 4．A 5．D
6．D 7．B 8．A 9．C 10．B
11．C 12．A 13．B 14．D 15．B
二判断题
1．错 2． 3． 4． 5．错
6．错 7． 8．错 9． 10．
三填空题
1 O(n)
2 s>nextp>next p>nexts
3 (13245)
4 n1
5 129
6 FR
7 p>lchild0&&p>rchild0
8 O(n2)
9 O(nlog2n) O(n)
10 开放定址法链址法
四算法设计题
1 设计序序表中实现二分查找算法
struct record {int key int others}
int bisearch(struct record r[ ] int k)
{
int low0midhighn1
while(low
mid(low+high)2
if(r[mid]keyk) return(mid+1) else if(r[mid]key>k) highmid1 else lowmid+1
}
return(0)
}
2 设计判断二叉树否二叉排序树算法
int minnum32768flag1
typedef struct node{int key struct node *lchild*rchild}bitree
void inorder(bitree *bt)
{
if (bt0) {inorder(bt>lchild) if(minnum>bt>key)flag0 minnumbt>keyinorder(bt>rchild)}
}
3 链式存储结构设计直接插入排序算法
void straightinsertsort(lklist *&head)
{
lklist *s*p*q int t
if (head0 || head>next0) return
else for(qheadphead>nextp0pq>next)
{
for(sheadsq>nextss>next) if (s>data>p>data) break
if(sq>next)qp
else{q>nextp>next p>nexts>next s>nextp tp>datap>datas>datas>datat}
}
}
数结构试卷（七）参考答案
选择题
1．B 2．B 3．C 4．B 5．B
6．A 7．C 8．C 9．B 10．D
二判断题
1． 2． 3． 4． 5．
6． 7． 8．错 9．错 10．错
三填空题
1 s>leftpp>right
2 n(n1)n(n1)2
3 n2
4 开放定址法链址法
5 14
6 2h12h1
7 (122435271826)
8 (121824273526)
9 5
10 i
四算法设计题
1 设计链式结构实现简单选择排序算法
void simpleselectsorlklist(lklist *&head)
{
lklist *p*q*s int mint
if(head0 ||head>next0) return
for(qhead q0qq>next)
{
minq>data sq
for(pq>next p0pp>next) if(min>p>data){minp>data sp}
if(sq){ts>data s>dataq>data q>datat}
}
}
2 设计序存储结构实现求子串算法
void substring(char s[ ] long start long count char t[ ])
{
long ijlengthstrlen(s)
if (start<1 || start>length) printf(The copy position is wrong)
else if (start+count1>length) printf(Too characters to be copied)
else { for(istart1j0 i
3 设计求结点二叉排序树中层次算法
int lev0
typedef struct node{int key struct node *lchild*rchild}bitree
void level(bitree *btint x)
{
if (bt0)
{lev++ if (bt>keyx) return else if (bt>key>x) level(bt>lchildx) else level(bt>rchildx)}
}
数结构试卷（八）参考答案
选择题
1．C 2．C 3．C 4．B 5．B
6．C 7．B 8．C 9．A 10．A
二判断题
1． 2．错 3． 4．错 5．错
6． 7． 8． 9． 10．
三填空题
1 (4913275076386597)
2 t(bitree *)malloc(sizeof(bitree))bstinsert(t>rchildk)
3 p>nexts
4 head>rlinkp>llink
5 CABD
6 116
7 0
8 (1327385076496597)
9 n1
10 50
四算法设计题
1 设计链式存储结构统计二叉树中结点数算法
void countnode(bitree *btint &count)
{
if(bt0)
{count++ countnode(bt>lchildcount) countnode(bt>rchildcount)}
}
2 设计算法图邻接矩阵转应邻接表算法
typedef struct {int vertex[m] int edge[m][m]}gadjmatrix
typedef struct node1{int infoint adjvertex struct node1 *nextarc}glinklistnode
typedef struct node2{int vertexinfoglinklistnode *firstarc}glinkheadnode
void adjmatrixtoadjlist(gadjmatrix g1[ ]glinkheadnode g2[ ])
{
int ij glinklistnode *p
for(i0i
{
p(glinklistnode *)malloc(sizeof(glinklistnode))p>adjvertexj
p>nextarcg[i]firstarc g[i]firstarcp
p(glinklistnode *)malloc(sizeof(glinklistnode))p>adjvertexi
p>nextarcg[j]firstarc g[j]firstarcp
}
}
数结构试卷（九）参考答案
选择题
1．A 2．A 3．A 4．C 5．D
6．D 7．C 8．B 9．C 10．A
11．C 12．C 13．D 14．A 15．A
二填空题
1 p>nexts>data
2 50
3 m1
4 68
5 快速堆
6 197
7 CBDA
8 6
9 (24653380705648)
10 8
三判断题
1．错 2． 3． 4． 5．错
6．错 7． 8． 9．错 10．
四算法设计题
1． 设计计算二叉树中结点值算法
void sum(bitree *btint &s)
{
if(bt0) {ss+bt>data sum(bt>lchilds) sum(bt>rchilds)}
}
2． 设计奇数移偶数前算法
void quickpass(int r[] int s int t)
{
int isjtxr[s]
while(i
while (i
r[i]x
}
3． 设计判断单链表中元素否递增算法
int isriselk(lklist *head)
{
if(head0||head>next0) return(1)else
for(qheadphead>next p0 qppp>next)if(q>data>p>data) return(0)
return(1)
}
数结构试卷（十）参考答案
选择题
1．A 2．D 3．B 4．B 5．B 6．D
7．A 8．D 9．D 10．C 11．B 12．D
二填空题
1 410
2 O(nlog2n)O(n2)
3 n
4 12
5 n(m1)+1
6 q>next
7 线性结构树型结构图型结构
8 O(n2) O(n+e)
9 83
10 (38132710657697)
11 (10132776659738)
12 124653
13 struct node *rchildbt0createbitree(bt>lchild)
14 lklistqp
三算法设计题
1 设计链式存储结构合排序算法
void mergelklist(lklist *halklist *hblklist *&hc)
{
lklist *shc0
while(ha0 && hb0)
if(ha>data
else {if(s0) hcshb else {s>nexthb shb}hbhb>next}
if(ha0) s>nexthb else s>nextha
}
2 设计二叉排序树查找结点X算法
bitree *bstsearch1(bitree *t int key)
{
bitree *pt
while(p0) if (p>keykey) return(p)else if (p>key>key)pp>lchild else pp>rchild
return(0)
}
3 设关键字序列(k1k2…kn1)堆设计算法关键字序列(k1k2…kn1x)调整堆
void adjustheap(int r[ ]int n)
{
int jnij2tempr[j1]
while (i>1) if (temp>r[i1])break else{r[j1]r[i1] ji ii2}
r[j1]temp
}
文档香网(httpswwwxiangdangnet)户传
《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档