数据结构pta训练题-编程题1(2)

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 数据结构pta训练题-编程题

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


输出样例:


49


解析


#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,表示需要建设更多公路。


输入样例:


6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3


输出样例:


12



解析


#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:



6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3


输出样例1:


12


输入样例2:


5 4
1 2 1
2 3 2
3 1 3
4 5 4



输出样例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;
}



后续的请关注编程2

整理不易,点个赞刷个评论再走吧!

目录
相关文章
|
1月前
|
存储 缓存 分布式计算
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
这篇文章是关于数据结构与算法的学习指南,涵盖了数据结构的分类、数据结构与算法的关系、实际编程中遇到的问题以及几个经典的算法面试题。
29 0
数据结构与算法学习一:学习前的准备,数据结构的分类,数据结构与算法的关系,实际编程中遇到的问题,几个经典算法问题
|
2月前
|
存储 索引 Python
Python编程的常用数据结构—列表
Python编程的常用数据结构—列表
|
2月前
|
存储 索引 Python
Python编程的常用数据结构—列表 原创
Python编程的常用数据结构—列表 原创
|
2月前
|
Python
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
28 0
|
2月前
|
算法 开发者 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
在编程的浩瀚宇宙中,数据结构如同基石,构建了解决问题的坚实框架。而并查集(Union-Find),这位数据结构界的“肌肉男”,以其独特的魅力和强大的功能,让无数开发者在面对复杂关系处理时,都能感受到前所未有的从容与自信。今天,就让我们一同揭开并查集的神秘面纱,看看它是如何成为你编程路上的得力助手的。
31 0
|
2月前
|
算法 程序员 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
并查集,一种处理不相交集合合并与查询的数据结构,被誉为编程的“肌肉男”。它提供Find(找根节点)和Union(合并集合)操作,常用于好友关系判断、图像处理、集合合并等。Python实现中,路径压缩和按秩合并优化效率。并查集的高效性能使其成为解决问题的强大工具,助力程序员应对复杂挑战。
29 0
|
3月前
|
存储 C#
揭秘C#.Net编程秘宝:结构体类型Struct,让你的数据结构秒变高效战斗机,编程界的新星就是你!
【8月更文挑战第4天】在C#编程中,结构体(`struct`)是一种整合多种数据类型的复合数据类型。与类不同,结构体是值类型,意味着数据被直接复制而非引用。这使其适合表示小型、固定的数据结构如点坐标。结构体默认私有成员且不可变,除非明确指定。通过`struct`关键字定义,可以包含字段、构造函数及方法。例如,定义一个表示二维点的结构体,并实现计算距离原点的方法。使用时如同普通类型,可通过实例化并调用其成员。设计时推荐保持结构体不可变以避免副作用,并注意装箱拆箱可能导致的性能影响。掌握结构体有助于构建高效的应用程序。
115 7
|
4月前
|
Python
告别低效!Python并查集:数据结构界的超级英雄,拯救你的编程人生!
【7月更文挑战第18天】并查集,数据结构超级英雄,用于不相交集合的合并与查询。Python实现包括初始化、查找根节点和合并操作。应用广泛,如社交网络分析、图论问题、集合划分等。示例代码展示了解决岛屿数量问题,统计连通的“1”单元格数。掌握并查集,提升编程效率,解决复杂问题。
52 6
|
4月前
|
算法 程序员 计算机视觉
Python并查集:数据结构界的肌肉男,让你在编程路上无所畏惧!
【7月更文挑战第16天】并查集,一种处理不相交集合合并与查询的数据结构,被誉为编程的“肌肉男”。它提供Find(找根节点)和Union(合并集合)操作,常用于好友关系判断、图像处理、集合合并等。Python实现中,路径压缩和按秩合并优化效率。并查集的高效性能使其成为解决问题的强大工具,助力程序员应对复杂挑战。
47 0
|
4月前
|
安全 调度 Python
Python堆与优先队列:不只是数据结构,更是你编程路上的超级加速器!
【7月更文挑战第8天】Python的heapq模块和queue.PriorityQueue提供堆与优先队列功能。堆,作为完全二叉树,支持排序性质,heapq用于单线程操作;PriorityQueue在多线程中保证安全。通过示例展示了如何插入、删除任务,以及在多线程任务调度中的应用。堆与优先队列是高效编程的关键工具,提升代码性能与并发处理能力。
39 0

热门文章

最新文章