数据结构与数据库技术复习题2010~2011.doc

数据结构部分
1、数据结构术语及其他们之间的关系,数据结构研究的内容。
2、算法定义及5个特征,对给定的一段程序要会求算法时间复杂度。
3、线性表的特点,顺序存储结构和链式存储结构的特点,创建、插入、删除算法。
4、栈、队列的特点,栈空、栈满条件,入栈、出栈动作描述,循环队列队空、队满的条件。
5、二叉树的术语,二叉树的性质,二叉树存储结构,满二叉树和完全二叉树的特点,二叉树遍历,由遍历序列还原一棵二叉树。
6、顺序查找和二分查找时元素需比较的次数,二分查找过程描述---判定树。
7、课堂讲过的每一种排序方法要求对给定的一组关键字都能给出每趟排序的结果,最后分析关键字比较的次数及排序的稳定性。
数据库技术部分
1、数据管理系统的三个阶段的特点,数据库术语及其他们之间关系,数据库系统的体系结构------三级模式和二级映射,数据独立性。
2、实体联系模型(E-R图)、层次模型、网状模型、关系模型(二维表),E-R图,关系表的特点,关系模型的3类完整性约束。关系模型包含的内容。
3、关系代数-----并、交、差、笛卡尔积、投影、选择、连接、自然连接。
4、数据库设计4个阶段,每个阶段要完成的任务。ER图向关系模型转换的原则、转换的方法。
5、SQL语句(创建、插入、修改、删除、查询),带条件的查询,简单的连接查询必须掌握。
一、选择题
,算法是指( C )。
A)查询方法 B)加工方法
C)解题方案的准确而完整的描述 D)排序方法
,哪个不是一个算法一般应该具有的基本特征( C )。
A)确定性 B)可行性 C)无穷性 D)拥有足够的情报
( C )。
A)算法的执行效率与数据的存储结构无关
B)算法的空间复杂度是指算法程序中指令(或语句)的条数(指的是算法所占用的空间)
C)算法的有穷性是指算法必须能在执行有限个步骤之后终止
D)以上三种描述都不对
( D )。
A)算法程序的长度 B)算法程序中的指令条数
C)算法程序所占的存储空间 D)算法执行过程中所需要的存储空间
( D )。
A)找出数据结构的合理性
B)找出算法中输入和输出之间的关系
C)分析算法的易懂性和可靠性
D)分析算法的效率以求改进
( C )。
A)执行算法程序所需要的时间 B)算法程序的长度
C)算法执行过程中所需要的基本运算次数 D)算法程序中的指令条数
( D )。
A)循环、分支、递归 B)顺序、循环、嵌套
C)循环、递归、选择 D)顺序、选择、循环
( B )。
A)数据所占的存储空间量 B)数据的逻辑结构在计算机中的表示
C)数据在计算机中的顺序存储方式 D)存储在外存中的数据
( A )。
A)线性表是线性结构 B)栈与队列是非线性结构
C)线性链表是非线性结构 D)二叉树是线性结构
( A )。
A)数据的存储结构 B)数据的逻辑结构 C)线性结构 D)树形结构
,从逻辑上可以把数据结构分为( A )。
A)线性结构和非线性结构 B)动态结构和静态结构
C)外部结构和内部结构 D)简单结构和复杂结构
( C )。
A)队列 B)线性表 C)二叉树 D)栈
( A )。
A)便于插入和删除操作
B)数据元素的物理顺序与逻辑顺序相同
C)花费的存储空间较顺序存储少
D)便于随机存取
( B )
A)线性表的链式存储结构与顺序存储结构所需要的存储空间是相同的
B)线性表的链式存储结构所需要的存储空间一般要多于顺序存储结构
C)线性表的链式存储结构所需要的存储空间一般要少于顺序存储结构
D)上述三种说法都不对
( C )。
A)可以提高对表的访问速度 B)可以随机访问
C)使空表和非空表的处理方法统一 D)节省存储空间
( B )。
A)不必事先估计存储空间 B)可以随机访问任意结点
C)插入元素不需要移动任何元素 D)所需空间与其长度成正比
,最节省时间的存储方式是( A )。
A)顺序表 B)单链表 C)双向链表 D)单循环链表
,双向链表的优点之一是( B )。
A)插入、删除操作更简单 B)顺序访问相邻结点更加方便
C)可以实现随机