计算机2级公共基础知识讲课用(第一部分).ppt

2012年计算机等级考试

二级公共基础知识培训

公共计算机教学部;第一章数据结构与算法;数据结构与算法历年试题分数分布;1．1算法;1．1算法;1.1.2算法复杂度;算法的历年考题;算法的历年考题;【真题4】下列叙述中正确的是________。（2007年3月）

A)数据的逻辑结构与存储结构是一一对应的

B)算法的时间复杂度与空间复杂度一定相关

C)算法的效率只与问题的规模有关，而与数据的存储结构无关

D)算法的时间复杂度是指执行算法所需要的计算工作量

解析：1、算法的时间复杂度是指执行算法所需要的计算工作量。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数；算法的空间复杂度一般是指执行这个算法所需要的内存空间。

2、算法的时间复杂度与空间复杂度并不相关。

3、数据的逻辑结构就是数据元素之间的逻辑关系，它是从逻辑上描述数据元素之间的关系，是独立于计算机的；数据的存储结构是研究数据元素和数据元素之间的关系如何在计算机中表示，它们并非一一对应。

4、算法的执行效率不仅与问题的规模有关，还与数据的存储结构有关。

答案：D;【真题5】下列叙述中正确的是________。（2006年9月）

A)一个算法的时间复杂度大，则其空间复杂度必定小

B)三种说法都不对

C)一个算法的空间复杂度大，则其时间复杂度也必定大

D)一个算法的空间复杂度大，则其时间复杂度必定小

解析：1、时间复杂度是指一个算法执行时间的相对度量；空间复杂度是指算法在运行过程中临时占用所需存储空间大小的度量。

2、人们都希望选择一个既省存储空间、又节省执行时间的算法。然而，有时为了加快算法的运行速度，不得不增加空间开销；有时为了能有效地存储算法和数据，又不得不牺牲运行时间。时间和空间的效率往往是一对矛盾，很难做到两全。但是，这不适用于所有的情况，也就是说时间复杂度和空间复杂度之间虽然经常矛盾，但是二者不存在必然的联系。

答案：B;1.2数据结构的基本概念;1.2数据结构的基本概念;1.2.1什么是数据结构;数据的逻辑结构和存储结构;;;;1.2.2数据结构的图形表示;1.2.3线性结构与非线性结构;\

;线性表及其顺序存储结构;1.3.2线性表的顺序存储结构;1.3.3线性表的插入运算;线性表的删除运算;;1.4栈和队列;栈及其基本运算;2.栈的顺序存储及其运算;;;;;;;;;1.4.2队列及其基本运算;队列示意图;2.循环队列及其运算;循环队列;;;;;;;;思考题;1.5线性链表;;线性表中存储结点的结构;1.5.2线性链表的基本运算;1.5.2线性链表的基本运算;;1.5.3循环链表及其基本运算;循环链表;【真题1】下列叙述中正确的是________。（2008年9月）

A)顺序存储结构能存储有序表，链式存储结构不能存储有序表

B)链式存储结构比顺序存储结构节省存储空间

C)顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的

D)顺序存储结构只针对线性结构，链式存储结构只针对非线性结构

解析：顺序存储方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里，结点之间的关系由存储单元的邻接关系来体现。而链式存储结构的存储空间不一定是连续的。链式结构的结点由两部分组成，一部分是数据信息，另一部分是地址域，因此在存储空间上要多于顺序存储所占用的空间。

答案：C;【真题2】下列叙述中正确的是________。（2007年9月）

A)程序设计语言中的数组一般是顺序存储结构，因此，利用数组只能处理线性结构

B)三种说法都不对

C)数据的逻辑结构与存储结构必定是一一对应的

D)由于计算机存储空间是向量式的存储结构，因此，数据的存储结构一定是线性结构

解析：数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构。数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等。

答案：B;【真题3】下列叙述中正确的是________。（2005年9月）

A)一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率

B)一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率

C)一个逻辑数据结构只能有一种存储结构

D)数据的逻辑结构属于线性结构，存储结构属于非线性结构

解析：一般来说，一种数据的逻辑结构根据需要可以表示成多种存储结构，常用的存储结构有顺序、链接、索引等存储结构。而采用不同的存储结构，其数据处理的效率是不同的。

答案：B;【真题6】下列对于线性链表的描述中正确