题库 第849页
编程题：二叉树的确定
二叉树采用二叉链表存储，要求根据给定的先序遍历序列和中序遍历序列建立二叉树，并输出后序遍历序列、结点总数、叶子数、度为1的结点数、度为2的结点数。### 输入格式:测试数据有多组，处理到文件尾。每组测试数据的第一行输入结点数n（1≤n≤10…
编程题：散步
最近HY喜欢上了散步。HY住在南山校区，他发现南山校区有n个景点（从1到n进行编号）很值得观赏，比如竹林舞步，小河夕阳等。HY不想错过每个景点，但又不想在一次散步过程中经过任意一个景点超过一次。HY的散步方案要求是从住所（设编号为0）出发，…
编程题：排序与查找
先对给定的待排序序列进行快速排序，再对待查找序列进行二分查找。快速排序的每次划分以首元素为支点，而且支点前的排序码小于等于支点的排序码，支点后的排序码大于支点的排序码。### 输入格式:测试数据有多组，处理到文件尾。每组测试数据第一行输入一…
编程题：二路归并排序
给定一个整数序列，请按非递减序输出采用二路归并排序（递归法）的各趟排序后的结果（每完成一次归并操作就输出归并后的结果）。### 输入格式:测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。…
编程题：堆排序
给定一个整数序列，请按非递减序输出采用堆排序的各趟排序后的结果。### 输入格式:测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。### 输出格式:对于每组测试，输出若干行，每行是一趟排…
编程题：快速排序
给定一个整数序列，请按非递减序输出采用快速排序（递归法）的各趟排序后的结果。注意：每趟排序以排序区间的首元素为枢轴（支点）。### 输入格式:测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整…
编程题：直接插入排序
给定一个整数序列，请按非递减序输出采用直接插入排序的各趟排序后的结果。### 输入格式:测试数据有多组，处理到文件尾。每组测试数据第一行输入一个整数n（1≤n≤100），第二行输入n个整数。### 输出格式:对于每组测试，输出若干行，每行是…
编程题：题目统计
在ACM程序设计竞赛赛场，当某个队伍正确解答一道题目后就会在其前面升起1个彩色气球。而且每种颜色的气球只能用在一道题目上，所以不同颜色的气球不能相互替代。已知比赛过程中已送出的气球数量以及每个气球的颜色，请统计已成功解决的不同题目的总数。#…
编程题：哈希查找的平均查找长度
对于给定的关键字序列，求采用哈希查找时查找成功和查找失败的平均查找长度。哈希函数：H(key) = key % K，其中K为某个不大于哈希表长M的整数。采用线性探测再散列处理冲突。### 输入格式:测试数据有多组，处理到文件尾。对于每组测试…
某国准备选择新的首都，并对新首都的位置提出要求：即新首都到该国所有其他城市的平均距离最短（当然并不一定要求城市之间直达，间接道路也是允许的，但必须可达）。
已知该国的城市信息，请回答新首都应选择哪一个城市。
### 输入格式:
首先输入一个正整数T，表示测试数据的组数，然后是T组测试数据。每组测试数据第一行输入2个整数n和m，表示该国的城市总数以及现有的道路总数（1≤n≤100， 0≤m≤n*(n-1)/2 ），为方便起见，我们规定城市编号为1到n。
接下来
某国准备选择新的首都，并对新首都的位置提出要求：即新首都到该国所有其他城市的平均距离最短（当然并不一定要求城市之间直达，间接道路也是允许的，但必须可达）。已知该国的城市信息，请回答新首都应选择哪一个城市。### 输入格式:首先输入一个正整数…
