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

1、内部资料,2011年3月计算机等级考试 二级公共基础知识培训讲义 理工大楼915,二级Access考试介绍,一、考试方式1笔试：90 分钟，满分100 分，其中含公共基础知识部分30分 2上机操作：90 分钟，满分100 分 二、笔试题型及分值（根据考试大纲及往年试题) 1选择题70 分（每小题2分，共3 5题）2填空题30 分（每空2 分，共15题） 三、上机操作1基本操作（30 分）2简单应用（40 分）3综合应用（30 分）,我们的目标,通过二级考试,基础知识部分：30分,设有10道选择题和5道填空题,第一章 数据结构与算法,1.1 算法 1.2 数据结构的基本概念 1.3 线性表及其顺

2、序存储结构 1.4 栈和队列 1.5 线性链表 1.6 树与二叉树 1.7 查找技术 1.8 排序技术,1.7 查找技术,查找是指在一个给定的数据结构中查找某个指定的元素。 1.7.1 顺序查找 顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查找到所要的元素为止；否则就是表中没有要找的元素，查找不成功。对于表中记录的关键字是无序的表，只能采用这种方法。 顺序查找的使用情况： （1）线性表为无序表； （2）表采用链式存储结构。,1.7.2 二分法查找,二分查找又称折半查找，是针对有序表进行查找的简单、有效而又较

3、常用的方法。所谓有序表，即要求表中的各元素按关键字的值有序（升序或降序）存放。只适用于顺序存储的有序表，对于长度为n的有序线性表，最坏情况只需比较log2n次。,历年考题,2005.4 （4）对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 A）log2n B）n/2 C）n D）n+1 2005.9 （2）下列数据结构中，能用二分法进行查找的是 A）顺序存储的有序线性表 B）线性链表 C）二叉链表 D）有序线性链表,历年考题,2006.9 （8）在长度为64的有序线性表中进行顺序查找，最坏情况下需要比较的次数为 A）63 B）64 C）6 D）7 2008.9 (3)在长度为n

4、的有序线性表中进行二分查找，最坏情况下需要比较的次数是 A) O(n) B) O(n2) C) O(log2n) D) O(nlog2n),1.8 排序技术,排序也是数据处理的重要内容。 排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。,1.冒泡排序法,2005年4月 选择题第3题、第4题,（3）对于长度为n的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是 A）冒泡排序为n/2 B）冒泡排序为n C）快速排序为n D）快速排序为n(n-1)/2 2006年4月 填空题第1题 对长度为10的线性表进行冒泡排序，最坏情况下需要比较的次数为_。,NCRE考题,2007年9月

5、选择题第7题 （7）冒泡排序在最坏情况下的比较次数是 A)n(n+1)/2 B)nlog2n C)n(n-1)/2 D)n/2 2008年4月 选择题第6题 对长度为n的线性表排序，在最坏情况下，比较次数不是n(n-1)/2的排序方法是 A)快速排序 B) 冒泡排序 C) 直接插入排序 D) 堆排序,一.选择题 1.算法的时间复杂度是指( ) A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 2.算法的空间复杂度是指( ) A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程

6、中所需要的存储空间 3.下列叙述中正确的是( ) A. 线性表是线性结构 B. 栈与队列是非线性结构 C. 线性链表是非线性结构 D. 二叉树是线性结构,4.数据的存储结构是指( ) A. 数据所占的存储空间量 B. 数据的逻辑结构在计算机中的表示 C. 数据在计算机中的顺序存储方式 D. 存储在外存中的数据 5.下列关于队列的叙述中正确的是( ) A. 在队列中只能插入数据 B. 在队列中只能删除数据 C. 队列是先进先出的线性表 D. 队列是先进后出的线性表 6.下列关于栈的叙述中正确的是( ) A. 在栈中只能插入数据 B. 在栈中只能删除数据 C. 栈是先进先出的线性表 D. 栈是先进

7、后出的线性表,7.设有下列二叉树： 对此二叉树中序遍历的结果是 A) ABCDEF B) DBEAFC C) ABDECF D) DEBFCA,8.在深度为5的满二叉树中，叶子结点的个数为( ) A. 32 B. 31 C. 16 D. 15 9.对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为( ) A. n+1 B. n C. (n+1)/2 D. n/2 10.设树T的度为4，其中度为1，2，3，4的结点个数分别为4，2，1，1 .则T的叶子结点数为 A. 8 B. 7 C. 6 D. 5,二.填空题,1. 对长度为n的有序线性表中进行二分查找，需要的比较次数为( ) 。

8、2. 设一棵完全二叉树共有700个结点，则在该二叉树中有( )个叶子结点 。 3. 设一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为( ) 。 4. 在最坏情况下，冒泡排序的时间复杂度为( ) 。 5. 在一个容量为15的循环队列中，若头指针front=6，尾指针rear=9，则该循环队列中共有( )个元素。,参考答案,一选择题 1.C 2.D 3.A 4.B 5.C 6.D 7.B 8.C 9.B 10.A 二填空题 1)log2n2) 350 3) DEBFCA 4) n(n-1)/2 5) 3,如何购买教材和辅导书？,目前，计算机等级考试的辅导书很多，考生在购买时一定要注意以下几点： （1）购买图书不在多而在精。鉴于一般考生的学习时间紧张，建议购买学习效率高的图书。 （2）是不是通过网络下载一些题目就不用买试卷了？对于这个问题，其实是很多考生的误区。目前来看，网络上提供的资料多是从辅导书中复制过去的，且都没有经过严谨的校对和排版，错误率相当高