笔试时间：2024年07月17日 暑期实习

历史笔试传送门：2023秋招笔试合集

第一题

题目

对于一个文件系统，第一行输入所有的父目录名称，第二行输入所有的子目录/文件名称，第三行输入待查询的文件或目录名称。对于查询的目录或文件名，如果存在子目录或文件，需要按输入的顺序，按层级输出所有的子目录和文件。“/”表示根目录，没有父目录。

输入描述

第一行是一个由所有的父目录名称组成的字符串，按空格分开。

第二行是对应父目录的所有子目录或文件名组成的字符串，按空格分开。

第三行是查询的文件名或目录名。

输出描述

按输入的顺序逐层输出所有的子目录和文件，包括查询的目录/文件本身。

样例输入一

/ / / home usr

home opt env usr 1.log

home

样例输出一

home usr 1.log

查询的home目录包含usr子目录，usr下有一个1.log文件，按顺序输出。

样例输入二

/ / / home usr

home opt env usr 1.log

env

样例输出二

env

env没有下挂的文件或子目录，直接输出查询本身。

参考题解

通过队列，将输入的查询入队，然后依次将可能存在的子文件或目录入队，直到队列为空。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <queue>
#include <vector>
#include <sstream>
using namespace std;

int main() {
    string parentDirsInput, subDirsInput, find;
    getline(cin, parentDirsInput);
    getline(cin, subDirsInput);
    getline(cin, find);
    
    stringstream ssParent(parentDirsInput), ssSub(subDirsInput);
    string temp;
    vector<string> parentDirs, subDirs;
    
    while (ssParent >> temp) {
        parentDirs.push_back(temp);
    }
    while (ssSub >> temp) {
        subDirs.push_back(temp);
    }
    
    int n = parentDirs.size();
    queue<string> queue;
    queue.push(find);
    
    while (!queue.empty()) {
        string str = queue.front();
        queue.pop();
        
        for (int i = 0; i < n; ++i) {
            if (parentDirs[i] == str) {
                queue.push(subDirs[i]);
            }
        }
        
        cout << str;
        if (!queue.empty()) cout << " ";
    }
    
    return 0;
}

Java：[此代码未进行大量数据的测试，仅供参考]

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    String[] parentDirs = sc.nextLine().split(" ");
    String[] subDirs =sc.nextLine().split(" ");
    String find = sc.nextLine();
    int n = parentDirs.length;
    sc.close();
    Queue<String> queue = new LinkedList<>();
    queue.offer(find);
    while(!queue.isEmpty()){
        String str = queue.poll();
        for (int i = 0; i < n; i++) {
            if(parentDirs[i].equals(str)){
                queue.offer(subDirs[i]);
            }
        }
        System.out.print(str);
        if(!queue.isEmpty()) System.out.print(" ");
    }
}

Python：[此代码未进行大量数据的测试，仅供参考]

from queue import Queue

def main():
    parent_dirs = input().split()
    sub_dirs = input().split()
    find = input()
    
    n = len(parent_dirs)
    queue = Queue()
    queue.put(find)
    
    while not queue.empty():
        str = queue.get()
        for i in range(n):
            if parent_dirs[i] == str:
                queue.put(sub_dirs[i])
        print(str, end="")
        if not queue.empty():
            print(" ", end="")

if __name__ == "__main__":
    main()

第二题

题目

一组n个软件和k（k < (n*(n - 1)/2)）个依赖关系，若干组查询，查询两个软件的前者是否是后者的直接依赖或间接依赖。（对于[a,b]判断a是否是b的前驱节点）。

输入描述

第一行输入两个正整数n和d ，代表软件的个数和依赖关系。

后面d行输入相应的依赖关系。

下一行输入一个正整数q，代表查询的组数。之后q行输入相应的查询。

输出描述

第一行输出q。

之后q行每行输出一个正整数，如果是依赖关系，输出1，否则输出0。

样例输入

3 3

0 1

1 2

0 2

2

1 0

0 1

样例输出

2

0

1

参考题解

判断是否能构成DAG(有向无环图)。

C++：[此代码未进行大量数据的测试，仅供参考]

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

bool** graph;
int n;

bool isDependency(int start, int end) {
    if (graph[start][end]) return true;
    for (int i = 0; i < n; ++i) {
        if (graph[start][i] && i != start) {
            if (isDependency(i, end)) return true;
        }
    }
    return false;
}

int main() {
    cin >> n;
    int d;
    cin >> d;
    
    vector<pair<int, int>> dependencies(d);
    for (int i = 0; i < d; ++i) {
        cin >> dependencies[i].first >> dependencies[i].second;
    }
    
    int q;
    cin >> q;
    
    vector<pair<int, int>> queries(q);
    for (int i = 0; i < q; ++i) {
        cin >> queries[i].first >> queries[i].second;
    }
    
    graph = new bool*[n];
    for (int i = 0; i < n; ++i) {
        graph[i] = new bool[n];
        memset(graph[i], false, n * sizeof(bool));
        graph[i][i] = true;
    }
    
    for (const auto& dependency : dependencies) {
        int i = dependency.first;
        int j = dependency.second;
        graph[i][j] = true;
    }
    
    cout << q << endl;
    for (const auto& query : q