1. 将答案整理到一个Word文档中：
    • 我将写好答案，可能会包含手写示意图拍照插入。
    • Word文档的命名为 学号+姓名。

一、概念题

1. 试述数据结构研究的三个方向的内容：逻辑结构、数据的存储结构和数据的运算

  • 逻辑结构：逻辑结构是指数据元素之间的关系，它不依赖于计算机的存储结构而存在，常见的逻辑结构包括集合、线性结构、树形结构和图形结构。

  • 数据的存储结构：存储结构是指数据在计算机中的实际存储形式。常见的存储结构包括顺序存储、链式存储、索引存储和散列存储。

  • 数据的运算：数据运算是指在特定数据结构上进行的操作，如插入、删除、查找、排序、合并等。每种数据结构支持的运算方式不同，效率也不一样。

2. 试述集合、线性结构、树形结构和图形结构4种常用数据结构的特性

  • 集合：数据元素之间除了“同属于一个集合”的关系外，数据元素之间无其他关系，彼此关系松散。

  • 线性结构：数据元素之间存在“一对一”的关系，例如链表和队列。

  • 树形结构：数据元素之间存在“一对多”的关系，例如二叉树，每个节点都可以有多个子节点。

  • 图形结构：数据元素之间存在“多对多”的关系，例如图，任何两个顶点之间可以有多条边相连。

3. 示意图：

  • 顺序存储结构：
1
a1 -> a2 -> a3 -> ... -> an
  • 链式存储结构：
1
[a1 |  ] -> [a2 |  ] -> [a3 |  ] -> ... -> [an |  ]

4. 逻辑结构的二元组定义式

  • B=(D,R)其中D={k1,k2,k3,…k9}
  • R={ < k1,k3 >,< k1,k8 >,< k2,k3 >,< k2,k4 >,< k2,k5 >,< k3,k9 >,< k4,k6 >,< k4,k7 >,< k5,k6 >,< k8,k9 >,< k9,k7 >}

6. 数学表达式的排序

将以下表达式按从小到大的顺序排列：

1/log2n < 2^100 < log2(log2n) < log2n < n^1/2 < n^2/3 < n < nlog2n < n^3/2 < n^log2n < (4/3)^n < (3/2)^n < n! < n^n

7. 各小题的答案

  1. n-1
  2. N-1
  3. N-1
  4. N*(n-1)/2
  5. N
  6. N^1/2
  7. 1100
  8. Log3n

三、上机实践

题2：代码解析与优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;

string a;
int n, x, res, power = 1;

int main() {
    int i, j, k;
    cin >> a >> x;
    
    for (i = 0; i < a.length(); i++) {
        res += a[i] * power;
        power *= x;
    }
    
    cout << res << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        int x = scanner.nextInt();
        int res = 0;
        int power = 1;

        for (int i = 0; i < a.length(); i++) {
            res += a.charAt(i) * power;
            power *= x;
        }

        System.out.println(res);
    }
}

这段代码的功能是将输入字符串 a 按位乘以给定的基数 x 的权值，最终求出加权和并输出。