2015 初赛TG 错题解析

得分:81.5

过失性失分：T6(1.5)

未掌握的知识点失分：T3(1.5) T12(1.5) T19(1.5)

未把已知活学活用T11(1.5)

没看懂程序 T26(8) T28-1(3)

T3

1948 年，（）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

冯·诺伊曼（John von Neumann） B. 图灵（Alan Turing）
欧拉（Leonhard Euler） D. 克劳德·香农（Claude Shannon）

蒙错了——香农用信息熵的概念来描述信源的不确定度。

T5[dope]

已知一棵二叉树有 2013 个节点，则其中至多有（）个节点有 2 个子节点。

1006 B. 1007 C. 1023 D. 1024

**学过二叉树的应该都知道至少也了解，最后一个非叶子节点为**n div 2**

在二叉树没有只有一个子节点的时候

total=(2*s_2)+1=(s_0)+(s_2);

所以 (s_2)=(s_0)-1;

(s_2)=(total-1)/2,(s_0)=(total+1)/2;

第 6 题

在一个无向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有 5 个顶点、8 条边的连通图。若要使它不再是连通图，至少要删去其中的（）条边。

2 B. 3 D. 5

✔答案：B,错选：D

分析： 无向图中，不是连通图意味着一个节点的度为0，最小为3

我思考的时候认为首先要搞成一个最小生成树，再在最小生成树上减掉一条边，这个做法应该适用于至多要删去几条边

第 10 题[dope]

IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（）位地址的 IPv6 协议所取代。

40 B. 48 D. 128

我是这样猜的：IPv4->IPv6升了两级，升一级至少得加一个二进制位吧，所以32<<2就得到了128

第 11 题

二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，12 个顶点的二分图至多有（）条边。

18 B. 24 C.36 D. 66

一边6个点，以左边来看，一个点最多和对面连6条边

第 12 题

（）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。

ASCII B. Unicode C. GBK 2312 D. BIG5

又到了一年一度拼人品的时候了=w=，不过显然A是不选的

Unicode（统一码、万国码、单一码）是计算机科学领域里的一项业界标准,包括字符集、编码方案等。Unicode 是为了解决传统的字符编码方案的局限而产生的，它为每种语言中的每个字符设定了统一并且唯一的二进制编码，以满足跨语言、跨平台进行文本转换、处理的要求。1990年开始研发，1994年正式公布。Unicode通常用两个字节表示一个字符，原有的英文编码从单字节变成双字节，只需要把高字节全部填为0就可以

第 19 题

（）属于 NP 类问题。

存在一个 P 类问题
任何一个 P 类问题
任何一个不属于 P 类的问题
任何一个在（输入规模的）指数时间内能够解决的问题

貌似NP问题年年倍受青睐啊

NP问题是指还未被证明是否存在多项式算法能够解决的问题

首先需要介绍P(Polynomial,多项式)问题.P问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题.NP(Non-Deterministic Polynomial, 非确定多项式)问题,是指可以在多项式时间内被非确定机(他可以猜,他总是能猜到最能满足你需要的那种选择,如果你让他解决n皇后问题,他只要猜n次就能完成----每次都是那么幸运)解决的问题

第 26 题

#include <stdio.h> 
#include <string.h> 
#define SIZE 100 
int n, m, p, count; 
int a[SIZE][SIZE]; 
void colour(int x, int y) 
{ 
 count++; 
 a[x][y] = 1; 
 if ((x > 1) && (a[x - 1][y] == 0)) 
  colour(x - 1, y); 
 if ((y > 1) && (a[x][y - 1] == 0)) 
  colour(x, y - 1); 
 if ((x < n) && (a[x + 1][y] == 0)) 
  colour(x + 1, y); 
 if ((y < m) && (a[x][y + 1] == 0)) 
  colour(x, y + 1);  
} 
int main() 
{ 
 int i, j, x, y, ans; 
 memset(a, 0, sizeof(a)); 
 scanf("%d%d%d", &n, &m, &p); 
 for (i = 1; i <= p; i++) { 
  scanf("%d%d", &x, &y); 
  a[x][y] = 1; 
 } 
 ans = 0;
for (i = 1; i <= n; i++) 
  for (j = 1; j <= m; j++) 
   if (a[i][j] == 0) { 
    count = 0; 
    colour(i, j); 
    if (ans < count) 
     ans = count; 
   } 
 printf("%d
", ans); 
 return 0; 
}

输入： 6 5 9 1 4 2 3 2 4 3 2 4 1 4 3 4 5 5 4 6 4 输出：_________

正确答案： 7

flood fill的最大面积