2016年全国计算机二级考试——第一章数据结构与算法.doc

《2016年全国计算机二级考试——第一章数据结构与算法.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

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

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

3、题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止，这是算法设计基本方法中的___。如果一个算法P显式地调用自己则称为___。如果算法P调用另一个算法Q,而算法Q又调用算法P，则称为_____.[解析]递归法直接递归间接递归调用7.算法中各操作之间的执行顺序称为_____。描述算法的工具通常有_____、_____、_____。[解析]控制结构传统流程图、N-S结构化流程图、算法描述语言8.从已知的初始条件出发，逐步推出所要求的各中间结果和最后结果，这是算法设计基本方法中的()[解析]递推法9.将问题的规模减半，而问题的性质不变，再重复“减

4、半”的过程，这是算法设计基本方法中的（）[解析]减半递推技术10.通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再试探，这是算法设计基本方法中的[解析]回溯法1.下列叙述中正确的是A.顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的B．顺序存储结构只针对线性结构，链式存储结构只针对非线性结构C．顺序存储结构能存储有序表，链式存储结构不能存储有序表D．链式存储结构比顺序存储结构节省存储空间[解析]顺序存储结构中各数据元素在存储空间中是按照逻

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

6、相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。2.数据的存储结构是指（）A．存储在外存中的数据B.数据所占的存储空间量C.数据在计算机中的顺序存储方式D.数据的逻辑结构在计算机中的表现[解析]数据的逻辑结构是指数据元素之间的逻辑关系的数据结构。数据的存储结构则是数据的逻辑结构在计算机中的物理实现，有时也称作数据的物理结构。两者的区别是数据的逻辑结构只涉及到数据之间抽象的数学关系，存储结构则涉及到如何在计算机中通过对数据的物理存储进行组织来表达数据元素之间的逻辑关系。比如在线性表的

7、顺序存储中是利用物理存储空间上的连续性来表达线性表中数据的前后件关系；在线性表的链式存储中是通过指针域构成的逻辑链条来表达数据的前后件关系。一般的，一种数据的逻辑机构对应的物理实现，即数据的存储结构不止一种。所以D3.在长度为n的顺序存储结构的线性表中，要在第i（1≤i≤n）个元素之前插入一个新元素，则需要移动表中的（）个元素，表的长度变为（）；若删除表中的第i（1≤i≤n）个元素，则需要移动表中的（）个元素，表的长度变为（）。[解析]n-i+1；n+1；n-i；n-14.一个栈的初始状态为空。现将元素1、2、3、4、5、A、B、C、D、E依次入栈，然后再依

8、次出栈，则元素出栈的顺序是（）A．12345ABCD