三、 完善程序（单选题, 每小题 3 分, 共计 30 分）
1. 家住农村的小明同学想去最要好的朋友刘东家去玩，刚好前段时间台风弄的到处都是泥水坑，小明家在坐标（0,0）的位置，刘东家在坐标（X，Y）的位置（-100<=X,Y<=100），小明看到地上有N（1<=N<=1000）个泥水坑，每个泥水坑的坐标为（Ai，Bi）位置（-100<=Ai, Bi<=100），他不想弄脏白色运动鞋，小明只能平行坐标轴一格一格移动（不能走斜对角线或者跳格，每格路径长度为1），为了避开泥水坑并尽快赶到刘东家，至少要走多少路？如果有路打印出路径长度，没有路打印“No Answer”。
输入描述：
第一行输入X，Y，N。
第二行到N+1行输入N个数对Ai,Bi。
输出描述:
输出一个整数，如果通过按字符不能使初始字符串变为最终字符串，则输出0, 否则输出最少需要按几次字符可以使初始字符串变为最终字符串。
样例输入
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
样例输出
11
01 #include<bits/stdc++.h>
02 using namespace std;
03 bool a[1005][1005], v[1005][1005];
04 struct point
05 {
06 int x,y,step;
07 };
08 int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
09 queue<point> r;
10 int main()
11 {
12 int n,startx,starty,p,q;
13 cin>>startx>>starty>>n;
14 startx += 100, starty += 100, p = 100, q = 100;
15 for(int i=1;i<=n;i++)
16 {
17 int j,k;
18 cin>>j>>k;
19 ① = true;
20 }
21 point start;
22 start.x = startx;
23 start.y = starty;
24 start.step = 0;
25 r.push(start);
26 v[startx][starty]=true;
27 int flag = 0;
28 while(!r.empty())
29 {
30 int x = r.front().x;
31 int y = r.front().y;
32 if(x==p && y==q)
33 {
34 printf("%d",r.front().step);
35 ②;
36 break;
37 }
38 for(int k=0;③;k++)
39 {
40 int tx,ty;
41 tx = x + dx[k];
42 ty = y + dy[k];
43 if(a[tx][ty] == false && v[tx][ty] == false)
44 {
45 point temp;
46 temp.x = tx;
47 temp.y = ty;
48 temp.step = ④;
49 r.push(temp);
50 ⑤ = true;
51 }
52 }
53 r.pop();
54 }
55 if(flag == 0)
56 printf("no answer");
57 return 0;
58 }
1) ①处应填( )
A. a[j+100][k+100] B. a[j][k]
C. a[j+100][k] D. a[j][k+100]
2) ②处应填( )
A. flag = 0 B. flag = 1
C. v[tx][ty] = true D. v[tx][ty] = false
3) ③处应填( )
A. k <= 3 B. k <= 4
C. k <= n D. k <= r.front().step
4) ④处应填( )
A. start.step B. start.step + 1
C. r.front().step + 1 D. r.front().step
5) ⑤处应填( )
A. a[tx+1][ty+1] B. v[tx+1][ty+1]
C. a[tx][ty] D. v[tx][ty]
2. 在大规模数据处理中，经常需要处理Top N 问题：在乱序数据中找到前 N 个数据。例如在海量搜索结果中找到权重最高的前 N 个结果。如下代码是一个经典的堆排序过程，请补充完整全部程序。
1 #include <cstdio>
2 #include <algorithm>
3 using namespace std;
4 void heap_handle(int *a, int index, int num)
5 {
6 int left = 2*index;
7 int right = 2*index+1;
8 int maxroot = index;
9 if( index <= num/2 )
10 {
11 if( ① )
12 {
13 maxroot = left;
14 }
15 if( ② )
16 {
17 maxroot = right;
18 }
19 if( ③ )
20 {
21 swap(a[index], a[maxroot]);
22 ④;
23 }
24 }
25 }
26 void build_heap(int *a, int num)
27 {
28 for(int i = num/2; i >= 1; --i)
29 {
30 heap_handle(a, i, num);
31 }
32 }
33 void heap_sort(int *a, int num)
34 {
35 int i;
36 build_heap(a, num);
37 for(i = num; i >=1; --i)
38 {
39 swap(a[1], a[i]);
40 ⑤;
41 }
42 }
43 void display(int *a, int num)
44 {
45 for(int i = 1; i <= num; ++i)
46 {
47 printf("%d ",a[i]);
48 }
49 printf("\n");
50 }
51 int main()
52 {
53 int n;
54 scanf("%d",&n);
55 int a[n+1];
56 for(int i = 1; i <= n; i++)
57 {
58 scanf("%d",a+i);
59 }
60
61 heap_sort(a, n);
62 display(a, n);
63 return 0;
64 }
1）①处应填( )
A．left > num && a[left] > a[maxroot]
B. left <= num && a[left] > a[maxroot]
C. right > num && a[right] > a[maxroot]
D. right <= num && a[right] > a[maxroot]
2) ②处应填( )
A．left > num && a[left] > a[maxroot]
B. left <= num && a[left] > a[maxroot]
C. right > num && a[right] > a[maxroot]
D. right <= num && a[right] > a[maxroot]
3) ③处应填( )
A．maxroot B. maxroot!=index C. maxroot%2 D. maxroot<=num
4) ④处应填( )
A．heap_handle(a, index, num)
B. heap_handle(a, maxroot, num)
C. heap_handle(a, maxroot-1, num)
D. heap_handle(a, maxroot, num/2)
5) ⑤处应填( )
A．heap_handle(a, 1, i)
B. heap_handle(a, 1, i+1)
C. heap_handle(a, 1, i-1)
D. heap_handle(a, 1, num)
答案：----->E:\csp\初赛集训模拟题试题包\23梦熊\押题卷