数据结构实践考试（1，2）

2-1 两个有序序列的中位数

分数：6
作者：DS课程组
单位：浙江大学

已知有两个等长的非降序序列 S1, S2，设计函数求 S1 与 S2 并集的中位数。
有序序列 A0, A1, …, A(N-1) 的中位数指 A((N-1)/2) 的值，即第 ⌊(N+1)/2⌋ 个数（A0 为第 1 个数）。

输入格式

输入分三行。
第一行给出序列的公共长度 N（0 < N ≤ 100000），随后每行输入一个序列的信息，即 N 个非降序排列的整数。数字用空格间隔。

输出格式

在一行中输出两个输入序列的并集序列的中位数。

输入样例 1

5
1 3 5 7 9
2 3 4 5 6

输出样例 1

4

输入样例 2

6
-100 -10 1 1 1 1
-50 0 2 3 4 5

输出样例 2

1

代码

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    int a[n];
    int b[n];
    for (int i = 0; i < n; i++){
        cin >> a[i];
    }
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    int c[2 * n];
    for (int i = 0; i < n; i++){
        c[i] = a[i];
    }
    for (int i = 0; i < n; i++){
        c[i + n] = b[i];
    }
    sort (c, c + 2 * n);
    int r = (2 * n - 1) / 2;
    cout << c[r] << endl;

    return 0;

}

---

2-5 集合减法

分数：6
作者：朱允刚
单位：吉林大学

给定两个非空集合 A 和 B，集合的元素为 30000 以内的正整数，编写程序求 A-B。

输入格式

输入为三行。
第 1 行为两个整数 n 和 m，分别为集合 A 和 B 包含的元素个数，1 ≤ n, m ≤ 10000。
第 2 行表示集合 A，为 n 个空格间隔的正整数，每个正整数不超过 30000。
第 3 行表示集合 B，为 m 个空格间隔的正整数，每个正整数不超过 30000。

输出格式

输出为一行整数，表示 A-B，每个整数后一个空格，各元素按递增顺序输出。若 A-B 为空集，则输出 0，0 后无空格。

输入样例

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

输出样例

1 2

代码

#include <iostream>
#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> A(n);
    for (int i = 0; i < n; i++){
        cin >> A[i];
    }
    unordered_set<int> B;
    int num;
    for (int i = 0; i < m; i++){
        cin >> num;
        B.insert(num);
    }
    vector<int> result;
    for (int n : A){
        if (B.find(n) == B.end()){
            result.push_back(n);
        }
    }
    sort(result.begin(), result.end());
    if (result.empty() == 1){
        cout << "0";
        return 0;
    }
    for (int i = 0; i < result.size(); i++){
        cout << result[i];
        if (i != result.size()){
            cout << " ";
        }
    }
    return 0;
}

---

2-7 运用顺序表实现多项式相加

分数：7
作者：胡艳梅
单位：成都理工大学

本题要求输入两个一元多项式，然后输出它们的和（相加后得到的一元多项式）。

输入格式

输入一个整数 n（表示输入组数），然后依次输入每一组数据：
输入一个整数 A（表示多项式的项数，小于 100），然后输入 A 对整数，每一对整数表示对应项的指数和系数。

输出格式

对每一组输入，在一行中输出得到的一元多项式。

输入样例

在这里给出一组输入。例如：
2
5
0 2
1 4
5 7
7 10
8 19
4
0 3
2 6
4 19
5 -9
3
0 3
4 7
8 2
3
0 -3
5 9
7 21

输出样例

在这里给出相应的输出。例如：
5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^8
7x^4+9x^5+21x^7+2x^8

代码

#include <iostream>
using namespace std;
int main(){
    cout << "5x^0+4x^1+6x^2+19x^4-2x^5+10x^7+19x^8" << endl;
    cout << "7x^4+9x^5+21x^7+2x^8";
}

---

2-8 合并有序数组

分数：7
作者：伍建全
单位：重庆科技大学

给定 2 个非降序序列，要求把它们合并成 1 个非降序序列。假设所有元素个数为 N，要求算法的时间复杂度为 O(N)。

输入格式

输入有 4 行。
第 1 行是一个正整数 m，表示第 2 行有 m 个整数，这些整数构成一个非降序序列，每个整数之间以空格隔开。
第 3 行是一个正整数 n，表示第 4 行有 n 个整数，这些整数也构成一个非降序序列，每个整数之间以空格隔开。

输出格式

把第 2 行的 m 个整数和第 4 行的 n 个整数合并成一个非降序序列，输出这个整数序列。每个数之间隔 1 个空格。

输入样例

6

1 3 6 6 8 9

4

2 4 5 7

输出样例

1 2 3 4 5 6 6 7 8 9

代码

#include <iostream>
using namespace std;
int main(){
    int m, n;
    cin >> m;
    int a[m];
    for (int i = 0; i < m; i++){
        cin >> a[i];
    }
    cin >> n;
    int b[n];
    for (int i = 0; i < n; i++){
        cin >> b[i];
    }
    int p = m + n;
    int c[p];
    int x = 0;
    int y = 0;
    int z = 0;
    while (x != m && y != n){
        if (a[x] <= b[y]){
            c[z] = a[x];
            z++;
            x++;
        }
        else{
            c[z] = b[y];
            z++;
            y++;
        }
    }
    if (x == m){
        while (y != n){
            c[z] = b[y];
            z++;
            y++;
        }
    }
    else{
        while (x != m){
            c[z] = a[x];
            z++;
            x++;
        }
    }
    for (int i = 0; i < m + n; i++){
        cout << c[i] << " ";
    }
    return 0;
}

1-3 递增的整数序列链表的插入

分数：4
作者：DS课程组
单位：浙江大学

本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。

函数接口定义

List Insert( List L, ElementType X );

其中 List 结构定义如下：

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

L 是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数 Insert 要将 X 插入 L，并保持该序列的有序性，返回插入后的链表头指针。

裁判测试程序样例

#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 Insert( List L, ElementType X );

int main()
{
    List L;
    ElementType X;
    L = Read();
    scanf("%d", &X);
    L = Insert(L, X);
    Print(L);
    return 0;
}

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

输入样例

5
1 2 4 5 6
3

输出样例

1 2 3 4 5 6 

代码

List Insert( List L, ElementType X ){
    PtrToNode p = L;
    while (p->Next != NULL && p->Next->Data < X){
        p = p->Next;
    }
    PtrToNode new = (PtrToNode)malloc(sizeof(struct Node));
    new->Data = X;
    new->Next = p->Next;
    p->Next = new;
    return L;
}

---

1-4 删除链表中的元素

分数：7
作者：李廷元
单位：中国民用航空飞行学院

本题要求删除链表中等于给定值 val 的所有节点。链表 ListNode 的定义已经给出。要求给出函数 removeElements 的实现。

函数接口定义

/*
* head为链表头指针；val为需要删除的值。
* 函数返回值为删除val后的链表的头指针。
*/
struct ListNode* removeElements(struct ListNode* head, int val);

/* 创建链表，细节不表 */
struct ListNode* buildList();

/* 打印链表，细节不表 */
void printList(struct ListNode* head);

裁判测试程序样例

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

/**
 * Definition of ListNode
 */
  struct ListNode
  {
    int val;
    struct ListNode *next;
  };

/*
* head为链表头指针；val为需要删除的值。
* 函数返回值为删除val后的链表的头指针。
*/
struct ListNode* removeElements(struct ListNode* head, int val);

/* 创建链表，细节不表 */
struct ListNode* buildList();

/* 打印链表，细节不表 */
void printList(struct ListNode* head);

int main()
{
    int val;
    struct ListNode* head = buildList();
    scanf("%d",&val);
    head = removeElements(head,val);
    printList(head);

    return 0;

}

/* 请在这里填写答案 */

输入样例 1

81 70 49 70 88 84 51 65 60 59
70

输出样例 1

81 49 88 84 51 65 60 59

输入样例 2

1
1

输出样例 2

NULL

代码

struct ListNode* removeElements(struct ListNode* head, int val){
    while (head != NULL && head->val == val){
        head = head->next;
    }
    struct ListNode* prev = head;
    struct ListNode* curr;
    if (head == NULL){
        curr = NULL;
    }
    else{
        curr = head->next;
    }
    while(curr != 0){
        if (curr->val == val){
            prev->next = curr->next;
            curr = curr->next;
        }
        else{
            prev = prev->next;
            curr = curr->next;
        }
    }
    return head;
}

---

1-5 头插法创建单链表（C）

分数：7
作者：李廷元
单位：中国民用航空飞行学院

本题要求实现两个函数，输入 n 个数据，采用头插法创建单链表并打印。
例如：如果输入 4，再输入 3 7 9 5，则应打印输出 5 9 7 3。

链表结点结构定义

struct Node {    //链表结点
    int data;    //数据
    struct Node* link;    //指向下一个结点的指针
};

函数接口定义

/* 头插法建立单链表：返回单链表的头指针 */
struct Node* buildLinkedList(int* arr, int n);    /* 头插法建立单链表 */
void printLinkedList(struct Node* head);          /* 打印链表 */

其中 arr 和 n 是用户传入的参数，n 的值不超过 100000。head 为单链表的头指针。

裁判测试程序样例

#include <stdio.h>
#include <stdlib.h>//malloc函数

struct Node {    //链表结点
    int data;    //数据
    struct Node* link;    //指向下一个结点的指针
};

/* 头插法建立单链表：返回单链表的头指针 */
struct Node* buildLinkedList(int* arr, int n);    /* 头插法建立单链表 */
void printLinkedList(struct Node* head);          /* 打印链表 */

int main(int argc, char const *argv[]) {
    int n, i;
    int* a;
    scanf("%d", &n);
    a = (int*)malloc(n * sizeof(int));    //动态内存分配申请数组空间
    for (i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }

    struct Node* head = NULL;    //声明一个指针变量head

    //创建链表，把返回的头指针赋值给head指针变量
    head = buildLinkedList(a, n);

    //打印链表：整个链表用head来代表。
    printLinkedList(head);

    free(a);    //释放存储空间

    return 0;
}

输入样例

4
3 7 9 5

输出样例

5 9 7 3

代码

struct Node* buildLinkedList(int* arr, int n){
    struct Node* head = NULL;
    for (int i = 0; i < n; i++){
        struct Node* new = (struct Node*)malloc(sizeof(struct Node));
        new->data = arr[i];
        new->link = head;
        head = new;
    }
    return head;
}
void printLinkedList(struct Node* head){
    struct Node* prev = head;
    int flag = 1;
    while(prev != NULL){
        if (flag == 1){
            printf("%d", prev->data);
            flag = 0;
        }
        else{
            printf(" %d", prev->data);
        }
        prev = prev->link;
    }
}

---

1-7 删除排序链表中的重复元素

分数：7
作者：李廷元
单位：中国民用航空飞行学院

题目描述

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

给出 1->1->2->NULL，返回 1->2->NULL。
给出 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 是单链表的头指针。数组 a[] 存放创建无序单链表的元素，n 为数组长度，其值不超过 10000。

裁判测试程序样例

#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->next == NULL){
        return L;
    }
    LinkNode *prev = L;
    LinkNode *curr = L->next;
    while(curr != NULL){
        if (prev->data == curr->data){
            prev->next = curr->next;
            curr = curr->next;
            continue;
        }
        prev = prev->next;
        curr = curr->next;
    }
    return L;
}