资源简介

1.初识数据结构
【要点提示】
1.瑞士计算机科学家沃斯指出“___________________”,形象地阐明了计算机程序设计的本质是______________________的设计。
2.数据结构的概念：
(1)数据元素：数据的______单位，可由若干数据项组成。数据项是具有独立含义的______数据表示单位。
(2)数据类型：具有__________的计算机数据的集合及在这个数据集合上的一组操作。数据类型可分为__________和__________。
(3)数据结构：数据之间的相互关系，即数据的__________。主要包含数据的__________、数据的__________和数据的________。
3.常见的数据结构
(1)数组：表示一批数据，不仅可以描述数据本身，还可以描述数据所处的位置或数据之间的前后顺序关系。可以迅速地通过______精确访问序列中的某个数据元素，又可以通过下标按顺序______序列中的每个元素。
(2)链表：表示一批数据，这类数据之间具有明确的相互链接的___________，但对数据对象本身的___________不作要求。常用的链表有单向链表、双向链表、循环链表。
(3)队列：数据具有“____________”且中间__________的组织和操作的性质。在数据序列的头部（称为队首）进行数据的读取（即出队），在数据序列的尾部（称为队尾）进行数据的插入（即入队）。
(4)栈：数据具有“___________”且所有操作只能在一端（称为栈顶）进行的性质。仅可在一端进行数据的读取(称为出栈)和插入（称为入栈）操作。
(5)树：数据元素前面只有一个元素，后面可以有______________元素相邻，所有元素之间的关系特征像一棵倒放的树。
4.对于同一问题，若依据不同的数据结构来设计算法，则算法的处理效率、程序的实现效率也会_______。
限时训练
1.以下关于数据结构的描述，不正确的是( )
A.数据的逻辑结构是指数据元素之间的逻辑排列和对应关系
B.数据的存储结构包括数据元素的存储及数据元素之间关系的存储
C.数据的运算是指对数据施加的操作，包括删除、查找、插入数据等
D.数据结构设计时不需要考虑编程实现和数据处理的效率
2.数据元素及其关系在计算机存储器内的表示，也称为数据的( )
A.线性结构 B.物理结构 C.逻辑结构 D.空间结构
3.下列数据结构中属于线性数据结构的是( )
①数组 ②栈 ③队列 ④链表 ⑤树
A.①②③④⑤ B.①②③④ C.①②④⑤ D.①②③⑤
4.用一带盖的玻璃筒来放取乒乓球，放、取球只能在带盖的一端进行（另一端为封闭状态)，且筒的直径只允许一个乒乓球进出。若放入球的编号序列为1、2、3、4，则取出球的编号序列不可能的是( )
A.1、2、3、4 B.2、3、4、1 C.4、2、3、1 D.3、2、1、4
5.关于数据项与数据元素的描述，下面说法不正确的是( )
A.数据元素可由若干数据项组成
B.同一数据元素中各数据项的数据类型必须相同
C.数据项是数据的最小单位，通常用来描述实体的某种属性
D.数据元素是数据的基本单位，在计算机中通常作为一个整体来处理
6.诸葛亮家族的部分家谱如图所示。和家谱图结构相似的数据结构是( )
A.链表
B.队列
C.树
D.栈
7.在日常幻灯片（如PowerPoint演示文稿）的放映中，可以通过超链接的方式进行幻灯片之间的任意跳转。与这种页面之间相互链接的表现形式相似的数据结构是( )
A.树 B.链表 C.队列 D.栈
8.数据结构中栈和队列的共同特点是( )
A.都是先进后出 B.都是先进先出
C.只允许在端点处插入和删除数据 D.没有共同点
9.小陈同学高一结束后需要换寝室，他将全部物品打包成6个箱子并编号叠放在一起（如图1-10所示）。为了搬运物品方便，他借了一辆手推车，该手推车一次最多能叠放3个箱子（如图1-11所示）箱子从上往下依次叠放在小推车上（假定每次只放一个箱子），小推车每次可以叠放1、2或3个箱子，小推车上的箱子也是从上往下依次拿取（假定每次只取一个箱子），搬运后的箱子仍引旧叠放在一起。
(1)在搬运中，与手推车上箱子叠放和拿取的过程相似的数据结构是___栈_______
(2)若搬运完毕后箱子的叠放顺序是2、1、3、4、6、5（从下往上），则每趟手推车至多需要搬运的箱子数是___2_____个。
(3)在每趟搬运时手推车上的箱子必须全部搬离的情况下：
请写出至少2个搬运完毕后箱子可能的叠放（从下往上）顺序：_123456___、_321654___
请写出至少1个搬运完毕后不可能的箱子叠放（从下往上）顺序：___342165_________
10.线性表是由零个或多个数据元素组成的有限序列，数据元素之间的关系是一对一的关系。线性表是一种基本的、常见的数据结构，可以根据需要向线性表中添加元素或者删除元素。数组、队列、栈、链表都是线性表的特殊形式。
小林使用数组、链表、队列和栈这四种数据结构，分别实现线性表中数据元素的删除操作，以探究这几种数据结构在数据删除操作中的特点。现假设有10个数据元素的线性表（数据不重复)，以删除数据元素“4”为例进行分析(10个数据元素的顺序表如图所示)，数据删除后其余数据元素的相对位置保持不变。
补充完整以下分析过程：
(1)数组存储：
如图所示，从a[0]开始找到数组元素“4”需要查找3次，删除“4”后，其后续数组元素需要往前移动___7____次；此时数组元素a[2]的值为__1_____, a[9]的值为____5___
(2)单链表存储：
如图1-14所示，从第1个节点的数据元素“2”开始找到数据元素“4”（出队元素依次在队尾入队）需要查找___3___次，删除该节点（如图1-15所示），其后续节点需要移动___0___
次；此时链表中数据元素的个数为__9____个。
(3)队列存储：
如图1-16所示，从队首查找需要出队3次找到数据元素“4”（出队元素依次在队尾入队），删除该元素后，为了保持原队列其他数据元素的次序不变，还需出队__7__次，入队_7___次；此时队列中数据元素的个数为_9___个。
(4)栈存储：
如图1-17所示，从栈顶查找需要出栈_3___次找到数据元素“4”，删除该元素后，为了保持原栈内其他数据元素的次序不变，还需入栈__2__次；此时栈顶指向的数据元素为__2_____
11.有如下图所示的单向链表：
从头指针head指向的节点开始查找数据元素“5”，并删除该节点，下列说法正确的是（ ）
A.共需查找3次
B.删除数据元素“5”的节点，后续节点需要移动3次
C.头指针head将指向数据元素“7”的节点
D.此时链表中数据元素的个数为6个
12.数组b中存储的数据情况如下图所示：
b[0] b[1] b[2] b[3] b[4] b[5] b[6] b[7] b[8] b[9]
20 12 8 6 9 5 10 7 18 11
要在数组元素b[2]后面插入数据“17”，则数组元素需要往后移动的次数为( )
A.0 B.3 C.4 D.7
13.队列Q1的存储情况如下图所示：
要查找并得到数据元素“3”，则需要队列Q1中的元素出队次数为( )
A.1 B.3 C.4 D.6
14.设栈S和队列Q的初始状态为空，元素w1、w2、w3、w4、w5依次通过栈S,一个元素出栈后即进入队列Q,下列不可能是出队序列的是( )
A.w5、w4、w3、w2、w1 B.w3、w2、w1、w4、w5
C.w4、w2、w1、w3、w5 D.w1、w2、w3、w4、w5
15.下列对数据结构的描述正确的是( )
A.逻辑结构相邻的两个数据元素，其存储位置也一定相邻
B.对于同一个问题，只能使用一种数据结构来设计算法并解决
C.选择的数据结构不同，算法的处理效率、程序的运行效率也不同
D.对同一操作（如删除、插入数据），不同的数据结构实现的方法相同
16.关于数组和链表，以下描述不正确的是( )
A.数组通过下标访问或遍历序列中的数据元素
B.常见的链表有单向链表、双向链表和循环链表
C.一般情况下，数组元素的插入和删除效率比链表要低
D.一般情况下，数组元素的查找效率比链表要低
17.下列关于数据结构的描述，正确的是（ ）
A.数据的物理结构是指数据元素之间的逻辑排列和对应关系
B.数据的逻辑结构是指数据元素及其关系在计算机存储器内的表示
C.数据的运算是指对数据施加的操作，但仅包括插入和删除数据
D.数据结构设计的目的是使数据元素间的相互关系能准确地反映现实问题中的事物逻辑

展开更多......

收起↑