ECNU 2024~2025学年数据结构期末试题

一、多项选择题（5分/题x10题=50分）
下列关于线性表的说法中，正确的有：
- 顺序表适合随机访问
- 链表可以动态分配内存
- 单链表可以直接访问任意节点
- 顺序表在插入和删除时效率较低
- ✔️ 顺序表（如数组）在内存中是连续存储的，故可以进行随机访问
- ✔️ 链表的节点通常是在程序运行时根据需要动态创建的
- ❌ 单链表不支持随机访问，必须从头指针开始，沿着指针链逐个向后遍历
- ✔️ 在顺序表中插入或删除一个元素时，为了保持内存的连续性，通常需要移动大量元素，相比链表效率较低
下列操作中，可能导致栈溢出的有：
- 递归过深
- 栈内存不足
- 栈空时进行出栈操作
- 入栈时超出栈容量
- ✔️
- ✔️
- ❌ 这种情况会导致栈下溢(Stack Underflow)，而不是栈溢出
- ✔️
以下关于哈希表的说法，正确的有：
- 哈希表的查找效率与装载因子有关
- 哈希冲突可以通过开放地址法解决
- 哈希表适用于区间查询
- 哈希函数的设计会影响哈希表性能
- ✔️ 装载因子 = 已保存的元素个数 / 哈希表长度。装载因子越大，说明表越满，发生哈希冲突的概率就越高
- ✔️
- ❌ 哈希表的特点是无序性，因此在查找特定值时非常快，但在进行区间查询时，哈希表通常需要全表扫描，效率极低
- ✔️
在二叉树中，下列情况可能导致树的高度增加的有：
- 插入一个叶子节点
- 删除一个度为 $1$ 的节点
- 插入一个非叶子节点
- 删除一个叶子节点
- ✔️
- ❌ 删除度为 $1$ 的节点通常是将其子树向上移动（挂到原父节点上），这会使该分支的长度减小 $1$ ，不会导致树高增加。
- ✔️
- ❌ 删除叶子节点如果是处于整棵树最深层的唯一叶子节点，树的高度会减小；否则高度不变。
以下关于排序算法的说法中，正确的有：
- 快速排序的平均时间复杂度是 $O(n\log n)$
- 冒泡排序是一种稳定排序
- 堆排序可以在 $O(1)$ 空间复杂度下完成
- 希尔排序是一种基于插入排序的改进算法
下列与图的表示相关的描述正确的有：
- 邻接矩阵适用于稠密图
- 邻接表适用于稀疏图
- 邻接矩阵的存储空间复杂度是 $O(|V|^2)$
- 邻接表的存储空间复杂度是 $O(|V|+|E|)$ （注： $|V|$ 和 $|E|$ 分别为顶点数和边数）
对于AVL树，以下说法正确的有：
- 它是一种平衡二叉搜索树
- 每个节点的平衡因子只能是 $-1$ 、 $0$ 或 $1$
- 插入节点时可能需要进行多次旋转操作
- 它适合用于频繁插入和删除的场景
- ✔️
- ✔️
- ❌ 插入一个节点时，只会进行一次LL/LR/RL/RR旋转操作
- ❌ AVL树在插入与删除时需要进行的旋转修复次数较多，故更适合查找频繁、而增删较少的场景
以下关于深度优先搜索（DFS）的描述正确的有：
- 它使用栈实现
- 递归方式实现时会占用系统栈
- 可用于拓扑排序
- 每次访问都优先选择未访问的相邻顶点
哈夫曼编码具有的性质包括：
- 是一种最优前缀编码
- 叶子节点权值越小，路径越短
- 适用于任意字符集的编码
- 编码结果的平均长度最短
- ✔️
- ❌ 权值越小的节点越靠近底层（路径越长），权值越大的节点越靠近根部（路径越短）
- ✔️
- ✔️
判断链表是否有环的常用算法包括：
- 快慢指针法
- 哈希表法
- 广度优先搜索
- 递归法
- ✔️ 设置两个指针，快指针（fast）每次走两步，慢指针（slow）每次走一步。如果链表中存在环，快指针最终一定会追上慢指针（即fast == slow）；如果链表无环，快指针会指向null
- ✔️ 在遍历链表的过程中，每访问一个节点，就将其地址（或引用）存入哈希表。在存入前先判断该节点是否已存在于哈希表中，如果存在，说明之前访问过该节点，即链表有环。
- ❌ BFS常用于图或者树的遍历以及图的环检测。
- ❌ 如果链表有环，简单的递归调用会导致死循环，最终导致栈溢出。
二、编程题（1.请用C或C++语言；2.不同小题的源代码请标识清楚所在题号；3.若无法提供源代码，请用自然语言描述思路；4.请将能运行出的结果截全屏展示）
第1题(25分)： 在一个学生成绩管理系统中，需要对学生的课程成绩进行管理。每个学生有多门课程的成绩，课程信息包括课程名称、课程编号、学分，学生信息包括学号、姓名、性别。
小题1（5分）：定义课程结构体，包含课程名称、课程编号、学分。
```
typedef struct{
    char id[105],name[105];
    double credit;
}course;
```
小题2（5分）：定义学生结构体，包含学号、姓名、性别以及一个课程结构体数组，用于存储该学生的多门课程信息。
```
typedef struct{
    int id;
    double total_credit;//在小题5中用到
    char name[105],sex;
    course c[105];
}student;
```

小题3（5分）：编写一个函数，输入学生数量，然后依次输入每个学生的信息（包括学号、姓名、性别以及每门课程的课程名称、课程编号、学分），并存储到学生结构体数组中。

student s[105];
int n,cnt[105];
void read_in(){
    std::cin>>n;
    for(int i=0;i<n;i++){
        std::cin>>s[i].id>>s[i].name>>s[i].sex;
        int k;
        std::cin>>k; 
        for(int j=0;j<k;j++)std::cin>>s[i].c[j].name>>s[i].c[j].id>>s[i].c[j].credit;
        cnt[i]=k;
    }
}

小题4（5分）：编写一个函数，在已存储学生信息的结构体数组中，根据学号查找（请指出使用的查找算法名称）某个学生，并输出该学生的所有课程信息。

void find_student(int student_id,student s[],int n){
    int pos=0;
    while(pos<n && s[pos].id!=student_id)pos++;//顺序查找
    if(pos==n)std::cout<<"未找到！"<<std::endl;
    else{
        for(int j=0;j<cnt[pos];j++){
            std::cout<<s[pos].c[j].name<<' '<<s[pos].c[j].id<<' '<<s[pos].c[j].credit<<std::endl;
        }
    }
}

小题5（5分）：编写一个函数，计算每个学生的总学分，并在结构体数组中增加一个成员变量来存储总学分，最后输出所有学生的学号、姓名以及总学分。

void total_credit(student s[],int n){
    for(int i=0;i<n;i++){
        for(int j=0;j<cnt[i];j++)
            s[i].total_credit+=s[i].c[j].credit;
        std::cout<<s[i].id<<' '<<s[i].name<<' '<<s[i].total_credit<<std::endl;
    }
}

最后附上主函数与测试样例：

int main(){
    read_in();
    int student_id;
    std::cin>>student_id;
    find_student(student_id,s,n);
    total_credit(s,n);
    return 0;
}
/*
3
2026001 ZhangSan M
3
Math M101 4
English E102 3
Physics P103 5

2026002 LiSi F
2
Math M101 4
Chemistry C104 3.5

2026003 WangWu M
4
Math M101 4
English E102 3
Physics P103 5
Computer CS105 4

2026002
*/

第2题(25分)： 在一个物流运输系统中，用图来表示城市之间的运输路线。图中的节点表示城市，边表示运输路线，边的权值表示运输费用。
小题1（4分）：定义一个城市结构体，包含城市名称和城市编号。
```
typedef struct{
    char name[105];
    int id;
}city;
```
小题2（4分）：使用邻接矩阵来存储该物流运输图，定义图的结构体，包含城市结构体数组和邻接矩阵。
```
typedef struct{
    city c[1005];
    int g[1005][1005];
}graph;
```

小题3（4分）：编写一个函数，输入城市数量，然后依次输入每个城市的名称和编号，初始化图的城市结构体数组。

int n;
city ci[1005];
void read_city(){
    std::cin>>n;
    for(int i=0;i<n;i++){
        std::cin>>ci[i].name>>ci[i].id;
    }
}

小题4（4分）：编写一个函数，输入运输路线数量，然后依次输入每条路线的起点城市编号、终点城市编号以及运输费用，填充邻接矩阵。

graph transfer;
void fill_g(){
    for(int i=0;i<1005;i++)
        for(int j=0;j<1005;j++)
            transfer.g[i][j]=INF;//INF=114514
     int m;
    std::cin>>m;
    for(int i=0;i<m;i++){
        int st,ed,exp;
        std::cin>>st>>ed>>exp;
        int st_id=0,ed_id=0;
        while(st_id<n&&ci[st_id].id!=st)st_id++;
        while(ed_id<n&&ci[ed_id].id!=ed)ed_id++;
        transfer.g[st_id][ed_id]=transfer.g[ed_id][st_id]=exp;
    }
}

小题5（4分）：编写一个函数，输出从指定城市出发，能够直接到达的所有城市及其运输费用。

int city_id;
void output_city(int city_id){
    for(int i=0;i<n;i++){
        if(transfer.g[city_id][i]!=INF)
            std::cout<<ci[i].name<<' '<<transfer.g[city_id][i]<<std::endl;
    }
}

小题6（5分）:编写一个函数，使用Floyd算法计算所有城市之间的最短运输费用路径，并输出任意两个城市之间的最短路径和费用。

int d[1005][1005],path[1005][1005];
void path_out(int st,int ed){
    if(path[st][ed]==INF&&transfer.g[st][ed]!=INF){
        std::cout<<"-->"<<ci[ed].name;
    }
    else{
        path_out(st,path[st][ed]);
        path_out(path[st][ed],ed);
    }
}
void floyd(){
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            d[i][j]=transfer.g[i][j];
            path[i][j]=INF;
         }
    for(int k=0;k<n;k++)
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                 if(d[i][k]+d[k][j]<d[i][j]){
                   d[i][j]=d[i][k]+d[k][j];
                   path[i][j]=k;
                 }
            }
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if(d[i][j]!=INF){
                std::cout<<ci[i].name<<' '<<ci[j].name<<':'<<std::endl;
                std::cout<<ci[i].name;
                path_out(i,j);
                std::cout<<std::endl;
                std::cout<<"expense:"<<d[i][j]<<std::endl;
             }
             else{
                std::cout<<ci[i].name<<' '<<ci[j].name<<':'<<std::endl;
                std::cout<<"Unreachable!"<<std::endl;
            }
}

最后附上主函数与测试样例：

int main(){
    read_city();
    fill_g();
    std::cin>>city_id;
    output_city(city_id);
    floyd();
    return 0;
}
/*
7
Beijing 0
Shanghai 1
Guangzhou 2
Shenzhen 3
Chengdu 4
Wuhan 5
Xian 6

8
0 1 100
0 2 300
1 2 180
1 3 220
2 3 120
2 4 260
3 4 150
5 6 90

0
*/

数据结构线性表栈队列树图查找排序

概率论 题目分类汇编

人工智能导论 题目集（考试用）

概率论题目分类汇编

人工智能导论题目集（考试用）