雪地行进

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com273基于Dijsktra算法的最短路径求解描述一张地图包括n个城市，假设城市间有m条路径（有向图），每条路径的长度已知。给定地图的一个起点城市和终点城市，利用Dijsktra算法求出起点到终点之间的最短路径。输入多组数据，每组数据有m+3行。第一行为两个整数n和m，分别代表城市个数n和路径条数m。第二行有n个字符，代表每个城市的名字。第三行到第m+2行每行有两个字符a和b和一个整数d，代表从城市a到城市b有一条距离为d的路

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com272基于二叉树的表达式求值描述输入一个表达式（表达式中的数均为小于10的正整数），利用二叉树来表示该表达式，创建表达式树，然后利用二叉树的遍历操作求表达式的值。输入多组数据。每组数据一行，为一个表达式，表达式以‘=’结尾。当输入只有一个“=”时，输入结束。输出每组数据输出一行，为表达式的值。输入样例2*(2+5)=1+2=输出样例143此题代码复制于基于二叉树的表达式求值算法#include<bi

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com262基于哈夫曼树的数据压缩算法描述输入一串字符串，根据给定的字符串中字符出现的频率建立相应哈夫曼树，构造哈夫曼编码表，在此基础上可以对待压缩文件进行压缩（即编码），同时可以对压缩后的二进制编码文件进行解压（即译码）。输入多组数据，每组数据一行，为一个字符串（只考虑26个小写字母即可）。当输入字符串为“0”时，输入结束。输出每组数据输出2n+4行（n为输入串中字符类别的个数）。第一行为统计出来的字符出现频率（只输出存在的

//代码在“BJFU_数据结构习题_268基于二叉链表的二叉树叶子结点到根结点的路径的求解”上修改的#include<iostream>using namespace std;char path[100];char path1[100];char path2[100];typedef struct BiTNode{ char data; struct ...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com299计数排序描述有一种简单的排序算法，叫做计数排序。这种排序算法对一个待排序的表进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键字互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设针对某一个记录，统计出的计数值为c，那么，这...

298基于快排思想的查找描述借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于key的记录。设此组记录存放于数组r[l…n]中。若查找成功，则输出该记录在r数组中的位置及其值，否则显示“not find”信息。输入多组数据，每组数据三行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数），第三行为要查找的key值。当n等于0时，输入结束。输出...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com297数组的正负排序描述对n个关键字取整数值的记录序列进行整理，以使所有关键字为负值的记录排在关键字为非负值的记录之前，要求：①采用顺序存储结构，至多使用一个记录的辅助存储空间;②算法的时间复杂度为O(n)。输入多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为整...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com持续补充中黑色标题意味代码未完成204基于顺序存储结构的图书信息表的创建和输出205基于顺序存储结构的图书信息表的排序206基于顺序存储结构的图书信息表的修改207基于顺序存储结构的图书信息表的逆序存储208基于顺序存储结构的图书信息表的最贵图书的查找209基于顺序存储结构的图书信息表的最爱图书的查找210...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com296砾石的交换排序描述设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红，白，蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置。输入多组数据，每组数据两行。第一行为砾石的数量n，第二行有n个...

295基于双向链表的双向冒泡排序法描述有n个记录存储在带头结点的双向链表中，利用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。(注：双向冒泡排序即相邻两趟排序向相反方向冒泡)。输入多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。输出每组数据输出一行，为从小到大排序后的序列。每两个元素之间用空...

294基于链表的简单选择排序描述试以单链表为存储结构，实现简单选择排序算法。输入多组数据，每组数据两行。第一行为序列的长度n，第二行为序列的n个元素（元素之间用空格分隔，元素都为正整数）。当n等于0时，输入结束。输出每组数据输出一行，为从小到大排序后的序列。每两个元素之间用空格隔开。输入样例 154 5 3 2 961 3 5 7 9 20输出样例 12 3 4 5 9...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com293基于链地址法的散列表的删除描述请写出在散列表中删除关键字为k的一个记录的算法，设散列函数为H，H(key)=key%13，解决冲突的方法为链地址法。输入多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要删除的关键字k。当n=0时输入结束。输出每组数据输出用链地址法处...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com292基于链地址法的散列表的插入描述请写出在散列表中插入关键字为k的一个记录的算法，设散列函数为H,H(key)=key%13，解决冲突的方法为链地址法。输入多组数据，每组三行，第一行为待输入的关键字的个数n，第二行为对应的n个关键字，第三行为需要插入的关键字k。当n=0时输入结束。输出每组数据输出用链地址法处...

平衡二叉树的高度的计算描述假设一棵平衡二叉树的每个结点都标明了平衡因子b，设计一个算法，求平衡二叉树的高度。输入多组数据，每组数据一行，为平衡二叉树的先序序列。输入的数字为该节点的平衡因子。当序列为“#”时，输入结束。输出每组数据输出一行，为平衡二叉树的高度。输入样例 1110###0##1110###0##10###输出样例 134第一种对普通的递归#include...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com290基于非递归的二叉排序树的结点的查找和插入描述已知二叉树T的结点形式为(llink,data,count,rlink)，在树中查找值为x的结点，若找到，则计数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树。请写出其非递归算法。输入多组数据，每组数据3行。第一行为二叉排序树的结点数n，第二...

289二叉排序树的限定条件下的数据输出描述已知二叉排序树采用二叉链表存储结构，根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild、rchild分别指向该结点左，右孩子的指针，data域存放结点数据。试编写算法，从小到大输出二叉排序树中所有数值大于等于x的结点的数据。要求先找到第一个满足条件的结点后，再依次输出其他满足条件的结点。输入多组数据，每组三行...

288二叉排序树的判定描述假设二叉树每个结点的元素均为一个单字符，根据给定的字符序列按照先序遍历的顺序递归创建该树的二叉链表，然后判断该二叉树是否为二叉排序树。输入多组数据，每组数据有一行。每行为一个二叉树对应的前序序列（其中‘#’表示空树）。当序列为“#”时，输入结束。输出每组数据输出1行，若此二叉树为二叉排序树则输出“YES”，否则输出“NO”。输入样例 1ba##c##ca...

287基于递归的折半查找描述请编写一个递归的折半查找算法，查找给定有序数组中的某一元素。输入多组数据，每组数据有三行。第一行为数组长度n，第二行为n个递增排列的数字，第三行为需要查找的数字k。当n=0时输入结束。输出每组数据输出一行，如果可以找到数字，则输出“YES”，否则输出“NO”。输入样例 151 4 6 7 8661 2 5 7 9 10080输出样例 1Y...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com286基于邻接矩阵的顶点的删除描述给定一个无向图，在此无向图中删除一个顶点。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表删除的顶点编号。当n和m都等于0时，输入结束。输出每...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com285基于邻接表的长度为k的简单路径的求解描述一个连通图采用邻接表作为存储结构。设计一个算法，判断无向图中任意给定的两点是否存在一条长度为k的简单路径。输入多组数据，每组m+3数据行。第一行有两个数字n，m和k，代表有n个顶点，m条边和长度k。第二行有n个字符，代表n个顶点的编号。第三行到第m+2行每行有两个字符h...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com284基于深度优先搜索的两顶点路径存在与否的判断描述设计一个算法，试基于深度优先搜索判断以邻接表方式存储的有向图中是否存在由顶点vi输入多组数据，每组m+3数据行。第一行有两个数字n和m，代表有n个顶点和m条边。第二行有n个字符，代表n个顶点的编号。第三行到第m+2行每行有两个字符h和k，代表边依附的两个顶点。第m...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com283最长的最短路径的求解描述设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点。输入多组数据，每组数据m+2行。每组数据第一行为两个整数n和m，代表有n个顶点m条路。顶点编号为1到n。第二行到第m+1行每行有三个整数a，b和c，代表顶点a和顶点b之间有一条长度为c的路。第m+2有一个整数v，代表顶点v。...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com282基于邻接表的深度优先遍历描述一个连通图采用邻接表作为存储结构。设计一个算法，实现从顶点v出发的深度优先遍历的非递归过程。输入多组数据，每组m+2数据行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个整数h和k，代表边依附的两个顶点。第m+2行有一个整数d，代表从...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com281基于邻接矩阵的边的删除描述给定一个无向图，在此无向图中增加一条边。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有两个数字f和g，代表删除的边所依附的两个顶点。当n和m都等于0时，输入结束。...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com280基于邻接表的边的删除描述给定一个无向图，在此无向图中删除一条边。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有两个数字f和g，代表删除的边所依附的两个顶点。当n和m都等于0时，输入结束。...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com279基于邻接矩阵的新边的增加描述给定一个无向图，在此无向图中增加一条边输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有两个数字f和g，代表增加的边所依附的两个顶点。当n和m都等于0时，输入结束。...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com278基于邻接表的新边的增加描述给定一个无向图，在此无向图中增加一条边。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有两个数字f和g，代表增加的边所依附的两个顶点。当n和m都等于0时，输入结束。...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com277基于邻接表的顶点的删除描述给定一个无向图，在此无向图中删除一个顶点。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表删除的顶点编号。当n和m都等于0时，输入结束。输出每组...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com276基于邻接矩阵的新顶点的增加描述给定一个无向图，在此无向图中增加一个新顶点。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表新插入的顶点编号。当n和m都等于0时，输入结束。输...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com275基于邻接表的新顶点的增加描述给定一个无向图，在此无向图中增加一个新顶点。输入多组数据，每组m+2行。第一行有两个数字n和m，代表有n个顶点和m条边。顶点编号为1到n。第二行到第m+1行每行有两个数字h和k，代表边依附的两个顶点。第m+2行有一个数字f，代表新插入的顶点编号。当n和m都等于0时，输入结束输出...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com274六度空间理论描述“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com271基于二叉链表的二叉树高度的计算描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，，编写递归算法计算二叉树的高度。输入多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数据分别输出一行，为二叉树的高度。输入样...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com270基于二叉链表的二叉树结点个数的统计描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写三个递归算法对二叉树的结点（度为0、1、2）个数进行统计。输入多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数据输出...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com269基于二叉链表的二叉树的遍历描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写三个递归算法分别实现二叉树的先序、中序和后序遍历。输入多组数据。每组数据一行，为二叉树的前序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数据输出三行，为二叉树的...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com268基于二叉链表的二叉树叶子结点到根结点的路径的求解描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写算法求出每个叶子结点到根结点的路径。输入多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数据输出n行（n...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com267基于二叉链表的二叉树最长路径的求解描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写算法求出该二叉树中第一条最长的路径。输入多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数据输出一行，第一行为二叉树的...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com266基于二叉链表的二叉树最大宽度的计算描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写算法计算该二叉树的最大宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。输入多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com265基于二叉链表的二叉树的双序遍历描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法实现该二叉树的双序遍历（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。输入多组数据。每组数据一行，为二叉树的...

欢迎登录北京林业大学OJ系统http://www.bjfuacm.com264基于二叉链表的二叉树左右孩子的交换描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，编写递归算法交换该二叉树的左右孩子。输入多组数据。每组数据一行，为二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数据输出一行。为交换左右孩子后的二...

263基于二叉链表的树结构相等的判断欢迎登录北京林业大学OJ系统http://www.bjfuacm.com描述设二叉树中每个结点的元素均为一个字符，按先序遍历的顺序建立二叉链表，按此方法创建两棵二叉树，然后编写递归算法判断这两棵树是否相等。输入多组数据，每组数据有两行。每行为一个二叉树的先序序列（序列中元素为‘0’时，表示该结点为空）。当输入只有一个“0”时，输入结束。输出每组数...