厦门大学信科数据库及数据结构试题厦门大学信科数据库及数据结构试题厦门大学信科数据库及数据结构试题厦门大学信科数据库及数据结构试题.doc

一、选择题(单选) 1. 关于数据元素，下列描述不正确的是（D）。 A. 数据元素可以包含多个数据项。 B. 数据结构的算法大多以数据元素为基本操作单位。 C. 数据元素一般代表某种现实世界中的对象。 D. 数据元素必须有一个关键字。 2. 循环链表head的尾结点指针p的特点是（A）。 A. p-next=head B. p-next=head-next C. p=head D. p=head-next 3. 设一个栈的输入序列是a,b,c,d,e，则下列序列是栈的合法输出序列的是（D）。 A. e a b c d B. d e a c b C. d c a b e D. c b a e d 4. 循环队列存储在数组A[0..m]中，则入队时的队尾指针操作为（D）。 A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 5. 在单链表中指针p所指的结点后插入新结点s有下列3个步骤： ① s-data=x （赋值） ② p-next=s ③ s-next=p-next 正确的步骤顺序为（B）。 A. ①②③ B. ③②① C. ②①③ D. 无正确答案 6. 对于先序遍历和后序遍历结果相同的二叉树为（B）。 A. 一般二叉树 B. 只有根结点的二叉树 C. 根结点无左孩子的二叉树 D. 根结点无右孩子的二叉树 7. 若图的邻接矩阵是对称阵，则此图必然为（B）。 A. 有向图 B. 无向图 C. 连通图 D. 有向图或无向图 8. 关于哈夫曼树，下列描述正确的是（D）。 A. 一定是二叉排序树 B. 是一棵完全二叉树 C. 是一棵平衡二叉树 D. 以上三种说法都不对 9. 长度为12的按关键字有序的待查找序列，采用顺序存储，若用二分查找，则在等概率情况下，查找成功的ASL是（A ）。 A. 37/12 B. 62/13 C. 39/12 D. 49/12 10. 在数据管理技术的发展过程中，经理了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是（A ）。 A. 数据库系统 B. 文件系统 C. 人工管理 D. 数据项管理 11. 下列有关数据库的描述中，正确的是（C ）。 A. 数据库是一个DBF文件 B. 数据库是一个关系 C. 数据库是一个结构化的数据集合 D. 数据库是一组文件 12. 数据库设计中，将E-R图转换成关系数据模型的过程属于（C）。 A. 需求分析阶段 B. 逻辑设计阶段 C. 概念设计阶段 D. 物理设计阶段 13. 将E-R图转换到关系模式时，实体与联系都可以表示成（B）。 A. 属性 B. 关系 C. 键 D. 域 二、填空题 1. 衡量算法的两个主要指标是 时间复杂度 和 空间复杂度 。 2. 线性表的顺序存储结构通过 数组下标 来反映数据元素之间的逻辑关系。 3. 链表是采用链式存储结构的线性表。进行 插入 、 删除 操作时，使用链表比使用顺序存储结构的效率高。 4. 栈又称为 后进先出 （线性）表，队列又称为 先进先出 （线性）表。 5. 二叉树的第h层上最多含有的结点数为 2h-1 。 6. 高度为8的完全二叉树至少有 64 个叶子结点。 7. 有向图的邻接矩阵 不是 对称阵。 8. 图的广度优先搜索算法中使用了 队 （辅助数据结构），以记录正在访问的这一层和上一层的顶点，以便于向下一层访问。 9. 二叉排序树的查找效率与二叉树的 高度 有关，在 待查序列全顺序或全逆序 情况下查找效率最低。 10. 衡量查找算法优劣的指标是 平均查找长度 （ASL） 。 11. CQ[0]～CQ[8]为一循环队列，初态front=rear=，a, b, c, d入队；a,