全国计算机二级公共基础知识考题分析培训教材.ppt

全国计算机等级考试二级公共基础知识
第一章 数据结构和算法
第二章 程序设计基础
第三章 软件工程基础
第四章 数据库设计基础
第一章 数据
【答案】移动队头指针
【解析】根据队列的特点，删除元素是在队头进行的操作，因此，首先取出并保存队头元素，然后移动队头指针，使移动后的指针成为新的队头指针。
页7
【例13】可以用带表头结点的链表表示线性表，也可用不带表头结点的链表表示的线性表，前者最主要的好处是（ ）。
A）可以加快对表的遍历
B）使空表和非空表的处理统一
C）节省存储空间
D）可以提高存取表元素的速度
【答案】 B）
【解析】用带头结点的链表表示线性表时，空表和非空表的插入、删除是相同的。当往空链表插入时，只要把待插入元素的指针域指向头结点的指针域，把头结点的指针域指向新增元素即可，当往非空链表插入元素时只要找到插入的位置，执行同样的操作即可完成插入。当链表只有一个元素时，删除操作只要修改指针指向下一个元素的指针所指的元素即可，跟一般的链表删除操作是一样的。

【例14】在双向链表中，每个结点有两个指针域，一个指向前驱结点，另一个指向＿＿＿＿＿。
【答案】 后继结点
【解析】根据双向链表的数据结构可知，双向链表每个结点有两个指针域，这两个指针分别指向它的前驱结点和后继结点。
页8
【例15】有关二叉树的下列说法正确的是（）。
A）二叉树的度为2
B)一棵二叉树的度可以小于2
C）二叉树中任何一个结点的度都为2
D）任何一棵二叉树中至少有一个结点的度为2
【答案】B）
【解析】根据二叉树的一些概念，不难得知A）选项、C）选项和D）选项均为错误答案。
【例16】设深度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为（）。
A）2h
B）2h－1
C）2h+1
D）h+1
【答案】B）
【解析】结点最少的情况，除根结点层只有1个结点外，其余h-1层均有两个结点，结点总数＝2(h－1)+1=2h－1。
页9
【例17】某二叉树的先序和后序遍历序列正好相反，则该二叉树一定是（）。
A）空或只有一个结点
B）完全二叉树
C）二叉排序树
D）深度等于其结点数
【答案】D）
【解析】对于深度等于结点数的二叉树，每层只有一个结点，假设从上向下分别为a1，a2，…，an，则先序遍历序列为a1，a2，…，an。后序遍历为an，an-1，…，a1。本题答案为D）选项 。
【例18】已知某二叉树的后序遍历序列是DACBE，中序遍历序列是DEBAC，则它的前序遍历序列是（ ）。
A）ACBED
B）DEABC
C）DECAB
D）EDBAC
【答案】D）
【解析】根据各种遍历算法，不难得出前序遍历序列是EDBAC。
页10
【例19】如下图二叉树的遍历，其中序遍历序列为＿＿＿＿＿；先序遍历序列为＿＿＿＿＿；后序遍历序列为＿＿＿＿＿。
【答案】DGBAECHIF ABDGCEFHI GDBEIHFCA
【解析】中序遍历：若二叉树为空，则空操作；否则
（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
先序遍历：若二叉树为空，则空操作；否则
（1）访问根结点；（2）前序遍历左子树；（3）前序遍历右子树。
后序遍历：若二叉树为空，则空操作；否则
（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
B
C
D
G
E
F
H
I
A
页11
【例20】有一棵树如右图所示，回答下面的问题：
（1）这棵树的根结点是＿＿＿＿＿。
（2）这棵树的叶子结点是＿＿＿＿＿。
（3）结点k3的度是＿＿＿＿＿。
（4）这棵树的度为＿＿＿＿＿。
（5）这棵树的深度是＿＿＿＿＿。
（6）结点k3的孩子结点是＿＿＿＿＿。
（7）结点k3的双亲结点是＿＿＿＿＿。
【答案】①k1；②k2，k5，k7，k4；③2；④3；⑤4；⑥k5，k6；⑦k1
【解析】树是由n（n≥0）个结点组成的有限集合。若n=0，称为空树；若n>0，则：（1）有一个特定的称为根（root）的结点。它只有直接后件，但没有直接前件；（2）除根结点以外的其它结点可以划分为m（m≥0）个互不相交的有限集合T0，T1，…，Tm－1，每个集合Ti（i=0，1，…，m－1）又是一棵树，称为根的子树，每棵子树的根结点有且仅有一个直接前