全国计算机二级考试——数据结构与算法

1、全国计算机二级考试第一章 数据结构与算法1. 一个算法一般都可以用 、 、 三种控制结构组合完成。 解析 顺序、选择（分支） 、循环（重复） 一个算法通常由两种基本要素组成：一是对数据对象的运算和操作，二是 。 解析 算法的控制结构在一般的计算机系统中，有算术运算、逻辑运算、关系运算和 四类基本的操作和运算。 解析 数据传输2. 常用于解决“是否存在”或“有多少种可能”等类型的问题（例如求解不定方程的问题）的算法涉及基本方法是（）A. 列举法 B. 归纳法C.递归法 D. 减半递推法 解析 列举就是列举出所有可能性，将所有可能性统统列举出来，然后解 决问题的方法。所以 A3. 根据提出的问题，

2、列举所有可能的情况，并用问题中给定的条件检验哪 些是需要的，哪些是不需要的，这是算法设计基本方法中的 。 解析 列举法4. 通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计 思想是（）A.列举法 B. 归纳法C.递归法 D.减半递推法 解析 B5. 在用二分法求解方程在一个闭区间的实根时，采用的算法设计技术是 （）A.列举法 B. 归纳法C. 递归法 D. 减半递推法 解析 二分法就是从一半处比较， 减半递推技术也称分治法， 将问题减半。 所以 D6. 将一个复杂的问题归结为若干个简单的问题， 然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为

3、 止，这是算法设计基本方法中的_。如果一个算法 P 显式地调用自己则称为。如果算法P调用另一个算法Q,而算法Q又调用算法P,则称为 . 解析 递归法 直接递归 间接递归调用7. 算法中各操作之间的执行顺序称为 。描述算法的工具通常有 解析 控制结构传统流程图、 N-S 结构化流程图、算法描述语言8. 从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这是算法设计基本方法中的 （ ） 解析 递推法9. 将问题的规模减半，而问题的性质不变，再重复“减半”的过程，这是 算法设计基本方法中的（） 解析 减半递推技术10. 通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐 步试探，

4、 对于每一步的试探， 若试探成功， 就得到问题的解， 若试探失败， 就逐步回退，换别的路线再试探，这是算法设计基本方法中的 解析 回溯法1. 下列叙述中正确的是A. 顺序存储结构的存储一定是连续的， 链式存储结构的存储空间不一定是 连续的B. 顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C. 顺序存储结构能存储有序表，链式存储结构不能存储有序表D. 链式存储结构比顺序存储结构节省存储空间 解析 顺序存储结构中各数据元素在存储空间中是按照逻辑顺序依次连 续存放的，在链式存储结构中元素之间的关系通过指针来连接，所以不要 求存储空间一定是连续的；顺序存储结构（或链式存储结构）既可以针对

5、线性结构，也可以针对非线性结构，但像栈、队列这样的线性结构一般采 用顺序存储结构（但也可以采取链式结构） ；树、二叉树这样的非线性结 构一般采用链式存储结构（但也可以采用顺序存储结构） ；链式存储结构 既可以存储无序表，也可以存储有序表，注意，链式存储结构存储的即使 是有序表，也不能进行二分查找；链式存储结构比顺序存储结构要多使用 存储空间，由于链式存储结构中要用额外空间来保存指针。所以 A顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素 存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系 来体现。而链式存储结构的存储空间不一定是连续的。2. 数据的存储结构是指（）A

6、. 存储在外存中的数据B.数据所占的存储空间量C. 数据在计算机中的顺序存储方式D.数据的逻辑结构在计算机中的表现 解析 数据的逻辑结构是指数据元素之间的逻辑关系的数据结构。数据的 存储结构则是数据的逻辑结构在计算机中的物理实现，有时也称作数据的 物理结构。两者的区别是数据的逻辑结构只涉及到数据之间抽象的数学关 系，存储结构则涉及到如何在计算机中通过对数据的物理存储进行组织来 表达数据元素之间的逻辑关系。比如在线性表的顺序存储中是利用物理存 储空间上的连续性来表达线性表中数据的前后件关系；在线性表的链式存 储中是通过指针域构成的逻辑链条来表达数据的前后件关系。一般的，一 种数据的逻辑机构对应的

7、物理实现，即数据的存储结构不止一种。所以D3. 在长度为n的顺序存储结构的线性表中， 要在第i （1 i n）个元素之 前插入一个新元素，则需要移动表中的（）个元素，表的长度变为（）；若删除表中的第i （1 i rear，队列中有n-front+rear个元素（其中n为循环队歹V的容量）；若front v rear，队歹V中有 real-front个元素；若front=rear队列中有 n 个或 0 个元素。循环队列是线性结构。所以 D6. 在一个容量为 15 的循环队列中，若头指针 front=6 ，尾指针 rear=4 ， 则该循环队列中共有 个元素； 若 front=4 ， rear=6

8、 ，则该循环队列中有个元素； 若 front=6 ， rear=6 ，则该循环队列中共有 个元素。 解析 本题主要考查对循环队列的存储形式和入队运算、出队运算的理 解。求解队列中元素个数的方法是：1. 若 front rear ，队列中有 n-front+rear 个元素（其中 n 为循环队 列的容量）；2. 若 front vrear ，队列中有 real-front 个元素；3. 若 front=rear ，队列中有 n 个或 0 个元素。循环队列是线性结构。所以 13 ； 2； 0 或 151. 下列对于线性链表的描述中正确的是（）A. 存储空间不一定是连续，且各元素的存储顺序是任意的B

9、. 存储空间不一定是连续，且前件元素一定存储在后件元素的前面C. 存储空间必须连续，且前件元素一定存储在后件元素的前面D. 存储空间必须连续，且各元素的存储顺序是任意的 解析 线性链表是通过增加一个指针域来把相邻的数据元素链接成一个 线性序列。线性链表的这种结构使得它存储数据的空间可以是离散的，并 不像顺序表那样一定要求物理上的连续空间。所以 A2. 在线性链表的插入算法中，若要把结点 q插在结点p后面，下列操作正 确的是（）A. 使结点p指向结点q,再使结点q指向结点p的后件结点B. 使结点q指向p的后件结点，再使结点 p指向结点qC. 使结点q指向结点P，再使结点P指向结点q的后件结点D.

10、 使结点p指向q的后件结点，再使结点 q指向结点p 解析 在修改结点指针域的操作中，有一个操作顺序的问题。比较选项A和B只是操作顺序颠倒了一下。 A中先使结点p指向q后，q就称为p新 的后件结点了，原先通过结点 p指向的后件结点与结点 p脱节了那么后面 的一步操作没有任何意义的。使结点 q 指向 p 的后件结点即使结点 q 成为 自己的后件结点。按照 B指定的顺序操作就不会出现引用结点 p的指针域 之前已经把它的值修改了的情形。至于 C和D是命题者设计的干扰项想让考生把p和d的顺序搞混。总结，做这种类型的试题，最好画图。插入结点：若结点 p 的后面是结点 s，要在p和s之间插入结点q, 般先将

11、结点q指向结点s,再讲结点p 指向q，顺序不能颠倒。删除结点：若结点p的后面是结点q，结点q的后面是结点s，若要删除结点q，只需将结点p指向s即可。3. 在长度为 64 的有序线性表中进行顺序查找，最坏情况下需要比较的次 数为（）A63 解析 只要是顺序查找（不管线性表是有序还是无序） ，都是从表头到表 尾逐个比较，若相同则结束查找，否则一直继续比较下一个表中元素，指 导整个表都遍历完。对于长度为 64 的线性表，平均要进行 64/2=321 次比 较，在最坏的情况下要进行 64 次比较。若采用二分（折半）查找，则最 坏情况下需要比较的次数为 log 264=6次，弹药注意采用二分（折半）查找

12、 的条件，必须是线性表采用顺序存储结构，而且线性表中的元素要有序， 这两个条件缺一不可。若对线性链表进行查找，则不管线性链表中的元素 是有序还是无序职能采用顺序查找。因此本题 B.4. 在一个nx m的二维线性表中顺序查找一个数据元素的算法时间复杂度 是（）（n+m） （n x m）（ n2）（m2） 解析 在一维线性表中顺序查找一个数据元素的算法时间复杂度是O（n），其中 n 是线性表的长度，二维线性表的顺序查找方法和一维线性表相似， 只不过是多了一维罢了。在二维表中进行顺序查找有两个方法：一是把二 维线性表看成是n个长度为m的一维线性表，顺序查找就是对这 n个一维线性表依次实施顺序查找，因

13、此它的算法时间复杂度是 （n）x0（ m = O（n x m）;二是直接把 nx m的二维线性看成一个 nx m的一维线 性表，那么在它当中用顺序查找法查找一个元素的算法时间复杂度是O（nx m）。5. 下列叙述中正确的是（）A. 线性链表是线性的链式存储结构B.栈与队列是非线性结构C.双向链表是非线性结构D.只有根结点的二叉树是线性结构 解析 线性表的链式存储结构称为线性链表;栈、队列、双向链表都是线 性结构;树、二叉树（不管它有多少个结点）都是非线性结构。所以A6. 下列关于链表结构的叙述正确的是（）A. 线性链表、带链的栈和带链的队列的结点的结构都是相同的B. 双向链表也就是循环链表C.

14、 线性链表与带链的结点的结构是不同的D. 在循环链表中通过任意一个结点可以找到链表中其他所有的结点，而 在双向链表中做不到这一点 解析 A、C 线性链表、带链的栈和带链的队列：结点（表示数据元素）=数据域（数据元素的映像）+指针域（指示后继元素存储位置）。B、D双向 链表：也叫双链表，是链表的一种，它的每个数据结点中都有两个指针， 分表指向直接后继和直接前驱。循环链表：循环 链表是另一种形式的链式存储结构，它的特点是表中最后一个结点的指针域指向头结点，整个链 表形成一个环。1. 一棵度数为 4 的树，它的 4 度结点有 1个，3 度结点有 2 个， 2度结点 有 3 个， 1 度结点 4 个，

15、问它的叶子结点有多少个？A5 解析 如果注意观察树的结构，你会发现树中的结点数总是比树中的分支 数多，其实也可以这么理解：如果在根结点前面加一条分支线，那么分支 数和结点数就一样多了。在树的结点里， n 度结点可以射出条分支，叶子 结点是 0度结点，因此它射出的分支数为0。此题中指导了 1到 4度结点的个数，就可以计算出树的总分支数：4X 1+3X 2+2X 3+1 X 4=20.因此树的总结点数是 21 ，减去其他读书的结点数 10就得到 0度结点（叶子结点） 的个数 11 了。所以 D2. 在深度为 7 的满二叉树中，叶子结点的个数为（）A32 解析 在满二叉树中每层的结点数都达到最大值，

16、而且叶子结点全部出现在最底层。第1层（根结点所在的层）有20个结点，第2层有21个结点， 第n层有2n-1个结点。在深度为7的满二叉树中，第7层有27-1 =64个结点 （全部是叶子结点） ，在深度为 7 的满二叉树中，共有 27-1=64个结点，本 题为 C3. 某二叉树有 5 个度为 2 的结点，则该项树中的叶子结点数是（）A 10 解析 根据二叉树的性质， 在任意二叉树中， 度为 0 的结点 （即叶子结点） 数总是比度为 2 的结点数多一个。所以 C4. 某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为（）An+12 解析 二叉树具有这样一个性质： 在任意一棵二叉树中， 度为 0

17、的结点（叶 子结点）总是比度为 2 的结点多一个。所以某二叉树中共有 n 个度为 2 的 结点，则该二叉树的叶子结点数为 n+1。所以本题为A5. 一科二叉树中共有 70 个叶子结点和 80个度为 1 的结点， 该二叉树的总 结点数为（）A 219 解析 二叉树具有这样一个性质： 在任意一棵二叉树中， 度为 0 的结点（叶 子结点）总是比度为 2 的结点多一个。本题告知，叶子结点有 70 个，那 度为 2 的结点既有 69 个，度为 1 的结点有 80 个，这颗二叉树共有 70+69+80=219个结点。所以 A6. 在深度为 7的满二叉树中，度为 2 的结点个数为（） 解析 满二叉树的定义是

18、除最后一层外，每一层的所有结点都有两个子结 点（即每一层上的结点数均达到最大值） 。第 1 层（根结点在第 1 层）拥 有的结点数是 20=1，第 2层拥有的结点数是 21=2，第 3层拥有的结点数是 22=4,，第n层拥有的结点数是2n-1。在深度为7的满二叉树中，叶 子结点全部在第 7层，其余结点都是 2 度结点。在满二叉树中，第 7 层拥 有的结点数是 27-1=64。二叉树具有这样一个性质：在任意一棵二叉树中， 度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个，所以度为 2 的 结点个数为 64-1=63 。7. 具有 8 个结点的完全二叉树中编号为4 的结点的右子结点的编号

19、为（）A 8C. 无此结点或 9 解析 设完全二叉树共有 n 个结点，如果从根结点开始，按层序（每一层从左到右）用自然数1, 2,，n给结点进行编号（i=1 , 2,，n）,有 以下结论：1. 若i=1，贝y该结点为根结点，它没有父结点；若 i 1,则该结点的父结 点编号为 i/2 ；其中 i/2 表示取 i/2 的整数部分。2. 若2i n,该结点无左子结点（也无右子结点）；若2i n,该结点无右子结点；若 2i+1 1, 5 和 1 交换位置得到 1, 5, 7, 3, 1, 6, 9, 3, 2, 7, 65V 7不管，继续往后扫描，扫描到 773, 7和 3交换位置得到 1, 5, 3

20、, 7, 1, 6, 9, 3, 2, 7, 67, 6, 9, 3, 2, 7, 66, 7, 9, 3, 2, 7, 671, 7和 1 交换位置得到 1, 5, 3, 1 76, 7和 6交换位置得到 1, 5, 3, 17V 9不管，继续往后扫描，扫描到9 3,9和 3交换位置得到 1,5,3,1,6,7,3,9,2,7,69 2,9和 2交换位置得到 1,5,3,1,6,7,3,2,9,7,69 7,9和 7交换位置得到 1,5,3,1,6,7,3,2,7,9,69 6,9和 6交换位置得到 1,5,3,1,6,7,3,2,7,6,9从前往后扫描结束, 9 交换到了线性表的最后。现在

21、我们来看看对剩下的线性表 1 , 5, 3, 1 , 6, 7, 3, 2, 7, 6, 9从后往前进行扫描的过程6V 7, 6 和 7 交换位置得到 1, 5, 3, 1, 6, 7, 3, 2, 6, 7, 96 2 不管,继续往前扫描,扫描到 22V 3, 2和3交换位置得到 1, 5, 3, 16, 7, 2, 3, 6, 7, 92V 7, 2和7交换位置得到 1, 5, 3, 16, 2, 7, 3, 6, 7, 92V 6, 2和6交换位置得到 1, 5, 3, 12, 6, 7, 3, 6, 7, 92 1 不管,继续往前扫描,扫描到 11v 3, 1 和 3 交换位置得到 1

22、, 5,1,3,2,6,7,3,6,7,91v 5, 1 和 5 交换位置得到 1, 1,5,3,2,6,7,3,6,7,92. 请写出用希尔排序法对序列 5,1,7,3,1,6,9,3,2,7,6进行第一遍扫描后的排序结果是 . 解析 5 , 1 , 3, 2, 1 , 6, 9, 7, 3, 7, 6希尔排序法的基本思想：将整个无序序列分割成若干的子序列分别进行插 入排序（插入排序：开始线性表中只有第 1 个元素,然后从线性表的第 2 个元素开始指导最后一个元素,逐次将其中的每一个元素插入到前面已经 有序的子表中）子序列的分割方法：将相隔某个增量h （ht=n/2k （k=1 , 2, 3

23、-log 2nn为待排序的线性表的长度） ）的元素构成一个子序列。在排序过程中，逐 次减小这个增量，最后当 h 减到 1 时进行一次插入排序，排序完成。按以上分析，第 1 次分割子序列 h=n/2=11/2=5 ，构成的子序列有 5，6、 1，9、7，3、3，2、1，7、6（最后一个元素 6 成单），每一个 序列进行插入排序，结果为 5，6、1，9、7，3、3，2、1，7、 6 （最后一个元素 6 成单），所以第一遍扫描后的结果是 5，1，3，2，1， 6，9，7，3，7，63. 请写出用简单选择排序法对序列5，1，7，3，1 ，6，9，3，2，7，6进行第一遍扫描后的排序结果是 . 解析 1

24、 ， 5 ， 3，2 ，1 ， 6， 9， 7， 3， 7，6扫描整个线性表，从中选择最小的元素，将它交换到表的最前面，对剩下 的子表采用同样的方法，直到子表为空。我们对线性表 5, 1, 7, 3, 1, 6, 9, 3, 2, 7, 6进行第1遍扫描，可以看出元素1最小，将1和第一 个位置上的元素5交换，就得到第1编扫描的结果 1 , 5 , 3, 2, 1, 6,9, 7, 3, 7, 6线性链表1. 下列对于线性链表的描述中正确的是 。（ 2005年4月）2. A.存储空间不一定是连续，且各元素的存储顺序是任意的3. B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面4. C.存储空间必须连续，且前件元素一定存储在后件元素的前面5. D.存储空间必须连续，且各元素的存储顺序是任意的答案A6. 下列叙述中正确的是？。（ 2006年4月）7. A.线性链表是线性表的链式存储结构B.栈与队列是非线性结构8. C.双向链表是非线性结构D.只有根结点的二叉树是线