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

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

2、中的解析列举法A.列举法B.归纳法C.递归法D.减半递推法4.通过列举少量的特殊情况，经过分析，最后找出一般的关系的算法设计思想是（）解析 B解析二分法就是从一半处比较， 减半递推技术也称分治法， 将问题减半。所以D6.将一个复杂的问题归结为若干个简单的问题， 然后将这些较简单的问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为称为_ 。如果算法P调用另一个算法Q,而算法Q又调用算法P,则称解析递归法 直接递归 间接递归调用解析控制结构传统流程图、N-S结构化流程图、算法描述语言A.列举法B.归纳法C.递归法D.减半递推法5.在用二分法求解方程在一个闭区间的实根时，采用的算法

3、设计技术是 （）A.列举法B.归纳法C.递归法D.减半递推法止，这是算法设计基本方法中的。如果一个算法P显式地调用自己则7.算法中各操作之间的执行顺序称为。描述算法的工具通常有8.从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这是算法设计基本方法中的（ ） 解析递推法9.将问题的规模减半，而问题的性质不变，再重复“减半”的过程，这是 算法设计基本方法中的（）解析减半递推技术10.通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐 步试探，对于每一步的试探， 若试探成功， 就得到问题的解， 若试探失败， 就逐步回退，换别的路线再试探，这是算法设计基本方法中的解析回溯法1.

4、下列叙述中正确的是A.顺序存储结构的存储一定是连续的， 链式存储结构的存储空间不一定是 连续的B.顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C.顺序存储结构能存储有序表，链式存储结构不能存储有序表D.链式存储结构比顺序存储结构节省存储空间解析顺序存储结构中各数据元素在存储空间中是按照逻辑顺序依次连 续存放的，在链式存储结构中元素之间的关系通过指针来连接， 所以不要 求存储空间一定是连续的； 顺序存储结构 （或链式存储结构）既可以针对 线性结构，也可以针对非线性结构，但像栈、队列这样的线性结构一般采 用顺序存储结构（但也可以采取链式结构） ；树、二叉树这样的非线性结构一般采用链式存

5、储结构（但也可以采用顺序存储结构） ；链式存储结构 既可以存储无序表，也可以存储有序表，注意，链式存储结构存储的即使 是有序表，也不能进行二分查找；链式存储结构比顺序存储结构要多使用 存储空间，由于链式存储结构中要用额外空间来保存指针。所以顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素 存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系 来体现。而链式存储结构的存储空间不一定是连续的2.数据的存储结构是指（）间量在计算机中的表现解析数据的逻辑结构是指数据元素之间的逻辑关系的数据结构。数据的 存储结构则是数据的逻辑结构在计算机中的物理实现， 有时也称作数据的 物理结构

6、。两者的区别是数据的逻辑结构只涉及到数据之间抽象的数学关 系，存储结构则涉及到如何在计算机中通过对数据的物理存储进行组织来表达数据元素之间的逻辑关系。比如在线性表的顺序存储中是利用物理存 储空间上的连续性来表达线性表中数据的前后件关系；在线性表的链式存 储中是通过指针域构成的逻辑链条来表达数据的前后件关系。一般的，一 种数据的逻辑机构对应的物理实现，即数据的存储结构不止一种。所以3.在长度为n的顺序存储结构的线性表中， 要在第i（1in）个元素之 前插入一个新元素，则需要移动表中的（）个元素，表的长度变为（） ； 若删除表中的第i（1irear，队列中有n-front+rear个元素（其中n为

7、循环队 歹y的容量）；若front V rear，队歹U中有real-front个元素；若front=rear，队列中有n个或0个元素。循环队列是线性结构6.在一个容量为15的循环队列中，若头指针 则该循环队列中共有 _ 个元素； 若front=4有_个元素； 若front=6，rear=6，则该循环队列中共有解析本题主要考查对循环队列的存储形式和入队运算、出队运算的理 解。求解队列中元素个数的方法是：若frontrear，队列中有n-front+rear个元素（其中n为循环队列的容量）； 若front Vrear，队列中有real-front个元素； 若front=rear，队列中有n个或0

8、个元素。循环队列是线性结构。所以13；2；0或15所以Dfront=6，尾指针rear=4，rear=6，则该循环队列中个元素。1.2.3.1.下列对于线性链表的描述中正确的是（）A.存储空间不一定是连续，且各元素的存储顺序是任意的B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的解析线性链表是通过增加一个指针域来把相邻的数据元素链接成一个 线性序列。线性链表的这种结构使得它存储数据的空间可以是离散的，并 不像顺序表那样一定要求物理上的连续空间。所以A2.在线性链表的插入算法中，

9、若要把结点q插在结点P后面，下列操作正确的是（）p指向结点q，再使结点q指向结点p的后件结点q指向p的后件结点，再使结点p指向结点q解析在修改结点指针域的操作中，有一个操作顺序的问题。比较选项和B只是操作顺序颠倒了一下。A中先使结点P指向q后，q就称为p新 的后件结点了，原先通过结点P指向的后件结点与结点P脱节了那么后面 的一步操作没有任何意义的。使结点q指向P的后件结点即使结点q成为 自己的后件结点。按照B指定的顺序操作就不会出现引用结点P的指针域 之前已经把它的值A.使结点B.使结点C.使结点q指向结点P,再使结点P指向结点q的后件结点D.使结点P指向q的后件结点，再使结点q指向结点P修改

10、了的情形。至于C和D是命题者设计的干扰项想让考生把p和d的顺序搞混。总结,做这种类型的试题,最好画图。插入结点：若结点s，要在P和s之间插入结点q, 一般先将结点 指向q,顺序不能颠倒。删除结点：若结点的后面是结点s，若要删除结点q,只需将结点3.在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次 数为（）A63 解析只要是顺序查找（不管线性表是有序还是无序） ，都是从表头到表 尾逐个比较，若相同则结束查找，否则一直继续比较下一个表中元素，指 导整个表都遍历完。对于长度为64的线性表，平均要进行64/2=321次比 较，在最坏的情况下要进行64次比较。若采用二分（折半）查找，则最

11、坏情况下需要比较的次数为log264=6次，弹药注意采用二分（折半）查找 的条件，必须是线性表采用顺序存储结构，而且线性表中的元素要有序， 这两个条件缺一不可。若对线性链表进行查找，则不管线性链表中的元素 是有序还是无序职能采用顺序查找。因此本题B.4.在一个nx m的二维线性表中顺序查找一个数据元素的算法时间复杂度是（）解析在一维线性表中顺序查找一个数据元素的算法时间复杂度是O（n），其中n是线性表的长度，二维线性表的顺序查找方法和一维线性表相似， 只不过是多了一维罢了。在二维表中进行顺序查找有两个方法：一是把二维线性表看成是n个长度为m的一维线性表，顺序查找就是对这n个一维p的后面是结点q

12、指向结点s，再讲结点pP的后面是结点q,结点q p指向s即可。(n+m) (nx m)线性表依次实施顺序查找， 因此它的算法时间复杂度是O（n）0（ m = 0（n Xm）;二是直接把nx m的二维线性看成一个nX m的一维线性表，那么在它当中用顺序查找法查找一个元素的算法时间复杂度是X m)。5.下列叙述中正确的是（）性结构叉树是线性结构解析线性表的链式存储结构称为线性链表；栈、队列、双向链表都是线 性结构；树、二叉树（不管它有多少个结点）都是非线性结构。所以6.下列关于链表结构的叙述正确的是（）A.线性链表、带链的栈和带链的队列的结点的结构都是相同的B.双向链表也就是循环链表C.线性链表与

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

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

15、）有20个结点，第2层有21个结点， 第n层有2n-1个结点。在深度为7的满二叉树中，第7层有27-1=64个结点 （全部是叶子结点） ，在深度为7的满二叉树中，共有27-1=64个结点，本题为C3.某二叉树有5个度为2的结点，则该项树中的叶子结点数是（）A10解析根据二叉树的性质， 在任意二叉树中， 度为0的结点（即叶子结点） 数总是比度为2的结点数多一个。所以C4.某二叉树中有n个度为2的结点，则该二叉树中的叶子结点为（）分表指向直接后继和直接前驱。循环链表：循环链表是另一种形式的链An+1 解析二叉树具有这样一个性质： 在任意一棵二叉树中， 度为0的结点（叶 子结点）总是比度为2的结点多

16、一个。所以某二叉树中共有n个度为2的 结点，则该二叉树的叶子结点数为n+1。所以本题为A5.一科二叉树中共有70个叶子结点和80个度为1的结点， 该二叉树的总 结点数为（）A219 解析二叉树具有这样一个性质： 在任意一棵二叉树中， 度为0的结点（叶 子结点）总是比度为2的结点多一个。本题告知，叶子结点有70个，那度为2的结点既有69个，度为1的结点有80个，这颗二叉树共有70+69+80=219个结点。所以A6.在深度为7的满二叉树中，度为2的结点个数为（）解析满二叉树的定义是除最后一层外，每一层的所有结点都有两个子结 点（即每一层上的结点数均达到最大值） 。第1层（根结点在第1层）拥 有的

17、结点数是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的结点的右子结点的编号为（）A8C.无此结点或9解析设完全二叉树共有n个结点，如果从根结点幵始，按层序（每一层 从左到右）用自然数1，2,，n给结点进行编号（i=1,2,，n）,有 以下结论：

18、1.若i=1，贝y该结点为根结点，它没有父结点；若i1,则该结点的父结 点编号为i/2；其中i/2表示取i/2的整数部分。2.若2in该结点无左子结点（也无右子结点）；若2in,该结点无右子结点;子结点编号为2i+1。若2i+11不管,继续往前扫描,扫描到151,5和1交换位置得到1,5,7,3，9,3,2,7,65V 7不管，继续往后扫描，扫描到73，7和3交换位置得到1，5，3，7，1，6，9，3，2，7，671，7和1交换位置得到1，5，3，1，7，6，9，3，2，7，676，7和6交换位置得到1，5，3，1，6，7，9，3，2，7，67V 9不管，继续往后扫描，扫描到93，9和3交换位

19、置得到1，5，3，1，6，7，3，9，2，7，692，9和2交换位置得到1，5，3，1，6，7，3，2，9，7，697，9和7交换位置得到1，5，3，1，6，7，3，2，7，9，696，9和6交换位置得到1，5，3，1，6，7，3，2，7，6，9从前往后扫描结束,9交换到了线性表的最后。现在我们来看看对剩下的线性表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，962不管，继续往前扫描，扫描到2V 3，2和3交换位置得到1,5,3，1，6，7，2，3，6，7，92V 7,2和7交换位置得到1,5,3,1,6,2

20、,7,3,6,7,92V 6,2和6交换位置得到1,5,3,1,2,6,7,3,6,7,921不管,继续往前扫描,扫描到1行第一遍扫描后的排序结果是希尔排序法的基本思想：将整个无序序列分割成若干的子序列分别进行插 入排序（插入排序：开始线性表中只有第1个元素,然后从线性表的第2个元素开始指导最后一个元素,逐次将其中的每一个元素插入到前面已经 有序的子表中）子序列的分割方法：将相隔某个增量h（ht=n/2k（k=1,2,3-log2nn为待排序的线性表的长度） ）的元素构成一个子序列。在排序过程中，逐 次减小这个增量,最后当h减到1，9、7，3、3，2 、1，序列进行插入排序，结果为5，6（最后

21、一个元素6成单），所以第一遍扫描后的结果是5，1，3，2，1，6，9，7，3，7，63.请写出用简单选择排序法对序列5，1，7，3，1，6，9，3，2，7，6进行第一遍扫描后的排序结果是解析 1，5，3，2，1，6，9，7，3，7，6扫描整个线性表，从中选择最小的元素，将它交换到表的最前面，对剩下13,1和3交换位置得到1，5，1，3，2，6，7，3，6，7，915，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，61时进行一次插入排序,排序完成。按以上分析，第1次分

22、割子序列h=n/2=11/2=5，构成的子序列有5，6、7、6（最后一个元素6成单），每一个6、1，9、7，3、3，2、1，7、9,7,3,7,6线性链表A.存储空间不一定是连续，且各元素的存储顺序是任意的B.存储空间不一定是连续，且前件元素一定存储在后件元素的前面C.存储空间必须连续，且前件元素一定存储在后件元素的前面D.存储空间必须连续，且各元素的存储顺序是任意的答案A线性结构答案A年9月） 答案线性结构的子表采用同样的方法，直到子表为空。我们对线性表5,1, 乙3,1,6,9,3,2,7,6进行第1遍扫描，可以看出元素1最小,1和第一个位置上的元素5交换，就得到第1编扫描的结果 1,5,3,2,1,6,1.下列对于线性链表的描述中正确的是。（2005年4月）2.下列叙述中正确的是？.。（2006年4月）A.线性链表是线性表的链式存储结构B.栈与队列是非线性结构