计算机等级考试二级公共基础知识辅导课件.ppt

《计算机等级考试二级公共基础知识辅导课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国计算机等级考试二级公共基础知识第一章数据结构和算法第二章程序设计基础第三章软件工程基础第四章数据库设计基础第一章数据结构和算法算法算法的基本概念算法复杂度数据结构的基本概念数据结构及图形表示线性结构与非线性结构线性表及其顺序存储结构线性表的基本概念顺序表的插入运算及删除运算线性表的顺序存储结构栈和队列栈及其基本运算队列及其基本运算线性链表线性链表的基本概念循环链表及其基本运算线性链表的基本运算树与二叉树树的基本概念二叉树的存储结构及遍历二叉树及其基本性质查找技术顺序查找二分查找法交换类排序选择类排序插入类排序排序技术【例1】算法的时间复杂度取决于（）。A）问题的规模B）待处理

2、的数据的初态C）问题的难度D）A）和B）【答案】D）【解析】在同一问题规模下，算法的时间复杂度不仅与问题的规模有关，与输入数据也有关，即输入数据所有的可能取值范围及输入各种数据或数据集的概率有关。【例2】通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论的算法设计方法是＿＿＿＿＿。【答案】归纳法【解析】归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。页1页2【例3】如果算法P调用另一个算法Q，而算法Q又调用算法

3、P，则称为＿＿＿＿。【答案】间接递归调用【解析】如果一个算法显式地调用自己则称为直接递归，如果通过另一算法调用自己为间接递归调用。【例4】在数据结构中，从逻辑上可以把数据结构分成()。A）内部结构和外部结构B）线性结构和非线性结构C）紧凑结构和非紧凑结构D）动态结构和静态结构【答案】B）【解析】逻辑结构反映数据元素之间的逻辑关系，线性结构表示数据元素之间为一对一的关系，非线性结构表示数据元素之间为一对多或者多对一的关系。页3【例5】线性结构中元素之间存在着＿＿＿＿＿关系，而树型结构中元素之间存在着一对多关系。【答案】一对一【解析】线性结构主要是指元素之间的一对一的关系，而树型结构是指

4、元素之间一对多的关系。【例6】对数据结构的两种基本运算是（）。A）插入和查找B）分类和分解C）插入和删除D）复制和修改【答案】C）【解析】一个数据结构中的元素结点可能是在动态地变化的。根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（称为插入运算），也可以删除数据结构中的某个结点（称为删除运算）。插入和删除是对数据结构的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改等。页4【例7】对线性表，在下列（）情况下应当采用链表表示。A)经常需要随机地存取元素B)经常需要进行插入和删除操作C)表中元素需要占据一片连续的存储空间D)表中元素的个数不变【答

5、案】B）【解析】由于链表不是顺序存储的，即当进行插入和删除操作时不需要进行移动大量的元素，所以当一些需要经常进行插入和删除操作的情况应当采用链表的方式存储。【例8】对于长度为ｎ的顺序存储的线性表，当随机插入和删除一个元素时，需平均移动元素的个数为＿＿＿＿＿。【答案】n／2【解析】删除一个元素，平均移动的元素的个数为（n－1+n－2+……+0）/n=(n－1)/2；插入一个元素，平均移动元素个数为（n+n－1+n－2+……+1）/n=(n+1)/2，所以总体移动元素个数为n/2。页5【例9】设初始输入序列为1，2，3，4，5，利用一个栈产生输出序列，下列（）序列是不可能通过栈产生的。A

6、）1，2，3，4，5B）5，3，4，1，2C）4，3，2，1，5D）3，4，5，2，1【答案】B）【解析】由于栈的压入和退出只能在栈顶进行，所以要使出栈的第一个数是序列的最后一个数5，只能先把序列所有元素都压入栈，但这时出栈序列只能是5，4，3，2，1，所以B）选项的出栈序列是错误的。【例10】判断一个栈ST（最多元素为MaxSize）为空的条件是（）。A）STtop!=－1B）STtop=－1C）STtop!=MaxSize－1D）STtop=MaxSize－1【答案】B）【解析】由顺序栈的结构可知，本题答案为B）。页6【例11】一个队列的入队序列是１，２，３，４，则队列的

7、输出序列是（）。A）１，４，３，２B）３，２，４，１C）４，３，２，１D）１，２，３，４【答案】D）【解析】由队列的先进先出的特点可以知道，入队序列是１，２，３，４，出队序列只能是１，２，３，４．所以答案为D）。【例12】从一个循环队列中删除一个元素，通常的操作是先取出元素，然后＿＿＿＿＿。【答案】移动队头指针【解析】根据队列的特点，删除元素是在队头进行的操作，因此，首先取出并保存队头元素，然后移动队头指针，使移动后的指针成为新的队头指针。页7【例13】可