全国计算机二级公共基础知识考题分析.ppt

全国计算机等级考试二级公共基础知识第一章数据结构和算法第二章程序设计基础第三章软件工程基础第四章数据库设计基础伞耀较徒坐貌厢谎瘩捕挖佩曼肃邓窿窘煮瓢邦宪遭筛醉遂莎苞尝卢誓啸酚全国计算机二级公共基础知识考题分析全国计算机二级公共基础知识考题分析第一章数据结构和算法算法算法的基本概念算法复杂度数据结构的基本概念数据结构及图形表示线性结构与非线性结构线性表及其顺序存储结构线性表的基本概念顺序表的插入运算及删除运算线性表的顺序存储结构栈和队列栈及其基本运算队列及其基本运算线性链表线性链表的基本概念循环链表及其基本运算线性链表的基本运算树与二叉树树的基本概念二叉树的存储结构及遍历二叉树及其基本性质查找技术顺序查找二分查找法交换类排序选择类排序插入类排序排序技术畔邢倘争迅莲孙吵组捉屑着根朗妮版履懂廖岛意艰凝捷碧傀柴凸那婚把脸全国计算机二级公共基础知识考题分析全国计算机二级公共基础知识考题分析【例1】算法的时间复杂度取决于()。A)问题的规模 B)待处理的数据的初态C)问题的难度 D)A)和B)【答案】 D)【解析】在同一问题规模下,算法的时间复杂度不仅与问题的规模有关,与输入数据也有关,即输入数据所有的可能取值范围及输入各种数据或数据集的概率有关。【例2】通过列举少量的特殊情况,经过分析,最后找出一般的关系。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论的算法设计方法是_____。【答案】 归纳法【解析】归纳法的基本思想是,通过列举少量的特殊情况,经过分析,最后找出一般的关系。从本质上讲,归纳就是通过观察一些简单而特殊的情况,最后总结出一般性的结论。页1广式所涡虽陋值佣辱昆孩寿属散该豪韩捻剑蜘蓑剂扣唤摩陡磁斩饱孰艰季全国计算机二级公共基础知识考题分析全国计算机二级公共基础知识考题分析页2【例3】如果算法P调用另一个算法Q,而算法Q又调用算法P,则称为____。【答案】间接递归调用【解析】如果一个算法显式地调用自己则称为直接递归,如果通过另一算法调用自己为间接递归调用。【例4】在数据结构中,从逻辑上可以把数据结构分成()。A)内部结构和外部结构B)线性结构和非线性结构C)紧凑结构和非紧凑结构 D)动态结构和静态结构【答案】 B)【解析】逻辑结构反映数据元素之间的逻辑关系,线性结构表示数据元素之间为一对一的关系,非线性结构表示数据元素之间为一对多或者多对一的关系。颅疡拴迂暇九炭福瓤卯浮贵芳霞颈硒啤痈仙壬墩蚂坝拟熊服函刺喳饲假观全国计算机二级公共基础知识考题分析全国计算机二级公共基础知识考题分析页3【例5】线性结构中元素之间存在着_____关系,而树型结构中元素之间存在着一对多关系。【答案】 一对一【解析】线性结构主要是指元素之间的一对一的关系,而树型结构是指元素之间一对多的关系。【例6】对数据结构的两种基本运算是()。A)插入和查找 B)分类和分解 C)插入和删除 D)复制和修改【答案】 C)【解析】一个数据结构中的元素结点可能是在动态地变化的。根据需要或在处理过程中,可以在一个数据结构中增加一个新结点(称为插入运算),也可以删除数据结构中的某个结点(称为删除运算)。插入和删除是对数据结构的两种基本运算。除此之外,对数据结构的运算还有查找、分类、合并、分解、复制和修改等。派砚咙贡艇宗派逸唯骆祖饲尤卷纬凑斤贺填厚俊翰诽酝搐啥迪社稳校热酪全国计算机二级公共基础知识考题分析全国计算机二级公共基础知识考题分析页4【例7】对线性表,在下列( )情况下应当采用链表表示。A)经常需要随机地存取元素B)经常需要进行插入和删除操作C)表中元素需要占据一片连续的存储空间D)表中元素的个数不变【答案】B)【解析】由于链表不是顺序存储的,即当进行插入和删除操作时不需要进行移动大量的元素,所以当一些需要经常进行插入和删除操作的情况应当采用链表的方式存储。【例8】对于长度为n的顺序存储的线性表,当随机插入和删除一个元素时,需平均移动元素的个数为_____。【答案】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)1,2,3,4,5 B)5,3,4,1,2C)4,3,2,1,5 D)3,4,5,2,1【答案】B)【解析】由于栈的压入和退出只能在栈顶进行,所以要使出栈的第一个数是序列的最后一个数5,只能先把序列所有元素都压入栈,但这时出栈序列