二级选择题讲义.pdf

计算机二级选择题不要害怕,不要直接放弃!目 标：至 少15 20分1、公共基础10分（不在于理解，在于掌握做题方法+适当的记忆）数据结构与算法（5分）程序设计基础（2分）软件工程基础（2分）数据库设计基础（1分）2、计算机基础知识4分3、Office 6 分6设数据元素的集合D=1,2,3,4,5 ）,则满足下列关系R的数据结构中为线性结构的是R=(1,2),R=(1,3),R=(1,2),R=(1,3),2),(5,1),(4,5)(4,1),(3,2),(5,4)(2,4),(4,5),(2,3)(2,4),(3,5),(1,2)计算机二级公共基础第一章数据结构与算法一、算法算法是指解题方案的准确而完整的迤述算法不等于程序,也不等于计算方法程序的编制不可能优于算法的设计比如：旅游（先规划一再实施）比如：在3,6,8,4,5里面找出最大数编程完成问题：在一无序数据系列中找出最大数（n个数）:算 法：用第一个数和第二数比较，取较大数；用这个较大数和下一个数比，取较大数;经过以上步骤n步，获得最大数程 序：#include void main()(int a4,i,m;scanf(%d,&a0);m=a0;for(i=l;im)m=ai;printf(The max number is%d,m);)2、算法的基本特征(1)可行性。

2)确定性每一条指令的含义明确，无二义性并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出3)有穷性算法必须在有限的时间内完成有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成4)拥有足够的情报3、算法复杂度主要包括时间复杂度和空间复杂度两个之间没有直接联系1)算法时间复杂度是指执行算法所需要的吐 复 建 量，可以用执行算法的过程中所需基本运算的执行次数来度量2)算法空间复杂度是指执行这个算法所需要的内底空回4、设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构基本运算包括：算术运算、逻辑运算、关系运算、数据传输算法的控制结构：顺序结构、选择结构、循环结构练习【1】、算法的有穷性是指（）A）算法程序的运行时间是有限的 B）算法程序所处理的数据量是有限的C）算法程序的长度是有限的 D）算法只能被有限的用户使用正确答案：A【解析】：有穷性是指算法程序的运行时间是有限的2】、算法的空间复杂度是指（）A）算法在执行过程中所需要的计算机存储空间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的临时工作单元数正确答案：A【解析】：算法的空间复杂度是指算法在执行过程中所需要的内存空间。

3、下列关于算法叙述正确的是（）A）算法就是程序B）设计算法时只需要考虑数据结构的设计C）设计算法时只需要考虑结果的可靠性D）以上三种说法都不对正确答案：D【解析】：算法是指解题方案的准确而完整的描述，算法不等于程序，也不等于计算方法，所以A错误设计算法时不仅要考虑对数据对象的运算和操作，还要考虑算法的控制结构4】、下列叙述中正确的是（）A）一个算法的空间复杂度大，则其时间复杂度也必定大B）一个算法的空间复杂度大，则其时间复杂度必定小C）一个算法的时间复杂度大，则其空间复杂度必定小D）算法的时间复杂度与空间复杂度没有直接关系正确答案：D【解析】：算法的空间复杂度是指算法在执行过程中所需要的内存空间，算法的时间复杂度，是指执行算法所需要的计算工作量，两者之间并没有直接关系，答案为D5、下列叙述中正确的是（）A）算法的效率只与问题的规模有关，而与数据的存储结构无关B卜算法时间复杂度是指执行算法所需要的计算工作量C）数据的逻辑结构与存储结构是一一对应的D）算法的时间复杂度与空间复杂度一定相关正确答案：B【解析】：算法的效率与问题的规模和数据的存储结构都有关，A错误算法的时间复杂度，是指执行算法所需要的计算工作量，B正确。

由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同，因此数据的逻辑结构和存储结构不是一一对应的，C错误算法的时间复杂度和空间复杂度没有直接的联系，D错误难度提升:下列叙述中正确的是算法的时间复杂度与算法程序中的语句条数成正比算法的时间复杂度与运行算法时特定的输入有关算法的时间复杂度与算法程序编制者的水平有关算法的时间复杂度与计算机的运行速度有关ID:5648810下列叙述中错误的是对于各种特定的输入，算法的时间复杂度是固定不变的算法的时间复杂度与使用的计算机系统无关算法的时间复杂度与使用的程序设计语言无关算法的时间复杂度与实现算法过程中的具体细节无关，如要查找的数据恰好是人第1个元素，只需比较1次；如要查找的数据是最后一个元素，贝 M个额据需要比较n次2标记二、数据结构1、数据结构的基本概念a、数 据：如声音、视频、文字、图像；学校的学生信息、公安部门的公民信息、银行的存款信息b、数据结构：是指相互有关联的数据元素的集合c、数据结构研究三个方面的问题：逻辑结构：就是各数据元素之间的前后件关系可以理解为图纸上画出来的关系图（线性结构、非线性结构）存储结构：各数据元素在计算机中的存储关系，即数据的存储结构。

数据的存储结构有顺序、链式、索引等对各种数据结构进行的运算：直找、排序、删除、插入等同一种逻辑结构的数据可以采用不同的存储结构，但影响数据处理效率春夏秋冬按顺序在9个房间里面找到9颗龙珠，即可打开大宝藏一、顺序存储 宝藏123456789 10二、链式存储1 2 3 4 5 6 7 8 9 10 11 12 13 14 15数据域 指针域datanextQ）结点结构aaaA三、索引仆）一个非空的线性链表示意图A T 族 T C I I 篇学生信息登记表有一个索引表班级名称学号姓名身份证号出生日期家庭住址1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 1陶欣 5 0 0 1 2 3 4 5 6 7 8 9 0 9 1 9 2 81 9 9 4/1/1 8重庆大足1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 2刘灵 5 1 0 9 8 0 8 7 6 5 2 4 3 5 1 2 3 41 9 9 5/7/1 2重庆梁平1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 3常志明,4 0 0 9 8 7 5 6 2 8 1 9 1 0 1 8 2 81 9 9 1/9/1 7湖北利川1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 4蒋顺 5 1 2 0 1 9 2 8 3 7 4 6 4 5 2 5 4 91 9 9 4/6/7湖北咸丰1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 5张宇澄 5 1 3 9 8 1 7 5 9 1 7 4 7 2 9 3 0 81 9 9 4/7;8重庆永川1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 6赵 小 矛 4 0 9 2 7 1 6 4 8 6 2 3 4 5 0 8 1 21 9 9 4/8/1重庆南川1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 7二惇说下色限5 1 5 1 2 3 4 5 6 7 8 9 8 7 6 5 4 31 9 9 3/6/1重庆垫江1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 8白敏 5 0 3 0 5 4 8 9 7 1 2 3 9 8 7 6 5 11 9 9 4/1 1/1 4重庆酉阳1 3 级旅管12 0 1 3 0 1 0 2 0 0 0 9杨婷婷 5 0 5 9 8 2 7 4 6 5 8 9 2 0 9 7 6 11 9 9 4/1 0/1 3重庆黔江1 3 级旅管12 0 1 3 0 1 0 2 0 0 1 0税正芳 4 1 4 9 8 7 3 6 4 5 7 8 9 0 1 2 8 71 9 9 5/4/1四川泸州1 3 级旅管12 0 1 3 0 1 0 2 0 0 1 1傅茂竹,4 5 6 7 8 9 1 2 3 4 9 8 7 6 5 9 3 21 9 9 4/3/1 0重庆万盛1 3 级旅管12 0 1 3 0 1 0 2 0 0 1 2陈建英 5 0 6 1 2 3 9 8 7 6 5 4 3 2 1 2 1 11 9 9 3/3/2 4重庆石柱栈三、数据结构（逻辑结构）分为两大类型：线性结构和非线性结构。

1）线性结构（非空的数据结构）条件：1）有且只有一个根鲤;（在数据结构中，没有前件的结点称为根结点2）每一个结点最多有一个前件，也最多有一个后件常见的线性结构有线返和线性链表等2）非线性结构：不满足线性结构条件的数据结构常见的非线性结构有树、二叉树和网等1】、下列叙述中正确的是（）A）有一祁上根结点的数据结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构2 8下列叙述中正确的是有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构有且只有一个根结点的数据结构一定是线性结构有且只有一个根结点的数据结构一定是非线性结构每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构四、线性表（逻辑结构）1.1）有且只有一个根结点；2）每一个结点最多有一个前件，也最多有一个后件学生1学生2学生3学生4学生5线性表可能是空表2、存储方式：顺序存储方式和链式存储方式245,9,824598线性表的顺序存储结构具有以下两个基本特点：(1)线性表中所有元素的所占的存储空间是连续的；(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的245,9,82453、线性表的插入、删除，直找(直找某个数和查找最大数、最小数)运算顺序存储、和链式存储24598结 论：1、在插入删除操作里面，顺序存储要移动数据，链式存储不移动数据，链式存储优于顺序存储，顺序存储插入、删除运算不方便。

2、在长度为n的线性表中，查找某个数最坏情况下需要查找n次；3、在长度为n的线性表中，找到最大数（或者最小数）需要比较n-1次 下列关于线性链表的叙述中，正确的是 o进行插入与删除时，不需要移动表中的元素I o各数据结点的存储顺序与逻辑顺序可以不一致，但它们的存储空间必须连续I c各数据结点的存储空间可以不连续，但它们的存储顺序与逻辑顺序必须一致下列叙述巾正确的是线性表链式存储结构的存储空间一般要少于顺序存储结构线性表链式存储结构与顺序存储结构的存储空间都是连续的线性表链式存储结构的存储空间可以是连续的，也可以是不连续的2 8下列叙述中正确的是有且只有一个根结点的数据结构可能是线性结构，也可能是非线性结构o有且只有一个根结点的数据结构一定是非线性结构o有且只有一个根结点的数据结构一定是线性结构o每一个结点最多有一个前件也最多有一个后件的数据结构一定是线性结构4 1下列叙述中正确的是顺序存储结构能存储有序表，链式存储结构不能存储有序表O链式存储结构比顺序存储结构节省存储空间顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的O顺序存储结构只针时线性结构，锌式存储结构只针时非线性结构2线性表的长度为n。

在最坏情况下，比较次数为n-l的算法是寻找最大项O有序表的插入O同时寻找最大项与最小项O顺序查找5性表的链式存储结构中，其存储空间一般是不连续的，并且前件结点的存储序号小于后件结点的存储序号前件结点的存储序号可以小于也可以大于后件结点的存储序号前件结点的存储序号大于后件结点的存储序号答案:B ID:56405t解析】链式存储结构使 人得节点在内存中不受位置的限制，结点存储号可以是任意的，并且能够保证逻辑上的线性关系故前标记五、栈定义：栈是限定在一端进行插入与删除运算的线性表栈是线性结构）在栈中，允许插入与删除的一端称为栈顶（top）-移动的，变化的，不允许插入与删除的另一端称为栈底（bottom）（栈底固定不变）栈是按照 先进后出或“后进先出的原则组织数据的正栈1、2、3、4、把2,3,1,5,6,8入。