数据结构作业.doc

线性表 Time Limit:1000MS Memory Limit:30000KBTotal Submit:854 Accepted:172 Description 实现一个线性表:参照课本P5上的sq_delete函数，对一个n不超过210的线性表进行删除操作 Input 第一行有一个整数n，表示线性表的大小，第二行有n个整数，分别是list1，list2.listn。第三行有一个整数q，表示q次删除操作，接下来q行，每行有一个整数k，表示删除线性表中第k个元素。 Output 对于每次删除操作输出一行，如果k不合法，输出 -1, 否则输出删除的元素。 Sample Input 53 2 1 5 43552 Sample Output 4-12Source 06级数据结构课程上机实践 环形队列 Time Limit:1000MS Memory Limit:30000KBTotal Submit:517 Accepted:162 Description 实现环形队列(MAXN不超过100001)，要求能够进行进队出队操作，参考课本P15页例程。 Input 初始时，队列为空。第一行有一个整数q，表示操作的个数，接下来的q行里，每行格式如下:enqueue xxx, 表示把整数xxx进队;dequeue, 表示出队. Output 对于每次出队操作，打印出队元素，如出队不成功，打印-1. Sample Input 3enqueue 1234567890dequeuedequeue Sample Output 1234567890-1Source 06级数据结构课程上机实践 铁路调度 Time Limit:1000MS Memory Limit:30000KBTotal Submit:223 Accepted:64 Description 如下图，表示一个铁路调度站，为栈式结构，所有的火车必须右端进去并且从左端离开，现在有n(0 n 10)列火车要进行调度，按照进入的顺序从1到n进行编号。对于一个给定的一个出站序列，你需要判断是否是一个合法的序列。例如： n = 4, 出站序列为 4321， 这是合法的，1234依次进栈，再依次出栈得到4321Input 输入第一行是一个整数k，表示有k个序列要求你进行判断，接下来2到k+1里每行有一个整数n和一个数字序列a1.an. Output 输出只有k行，对于第i个序列如果它是一个合法的出站序列，输出yes,否则输出no(不包括括号) Sample Input 34 43214 34213 312Sample Output yesyesnoSource 06级数据结构课程上机实践 Link-list Time Limit:1000MS Memory Limit:30000KBTotal Submit:475 Accepted:126 Description 实现线性链表的创建于插入(插入到已有元素之后)。 Input 第一行有一个整数n( 0 n = 64 ),为初始链表的元素个数, 第二行有n个整数，依次为链表中的元素。第三行有一个整数q，表示插入操作的个数。接下来q行里每行内有两个整数，第一个整数为链表中已经出现的元素，第二整数是要被插入的元素， 并且数据保证链表中始终不会出现相同的元素。Output 对于每次操作，将链表从头到尾打印出来，整数间用空格隔开。Sample Input 23 523 45 6Sample Output 3 4 53 4 5 6Source 06级数据结构课程上机实践 字符串匹配 Time Limit:1000MS Memory Limit:30000KBTotal Submit:194 Accepted:11 Description 给你2个字符串(可能包括数字以及标点)，长度=50124，请你求出最长的连续的公共子序列。 Input 输入有2个字符串A，B, 各占一行。 Output 输出字符串A和B的最长连续公共子序列的长度L。 Sample Input aaaabaSample Output 1Source 06级数据结构课程上机实践 string Time Limit:1000MS Memory Limit:30000KBTotal Submit:437 Accepted:97 Description 实现字符串的strcat, strsub, strequ操作，参照课本P62例程 Input 第一行有一个字符串，为被操作字符串的初值(可能为空串)，接下来有一个整数q，表示操作的个数，接下来q行每行为下列情况的一种:1. strcat ssss 表示把字符串ssss连接到被操作的字符串之后;2. strsub b e 表示求被操作字符串的子串(Sb.Sb+e-1);3. strequ ssss 判断被操作字符串与ssss是否相等(每次strcat操作之后，被操作的字符串被永久的改变。)被操作字符串最长长度不超过1024 Output 对于情况1,输出一行，为连接ssss之后的被操作字符串。(数据保证不会操作fail)对于情况2,输出一行，输出子串，如失败输出fail(不包含引号)对于情况3,输出一行，如果相等，输出yes，否则输出no; Sample Input abc4strcat destrsub 1 4strsub 0 10000strequ abcd Sample Output abcdebcdefailnoSource 06级数据结构课程上机实践 选择排序 Time Limit:1000MS Memory Limit:30000KBTotal Submit:319 Accepted:144 Description 实现选择排序 Input 第一行一个整数n(n 1024)，第二行有n个整数。 Output 输出一行，为排序后的n个整数，以空格隔开 Sample Input 99 8 7 6 5 4 3 2 1 Sample Output 1 2 3 4 5 6 7 8 9Source 06级数据结构课程上机实践 快速排序 Time Limit:1000MS Memory Limit:30000KBTotal Submit:334 Accepted:139 Description 实现快速排序 Input 每个case有两行，第一行一个整数n(n = 20000)，第二行有n个整数。处理到文件结尾 Output 输出一行，为排序后的n个整数，以空格隔开 Sample Input 99 8 7 6 5 4 3 2 1 Sample Output 1 2 3 4 5 6 7 8 9 Source 06级数据结构课程上机实践 冒泡排序 Time Limit:1000MS Memory Limit:30000KBTotal Submit:221 Accepted:131 Description 实现冒泡排序 Input 每个case有两行，第一行一个整数n(n = 1024)，第二行有n个整数。处理到文件结尾 Output 输出一行，为排序后的n个整数，以空格隔开 Sample Input 99 8 7 6 5 4 3 2 1Sample Output 1 2 3 4 5 6 7 8 9 Source 06级数据结构课程上机实践 询问 Time Limit:3000MS Memory Limit:30000KBTotal Submit:541 Accepted:131 Description 对于n个整数，找出第1小，第2小.第k小的整数 Input 输入第一行有2个整数，n(0 n = 1000000) 和 k (0 k 1024, k = n ), 第二行有n个空格隔开的整数。 Output 按顺序输出第1小，第2小.第k小的整数，两个数之间用空格隔开。 Sample Input 4 22 2 1 3 Sample Output 1 2 Source 06级数据结构课程上机实践 稀疏矩阵三元组转化 Time Limit:3000MS Memory Limit:30000KBTotal Submit:370 Accepted:88 Description 利用原稀疏矩阵的三元数组a，求转置矩阵的三元数组b，并将其规格化，即按行号递增，若行号相同则按照列号递增的顺序。参照课本P93.94例程 Input 第一行有三个整数m,n,c表示矩阵的行数和列数以及原三元组a的个数，(m,n = 1000)接下来c行里每行有三个整数分别表示三元组的行，列以及元素值处理到文件结尾处 Output 输出三元数组b，每个三元组一行。 Sample Input 2 2 20 0 11 0 2Sample Output 0 0 10 1 2Source 06级数据结构课程上机实践 树的遍历 Time Limit:1000MS Memory Limit:30000KBTotal Submit:61 Accepted:35 Description 根据树的层号表示建树，打印树的后序遍历序列。层号表示法参见课本P117 A / B C / D E可以表示为 (0,A) (1,B) (2,D) (2,E) (1,C) Input 第一行为一个整数n,表示结点个数(n=26), 结点用大写子母表示，接下来一行里有n个二元组(k,L)(中间不含空格，组间有空格隔开), 表示层号和结点标识。 Output 输出只有一行，为树的后序遍历序列(不一定是二叉树) Sample Input 5(0,A) (1,B) (2,D) (2,E) (1,C) Sample Output DEBCA Source 06级数据结构课程上机实践 二叉树的深度 Time Limit:1000MS Memory Limit:30000KBTotal Submit:46 Accepted:31 Description 给定一个有根二叉树，规定连接两个节点的每条边长度是1，定义树的深度为根到叶子节点距离的最大值。 Input 第一行是整数n(0 n = 10000)节点用1.n表示，接下来有n行，分别表示节点1.n的孩子的情况每一行有个整数lc, rc，分别表示结点i的左右儿子，为0表示，该孩子为空。 Output 输出一行，一个整数，为树的深度. Sample Input 32 30 00 0 Sample Output 2 Source 06级数据结构课程上机实践 树重建 Time Limit:1000MS Memory Limit:30000KBTotal Submit:30 Accepted:22 Description 利用树的前序和中序遍历，找出树的后序遍历。Input 输入只有一行，包含两个分开的字符串。分别表示一个树的前序和中序遍历。字符串有不同的大写字母构成。处理到文件结束。 Output 对每一组测试数据，输出它的后序遍历。Sample Input DBACEGF ABCDEFG Sample Output ACBFGED Source 06级数据结构课程上机实践 完全二叉树？ Time Limit:1000MS Memory Limit:30000KBTotal Submit:60 Accepted:31 Description 二叉树T中，如果非叶子结点都有两棵非空子树，那么称二叉树T是一棵完全二叉树。现在根据边的连接情况判断一棵树是否是完全二叉树。 Input 第一行有2个整数n(0 n 1024)和r(1=r=n), 表示结点数和树根，接下来n-1行每行有2个整数a,b (1 = a,b = n)表示a结点和b结点有一条边相连(数据保证是一棵树而不是一座森林) Output 如果是完全二叉树 输出yes 否则输出no Sample Input 5 11 23 14 22 5 Sample Output yes Source 06级数据结构课程上机实践 Huffman树 Time Limit:1000MS Memory Limit:30000KBTotal Submit:18 Accepted:12 Description 我们大家都学习了Huffman算法，给出每一个点的权值，它可以求出一个具有最小加权外部路径的二叉树，也就是使造价 W(k1)*Lk1 + . + W(kn)*Lkn (树枝长度为根结点到叶结点边数)最小的二叉树。现在由你来完成这项工作。 Input 输入一共有2行。第一行为一个整数n，它表示点的个数。第二行有n(1 n = 1000)个数，第i（1 = i = n）个数表示第i个点的权值 Output 输出为一个数，为最小造价值。 Sample Input 510 5 20 10 18 Sample Output 141 Source 06级数据结构课程上机实践 连通？ Time Limit:1000MS Memory Limit:65536KBTotal Submit:48 Accepted:21 Description 如果无向图G每对顶点v和w都有从v到w的路径，那么称无向图G是连通的。现在给定一张无向图,判断它是否是连通的。 Input 第一行有2个整数n和m(0 n,m 1000000), 接下来m行每行有2个整数u,v (1=u,v=n)表示u和v有边连接。 Output 如果无向图是连通的输出yes，否则输出no Sample Input 4 61 22 31 34 12 44 3Sample Output yesHint图的遍历算法 Source 06级数据结构课程上机实践 最短路 Time Limit:1000MS Memory Limit:30000KBTotal Submit:13 Accepted:4 Description 求出有n(1 n 600)个结点有向图中，结点1到结点n的最短路径。 Input 第一行有2个整数n和m(0 m = n*(n-1)/2)，接下来m行每行有三个整数u,v,w结点u到v之间有一条权为w的边(w1000000)。Output 输出结点1到结点n之间的最短路径，如果1到n之间不存在路径，输出 -1。 Sample Input 3 31 2 102 3 151 3 30 Sample Output 25 Source 06级数据结构课程上机实践 最短路2 Time Lim