文档介绍：第一章数据结构与算法
1-1 算法
算法: 是指解题方案的准确而完整的描述(选择)
基本特征:
1 可行性 2 确定性 3 有穷性 4 拥有足够的情报(填空)
有穷性: 指算法执行有限个步骤后能终止(选择)
基本运算: 算术运算、关系运算、逻辑运算、
数据传输(选择或填空)
控制结构: 顺序结构、选择结构、循环结构(选择或填空)
算法复杂度: 时间复杂度和空间复杂度(填空)
时间复杂度: 是指执行算法所需要的计算工作量(选择)
空间复杂度: 是指执行算法所需要的内存空间(选择)
1-2 数据结构的基本概念
数据结构研究的三个方面:
1 数据的逻辑结构
2 数据的存储结构
3 对各种数据结构的运算(填空)
数据结构: 是指相互有关联的数据元素的集合(选择)
典型考题
数据结构中,与所用计算机无关的是数据的( )
A存储结构 B物理结构 C逻辑结构 D物理和存储结构
解析: 数据的存储结构和物理结构是同一概念,它们和计算机有关。本题答案C
1-3 线性表及其顺序存储结构
线性表: 由一组数据元素构成,数据元素的位置只取决于
自己的序号(选择)
如下图所示:
A1
A2
A3
……
An
结点个数n称为线性表的长度,当n=0时,称为空表。
线性表的顺序存储结构:
1 线性表中所有元素的所占的存储空间是连续的(选择)
2 线性表中各数据元素在存储空间中是按逻辑顺序依次
存放的(选择)
ai的存储地址为: ADR(ai)=ADR(a1)+(i-1)k
上述公式中: ADR(a1)为第一个元素的地址
k代表每个元素占的字节数
典型考题
顺序存储方法是把逻辑上相邻的结点存储在物理位置______的存储单元中。
解析: 根据顺序存储的概念,数据的逻辑顺序和物理顺序完全一致,故本题答案为相邻。
1-4 栈和队列
栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶(填空),而不允许插入与删除的另一端称为栈底(填空)。
如下图所示:
E
D
C
B
A
栈顶
栈底
栈组织数据的特点是: 先进后出或后进先出(选择)
栈的基本运算: 1 入栈 2 退栈 3 读栈顶元素(填空)
典型考题
栈底至栈顶依次存放元素A,B,C,D,在第五个元素E入栈前,栈中元素可以出栈,则出栈序列可能是( )
A ABCED B DBCEA C CDABE D DCBEA
解析: 根据栈的特点,4个元素出栈的顺序是D,C,B,A故A,B,C三个选项均错误。当D,C,B依次出栈后,E此时入栈再立即出栈,最后元素A再出栈,序列是DCBEA。
本题答案 D
队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。
如下图所示:
队头
A
B
C
D(队尾)
队列组织数据的特点是: 先进先出或后进后出(选择)
典型考题
栈和队列的共同点是( )
A 都是先进先出 B都是先进后出
C 只允许在端点处插入和删除元素
D 没有共同点
解析: 由栈和队列的定义可知,它们都只能在某端进行插入或删除操作。本题答案 C
1-5 线性链表
数据结构中的每一个结点对应于一个存储单元,这种存储单元称为存储结点,简称结点。
结点由两部分组成:
1 存储数据元素值,称为数据域。
2 存放指针称指针域,用于指向前一个或后一个结点。
如下图所示:
数据1
指针
数据2
指针
数据3
指针
链式存储结构特点:
1 存储数据结构的存储空间可以不连续(选择)
2 链式存储方式即可用于表示线性结构,也可用于表示
非线性结构(选择)
典型考题
1 线性表的顺序存储结构和链式存储结构分别是( )
A 顺序存取的存储结构、顺序存取的存储结构
B 随机存取的存储结构、顺序存取的存储结构
C 随机存取的存储结构、随机存取的存储结构
D 任意存取的存储结构、任意存取的存储结构
解析: 对于顺序存储,ADR(ai)=ADR(a1)+(i-1)K,根据序号i即可访问第i个元素,应为随机存取方式; 对于链式存储,要访问第i个元素只能从第一个元素由指针逐步访问,应为顺序存取。本题答案 B
2 用链表表示线性表的优点是( )
A 便于插入和删除操作
B 数据元素的物理顺序和逻辑顺序相同
C 花费的存储空间较顺序存储少
D 便于随机存取
解析: 在线性表的顺序存储中,为在某位置插入或删除元素,需将此位置后的元素均向后或向前移动,十分不方便; 而在链表中只需修改结点的指针即可实现。本题答案 A
1-6 树与二叉树
树是一种简单的非线性(选择)结构。
在树结构中,每一个结点只有一个前