数据结构OJ

发表于2023-01-13|更新于2023-06-09

|字数总计:31.6k|阅读时长:128分钟

Date(类与对象)

题目描述:

下面是一个日期类的定义，请在类外实现其所有的方法，并在主函数中生成对象测试之。

注意，在判断明天日期时，要加入跨月、跨年、闰年的判断

例如9.月30日的明天是10月1日，12月31日的明天是第二年的1月1日

2月28日的明天要区分是否闰年，闰年则是2月29日，非闰年则是3月1日

输入:

测试数据的组数t
第一组测试数据的年月日
……….
要求第一个日期的年月日初始化采用构造函数，第二个日期的年月日初始化采用setDate方法，第三个日期又采用构造函数，第四个日期又采用setDate方法，以此类推。

输出:

输出今天的日期
输出明天的日期

输入样例一

输出样例一

Today is 2012/01/03
Tomorrow is 2012/01/04
Today is 2012/02/28
Tomorrow is 2012/02/29
Today is 2012/03/31
Tomorrow is 2012/04/01
Today is 2012/04/30
Tomorrow is 2012/05/01

参考答案:

#include <iostream>
#include <iomanip>

using namespace std;

class Date {
private:
    int year, month, day;
public:
    Date() {
        year = month = day = -1;
    }

    Date(int y, int m, int d) {
        year = y;
        month = m;
        day = d;
    }

    int getYear() {
        return year;
    }

    int getMonth() {
        return month;
    }

    int getDay() {
        return day;
    }

    void setDate(int y, int m, int d) {
        year = y;
        month = m;
        day = d;
    }

    void print() {
        cout << "Today is " << year << "/";
        cout << setw(2) << setfill('0') << month << "/";
        cout << setw(2) << setfill('0') << day << endl;
        addOneDay();
        cout << "Tomorrow is " << year << "/";
        cout << setw(2) << setfill('0') << month << "/";
        cout << setw(2) << setfill('0') << day << endl;
    }

    void addOneDay() {
        int months[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        if ((year % 100 != 0 && year % 4 == 0) || (year % 400 == 0)) {
            months[1] = 29;
        }
        day += 1;
        if (months[month - 1] < day) {
            day -= months[month - 1];
            month += 1;
        }
        if (month > 12) {
            year += 1;
            month -= 12;
        }
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int year, month, day;
        cin >> year >> month >> day;
        Date date;
        if (t % 2 != 0) {
            date = *new Date(year, month, day);
        } else {
            date.setDate(year, month, day);
        }
        date.print();
    }
    return 0;
}

DS串应用–KMP算法

题目描述:

学习KMP算法，给出主串和模式串，求模式串在主串的位置

算法框架如下，仅供参考

输入:

第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串
以此类推

输出:

第一行输出第1个实例的模式串的next值
第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0
以此类推

输入样例一

3
qwertyuiop
tyu
aabbccdd
ccc
aaaabababac
abac

输出样例一

参考答案:

DS串应用—最长重复子串

题目描述:

求串的最长重复子串长度（子串不重叠）。例如：abcaefabcabc的最长重复子串是串abca，长度为4。

输入:

测试次数t

t个测试串

输出:

对每个测试串，输出最长重复子串长度，若没有重复子串，输出-1.

输入样例一

3
abcaefabcabc
0szu0123szu1
szuabcefg

输出样例一

4
3
-1

参考答案:

DS二叉排序树之创建和插入

题目描述:

给出一个数据序列，建立二叉排序树，并实现插入功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入:

第一行输入t，表示有t个数据序列
第二行输入n，表示首个序列包含n个数据
第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第四行输入m，表示要插入m个数据
从第五行起，输入m行，每行一个要插入的数据，都是自然数且和前面的数据不等
以此类推输入下一个示例

输出:

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到
从第二行起，输出插入第m个数据后的有序序列，输出m行
以此类推输出下一个示例的结果

输入样例一

1
6
22 33 55 66 11 44
3
77
50
10

输出样例一

11 22 33 44 55 66 
11 22 33 44 55 66 77 
11 22 33 44 50 55 66 77 
10 11 22 33 44 50 55 66 77

参考答案:

DS二叉排序树之删除

题目描述:

给出一个数据序列，建立二叉排序树，并实现删除功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入:

第一行输入t，表示有t个数据序列
第二行输入n，表示首个序列包含n个数据
第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第四行输入m，表示要删除m个数据
从第五行起，输入m行，每行一个要删除的数据，都是自然数
以此类推输入下一个示例

输出:

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到
从第二行起，输出删除第m个数据后的有序序列，输出m行
以此类推输出下一个示例的结果

输入样例一

1
6
22 33 55 66 11 44
3
66
22
77

输出样例一

11 22 33 44 55 66 
11 22 33 44 55 
11 33 44 55 
11 33 44 55

参考答案:

DS二叉排序树之查找

题目描述:

给出一个数据序列，建立二叉排序树，并实现查找功能

对二叉排序树进行中序遍历，可以得到有序的数据序列

输入:

第一行输入t，表示有t个数据序列
第二行输入n，表示首个序列包含n个数据
第三行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第四行输入m，表示要查找m个数据
从第五行起，输入m行，每行一个要查找的数据，都是自然数
以此类推输入下一个示例

输出:

第一行输出有序的数据序列，对二叉排序树进行中序遍历可以得到
从第二行起，输出查找结果，如果查找成功输出查找次数，如果查找失败输出-1
以此类推输出下一个示例的结果

输入样例一

1
6
22 33 55 66 11 44
7
11
22
33
44
55
66
77

输出样例一

11 22 33 44 55 66 
2
1
2
4
3
4
-1

参考答案:

DS二叉树–二叉树构建与遍历（含代码框架）

题目描述:

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构，并输出该二叉树的先序遍历、中序遍历和后序遍历结果

本题目的代码框架参考如下

三种遍历的代码框架

主函数如下：

输入:

第一行输入一个整数t，表示有t个二叉树
第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出:

输出每个二叉树的先序遍历、中序遍历和后序遍历结果

输入样例一

2
AB0C00D00
AB00C00

输出样例一

ABCD
BCAD
CBDA
ABC
BAC
BCA

参考答案:

DS二叉树–后序遍历非递归算法

题目描述:

求一颗树的后序遍历的非递归算法

要求：必须是非递归算法，使用堆栈对象来实现

建树方法采用“先序遍历+空树用0表示”的方法

算法流程：

输入:

第一行输入一个整数t，表示有t个测试数据
第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出:

逐行输出每个二叉树的后序遍历结果

输入样例一

3
AB0C00D00
ABC00D00EF000
ABCD0000E0F00

输出样例一

CBDA
CDBFEA
DCBFEA

参考答案:

DS二叉树–基于数组存储的构建

题目描述:

任意二叉树可以根据完全二叉树性质保存在一个数组中。已知二叉树的数组存储，用程序构建该二叉树。

提示：用递归方法或非递归都可以

递归方法的代码框架如下：

输入:

第一行输入一个整数t，表示有t个测试数据
第二行起输入二叉树的数组存储结果，空树用字符‘0’表示，输入t行
数组的数据由大写字母和0表示

输出:

逐行输出每个二叉树的先序结果

输入样例一

3
ABC0D
ABCDEF000G
ABEC0F0D0

输出样例一

ABDC
ABDEGCF
ABCDEF

参考答案:

DS二叉树–层次遍历

题目描述:

层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。

建树方法采用“先序遍历+空树用0表示”的方法

要求：采用队列对象实现，函数框架如下：

输入:

第一行输入一个整数t，表示有t个测试数据
第二行起输入二叉树先序遍历的结果，空树用字符‘0’表示，输入t行

输出:

逐行输出每个二叉树的层次遍历结果

输入样例一

2
AB0C00D00
ABCD00E000FG00H0I00

输出样例一

1
2
3

ABDC
ABFCGHDEI

参考答案:

DS二叉树–赫夫曼树的构建与编码（含代码框架）

题目描述:

给定n个权值，根据这些权值构造huffman树，并进行huffman编码

参考课本算法，注意数组访问是从位置1开始

要求：赫夫曼的构建中，默认左孩子权值不大于右孩子权值

代码框架参考如下：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
 
const int MaxW = 9999999;  // 假设结点权值不超过9999999
// 定义huffman树结点类
class HuffNode
{
public:
    int weight;     // 权值
    int parent;     // 父结点下标
    int leftchild;  // 左孩子下标
    int rightchild; // 右孩子下标
};
// 定义赫夫曼树类
class HuffMan
{
private:
    void MakeTree();    // 建树，私有函数，被公有函数调用
    void SelectMin(int pos, int *s1, int*s2);  // 从 1 到 pos 的位置找出权值最小的两个结点，把结点下标存在 s1 和 s2 中
public:
    int len;    // 结点数量
    int lnum;   // 叶子数量
    HuffNode *huffTree; // 赫夫曼树，用数组表示
    string *huffCode;   // 每个字符对应的赫夫曼编码
    void MakeTree(int n, int wt[]); // 公有函数，被主函数main调用
    void Coding();  // 公有函数，被主函数main调用
    void Destroy();
};
// 构建huffman树
void HuffMan::MakeTree(int n, int wt[])
{
    // 参数是叶子结点数量和叶子权值
    // 公有函数，对外接口
    int i;
    lnum = n;
    len = 2 * n - 1;
    huffTree = new HuffNode[2 * n];
    huffCode = new string[lnum + 1];    // 位置从 1 开始计算
    // huffCode实质是个二维字符数组，第 i 行表示第 i 个字符对应的编码
    // 赫夫曼树huffTree初始化
    for(i = 1; i <= n; i ++)
        huffTree[i].weight = wt[i - 1]; // 第0号不用，从1开始编号
    for(i = 1; i <= len; i ++)
    {
        if(i > n) huffTree[i].weight = 0;  // 前n个结点是叶子，已经设置
        huffTree[i].parent = 0;
        huffTree[i].leftchild = 0;
        huffTree[i].rightchild = 0;
    }
    MakeTree();  // 调用私有函数建树
}
void HuffMan::SelectMin(int pos, int *s1, int *s2)
{
    // 找出最小的两个权值的下标
    // 函数采用地址传递的方法，找出两个下标保存在 s1 和 s2 中
    int w1, w2, i;
    w1 = w2 = MaxW;  // 初始化w1和w2为最大值，在比较中会被实际的权值替换
    *s1 = *s2 = 0;
    for(i = 1; i <= pos; i ++)
    {
        // 比较过程如下：
        // 如果第 i 个结点的权值小于 w1，且第 i 个结点是未选择的结点，提示：如果第 i 结点未选择，它父亲为 0
        // 把第 w1 和 s1 保存到 w2 和 s2，即原来的第一最小值变成第二最小值
        // 把第 i 结点的权值和下标保存到 w1 和 s1，作为第一最小值
        // 否则，如果第 i 结点的权值小于 w2，且第 i 结点是未选择的结点
        // 把第 i 结点的权值和下标保存到 w2 和 s2，作为第二最小值
    }
}
void HuffMan::MakeTree()
{
    // 私有函数，被公有函数调用
    int i, s1, s2;
    for(i = lnum + 1; i <= len; i ++)
    {
        SelectMin(i - 1, &s1, &s2);  // 找出两个最小权值的下标放入 s1 和 s2 中
        // 将找出的两棵权值最小的子树合并为一棵子树，过程包括
        // 结点 s1 和结点 s2 的父亲设为 i
        // 结点 i 的左右孩子分别设为 s1 和 s2
        // 结点 i 的权值等于 s1 和 s2 的权值和
    }
}
// 销毁赫夫曼树
void HuffMan::Destroy()
{
    len  = 0;
    lnum = 0;
    delete []huffTree;
    delete []huffCode;
}
// 赫夫曼编码
void HuffMan::Coding()
{
    char *cd;
    int i, c, f, start;
    // 求 n 个结点的赫夫曼编码
    cd = new char[lnum];    // 分配求编码的工作空间
    cd[lnum - 1] = '\0';    // 编码结束符
    for(i = 1; i <= lnum; ++ i)
    {
        // 逐个字符求赫夫曼编码
        start = lnum - 1;   // 编码结束符位置
        // 参考课本P147算法6.12 HuffmanCoding代码
        huffCode[i].assign(&cd[start]); // 把cd中从start到末尾的编码复制到huffCode中
    }
    delete []cd;    // 释放工作空间
}
// 主函数
int main()
{
    int t, n, i, j;
    int wt[800];
    HuffMan myHuff;
    cin >> t;
    for(i = 0; i < t; i ++)
    {
        cin >> n;
        for(j = 0; j < n; j ++)
        {
            cout << myHuff.huffTree[j].weight << '-';   // 输出各权值
            cout << myHuff.huffCode[j] << endl; // 输出各编码
        }
        myHuff.Destroy();
    }
    return 0;
}

输入:

第一行输入t，表示有t个测试实例
第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权值全是小于1万的正整数
依此类推

输出:

逐行输出每个权值对应的编码，格式如下：权值-编码
即每行先输出1个权值，再输出一个短划线，再输出对应编码，接着下一行输入下一个权值和编码。
以此类推

输入样例一

1
2
3

1
5 15 4 4 3 2

输出样例一

参考答案:

DS二叉树–赫夫曼树解码（含代码框架）

题目描述:

已知赫夫曼编码算法和程序，在此基础上进行赫夫曼解码

在赫夫曼树的类定义中增加了一个公有方法：

int Decode(const string codestr, char txtstr[]); //输入编码串codestr，输出解码串txtstr

该方法如果解码成功则返回1，解码失败则返回-1，本程序增加宏定义ok表示1，error表示-1

解码方法的代码框架如下：

输入:

第一行输入t，表示有t个测试实例
第二行先输入n，表示第1个实例有n个权值，接着输入n个权值，权值全是小于1万的正整数
第三行输入n个字母，表示与权值对应的字符
第四行输入k，表示要输入k个编码串
第五行起输入k个编码串
以此类推输入下一个示例

输出:

每行输出解码后的字符串，如果解码失败直接输出字符串“error”，不要输出部分解码结果

输入样例一

2
5 15 4 4 3 2
A B C D E
3
11111
10100001001
00000101100
4 7 5 2 4
A B C D
3
1010000
111011
111110111

输出样例一

AAAAA
ABEAD
error
BBAAA
error
DCD

参考答案:

DS二叉树——二叉树之数组存储

题目描述:

二叉树可以采用数组的方法进行存储，把数组中的数据依次自上而下,自左至右存储到二叉树结点中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点就在数组中用0来表示。，如下图所示

从上图可以看出，右边的是一颗普通的二叉树，当它与左边的完全二叉树对比，发现它比完全二叉树少了第5号结点，所以在数组中用0表示，同样它还少了完全二叉树中的第10、11号结点，所以在数组中也用0表示。

结点存储的数据均为非负整数

输入:

第一行输入一个整数t，表示有t个二叉树
第二行起，每行输入一个数组，先输入数组长度，再输入数组内数据，每个数据之间用空格隔开，输入的数据都是非负整数
连续输入t行

输出:

每行输出一个示例的先序遍历结果，每个结点之间用空格隔开

输入样例一

3
3 1 2 3
5 1 2 3 0 4
13 1 2 3 4 0 5 6 7 8 0 0 9 10

输出样例一

1 2 3 
1 2 4 3 
1 2 4 7 8 3 5 9 10 6

参考答案:

DS二叉树——二叉树之父子结点

题目描述:

给定一颗二叉树的逻辑结构如下图，（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构。

编写程序输出该树的所有叶子结点和它们的父亲结点

输入:

第一行输入一个整数t，表示有t个二叉树
第二行起，按照题目表示的输入方法，输入每个二叉树的先序遍历，连续输入t行

输出:

第一行按先序遍历，输出第1个示例的叶子节点
第二行输出第1个示例中与叶子相对应的父亲节点
以此类推输出其它示例的结果

输入样例一

3
AB0C00D00
AB00C00
ABCD0000EF000

输出样例一

C D 
B A 
B C 
A A 
D F 
C E

参考答案:

DS二叉树—二叉树结点的最大距离

题目描述:

二叉树两个结点的距离是一个结点经过双亲结点，祖先结点等中间结点到达另一个结点经过的分支数。二叉树结点的最大距离是所有结点间距离的最大值。例如，下图所示二叉树结点最大距离是3，C和D的距离。

二叉树用先序遍历顺序创建，#表示空树。计算二叉树结点最大距离和最大距离的两个结点(假设二叉树中取最大距离的两个结点唯一）。

输入:

测试次数T
第2行之后的T行，每行为一棵二叉树先序遍历结果（#表示空树）

输出:

对每棵二叉树，输出树的结点最大距离和最大距离的结点，输出格式见样例。

输入样例一

4
A##
ABC##EF#G###D##
ABEH###F#K###
AB###

输出样例一

0:
5:G D
4:H K
1:B A

参考答案:

DS二叉树—二叉树镜面反转

题目描述:

假设二叉树用二叉链表存储，用先序序列结果创建。输入二叉树的先序序列，请你先创建二叉树，并对树做个镜面反转，再输出反转后的二叉树的先序遍历、中序遍历、后序遍历和层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

测试次数t
每组测试数据是一个二叉树的先序遍历序列，#表示空树

输出:

对每棵二叉树，输出镜面反转后的先序、中序、后序和层次遍历序列。如果空树，输出四个NULL（后面不加空格）。如下：
NULL
NULL
NULL
NULL

输入样例一

3
41#32###65##7##
AB#C##D##
AB##C##

输出样例一

4 6 7 5 1 3 2 
7 6 5 4 3 2 1 
7 5 6 2 3 1 4 
4 6 1 7 5 3 2 
A D B C 
D A C B 
D C B A 
A D B C 
A C B 
C A B 
C B A 
A C B

参考答案:

DS内排—2-路归并排序

题目描述:

输入一组字符串，用2-路归并排序按字典顺序进行降序排序。

输入:

测试次数t
每组测试数据：数据个数n，后跟n个字符串，字符串不含空格。

输出:

对每组测试数据，输出2-路归并排序的每一趟排序结果。每组测试数据的输出之间有1空行。

输入样例一

2
6 shenzhen beijing guangzhou futian nanshan baoan
10 apple pear peach grape cherry dew fig haw lemon marc

输出样例一

shenzhen beijing guangzhou futian nanshan baoan
shenzhen guangzhou futian beijing nanshan baoan
shenzhen nanshan guangzhou futian beijing baoan

pear apple peach grape dew cherry haw fig marc lemon
pear peach grape apple haw fig dew cherry marc lemon
pear peach haw grape fig dew cherry apple marc lemon
pear peach marc lemon haw grape fig dew cherry apple

参考答案:

DS内排—堆排序

题目描述:

给定一组数据，使用堆排序完成数据的降序排序。（建小顶堆)。

输入:

数据个数n，n个整数数据

输出:

初始创建的小顶堆序列
每趟交换、筛选后的数据序列，输出格式见样例

输入样例一

1
2
3

8 34 23 677 2 1 453 3 7

输出样例一

8 1 2 3 7 23 453 677 34
8 2 7 3 34 23 453 677 1
8 3 7 453 34 23 677 2 1
8 7 23 453 34 677 3 2 1
8 23 34 453 677 7 3 2 1
8 34 677 453 23 7 3 2 1
8 453 677 34 23 7 3 2 1
8 677 453 34 23 7 3 2 1

参考答案:

DS内排—直插排序

题目描述:

给定一组数据，使用直插排序完成数据的升序排序。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

数据个数n，n个数据

输出:

直插排序的每一趟排序结果

输入样例一

1	7 34 23 677 2 1 453 3

输出样例一

23 34 677 2 1 453 3
23 34 677 2 1 453 3
2 23 34 677 1 453 3
1 2 23 34 677 453 3
1 2 23 34 453 677 3
1 2 3 23 34 453 677

参考答案:

DS单链表–合并

题目描述:

假定两个单链表是递增有序，定义并实现以下函数，完成两个单链表的合并，继续保持递增有序

int LL_merge(ListNode *La, ListNode *Lb)

输入:

第1行先输入n表示有n个数据，接着输入n个数据

第2行先输入m表示有M个数据，接着输入m个数据

输出:

输出合并后的单链表数据，数据之间用空格隔开

输入样例一

1
2
3

3 11 33 55
4 22 44 66 88

输出样例一

1 2	11 22 33 44 55 66 88

参考答案:

DS单链表–类实现

题目描述:

用C++语言和类实现单链表，含头结点

属性包括：data数据域、next指针域

操作包括：插入、删除、查找

注意：单链表不是数组，所以位置从1开始对应首结点，头结点不放数据

类定义参考

输入:

第1行先输入n表示有n个数据，接着输入n个数据
第2行输入要插入的位置和新数据
第3行输入要插入的位置和新数据
第4行输入要删除的位置
第5行输入要删除的位置
第6行输入要查找的位置
第7行输入要查找的位置

输出:

数据之间用空格隔开，
第1行输出创建后的单链表的数据
每成功执行一次操作（插入或删除），输出执行后的单链表数据
每成功执行一次查找，输出查找到的数据
如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出单链表

输入样例一

6 11 22 33 44 55 66
3 777
1 888
1
11
0
5

输出样例一

11 22 33 44 55 66 
11 22 777 33 44 55 66 
888 11 22 777 33 44 55 66 
11 22 777 33 44 55 66 
error
error
44

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class ListNode {
public:
    int data;
    ListNode *next;

    ListNode() {
        next = NULL;
    }
};

class LinkList {
public:
    ListNode *head;
    int len;

    LinkList() {
        head = new ListNode();
        len = 0;
    }

    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }

    ListNode *LL_index(int i) {
        if (i > len || i < 0) {
            return NULL;
        }
        ListNode *p = head;
        for (int j = 0; j < i; j++) {
            p = p->next;
        }
        return p;
    }

    int LL_get(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        ListNode *p = LL_index(i);
        return p->data;
    }

    int LL_insert(int i, int item) {
        if (i > len + 1 || i <= 0) {
            return error;
        }
        len++;
        ListNode *p = LL_index(i - 1);
        ListNode *temp = new ListNode();
        temp->data = item;
        temp->next = p->next;
        p->next = temp;
        return ok;
    }

    int LL_del(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        len--;
        ListNode *p = LL_index(i - 1);
        p->next = p->next->next;
        return ok;
    }

    void LL_display() {
        ListNode *p = head->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }
};

int main() {
    int n;
    cin >> n;
    LinkList *list = new LinkList();
    for (int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;
        list->LL_insert(i, temp);
    }
    list->LL_display();

    int index, item;
    cin >> index >> item;
    if (list->LL_insert(index, item) == ok) {
        list->LL_display();
    } else {
        cout << "error" << endl;
    }
    cin >> index >> item;
    if (list->LL_insert(index, item) == ok) {
        list->LL_display();
    } else {
        cout << "error" << endl;
    }
    cin >> index;
    if (list->LL_del(index) == ok) {
        list->LL_display();
    } else {
        cout << "error" << endl;
    }
    cin >> index;
    if (list->LL_del(index) == ok) {
        list->LL_display();
    } else {
        cout << "error" << endl;
    }
    cin >> index;
    if (list->LL_get(index) != error) {
        cout << list->LL_get(index) << endl;
    } else {
        cout << "error" << endl;
    }
    cin >> index;
    if (list->LL_get(index) != error) {
        cout << list->LL_get(index) << endl;
    } else {
        cout << "error" << endl;
    }

}

DS单链表–结点交换

题目描述:

用C++实现含头结点的单链表，然后实现单链表的两个结点交换位置。

注意不能简单交换两个结点包含数据，必须通过修改指针来实现两个结点的位置交换

交换函数定义可以参考：

swap（int pa, int pb) //pa和pb表示两个结点在单链表的位置序号

swap (ListNode * p, ListNode * q) //p和q表示指向两个结点的指针

输入:

第1行先输入n表示有n个数据，接着输入n个数据
第2行输入要交换的两个结点位置
第3行输入要交换的两个结点位置

输出:

第一行输出单链表创建后的所有数据，数据之间用空格隔开
第二行输出执行第1次交换操作后的单链表数据，数据之间用空格隔开
第三行输出执行第2次交换操作后的单链表数据，数据之间用空格隔开
如果发现输入位置不合法，输出字符串error，不必输出单链表

输入样例一

5 11 22 33 44 55
1 4
2 6

输出样例一

11 22 33 44 55 
44 22 33 11 55 
error

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class ListNode {
public:
    int data;
    ListNode *next;

    ListNode() {
        next = NULL;
    }
};

class LinkList {
public:
    ListNode *head;
    int len;

    LinkList() {
        head = new ListNode();
        len = 0;
    }

    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }

    ListNode *LL_index(int i) {
        if (i > len || i < 0) {
            return NULL;
        }
        ListNode *p = head;
        for (int j = 0; j < i; j++) {
            p = p->next;
        }
        return p;
    }

    int LL_get(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        ListNode *p = LL_index(i);
        return p->data;
    }

    int LL_insert(int i, int item) {
        if (i > len + 1 || i <= 0) {
            return error;
        }
        len++;
        ListNode *p = LL_index(i - 1);
        ListNode *temp = new ListNode();
        temp->data = item;
        temp->next = p->next;
        p->next = temp;
        return ok;
    }

    int LL_del(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        len--;
        ListNode *p = LL_index(i - 1);
        p->next = p->next->next;
        return ok;
    }

    void LL_display() {
        ListNode *p = head->next;
        while (p) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    int swap(int pa, int pb) {
        if (pa < 1 || pb < 1 || pa > len || pb > len) {
            return error;
        }
        ListNode *p = LL_index(pa - 1), *q = LL_index(pb - 1);

        if (p->next == q)//防止相邻节点爆炸
        {
            p->next = q->next;
            q->next = p->next->next;
            p->next->next = q;
            return true;
        }

        ListNode *t = p->next;//交换前驱
        p->next = q->next;
        q->next = t;

        t = p->next->next;//交换后继
        p->next->next = q->next->next;
        q->next->next = t;

        return ok;

    }
};

int main() {
    int n;
    cin >> n;
    LinkList *list = new LinkList();
    for (int i = 1; i <= n; i++) {
        int temp;
        cin >> temp;
        list->LL_insert(i, temp);
    }
    list->LL_display();
    int index1, index2;
    cin >> index1 >> index2;
    if (list->swap(index1, index2) == ok) {
        list->LL_display();
    } else {
        cout << "error" << endl;
    }
    cin >> index1 >> index2;
    if (list->swap(index1, index2) == ok) {
        list->LL_display();
    } else {
        cout << "error" << endl;
    }

}

DS单链表—删除重复元素

题目描述:

给定n个整数，按输入顺序建立单链表，删除其中的重复数字，输出结果链表。（要求不可以构建新结点，不可以定义新链表。在原链表上删除。）

输入:

测试次数t

每组测试数据一行：

n（表示有n个整数），后跟n个数字

输出:

对每组测试数据，输出删除重复数字后的结果链表表长和每个元素，具体格式见样例。

输入样例一

3
10 1 2 3 4 1 2 10 20 30 20
5 1 1 1 1 1
6 20 22 22 22 22 20

输出样例一

1
2
3

7: 1 2 3 4 10 20 30
1: 1
2: 20 22

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class ListNode {
public:
    int data;
    ListNode *next;

    ListNode() {
        next = NULL;
    }
};

class LinkList {
public:
    ListNode *head;
    int len;

    LinkList() {
        head = new ListNode();
        head->data = 0;
        len = 0;
    }

    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }

    ListNode *LL_index(int i) {
        if (i > len || i < 0) {
            return NULL;
        }
        ListNode *p = head;
        for (int j = 0; j < i; j++) {
            p = p->next;
        }
        return p;
    }

    int LL_get(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        ListNode *p = LL_index(i);
        return p->data;
    }

    int LL_insert(int i, int item) {
        if (i > len + 1 || i <= 0) {
            return error;
        }
        len++;
        ListNode *p = LL_index(i - 1);
        ListNode *temp = new ListNode();
        temp->data = item;
        temp->next = p->next;
        p->next = temp;
        if (p->next->next == NULL) {
            p->next->next = head->next;
        }
        return ok;
    }

    int LL_insert_Dependent(int item) {
        ListNode *p = head->next;
        while (p && p->next != NULL) {
            if (p->data == item) {
                return error;
            }
            p = p->next;
        }

        ListNode *temp = new ListNode();
        temp->data = item;
        if (p == NULL) {
            p = temp;
            head->next = p;
            len++;
            return ok;
        }
        if (p->data == item) {
            return error;
        }
        p->next = temp;
        len++;
        return ok;
    }

    int LL_del(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        len--;
        ListNode *p = LL_index(i - 1);
        ListNode *temp = p->next;
        p->next = p->next->next;
        return temp->data;
    }

    void LL_display() {
        cout << len << ": ";
        ListNode *p = head->next;
        while (p->next != NULL) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << p->data << endl;
    }

    int swap(int pa, int pb) {
        if (pa < 1 || pb < 1 || pa > len || pb > len) {
            return error;
        }
        ListNode *p = LL_index(pa - 1), *q = LL_index(pb - 1);

        if (p->next == q)//防止相邻节点爆炸
        {
            p->next = q->next;
            q->next = p->next->next;
            p->next->next = q;
            return true;
        }

        ListNode *t = p->next;//交换前驱
        p->next = q->next;
        q->next = t;

        t = p->next->next;//交换后继
        p->next->next = q->next->next;
        q->next->next = t;
        return ok;

    }

    int delNode(ListNode *del) {
        ListNode *p = head->next;
        while (p->next != del) {
            p = p->next;
        }
        len--;
        ListNode *temp = p->next;
        p->next = p->next->next;
        // 如果删除的是第一个节点，要将head重新指向头节点
        if (temp == head->next) {
            head->next = temp->next;
        }
        return temp->data;
    }


    void Circle(int k, int s) {
        ListNode *p = head;
        for (int i = 0; i < s - 1; i++) {
            p = p->next;
        }
        while (len != 0) {
            for (int i = 0; i < k; i++) {
                p = p->next;
            }
            if (len != 1) {
                cout << p->data << " ";
            } else {
                cout << p->data << endl;
            }
            delNode(p);
        }
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        LinkList *list = new LinkList();
        for (int i = 1; i <= n; i++) {
            int item;
            cin >> item;
            list->LL_insert_Dependent(item);
        }
        list->LL_display();
    }

}

DS双向链表—祖玛

题目描述:

祖玛是一款曾经风靡全球的游戏，其玩法是：在一条轨道上初始排列着若干个彩色珠子，其中任意三个相邻的珠子不会完全同色。此后，你可以发射珠子到轨道上并加入原有序列中。一旦有三个或更多同色的珠子变成相邻，它们就会立即消失。这类消除现象可能会连锁式发生，其间你将暂时不能发射珠子。

给定轨道上初始的珠子序列，然后是玩家所做的一系列操作。你的任务是，在各次操作之后及时计算出新的珠子序列。

输入:

第一行是一个由大写字母’A’~’Z’组成的字符串，表示轨道上初始的珠子序列，不同的字母表示不同的颜色。
第二行是一个数字n，表示玩家共有n次操作。
接下来的n行依次对应于各次操作。每次操作由一个数字k和一个大写字母描述，以空格分隔。其中，大写字母为新珠子的颜色。若插入前共有m颗珠子，位置0至m-1，则k ∈ [0, m]表示新珠子嵌入在轨道上的位置。

输出:

输出共n行，依次给出各次操作（及可能随即发生的消除现象）之后轨道上的珠子序列。
如果轨道上已没有珠子，则以“-”表示。

输入样例一

ACCBA
5
1 B
0 A
2 B
4 C
0 A

输出样例一

ABCCBA
AABCCBA
AABBCCBA
-
A

参考答案:

#include<iostream>

using namespace std;


void Insert(char *&str, int index, char ch, int size) {
    for (int i = size; i > index; i--) {
        str[i] = str[i - 1];
    }
    str[index] = ch;
}

int DeleteWords(char *&str, int index, int size) {
    char temp = str[index];
    int cnt = 0;
    for (int i = index; i < size; i++) {
        if (str[i] == temp) {
            cnt++;
        } else {
            break;
        }
    }
    for (int i = index; i <= size - cnt; i++) {
        str[i] = str[i + cnt];
    }
    return cnt;
}

bool FindThreeDuplicateWords(char *&str, int &size) {
    for (int i = 0; i <= size - 3; i++) {
        if (str[i] == str[i + 1]) {
            if (str[i + 1] == str[i + 2]) {
                int cnt = DeleteWords(str, i, size);
                size -= cnt;
                return true;
            }
        }
    }
    return false;
}


int main() {
    string temp;
    cin >> temp;
    int size = temp.length();
    char *str = new char[100];
    for (int i = 0; i < size; i++) {
        str[i] = temp[i];
    }
    int t;
    cin >> t;
    while (t--) {
        int index;
        char ch;
        cin >> index >> ch;
        Insert(str, index, ch, size);
        size++;
        while (true) {
            if (!FindThreeDuplicateWords(str, size)) {
                break;
            }
        }
        if (size == 0) {
            cout << "-";
        } else {
            for (int i = 0; i < size; i++) {
                cout << str[i];
            }
        }
        cout << endl;
    }
    return 0;
}

DS哈希查找–Trie树

题目描述:

Trie树又称单词查找树，是一种树形结构，如下图所示。

它是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

输入的一组单词，创建Trie树。输入字符串，计算以该字符串为公共前缀的单词数。

（提示：树结点有26个指针，指向单词的下一字母结点。兄弟节点按词典序排序。）

输入:

测试数据有多组
每组测试数据格式为：
第一行：一行单词，单词全小写字母，且单词不会重复，单词的长度不超过10
第二行：测试公共前缀字符串数量t
后跟t行，每行一个字符串

输出:

每组测试数据输出格式为：
第一行：创建的Trie树的层次遍历结果
第2~t+1行：对每行字符串，输出树中以该字符串为公共前缀的单词数。

输入样例一

abcd abd bcd efg hig
3
ab
bc
abcde

输出样例一

abehbcficddggd
2
1
0

参考答案:

DS哈希查找—线性探测再散列

题目描述:

定义哈希函数为H(key) = key%11，输入表长（大于、等于11）。输入关键字集合，用线性探测再散列构建哈希表，并查找给定关键字。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

测试次数t
每组测试数据为：
哈希表长m、关键字个数n
n个关键字
查找次数k

k个待查关键字

输出:

对每组测试数据，输出以下信息：
构造的哈希表信息，数组中没有关键字的位置输出NULL

对k个待查关键字，分别输出：0或1（0—不成功，1—成功）、比较次数、查找成功的位置（从1开始）

输入样例一

1
12 10
22 19 21 8 9 30 33 4 15 14
4
22
56
30
17

输出样例一

22 30 33 14 4 15 NULL NULL 19 8 21 9
1 1 1
0 6
1 6 2
0 1

参考答案:

DS哈希查找与增补

题目描述:

给出一个数据序列，建立哈希表，采用求余法作为哈希函数，模数为11，哈希冲突用链地址法和表尾插入

如果首次查找失败，就把数据插入到相应的位置中

实现哈希查找与增补功能

输入:

第一行输入n，表示有n个数据
第二行输入n个数据，都是自然数且互不相同，数据之间用空格隔开
第三行输入t，表示要查找t个数据
从第四行起，每行输入一个要查找的数据，都是正整数

输出:

每行输出对应数据的查找结果，每个结果表示为数据所在位置[0，11）和查找次数，中间用空格分开

输入样例一

6
11 23 39 48 75 62
6
39
52
52
63
63
52

输出样例一

6 1
error
8 1
error
8 2
8 1

参考答案:

DS图—图的最短路径（不含代码框架）

题目描述:

给出一个图的邻接矩阵，输入顶点v，用迪杰斯特拉算法求顶点v到其它顶点的最短路径。

注：不允许用STL实现。

输入:

第一行输入t，表示有t个测试实例
第二行输入顶点数n和n个顶点信息
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其它结点如果相连则为距离，无连接则为0，数据之间用空格
隔开。第四行输入v0，表示求v0到其他顶点的最短路径距离
以此类推输入下一个示例

输出:

对每组测试数据，输出：
每行输出v0到某个顶点的最短距离和最短路径
每行格式：v0编号-其他顶点编号-最短路径值—-[最短路径]。没有路径输出：v0编号-其他顶点编号–1。具体请参考示范数据

输入样例一

2
5 0 1 2 3 4
0 5 0 7 15
0 0 5 0 0
0 0 0 0 1
0 0 2 0 0
0 0 0 0 0
0
6 V0 V1 V2 V3 V4 V5
0 0 10 0 30 100
0 0 5 0 0 0
0 0 0 50 0 0
0 0 0 0 0 10
0 0 0 20 0 60
0 0 0 0 0 0
V0

输出样例一

0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]
V0-V1--1
V0-V2-10----[V0 V2 ]
V0-V3-50----[V0 V4 V3 ]
V0-V4-30----[V0 V4 ]
V0-V5-60----[V0 V4 V3 V5 ]

参考答案:

DS图—图的连通分量

题目描述:

输入无向图顶点信息和边信息，创建图的邻接矩阵存储结构，计算图的连通分量个数。

输入:

测试次数t

每组测试数据格式如下：

第一行：顶点数顶点信息

第二行：边数

第三行开始，每行一条边信息

输出:

每组测试数据输出，顶点信息和邻接矩阵信息
输出图的连通分量个数，具体输出格式见样例。
每组输出直接用空行分隔。

输入样例一

3
4 A B C D
2
A B
A C
6 V1 V2 V3 V4 V5 V6
5
V1 V2
V1 V3
V2 V4
V5 V6
V3 V5
8 1 2 3 4 5 6 7 8
5
1 2
1 3
5 6
5 7
4 8

输出样例一

A B C D
0 1 1 0
1 0 0 0
1 0 0 0
0 0 0 0
2

V1 V2 V3 V4 V5 V6
0 1 1 0 0 0
1 0 0 1 0 0
1 0 0 0 1 0
0 1 0 0 0 0
0 0 1 0 0 1
0 0 0 0 1 0
1

1 2 3 4 5 6 7 8
0 1 1 0 0 0 0 0
1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 1 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
3

参考答案:

DS图—图的邻接矩阵存储及度计算

题目描述:

假设图用邻接矩阵存储。输入图的顶点信息和边信息，完成邻接矩阵的设置，并计算各顶点的入度、出度和度，并输出图中的孤立点（度为0的顶点）

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

测试次数T，每组测试数据格式如下：
图类型顶点数（D—有向图，U—无向图）
顶点信息
边数
每行一条边（顶点1 顶点2）或弧（弧尾弧头）信息

输出:

每组测试数据输出如下信息（具体输出格式见样例）：
图的邻接矩阵
按顶点信息输出各顶点的度（无向图）或各顶点的出度入度度（有向图）。孤立点的度信息不输出。
图的孤立点。若没有孤立点，不输出任何信息。

输入样例一

2
D 5
V1 V2 V3 V4 V5
7
V1 V2
V1 V4
V2 V3
V3 V1
V3 V5
V4 V3
V4 V5
U 5
A B C D E
5
A B
A C
B D
D C
A D

输出样例一

参考答案:

DS图—图非0面积

题目描述:

编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。

输入:

测试次数t
每组测试数据格式为：
数组大小m,n
一个由0和1组成的m*n的二维数组

输出:

对每个二维数组，输出符号”1”围住的”0”的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。

输入样例一

2
10 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
5 8
0 1 1 0 0 1 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0
0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0

输出样例一

1
2
3

15
5

参考答案:

DS图—最小生成树

题目描述:

根据输入创建无向网。分别用Prim算法和Kruskal算法构建最小生成树。（假设：输入数据的最小生成树唯一。）

输入:

顶点数n

n个顶点

边数m

m条边信息,格式为：顶点1 顶点2 权值

Prim算法的起点v

输出:

输出最小生成树的权值之和

对两种算法，按树的生长顺序，输出边信息(Kruskal中边顶点按数组序号升序输出)

输入样例一

6
v1 v2 v3 v4 v5 v6 
10
v1 v2 6
v1 v3 1
v1 v4 5
v2 v3 5
v2 v5 3
v3 v4 5
v3 v5 6
v3 v6 4
v4 v6 2
v5 v6 6
v1

输出样例一

15
prim:
v1 v3 1
v3 v6 4
v6 v4 2
v3 v2 5
v2 v5 3
kruskal:
v1 v3 1
v4 v6 2
v2 v5 3
v3 v6 4
v2 v3 5

参考答案:

DS图遍历–广度优先搜索

题目描述:

给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始

注意：图n个顶点编号从0到n-1

代码框架如下：

输入:

第一行输入t，表示有t个测试实例
第二行输入n，表示第1个图有n个结点
第三行起，每行输入邻接矩阵的一行，以此类推输入n行
第i个结点与其他结点如果相连则为1，无连接则为0，数据之间用空格隔开
以此类推输入下一个示例

输出:

每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开

输入样例一

输出样例一

1
2
3

0 2 3 1 
0 3 4 2 1

参考答案:

DS图遍历–深度优先搜索

题目描述:

给出一个图的邻接矩阵，对图进行深度优先搜索，从顶点0开始

注意：图n个顶点编号从0到n-1

代码框架如下：

输入:

输出:

每行输出一个图的深度优先搜索结果，结点编号之间用空格隔开

输入样例一

输出样例一

1
2
3

0 2 1 3 
0 3 2 1 4

参考答案:

DS基数排序

题目描述:

给定一组数据，对其进行基数升序排序。

输入:

测试次数t
每组测试数据一行：数字个数n，后跟n个数字（整数）

输出:

对每组测试数据，输出每趟分配、收集的结果。若分配中该位没有数字，输出NULL。具体输出格式见样例。每组测试数据间以空行分隔。

输入样例一

1
2
3

2
10 278 109 63 930 589 184 505 269 8 83
6 57 0 93 19 18 99

输出样例一

0:->930->^
1:NULL
2:NULL
3:->63->83->^
4:->184->^
5:->505->^
6:NULL
7:NULL
8:->278->8->^
9:->109->589->269->^
930 63 83 184 505 278 8 109 589 269
0:->505->8->109->^
1:NULL
2:NULL
3:->930->^
4:NULL
5:NULL
6:->63->269->^
7:->278->^
8:->83->184->589->^
9:NULL
505 8 109 930 63 269 278 83 184 589
0:->8->63->83->^
1:->109->184->^
2:->269->278->^
3:NULL
4:NULL
5:->505->589->^
6:NULL
7:NULL
8:NULL
9:->930->^
8 63 83 109 184 269 278 505 589 930

0:->0->^
1:NULL
2:NULL
3:->93->^
4:NULL
5:NULL
6:NULL
7:->57->^
8:->18->^
9:->19->99->^
0 93 57 18 19 99
0:->0->^
1:->18->19->^
2:NULL
3:NULL
4:NULL
5:->57->^
6:NULL
7:NULL
8:NULL
9:->93->99->^
0 18 19 57 93 99

参考答案:

DS堆栈–括号匹配

题目描述:

处理表达式过程中需要对括号匹配进行检验，括号匹配包括三种：“(”和“)”，“[”和“]”，“{”和“}”。例如表达式中包含括号如下：

(	)	[	(	)	(	[	]	)	]	{	}
1	2	3	4	5	6	7	8	9	10	11	12

从上例可以看出第1和第2个括号匹配，第3和第10个括号匹配，4和5匹配，6和9匹配，7和8匹配，11和12匹配。从中可以看到括号嵌套的的情况是比较复杂的，使用堆栈可以很方便的处理这种括号匹配检验，可以遵循以下规则：

1、当接收第1个左括号，表示新的一组匹配检查开始；随后如果连续接收到左括号，则不断进堆栈。

2、当接受第1个右括号，则和最新进栈的左括号进行匹配，表示嵌套中1组括号已经匹配消除

3、若到最后，括号不能完全匹配，则说明输入的表达式有错

建议使用C++自带的stack对象来实现

stack类使用的参考代码

n包含头文件<stack> ： #include <stack>

n创建一个堆栈对象s（注意stack是模板类）：stack <char> s; //堆栈的数据类型是字符型

n把一个字符ct压入堆栈： s.push(ct);

n把栈顶元素弹出：s.pop();

n获取栈顶元素，放入变量c2： c2 = s.top();

n判断堆栈是否空： s.empty()，如果为空则函数返回true，如果不空则返回false

输入:

第一行输入一个t，表示下面将有t组测试数据。接下来的t行的每行输入一个表达式，表达式只考虑英文半角状态输入，无需考虑中文全角输入

输出:

对于每一行的表达式，检查括号是否匹配，匹配则输入ok，不匹配则输出error

输入样例一

2
(a+b)[4*5+(-6)]
[5*8]/{(a+b)-6

输出样例一

1
2
3

ok
error

参考答案:

DS堆栈–行编辑

题目描述:

使用C++的STL堆栈对象，编写程序实现行编辑功能。行编辑功能是：当输入#字符，则执行退格操作；如果无字符可退就不操作，不会报错

本程序默认不会显示#字符，所以连续输入多个#表示连续执行多次退格操作

每输入一行字符打回车则表示字符串结束

注意：必须使用堆栈实现，而且结果必须是正序输出

输入:

第一行输入一个整数t，表示有t行字符串要输入
第二行起输入一行字符串，共输入t行

输出:

每行输出最终处理后的结果，如果一行输入的字符串经过处理后没有字符输出，则直接输出NULL

输入样例一

4
chinaa#
sb#zb#u
##shen###zhen###
chi##a#####

输出样例一

china
szu
sz
NULL

参考答案:

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        stack<char> s1;
        stack<char> s2;
        string str;
        cin >> str;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            if (str[i] == '#' && !s1.empty()) {
                s1.pop();
            } else if (str[i] != '#') {
                s1.push(str[i]);
            }
        }
        while (!s1.empty()) {
            s2.push(s1.top());
            s1.pop();
        }
        if (s2.empty()) {
            cout << "NULL" << endl;
        } else {
            while (!s2.empty()) {
                cout << s2.top();
                s2.pop();
            }
            cout << endl;
        }
    }
    return 0;
}

DS堆栈–迷宫求解

题目描述:

给出一个N*N的迷宫矩阵示意图，从起点[0,0]出发，寻找路径到达终点[N-1, N-1]

要求使用堆栈对象来实现，具体算法参考课本3.2.4节51页

输入:

第一行输入t，表示有t个迷宫
第二行输入n，表示第一个迷宫有n行n列
第三行起，输入迷宫每一行的每个方格的状态，0表示可通过，1表示不可通过
输入n行
以此类推输入下一个迷宫

输出:

逐个输出迷宫的路径
如果迷宫不存在路径，则输出no path并回车
如果迷宫存在路径，将路径中每个方格的x和y坐标输出，从起点到终点，每输出四个方格就换行，最终以单词END结尾，具体格式参考示范数据
输出的代码参考如下：
//path是保存路径的堆栈，堆栈中每个元素都包含x坐标和y坐标，用属性xp和yp表示
//path1是一个临时堆栈，把path的数据倒序输出到path1，使得路径按正序输出
if (!path.empty()) //找到路径
{ //……若干代码，实现path的数据导入path1
i=0; //以下是输出路径的代码
while (!path1.empty())
{ cpos = path1.top();
if ( (++i)%4 == 0 )
cout<<’[‘<<cpos.xp<<’,’<<cpos.yp<<’]’<<”–”<<endl;
else
cout<<’[‘<<cpos.xp<<’,’<<cpos.yp<<’]’<<”–”;
path1.pop();
}
cout<<”END”<<endl;
}
else
cout<<”no path”<<endl; //找不到路径输出no path

输入样例一

2
8
0 0 0 1 1 1 1 1
1 0 0 0 1 0 0 1
1 0 0 0 1 0 0 0
1 1 0 0 0 0 0 1
0 0 1 1 0 1 1 0
0 0 0 0 0 0 1 1
1 1 1 1 1 0 0 1
0 0 0 0 1 0 0 0
7
0 0 0 1 1 1 1
1 0 0 1 0 0 1
1 0 0 1 0 0 0
1 1 0 0 0 0 1
0 0 1 1 0 1 0
1 0 0 0 0 1 0
0 0 0 0 1 1 0

输出样例一

[0,0]--[0,1]--[0,2]--[1,2]--
[1,3]--[2,3]--[3,3]--[3,4]--
[4,4]--[5,4]--[5,5]--[6,5]--
[6,6]--[7,6]--[7,7]--END
no path

参考答案:

DS堆栈–逆序输出（使用STL栈）

题目描述:

C++中已经自带堆栈对象stack，无需编写堆栈操作的具体实现代码。

本题目主要帮助大家熟悉stack对象的使用，然后实现字符串的逆序输出

输入一个字符串，按字符按输入顺序压入堆栈，然后根据堆栈后进先出的特点，做逆序输出

stack类使用的参考代码

n包含头文件<stack> ： #include <stack>

n创建一个堆栈对象s（注意stack是模板类）：stack <char> s; //堆栈的数据类型是字符型

n把一个字符ct压入堆栈： s.push(ct);

n把栈顶元素弹出：s.pop();

n获取栈顶元素，放入变量c2： c2 = s.top();

n判断堆栈是否空： s.empty()，如果为空则函数返回true，如果不空则返回false

输入:

第一行输入t，表示有t个测试实例第二起，每一行输入一个字符串，注意字符串不要包含空格
字符串的输入可以考虑一下代码：
#include
int main()
{ string str;
Int len;
cin>>str; //把输入的字符串保存在变量str中
len = str.length() //获取输入字符串的长度
}

输出:

每行逆序输出每一个字符串

输入样例一

2
abcdef
aabbcc

输出样例一

1
2
3

fedcba
ccbbaa

参考答案:

#include <iostream>
#include <stack>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        stack<char> s;
        string str;
        cin >> str;
        int len = str.length();
        for (int i = 0; i < len; i++) {
            s.push(str[i]);
        }
        for (int i = 0; i < len; i++) {
            cout << s.top();
            s.pop();
        }
        cout << endl;
    }
}

DS循环链表—约瑟夫环(Ver. I - A)

题目描述:

N个人坐成一个圆环（编号为1 - N），从第S个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2，S = 1。2号先出列，然后是1号，最后剩下的是3号。

要求使用循环链表实现。

输入:

测试数据有多组
每组包括3个数N、K、S，表示有N个人，从第S个人开始，数到K出列。(1 <= N <= 10^6，1 <= K <= 10, 1 <= S <= N)

输出:

出列的人的编号

输入样例一

1 2	13 3 1 3 2 1

输出样例一

1 2	3 6 9 12 2 7 11 4 10 5 1 8 13 2 1 3

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class ListNode {
public:
    int data;
    ListNode *next;

    ListNode() {
        next = NULL;
    }
};

class LinkList {
public:
    ListNode *head;
    int len;

    LinkList() {
        head = new ListNode();
        head->data = 0;
        len = 0;
    }

    ~LinkList() {
        ListNode *p, *q;
        p = head;
        while (p != NULL) {
            q = p;
            p = p->next;
            delete q;
        }
        len = 0;
        head = NULL;
    }

    ListNode *LL_index(int i) {
        if (i > len || i < 0) {
            return NULL;
        }
        ListNode *p = head;
        for (int j = 0; j < i; j++) {
            p = p->next;
        }
        return p;
    }

    int LL_get(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        ListNode *p = LL_index(i);
        return p->data;
    }

    int LL_insert(int i, int item) {
        if (i > len + 1 || i <= 0) {
            return error;
        }
        len++;
        ListNode *p = LL_index(i - 1);
        ListNode *temp = new ListNode();
        temp->data = item;
        temp->next = p->next;
        p->next = temp;
        if (p->next->next == NULL) {
            p->next->next = head->next;
        }
        return ok;
    }

    int LL_del(int i) {
        if (i > len || i <= 0) {
            return error;
        }
        len--;
        ListNode *p = LL_index(i - 1);
        ListNode *temp = p->next;
        p->next = p->next->next;
        return temp->data;
    }

    void LL_display() {
        ListNode *p = head->next;
        cout << p->data << " ";
        p = p->next;
        while (p && p != head->next) {
            cout << p->data << " ";
            p = p->next;
        }
        cout << endl;
    }

    int swap(int pa, int pb) {
        if (pa < 1 || pb < 1 || pa > len || pb > len) {
            return error;
        }
        ListNode *p = LL_index(pa - 1), *q = LL_index(pb - 1);

        if (p->next == q)//防止相邻节点爆炸
        {
            p->next = q->next;
            q->next = p->next->next;
            p->next->next = q;
            return true;
        }

        ListNode *t = p->next;//交换前驱
        p->next = q->next;
        q->next = t;

        t = p->next->next;//交换后继
        p->next->next = q->next->next;
        q->next->next = t;
        return ok;

    }

    int delNode(ListNode *del) {
        ListNode *p = head->next;
        while (p->next != del) {
            p = p->next;
        }
        len--;
        ListNode *temp = p->next;
        p->next = p->next->next;
        // 如果删除的是第一个节点，要将head重新指向头节点
        if (temp == head->next) {
            head->next = temp->next;
        }
        return temp->data;
    }


    void Circle(int k, int s) {
        ListNode *p = head;
        for (int i = 0; i < s - 1; i++) {
            p = p->next;
        }
        while (len != 0) {
            for (int i = 0; i < k; i++) {
                p = p->next;
            }
            if (len != 1) {
                cout << p->data << " ";
            } else {
                cout << p->data << endl;
            }
            delNode(p);
        }
    }
};

int main() {
    int n;
    while (cin >> n) {
        int k, s;
        cin >> k >> s;
        LinkList *list = new LinkList();
        for (int i = 1; i <= n; i++) {
            list->LL_insert(i, i);
        }
        list->Circle(k, s);


    }

}

DS排序–希尔排序

题目描述:

给出一个数据序列，使用希尔排序算法进行降序排序。

间隔gap使用序列长度循环除2直到1

输入:

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出:

对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

输入样例一

2
6
111 22 6 444 333 55
8
77 555 33 1 444 77 666 2222

输出样例一

444 333 55 111 22 6
444 333 111 55 22 6

444 555 666 2222 77 77 33 1
666 2222 444 555 77 77 33 1
2222 666 555 444 77 77 33 1

参考答案:

DS排序–折半插入排序

题目描述:

给出一个数据序列，使用折半插入排序算法进行降序排序。

输入:

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出:

对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

输入样例一

2
5
111 22 6 444 333
8
30 13 70 85 39 42 6 20

输出样例一

111 22 6 444 333
111 22 6 444 333
444 111 22 6 333
444 333 111 22 6

30 13 70 85 39 42 6 20
70 30 13 85 39 42 6 20
85 70 30 13 39 42 6 20
85 70 39 30 13 42 6 20
85 70 42 39 30 13 6 20
85 70 42 39 30 13 6 20
85 70 42 39 30 20 13 6

参考答案:

DS排序–简单选择排序

题目描述:

给出一个数据序列，使用简单选择排序算法进行升序排序

输入:

第一行输入t，表示有t个测试示例
第二行输入n，表示第一个示例有n个数据(n>1)
第三行输入n个数据，都是正整数，数据之间用空格隔开
以此类推

输出:

对每组测试数据，输出每趟排序结果。不同组测试数据间用空行分隔。

输入样例一

2
6
21 25 49 25 16 8
8
30 13 70 85 39 42 6 20

输出样例一

8 25 49 25 16 21
8 16 49 25 25 21
8 16 21 25 25 49
8 16 21 25 25 49
8 16 21 25 25 49
8 16 21 25 25 49

6 13 70 85 39 42 30 20
6 13 70 85 39 42 30 20
6 13 20 85 39 42 30 70
6 13 20 30 39 42 85 70
6 13 20 30 39 42 85 70
6 13 20 30 39 42 85 70
6 13 20 30 39 42 70 85
6 13 20 30 39 42 70 85

参考答案:

DS排序—快速排序

题目描述:

输入一组数据，用快速排序进行升序排序。

输入:

测试次数t
每组测试数据为：
数据个数n，n个数字

输出:

对每组测试数据，输出快速排序每趟排好的数字及位置（位置从1开始）。不同组测试数据的输出以空行分隔。

输入样例一

2
6 111 22 6 444 333 55
8 77 555 33 1 444 77 10 200

输出样例一

参考答案:

DS查找——折半查找求平方根

题目描述:

假定输入y是整数，我们用折半查找来找这个平方根。在从0到y之间必定有一个取值是y的平方根，如果我们查找的数x比y的平方根小，则x²<y，如果我们查找的数x比y的平方根大，则x²>y，我们可以据此缩小查找范围，当我们查找的数足够准确时（比如满足|x²-y|<0.00001），就可以认为找到了y的平方根。

比如求5的平方根x，则x一定满足 0<=x<=5，取x为(5+0)/2=2.5，因为2.5的平方为6.25>5，所以x一定小于2.5，也即x满足0<=x<=2.5，取x为1.25，以此类推

X的范围		X的取值	x²	x²-y
0	5	2.5	6.25	1.25
0	2.5	1.25	1.5625	-3.4375
1.25	2.5	1.875	3.515625	-1.484375
1.875	2.5	2.1875	4.78515625	-0.21484375
2.1875	2.5	2.34375	5.4931640625	0.4931640625
2.1875	2.34375	2.265625	5.133056640625	0.133056640625
2.1875	2.265625	2.2265625	…	…

最后求得5的平方根为2.236

温馨提示：计算过程中为确保精确性，计算变量的类型都用double

保留小数位数请采用printf("%.3lf\n",x) 的格式输出

程序框架参考平时练习中折半查找的方法

输入:

第1行输入一个整数n(<100)，表示有n个数
从第2行起到第n+1行输入n个整数

输出:

输出n个数的平方根，精确到小数点后三位。

输入样例一

2
13
5

输出样例一

1 2	3.606 2.236

参考答案:

DS查找—二叉树平衡因子

题目描述:

二叉树用数组存储，将二叉树的结点数据依次自上而下,自左至右存储到数组中，一般二叉树与完全二叉树对比，比完全二叉树缺少的结点在数组中用0来表示。

计算二叉树每个结点的平衡因子，并按后序遍历的顺序输出结点的平衡因子。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

测试次数t
每组测试数据一行，数组元素个数n，后跟n个字符，二叉树的数组存储。

输出:

对每组测试数据，按后序遍历的顺序输出树中结点的平衡因子（测试数据没有空树）

输入样例一

2
6 ABC00D
24 ABCD0EF0000H00000000000I

输出样例一

B 0
D 0
C 1
A -1
D 0
B 1
I 0
H 1
E 2
F 0
C 2
A -2

参考答案:

DS栈—波兰式，逆波兰式

题目描述:

表达式有三种表示方法，分别为：

前缀表示(波兰式)：运算符+操作数1+操作数2

中缀表示：操作数1+运算符+操作数2

后缀表示(逆波兰式)：操作数1+操作数2+运算符

例如：a +b * (c -d ) - e/f

波兰式：-+a*b-cd/ef （运算符在操作数的前面，用递归计算波兰式）

中缀式：a+b*c-d-e/f

逆波兰式：abcd-*+ef/- （运算符在操作数的后面，用栈计算逆波兰式）

中缀表示就是原表达式去掉扣号。

根据表达式求波兰式、逆波兰式都是教材第三章表达式求值的思想。

求波兰式，需要操作数栈(注意不是计算结果入栈，有计算式入栈)，运算符栈。区别在于从后往前扫描表达式，‘(’ 换成')','('换成‘)’。栈顶运算符优先级>新读入运算符优先级出栈，教材第三章表3.1中的相同运算符优先级>（从左往右计算）改为<，例如栈顶为‘+‘，新读入的为‘+’，则栈顶优先级<新读入的优先级。

求逆波兰式，只需要运算符栈。操作数直接输出，操作符按表3.1优先级顺序出栈，输出。

输入表达式，求其波兰式和逆波兰式。

输入:

测试次数
每组测试数据一行，一个合法表达式

输出:

对每组测试数据，输出两行
第一行，表达式的波兰表示
第二行，表达式的逆波兰表示
不同组测试数据间以空行分隔。

输入样例一

2
4+2*3-10/5
12+3*5+(2+10)*5

输出样例一

- + 4 * 2 3 / 10 5
4 2 3 * + 10 5 / -

+ + 12 * 3 5 * + 2 10 5
12 3 5 * + 2 10 + 5 * +

参考答案:

DS树–二叉树之最大路径

题目描述:

给定一颗二叉树的逻辑结构（先序遍历的结果，空树用字符‘0’表示，例如AB0C00D00），建立该二叉树的二叉链式存储结构

二叉树的每个结点都有一个权值，从根结点到每个叶子结点将形成一条路径，每条路径的权值等于路径上所有结点的权值和。编程求出二叉树的最大路径权值。如下图所示，共有4个叶子即有4条路径，

路径1权值=5 + 4 + 11 + 7 = 27 路径2权值=5 + 4 + 11 + 2 = 22

路径3权值=5 + 8 + 13 = 26 路径4权值=5 + 8 + 4 + 1 = 18

可计算出最大路径权值是27。

该树输入的先序遍历结果为ABCD00E000FG00H0I00，各结点权值为：

A-5，B-4，C-11，D-7，E-2，F-8，G-13，H-4，I-1

输入:

第一行输入一个整数t，表示有t个测试数据
第二行输入一棵二叉树的先序遍历，每个结点用字母表示
第三行先输入n表示二叉树的结点数量，然后输入每个结点的权值，权值顺序与前面结点输入顺序对应
以此类推输入下一棵二叉树

输出:

每行输出每棵二叉树的最大路径权值，如果最大路径权值有重复，只输出1个

输入样例一

2
AB0C00D00
4 5 3 2 6
ABCD00E000FG00H0I00
9 5 4 11 7 2 8 13 4 1

输出样例一

1
2
3

11
27

参考答案:

DS树–二叉树高度

题目描述:

给出一棵二叉树，求它的高度。二叉树的创建采用前面实验的方法。

注意，二叉树的层数是从1开始

输入:

第一行输入一个整数t，表示有t个二叉树
第二行起输入每个二叉树的先序遍历结果，空树用字符‘0’表示，连续输入t行

输出:

每行输出一个二叉树的高度

输入样例一

1
2
3

1
AB0C00D00

输出样例一

1
2

参考答案:

DS树–带权路径和

题目描述:

计算一棵二叉树的带权路径总和，即求赫夫曼树的带权路径和。

已知一棵二叉树的叶子权值，该二叉树的带权案路径和APL等于叶子权值乘于根节点到叶子的分支数，然后求总和。如下图中，叶子都用大写字母表示，权值对应为：A-7，B-6，C-2，D-3

树的带权路径和 = 7*1 + 6*2 + 2*3 + 3*3 = 34

本题二叉树的创建参考前面的方法

输入:

第一行输入一个整数t，表示有t个二叉树
第二行输入一棵二叉树的先序遍历结果，空树用字符‘0’表示，注意输入全是英文字母和0，其中大写字母表示叶子
第三行先输入n表示有n个叶子，接着输入n个数据表示n个叶子的权值，权值的顺序和前面输入的大写字母顺序对应
以此类推输入下一棵二叉树

输出:

输出每一棵二叉树的带权路径和

输入样例一

2
xA00tB00zC00D00
4 7 6 2 3
ab0C00D00
2 10 20

输出样例一

1
2
3

34
40

参考答案:

DS森林叶子编码

题目描述:

给定一组森林，编写程序生成对应的二叉树，输出这颗二叉树叶结点对应的二进制编码.规定二叉树的左边由0表示，二叉树的右边由1表示。

输入:

输入：
N B 表示N个树，每结点最多B个分支
第2行至第N+1行，每个树的先序遍历

输出:

每行表示一个叶结点对应的二进制编码.

输入样例一

3 3
A B 0 0 0 C 0 0 0 D 0 0 0
E F 0 0 0 0 0
G H 0 0 0 I J 0 0 0 0 0 0

输出样例一

0 1 1
1 0
1 1 0 1 0

参考答案:

DS线性表—多项式相加

题目描述:

对于一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn ，每个项都有系数和指数两部分，例如p2x2的系数为p2,指数为2。

编程实现两个多项式的相加。

例如5+x+2x2+3x3，-5-x+6x2+4x4，两者相加结果：8x2+3x3+4x4

其中系数5和-5都是x的0次方的系数，相加后为0，所以不显示。x的1次方同理不显示。

可用顺序表或单链表实现。

输入:

第1行：输入t表示有t组测试数据

第2行：输入n表示有第1组的第1个多项式包含n个项

第3行：输入第一项的系数和指数，以此类推输入n行

接着输入m表示第1组的第2个多项式包含m项

同理输入第2个多项式的m个项的系数和指数

参考上面输入第2组数据，以此类推输入t组

假设所有数据都是整数

输出:

对于每1组数据，先用两行输出两个原来的多项式，再用一行输出运算结果，不必考虑结果全为0的情况

输出格式参考样本数据，格式要求包括：

1.如果指数或系数是负数，用小括号括起来。

2.如果系数为0，则该项不用输出。

3.如果指数不为0，则用符号^表示，例如x的3次方，表示为x^3。

4.多项式的每个项之间用符号+连接，每个+两边加1个空格隔开。

输入样例一

输出样例一

5 + 1x^1 + 2x^2 + 3x^3
(-5) + (-1)x^1 + 6x^2 + 4x^4
8x^2 + 3x^3 + 4x^4
(-3) + (-5)x^1 + 2x^2
9x^(-1) + 2 + 3x^1 + (-2)x^2
9x^(-1) + (-1) + (-2)x^1

参考答案:

DS链表—学生宿舍管理

题目描述:

假设某校有20间宿舍，宿舍编号101，102，...,120。每间只住一名学生。初始部分宿舍已用。用两个链表（已用宿舍链表和可用宿舍链表）维护宿舍的管理，实现宿舍分配、宿舍交回。

约定已用宿舍链表按宿舍号升序链接。初始可用宿舍链表也按宿舍号升序链接。

宿舍分配从可用宿舍链表中摘取第一间宿舍分配给学生。学生交回的宿舍挂在可用宿舍链表最后。

备注：使用list容器或静态链表。不用考虑宿舍分配和交回不成功的情况。

输入:

初始宿舍状态，第一行输入n，表示已用宿舍n间
后跟n行数据，每行格式为：宿舍号学生姓名
操作次数m，后跟m行操作，操作格式如下：

assign 学生 //为学生分配宿舍，从可用宿舍链表头摘取一间宿舍，
//按宿舍号升序挂在已用宿舍链表中。

return 宿舍号   //学生退宿舍，删除已用宿舍链表中对应结点，
                         //挂在可用宿舍链表尾部。
display_free   //输出可用宿舍链表信息。
display_used   //输出已用宿舍链表信息。

输出:

display_free依次输出当前可用宿舍链表中的宿舍号，具体格式见样例。
display_used依次输出当前已用宿舍链表中的学生和宿舍号，具体格式见样例。

输入样例一

5
李明  103
张三  106
王五  107
钱伟  112
章立  118
8
assign 李四
assign 赵六
return 118
return 101
assign 马山
display_used
assign 林立
display_free

输出样例一

1
2
3

赵六(102)-李明(103)-马山(104)-张三(106)-王五(107)-钱伟(112)
108-109-110-111-113-114-115-116-117-119-120-118-101

参考答案:

DS队列–组队列

题目描述:

组队列是队列结构中一种常见的队列结构，在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令：

1、 ENQUEUE，表示当有新的元素进入队列，首先会检索是否有同一组的元素已经存在，如果有，则新元素排在同组的最后，如果没有则插入队列末尾。

2、 DEQUEUE，表示队列头元素出队

3、 STOP，停止操作

建议使用C++自带的队列对象queue，编程更方便

输入:

第1行输入一个t(t<=10)，表示1个队列中有多少个组
第2行输入一个第1组的元素个数和数值
第3行输入一个第2组的元素个数和数值
以此类推输入完t组以定义同组元素之后，开始输入多个操作命令(<200)，对空的组队列进行操作，例如输入ENQUEUE 100，表示把元素100插入队列

输出:

DEQUEUE出队的元素

输入样例一

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
STOP

输出样例一

1 2	101 102 103

参考答案:

DS静态查找之折半查找

题目描述:

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用折半查找算法

输入:

第一行输入n，表示队列有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入t，表示有t个要查找的数值
第四行起，输入t个数值，输入t行

输出:

每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error

输入样例一

8
11 22 33 44 55 66 77 88
3
22
88
99

输出样例一

2
8
error

参考答案:

DS静态查找之顺序查找

题目描述:

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用带哨兵的顺序查找算法

输入:

输出:

每行输出一个要查找的数值在队列的位置，如果查找不成功，输出字符串error

输入样例一

8
33 66 22 88 11 27 44 55
3
22
11
99

输出样例一

3
5
error

参考答案:

DS静态查找之顺序索引查找

题目描述:

给出一个队列和要查找的数值，找出数值在队列中的位置，队列位置从1开始

要求使用顺序索引查找算法，其中索引表查找和块内查找都采用不带哨兵、从头开始的顺序查找方法。

输入:

第一行输入n，表示主表有n个数据
第二行输入n个数据，都是正整数，用空格隔开
第三行输入k，表示主表划分为k个块，k也是索引表的长度
第四行输入k个数据，表示索引表中每个块的最大值
第五行输入t，表示有t个要查找的数值
第六行起，输入t个数值，输入t行

输出:

每行输出一个要查找的数值在队列的位置和查找次数，数据之间用短划线隔开，如果查找不成功，输出字符串error

输入样例一

18
22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53
3
22 48 86
6
13
5
48
40
53
90

输出样例一

3-4
error
12-8
error
18-9
error

参考答案:

DS顺序表–合并操作

题目描述:

建立顺序表的类，属性包括：数组、实际长度、最大长度（设定为1000）

已知两个递增序列，把两个序列的数据合并到顺序表中，并使得顺序表的数据递增有序

输入:

第1行先输入n表示有n个数据，接着输入n个数据，表示第1个序列，要求数据递增互不等
第2行先输入m表示有m个数据，接着输入m个数据，表示第2个序列，要求数据递增互不等

输出:

顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开
第1行输出创建后的顺序表内容

输入样例一

1
2
3

3 11 33 55
5 22 44 66 88 99

输出样例一

1 2	8 11 22 33 44 55 66 88 99

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class SeqList {
private:
    int *list;
    int maxsize;
    int size;
public:
    SeqList() {
        maxsize = 1000;
        size = 0;
        list = new int[maxsize];
    }

    ~SeqList() {}

    int list_size() {
        return size;
    }

    int list_insert(int i, int item) {
        i -= 1;
        if (i > size || i < 0) {
            return error;
        }
        if (i == size) {
            list[size++] = item;
            return ok;
        }
        for (int j = size; j >= i; j--) {
            list[j] = list[j - 1];
        }
        list[i] = item;
        size++;
        return ok;
    }

    int list_del(int i) {
        i -= 1;
        if (i >= size || i < 0) {
            return error;
        }
        for (int j = i; j < size; j++) {
            list[j] = list[j + 1];
        }
        size--;
        return ok;
    }

    int list_get(int i) {
        i -= 1;
        if (i >= size || i < 0) {
            return error;
        }
        return list[i];
    }

    void list_display() {
        cout << size << " ";
        for (int i = 0; i < size; i++) {
            cout << list[i] << " ";
        }
        cout << endl;
    }

    int getFront() {
        if (size == 0) {
            return 99999;
        }
        return list[0];
    }

};

int main() {
    int n1, n2;
    cin >> n1;
    SeqList list1 = *new SeqList();
    for (int i = 1; i <= n1; i++) {
        int item;
        cin >> item;
        list1.list_insert(i, item);
    }
    cin >> n2;
    SeqList list2 = *new SeqList();
    for (int i = 1; i <= n2; i++) {
        int item;
        cin >> item;
        list2.list_insert(i, item);
    }

    SeqList list = *new SeqList();
    for (int i = 1; i <= n1 + n2; i++) {
        if (list1.getFront() < list2.getFront()) {
            list.list_insert(i, list1.getFront());
            list1.list_del(1);
        } else {
            list.list_insert(i, list2.getFront());
            list2.list_del(1);
        }
    }
    list.list_display();
    return 0;
}

DS顺序表–类实现

题目描述:

用C++语言和类实现顺序表

属性包括：数组、实际长度、最大长度（设定为1000）

操作包括：创建、插入、删除、查找

类定义参考

输入:

第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据
第2行输入要插入的位置和新数据
第3行输入要插入的位置和新数据
第4行输入要删除的位置
第5行输入要删除的位置
第6行输入要查找的位置
第7行输入要查找的位置

输出:

数据之间用空格隔开
第1行输出创建后的顺序表内容，包括顺序表实际长度和数据
每成功执行一次操作（插入或删除），输出执行后的顺序表内容
每成功执行一次查找，输出查找到的数据
如果执行操作失败（包括插入、删除、查找等失败），输出字符串error，不必输出顺序表内容

输入样例一

6 11 22 33 44 55 66
3 777
1 888
1
9
0
5

输出样例一

6 11 22 33 44 55 66 
7 11 22 777 33 44 55 66 
8 888 11 22 777 33 44 55 66 
7 11 22 777 33 44 55 66 
error
error
44

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class SeqList {
private:
    int *list;
    int maxsize;
    int size;
public:
    SeqList() {
        maxsize = 1000;
        size = 0;
        list = new int[maxsize];
    }

    ~SeqList() {}

    int list_size() {
        return size;
    }

    int list_insert(int i, int item) {
        i-=1;
        if (i > size || i < 0) {
            return error;
        }
        if (i == size) {
            list[size++] = item;
            return ok;
        }
        for (int j = size; j >= i; j--) {
            list[j] = list[j - 1];
        }
        list[i] = item;
        size++;
        return ok;
    }

    int list_del(int i) {
        i -= 1;
        if (i >= size || i < 0) {
            return error;
        }
        int temp = list[i];
        size--;
        for (int j = i; j < size; j++) {
            list[j] = list[j + 1];
        }
        return ok;
    }

    int list_get(int i) {
        i -= 1;
        if (i >= size || i < 0) {
            return error;
        }
        return list[i];
    }

    void list_display() {
        cout << size << " ";
        for (int i = 0; i < size; i++) {
            cout << list[i] << " ";
        }
        cout << endl;
    }

};

int main() {
    int n;
    cin >> n;
    SeqList list = *new SeqList();
    for (int i = 1; i <= n; i++) {
        int item;
        cin >> item;
        list.list_insert(i, item);
    }
    list.list_display();

    int i, item;
    cin >> i >> item;
    if (list.list_insert(i, item) == ok) {
        list.list_display();
    } else {
        cout << "error" << endl;
    }
    cin >> i >> item;
    if (list.list_insert(i, item) == ok) {
        list.list_display();
    } else {
        cout << "error" << endl;
    }

    cin >> i;
    if (list.list_del(i) == ok) {
        list.list_display();
    } else {
        cout << "error" << endl;
    }
    cin >> i;
    if (list.list_del(i) == ok) {
        list.list_display();
    } else {
        cout << "error" << endl;
    }
    cin >> i;
    if (list.list_get(i) != error) {
        cout << list.list_get(i) << endl;
    } else {
        cout << "error" << endl;
    }
    cin >> i;
    if (!list.list_get(i) != error) {
        cout << list.list_get(i) << endl;
    } else {
        cout << "error" << endl;
    }

}

DS顺序表–连续操作

题目描述:

建立顺序表的类，属性包括：数组、实际长度、最大长度（设定为1000）

该类具有以下成员函数：

构造函数：实现顺序表的初始化。

插入多个数据的multiinsert(int i, int n, int item[])函数，实现在第i个位置，连续插入来自数组item的n个数据，即从位置i开始插入多个数据。

删除多个数据的multidel(int i, int n)函数，实现从第i个位置开始，连续删除n个数据，即从位置i开始删除多个数据。

编写main函数测试该顺序表类。

输入:

第1行先输入n表示有n个数据，即n是实际长度；接着输入n个数据
第2行先输入i表示插入开始的位置，再输入k表示有k个插入数据，接着输入k个数据
第3行先输入i表示删除开始的位置，再输入k表示要删除k个数据

输出:

顺序表内容包括顺序表的实际长度和数据，数据之间用空格隔开
第1行输出创建后的顺序表内容
第2行输出执行连续插入后的顺序表内容
第3行输出执行连续删除后的顺序表内容

输入样例一

1
2
3

6 11 22 33 44 55 66
2 3 99 88 77
4 5

输出样例一

6 11 22 33 44 55 66 
9 11 99 88 77 22 33 44 55 66 
4 11 99 88 66

参考答案:

#include <iostream>

using namespace std;

#define ok 0
#define error -1

class SeqList {
private:
    int *list;
    int maxsize;
    int size;
public:
    SeqList() {
        maxsize = 1000;
        size = 0;
        list = new int[maxsize];
    }

    ~SeqList() {}

    int list_size() {
        return size;
    }

    int list_insert(int i, int item) {
        i -= 1;
        if (i > size || i < 0) {
            return error;
        }
        if (i == size) {
            list[size++] = item;
            return ok;
        }
        for (int j = size; j >= i; j--) {
            list[j] = list[j - 1];
        }
        list[i] = item;
        size++;
        return ok;
    }

    int list_del(int i) {
        i -= 1;
        if (i >= size || i < 0) {
            return error;
        }
        int temp = list[i];
        size--;
        for (int j = i; j < size; j++) {
            list[j] = list[j + 1];
        }
        return ok;
    }

    int list_get(int i) {
        i -= 1;
        if (i >= size || i < 0) {
            return error;
        }
        return list[i];
    }

    void list_display() {
        cout << size << " ";
        for (int i = 0; i < size; i++) {
            cout << list[i] << " ";
        }
        cout << endl;
    }

};

int main() {
    int n;
    cin >> n;
    SeqList list = *new SeqList();
    for (int i = 1; i <= n; i++) {
        int item;
        cin >> item;
        list.list_insert(i, item);
    }
    list.list_display();

    int i, item;
    cin >> i;
    int t;
    cin >> t;
    int *a = new int[t];
    for (int j = 0; j < t; j++) {
        cin >> item;
        a[j]=item;
    }
    for (int j = t-1; j >= 0; j--) {
        list.list_insert(i, a[j]);
    }
    list.list_display();
    cin >> i >> t;
    for (int j = 0; j < t; j++) {
        cin >> item;
        list.list_del(i);
    }
    list.list_display();

}

DS顺序表之循环移位

题目描述:

顺序表的移位是循环移位，例如顺序表：1，2，3，4，5，6。如果左移1位，即原来的头元素移动到末尾，其它元素向左移1位，变成2，3，4，5，6，1。同理，如果右移1位，即原来的尾元素移动到头，其它元素向右移1位，变成6，1，2，3，4，5。以下是移位的多个例子：

原数据：1，2，3，4，5，6

左移3位：4，5，6，1，2，3，与原数据对比

右移4位：3，4，5，6，1，2，与原数据对比

请编写程序实现顺序表的循环移位操作

输入:

第1行输入n表示顺序表包含的·n个数据
第2行输入n个数据，数据是小于100的正整数
第3行输入移动方向和移动的位数，左移方向为0，右移方向为1
第4行输入移动方向和移动的位数，左移方向为0，右移方向为1
注意：移动操作是针对上一次移动后的结果进行的

输出:

第一行输出创建后，顺序表内的所有数据，数据之间用空格隔开
第二行输出第一次移位操作后，顺序表内的所有数据，数据之间用空格隔开
第三行输出第二次移位操作后，顺序表内的所有数据，数据之间用空格隔开

输入样例一

5
11 22 33 44 55
0 2
1 4

输出样例一

11 22 33 44 55 
33 44 55 11 22 
44 55 11 22 33

参考答案:

#include <iostream>

using namespace std;


void MoveToLeft(int *arr, int n) {
    int temp = arr[0];
    for (int i = 0; i < n - 1; i++) {
        arr[i] = arr[i + 1];
    }
    arr[n - 1] = temp;
}

void MoveToRight(int *arr, int n) {
    int temp = arr[n - 1];
    for (int i = n - 1; i >= 1; i--) {
        arr[i] = arr[i - 1];
    }
    arr[0] = temp;
}

void Move(int *arr, int n, int direct, int move) {
    if (direct == 0) {
        for (int i = 0; i < move; i++) {
            MoveToLeft(arr, n);
        }
    } else {
        for (int i = 0; i < move; i++) {
            MoveToRight(arr, n);
        }
    }
}

void print(int *arr, int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    int *arr = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    print(arr, n);
    int direct, move;

    cin >> direct >> move;
    Move(arr, n, direct, move);
    print(arr, n);

    cin >> direct >> move;
    Move(arr, n, direct, move);
    print(arr, n);
    return 0;
}

Point_Array

题目描述:

上面是我们曾经练习过的一个习题，请在原来代码的基础上作以下修改：1、增加自写的拷贝构造函数；2、增加自写的析构函数；3、将getDisTo方法的参数修改为getDisTo(const Point &p)；4、根据下面输出的内容修改相应的构造函数。

然后在主函数中根据用户输入的数目建立Point数组，求出数组内距离最大的两个点之间的距离值。

输入:

测试数据的组数 t
第一组点的个数
第一个点的 x 坐标 y坐标
第二个点的 x坐标 y坐标
…………

输出:

输出第一组距离最大的两个点以及其距离
………..
在C++中，输出指定精度的参考代码如下：

#include
#include //必须包含这个头文件
using namespace std;
void main( )
{ double a =3.141596;
cout<<fixed<<setprecision(3)<<a<<endl; //输出小数点后3位

输入样例一

输出样例一

Constructor.
Constructor.
Constructor.
Constructor.
The longeset distance is 10.44,between p[1] and p[3].
Distructor.
Distructor.
Distructor.
Distructor.
Constructor.
Constructor.
Constructor.
The longeset distance is 17.03,between p[0] and p[1].
Distructor.
Distructor.
Distructor.

参考答案:

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

class Point {
private:
    double x, y;
public:
    Point() {
        x = 0;
        y = 0;
        cout << "Constructor." << endl;
    }

    Point(double x_value, double y_value) {
        x = x_value;
        y = y_value;
        cout << "Constructor." << endl;
    }

    double getX() {
        return x;
    }

    double getY() {
        return y;
    }

    void setXY(double x1, double y1) {
        x = x1;
        y = y1;
    }

    void setX(double x_value) {
        x = x_value;
    }

    void setY(double y_value) {
        y = y_value;
    }

    double getDisTo(const Point &p) {
        return sqrt(pow(this->x - p.x, 2) + pow(this->y - p.y, 2));
    }


    ~Point() {
        cout << "Distructor." << endl;
    }

};

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        Point *p = new Point[n];

        for (int i = 0; i < n; i++) {
            int x, y;
            cin >> x >> y;
            p[i].setXY(x, y);
        }
        double max = 0;
        int imax = 0, jmax = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double temp = p[i].getDisTo(p[j]);
                if (max < temp) {
                    max = temp;
                    imax = i;
                    jmax = j;
                }
            }
        }
        cout << "The longeset distance is ";
        cout << fixed << setprecision(2) << max;
        cout << ",between p[" << imax << "] and p[" << jmax << "]." << endl;
        delete []p;
    }
    return 0;
}

串应用- 计算一个串的最长的真前后缀

题目描述:

给定一个串，如ABCDAB，则
ABCDAB的真前缀有：{ A, AB,ABC, ABCD, ABCDA }
ABCDAB的真后缀有：{ B, AB,DAB, CDAB, BCDAB }
因此，该串的真前缀和真后缀中最长的相等串为AB，我们称之为该串的“最长的真前后缀”。

试实现一个函数string matched_Prefix_Postfix(string str)，得到输入串str的最长的真前后缀。若不存在最长的真前后缀则输出empty

输入:

第1行：串的个数 n
第2行到第n+1行：n个字符串

输出:

n个最长的真前后缀，若不存在最长的真前后缀则输出empty。

输入样例一

6
a
ab
abc
abcd
abcda
abcdab

输出样例一

empty
empty
empty
empty
a
ab

参考答案:

二叉平衡树练习

题目描述:

对二叉平衡树进行四种操作：

1 D K 表示插入一个新数据，数据为D用于输出，关键值为K用于排序；
2 输出当前树中最大关键值所带的数据，并删除该数据，如果没有这个关键值，则输出0；
3 输出当前树中最小关键值所带的数据，并删除该数据，如果没有这个关键值，则输出0；
4 K 输出关键值为 K 的数据，并删除该数据，如果没有这个关键值，则输出0。

要求必须实现平衡树，不可以使用各类库函数

AVL代码模板参考:

#include<stdio.h>
const int maxn = 1e5 + 10;
struct Node
{
    int key;        // 关键值
    int data;       // 携带的数据
    int left;       // 左子树地址（数组下标）
    int right;      // 右子树地址（数组下标）
    int height;     // 当前结点为根的子树高度
    void Init(){data = key = left = right = height = -1;}
    void Init(int k_, int d_=0){Init(); key = k_; data = d_;}
    Node(){Init();}
    Node(int k_, int d_=0){Init(k_, d_);}
};
 
Node tr[maxn];
int root, tp;  // root标记根节点位置，tp全局结点分配下标
 
inline int UpdateHeight(int now)
{
    // 更新 tr[now] 结点的子树高度，即tr[now].height的值
}
inline int HeightDiff(int now)
{
    // 计算 tr[now] 结点的平衡因子
}
int LL(int an)
{
}
int RR(int an)
{
}
int LR(int an)
{
}
int RL(int an)
{
}
void Insert(int &now, int key, int data=0)
{
    if(now == -1)
    {
        // 传入指针为空，新建结点保存数据
        now = ++ tp;
        tr[now].Init(key, data);
    }
    // 判断插入哪个子树，插入数据，判断平衡因子，做正确旋转，更新高度
}
void Delete(int &now, int key)
{
    if(now == -1) return;
    else if(key < tr[now].key) Delete(tr[now].left, key);
    else if(key > tr[now].key) Delete(tr[now].right, key);
    else
    {
        // 删除当前结点
    }
    // 处理树平衡
}
 
int main()
{
    int n, op, key, data;
    while(scanf("%d", &n) != EOF)
    {
        for(root = tp = -1; n --; )  // 初始化根结点和“内存指针”
        {
            scanf("%d", &op);
            if(op == 1)
            {
            }
            else if(op == 2)
            {
            }
            else if(op == 3)
            {
            }
            else
            {
            }
    }
    return 0;
}

输入:

每组数据第一行n表示有n个操作
接下来n行操作内容

输出:

按操作规则输出对应内容

输入样例一

输出样例一

参考答案:

二叉树的中后序遍历构建及求叶子

题目描述:

按中序遍历和后序遍历给出一棵二叉树，求这棵二叉树中叶子节点权值的最小值。

输入保证叶子节点的权值各不相同。

输入:

测试数据有多组
对于每组测试数据，首先输入一个整数N (1 <= N <= 10000)，代表二叉树有N个节点，接下来的一行输入这棵二叉树中序遍历的结果，最后一行输入这棵二叉树后序遍历的结果
输入一直处理到文件尾(EOF)

输出:

对于每组测试数据，输出一个整数，代表二叉树中叶子节点权值最小值

输入样例一

7
3 2 1 4 5 7 6
3 1 2 5 6 7 4
8
7 8 11 3 5 16 12 18
8 3 11 7 16 18 12 5
1
255
255

输出样例一

1
2
3

1
3
255

参考答案:

冒泡排序

题目描述:

给定一个包含从0到n-1各一次的数组，若使用冒泡排序将其排为升序，问其中需要进行多少次交换

输入:

测试数据有多组，
每组由两行组成：第一行包含正整数n（n <= 5000）; 下一行包含从0到n-1的n个整数的序列。

输出:

对于每组测试数据，
输出交换次数

输入样例一

1 2	10 1 3 6 9 0 8 5 7 4 2

输出样例一

参考答案:

动态数组

题目描述:

一开始未知数组长度，根据要求创建不同类型的指针，并且使用指针创建相应长度的数组，然后再完成不同的要求

若要求创建整数数组，计算数组内所有数据的平均值

若要求创建字符数组，找出数组内的最大字母

若要求创建浮点数数组，找出数组的最小值

要求程序整个过程不能使用数组下标，从数组创建、输入到搜索、比较、计算，到输出都必须使用指针

提示：使用new关键字

输入:

第一行输入t表示有t个测试实例
第二行先输入一个大写字母表示数组类型，I表示整数类型，C表示字符类型，F表示浮点数类型；然后输入n表示数组长度。
第三行输入n个数据
依次输入t个实例

输出:

每个根据不同的数组类型输出相应的结果

输入样例一

3
C 5
A D E B C
I 6
22 55 77 33 88 55
F 4
3.1 1.9 6.5 4.8

输出样例一

E
55
1.9

参考答案:

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        char ch;
        cin >> ch;
        if (ch == 'C') {
            int n;
            cin >> n;
            char *data = new char[n];
            for (int i = 0; i < n; i++) {
                cin >> data[i];
            }
            char max = data[0];
            for (int i = 0; i < n; i++) {
                if (data[i] > max) {
                    max = data[i];
                }
            }
            cout << max << endl;
        } else if (ch == 'I') {
            int n;
            cin >> n;
            int *data = new int[n];
            int avg = 0, sum = 0;
            for (int i = 0; i < n; i++) {
                cin >> data[i];
                sum += data[i];
            }
            avg = sum / n;
            cout << avg << endl;
        } else if (ch == 'F') {
            int n;
            cin >> n;
            double *data = new double[n];
            for (int i = 0; i < n; i++) {
                cin >> data[i];
            }
            double min = data[0];
            for (int i = 0; i < n; i++) {
                if (data[i] < min) {
                    min = data[i];
                }
            }
            cout << min << endl;
        }
    }
    return 0;
}

图的应用之——图的连通

题目描述:

给定一个图的邻接矩阵，请判断该图是否是连通图。连通图：任意两个顶点之间都有路径。

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

第1行输入一个整数k，表示有k个测试数据
第2行输入一个整数n，表示有n个结点
从第3行起到第n+2行输入一个邻接矩阵，其中Matrix[i,j]=1表示第i，j个结点之间有边，否则不存在边。
接下来是第2到第k个测试数据的结点数和邻接矩阵

输出:

输出Yes or No表示图是否是强连通图

输入样例一

2
4
0 1 1 1 
1 0 1 1 
1 1 0 1 
1 1 1 0 
7
0 1 0 0 0 0 0 
0 0 1 1 0 0 0 
1 0 0 0 0 0 0 
1 0 1 0 0 0 0 
0 0 0 0 0 1 1 
0 1 0 0 0 0 0 
0 0 0 1 0 1 0

输出样例一

1
2
3

Yes
No

参考答案:

图的最短路径-STL版

题目描述:

给出一个图的邻接矩阵，输入顶点v，用迪杰斯特拉算法求顶点v到其它顶点的最短路径。

/////////////////////////////////////////////////////////////////////////////////////////////////////////

基本STL的用法：


class Vertex {
public:
    int indexNo;
    string label;
    int distance;
    bool isVisited;
};
void foo() {
    vector<Vertex> v;
    Vertex& x = v[1];      //引用组数v的第1个元素，注意此处的引用&的用法
    x.isVisited = 10;      //修改组数v的第1个元素的isVisited属性值=10
    x.label = "V0";        //修改组数v的第1个元素的label属性值="V0"
}

/////////////////////////////////////////////////////////////////////////////////////
// 代码框架
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//定义无穷大距离
#define MAX_DIS 0x7FFFFF

class Vertex {
public:
    int indexNo;   //顶点索引号：顶点位于顶点数组的下标取值[0,n)
    string label;  //顶点的标签
    int distance;  //顶点到源点的距离
    bool isVisited; //顶点是否已经按Dijkstra算法处理过（不用再处理了）
    vector<int> path; //顶点到源点的路径

    Vertex(int indexNo, const string& label="", int distance=MAX_DIS) {
        this->label = label;
        this->distance = distance;

        this->indexNo = indexNo;
        this->isVisited = false;
    }
    void updatePath(const vector<int>& prePath) {
        this->path = prePath;   //复制源结点到前一个结点的路径
                                //TODO: 增加本结点到路径数组this->path中
    }

    //打印输出本结点信息
    //输入：顶点数组（供查询用）、源结点索引号（顶点数组下标）
    void displayPath(vector<Vertex>& vertexes, int sourceNo) {

        //0-1-5----[0 1 ]
        cout << vertexes[sourceNo].label; //0
        cout << "-";
        cout << this->label; //1

        cout << "-";
        if (this->distance >= MAX_DIS) {
                                    //TODO: 如果源结点到本结点距离无穷大，则（按题目要求）输出-1
            return;
        }
        cout << this->distance; //5
        cout << "----";

        cout << "[";
        int i=0;
        int size = this->path.size();
        for(; i<size; ++i) {
                                    //TODO: 如果源结点到本结点距离<无穷大，则（按题目要求）输出标签和空格
        }
        cout << "]";
        cout << endl;
    }
};

//打印顶点信息，供调试用
ostream& operator<<(ostream& out, const Vertex& v) {
    out << v.indexNo << "_" << v.label << ": " << v.distance << " ";
    return out;
}

/////////////////////////////////////////////////////
class Graph {
public:
    vector<Vertex> vertexes; //顶点数组：存放顶点信息
    vector<vector<int> > adjMat;  //邻接矩阵：存放每对结点距离，若1对结点i,j之间无边相连，则adjMat[i,j]=0
public:

    void printVertexes() {  //用于调试
        int i=0;
        int n = vertexes.size();
        for(; i<n; ++i) {
            cout << vertexes[i];
        }
        cout << endl;
    }

    int getNo(string& label) {
        //TODO： 遍历顶点数组vertexes，找到标签属性=label的顶点索引号
        //并返回。
        int i=0;
        //int n = vertexes.size();


    }
    void readVertexes() {
    //读入每个顶点信息
        int n;
        cin >> n;

        int indexNo=0;
        for(; indexNo<n; ++indexNo) {
            string label;
            //TODO： 读入标签到label变量

            //Vertex(int indexNo, const string& label="", int distance=MAX_DIS)
            //TODO： 创建顶点对象v

            this->vertexes.push_back(v);  //把v加入顶点数组
        }

    }
    void readAdjMat() {
    //读取距离矩阵，并存放成员变量adjMat
        int n = this->vertexes.size();

        int i=0;
        for(; i<n; ++i) {

            vector<int> row;  //创建矩阵的一行对象row
            int j=0;
            for(; j<n; ++j) {
                int dis;
                //TODO: 读取输入的顶点i,j之间的距离，存入变量dis
                //TODO: 将dis插入row
            }

            //TODO: 将矩阵的一行row附加到邻接矩阵adjMat中

        }
    }

    void update(int rootNo) {
    //将顶点rootNo选入visited集合之后，
    //更新与rootNo关联的所有结点（未访问）：到源点的距离、路径信息
        int i=0;
        int n = vertexes.size();

        Vertex& root = vertexes[rootNo];   //获取rootNo对应顶点对象，便于下面代码写作
        int rootDis = root.distance;

        for(; i<n; ++i) {
            Vertex& v = vertexes[i]; //获取当前顶点对象，便于下面代码写作

            if (v.isVisited)
                //TODO:  如果v已经访问过，则pass

            // TODO: 如果rootNo到i 之间没有边，则pass


            //计算顶点i：到源点的新距离
            int newDis = rootDis + this->adjMat[rootNo][i];
            if (newDis < v.distance) {
                v.distance = newDis;  //更新顶点i的距离信息

                //TODO: 更新顶点i的路径信息， 提示：调用v对象的一个方法
            }
        }
    }

    int select() {
    //从未曾访问的顶点集合中，选择距离源点最短的顶点（其索引号为minNo）
    //返回 minNo
        int minDis = MAX_DIS;
        int minNo = -1;

        int i=0;
        int n = vertexes.size();
        for(; i<n; ++i) {
            Vertex& v = vertexes[i];

            //TODO：如果顶点i已经访问过，则pass

            if (v.distance < minDis) {
                //TODO：记录顶点i的距离和编号到minDis、minNo中

            }
        }

        //TODO：检查minNo是否为-1,
        //若是，则返回-1

        //获得有效的顶点编号
        vertexes[minNo].isVisited = true;
        return minNo;
    }

    void readSourceNo() {
    //从输入读取源结点标签，执行Dijikstra算法

        /////////////////////////////////////////////
        //1）读取源点
        string slabel;
        cin >> slabel;

        int sourceNo;  //源结点索引
        //TODO： 调用一个Graph的成员函数返回标签=slabel的顶点索引号
        //并将编号存入sourceNo

        /////////////////////////////////////////////
        //2） 初始化源点
        Vertex& source = vertexes[sourceNo];  //获取源点对象source，便于下面代码写作
        //TODO：设置source的isVisited为true
        //TODO：设置source到源点的距离为0
        //TODO: 设置source到源点的路径为[sourceNo]

        //TODO: 以sourceNo为参数调用update成员函数

        //////////////////////////////////////////////
        //3）Dikstra主算法
        int i=0;
        int n = vertexes.size();
        for(; i<(n-1); ++i) {

            int v;  //当前未访问过的顶点集合中，距离源点的距离最短的顶点索引号为v

            //TODO：调用select方法，并将返回值存入v

            //TODO: v=-1，则退出for循环

            //TODO:将v作为参数，调用update方法
        }

        /////////////////////////////////////////////
        // 4）打印除源点外的其它顶点信息（按顶点索引号顺序打印）
        string sourceLabel = source.label;
        for(i=0; i<n; ++i) {
            //TODO：如果i=sourceNo，则pass

            Vertex& v = vertexes[i];  //获取当前顶点对象v，便于下述代码写作
            //TODO：调用v的一个方法，打印输出源点到顶点v的距离、路径
        }
    }

    void main() {
        readVertexes();  //读取顶点数组
        readAdjMat();    //读取距离矩阵
        readSourceNo();  //读取源点、并执行Dijkstra算法
    }
};


int main() {

    int t;
    cin >> t;

    while (t--) {
        Graph g;
        g.main();
    }

    return 0;
}

输入:

第一行输入t，表示有t个测试实例

第二行输入顶点数n和n个顶点信息

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其它结点如果相连则为距离，无连接则为0，数据之间用空格

隔开。第四行输入v0，表示求v0到其他顶点的最短路径距离

以此类推输入下一个示例

输出:

对每组测试数据，输出：

每行输出v0到某个顶点的最短距离和最短路径

每行格式：v0编号-其他顶点编号-最短路径值—-[最短路径]。没有路径输出：v0编号-其他顶点编号–1。具体请参考示范数据

输入样例一

2
5 0 1 2 3 4
0 5 0 7 15
0 0 5 0 0
0 0 0 0 1
0 0 2 0 0
0 0 0 0 0
0
6 V0 V1 V2 V3 V4 V5
0 0 10 0 30 100
0 0 5 0 0 0
0 0 0 50 0 0
0 0 0 0 0 10
0 0 0 20 0 60
0 0 0 0 0 0
V0

输出样例一

0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]
V0-V1--1
V0-V2-10----[V0 V2 ]
V0-V3-50----[V0 V4 V3 ]
V0-V4-30----[V0 V4 ]
V0-V5-60----[V0 V4 V3 V5 ]

参考答案:

图综合练习–拓扑排序

题目描述:

已知有向图，顶点从0开始编号，求它的求拓扑有序序列。

拓扑排序算法：给出有向图邻接矩阵
1.逐列扫描矩阵，找出入度为0且编号最小的顶点v

2.输出v，并标识v已访问

3.把矩阵第v行全清0

重复上述步骤，直到所有顶点输出为止

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入:

第一行输入一个整数t，表示有t个有向图
第二行输入n，表示图有n个顶点
第三行起，输入n行整数，表示图对应的邻接矩阵
以此类推输入下一个图的顶点数和邻接矩阵

输出:

每行输出一个图的拓扑有序序列

输入样例一

2
5
0 1 0 1 1
0 0 1 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
7
0 0 0 0 0 0 0
1 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

输出样例一

1
2
3

0 1 3 2 4 
4 6 5 1 3 2 0

参考答案:

图综合练习–构建邻接表

题目描述:

已知一有向图，构建该图对应的邻接表。

邻接表包含数组和单链表两种数据结构，其中每个数组元素也是单链表的头结点，数组元素包含两个属性，属性一是顶点编号info，属性二是指针域next指向与它相连的顶点信息。

单链表的每个结点也包含两个属性，属性一是顶点在数组的位置下标，属性二是指针域next指向下一个结点。

输入:

第1行输入整数t，表示有t个图
第2行输入n和k，表示该图有n个顶点和k条弧。
第3行输入n个顶点。
第4行起输入k条弧的起点和终点，连续输入k行
以此类推输入下一个图

输出:

输出每个图的邻接表，每行输出格式：数组下标顶点编号-连接顶点下标-……-^，数组下标从0开始。
具体格式请参考样例数据，每行最后加入“^”表示NULL。

输入样例一

1
5 7
A B C D E
A B
A D
A E
B D
C B
C E
E D

输出样例一

0 A-1-3-4-^
1 B-3-^
2 C-1-4-^
3 D-^
4 E-3-^

参考答案:

完全二叉树的根

题目描述:

有一棵n个节点的完全二叉树，存储着 1~n 的值。

有n(n-1)(n-2)条关于这颗树的信息，每条信息，由一个四元组组成(i,j,k,0/1)(i≠j≠k)，均不完全一样。

若四元组最后一个元素为0，表示值为k的这个节点不是值为 i 的结点和值为 j 的结点的最近公共祖先，

若四元组最后一个元素为1，则反之。

基于给出的信息，求根结点的值。

输入:

一行一个整数n (3 ≤ n ≤ 8)
接下来n(n-1)(n-2)行，每行四个整数表示四元组(i,j,k,0/1)(i≠j≠k)

输出:

一行一个整数，表示树根节点的值

输入样例一

输出样例一

参考答案:

广度优先搜索-STL对象版

题目描述:

广度优先搜索-STL对象版

给出一个图的邻接矩阵，对图进行广度优先搜索，从顶点0开始

注意：图n个顶点编号从0到n-1

/////////////////////////////////////////////////////////////////////////////////////////////////////////

基本STL的用法：

1）

vector<int>::push_back(1); //将1增加到数组尾部
vector<E>::push_back(e); //将类型为E的一个对象e增加到数组尾部.其中类型E可以自行定义，如Vertex类，int类等。
2.1)
vector<int> vec; 
int x = vec[1];  //读取组数v（索引从0开始）的第1个元素
2.2)
vector<int> v; 
int& x = v[1]; //引用组数v的第1个元素，注意此处的引用&的用法
 x = 10; //修改组数v的第1个元素为10
3.1）
queue<int> my_queue;
my_queue.push(0); //将0增加到队列尾部
3.2）
int root = my_queue.front(); //读取队列的首元素
my_queue.pop(); //弹出队列的首元素

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

代码框架如下：

输入:

输出:

每行输出一个图的广度优先搜索结果，结点编号之间用空格隔开

输入样例一

输出样例一

1 2	0 2 3 1 0 3 4 2 1

参考答案:

成绩查询（指针运算）

题目描述:

已知一组学生成绩，然后根据输入的序号查询成绩

要求：

1. 使用一个整数数组存储学生成绩

2. 使用一个指针指向数组中间元素

3. 使用++和--运算符，求出数组中间元素的前一个成绩和后一个成绩

4. 输入一个序号，然后计算这个序号的元素和中间元素的距离，然后使用指针去访问

例如有11个学生，指针指向中间的学生也就是第6个学生，若输入序号3，即查询第3个学生的成绩，第3和第6之间距离为3，那么指针应该怎么运算呢？？？

5. 整个程序除了输入时可以使用数组下标，其他部分都不能使用，都必须使用指针进行访问，且只能定义一个指针变量。

输入:

第一行输入t表示有t个测试实例
第二行先输入n，表示有n个学生，然后再输入n个成绩（正整数）
第三行输入1个序号，表示要查询成绩的学生的序号。
依次输入t个实例
按自然意义，序号是从1开始计算
提示：在数组中是从……..

输出:

对于每个测试实例：
第一行输出数组中间元素的前一个成绩和后一个成绩(若为偶数，取中间右边的数为中间数）
第二行根据序号输出1个成绩

输入样例一

2
7 66 99 88 44 77 33 11
2
11 60 80 50 20 90 35 70 40 10 95 30
9

输出样例一

参考答案:

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        int *arr = new int[n];
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int *p = arr;
        int mid = (n / 2);
        while (mid--) {
            p++;
        }
        cout << *(p - 1) << " " << *(p + 1) << endl;
        int find;
        cin >> find;
        p = arr;
        while (find--) {
            p++;
        }
        cout << *(p - 1) << endl;
    }
}

拓扑排序-STL版

题目描述:

已知有向图，顶点从0开始编号，求它的求拓扑有序序列。

拓扑排序算法：给出有向图邻接矩阵
1.逐列扫描矩阵，找出入度为0且编号最小的顶点v

2.输出v，并标识v已访问

3.把矩阵第v行全清0

重复上述步骤，直到所有顶点输出为止

/////////////////////////////////////////////////
// STL::vector基本用法
1)
vector<int>::push_back(1); //将1增加到数组尾部
vector<E>::push_back(e); //将类型为E的一个对象e增加到数组尾部.其中类型E可以自行定义，如Vertex类，int类等。
2.1)
vector<int> vec; 
int x = vec[1];  //读取组数v（索引从0开始）的第1个元素
2.2)
vector<int> v; 
int& x = v[1]; //引用组数v的第1个元素，注意此处的引用&的用法
 x = 10; //修改组数v的第1个元素为10

vector<vector<int> > adjMat; //声明一个矩阵对象adjMat
vector<int> row;  //声明一个vector（动态数组）对象row表示矩阵的一行
int j=0;
for(; j<n; ++j) {
    int edge;
    cin >> edge;
    row.push_back(edge); //将边信息增加到数组row的最后
}

this->adjMat.push_back(row); //将row增加到数组adjMat的最后

//////////////////////////////////////////////////////////////////////////////////////////

// 参考代码框架

#include <iostream>
#include <vector>
using namespace std;
class Graph {
public:
    vector<bool> isFinished;      //索引号所指示的顶点是否已处理过
    vector<vector<int> > adjMat;  //邻接矩阵
    int n;                        //顶点数 as 成员变量
public:
    void readAdjMatrix() {
        //从输入读入邻接矩阵，存入this->adjMat
        cin >> this->n;           //顶点数
        int i=0;
        for(; i<n; ++i) {
            //TODO：设置this->isFinished数组：每个顶点未曾访问过
            //提示：调用vector::push_back方法
            vector<int> row;
            int j=0;
            for(; j<n; ++j) {
                int edge;
                cin >> edge;    //读入顶点对i,j之间是否有一条边
                //TODO：将边信息增加入row
            }
            //TODO：将row增加入this->adjMat
            //提示：以row为参数，调用adjMat的push_back方法
        }
    }
    bool isZeroInDegrees(int vertexNo) {
    //判定顶点vertexNo是否没有入度
        int i=0;
        //this->adjMat[i][vertexNo] == 0
        //表示顶点i与vertexNo之间没有边相连
        for(; i<n && this->adjMat[i][vertexNo] == 0; ++i);
        //TODO：返回true if 顶点vertexNo没有入度; false [otherwise]
    }
    int select() {
    //从所有顶点中，选出一个顶点i，满足：
    //1) i没有处理过，即isFinished[i]=false
    //2) i的入度为0
        int i = 0;
        for (; i < n; ++i) {
            //TODO：若顶点i的已经处理过，则pass
            //TODO：若顶点度>0，则pass
            //提示：调用isZeroInDegrees
            //TODO: 设置顶点i已经处理过，即isFinished[i]为正确值
            //TODO: 返回i
        }
        //TODO: 返回-1, 表示未找到满足1)+2)条件的顶点
    }
    void update(int rootNo) {
    //更新顶点rootNo的出弧，即将顶点rootNo从图中断开
        int j=0;
        for(;j<n; ++j) {
            //TODO： 设置adjMat[rootNo][j]为0
        }
    }
    /////////////////////////////////////////////////////
    // 拓扑排序主算法
    void topologySort() {
        int i=0;
        for(; i<n; ++i) {  //遍历n次：即按拓扑序，依次选择（排出）n个顶点
            int root;  // 声明顶点索引号（编号）用于存放本次选出的顶点
            //TODO： 调用select方法，并将其返回值存入root
            //TODO： 若root=-1，则break;
            // root=-1表示没有可以排出的顶点
            //TODO: 以root为参数，调用update方法
            //TODO：输出当前选出的顶点root 和一个空格
        }
        //TODO：输出一行
    }
    void main() {
        readAdjMatrix();
        topologySort();
    }
};
int main() {
    int t;
    cin >> t;
    while (t--) {
        Graph g;
        g.main();
    }
    return 0;
}

输入:

输出:

每行输出一个图的拓扑有序序列

输入样例一

2
5
0 1 0 1 1
0 0 1 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
7
0 0 0 0 0 0 0
1 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

输出样例一

1 2	0 1 3 2 4 4 6 5 1 3 2 0

参考答案:

月份查询（指针数组）

题目描述:

已知每个月份的英文单词如下，要求创建一个指针数组，数组中的每个指针指向一个月份的英文字符串，要求根据输入的月份数字输出相应的英文单词

1月 January

2月 February

3月 March

4月 April

5月 May

6月 June

7月 July

8月 Aguest

9月 September

10月 October

11月 November

12月 December

输入:

第一行输入t表示t个测试实例
接着每行输入一个月份的数字
依次输入t行

输出:

每行输出相应的月份的字符串，若没有这个月份的单词，输出error

输入样例一

输出样例一

May
November
error

参考答案:

#include <iostream>

using namespace std;

int main() {
    char *month[12] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October",
                       "November", "December"};
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;
        if (m > 12 || m < 1) {
            cout << "error" << endl;
        } else {
            cout << month[m - 1] << endl;
        }
    }
}

火车站(stack)

题目描述:

火车站只有一条铁路，所有的火车都停在那里。所以所有的火车都是从一边进站，从另一边出站。如果A列先进入铁路，然后B列在A列离开之前进入铁路，那么A列在B列离开之前不能离开。下图说明了问题所在。车站里最多有9列火车，所有的火车都有一个ID（编号从1到N），火车按照O1的顺序进入火车，火车是否可以按照O2的顺序驶出。

输入:

输入包含几个测试用例。

每个测试用例由一个整数（列车数）和两个字符串组成。两个字符串分别为列车入站顺序和列车出站顺序。

输出:

如果不能按照指定顺序出站，输出“No”。

如果可以，输出“Yes”，然后输出出入站顺序（对于进入铁路的列车，应输出“in”，对于出铁路的列车，应输出“out”）。在每个测试用例之后打印一行包含“FINISH”。

输入样例一

输出样例一

Yes
in
in
in
out
out
out
FINISH
No
FINISH
Yes
in
out
in
out
in
out
FINISH

参考答案:

矩阵左转

题目描述:

输入一个2*3的矩阵，将这个矩阵向左旋转90度后输出

比如现在有2*3矩阵：

1 2 3

4 5 6

向左旋转90度后的矩阵变为：

3 6

2 5

1 4

要求：除了矩阵创建和数据输入可以使用数组和数组下标的方法，其他过程对矩阵的任何访问都必须使用指针

提示：m行n列的二维矩阵，第i行第j列的元素与首元素的距离为i*n+j，序号从0开始计算

输入:

第一行输入t表示有t个测试实例
连续两行输入一个2*3的矩阵的数据
依次输入t个实例

输出:

依次输出左转后的矩阵结果
在输出的每行中，每个数据之间都用空格隔开，最后一个数据后面也带有空格

输入样例一

输出样例一

参考答案:

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        int m = 2, n = 3;
        int a[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cin >> a[i][j];
            }
        }
        int *p = a[0];
        for (int i = n-1; i >= 0; i--) {
            for (int j = 0; j < m; j++) {
                cout << *(p + j * n + i)<<" ";
            }
            cout << endl;
        }
    }
}

稳定排序

题目描述:

给出二元数组a[MAXN][2]，按第一个关键值从小到大排序后输出，要求第一关键值相同情况下不改变原数组次序

输入:

每组数据第一行为整数n，1 <= n <= 10 ^ 5。
接下来n行每行两个整数空格隔开。

输出:

输出排序后的数组

输入样例一

输出样例一

参考答案:

货币套汇（图路径）

题目描述:

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，1法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。给定n种货币c1 ,c2 ,... ,cn的有关兑换率，试设计一个有效算法，确定货币间是否存在套汇的可能性。

提示：判断图上是否出现正环,即环上所有的边相乘大于1

输入:

第一行：测试数据组数
每组测试数据格式为：
第一行：正整数n (1< =n< =30)，正整数m，分别表示n种货币和m种不同的货币兑换率。
2n+1行，n种货币的名称。
n+2n+m+1行，每行有3 个数据项ci，rij 和cj ，表示货币ci 和cj的兑换率为 rij。

输出:

对每组测试数据，如果存在套汇的可能则输出YES
如果不存在套汇的可能，则输出NO。

输入样例一

2
3 3
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3 6
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

输出样例一

1
2

YES
NO

参考答案:

道路建设 (Ver. I)

题目描述:

有N个村庄，编号从1到N，你应该建造一些道路，使每个村庄都可以相互连接。

两个村A和B是相连的，当且仅当A和B之间有一条道路，或者存在一个村C使得在A和C之间有一条道路，并且C和B相连。

现在一些村庄之间已经有一些道路，你的任务就是修建一些道路，使所有村庄都连通起来，并且所有道路的长度总和是最小的。

输入:

测试数据有多组

第一行是整数N（3 <= N <= 100），代表村庄的数量。然后是N行，其中第i行包含N个整数，这些N个整数中的第j个是村庄i和村庄j之间的距离（距离是[1,1000]内的整数）。

然后是整数Q（0 <= Q <= N *（N + 1）/ 2），接下来是Q行，每行包含两个整数a和b（1 <= a <b <= N），代表着村庄a和村庄b之间的道路已经建成。

输出:

对于每组测试数据

输出一个整数，表示要构建的道路的长度总和最小值

输入样例一

输出样例一

参考答案:

文章作者: magic-H

文章链接: https://magic-h.top/25737.html

数据结构