文档介绍：第一部分公共基础知识 (30分:10道选择题+5道填空题)
数据结构与算法
数据结构:讨论数据的逻辑结构和存储结构
算法:对特定问题求解步骤的一种描述,算法复杂度的概念和意义。
程序设计基础
结构化程序设计
面向对象程序设计方法
软件工程基础
用科学知识和技术原理来定义、开发、维护软件。
数据库设计基础
研究数据库的结构、存储、设计、管理和使用的一门软件学科。
一、数据结构含义
相互之间存在一种或多种特定关系的数据元素的集合。
数据结构与算法
逻辑结构
集合
线性
树
图
数据的存储结构(物理结构)是指______
A)存储在外存中的数据 B)数据所占的存储空间量
C)数据在计算机中的顺序存储方式 D数据的逻辑结构在计算机中的表示
D
存储结构
顺序存储方式:逻辑上相邻的元素存储在物理上相邻的存储单元里。
链式存储方式:每个节点至少包含一个指针域,用指针来体现元素逻辑上的联系。
二、线性结构
1、线性表
学号
姓名
性别
年龄
班级
880801
王小林
男
19
计1
880802
陈红
女
20
计2
︰
︰
︰
︰
︰
数据元素:记录
a1
a2
︰
an
空闲
内存状态
顺序存储
a1
a2
an
…
链式存储
俗称单链表,也可形成循环单链表,双链表,循环双链表。
指针
a1
a2
an
…
A
B
C
二、线性结构
2、栈和队列
an
an-1
︰
a2
a1
进栈
出栈
栈顶
栈底
a1 a2 a3 … an
队头
队尾
入队列
出队列
各自的特点是?
eg:下列数据结构中,能够按照“先进后出”原则存取数据的是_____      A)循环队列      B)栈         C)队列      D)二叉树
B
三、非线性结构
1、树和二叉树
2、二叉树的性质
(1)在二叉树的第i层上至多有结点。(i≧1)
(2)深度为k的二叉树至多有结点。(k ≧1)
(3)一棵深度为k且有2k-1结点的二叉树称为满二叉树。
(4)深度为k,有n个节点的二叉树,当且仅当其每个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时,称之为完全二叉树。
第i层:①1 ②2 ③4 ④8 …依次推断
2i-1
深i层:①1 ②3 ③7 ④15 …依次推断
2i-1
2i-1
2i-1
满二叉树完全二叉树非完全二叉树
1
2
3
4
5
6
7
1
2
3
4
5
6
1
2
3
4
(5)具有n个节点的完全二叉树的深度为log2n+1
(6)树的度为所有结点中最大的度
(7)任何一棵二叉树如叶子结点数为n1,度为2的结点数n2,则n1=n2+1
3、遍历二叉树(按某种搜索路径巡访树中各节点)---图1
(1)先序遍历(根结点左子树右子树)
(2)中序遍历(左子树根结点右子树)
(3)后序遍历(左结点右子树根结点)
先序:1 2 4 5 3 6 中序:4 2 5 1 6 3
后序:4 5 2 6 3 1
图1
根结点
叶子结点
DBXEAYFZC
A
B
C
D
E
F
Z
X
Y
对二叉树进行中序遍历的结果?
对二叉树进行后序遍历的结果?
DXEBYZFCA
eg1:下列叙述中正确的是_________ A)有一个以上根结点的数据结构不一定是非线性结构 B)只有一个根结点的数据结构不一定是线性结构 C)循环链表是非线性结构 D)双向链表是非线性结构
B
eg:一个栈初始状态为空,首先将5,4,3,2,1依次入栈,然后退栈一次,再将元素A,B,C,D依次如栈,之后将所有元素退栈,则所有元素退栈(包括中间退栈的元素)的顺序为_______________________
eg:设某循环队列的容量为50,如果头指针front=45(指向队头元素的前一位置),尾指针rear=10(指向队尾元素),则该循环队列中共有_____个元素。
eg:某二叉树共有7个结点,其中叶子结点只有1个,则该二叉树的深度为(假设根结点在第1层)______ A)3       B)4             C)6        D)7
eg:一棵二叉树的中序遍历结果为DBEAFC,前序遍历结果为ABDECF,则后序遍历结果为__________。
eg:下列数据结构中,属于非线性结构的是_________ A)循环队列     B)带链队列    C)二叉树    D)带链栈
eg:某二叉树有5个度为2的结点以及3个度为1的结点,则该二叉树中共有________个结点。
eg:在深度为7的满二又树中,度为2的