2011年3月二级公共基础知识讲义(1.7和1.8及课后习题)

内部资料2011年3月计算机等级考试二级公共基础知识培训讲义理工大楼915二级Access考试介绍一、考试方式1．笔试：90分钟，满分100分，其中含公共基础知识部分30分2．上机操作：90分钟，满分100分二、笔试题型及分值（根据考试大纲及往年试题)1．选择题70分（每小题2分，共35题）2．填空题30分（每空2分，共15题）三、上机操作1．基本操作（30分）2．简单应用（40分）3．综合应用（30分）我们的目标通过二级考试基础知识部分：30分设有10道选择题和5道填空题第一章数据结构与算法1.1算法1.2数据结构的基本概念1.3线性表及其顺序存储结构1.4栈和队列1.5线性链表1.6树与二叉树1.7查找技术1.8排序技术1.7查找技术查找是指在一个给定的数据结构中查找某个指定的元素。1.7.1顺序查找顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查找到所要的元素为止；否则就是表中没有要找的元素，查找不成功。对于表中记录的关键字是无序的表，只能采用这种方法。顺序查找的使用情况：（1）线性表为无序表；（2）表采用链式存储结构。1.7.2二分法查找二分查找又称折半查找，是针对有序表进行查找的简单、有效而又较常用的方法。所谓有序表，即要求表中的各元素按关键字的值有序（升序或降序）存放。只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。历年考题2005.4（4）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为A）log2nB）n/2C）nD）n+12005.9（2）下列数据结构中，能用二分法进行查找的是A）顺序存储的有序线性表B）线性链表C）二叉链表D）有序线性链表历年考题2006.9（8）在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为A）63B）64C）6D）72008.9(3)在长度为n的有序线性表中进行二分查找，最坏情况下需要比较的次数是A)O(n)B)O(n2)C)O(log2n)D)O(nlog2n)1.8排序技术排序也是数据处理的重要内容。排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。1.冒泡排序法[2005年4月选择题第3题、第4题]（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是A）冒泡排序为n/2B）冒泡排序为nC）快速排序为nD）快速排序为n(n-1)/2[2006年4月填空题第1题]对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_____。NCRE考题[2007年9月选择题第7题]（7）冒泡排序在最坏情况下的比较次数是A)n(n+1)/2B)nlog2nC)n(n-1)/2D)n/2[2008年4月选择题第6题]对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是A)快速排序B)冒泡排序C)直接插入排序D)堆排序一.选择题1.算法的时间复杂度是指()A.执行算法程序所需要的时间B.算法程序的长度C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数2.算法的空间复杂度是指()A.算法程序的长度B.算法程序中的指令条数C.算法程序所占的存储空间D.算法执行过程中所需要的存储空间3.下列叙述中正确的是()A.线性表是线性结构B.栈与队列是非线性结构C.线性链表是非线性结构D.二叉树是线性结构4.数据的存储结构是指()A.数据所占的存储空间量B.数据的逻辑结构在计算机中的表示C.数据在计算机中的顺序存储方式D.存储在外存中的数据5.下列关于队列的叙述中正确的是()A.在队列中只能插入数据B.在队列中只能删除数据C.队列是先进先出的线性表D.队列是先进后出的线性表6.下列关于栈的叙述中正确的是()A.在栈中只能插入数据B.在栈中只能删除数据C.栈是先进先出的线性表D.栈是先进后出的线性表7.设有下列二叉树：对此二叉树中序遍历的结果是A)ABCDEFB)DBEAFCC)ABDECFD)DEBFCA8.在深度为5的满二叉树中，叶子结点的个数为()A.32B.31C.16D.159.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为()A.n+1B.nC.(n+1)/2D.n/210.设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1.则T的叶子结点数为A.8B.7C.6D.5二.填空题1.对长度为n的有序线性表中进行二分查找，需要的比较次数为()。2.设一棵完全二叉树共有700个结点，则在该二叉树中有()个叶子结点。3.设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为()。4.在最坏情况下，冒泡排序的时间复杂度为()。5.在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有()个元素。参考答案一．选择题1.C2.D3.A4.B5.C6.D7.B8.C9.B10.A二．填空题1)log2n2)3503)DEBFCA4)n(n-1)/25)3如何购买教材和辅导书？目前，计算机等级考试的辅导书很多，考生在购买时一定要注意以下几点：（1）购买图书不在多而在精。鉴于一般考生的学习时间紧张，建议购买学习效率高的图书。（2）是不是通过网络下载一些题目就不用买试卷了？对于这个问题，其实是很多考生的误区。目前来看，网络上提供的资料多是从辅导书中复制过去的，且都没有经过严谨的校对和排版，错误率相当高。我们一般不建议这样的做法。（3）做题就做真题，真题，真题！（4）解析是否到位？其实，题目哪都有，关键是看题目的解析是否详细、是否通俗易懂。紧扣最新全国计算机等级考试大纲汇集数套笔试真题和全真模拟试卷富含笔试真题完整答案和详细解析凝聚金牌教师数年教学心得和经验