第一部分公共基础知识(精选).pptVIP

eg:数据库设计中，用E-R图来描述信息结构但不涉及信息在计算机中的表示，它属于数据库设计的( ) A）需求分析阶段 B）逻辑设计阶段 C）概念设计阶段 D）物理设计阶段 eg:在学生管理的关系数据库中，存取一个学生信息的数据单位是( )A）文件 B）数据库 C）字段 D）记录 eg:数据库管理系统中负责数据模式定义的语言是( )A）数据定义语言 B）数据管理语言C）数据操纵语言 D）数据控制语言 C D A （1）数据定义语言：负责数据的模式定义与数据的物理存取构建； （2）数据操纵语言：负责数据的操纵，如查询与增、删、改等； （3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。 eg:数据库设计的四个阶段是：需求分析，概念设计，逻辑设计和________ 物理设计 则由关系R和S得到关系T的操作是 ? A B C b 2 1 则由关系R得到关系S的操作是 ? eg:索引属于( )A)模式 B)内模式 C)外模式 D)概念模式 B 第一部分 公共基础知识（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