19. 十九届（2013）试题
19.1 十九届普及组
19.2 十九届提高组
一、单项选择题（共15题，每题1.5分，共计22.5分；每题有且仅有一个正确选项）
1．一个32位整型变量占用（  A  ）个字节。
A．4            B．8            C．32            D．128
2．二进制数11.01在十进制下是（  A  ）。
A．3.25            B．4.125            C．6.25            D．11.125
3．下面的故事与（  B  ）算法有着异曲同工之妙。
从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚在给小和尚
讲故事…………………………’”
A．枚举            B．递归            C．贪心            D．分治
4．1948年，（ D  ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。
A．冯•诺伊曼(John von Neumann)            B．图灵（Alan Turing）
C．欧拉（Leonhard Euler）                D．克劳德•香农（Claude Shannon）
【分析】  香农信息论鼻祖
5．已知一棵二叉树有2013个节点，则其中至多有（  A  ）个节点有2个子节点。
A．1006            B．1007            C．1023            D．1024
【分析】（1）树根深度为0，深度为10的满二叉树节点总数2047；
（2）本题树深为10的完全二叉树，与满二叉树相比少了34个节点，
（3）深度为9的满二叉树节点总数量为1023；
（4）1023-（34/2）=1006
6．在一个有向图中，如果任意两点之间都存在路径相连，则称其为连通图。右图是一个有5个顶点、8条边的连通图。若要使它不再是连通图，至少要删去其中的（  B  ）条边。
A．2            B．3            C．4            D．5
【分析】要使图不联通，只要其中某一个节点不连通即可，所有顶点度最少是3，所以最少需要删除3条边
7．斐波那契数列的定义如下：F1=1，F2=1，Fn=Fn-1+Fn-2（n≥3）。如果用下面的函数计算斐波那契数列的第n项，则其时间复杂度为（  D  ）。
function F(n:longint):longint;
begin
    if n<=2 then
        F:=1
数学二进制的算法
    else
        F:=F(n-1)+F(n-2);
end;
A．O(1)            B．O(n)            C．O(n2)            D．O(Fn)
【分析】计算F1需要1次，计算F2需要一次，计算Fn需要计算F(n-1)的次数加上F（n-2）的次数，所以其实就是计算Fn次，于是答案选择D，至于这个Fn到底是多大，数学上可以计算，它等于O((（1+sqrt(5)）/2)^n).
8．二叉查树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查树的（  B  ）是一个有序序列。
A．先序遍历        B．中序遍历        C．后序遍历        D．宽度优先遍历
9．将（2，6，10，17）分别存储到某个地址区间为0～10的哈希表中，如果哈希函数h(x)=（ D  ），将不会产生冲突，其中a mod b表示a除以b的余数。
A．x mod 11                        B．x2 mod 11
C．2x mod 11                    D．mod 11，其中表示下取整
【分析】A项6和17对11取余都是6发生冲突，B项10的平方和17的平方对11取余都是1发生冲突，C项6的两倍和17的两倍对11取余都是1发生冲突，D项分别为1，2，3，4，不冲突
10．IPv4协议使用32位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（  D  ）位地址的IPv6协议所取代。
A．40            B．48            C．64            D．128
11．二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么12个顶点的二分图至多有（  C  ）条边。
A．18            B．24            C．36            D．66
【分析】二分为6个和6个的顶点，此时边最多，有36条边。
12．（  B  ）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、跨平台的文本交换。目前它已经收录了超过十万个不同字符。
A．ASCII            B．Unicode            C．GBK2312            D．BIG5
【分析】
UNICODE与ASCII的区别 .
1.ASCII的特点
（1）ASCII 是用来表示英文字符的一种编码规范。每个ASCII字符占用1 个字节，因此，ASCII 编码可以表示的最大字符数是255（00H—FFH）。这对于英文而言，是没有问题的，一般只什么用到前128个(00H--7FH,最高位为0)。而最高位为1 的另128 个字符（80H—FFH）被称为“扩展ASCII”，一般用来存放英文的制表符、部分音标字符等等的一些其它符号。
（2）但是对于中文等比较复杂的语言，255个字符显然不够用。于是，各个国家纷纷制定了自己的文字编码规范，其中中文的文字编码规范叫做“GB2312—80”， 它是和ASCII 兼容的一种编码规范， 其实就是利用扩展ASCII没有真正标准化这一点，把一个中文字符用两个扩展ASCII 字符来表示，以区分ASCII 码部分。
    但是这个方法有问题，最大的问题就是中文的文字编码和扩展ASCII 码有重叠。而很多软件利用扩展ASCII 码的英文制表符来画表格，这样的软件用到中文系统中，这些表格就会被误认作中文字符，出现乱码。另外，由于各国和各地区都有自己的文字编码规则，它们互相冲突，这给各国和各地区交换信息带来了很大的麻烦。
2.UNICODE的产生
（1）要真正解决这个问题，不能从扩展ASCII 的角度入手，UNICODE作为一个全新的编码系统应运而生，它可以将中文、法文、德文……等等所有的文字统一起来考虑，为每一个文字都分配一个单独的编码。
3.什么是UNICODE
Unicode与ASCII一样也是一种字符编码方法，它占用两个字节（0000H—FFFFH）,容纳65536 个字符，这完全可以容纳全世界所有语言文字的编码。在Unicode 里，所有的字符都按一个字符来处理， 它们都有一个唯一的Unicode 码。
13．把64位非零浮点数强制转换成32位浮点数后，不可能（  D  ）。
A．大于原数        B．小于原数    C．等于原数    D．与原数符号相反
【分析】64位非零浮点数强制转换成32位浮点数，两个数会有大小上的细微差别，但不会发生符号变化，因为有专门的符号位
14．对一个n个顶点、m条边的带权有向简单图用Dijkstr算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（  B  ）。
A．O(mn+n3)      B．O(n2)        C．O((m+n)log n)      D．O((m+n2)log n)
【分析】Dijkstra算法（双重for 循环）计算单源最短路时间复杂度如果不借助堆或优先队列优化，是O（n^2）.
15．T(n)表示某个算法输入规模为n时的运算次数。如果T(1)为常数，且有递归式
T(n)=2*T(n / 2)+2n，那么T(n) = （  B  ）。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。