匿名网友
一 单项选择题（4*10分）
1.int a = 4，则对于表达式++(a++)的结果的说法正确的是（）
（A）结果为5
（B）结果为6
（C）结果为7
（D）以上都不是
2.如下代码段，哪种描述是正确的（）
class A{/*…*/};
void f(const A** p){/*…*/}
void g(const A* const* p){/*…*/}
void k(const A*& p){/*…*/}
void main()
{
const A *ca = new A();
A *a = new A();
A** p = &a;
k(ca); [1]
f(p); [2]
g(p); [3]
//…
}
（A）全部正确
（B）[2]错，[1] [3]正确
（C）[1][2]错，[3]正确
（D）[1]正确，[2][3]错
3.给出下述节点及权值（括号中数字为权值）：a(7)，b(5)，c(4)，d(2)，构造Huffman树，其带权路径长度为（ ）
（A）18
（B）35
（C）36
（D）46
4.有一场演出，共八位演员A,B,C,D,E,F,G,H参加，对其出场次序有如下要求：BH需在A之后出厂，E出场之后BF才能出场，D需要在CH之前、B之后出场，F需要在CD之前出场，G需要在CH之后出场，则下列说法正确的是（）
① 无法唯一确定B第几个出场
② 无法唯一确定D第几个出场
③ 演员的出场次序有且仅有4种方案可选
④ 任意一种方案C都必然在第6位出场
⑤ 演员的出场次序最多可以有6中方案可选
（A）①③
（B）②⑤
（C）①④⑤
（D）②③④
5.如下代码的输出结果是（）
int _tmain(int argc,_TCHAR* argv[])
{
int a[2][5] = {{2,3,4,5,6},{7,8,9,10,11}};
int *ptr = (int*)(&a+1);
cout << *(ptr-3)<<endl;
}
（A）3 （B）4 （C）9 （D）10
6.如下代码的输出结果是（）
include<iostream>
using namespace std;
int WhoAmi(int num1,int num2)
{
if(num2 == 0)
return num1;
int num = num1^num2;
int carry = (num1&num2)<<1;
return WhoAmi(num,carry);
}
int _tmain(int argc,_TCHAR* argv[])
{
cout<<WhoAmi(5,6)<<endl;
return 0;
}
（A）1 （B）11 （C）-1 （D）30
7.一动态链接库发表的导出类如下，以下哪种做法对该类的更新是没有问题的？（只列出改动部分）（）
class _decispec(dllexport)PubliClass
{
public:
virtual void A();
virtual void B();
void C();
friend void D();
//…
};
class PubliClass{/*…*/};
（A）virtual void B();
（B）virtual void A();
（C）void C() const;
（D）void D()
8.有如下函数，则funb(10)为（）
int func(unsigned int v)
{
v ^= v>>16;
v ^= v>>8;
v ^= v<<4;
v &= (0x6996>>v) & 1;
}
int funb(int n)
{
unsigned int t = 1<<n;
int val = 0;
for(int i = 0; i<t; ++i)
{
val += func(i);
}
return val;
}
（A）255 （B）511 （C）512 （D）1024
9.如下代码的输出结果是（）
#include<iostream>
using namespace std;
int function2(int a[], int b, int e)
{
if(e – b <= 1)
return abs(a[b] – a[e]) >= 3 ? a[b] : a[e];
int l = 0, r = 0;
l = function2(a, b, b+(e – b)/2);
if (l%2 == 0)
r = function2(a, b+(e -b)/2 +1, e);
else
return l;
if(l | r)
return l|r;
else
return r;
}
int main()
{
int a[] = {10, 5, 8, 4, 5, 20, 2,3};
cout<<function2(a, 0, sizeof(a)/sizeof(1))<<endl;
int b[] = {3, 5, 8, 4, 8, 30, 2, 3};
cout<<function2(b, 0, sizeof(b) / sizeof(1))<<endl;
return 0;
}
（A）15, 5 （B）10, 5 （C）20, 3 （D）其它
10.如下代码的输出结果是（）
#include<iostream>
using namespace std;
#include<iostream>
using namespace std;
void getNext(char *p, int *next, int &m)
{
int j = 0, k = -1;
next[0] = -1;
m = -1;
while(j<strlen(p) – 1)
{
if(k == -1 || p[j] == p[k])
{
j++;
k++;
next[j] = k;
if(m<k)
m = k;
}
else
{
k = next[k];
}
}
}
int func(char *s, char *p, int &m)
{
int next[100];
int count = 0, i = 0, j = 0;
getNext(p, next, m);
while(i<strlen(s))
{
if(j == -1 || s[i] == p[j])
{
i++;
j++;
}
else
{
j =next[j];
}
if(m == j)
count++;
if(j==strlen(p))
return count;
}
return -1;
}
int main()
{
char* str = “acabaabaabcaeabaabcacabaabcd”;
char* subStr = “abaabcac”;
int m = -1;
cout<<func(str, subStr, m)<<endl;
return 0;
}
（A）3 （B）4 （C）13 （D）以上都不是
二 程序设计题（20*3分）
1.给定一个字符串S， 求所有长度小于等于3的子串出现的次数，输出结果按出现次数从大到小排序，如果次数相同，按字典序排序，比如，给定字符串“abcdab”，输出结果为
a 2
ab 2
b 2
abc 1
bc 1
bcd 1
c 1
cd 1
cda 1
d 1
da 1
dab 1
函数原型：
std::vector<std::pair<std::string, int>> calculate3Gram(const std::string &S);
2.某地生态系统存在一个复杂的物种食物网，科学家们要做一个循环食物链分析，所谓“循环食物链”是指物种之间直接或间接互为食物关系，现在请：
（1）设计一个数据结构，可以存储完整的食物网
（2）根据在（1）中设计的数据结构，编写一段代码判断一个给定的食物网中是否存在循环食物链
3.有关部门正在规划建设高速铁路系统以连接全国各个城市。其中部分城市之间已经修建了铁路，建设高速铁路系统，既可以对原有线路进行翻新，也可以完全新建，而翻新成本远小于完全新建的成本。请编写一段代码计算建设高速铁路系统的最小成本。
函数原型：
double solve(const vector<pair<double, double>> & cities,
const vector<pair<int, int>>&railways,
double m, double n);
输入：
vector<pair<double, double>>cities 为各个城市的位置（x,y坐标值）。
vector<pair<int, int>>railways表示已经修建铁路，其中pair<int, int>（a,b）表示城市a和b之间已经建有铁路，a和b为城市在cities中的index，即 0<= a，b<city.size()
m为翻新铁路的单位成本，n为新建铁路的单位成本（单位成本乘以城市间的距离即为实际成本）。
返回值：
建设高速铁路系统的最小成本
