2025-2026-1《数据结构》测验1（线性结构）总结

一、关于数据结构的说法，正确的是 ( )。

题干：以下关于数据结构的说法中，正确的是 ( )。

A. 数据的逻辑结构独立于其存储结构

B. 数据的存储结构独立于其逻辑结构

C. 数据的逻辑结构唯一决定了其存储结构

D. 数据结构仅由其逻辑结构和存储结构决定

答案：A

解析：

数据的逻辑结构是指数据元素之间的逻辑关系（如线性、树、图等），是抽象的概念，与存储方式无关；
数据的存储结构是逻辑结构在计算机中的物理实现（如顺序存储、链式存储等），依赖于逻辑结构但不被其唯一决定（同一逻辑结构可对应多种存储结构）；
数据结构由逻辑结构、存储结构和运算三部分组成，并非仅前两者。

因此，只有 A 选项正确。

二、下列程序段的时间复杂度是（）。

题干：

int sum = 0;
for(int i = 1; i < n; i *= 2)
  for(int j = 0; j < i; j++)
   sum++;

A. O(logn)

B. O(nlogn)

C. O(n)

D. O(n²)

答案：C

解析：

外层循环：i从 1 开始，每次乘 2，直到i < n，循环次数为log₂n（如n=8时，i=1,2,4，共 3 次）。
内层循环：每次外层循环时，j从 0 到i-1，执行i次。
总执行次数：内层循环次数总和为1 + 2 + 4 + … + 2^k（其中2^k < n），这是首项为 1、公比为 2 的等比数列，求和得2^(k+1) - 1。由于2^k < n，则2^(k+1) ≤ 2n，总和约为n。

因此，时间复杂度为 O (n)。

三、程序 P1 和 P2 时间复杂度的递推公式对应的时间复杂度是（）。

题干：程序 P1 和 P2 时间复杂度的递推公式：

P1: T(1)=1, T(N)=T(N/2)+1;

P2: T(1)=1, T(N)=2T(N/2)+1;

则下列关于两程序时间复杂度的结论中最准确的是：

A. 均为 O (logN)

B. P1 是 O (logN)，P2 是 O (N)

C. 均为 O (N)

D. P1 是 O (logN)，P2 是 O (NlogN)

答案：B

解析：

P1 分析：递推公式展开：T(N) = T(N/2) + 1 = T(N/4) + 1 + 1 = ... = T(1) + log₂N（共log₂N个 1 相加）。因此，T(N) = O(logN)。
P2 分析：递推公式展开：T(N) = 2T(N/2) + 1 = 2[2T(N/4) + 1] + 1 = 2²T(N/4) + 2 + 1 = ... = 2^k T(N/2^k) + (2^k - 1)（其中k=log₂N）。代入T(1)=1得：T(N) = N + (N - 1) = O(N)。

因此，P1 为 O (logN)，P2 为 O (N)，答案选 B。

四、创建一个包括 n 个结点的有序单链表的算法的时间复杂度是（）。

题干：创建一个包括 n 个结点的有序单链表的算法的时间复杂度是（）。

A. O(1)

B. O(n)

C. O(n²)

D. O(nlog₂n)

答案：C

解析：有序单链表的创建需要保证插入的每个新节点按顺序排列。对于第 i 个节点（从 0 开始计数），插入时可能需要遍历前 i 个节点才能找到合适位置，最坏情况下总操作次数为0 + 1 + 2 + ... + (n-1) = n(n-1)/2，因此时间复杂度为 O (n²)。

五、判断共享栈满的条件是（）。

题干：设有一个顺序共享栈 Share [0…n-1]，其中第一个栈顶指针 top1 的初值为 - 1，第二个栈顶指针 top2 的初值为 n，则判断共享栈满的条件是（）。

A. top2 - top1 == 1

B. top1 - top2 == 1

C. top1 == top2

D. 以上都不对

答案：A

解析：

共享栈中，top1 从 - 1 开始（向左栈底）向右增长，top2 从 n 开始（向右栈底）向左增长。
当左栈顶与右栈顶相邻时，栈满，即top1 + 1 == top2，等价于top2 - top1 == 1。

六、后缀式 5 2 6 4 - / 5 + 6 * + 的值是（）。

题干：后缀式（postfix expression，也叫逆波兰式，reverse Polish notation）5 2 6 4 - / 5 + 6 * + 的值是：

答案：41

解析：使用栈计算后缀式，规则为：遇数字入栈，遇运算符弹出栈顶两个元素（后弹出为左操作数，先弹出为右操作数），运算结果入栈，最终栈顶为结果。步骤：

数字入栈：[5, 2, 6, 4]
遇-：弹出 4、6，计算6-4=2，入栈 → [5, 2, 2]
遇/：弹出 2、2，计算2/2=1，入栈 → [5, 1]
数字入栈：[5, 1, 5]
遇+：弹出 5、1，计算1+5=6，入栈 → [5, 6]
数字入栈：[5, 6, 6]
遇*：弹出 6、6，计算6*6=36，入栈 → [5, 36]
遇+：弹出 36、5，计算5+36=41，入栈 →[41]

最终结果为 41。

七、单链表逆转

分数：5

作者：陈越

单位：浙江大学

题目描述：

本题要求实现一个函数，将给定的单链表逆转。

函数接口定义：

List Reverse( List L );

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

L是给定单链表，函数Reverse要返回被逆转后的链表。

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

List Reverse( List L );

int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}

/* 你的代码将被嵌在这里 */

输入样例：

5
1 3 4 5 2

输出样例：

1
2 5 4 3 1

解析：

List Reverse( List L ){
    List prev = NULL;  // 前驱节点，初始为NULL（逆转后链表的尾节点）
    List curr = L;     // 当前节点，从原链表头开始
    List next = NULL;  // 暂存当前节点的下一个节点，防止断链

    while(curr != NULL){
        next = curr->Next;  // 保存下一个节点
        curr->Next = prev;  // 当前节点指向其前驱，实现逆转
        prev = curr;        // 前驱节点后移
        curr = next;        // 当前节点后移
    }
    return prev;  // 循环结束后，prev为新链表的头节点
}

关键思路：通过三个指针（prev、curr、next）迭代调整节点指向，将每个节点的Next从 “指向下一个节点” 改为 “指向前一个节点”，最终原链表尾节点成为新链表头节点。

八、删除排序链表中的重复元素

分数：8

作者：李廷元

单位：中国民用航空飞行学院

题目描述：

编写一个函数，对于一个给定的排序链表，删除所有重复的元素，每个元素只留下一个。

示例 1：输入1->1->2->NULL，返回1->2->NULL
示例 2：输入1->1->2->3->3->NULL，返回1->2->3->NULL

单链表结点类型定义：

typedef int ElemType;    //元素的数据类型

typedef struct LNode {
    ElemType data;        //结点的数据域
    struct LNode *next;    //指向后继结点
} LinkNode;             //单链表结点类型

函数接口定义：

/*尾插法建立单链表,细节不表*/
LinkNode* CreateListR(ElemType a[], int n);

/*输出线性表,细节不表*/
void DispList(LinkNode *L);

/*删除排序链表中的重复元素*/
LinkNode* deleteDuplicates(LinkNode *L);

其中 L是单链表的头指针。

裁判测试程序样例：

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;    /*元素的数据类型*/

typedef struct LNode {    /*单链表结点类型定义*/
    ElemType data;        /*结点的数据域*/
    struct LNode *next;    /*指向后继结点*/
} LinkNode;             /*单链表结点类型*/

/*尾插法建立单链表,细节不表*/
LinkNode* CreateListR(ElemType a[], int n);

/*输出线性表,细节不表*/
void DispList(LinkNode *L);

/*删除排序链表中的重复元素*/
LinkNode* deleteDuplicates(LinkNode *L);

int main()
{    
    ElemType a[10000], x;
    int n = 0;

    while (scanf("%d", &x) != EOF) {
        a[n++] = x;
    }

    LinkNode* L = CreateListR(a, n);

    L = deleteDuplicates(L);
    DispList(L);

    return 0;
}

/* 请在下面填写答案 */

输入样例：

1 1 2 3 3

输出样例：

1 2 3

解析：

LinkNode* deleteDuplicates(LinkNode *L){
    if(L == NULL || L->next == NULL){  // 空链表或只有一个节点，直接返回
        return L;
    }
    LinkNode* p = L;  // 遍历指针，从表头开始
    while(p->next != NULL){  // 遍历至倒数第二个节点
        if (p->data == p->next->data){  // 当前节点与后继节点值相同（重复）
            p->next = p->next->next;  // 跳过后继节点（删除重复节点）
        } else {
            p = p->next;  // 不重复则后移
        }
    }
    return L;
}

关键思路：利用排序链表 “重复元素相邻” 的特性，通过遍历比较当前节点与后继节点的值，若重复则删除后继节点（跳过并断开连接），否则继续遍历，时间复杂度 O (n)。

九、进制转换

分数：5

作者：YJ

单位：西南石油大学

题目描述：

设计一个顺序栈，并利用该顺序栈将给定的十进制整数转换为二进制输出。

函数接口定义：

Status SPush( SqStack &s,ElemType x);  // 入栈操作
Status SPop( SqStack &s,int &e );      // 出栈操作

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MaxSize 10
#define OK 1
#define ERROR 0
typedef int Status;
typedef int ElemType;

typedef struct{
    ElemType *data;    //存储元素的数组
    int top;           //栈顶指针
    int stacksize;       //栈最大容量
}SqStack;

void CreateStack(SqStack &s)
{
    s.data= (ElemType *)malloc(MaxSize*sizeof(ElemType));
    s.top=0;
    s.stacksize=MaxSize;
}

Status SPush( SqStack &s, ElemType x );  
Status SPop( SqStack &s,int &e );

int main()
{
    SqStack s;
    int N,e;
    CreateStack(s);
    scanf("%d", &N);
    while (N) {  // 将十进制数N转换为二进制，余数入栈
        if(SPush(s,N%2))
           N=N/2;
        else{ 
            printf("stack is overflow!\n");
           return 0;
      }
    }
    while(SPop(s,e))  // 出栈并打印，得到二进制数
       printf("%d",e);
    printf("\n");
    return 0;
}
/* 请在这里填写答案 */

输入样例：

输出样例：

1111111111

解析：

// 入栈操作：将元素x压入栈s，成功返回OK，失败返回ERROR
Status SPush( SqStack &s,ElemType x){
    if (s.top >= s.stacksize){  // 栈满，入栈失败
        return ERROR;
    }
    s.data[s.top] = x;  // 元素存入栈顶
    s.top++;  // 栈顶指针上移
    return OK;
}

// 出栈操作：将栈s的栈顶元素弹出到e，成功返回OK，失败返回ERROR
Status SPop( SqStack &s,int &e ){
    if (s.top == 0){  // 栈空，出栈失败
        return ERROR;
    }
    s.top--;  // 栈顶指针下移
    e = s.data[s.top];  // 取栈顶元素
    return OK;
}

关键思路：十进制转二进制的核心是 “除 2 取余，逆序排列”。利用栈 “后进先出” 的特性，将余数依次入栈，再出栈即可得到逆序的二进制数。

十、在顺序表 list 的第 i 个位置上插入元素 x

分数：6

作者：陈越

单位：浙江大学

题目描述：

请编写程序，将 n 个整数存入顺序表，对任一给定整数 x，将其插入顺序表中指定的第 i 个位置。注意：i 代表位序，从 1 开始，不是数组下标。

输入格式：

第一行给出正整数 n（≤10⁴）；
第二行给出 n 个整数，空格分隔；
第三行给出插入位置 i 和待插入元素 x。

输出格式：

若顺序表已满（已有 10⁴个元素）：输出错误：表满不能插入。
若插入位置不合法（i≤0 或 i>n+1）：输出错误：插入位置不合法。
无论是否插入成功，均顺序输出表中元素，每个元素后跟一个空格。

输入样例 1：

5
1 2 3 4 5
3 8

输出样例 1：

1 2 8 3 4 5

输入样例 2：

5
4 3 6 8 0
0 1

输出样例 2：

错误：插入位置不合法。
4 3 6 8 0

解析：

#include<iostream>
using namespace std;

int main(){
    int a[10000];  // 顺序表最大容量10000
    int n;
    cin >> n;
    // 读入n个整数到顺序表
    for (int i = 0; i < n; i++){
        int b;
        cin >> b;
        a[i] = b;
    }
    int i, x;  // 插入位置i和元素x
    cin >> i >> x;

    // 检查插入条件
    if (n >= 10000) {
        cout << "错误：表满不能插入。" << endl;
    } else if (i <= 0 || i > n + 1) {  // 位置i需在[1, n+1]范围内
        cout << "错误：插入位置不合法。" << endl;
    } else {
        // 从后往前移动元素，为插入x腾出位置
        for (int j = n - 1; j >= i - 1; j--){
            a[j + 1] = a[j];
        }
        a[i - 1] = x;  // 插入x（i是位序，对应下标i-1）
        n++;  // 表长加1
    }

    // 输出顺序表元素
    for (int k = 0; k < n; k++){
        cout << a[k] << " ";
    }
    return 0;
}

关键思路：顺序表插入的核心是 “移动元素腾位置”。需先检查表是否已满和位置是否合法，若合法则从插入位置的前一个元素开始，依次将元素后移一位，再插入新元素。

十一、出栈序列的合法性

分数：6作者：陈越单位：浙江大学

题目描述：

给定一个最大容量为 m 的堆栈，将 n 个数字按 1, 2, 3, …, n 的顺序入栈，允许按任何顺序出栈，判断给定的 k 个出栈序列是否合法。

输入格式：

第一行：3 个正整数 m（栈容量）、n（入栈元素数）、k（待检查序列数）；
后续 k 行：每行 n 个数字，为待检查的出栈序列。

输出格式：

对每个序列，若合法输出YES，否则输出NO。

输入样例：

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

输出样例：

YES
NO
NO
YES
NO

解析：

#include <iostream>
#include<stack>
using namespace std;

int main(){
    int m, n, k;
    cin >> m >> n >> k;  // 栈容量m，元素数n，序列数k
    for (int i = 0; i < k; i++){
        int target[1000];  // 存储待检查的出栈序列
        for (int j = 0; j < n; j++){
            cin >> target[j];
        }

        stack<int> st;  // 模拟堆栈
        int current = 0;  // 指向target中当前待匹配的元素
        bool is_valid = true;

        // 按1~n顺序入栈
        for (int j = 1; j <= n; j++){
            st.push(j);
            if (st.size() > m){  // 栈容量超限，序列无效
                is_valid = false;
                break;
            }
            // 栈顶与target[current]匹配时，出栈并移动current
            while (!st.empty() && st.top() == target[current]){
                st.pop();
                current++;
            }
        }

        // 合法条件：栈空且所有元素匹配
        if (is_valid && st.empty() && current == n){
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

关键思路：通过模拟入栈过程验证序列合法性。按 1~n 顺序入栈，每次入栈后检查栈顶是否与目标序列当前元素匹配，匹配则出栈；若栈容量超限或最终栈非空，则序列无效。

2025-2026-1《数据结构》测验1（线性结构）总结

一、关于数据结构的说法，正确的是 ( )。

二、下列程序段的时间复杂度是（ ）。

三、程序 P1 和 P2 时间复杂度的递推公式对应的时间复杂度是（ ）。

四、创建一个包括 n 个结点的有序单链表的算法的时间复杂度是（ ）。

五、判断共享栈满的条件是（ ）。

六、后缀式 5 2 6 4 - / 5 + 6 * + 的值是（ ）。

七、单链表逆转

题目描述：

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

解析：

八、删除排序链表中的重复元素

题目描述：

单链表结点类型定义：

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

解析：

九、进制转换

题目描述：

函数接口定义：

裁判测试程序样例：

输入样例：

输出样例：

解析：

十、在顺序表 list 的第 i 个位置上插入元素 x

题目描述：

输入格式：

输出格式：

输入样例 1：

输出样例 1：

输入样例 2：

输出样例 2：

解析：

十一、出栈序列的合法性

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解析：

二、下列程序段的时间复杂度是（）。

三、程序 P1 和 P2 时间复杂度的递推公式对应的时间复杂度是（）。

四、创建一个包括 n 个结点的有序单链表的算法的时间复杂度是（）。

五、判断共享栈满的条件是（）。

六、后缀式 5 2 6 4 - / 5 + 6 * + 的值是（）。