2024-2025学年下学期期中

2024-2025学年下学期期中试卷（A）——杜育根

一、单选题（共 20 题，20 分）

在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。（1.0）

A. 逻辑结构

B. 顺序存储结构

C. 链表存储结构

D. 以上都不对
数据结构中，在逻辑上可以把数据结构分成（）。（1.0）

A. 动态结构和静态结构

B. 紧凑结构和非紧凑结构

C. 线性结构和非线性结构

D. 内部结构和外部结构
一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。（1.0）

A. 确定性、可行性、有穷性

B. 易读性、确定性、有效性

C. 有穷性、稳定性、确定性

D. 可行性、易读性、有穷性
以下关于数据的逻辑结构的叙述中正确的是（）。（1.0）

A. 数据的逻辑结构是数据间关系的描述

B. 数据的逻辑结构反映了数据在计算机中的存储方式

C. 数据的逻辑结构分为顺序结构和链式结构

D. 数据的逻辑结构分为静态结构和动态结构
以下数据结构中不属于线性数据结构的是（）。（1.0）

A. 队列

B. 线性表

C. 二叉树

D. 栈
数据的存储结构是指（）。（1.0）

A. 数据所占的存储空间量

B. 数据的逻辑结构在计算机中的表示

C. 数据在计算机中的顺序存储方式

D. 存储在外存中的数据
在 $n$ 个结点的顺序表中，算法的时间复杂度是 $O(1)$ 的操作是（）。（1.0）

A. 访问第 $i$ 个结点（ $1\le i\le n$ ）和求第 $i$ 个结点的直接前驱（ $2\le i\le n$ ）

B. 在第 $i$ 个结点后插入一个新结点（ $1\le i\le n$ ）

C. 删除第 $i$ 个结点（ $1\le i\le n$ ）

D. 将 $n$ 个结点从小到大排序
向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。（1.0）

A. 8

B. 63.5

C. 63

D. 7
若让元素 1, 2, 3, 4, 5 依次进栈，则出栈次序不可能出现在（）种情况。（1.0）

A. 5, 4, 3, 2, 1

B. 2, 1, 5, 4, 3

C. 4, 3, 1, 2, 5

D. 2, 3, 5, 4, 1
设有一个递归算法如下：
```
int fact(int n) { // n 大于等于 0
    if (n <= 0) return 1;
    else return n * fact(n - 1);
}
```
则计算 fact(n) 需要调用该函数的次数为（）。（1.0）

A. $n+1$

B. $n-1$

C. $n$

D. $n+2$
设栈 $S$ 和队列 $Q$ 的初始状态为空，元素 $e1$ 、 $e2$ 、 $e3$ 、 $e4$ 、 $e5$ 和 $e6$ 依次进入栈 $S$ ，一个元素出栈后即进入 $Q$ ，若 6 个元素出队的序列是 $e2$ 、 $e4$ 、 $e3$ 、 $e6$ 、 $e5$ 和 $e1$ ，则栈 $S$ 的容量至少应该是（）。（1.0）

A. 2

B. 3

C. 4

D. 6
下述几种排序方法中，要求内存最大的是（）。（1.0）

A. 希尔排序

B. 快速排序

C. 归并排序

D. 堆排序
下述几种排序方法中，（）是稳定的排序方法。（1.0）

A. 希尔排序

B. 快速排序

C. 归并排序

D. 堆排序
在寻找 $n$ 个元素中第 $k$ 小元素问题中，如快速排序算法思想，运用分治算法对 $n$ 个元素进行划分，如何选择划分基准？下面（）答案解释最合理。（1.0）

A. 随机选择一个元素作为划分基准

B. 取子序列的第一个元素作为划分基准

C. 用中位数的中位数方法寻找划分基准

D. 以上皆可行，但不同方法，算法复杂度上界可能不同
使用分治法求解不需要满足的条件是（）。（1.0）

A. 子问题必须是一样的

B. 子问题不能够重复

C. 子问题的解可以合并

D. 原问题和子问题使用相同的方法解
（）是贪心算法的基本要素。（1.0）

A. 重叠子问题

B. 构造最优解

C. 贪心选择性质

D. 定义最优解
有一批集装箱要装上一艘载重量为 $C$ 的轮船，其中集装箱 $i$ 的重量为 $W_i$ 。要求在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。采用贪心算法的最优装载问题的主要计算量在于将集装箱依其重量从小到大排序，故算法的时间复杂度为（）。（1.0）

A. $O(n)$

B. $O(\log_2 n)$

C. $O(n^3)$

D. $O(n\log_2 n)$
一棵哈夫曼树共有 215 个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。（1.0）

A. 107

B. 108

C. 214

D. 215
一个问题可用动态规划算法或贪心算法求解的关键特征是问题的（）。（1.0）

A. 贪心选择性质

B. 重叠子问题

C. 最优子结构性质

D. 定义最优解
回溯法在问题的解空间树中，按（）策略，从根结点出发搜索解空间树。（1.0）

A. 广度优先

B. 活结点优先

C. 扩展结点优先

D. 深度优先

二、多选题（共 5 题，10 分）

数据结构是指互相之间存在着一种或多种关系的数据元素的集合，基本的数据结构通常是（）。（2.0）

A. 集合结构

B. 线性结构

C. 树型结构

D. 图形结构
算法的基本结构有（）。（2.0）

A. 顺序结构

B. 分支结构

C. 循环结构

D. 跳跃结构
递归方法一般用来解决哪些类型的问题？（）（2.0）

A. 数据的定义是按递归定义的

B. 问题解法按递归算法实现

C. 数据的结构形式是按递归定义的

D. 问题的复杂程度超过一般算法能够解决的
用链表表示线性表的优点是（）。（2.0）

A. 便于插入和删除操作

B. 数据元素的物理顺序与逻辑顺序相同

C. 花费的存储空间较顺序存储少

D. 便于随机存取
算法的实现方式有（）。（2.0）

A. 子程序

B. 函数

C. 模块

D. 过程

三、判断题（共 10 题，10 分）

数据项是数据的最小单位。（）（1.0）
设置数据结构的基本操作的最重要准则是，实现应用程序与存储结构的独立。（）（1.0）
数据的逻辑结构与数据元素本身的内容和形式无关。（）（1.0）
数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）（1.0）
一个算法的语句频度之和为 $T(n)=1024n+4n\log n$ ，则算法的时间复杂度为 $O(n\log n)$ 。（）（1.0）
顺序存储结构要求连续的存储区域，在存储管理上不够灵活，因此不常用。（）（1.0）
抽象数据类型与计算机内部表示和实现无关。（）（1.0）
根据算法的时间复杂性，人们常常把算法分成两类：多项式阶算法和指数阶算法。当 $n$ 很大时，可以证明有关系
$O(1)<O(\log_2\log_2 n)<O(\log_2 n)<O(n)<O(n\log_2 n)<O(n^2)<O(2^n).$
（）（1.0）
哈夫曼树、完全二叉树都是数据的逻辑结构。（）（1.0）
数据结构概念包括数据之间的逻辑结构、数据在计算机中的存储方式和数据的运算三个方面。（）（1.0）

四、简答题（共 2 题，20 分）

对于一个简单的 BFS 问题，如果一个状态可以延展出 $n$ 个状态，并且我们需要穷举所有 $m$ 步可以到达的状态，那么整个算法复杂度是多少？（10.0）

分析下列程序的时间复杂度。（10.0）

x = n; // n > 1
y = 0;
while (x >= (y + 1) * (y + 1))
    y++;

五、填空题（共 3 题，27 分）

设计一个顺序存储结构解决约瑟夫问题，有 $n$ 个人（ $n>0$ ），编号 $1,2,\ldots,n$ ，报到 $m$ 的人出圈。要求按出圈顺序输出人员编号。设计的算法是：用 count 来计数，s 记录报数人编号，当 count 数到 $m$ 时，对应报数人出圈，顺序表当前长度 length 值减 1，即从表中删除对应元素，后面前移。请填写空缺的语句。（12.0）

void Josephus(int a[], int n, int m)
{
    int s = 0;
    for (int length = n; length >= 2; length--)
    {
        for (int count = 0; count < m - 1; count++)
            s = __________1__________;
        cout << __________2__________ << endl;
        for (int i = s + 1; i < length; i++)
            __________3__________;
    }
    cout << __________4__________;
}

下面程序用递归算法实现一个整数按逆序存到一个字符数组里。如 123 存放成 "321" 字符数组。（6.0）

#include <stdio.h>

void convert(char *s, int n)
{
    int i;
    if (i = n / 10) convert(__________1__________, i);
    *s = __________2__________;
}

int main()
{
    int number;
    char str[10] = "";
    scanf("%d", &number);
    convert(str, number);
    puts(str);
}

已知二叉树的结构体在 C++ 语言中被定义为：

struct ListNode {
    ListNode* left;
    ListNode* right;
    int val;
    ListNode(int v) : val(v), left(NULL), right(NULL) {}
};

填写以下函数，该函数完成二叉树的非递归的中序遍历。其中，stack s 为标准模板库中的栈。（9.0）

int visit(ListNode* node) {
    stack<ListNode*> s;
    s.push(node);
    while (__________1__________) {
        while (NULL != s.top()) {
            s.push(__________2__________);
        }
        ListNode* p = s.top();
        s.pop();
        if (!s.empty()) {
            p = s.top();
            s.pop();
            cout << p->val;
            s.push(__________3__________);
        }
    }
    return 0;
}

六、编程题（2 题，13 分）

【代码】给定一个二叉树，统计二叉树的叶结点个数。对于没有左儿子或者右儿子的节点，left 或者 right 为空指针。（5.0）
【代码】设线性表 $L=(a_1,a_2,a_3,\ldots,a_{n-2},a_{n-1},a_n)$ 。采用带头结点的单链表保存，链表中的节点定义如下：
```
typedef struct node {
    int data;
    struct node *next;
} NODE;
```
请设计一个空间复杂度为 $O(1)$ 且时间上尽可能高效的算法，重新排列 $L$ 中的各结点，得到线性表 $L'=(a_1,a_n,a_2,a_{n-1},a_3,a_{n-2},\ldots)$ 。

要求：

(1) 给出算法的基本设计思想。根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（6.0）

(3) 说明你所设计的算法的时间复杂度。（2.0）

2024-2025学年下学期期中试卷（A）——杜育根​

一、单选题（共 20 题，20 分）​

二、多选题（共 5 题，10 分）​

三、判断题（共 10 题，10 分）​

四、简答题（共 2 题，20 分）​

五、填空题（共 3 题，27 分）​

六、编程题（2 题，13 分）​