数据结构pta训练题-编程题1-Toy模板网

这篇具有很好参考价值的文章主要介绍了数据结构pta训练题-编程题1。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

万字长文，整理不易。点赞加评论期末高分过！

感谢你这么帅（漂亮）还支持我

训练网站：PTA训练平台

7-1 一元多项式的乘法与加法运算

设计函数分别求两个一元多项式的乘积与和。

输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

4 3 4 -5 2  6 1  -2 0
3 5 20  -7 4  3 1

输出样例:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

解析：

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

typedef int ElementType;
typedef struct LNode *List;

struct LNode {
    ElementType coe;//系数
    ElementType exp;//指数
    List Next;//下一个节点
};

void Insert(List L, ElementType coe, ElementType exp);//插入
List Multi(List p1, List p2);//乘法
List Plus(List p1, List p2);//加法
int compare(List p1, List p2);//比较系数大小

int main() {
    List p1, p2;
    List p;
    int num1, num2, coe, exp;
    int i;
    p1 = (List) malloc(sizeof(struct LNode));
    p2 = (List) malloc(sizeof(struct LNode));
    p1->Next = NULL;
    p2->Next = NULL;

    scanf("%d", &num1);
    for (i = 0; i < num1; i++) {
        scanf("%d %d", &coe, &exp);
        Insert(p1, coe, exp);
    }
    scanf("%d", &num2);
    for (i = 0; i < num2; i++) {
        scanf("%d %d", &coe, &exp);
        Insert(p2, coe, exp);
    }
    //乘法运算
    p = Multi(p1->Next, p2->Next);
    while (p) {
        if (p->Next != NULL) {
            printf("%d %d ", p->coe, p->exp);//非最后一个节点,不换行打印,后接空格
        } else {
            printf("%d %d\n", p->coe, p->exp);//最后一个节点,换行打印
        }
        p = p->Next;
    }
    //加法运算
    p = Plus(p1->Next, p2->Next);
    if (p) {
        while (p) {
            if (p->Next != NULL) {
                printf("%d %d ", p->coe, p->exp);
            } else {
                printf("%d %d\n", p->coe, p->exp);
            }
            p = p->Next;
        }
    } else {//防止出现p1,p2抵消为零的情况
        printf("0 0\n");
    }
    return 0;
}

/**
 * 向链表中添加元素
 * @param L 需要添加的链表
 * @param coefficient 系数
 * @param exponent 指数
 */
void Insert(List L, ElementType coe, ElementType exp) {
    List s, p;
    p = L;

    while (p->Next)//找到最后一个节点
        p = p->Next;

    s = (List) malloc(sizeof(struct LNode));
    s->Next = NULL;
    s->coe = coe;
    s->exp = exp;

    p->Next = s;
}

/**
 * 两个多项式相乘
 * @param p1 代表多项式1的链表
 * @param p2 代表多项式2的链表
 * @return p 相乘后生成的新链表
 */
List Multi(List p1, List p2) {
    List p, p1a, p2a, s;
    int flag = 1;
    p = (List) malloc(sizeof(struct LNode));
    p->Next = NULL;
    p1a = p1;

    while (p1a) {
        p2a = p2;//确保p1多项式中的每一项可以与p2多项式中的每一项分别相乘
        s = (List) malloc(sizeof(struct LNode));
        s->Next = NULL;

        while (p2a) {//与p2多项式中的每一项分别相乘
            Insert(s, p1a->coe * p2a->coe, p1a->exp + p2a->exp);
            p2a = p2a->Next;
        }
        s = s->Next;

        if (flag == 1) {
            p = p->Next;
            /*
             * 如果是p1第一项与p2每一项相乘,那么先将链表p向后移一位,将头结点屏蔽
             * 因为默认初始化的P1头结点有默认的exp = 0,coe = 0,这两个数据是多余的
             * 如果不后移,那么头结点默认的数值0将会一直尾随整个乘法运算,导致最后的结果后面多两个0 0
             */
            flag = 0;

        }
        p = Plus(p, s);//相加,确保同类项合并
        p1a = p1a->Next;
        free(s);
    }

    return p;
}

/**
 * 比较两多项式指数大小
 * @param p1 代表多项式1的链表
 * @param p2 代表多项式2的链表
 * @return 返回值为0时表示两指数相同,可以进行加法运算
 */
int compare(List p1, List p2) {
    if (p1->exp > p2->exp)
        return 1;//p1指数大
    else if (p1->exp < p2->exp)
        return -1;//p1指数小
    else
        return 0;//指数相同
}

/**
 * 两个多项式相加
 * @param p1 代表多项式1的链表
 * @param p2 代表多项式2的链表
 * @return p 相加后生成的新链表
 */
List Plus(List p1, List p2) {
    List p, p1a, p2a;
    int temp;
    p = (List) malloc(sizeof(struct LNode));
    p->Next = NULL;
    p1a = p1;
    p2a = p2;

    while (p1a && p2a) {
        temp = compare(p1a, p2a);
        //判断指数大小,同指数才可以运算
        switch (temp) {
            case 1:
                //当前p1a的指数大,将当前p1a的数据放入新链表
                Insert(p, p1a->coe, p1a->exp);
                p1a = p1a->Next;//p1a向后移动,p2a不改变
                break;
            case -1:
                //当前p2a的指数大,将当前p2a的数据放入新链表
                Insert(p, p2a->coe, p2a->exp);
                p2a = p2a->Next;//p2a向后移动,p1a不改变
                break;
            case 0:
                //指数相同,进行运算
                if ((p1a->coe + p2a->coe) == 0) {
                    //系数为0,数据不放入新链表,直接将p1a和p2a后移
                    p1a = p1a->Next;
                    p2a = p2a->Next;
                } else {
                    //数据放入新链表,p1a和p2a后移
                    Insert(p, p1a->coe + p2a->coe, p2a->exp);
                    p1a = p1a->Next;
                    p2a = p2a->Next;
                }
                break;
            default:
                break;
        }
    }
    while (p1a) {
        //p1a的项数多,将剩余项放入链表
        Insert(p, p1a->coe, p1a->exp);
        p1a = p1a->Next;
    }
    while (p2a) {
        //p2a的项数多,将剩余项放入链表
        Insert(p, p2a->coe, p2a->exp);
        p2a = p2a->Next;
    }
    p = p->Next;
    return p;
}

7-2 符号配对

请编写程序检查C语言源程序中下列符号是否配对：/*与*/、(与)、[与]、{与}。

输入格式:
输入为一个C语言源程序。当读到某一行中只有一个句点.和一个回车的时候，标志着输入结束。程序中需要检查配对的符号不超过100个。

输出格式:
首先，如果所有符号配对正确，则在第一行中输出YES，否则输出NO。然后在第二行中指出第一个不配对的符号：如果缺少左符号，则输出?-右符号；如果缺少右符号，则输出左符号-?。

输入样例1：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) { /*/
        A[i] = i;
}
.

输出样例1：

NO
/*-?

输入样例2：

void test()
{
    int i, A[10];
    for (i=0; i<10; i++) /**/
        A[i] = i;
}]
.

输出样例2：

NO
?-]

输入样例3：

void test()
{
    int i
    double A[10];
    for (i=0; i<10; i++) /**/
        A[i] = 0.1*i;
}
.

输出样例3：

YES

解析：

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

#define Maxsize 105
typedef struct StackRecord *Stack;
struct StackRecord {
    int top;
    char *array;
};

Stack creat();//创建空栈
int cheekEmpty(Stack s);//判断栈是否为空
void push(Stack s, char x);//添加新元素
void pop(Stack s);//删除
char top(Stack s);//取出

char a[100];
char str[200];

int main() {
    int i, j = 0, flag = 0;
    char ch;
    Stack s = creat();

    while (gets(str)) {
        if (str[0] == '.' && !str[1])
            break;
        for( i=0; str[i]; i++){
            if(str[i]=='('||str[i]=='['||str[i]=='{'||str[i]==')'||str[i]=='}' ||str[i]==']')
                a[j++]=str[i];
            else if(str[i]=='/'&&str[i+1]=='*'){
                a[j++]='<';
                i++;
            }else if(str[i]=='*'&&str[i+1]=='/'){
                a[j++]='>';
                i++;
            }
        }
    }

    for (i = 0; i < j; i++) {
        if (a[i] == '(' || a[i] == '[' || a[i] == '{' || a[i] == '<') {
            push(s, a[i]);
        } else if (a[i] == ')') {
            if (s->top != -1 && top(s) == '(') {
                pop(s);
            } else {
                ch = a[i];
                flag = 1;
                break;
            }
        } else if (a[i] == ']') {
            if (s->top != -1 && top(s) == '[') pop(s);
            else {
                ch = a[i];
                flag = 1;
                break;
            }
        } else if (a[i] == '}') {
            if (s->top != -1 && top(s) == '{') pop(s);
            else {
                ch = a[i];
                flag = 1;
                break;
            }
        } else if (a[i] == '>') {
            if (s->top != -1 && top(s) == '<') pop(s);
            else {
                ch = a[i];
                flag = 1;
                break;
            }
        }
    }

    if (!flag && cheekEmpty(s)) {
        printf("YES\n");
    } else {
        printf("NO\n");
        if (!cheekEmpty(s)) {
            if (top(s) == '<') printf("/*-?\n");
            else printf("%c-?\n", top(s));
        } else {
            if (ch == '>') printf("?-*/\n");
            else printf("?-%c\n", ch);
        }
    }

    return 0;
}

/**
 * 创建新栈
 * @return
 */
Stack creat() {
    Stack s = (Stack) malloc(sizeof(struct StackRecord));
    s->top = -1;
    s->array = (char *) malloc(sizeof(char) * Maxsize);
    return s;
}

/**
 * 判断是否为空栈
 * @param s
 * @return
 */
int cheekEmpty(Stack s) {
    if (s->top == -1)
        return 1;
    else
        return 0;
}

/**
 *添加元素
 * @param s
 * @param x
 */
void push(Stack s, char x) {
    s->array[++(s->top)] = x;
}

/**
 *删除
 * @param s
 */
void pop(Stack s) {
    s->top--;
}

/**
 *取出
 * @param s
 */
char top(Stack s) {
    return s->array[s->top];
}

7-3 银行业务队列简单模拟

设某银行有A、B两个业务窗口，且处理业务的速度不一样，其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时，B窗口处理完1个顾客。给定到达银行的顾客序列，请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔，并且当不同窗口同时处理完2个顾客时，A窗口顾客优先输出。

输入格式:
输入为一行正整数，其中第1个数字N(≤1000)为顾客总数，后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务，为偶数的顾客则去B窗口。数字间以空格分隔。

输出格式:
按业务处理完成的顺序输出顾客的编号。数字间以空格分隔，但最后一个编号后不能有多余的空格。

输入样例:

8 2 1 3 9 4 11 13 15

输出样例:

1 3 2 9 11 4 13 15

解答

#include <stdio.h>

const int MAX = 1010;

int main() {

    int a[MAX], b[MAX], cnta, cntb;
    cnta = cntb = 0;
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int temp;
        scanf("%d", &temp);
        if (temp % 2) a[++cnta] = temp;
        else b[++cntb] = temp;
    }
    int flag = 0, x = 1, y = 1;
    while (x <= cnta || y <= cntb) {
        if (x <= cnta) {
            if (flag++) printf(" ");
            printf("%d", a[x++]);
        }
        if (x <= cnta) {
            if (flag++) printf(" ");
            printf("%d", a[x++]);
        }
        if (y <= cntb) {
            if (flag++) printf(" ");
            printf("%d", b[y++]);
        }
    }
    return 0;
}

7-4 顺序存储的二叉树的最近的公共祖先问题

设顺序存储的二叉树中有编号为i和j的两个结点，请设计算法求出它们最近的公共祖先结点的编号和值。

输入格式:
输入第1行给出正整数n（≤1000），即顺序存储的最大容量；第2行给出n个非负整数，其间以空格分隔。其中0代表二叉树中的空结点（如果第1个结点为0，则代表一棵空树）；第3行给出一对结点编号i和j。

题目保证输入正确对应一棵二叉树，且1≤i,j≤n。

输出格式:
如果i或j对应的是空结点，则输出ERROR: T[x] is NULL，其中x是i或j中先发现错误的那个编号；否则在一行中输出编号为i和j的两个结点最近的公共祖先结点的编号和值，其间以1个空格分隔。

输入样例1：

15
4 3 5 1 10 0 7 0 2 0 9 0 0 6 8
11 4

输出样例1：

2 3

输入样例2：

15
4 3 5 1 0 0 7 0 2 0 9 0 0 6 8
12 8

输出样例2：

ERROR: T[12] is NULL

解析

#include <stdio.h>

int find(int i, int j);

int main() {
    int n, i, j, m;
    int a[1000];
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    scanf("%d %d", &i, &j);

    if (a[i] == 0)//查错
    {
        printf("ERROR: T[%d] is NULL\n", i);
        return 0;
    }
    if (a[j] == 0)//查错
    {
        printf("ERROR: T[%d] is NULL\n", j);
        return 0;
    }
    m = find(i, j);
    printf("%d %d", m, a[m]);
    return 0;
}

/**
 * 查找公共祖先,二分查找
 * @param i 
 * @param j 
 * @return 
 */
int find(int i, int j) {
    if (i == j) {
        return i;
    } else if (i > j) {
        return find(i / 2, j);
    } else if (i < j) {
        return find(i, j / 2);
    }
}

7-5 修理牧场

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L
i

个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L
i

的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

输入格式:
输入首先给出正整数N（≤10
4
），表示要将木头锯成N块。第二行给出N个正整数（≤50），表示每段木块的长度。

输出格式:
输出一个整数，即将木头锯成N块的最少花费。

输入样例:

8
4 5 1 2 1 3 1 1

输出样例:

解析

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

typedef int ElemType;
typedef struct HuffmanTreeNode {
    ElemType data;  //哈夫曼树中节点的权值
    struct HuffmanTreeNode *left;
    struct HuffmanTreeNode *right;
} HuffmanTreeNode, *HuffmanTree;

HuffmanTree createHuffmanTree(ElemType arr[], int N) {
    HuffmanTree treeArr[N];
    HuffmanTree tree, pRoot = NULL;

    for (int i = 0; i < N; i++) {  //初始化结构体指针数组,数组中每一个元素为一个结构体指针类型
        tree = (HuffmanTree) malloc(sizeof(HuffmanTreeNode));
        tree->data = arr[i];
        tree->left = tree->right = NULL;
        treeArr[i] = tree;
    }

    for (int i = 1; i < N; i++) {  //进行 n-1 次循环建立哈夫曼树

        //k1为当前数组中第一个非空树的索引，k2为第二个非空树的索引
        int k1 = -1, k2 = 0;
        for (int j = 0; j < N; j++) {
            if (treeArr[j] != NULL && k1 == -1) {
                k1 = j;
                continue;
            }
            if (treeArr[j] != NULL) {
                k2 = j;
                break;
            }
        }
        //循环遍历当前数组，找出最小值索引k1,和次小值索引k2
        for (int j = k2; j < N; j++) {
            if (treeArr[j] != NULL) {
                if (treeArr[j]->data < treeArr[k1]->data) {//最小
                    k2 = k1;
                    k1 = j;
                } else if (treeArr[j]->data < treeArr[k2]->data) {//次小
                    k2 = j;
                }
            }
        }
        //由最小权值树和次最小权值树建立一棵新树,pRoot指向树根结点
        pRoot = (HuffmanTree) malloc(sizeof(HuffmanTreeNode));
        pRoot->data = treeArr[k1]->data + treeArr[k2]->data;
        pRoot->left = treeArr[k1];
        pRoot->right = treeArr[k2];

        treeArr[k1] = pRoot; //将新生成的数加入到数组中k1的位置
        treeArr[k2] = NULL; //k2位置为空
    }

    return pRoot;
}

ElemType calculateWeightLength(HuffmanTree ptrTree, int len) {
    if (ptrTree == NULL) { //空树返回0
        return 0;
    } else {
        if (ptrTree->left == NULL && ptrTree->right == NULL) { //访问到叶子节点
            return ptrTree->data * len;
        } else {
            return calculateWeightLength(ptrTree->left, len + 1) + calculateWeightLength(ptrTree->right, len + 1); //向下递归计算
        }
    }
}

int main() {
    ElemType arr[10001];
    int i = 0, N;
    scanf("%d", &N);

    while (i < N)
        scanf("%d", &arr[i++]);

    HuffmanTree pRoot = createHuffmanTree(arr, N);  //返回指向哈夫曼树根节点的指针

    printf("%d", calculateWeightLength(pRoot, 0));

    return 0;
}

7-6 公路村村通

现有村落间道路的统计数据表中，列出了有可能建设成标准公路的若干条道路的成本，求使每个村落都有公路连通所需要的最低成本。

输入格式:
输入数据包括城镇数目正整数N（≤1000）和候选道路数目M（≤3N）；随后的M行对应M条道路，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号以及该道路改建的预算成本。为简单起见，城镇从1到N编号。

输出格式:
输出村村通需要的最低成本。如果输入数据不足以保证畅通，则输出−1，表示需要建设更多公路。

输入样例:

输出样例:

解析

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

int fa[1005];

typedef struct {
    int l;
    int r;
    int weight;
} Node;

Node p[3005];
int n, m, sum, cnt;

int cmp(const void *a, const void *b) {
    Node *p1 = (Node *) a;
    Node *p2 = (Node *) b;
    return p1->weight - p2->weight;
}

int Find(int x) {
    return (x == fa[x]) ? (x) : (fa[x] = Find(fa[x]));
}

void Union(int x, int y) {
    fa[Find(x)] = Find(y);
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 0; i < m; i++)
        scanf("%d %d %d", &p[i].l, &p[i].r, &p[i].weight);
    qsort(p, m, sizeof(Node), cmp);
    for (int i = 0; i < m; i++) {
        if (Find(p[i].l) != Find(p[i].r)) {
            sum += p[i].weight;
            Union(p[i].l, p[i].r);
            cnt++;
        }
        if (cnt == n - 1)
            break;
    }
    if (cnt == n - 1)
        printf("%d\n", sum);
    else
        printf("-1\n");
    return 0;
}

7-7 畅通工程之最低成本建设问题

某地区经过对城镇交通状况的调查，得到现有城镇间快速道路的统计数据，并提出“畅通工程”的目标：使整个地区任何两个城镇间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到城镇道路统计表，表中列出了有可能建设成快速路的若干条道路的成本，求畅通工程需要的最低成本。

输入格式:
输入的第一行给出城镇数目N (1<N≤1000)和候选道路数目M≤3N；随后的M行，每行给出3个正整数，分别是该条道路直接连通的两个城镇的编号（从1编号到N）以及该道路改建的预算成本。

输出格式:
输出畅通工程需要的最低成本。如果输入数据不足以保证畅通，则输出“Impossible”。

输入样例1:

输出样例1:

输入样例2:

输出样例2:

Impossible

解析

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

struct path {
    int a, b, c;
} p[3000];
int f[1001], n, m;

void init() {
    for (int i = 1; i <= n; i++) f[i] = i;
}

int getf(int k) {
    if (f[k] == k) return f[k];
    return f[k] = getf(f[k]);
}

int cmp(const void *a, const void *b) {
    return ((struct path *) a)->c - ((struct path *) b)->c;
}

int main() {
    scanf("%d%d", &n, &m);
    init();
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].c);
    }
    qsort(p, m, sizeof(p[0]), cmp);
    int c = 0, ans = 0;
    for (int i = 0; i < m; i++) {
        if (getf(p[i].a) != getf(p[i].b)) {
            ans += p[i].c;
            c++;
            f[getf(p[i].a)] = getf(p[i].b);
        }
    }
    if (c < n - 1) printf("Impossible\n");
    else printf("%d\n", ans);
    return 0;
}