B

[考点] 链表
[解析] 本题中，s.link=p.link指的是s的后继指向p的后继，p.link=s标识的是p的后继为s，这样就可以实现在结点p之后插入结点s的操作。所以，选项B正确。

B

[考点] 链表
[解析] 当在单链表的两个结点之间插入一个新的结点时，需要把前面结点的指针域指向新插入的结点(q.link=s)，把新插入结点的指针域指向后面的结点(s.link=p)。所以，选项B正确。

A

[考点] 链表

D

[考点] 链表
[解析] 循环链表(Circular LinkedList)是一种首尾相接的链表，它与单链表的唯一区别在于对尾结点的处理。因为在单链表中，尾结点的指针域改为指向头结点就得到了单循环链表。单循环链表可以用头指针head或尾指针rear表示，用尾指针rear表示的单循环链表查找开始结点和尾结点就很方便，查找的时间复杂度为O(l)。
   循环链表带头结点，链表最后一个结点的link指向链表的头结点，而链表头结点的link才指向第一个结点。因此，删除操作的步骤如下：首先找到待删除的结点：s=rear.link.link，接着在链表中删除结点s(让头结点指向链表中第二个结点)：rear.link.link=s.link。所以，选项D正确。

B

[考点] 链表
[解析] 对于选项A，最后一个操作p.right.left=s，此时，p.right指向s,p.right.left=s等价于s.left=s，显然是错误的。因此，选项A错误。
   对于选项B，描述正确。因此，选项B正确。
   对于选项C，如果先执行语句p.right=s，由于没有记录结点p的后继结点，后面的操作将无法找到结点p的后继结点。因此，选项C错误。
   对于选项D，p.right.left=s也等价于s.left=s，显然是错误的。因此，选项D错误。

C

[考点] 栈和队列
[解析] 栈是一个后进先出的数据结构，可以根据这个特点进行分析。
   对于选项A，可以把字符A、B、C、D、E按顺序入栈，然后出栈，此时就可以得到选项A,中的序列。所以，选项A正确。
   对于选项B，由于序列第一个元素为字符D，那么肯定需要先把字符A、B、C、D入栈，然后，字符D出栈得到第一个元素字符D，由于序列的下一个元素为字符E，因此，下一步需要把字符E入栈再出栈，此时就可以得到字符E，接下来栈中的元素依次出栈得到序列CBA。所以，选项B正确。
   对于选项C，序列第一个元素为字符D，那么肯定需要先把字符A、B、C、D入栈，然后字符D出栈得到第一个元素字符D，由于第二个元素为字符C，那么下一步字符C出栈得到序列DC，接下来序列为E，那么需要把字符E入栈再出栈得到字符E，此时栈中字符A在栈底，字符B在栈项，只能得到出栈序列BA，而无法得到序列AB。因此，不可能得到输出序列DCEAB。所以，选项C错误。
   对于选项D，字符A、B、C、D、E五个元素每个元素入栈后就马上出栈，此时就可以得到这个序列。所以，选项D正确。
   因此，本题的答案为C。

A

[考点] 栈和队列

C

[考点] 栈和队列

A

[考点] 栈和队列
[解析] 栈是一种特殊的线性表，在实现的时候可以把顺序表的头看作栈底。栈顶索引top指向栈顶的下一个位置，初始化top=0，对于出栈操作，首先，向索引为top的位置放入入栈的元素，然后，top+1，由此可见，入栈操作栈指针的变化为top++；而对于出栈操作，首先要判断栈是否为空(top=0时栈为空)，如果不为空，则首先进行top-1操作，然后再取出top所在位置的元素，此时指针的变化为--top。所以，选项A正确。

D

[考点] 栈和队列
[解析] 队列是一种线性表，它只允许在表的前端(front)进行删除操作，在表的后端(rear)进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。
   在循环队列中，队头指向的是队首元素的前一个位置，队尾指向队尾元素所在位置。循环队列的front和rear必有一个不指向实质元素，否则，无法判断队列满或空。而且队列头的下标有可能会小于队列尾的下标。所以，当前队列中的元素个数是(rear-froot+m)%m。因此，选项D正确。

A

[考点] 二叉树
[解析] 二叉树是每个结点最多有两个子树的树结构，通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。所谓遍历(traversal)，是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。而通常情况下，如果中序遍历未知，则无法还原出二叉树。但本题只要求判断根结点的孩子结点，因此，是可以实现的。
   二叉树中的前序遍历也叫作先根遍历、先序遍历，遵循的原则为“根左右”，即首先遍历根结点，再遍历根结点的左子树结点，最后遍历根结点的右子树结点。从前序遍历序列可知，结点e紧跟着结点a，可得结论：①结点a为根结点；②当结点e为结点a的右孩子时，结点a有且仅有结点e-个孩子。
   二叉树中的后序遍历也叫作后根遍历，遵循的原则为“左右根”，即首先遍历左子树结点，再遍历右子树结点，最后遍历根结点。从后序遍历序列可知，结点e之后紧跟结点a，可得结论：当结点e为结点a的左孩子时，结点a有且仅有结点e一个孩子。从前面3个结论可知根结点的孩子有且仅有e。
   通过前序遍历序列和后序遍历序列不能确定唯一的一棵二叉树，本例存在如下图所示的两种情况。
   
   无论是以上哪一种情况，都可以看出根结点的孩子结点只有e。通过以上分析可知，选项
   A是正确的。

C

[考点] 二叉树
[解析] 根据题目意思可知，m个结点共有3m个指针，而除了根结点外，每个结点都有父结点(即需要占用一个父结点的指针)，所以，空指针数为3m-(m-1)=2m+1，选项C正确。

D

[考点] 二叉树
[解析] 度的含义是一个结点所拥有的孩子个数。结点的度为0表示该结点没有孩子结点，也就是说，该结点为叶子结点。结点的度为2表示该结点有两个孩子结点。
   在二叉树中，存在这样一个结论：对于任何一棵二叉树，度为0的结点(就是叶子结点)数总是比度为2的结点数多一个。即假定度为0的结点(就是叶子结点)个数为n0，度为2的结点的个数为n2，那么数值上满足如下公式：n0=n2+1。证明过程如下。
   假设n1为二叉树T中度为1的结点数，因为二叉树中所有结点的度都小于或等于2，所以，其结点总数为：
   n=n0+n1+n2
   而二叉树中的分支数，除了根结点外，其余结点都有一个分支进入，设B为分支总数，则n=B+1。由于这些分支是由度为1或2的结点射出的，所以，B=n1+2n2，于是得出如下结论：
   n=n1+2n2+1
   由上述表达式可得：n0=n2+1。
   本题中，由于已知叶子结点数为20，即n0的值为20，所以，n2的值为19，选项D正确。

A

[考点] 二叉树
[解析] 对于任何一棵二叉树，度为0的结点(就是叶子结点)数总是比度为2的结点数多一个。即假定度为0的结点(就是叶子结点)个数为n0，度为2的结点的个数为n2，那么数值上满足如下公式：n0=n2+1。
   而在一个完全二叉树中，其左右子树的深度之差不大于1，所以，只可能只有一个度为1的结点，或者没有。定义二叉树中所有结点个数为n，度为1的结点数为n1，那么n0+n1+n2=n，而n0=n2+1，所以叶子结点的个数n0=(n+1-n1)/2，其中n1可能为0，可能为1，n=289，只有当n1=0的时候，n+1-n1才能整除2，因此，n1=0，此时n0=(289+1)/2=145。所以，选项A正确。

B

[考点] 二叉树
[解析] 如果需要得到的序列为递增序列，按照二叉排序树的定义，应该先访问左子树，再访问根结点，最后访问右子树，根据定义可知，能够得到一个递增有序序列的遍历方式是中序遍历。所以，选项B正确。

B

[考点] 二叉树
[解析] 本题中，由于没有明确交代二叉树的类型或性质，所以，本题中的二叉树是无法确定类型的，自然而然也就不一定是平衡的了。也就是说，深度d的值并不一定等于logn，很有可能d的值比logn的值大，而栈空间的大小通常为二叉树的深度，所以，栈的大小应该是O(d)，而不是O(logn)。因此，本题的答案为B。

D

[考点] 二叉树
[解析] 对于二叉排序树而言，右结点元素的值总是比根结点元素的值大，左结点元素的值总是比根结点元素的值小。本题中，给出的序列是递增的。通过逐一对比可知，只有选项D正确。

A

[考点] 图
[解析] 本题要想选出正确答案，首先需要弄懂度的概念。度指的是与该顶点相关联的边数。在有向图中，度又分为入度(in-degree)和出度(out-degree)。以某顶点为弧头，终止于该顶点的弧的数目称为该顶点的入度。以某项点为弧尾，起始于该顶点的弧的数目称为该顶点的出度。在某顶点的入度和出度的和称为该顶点的度。
   在有向图的邻接表中，从一个顶点出发的弧链接在同一链表中，邻接表中结点的个数恰为图中弧的数目，所以，顶点入度之和为弧数和的一倍。如果为无向图，同一条边有两个结点，分别出现在和它相关的两个顶点的链表中，因此，无向图的邻接表中结点个数为边数的2倍。本题中顶点的出度之和为m，所以，所有顶点的入度之和也为m(一条弧对应一个入度与一个出度)，通过以上分析可知，选项A正确。

B

[考点] 图
[解析] 如果图中的每条边都是有方向的，则称为有向图。在一个有向图中，边是由两个顶点组成的有序对，有序对通常用尖括号表示，例如＜vi,vj＞表示一条有向边，其中vi是边的始点，vj是边的终点。在有向图中，＜vi,vj＞和＜vj,vi＞代表两条不同的有向边。
   在有向图中，任意两个结点之间都可以形成一对有向边，对于具有n个顶点的有向图，其边的条数为n(n-1)。所以，选项B正确。

D

[考点] 图
[解析] 本题要选出正确答案，必须弄明白无向图的深度优先遍历的原理。其实，图的深度优先遍历类似于树的前序遍历。假设给定无向图G的初态是所有顶点均未曾被访问过，深度优先遍历过程是这样的：在无向图G中任选一个顶点v为初始出发点(源点)，首先访问源点v，并将其标记为已访问过，然后，依次从源点v出发，搜索源点v的每个相邻结点w。如果结点w未曾被访问过，那么以结点w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点(亦称为从源点可达的顶点)均已被访问为止。如果此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
   图的深度优先遍历伪代码如下所示。
   (1)访问顶点v; visited[v]=1;    //算法执行前visited[n]=0
   (2)w=顶点v的第一个邻接点;
   (3)while(w存在)
   if(w未被访问)
   从顶点w出发递归执行该算法;
   w=顶点v的下一个邻接点;
   本题中，按照上述方法可知，选项D正确。

B

[考点] 图
[解析] 如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条，有这样一条路径，沿此路径上各边的权值总和(称为路径长度)最小，该路径称为最短路径。
   本题中，如果将各条边的权值按从小到大排序，权值乘以2之后的排序也不会变，也就是权重的相对关系不变，p仍是最短路径。所以，选项B正确。

B

[考点] 图
[解析] 图的广度优先搜索算法需使用的辅助数据结构为队列，图的深度优先搜索算法需使用的辅助数据结构为栈。
   什么是广度优先搜索呢?当一个结点被加入队列时，要标记为已遍历。遍历过程中，对于队列第一个元素，遍历其所有能够一步达到的结点；如果是标记未遍历的，将其加入队列，从第一个元素出发所有能一步直接达到的结点遍历结束后将这个元素出列。广度优先需要保证先访问顶点的未访问邻接点优先访问，恰好就是先进先出。整个过程也可以看作一个倒立的树形，具体步骤如下：
   (1)把根结点放到队列的末尾。
   (2)每次从队列的头部取出一个元素，查看这个元素所有的一级元素，把它们放到队列的末尾，并把这个元素记为它下一级元素的前驱。
   (3)找到所要找的元素时结束程序。
   (4)如果遍历整棵树还没有找到，结束程序。
   什么是图的深度优先搜索呢?当遍历到某个结点A时，如果标记未遍历，将其入栈，遍历它能够一步直接达到的结点；如果找到的结点标记未遍历，将其入栈且标记为已遍历，然后对其进行类似A的操作，否则，找能够一步直接达到的结点进行类似操作，直到所有能够一步直接达到的结点都已遍历，将A出栈。
   整个过程可以想象成一个倒立的树形，具体步骤如下：
   (1)把根结点压入栈中。
   (2)每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素记为它下一级元素的前驱。
   (3)找到所要找的元素时结束程序。
   (4)如果遍历整棵树还没有找到，结束程序。
   根据以上的分析可知，本题的答案为B。

C

[考点] 图
[解析] 图的遍历指的是从图中的任意一个顶点出发，对图中的所有顶点访问一次且仅访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其他操作都是建立在遍历操作的基础之上。
   由于图的复杂性，图的遍历操作也比较复杂，主要表现在以下几个方面：
   (1)在图中，没有一个固定的首结点，因为任意一个顶点都可作为第一个被访问的结点。
   (2)在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
   (3)在图中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
   (4)在图中，一个顶点可以和其他多个顶点相连，当访问过这样的顶点后，存在如何选取下一个要访问的顶点的问题。
   鉴于图的遍历比较复杂，通常情况下，图的遍历有两种方式：深度优先遍历(Depth First Search, DFS)和广度优先遍历(Breadth First Search, BFS)。由于图存在回路，所以，在遍历过程中，为了区别一个顶点是否已经被访问过和避免一个顶点被多次访问，应记下每个访问过的顶点，即每个顶点对应有一个标志位，该标志位初始值为False(表示未访问)，一旦该顶点被访问，就将其置为True(表示已访问)，以后在遍历图的过程中，如果又碰到该顶点，视其标志位的状态来决定是否对其访问。
   通常情况下，除了使用递归法可以实现图的遍历以外，还可以使用栈的方法实现，具体方法如下：①如果栈为空，则退出程序，否则，访问栈顶结点，但不弹出栈顶结点；②如果栈项结点的所有直接邻接点都已访问过，则弹出栈项结点，否则，将该栈顶结点未访问的其中一个邻接点压入栈中，同时，标记该邻接点为已访问，继续执行①。所以，选项C中的描述是错误的。
   [考点] 图

B

A

[解析] 大顶堆要求结点的关键字既大于或等于左孩子的关键字值，又大于或等于右孩子的关键字值，且要求是完全二叉树。大顶堆具有如下性质：k(i)≥k(2i)且k(i)≥k(2i+1)。很显然，本题中的序列正好满足这一要求。所以，选项A正确。

B

[解析] 本题中，数组和链表顺序遍历的时间复杂度都为O(n)。具体而言，有序链表顺序遍历的时间复杂度为O(n)，对于删除和插入操作，虽然它们的时间复杂度都为O(l)(因为不需要结点的移动操作)，但是在删除前首先得找到待删除结点的地址，这个操作的时间复杂度为O(n)，在插入结点前，首先得找到结点应该被插入的地方，这个操作的时间复杂度也为O(n)，因此，插入与删除的时间复杂度都为O(n)。
   对于有序数组而言，顺序遍历的时间复杂度也为O(n)。插入的时候只需要找到待插入的位置，然后把其余的元素依次向后移动一个位置；同理，当删除一个元素的时候，需要把这个元素后面的所有元素依次向前移动一个位置。
   通过以上分析可知，与数组相比，链表在删除与插入操作的时候，没有额外的元素移动操作，因此，具有更高的效率。所以，选项A错误，选项B正确。
   对于选项C，哈希表即散列表，它是通过计算待添加元素的hash值来决定存储位置的，因此，也无法维持数据的有序，所以，选项C错误。
   本题中，对于选项D，由于队列是先进先出的数据结构，且只能在队尾添加元素，所以，队列无法维持数据有序，选项D错误。
   综上可知，本题的答案为B。

A

[解析] 只要弄懂了文件的各类组织形式，问题也就迎刃而解了。
   本题中，对于选项A，顺序文件由一系列记录按照某种顺序排列形成。在顺序文件中，记录按其在文件中的逻辑顺序依次进入存储介质而建立，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。它是最常用的文件组织形式。记录通常是定长的，因而能用较快的速度查找文件中的记录。在顺序文件中，如果次序相继的两个物理记录在存储介质上的存储位置是相邻的，那么它们又称为连续文件。顺序文件组织是唯一可以很容易地存储在磁盘和磁带上的文件组织。顺序文件中的记录是一个接着一个地顺序存放，只知道第一个记录的存储位置，就可以通过遍历依次知道所有记录的位置。例如，当建立顺序文件时，数据是以一个接着一个的顺序写到文件中的，在读取或查找文件中的某一数据时，也是从文件头开始，一个记录一个记录地顺序读取或查找，直到找到要读取或查找的记录为止。由于顺序文件不能直接读取某条记录的信息，因此，在对文件的随机访问中，性能不太理想。所以，选项A不适用于上述场景。
   对于选项B，在文件中随机存取记录，需要知道记录的地址。例如，一个客户想要查询银行账户，客户和出纳员都不知道客户记录的地址，此时客户只能向出纳员提供自己的个人账号。这里，索引文件可以把账号和记录地址关联起来。索引文件由数据文件组成，它是带索引的顺序文件。索引本身非常小，只占两个字段，分别为顺序文件的键和在磁盘上相应记录的地址。存取文件中的记录需按以下步骤操作：
   (1)整个索引文件都载入到内存中(文件很小，只占用很小的内存空间)。
   (2)搜索项目，用高效的算法(例如折半查询法)查找目标键。
   (3)检索记录的地址。
   (4)按照地址，检索数据记录并返回给用户。
   索引文件由索引表和主文件两部分构成。其中，索引表是一张指示逻辑记录和物理记录之间对应关系的表。索引表中的内容称作索引项。索引项按键(或逻辑记录号)进行顺序排列。若文件本身也是按关键字顺序排列，则称为索引顺序文件。否则，称为索引非顺序文件。很显然，索引文件适合随机存储。所以，选项B适用于上述场景。
   对于选项C，链接文件是对系统中已有的某个文件指定另外一个可用于访问它的名称，链接文件能否随机访问取决于它指向的文件是否适用于随机访问。因此，链接文件有可能适用于随机访问。所以，选项C适用于上述场景。
   对于选项D，Hash文件也称为散列文件，是利用散列存储方式组织的文件，亦称为直接存取文件。它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录哈希到存储设备上。在散列文件中，使用一个函数(算法)来完成一种将关键字映射到存储器地址的映射，根据用户给出的关键字，经函数计算得到目标地址，再进行目标的检索。通过上面分析可知，选项D适用于上述场景。
   通过上述分析可知，本题的答案为A。

A

[解析] 哈夫曼编码(Huffman Coding)使用到一种叫作“前缀编码”的技术，即任意一个数据的编码都不是另一个数据编码的前缀。而最优二叉树即哈夫曼树(带权路径长度最小的二叉树)就是一种实现哈夫曼编码的方式。哈夫曼编码的过程就是构造哈夫曼树的过程，构造哈夫曼树的相应算法如下图所示。
   
   (1)有一组需要编码且带有权值的字母，例如a(4)、b(8)、c(1)、d(2)、e(11)。括号内分别为各字母相对应的权值。
   (2)选取字母中权值较小的c(1)、d(2)组成一个新二叉树，其父结点的权值为这两个字母权值之和，记为f(3)，然后将该结点加入到原字母序列中去(不包括已经选择的权值最小的两个字母)，则剩下的字母为a(4)、b(8)、e(11)和f(3)。
   (3)重复进行步骤(2)，直到所有字母都加入二叉树中为止，最后得到的二叉树如下图所示。
   
   如果用0表示左分支，1表示右分支，则得到的编码为：a(110)、b(10)、c(1110)、d(1111)、e(0)。
   由于哈夫曼编码不是唯一的，本题主要的思路为：对于每个选项而言，首先画出二叉树结构图，然后判断其是否满足哈夫曼编码的条件。
   选项A对应的二叉树结构如下图所示。显然，满足哈夫曼编码的条件。
   
   选项B对应的二叉树结构如下图所示。对于这个二叉树而言，第一步选出权值小的两个结点a:4和b:3，其父结点的权值为f1:7，然后从列表里删除结点a和结点b，增加结点f1，结果为{o:12, h:7, i:10, f1:7}；接着再次选出权值较小的两个结点h和f1，构造它们的父结点f2:14，然后从列表里删除结点h与f1，增加新结点f2：{o:12, i:10, f2:14}；接下来应该选权值较小的两个结点o与i。所以，结点o与i肯定是兄弟结点，这个二叉树不满足条件。因此，选项B错误。
   
   同理，对于选项C和选项D可以采用同样的方法进行分析。所以，本题的答案为A。

AB

[考点] 栈和队列

AC

[考点] 二叉树
[解析] 对于选项A，红黑树是每个结点都带有颜色属性的二叉查找树，颜色或红色或黑色。除了具有二叉查找树的一般性质以外，对于任何有效的红黑树，还有如下的额外要求：
   (1)结点是红色或黑色。
   (2)根结点是黑色。
   (3)每个叶子结点(空结点)是黑色的。
   (4)每个红色结点的两个子结点都是黑色(从每个叶子到根的所有路径上不能有两个连续的红色结点)。
   (5)从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
   所以，红黑树是二叉树，选项A正确。
   对于选项B，B树是一种平衡的多叉树。所以，选项B不正确。
   对于选项C，AVL树是平衡二叉树。所以，选项C正确。
   对于选项D，B+树是一种树数据结构，是一个n叉树，每个结点通常有多个孩子，一棵B+树包含根结点、内部结点和叶子结点。根结点可能是一个叶子结点，也可能是一个包含两个或两个以上孩子的结点。所以，选项D不正确。

AB

[考点] 二叉树
[解析] 堆是一种特殊的树形结构，有大顶堆和小顶堆两种。大顶堆(小顶堆)的特点是根结点的值最大(最小)，且根结点的子树也为一个大顶堆(小顶堆)。
   对于选项A，完全二叉树是指除最后一层外，每一层的结点数均达到最大值：在使用的时候堆是采用数组来存储的，因此，它满足完全二叉树的特点。所以，选项A正确。
   对于选项B，平衡二叉树(Balanced Binary Tree)又称为AVL树(有别于AVL算法)，具有以下性质：它是一棵空树或它的左右两个子树的深度差绝对值不超过1，并且左右两棵子树都是一棵平衡二叉树。由于完全二叉树一定满足平衡二叉树的性质，所以，选项B正确。
   对于选项C，排序二叉树有如下性质：
   (1)若左子树不为空，则左子树上所有结点的值均小于它的根结点的值。
   (2)若右子树不为空，则右子树上所有结点的值均大于或等于它的根结点的值。
   (3)左、右子树也分别为二叉排序树。
   (4)没有键值相等的结点。
   显然，堆不满足这个性质。所以，选项C不正确。
   对于选项D，满二叉树是指树中除最后一层无任何子结点外，每一层上的所有结点都有两个子结点的二叉树。满二叉树中结点的个数为1、3、7等特殊的数字，而堆中的结点可以是任意的，因此，不能保证堆是满二叉树。所以，选项D不正确。

AC

[考点] 二叉树
[解析] 根据条件(2)，叶子结点只能在同一层，根据条件(1)，上一层的父结点只能是3个或4个，只能是下图所示的两种结果。
   
   所以，本题的答案为A、C。

ACD

[解析] 下图给出了其中的一种哈夫曼树。
   从下图中的二叉树可以得到字母的哈夫曼编码为：a→10，b→11，c→000，d→001，e→01。在求解哈夫曼编码的时候，由于同一个结点的左右两个孩子的顺序是任意的，因此，哈夫曼编码不是固定的，例如把结点a和结点b的位置交换后，a→11，b→10，但是在任何情况下编码的长度(位数)是固定的。
   
   对于选项A，一个字符的编码最多只占用了3位，而且出现次数越多，编码的长度越短。因此，用编码值来存储可以花费最少的存储空间。所以，选项A正确。
   从上面分析可知，选项B错误，选项C正确。
   对于选项D，编码最长的位数为3，最短的位数为2，显然，字符b的编码是最短的，字符d的编码是最长的。所以，选项D正确。

ABCD

[考点] 逻辑题　数学计算
[解析] 本题中，rand_k函数会随机返回一个[1,k]之间的随机数(k≥2)，并且每个整数出现的概率相等。对于rand_x(x＜7)，可以采取直接截断的方式，即只要rand函数生成的随机数大于x，则直接忽略，重新取值，直至取到小于等于x的数字返回。这样可以保证rand_x能够做到等概率产生随机数。所以，选项A正确。
   对于rand_x(x＞7)，可以采用7×rand_7+rand_7的方式等概率生成。由于rand_7函数产生随机数的范围是[1,7]，所以7×rand_7+rand_7表达式的范围为[8,56]，即可以得到1/49等概率的8～56，只要在产生的时候减7，就可以得到等概率1/49的1～49。当要产生rand_21时，只需要把rand_49截断成rand_42，再统一除以2即可。因此，选项B正确。
   同理可知，选项C与选项D正确。所以，本题的答案为A、B、C和D。

CD

[考点] 排列组合与概率
[解析] 假设“朋友乘火车、轮船、汽车、飞机来”分别为事件a、b、c、d，根据题意，事件a、b、c、d之间是互斥的，且P(a)=0.3，P(b)=0.2，P(c)=0.1，P(d)=0.4，那么他坐各类交通工具不迟到的概率分别是：1-1/4=3/4，1-1/3=2/3，1-1/12=11/12，1-0=1。根据这些条件，可以得出以下结论：
   (1)对于选项A，如果他准点，那么他乘飞机的概率P1=(0.4×1)/(0.3×3/4+0.2×2/3+0.1×11/12+0.4×1)=8/17=0.47，该值比0.5小。所以，选项A错误。
   (2)对于选项B，他乘火车的准点率P2=0.3×3/4=9/40=27/120=0.225，他坐汽车的准点率P3=0.1×11/12=11/120=0.0917，他坐轮船的准点率P4=0.2×2/3=2/15=16/120=0.133，显然，他坐火车或汽车的准点率比坐轮船要高。所以，选项B错误。
   (3)对于选项C，如果他迟到，那么他乘火车的概率P5=(0.3×1/4)/(0.3×1/4+0.2×1/3+0.1×1/12+0.4×0)=0.5。所以，选项C正确。
   (4)对于选项D，如果他准点，那么他乘轮船的概率P6=(0.2×2/3)/(0.3×3/4+0.2×2/3+0.1×11/12+0.4×1)=8/51，他乘汽车的概率P7=(0.1×11/12)/(0.3×3/4+0.2×2/3+0.1×11/12+0.4×1)=11/102，他乘火车的概率P8=(0.3×3/4)/(0.3×3/4+0.2×2/3+0.1×11/12+0.4×1)=9/34。此时，乘轮船或汽车的概率为8/51+11/102=9/34，即等于乘火车的概率。所以，选项D正确。
   因此，本题的答案为C、D。

5

[考点] 二叉树
[解析] 这5种形态如下图所示。
   

12

[考点] 二叉树
[解析] 要使得二叉树的深度最低，那么就需要把二叉树每一层都排满，即排成一个完全二叉树，深度为k的完全二叉树最多有2^k-1个结点。当k=11时，2^k-1=2047＜4000，当k=12时，2^k-1=4095＞4000。因此，树的最低深度为12，且最后一层结点的个数为4000-2017=1983。

53

[解析] 根据哈夫曼树的构造算法得到的这个序列的一个哈夫曼树如下图所示。
   
   树的带权路径长度为树中所有叶子结点的带权路径长度和，这棵树的带权路径长度为：3×3+2×3+5×2+6×2+8×2=53。

1

[考点] 逻辑题　数学计算
[解析] 123456789101112…2014可以被分解为以下形式：1×10^n+2×10^(n-1)+…+2014(①式)。而10^m-1(m为自然数)都可以被9整除，一个能够被9整除的数具有这样一个特点：各个数位上的数字之和能被9整除，可以使用1×9999…9(共n-1个9)+2×9999…9(共n-2个9)+…+2013×9(②式)来表示一个能够整除9的数。用①式减掉②式之后，其余数不变，结果为1+2+…+2014，所以，本题的问题就转换为求1～2014的和除以9得到的余数了，而1+2+…+2014=(1+2014)×2014/2=2029105。不能被9整除的数具有这样一个特点：如果各位数字之和不能被9整除，那么余数就是这个和除以9得到的余数。对于数字2029105而言，2+0+2+9+1+0+5=19；对于19而言，1+9=10；对于10而言，1+0=1，所以，2029105%9=1。因此，123456789101112…2014除以9的余数是1。

DQFXAPBNMYCW

[考点] 排序算法
[解析] 归并排序是利用递归与分治技术将数据序列划分成越来越小的子序列，再对子序列进行排序，最后再用递归法将排好序的子序列合并成越来越大的有序序列。其中，“归”是递归的意思，即递归地将数组折半分割为多个数组，例如数组[2,6,1,0]，会先折半，分为[2,6]和[1,0]两个子数组，然后再折半将数组分割，分为[2]、[6]和[1]、[0]。“并”就是将分开的数组按照从小到大或者从大到小的顺序再放到一个数组中。例如上面的[2]、[6]合并到一个数组中是[2,6]，[1]、[0]合并到一个数组中是[0,1]，然后再将[2,6]和[0,1]合并到一个数组中，即[0,1,2,6]。
   具体而言，二路归并排序算法的原理如下：对于给定的一组记录(假设共有n个记录)，首先将数组中的元素两两分组，得到n/2(向上取整)个长度为2或1的有序子序列，对每个分组中的元素进行排序，再将其两两归并，反复执行此过程，直到得到一个有序序列为止。
   对于本题而言，一次扫描后的结果为：