vfp无纸化真考题33答题.doc

无纸化真考题试题三十三(2015.9) 1. 下列叙述中正确的是 A) 数据的存储结构会影响算法的效率 B) 算法设计只需考虑结果的可靠性 C) 算法复杂度是指算法控制结构的复杂程度 D) 算法复杂度是用算法中指令的条数来度量的 参考答案：A 【解析】算法的基本特征包括可行性、确定性、有穷性、足够的初始信息，算法的设计必须考虑到算法的复杂度，B选项错误。算法的复杂度是指该算法所需要的计算机资源的多少，即时间和空间的资源，分为时间复杂度和空间复杂度。算法控制结构在具体实现中影响程序执行时间，与算法复杂度无关，C选项错误。算法的时间复杂度是用算法所执行的基本运算次数来度量的，而不是算法中指令的条数，D选项错误。数据的存储结构与算法的复杂度有关，会影响算法的效率。A选项正确。 2. 设数据集合为D={ 1, 2, 3, 4, 5 }。下列数据结构 B=(D, R)中为非线性结构的是 A) R={ (1,2), (2,3), (3,4), (4,5) } B) R={ (1,2), (2,3), (4,3), (3,5) } C) R={ (5,4), (4,3), (3,2), (2,1) } D) R={ (2,5), (5,4), (3,2), (4,3) } 参考答案：B 【解析】一个非空的数据结构如果满足以下两个条件：有且只有一个根结点；每一个结点最多有一个前件，也最多有一个后件，称为线性结构。不同时满足以上两个条件的数据结构就称为非线性结构。B选项中，由(2,3) 、(4,3)可知，结点3有两个前件2和4，为非线性结构，故选择B选项。 3. 某二叉树共有150个结点，其中有50个度为1的结点，则 A) 不存在这样的二叉树 B) 该二叉树有49个叶子结点 C) 该二叉树有50个叶子结点 D) 该二叉树有51个叶子结点 参考答案：A 【解析】在树结构中，一个结点所拥有的后件个数称为该结点的度。对任何一棵二叉树，度为0的结点（即叶子结点）总是比度为2的结点多一个。二叉树中有150个结点，设叶子结点个数为n0，度为1的结点个数为50，设度为2的结点个数为n2。150=n0+50+n2且n0=n2+1，则n0=50.5，n2=49.5。由于结点个数必须是整数，所以不存在这样的二叉树，故选择A选项。 4. 循环队列的存储空间为 Q(1:50)，初始状态为front=rear=50。经过一系列正常的入队与退队操作后，front=rear=25，此后又正常地插入了一个元素，则循环队列中的元素个数为 A) 51 B) 50 C) 46 D) 1 参考答案：D 【解析】循环队列是队列的一种顺序存储结构，用队尾指针rear指向队列中的队尾元素，用排头指针front指向排头元素的前一个位置。入队运算时，队尾指针进1（即rear+1），然后在rear指针指向的位置插入新元素。当front=rear=25时可知队列空或者队列满，此后又正常地插入了一个元素说明之前队列为空，所以插入操作之后队列里只有一个元素。D选项正确。 5. 下列排序方法中，最坏情况下时间复杂度（即比较次数）低于O(n2)的是 A) 快速排序 B) 简单插入排序 C) 冒泡排序 D) 堆排序 参考答案：D 【解析】对长度为n的线性表排序，下表为常用排序方法最坏情况的时间复杂度： 方法最坏情况时间冒泡排序O(n2)简单插入排序O(n2)简单选择排序O(n2)快速排序O(n2)堆排序O(nlog2n)时间复杂度低于O(n2)的排序算法是堆排序，D选项正确。 6. 下面描述正确的是 A) 软件测试是指动态测试 B) 软件测试可以随机地选取测试数据 C) 软件测试是保证软件质量的重要手段 D) 软件测试的目的是发现和改正错误 参考答案：C 【解析】软件测试有多种方法，根据软件是否需要被执行，可以分为静态测试和动态测试，A选项叙述错误。软件测试应在测试之前制定测试计划，并严格执行，排除测试随意性，并且需要设计正确的测试用例，B选项叙述错误。软件测试就是在软件投入运行之前，尽可能多地发现软件中的错误，改正错误是调试的过程，D选项叙述错误。软件测试是保证软件质量的重要手段，C选项正确。 7. 下面图中属于软件设计建模工具的是 A) DFD图(数据流程图) B) 程序流程图（PFD图） C) 用例图 （USE_CASE图） D) 网络工程图 参考答案：B 【解析】结构化分析方法的常用工具：数据流程图（DFD）、数据字典（DD）、判定表、判定树。常用的过程设计建模工具如下所述：图形工具（PFD图、N-S图、PAD图、HIPO）、表格工具（判定表）、