文章目录
一、判断题
1-1
只有当局部最优跟全局最优解一致的时候，贪心法才能给出正确的解。
T F
1-2
令S为活动选择问题（Activity Selection Problem）中所有活动的集合。则一定存在S的某个最大相容活动子集是包含了最早结束的活动am的。
T F
1-3
令S为活动选择问题（Activity Selection Problem）中所有活动的集合。则最早结束的活动am一定被包含在S的所有最大相容活动子集中。
T F
1-4
在活动选择问题（Activity Selection Problem）中，令 S 为活动的集合。以“每次收集最迟开始的活动”为贪心原则，可以正确找到 S 中相互兼容活动的最大规模的子集合。
T F
1-5
令 C 为字母集，其中每个字符 c 有对应频率 c.freq。若 C 的大小为 n，则其中任一字符 c 的最优前缀编码长度都不会超过 n−1.
T F
二、单选题
2-1
给定一段文本中的4个字符(a, b, c, d)。设a和b具有最低的出现频率。下列哪组编码是这段文本可能的哈夫曼编码？
A. a: 000, b:001, c:01, d:1
B.a: 000, b:001, c:01, d:11
C.a: 000, b:001, c:10, d:1
D.a: 010, b:001, c:01, d:1
2-2
给定一段文本中的 4 个字符 (u,v,w,x) 及其出现频率 (fu,fv,fw,fx)。若对应的哈夫曼编码为 u: 00, v: 010, w: 011, x: 1，则下列哪组频率可能对应
(fu,fv,fw,fx)?
A.15, 23, 16, 45
B.30, 21, 12, 33
C.41, 12, 20, 32
D.55, 22, 18, 46
三、编程题
7-1 汽车加油问题 (20 分)
题目描述
题目来源：王晓东《算法设计与分析》
一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。
输入格式:
第一行有 2 个正整数n和 k（k<=1000 )，表示汽车加满油后可行驶n公里，且旅途中有 k个加油站。 第二行有 k+1 个整数，表示第 k 个加油站与第k-1 个加油站之间的距离。 第 0 个加油站表示出发地，汽车已加满油。 第 k+1 个加油站表示目的地。
输出格式:
输出最少加油次数。如果无法到达目的地，则输出“No Solution!”。
输入样例:
7 7
1 2 3 4 5 1 6 6
输出样例:
4
基本思路
cnt_res记录需要加油次数
each表示到每个车站时油量
若each足够到达下一站，则该站不用加油
若each不够，加满后够到下一站，则该站加油
若each不够，加满后也不够，则输出"No Solution!"
参考代码
#include <iostream>
using namespace std;
int main()
{
int n,k;
cin>>n>>k;
int a[k+1];
for(int i=0;i<=k;i++)
{
cin>>a[i];
}
int cnt_res=0;
int each=n;
bool flag=true;
for(int i=1;i<k;i++)
{
each-=a[i];
if(each>=a[i+1])
{
continue;
}
else if(n>=a[i+1])
{
cnt_res++;
each=n;
}
else{
cout<<"No Solution!";
flag=false;
break;
}
}
if(flag) cout<<cnt_res;
}
7-3 排队接水 (15 分)
题目描述
有n个人在一个水龙头前排队接水，假如每个人接水的时间为Ti，请编程找出这n个人排队的一种顺序，使得n个人的平均等待时间最小。
输入格式:
共两行，第一行为n(1≤n≤1000)；第二行分别表示第1个人到第n个人每人的接水时间T1，T2，…，Tn，每个数据之间有1个空格。
输出格式:
输出为这种排列方案下的平均等待时间(输出结果精确到小数点后两位)。
输入样例:
10
56 12 1 99 1000 234 33 55 99 812
输出样例:
291.90
基本思路
排序后存每个人的等待时间，求和后求平均
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
struct peo{
int each_time;
int wait_time=0;
};
bool cmp(peo a,peo b){
return a.each_time<b.each_time;
}
int main()
{
int n;
cin>>n;
peo people[n];
for(int i=0;i<n;i++)
{
cin>>people[i].each_time;
}
sort(people,people+n,cmp);
int each=0;
for(int i=0;i<n;i++)
{
people[i].wait_time+=each;
each+=people[i].each_time;
}
double sum=0;
for(int i=0;i<n;i++)
{
sum+=people[i].wait_time;
// cout<<people[i].wait_time<<" ";
}
printf("%.2lf",sum/n);
}
7-10 选点问题 (15 分)
题目描述
数轴上有n个闭区间[ai, bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
输入格式:
第一行一个数字n，表示有n个闭区间。 下面n行，每行包含2个数字，表示闭区间[ai, bi]
输出格式:
一个整数，表示至少需要几个点
输入样例:
在这里给出一组输入。例如：
3
1 3
2 4
5 6
输出样例:
在这里给出相应的输出。例如：
2
基本思路
从头开始循环，看能同时相交的最大区间数，与前面有相交的区间visit设为1，具体可参考上机题中的会场安排问题，不过那个是要不相交，这个是要相交
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
struct p{
int start;
int end;
int visited=0;
};
bool cmp(p a,p b)
{
if(a.start==b.start)
{
return a.end<b.end;
}
else{
return a.start<b.start;
}
}
int main()
{
int n;
cin>>n;
p point[n];
for(int i=0;i<n;i++)
{
cin>>point[i].start>>point[i].end;
}
sort(point,point+n,cmp);
int cnt_res=0;
for(int i=0;i<n;i++)
{
if(point[i].visited==0)
{
cnt_res++;
for(int j=i+1;j<n;j++)
{
if(point[j].start<=point[i].end&&point[j].visited==0)
{
point[j].visited=1;
}
}
}
}
cout<<cnt_res;
}
7-4 程序存储问题 (90 分)
题目描述
设有n 个程序{1,2,…, n }要存放在长度为L的磁带上。程序i存放在磁带上的长度是 li，1≤i≤n。 程序存储问题要求确定这n 个程序在磁带上的一个存储方案， 使得能够在磁带上存储尽可能多的程序。 对于给定的n个程序存放在磁带上的长度，计算磁带上最多可以存储的程序数。
输入格式:
第一行是2 个正整数，分别表示文件个数n和磁带的长度L。接下来的1行中，有n个正整数，表示程序存放在磁带上的长度。
输出格式:
输出最多可以存储的程序数。
输入样例:
在这里给出一组输入。例如：
6 50
2 3 13 8 80 20
输出样例:
在这里给出相应的输出。例如：
5
基本思路
排序后遍历，相加直到超过所能存储的最大值
参考代码
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n,l;
cin>>n>>l;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
sort(a,a+n);
int sum=0;
int cnt_res=0;
for(int i=0;i<n;i++)
{
if(sum+a[i]<=l)
{
sum+=a[i];
cnt_res++;
}
else{
break;
}
}
cout<<cnt_res;
}