数据结构 | 东北大学&厦门大学期末试卷查漏补缺

发布时间:2023年12月20日

Prim变型算法(不会)?

有人给出求解最小生成树的另外一种算法:将连通图中的边按其权值从大到小顺序逐个删除直至不可再删,删除要遵循的原则是:保证在删除该边后各个顶点之间应该是连通的。请问该算法是正确的吗?如果认为是正确的,请给出证明。如果是错误的,请给出反例。


二叉排序树(由大到小遍历)

?

?

由小到大的遍历方法是中序遍历(左-根-右

那么如果要由大到小的遍历:则是逆中序遍历(右-根-左)?

已知中序和后序遍历如何画出二叉树

排序的时间复杂度和空间复杂度

(3)假设有个系统要多次对n个关键字进行排序,n很大且每次排序时关键字的分布情况不明。系统不希望每次排序时间变动过大,而且希望越快越好,哪种排序算法较好?为什么?

归并排序?


?最大子序列(不会)

给出一系列整数,设计算法求出总和最大的子系列,要求算法的时间复杂性在O(n)之内。比如对于整数系列-1,2,-1,3,-2,总和最大的子系列是2,-1,3(连续的、最大的)。

?

#include <iostream>  
#include <vector>  
#include <algorithm>  
  
using namespace std;  
  
int maxSumSubsequence(const vector<int>& nums) {  
    int n = nums.size();  
    vector<int> prefixSum(n + 1, 0);  
    for (int i = 0; i < n; ++i) {  
        prefixSum[i + 1] = prefixSum[i] + nums[i];  
    }  
    int maxSum = prefixSum[1];  
    int maxIndex = 0;  
    for (int i = 1; i <= n; ++i) {  
        for (int j = i; j <= n; ++j) {  
            int sum = prefixSum[j] - prefixSum[i - 1];  
            if (sum > maxSum) {  
                maxSum = sum;  
                maxIndex = i;  
            }  
        }  
    }  
    vector<int> maxSubsequence(maxIndex + 1);  
    for (int i = 0; i < maxIndex + 1; ++i) {  
        maxSubsequence[i] = nums[i];  
    }  
    return maxSubsequence;  
}  
  
int main() {  
    vector<int> nums = {-1, 2, -1, 3, -2};  
    vector<int> maxSubsequence = maxSumSubsequence(nums);  
    cout << "Max sum subsequence: ";  
    for (int num : maxSubsequence) {  
        cout << num << " ";  
    }  
    cout << endl;  
    return 0;  
}

带/不带头结点的单链表?

带头结点

?

head->next=NULL (头结点为空不影响整个链表的结构)

?

?不带头结点

?

head==NULL?

稀疏矩阵?

?


数据的存储结构

顺序存储结构

线性存储结构

散列存储结构

索引存储结构?

串?

两个串相等的充分必要条件是:两个串长度相等,且各个位置对应字符相等??


?

链表插入元素?

#include <iostream>  
using namespace std;  
  
// 定义链表节点  
struct ListNode {  
    int val;  
    ListNode* next;  
    ListNode(int x) : val(x), next(NULL) {}  
};  
  
// 插入元素e到链表L中  
ListNode* insertIntoSortedList(ListNode* head, int e) {  
    // 创建新节点  
    ListNode* newNode = new ListNode(e);  
    // 如果链表为空,将新节点作为头节点  
    if (head == NULL) {  
        head = newNode;  
    }  
    // 否则,遍历链表找到插入位置的前一个节点  
    else {  
        ListNode* cur = head;  
        while (cur->next != NULL && cur->next->val < e) {  
            cur = cur->next;  
        }  
    }  
    // 将新节点插入到合适位置  
    newNode->next = cur->next;  
    cur->next = newNode;  
    return head;  
}  
  
// 打印链表(从头到尾)  
void printList(ListNode* head) {  
    ListNode* cur = head;  
    while (cur != NULL) {  
        cout << cur->val << " ";  
        cur = cur->next;  
    }  
    cout << endl;  
}  

?

文章来源:https://blog.csdn.net/kazuma_hn/article/details/135112840
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。