2025-2026-1 数据结构 期末试卷回忆

A卷

选择题考了一个哈希表的查找效率，其他他们都记不清楚了

但是据说选择题比较简单

大题总共有五个

第1个

一个简单的递归画图

第一个是递归函数m(x) if(x<3) return x else return m(x-1)+m(x-3)+1 1.画出m(5)的调用递归树 2.求m(5)的值

第2个

程序填空（有序链表拼接）

第二个是这个
#include <stdio.h>
#include <stdlib.h>

// 链表节点结构体
typedef struct ListNode {
    int val;
    struct ListNode *next;
} ListNode;

/**
 * 合并两个有序链表
 * 
 * @param l1 第一个有序链表的头指针
 * @param l2 第二个有序链表的头指针
 * @return 合并后的有序链表头指针
 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    // 处理空链表的情况
    // 空1: ______________________________
    if (l1 == NULL) return l2;
    if (l2 == NULL) return l1;

    ListNode* head = NULL;  // 新链表的头节点
    ListNode* tail = NULL;  // 新链表的尾节点

    // 确定头节点（选择两个链表头节点中较小的一个）
    // 空2: ______________________________
    if (l1->val <= l2->val) {
        head = tail = l1;
        l1 = l1->next;
    } else {
        head = tail = l2;
        l2 = l2->next;
    }

    // 遍历两个链表，逐个比较并连接到tail后面
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            tail = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            tail = l2;
            l2 = l2->next;
        }
    }

    // 将剩余部分直接连接到新链表尾部
    // 空3: ______________________________
    tail->next = (l1 != NULL) ? l1 : l2;

    return head;
}

第3个

升序的数组 1.写二分查找代码 2.如果将数组旋转，写二分思路查找目标值，并且写出完整代码

第4个

用两个队列实现栈 1.写思路 2.写伪代码，有Q1,Q2,isempty,enqueue,outqueue

第5个

第五题是如果循环队列只有front和rear，有什么问题？如果用arr[n]中的一个单元来作为牺牲元素解决这个问题，应该如何解决。写入队和出队的伪代码

B卷

选择题十道整体相对简单。

有印象的有考查哈希表的线性探测，顺序表和链表的对比判断对错单选题，递归函数的结果

大题总共有五个

第1个

递归画图

int fun(int a[], int n) { if (n == 0) return 0;

if (a[n-1] % 2 == 0)
    return fun(a, n-1) + a[n-1];
else
    return fun(a, n-1) - a[n-1];

}

给定 a[] 和 n，求结果

第2个

程序填空（单链表反转），2个空

第3个

写一个完整 C 语言函数，求一个链表的倒数第 k 个元素，先写思路然后手写代码

第4个

为什么哈希表线性探测处理哈希冲突删元素不能直接设置为 NULL，并问正确的方式是什么

第5个

手写一个有头结点的单链表实现的队列代码，要求写结构体 LinkNode 和 LinkQueue，Queue 要有 front 和 rear 属性，然后要完成入队和出队两个函数。