18级数据结构与算法分析期末试卷

问题 A: 有向图的出度

题目描述

给你一个有向图,它顶点用大写字母表示,它的序号从A开始,请你编程找出有向图的所有出度为0的顶点,按照字典序输出所有出度为0的顶点名称。

输入

有若干个输入案例,每个案例的第一行有两个整数n、e(1<=n<=26),n表示图中的顶点数,e表示有向边的条数,n、e都为0时表示结束。接着有e行,每行两个大写字母v1、v2,表示从顶点v1到v2有一条有向边连接。顶点的序号从A开始。

输出

每个案例输出一行,按照字典序输出所有出度为0的顶点名称。

样例输入

4 5
A B
A D
A C
D C
D B
3 2
B C
B A
0 0

样例输出

Case 1:B C
Case 2:A C

AC代码:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int index = 1;
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            if (m == 0 && n == 0) {
                break;
            }
            char[][] arr = new char[m][m];
            for (int i = 0; i < n; i++) {
                char a, b;
                a = sc.next().charAt(0);
                b = sc.next().charAt(0);
                arr[a - 65][b - 65] = 1;
            }
            ArrayList<String> l = new ArrayList<String>();
            for (int i = 0; i < m; i++) {
                int j = 0;
                for (j = 0; j < m; j++) {
                    if (arr[i][j] == 1) {
                        break;
                    }
                }
                if (j >= m) {
                    l.add((char) (i + 65) + "");
                }
            }

            System.out.print("Case " + (index++) + ":");
            for (int i = 0; i < l.size() - 1; i++) {
                System.out.print((l.get(i)) + " ");
            }
            System.out.println(l.get(l.size() - 1));
        }
    }

}

问题 B: 二叉树中结点的孩子

题目描述

二叉树的存储可以用顺序存储和链式存储来完成。现在给你顺序存储的二叉树,请你转化为链式存储,输出某结点的孩子情况。

输入

输入有若干个案例,每个案例两行,第一行是一个按顺序存储的二叉树,如果结点处空用半角的‘.’代替,第二行是要查询的结点。

输出

输出结点的孩子情况

样例输入

ABCDEFGHIJKL
E
A.B...C.......D
C
ABCD.EFG
D
T
T

样例输出

Case 1:E的左孩子为J,右孩子为K
Case 2:C仅有右孩子D
Case 3:D仅有左孩子G
Case 4:T是叶子

AC代码:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int index = 1;
        while (sc.hasNext()) {
            String str = sc.next();
            char c = sc.next().charAt(0);
            char[] arr = str.toCharArray();
            char ar = '0', br = '0';
            System.out.print("Case " + (index++) + ":");
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] == c) {
                    int a = 0;
                    int b = 0;
                    if (2 * i + 1 < arr.length) {
                        if (arr[2 * i + 1] != '.') {
                            a = 1;
                            ar = arr[2 * i + 1];
                        }
                    }
                    if (2 * i + 2 < arr.length) {
                        if (arr[2 * i + 2] != '.') {
                            br = arr[2 * i + 2];
                            b = 1;
                        }
                    }
                    if (a == 1 && b == 1) {
                        System.out.print(arr[i] + "的左孩子为" + ar);
                        System.out.println(",右孩子为" + br);
                    } else if (a == 1 && b == 0) {
                        System.out.println(arr[i] + "仅有左孩子" + ar);
                    } else if (a == 0 && b == 1) {
                        System.out.println(arr[i] + "仅有右孩子" + br);
                    } else {
                        System.out.println(arr[i] + "是叶子");
                    }
                    break;
                }
            }
        }
    }
}

问题 C: 哈夫曼树

题目描述

给出n个有权值的叶结点,用这些结点生成哈夫曼树,求这棵树的带权路径长度(即这棵树的权)。

输入

输入有若干组,每组第一行输入一个整数n(2<=n<=30),第二行输入n个叶结点的权值(叶结点权值不超过100)。

输出

输出哈夫曼树的带权路径长度。

样例输入

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

样例输出

49
3
133

AC代码:

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            Queue<Integer> q = new PriorityQueue<Integer>();
            for (int i = 0; i < m; i++) {
                q.add(sc.nextInt());
            }
            int count = 0;
            while (q.size() != 1) {
                int a = q.poll();
                int b = q.poll();
                count += (a + b);
                q.add(a + b);
            }
            System.out.println(count);
        }
    }
}

问题 D: 二分查找

这题不用二分也能过

题目描述

某单位组织了一场业务考试。参加考试的人数为N(100<=N<=900)。成绩出来后,员工可以通过准考证号查询成绩。现给出准考证号,请输出此准考证号对应的成绩。

输入

输入只有一个案例。第一个数是M,表示有M条成绩。接下来是M条成绩(成绩格式是准考证号、成绩,准考证号已按从低到高排好序)。然后是一个正整数N,表示要进行N次查询,后面是N个准考证号。

输出

如果找到输出相应的成绩,否则输出“未查到”。

样例输入

12
573220001 71
573220002 71
573220003 57
573220004 0
573220005 58
573220006 86
573220007 71
573220008 0
573220009 72
573220010 59
573220011 78
573220012 100
6
573220002
573220007
673220011
573220010
773220033
573220012

样例输出

71
71
未查到
59
未查到
100

AC代码:

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            ArrayList<Item> list = new ArrayList<Item>();
            for (int i = 0; i < m; i++) {
                list.add(new Item(sc.next(), sc.next()));
            }
            int n = sc.nextInt();
            for (int i = 0; i < n; i++) {
                String str = sc.next();
                int j = 0;
                for (j = 0; j < list.size(); j++) {
                    if (list.get(j).s1.equals(str)) {
                        System.out.println(list.get(j).s2);
                        break;
                    }
                }
                if (j >= list.size()) {
                    System.out.println("未查到");
                }
            }
        }
    }
}

class Item {
    String s1;
    String s2;

    public Item(String s1, String s2) {
        this.s1 = s1;
        this.s2 = s2;
    }
}

问题 E: 最短路径

题目描述

对于给定的有向图及两个图中的顶点,请实现一个函数,分别判断这两个顶点之间是否有路径,并打印包含这两个顶点的最短路径上的权值和。

输入

有多组测试数据,每组先输入m和n,表示m个顶点,n条边,接下来n行,每行表示一条边的两个顶点和权值。再一个整数p,接下来输入p行每行起点x和终点y,计算起点到终点的最短路径。(起点可能是编号1,也可能是编号2,任意编号都可以作为起点的)

输出

根据输入信息输出起点到达终点最短路径。

样例输入

6 8
0 5 100
0 2 10
0 4 30
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60
3
1 4
1 5
1 3
6 11
0 1 50
0 2 10
0 4 45
1 4 10
1 2 15
2 0 20
2 3 15
3 1 20
3 4 35
4 3 30
5 3 40
1
3 4

样例输出

1->4无路径
1->5最短路径是65
1->3最短路径是55
3->4最短路径是30

AC代码:

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            int[][] map = new int[100][100];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < m; j++) {
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
            for (int i = 0; i < n; i++) {
                map[sc.nextInt()][sc.nextInt()] = sc.nextInt();
            }
            Graph g = new Graph(m, n, map);
            int a = sc.nextInt();
            for (int i = 0; i < a; i++) {
                int c = sc.nextInt();
                int d = sc.nextInt();
                g.dijkstra(c, d);
            }
        }
    }
}

class Graph {
    private int[][] map;
    private int m;
    private int[] dist;

    public Graph(int m, int n, int[][] map) {
        this.m = m;
        this.map = map;
        this.dist = new int[m];
    }

    public void dijkstra(int v0, int d) {
        boolean[] s = new boolean[m];
        for (int i = 0; i < m; i++) {
            s[i] = false;
            dist[i] = map[v0][i];
        }
        dist[v0] = 0;
        s[v0] = true;
        int v = 0;
        for (int i = 1; i < m - 1; i++) {
            int min = Integer.MAX_VALUE;
            for (int w = 0; w < m; w++) {
                if (!s[w] && dist[w] < min) {
                    v = w;
                    min = dist[w];
                }
            }
            s[v] = true;
            for (int j = 0; j < m; j++) {
                if (!s[j] && (min + map[v][j] < dist[j]) && map[v][j] != Integer.MAX_VALUE) {
                    dist[j] = min + map[v][j];
                }
            }
        }
        if (dist[d] != Integer.MAX_VALUE) {
            System.out.println(v0 + "->" + d + "最短路径是" + dist[d]);
        } else {
            System.out.println(v0 + "->" + d + "无路径");
        }
    }
}

问题 F: 快速排序之路

题目描述

给你n个数,分成K组,每组以第一人为VIP数据,用快速排序的方法,让小的在VIP前,大的在VIP后。请你编程完成。

例如:

10 2

4 2 3 9 8 7 5 6 0 -1

将输入数据分为两组(每组10/2个数,除不尽时余下的是最后一组),第一组为4 2 3 9 8.第二组为7 5 6 0 -1。每一组数据进行一次快速排序后:

第一组数据为3 2 4 9 8,第二组为:-1 5 6 0 7。最终输出3 2 4 9 8 -1 5 6 0 7即可!

输入

有多组测试数据,每组先输入2个整数n和K,接下来输入n整数。

输出

输出处理后的序列

样例输入

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

样例输出

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

AC代码:

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
#define MAX 1000005
int ar[MAX];
int par(int arr[], int low, int high) {
    int i = low;
    int j = high;
    int x = arr[i];
    while(i < j) {
        while(i < j && arr[j] >= x) {
            j--;
	}
        if(i < j) {
            arr[i] = arr[j];
            i++;
        }
        while(i < j && arr[i] < x) {
            i++;
        }
        if(i < j) {
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = x;
    return i;
}

void sort(int arr[],int low,int high) {
    if(low < high) {
        int index = par(arr, low, high);
        return;
    }
}
int main() {
    int m ,n;
    while(cin >> m >> n) {
        memset(ar, 0, sizeof(ar));
        for(int i = 0; i < m; i++) {
            cin >> ar[i];
        }
        int a = m / n;
        for(int i = 0; i < m; i += a) {
            if(i + a - 1 > m) {
                break;
            }
            sort(ar,i, i + a - 1);
        }
        for(int i = 0; i < m; i++) {
            cout << ar[i] << " ";
        }
        cout << endl;
    }
}

本文由 罗罗 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.lwjppz.cn /archives/datastructure-algorithm-analysis-of-grade-18
最后更新于:2020-02-09 12:03:05

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×