部分公共基础知识.ppt

《部分公共基础知识.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一部分公共基础知识（30分：10道选择题+5道填空题）数据结构与算法数据结构：讨论数据的逻辑结构和存储结构算法：对特定问题求解步骤的一种描述，算法复杂度的概念和意义。程序设计基础结构化程序设计面向对象程序设计方法软件工程基础用科学知识和技术原理来定义、开发、维护软件。数据库设计基础研究数据库的结构、存储、设计、管理和使用的一门软件学科。一、数据结构含义相互之间存在一种或多种特定关系的数据元素的集合。数据结构与算法逻辑结构集合线性树图数据的存储结构（物理结构）是指______A)存储在外存中的数据B)数据所占的存储空间量C)数据在计算机中的顺序存储方式D数据的逻

2、辑结构在计算机中的表示D存储结构顺序存储方式：逻辑上相邻的元素存储在物理上相邻的存储单元里。链式存储方式：每个节点至少包含一个指针域，用指针来体现元素逻辑上的联系。二、线性结构1、线性表学号姓名性别年龄班级880801王小林男19计1880802陈红女20计2︰︰︰︰︰数据元素：记录a1a2︰an空闲内存状态顺序存储a1a2an…链式存储俗称单链表，也可形成循环单链表，双链表,循环双链表。指针a1a2an…ABC二、线性结构2、栈和队列anan-1︰a2a1进栈出栈栈顶栈底a1a2a3…an队头队尾入队列出队列各自的特点是？eg：下列数据结构中，能够按照“先进后

3、出”原则存取数据的是_____    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-12i-12i-1满二叉树完全二叉树非完全二叉树12345671234561234（5）具

4、有n个节点的完全二叉树的深度为log2n+1（6）树的度为所有结点中最大的度（7）任何一棵二叉树如叶子结点数为n1，度为2的结点数n2，则n1=n2+13、遍历二叉树（按某种搜索路径巡访树中各节点）---图1（1）先序遍历（根结点左子树右子树）（2）中序遍历（左子树根结点右子树）（3）后序遍历（左结点右子树根结点）先序：124536中序：425163后序：452631图1根结点叶子结点DBXEAYFZCABCDEFZXY对二叉树进行中序遍历的结果?对二叉树进行后序遍历的结果?DXEBYZFCAeg1:下列叙述中正确的是_________A）有一个以上根结点的数据

5、结构不一定是非线性结构B）只有一个根结点的数据结构不一定是线性结构C）循环链表是非线性结构D）双向链表是非线性结构Beg:一个栈初始状态为空，首先将5,4,3,2,1依次入栈，然后退栈一次，再将元素A,B,C,D依次如栈，之后将所有元素退栈，则所有元素退栈（包括中间退栈的元素）的顺序为_______________________eg:设某循环队列的容量为50，如果头指针front=45（指向队头元素的前一位置），尾指针rear=10（指向队尾元素），则该循环队列中共有_____个元素。eg:某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（假设根

6、结点在第1层）______A）3     B）4         C）6       D）7eg:一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后序遍历结果为__________。eg:下列数据结构中，属于非线性结构的是_________A）循环队列B）带链队列C）二叉树D）带链栈eg:某二叉树有5个度为2的结点以及3个度为1的结点，则该二叉树中共有________个结点。eg:在深度为7的满二又树中，度为2的结点个数为______1,D,C,B,A,2,3,4,515DDEBFCAC14631、算法特征可行性、确定性、有穷性、拥有足

7、够情报2、算法基本运算算术运算、逻辑运算、关系运算、数据传输3、算法基本控制结构顺序、选择、循环结构4、算法基本设计方法列举法、归纳法、递推、回溯等5、算法度量时间复杂度:执行算法所需要的计算工作量空间复杂度：算法在执行过程中所需的计算机存储空间算法eg:算法的时间复杂度是指________A）算法的执行时间B）算法所处理的数据量C）算法程序中的语句或指令条数D）算法在执行过程中所需要的基本运算次数D查找（在一个给定的数据结构中查找某个指定的元素）[21，46，24，57，99，77，86]，查找99顺序查找：从表中第一个记录开始，逐个进行记录关键字和给定值的比

8、较。(适用条件)二分查找