数据结构实验考试题.docx
- 文档编号:11909032
- 上传时间:2023-06-03
- 格式:DOCX
- 页数:26
- 大小:31.31KB
数据结构实验考试题.docx
《数据结构实验考试题.docx》由会员分享,可在线阅读,更多相关《数据结构实验考试题.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构实验考试题
第 1 题 :
报数问题
(时间限制为:
5000毫秒)
5
输入:
标准输入 输出:
标准输出
描述:
n个人围成一个圈,每个人分别标注为1、2、...、n,要求从1号从1开始报数,报到k的人出圈,接着下一个人又从1开始报数,如此循环,直到只剩最后一个人时,该人即为胜利者。
例如当n=10,k=4时,依次出列的人分别为4、8、2、7、3、10,9、1、6、5,则5号位置的人为胜利者。
给定n个人,请你编程计算出最后胜利者标号数。
输入:
输入包含若干个用例,每个用例为接受键盘输入的两个数n(1<=n<=1000000),k(1<=k<=50),分别表示总人数及报到出圈数。
输入为“00“表示输入用例结束。
输出:
每个用例用一行输出最后胜利者的标号数。
输入样例1:
11
104
00
输出样例1:
1
5
第2题 :
成绩统计(顺序线性表)
(时间限制为:
1000毫秒)
描述:
根据输入统计学生的平均分及各科平均分。
输入:
第一行为学生的个数n及课程数m,第二行至m+1行为课程名,接下来为各学生的姓名及成绩,每个学生的信息占两行,第一行为学生的姓名,第二行为m个实数,表示学生各科成绩。
输出:
输出包含2n+2m行,前2n行为学生的平均分,其中第一行为学生姓名,第二行为该生的平均分,后2m行为各课程的平均分,其中第一行为课程名,第二行为对应的平均分。
(保留两位小数)
样例输入:
32
english
computer
zhangshan
87.598
lisi
8078
wangwu
6059
样例输出:
zhangshan
92.75
lisi
79.00
wangwu
59.50
english
75.83
computer
78.33
第 3题 :
合并线性表
(时间限制为:
500毫秒)
描述:
已知两非递减的顺序线性表,要求合并成一个新的非递减顺序线性表。
输入:
输入包含四行,第一行为自然数n,表示第一个非递减顺序线性表的长度,第二行为n个自然数构成的非递减顺序线性表,第三行为自然数m,表示第二个非递减顺序线性表的长度,第四行为m个自然数构成的非递减顺序线性表。
输出:
用一行输出合并后的非递减顺序线性表,各数之间用一个空格隔开。
样例输入:
2
13
3
236
样例输出:
12336
第 4 题 :
链式线性表的插入与删除
(时间限制为:
500毫秒)
描述:
删除链式线性表指定位置的元素。
输入:
第一行为自然数n,表示链式线性表的长度,第二行为n个自然数表示链式线性表各元素值。
第三行为指定删除的位置,第四行为插入的位置及元素值(如果位置不对,则不作操作,插入位置应在删除元素后重新计数)。
输出:
输出删除与插入元素后的链式线性表的所有元素,元素之间用一个空格隔开。
样例输入:
5
12345
3
67
样例输出:
1245
第 5 题 :
数制转换
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
数制转换。
(要求采用栈实现,练习进栈入栈函数的编写)
输入:
输入的第一行包含两个数,n,d
n表示要转换的数的个数
d表示要转换成的进制数
接下来是n个十进制数
输出:
对每一测试用例,用一行输出数制转换后的结果
输入样例:
28
123
213
输出样例:
173
325
第 6题 :
括号匹配的检验
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
采用栈实现,练习进栈入栈函数的编写.
输入:
输入的第一行包含一个数,n
n表示要用例的个数
接下来是n行由括号构成的字符串,包含‘(’、‘)’、‘[’、‘]’。
输出:
对每一测试用例,用一行输出结果,如果匹配,输出“YES”,否则输出“NO”
输入样例:
2
[([][]())]
)[]()
输出样例:
YES
NO
第 7 题 :
行编辑程序
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
如果遇到‘#’,表示后退一格,即前一字符无效,如果遇到@,表示前一单词无效,即退出到空格或所在行头为止。
采用栈实现。
输入:
输入包含若干行,由各种字符构成。
输出:
利用描述规则输出最后的文本内容。
输入样例:
whli##ilr#e(s#*s)
outcha@putchar(*s=#++)
输出样例:
while(*s)
putchar(*s ++)
第 8 题 :
循环队列
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
根据给定的空间构造顺序循环队列,规定队满处理方法为少用一个元素空间。
例如,给定5个元素空间构造循环队列,则只能存放4个元素。
试根据入队及出队操作判断队列最后的元素存放情况,并输出最后队列中的元素值,即完成给定入队及出列操作后一次性全部出队的元素值。
要求采用顺序队列完成。
输入:
输入的第一行为一个自然数n,表示要求构造的顺序循环队列空间数。
第二行为操作次k,接下来k行为出队入队操作,每行各代表一次操作。
入队用in表示,出队用out表示,如果是入队,则in隔一空格后为一整数,表示入队元素值。
输出:
输出完成所有入队出队操作后,一次性出队元素。
用一个空格隔开。
可以假定队在完成所有操作后不为空。
输入样例:
4
7
in1
in2
in5
in6
out
out
in8
输出样例:
58
第 9题 :
对称矩阵存储
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
对于对称矩阵的存储,可以只存储下三角中的元素。
对于给定的对称矩阵,要求进行压缩存储。
输入:
输入包括若干个测试用例,对于每一个测试用例,第一行为一个正整数n(1<=n<=100)表示方阵的维数,接下来为n阶方阵。
每一测试用例最后一行为两个正整数i,j(1<=i,j<=n),表示需求元素在压缩存储的相对位置。
输出:
对每一个测试用例,用两行输出,第一行输出压缩存储结果,以一个空格隔开,第二行输出所求元素在压缩存储中的相对位置。
输入样例:
4
1234
2278
3739
4895
21
3
159
527
973
13
输出样例:
1223734895
2
152973
4
第 10题 :
稀疏矩阵的操作
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
稀疏矩阵可以采用三元组存储。
输入:
输入包含若干个测试用例,每个测试用例的第一行为两个正整数m,n(1<=m,n<=100),表示矩阵的行数和列数,接下来m行,每行n个整数,表示稀疏矩阵的元素,要求输出三元组存储表示。
(0不存储)
输出:
对每一测试用例,输出三元组存储表示。
要求第一行输出矩阵行数、列数和非0元素个数。
输入样例:
56
500040
082000
900010
067000
000000
输出样例:
568
115
154
228
232
319
351
426
437
第 11题 :
三元组的快速转置
(时间限制为:
1000毫秒)
标准输入输出
题目描述:
使用快速转置算法实验三元组的转置。
输入:
输入包含若干个测试用例,每个测试用例第一行为两个正整数m,n表示稀疏矩阵的行数和列数,接下来m行,每行n个整数,表示稀疏矩阵元素。
要求采用三元组存储,并使用普通转置方法实验三元组的逆置。
输出:
对每一测试用例,输出逆置后的三元组。
输入样例:
56
500040
082000
900010
067000
000000
输出样例:
658
115
139
228
246
322
347
514
531
第 12 题 :
模式匹配
(时间限制为:
1000毫秒)
描述:
求一个字符串在另一个字符串中的位置,称为模式匹配,如果匹配成功,则输出第一次匹配成功的位置,否则输出0。
KMP算法是一种高效的模式匹配算法。
要求采用KMP算法完成该题目。
输入:
输入包今含若干个测试用例,每个测试用例占两行,其中第一行为目标字符串,第二行为模式串。
输出:
对每个测试用例,用两行输出,其中第一行输出该用例的模式串的各字符的next值,第二行输出模式串在目标串中第一次匹配成功的位置。
如果匹配不成功,则输出0。
样例输入:
abcdefg
bcd
0000001
0001
110011001100
111
dabcabcabc
abc
样例输出:
011
2
0123
4
012
0
011
2
第 13 题 :
链式二叉树的创建及遍历
(时间限制为:
1000毫秒)
题目2:
链式二叉树的创建及遍历
描述:
树的遍历有先序遍历、中序遍历和后序遍历。
先序遍历的操作定义是先访问根结点,然后访问左子树,最后访问右子树。
中序遍历的操作定义是先访问左子树,然后访问根,最后访问右子树。
后序遍历的操作定义是先访问左子树,然后访问右子树,最后访问根。
对于采用链式存储结构的二叉树操作中,创建二叉树通常采用先序次序方式输入二叉树中的结点的值,空格表示空树。
对于如下的二叉树,我们可以通过如下输入“AE-F--H--”得到(‘-’表示空子树)。
试根据输入创建对应的链式二叉树,并输入其先序、中序和后序遍历结果。
输入:
输入第一行为一个自然数n,表示用例个数
接下来为n行字符串,每行用先序方式输入的要求创建的二叉树结点,’-’表示前一结点的子树为空子树。
输出:
对每个测试用例,分别用三行依次输出其先序、中序和后序遍历结果。
样例输入:
1
abdh---e-i--cf-j--gk---
样例输出:
abdheicfjgk
hdbeiafjckg
hdiebjfkgca
第 14题 :
遍历问题
(时间限制为:
1000毫秒)
描述:
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。
现要求根据输入的中序遍历结果及某一种遍历,要求输出另一种遍历。
输入:
输入包括若干个测试用例,第一行为一个自然数n,表示用例个数,接下来4n行,即每个用例占4行,其中第一行表示第一种遍历方式,第二行为第一种遍历结果,第三行为第二种遍历方式,第4行为第二种遍历结果。
注明:
先序遍历方式用“pre”表示,中序遍历方式用“in”表示,后序遍历方式用“post”表示。
输出:
对每个测试用例,输出相应的另一种遍历方式及结果。
每个用例用一行输出,输出格式为先输出相应的遍历方式,然后一个冒号,再加一个空格,最后输出相应的遍历结果。
样例输入:
1
pre
ABDFCEG
in
BFDAEGC
样例输出:
post:
FDBGECA
第 15题 :
哈夫曼编码
(时间限制为:
1000毫秒)
题目描述:
根据给定的叶结点字符及其对应的权值,进行哈夫曼编码。
输入:
第一行为叶子结点的数目n(1<=n<=100)。
第二行为一个字符串,包含n个字符,每个字符对应一个叶子结点,第三行为每个叶子结点的概率(即权值),要求根据各叶结点构造哈夫曼值,并进行哈夫曼编码。
构造哈夫曼树的原则是先两个最小的,构造一个父结点,其中最小的结点为左孩子,次小的为右孩子,如果两个最小的叶结点相等,则取排在前一个位置的为左孩子。
编码原则是左孩子为0,右孩子为1。
输出:
根据字符出现的次序,每个字符用一行输出其哈夫曼编码。
输入样例:
8
abcdefgh
529781423311
输出样例:
0001
10
1110
1111
110
01
0000
001
第 16 题 :
解码
(时间限制为:
1000毫秒)
描述:
通常要求根据给定的编码本对密文进行解码。
现已给定相应字符的哈夫曼编码,要求根据编码对密文进行解码。
输入:
输入的第一行为出现的字符的个数n,接下来n行为字符及对应字符的哈夫曼编码,相应字符后为冒号和一空格,然后是哈夫曼编码。
然后一个自然数m,表示m行需要进行解码的“0”、“1”符号串。
接下来m行分别为“0”、“1”符号串,即需要解码的串。
输出:
对每一行需要解码的串,进行解码,并输出解码后的结果。
样例输入:
3
a:
00
b:
01
c:
1
2
00000111
0001110001
样例输出:
aabcc
abccab
第 17 题 :
图的广度优先搜索
(时间限制为:
1000毫秒)
描述:
图的广度优先搜索类似于树的按层次遍历,即从某个结点开始,先访问该结点,然后访问该结点的所有邻接点,再依次访问各邻接点的邻接点。
如此进行下去,直到所有的结点都访问为止。
在该题中,假定所有的结点以“A”--“Z”中的若干字符表示,且要求结点的访问顺序要求根据由“A”至“Z”的字典顺序进行访问。
例如有如下图:
如果要求从H开始进行广度优先搜索,则搜索结果为:
H->A->E->K->U.
输入:
输入只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。
数字为0表示不邻接,否则为相应的边的长度。
最后一行为一个字符,表示要求进行广度优先搜索的起始顶点。
输出:
用一行输出广度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。
要求同一顶点的邻接点的访问顺序按“A”---“Z”的字典顺序。
样例输入:
5
HUEAK
00230
00074
20000
37001
04010
H
样例输出:
HAEKU
第 18 题 :
图的深度优先搜索
(时间限制为:
1000毫秒)
描述:
图的深度优先搜索类似于树的先根遍历,是树的先根遍历的推广。
即从某个结点开始,先访问该结点,然后深度访问该结点的第一棵子树,依次为第二顶子树。
如此进行下去,直到所有的结点都访问为止。
在该题中,假定所有的结点以“A”至“Z”中的若干字符表示,且要求结点的访问顺序根据“A”至“Z”的字典顺序进行访问。
例如有如下图:
如果要求从H开始进行深度优先搜索,则搜索结果为:
H->A->K->U->E.
输入:
输入只包含一个测试用例,第一行为一个自然数n,表示顶点的个数,第二行为n个大写字母构成的字符串,表示顶点,接下来是为一个n*n大小的矩阵,表示图的邻接关系。
数字为0表示不邻接,否则为相应的边的长度。
最后一行为一个字符,表示要求进行深度优先搜索的起始顶点。
输出:
用一行输出深度优先搜索结果,起始点为给定的顶点,各顶点之间用一个空格隔开。
要求同一层顶点的邻接点的访问顺序按“A”至“Z”的字典顺序。
样例输入:
5
HUEAK
00230
00074
20000
37001
04010
H
样例输出:
HAKUE
第 19题 :
拓扑排序
(时间限制为:
1000毫秒)
描述:
学校领导在大学生培养计划的制订中,涉及到课程的安排问题,由于课程较多,现在要求编程高手的你帮忙。
假定课程之间的先修关系已确定,现在要求你根据先修关系,通过编程确定各门课程的先后关系,并生成一张课程先后安排顺序表,以帮助学校设置各年度课程。
输入:
输入只包括一个测试用例,第一行为一个自然数n,表示课程数量,第二行为n个单词,分别表示n门课程,一个单词表示一门课程,单词全为小写状态,各单词之间用一个空格隔开。
接下来为n*n行0和1构成的矩阵,表示各门课程之间的先修关系。
假设i行j列为1,表示第i课程为第j课程的先修课。
否则表示不存在先修关系。
输出
要求根据各课程之间的先修关系,用一行输出课程的拓扑排序结果。
注意:
如果两门课程的访问顺序相同,则根据课程名的字典顺序进行访问。
样例输入
4
dbccomputermath
0000
1010
0000
0010
样例输出:
cdbmathcomputer
第 20题 :
顺序查找
(时间限制为:
100毫秒)
标准输入输出
题目描述:
实现顺序查找。
要求查找给定的值在数据表中相应的存储位置。
本题目假定所有的元素互不相同,并且要求查找顺序为从后往前查询。
输入:
输入包含若干个测试用例,第一行为测试用例个数k。
每个测试用例占3行,其中第一行为元素个数n,第二行为n个元素值,即数据表中的元素,第三行为需要查找的元素。
输出:
对每一测试用例,分别用一行输出两个值,分别表示相应的位置和查找次数,用空格隔开。
如果查找不成功,则位置表0表示。
输入样例:
1
5
24179
7
输出样例:
42
第 21 题 :
折半查找
(时间限制为:
100毫秒)
标准输入输出
题目描述:
实现折半查找。
要求查找给定的值在数据表中相应的存储位置。
本题目假定输入元素均按非降序输入。
输入:
输入包含若干个测试用例,第一行为测试用例个数k。
每个测试用例占3行,其中第一行为元素个数n,第二行为n个元素值,即数据表中的元素,第三行为需要查找的元素。
输出:
对每一测试用例,分别用一行输出两个值,分别表示相应的位置和查找次数,用空格隔开。
如果查找不成功,则位置表0表示。
输入样例:
1
5
12479
4
输出样例:
31
第 22 题 :
直接插入排序
(时间限制为:
100毫秒)
标准输入输出
题目描述:
利用直接插入排序算法实现线性表的排序。
要求输出第k趟排序的结果。
例如原来线性表为:
26,12,25,4,36,15,21,第一趟直接排序排序结果为:
12,26,25,4,36,15,21,第二趟直接插入排序结果为:
12,25,26,4,36,15,21。
输入:
输入包含若干个测试用例,第一行为测试用例个数。
每个测试用例占3行,第一个为元素个数n(1<=n<=1000),第二行为n个元素值(整数),即需要排序的元素个数,第三行为k(1<=k<=n-1),即要求的第k趟排序结果。
输出:
对每一测试用例,用一行输出第k趟排序结果,用空格隔开。
输入样例:
1
5
24197
3
输出样例:
12497
第 23 题 :
希尔排序
(时间限制为:
100毫秒)
标准输入输出
题目描述:
利用希尔排序算法实现线性表的排序。
希尔排序是根据给定的增量序列将线性表分隔成某个“增量”的记录组成一个子序例,在子序列中采用直接插入排序完成。
输入:
输入包含若干个测试用例,第一行为测试用例个数。
每个测试用例占4行,第一行为元素个数n(1<=n<=1000),第二行为n个元素值(整数),即需要排序的元素个数,第三行增量序列中增量个数m,第四行为m个增量,可以假定最后一个增量为1。
输出:
对每一测试用例,用m行输出各增量进行希尔排序结果,用空格隔开。
输入样例:
1
10
4938659776132749554
3
531
输出样例:
1327495544938659776
1344938274955659776
4132738494955657697
第 24 题 :
顺序线性表操作
(时间限制为:
500毫秒)
描述
请你定义一个线性表,可以对表进行“在某个位置之前插入一个元素”、“删除某个位置的元素”、“清除所有元素”、“获取某个位置的元素”等操作。
键盘输入一些命令,可以执行上述操作。
本题中,线性表元素为整数,线性表的第一个元素位置为1。
线性表的最大长度为1000。
输入
各个命令以及相关数据,它们对应的格式如下:
在某个位置之前插入操作:
insert,接下来的一行是插入的组数n,下面是n行数据,每行数据有两个值,分别代表位置与插入的元素值
清除线性表:
clear
获取某个位置的元素:
getelem,接下来一行是需要获取的元素位置
删除某个位置的元素:
delete,接下来一行是被删除的元素位置
当输入的命令为exit时,程序结束
输出
当输入的命令为getelem时,请输出获取的元素值,
当输入的命令是delete时,请输出被删除的那个元素值
注意,所有的元素均占一行
样例输入
insert
2
11
22
delete
1
clear
insert
2
13
24
getelem
2
exit
样例输出
1
4
提示
要求采用顺序线性表实现
第 25 题 :
链式线性表的操作
(时间限制为:
500毫秒)
描述
请你定义一个链式线性表,可以对表进行“在某个位置之前插入一个元素”、“删除某个位置的元素”、“清除所有元素”、“获取某个位置的元素”、“修改某个位置的元素”等操作。
键盘输入一些命令,可以执行上述操作。
本题中,线性表元素为整数。
输入
各个命令以及相关数据,它们对应的格式如下:
在某个位置之前插入操作:
insert,接下来的一行是插入的组数n,下面是n行数据,每行数据有两个值,分别代表位置与插入的元素值
清除线性表:
clear
获取某个位置的元素:
getelem,接下来一行是需要获取的元素位置
删除某个位置的元素:
delete,接下来一行是被删除的元素位置
修改某个位置的元素:
update,接下来一行是被修改的元素位置及值
打印所有元素:
getallelem
当输入的命令为exit时,程序结束
输出
当输入的命令为getelem时,请输出获取的元素值,
当输入的命令是delete时,请输出被删除的那个元素值
当输入的命令是getallelem时,请输出所有元素值
注意,每一个命令对应一行输出,如果一行有多个元素,则元素之间用空格隔开。
样例输入
insert
2
11
22
update
25
getallelem
delete
1
getallelem
clear
insert
2
13
24
getelem
2
exit
样例输出
15
1
5
4
提示
要求使用链式存储结构,可以采用单链表、双链表或循环链表实现。
.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 考试题