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

一、选择题(单选)1. 关于数据元素，下列描述不正确的是（D）。A. 数据元素可以包含多个数据项。B. 数据结构的算法大多以数据元素为基本操作单位。C. 数据元素一般代表某种现实世界中的对象。D. 数据元素必须有一个关键字。2. 循环链表head的尾结点指针p的特点是（A）。A. p-next=head B. p-next=head-nextC. p=head D. p=head-next3. 设一个栈的输入序列是a,b,c,d,e，则下列序列是栈的合法输出序列的是（D）。A. e a b c d B. d e a c bC. d c a b e D. c b a e d4. 循环队列存储在数组A0.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/1210. 在数据管理技术的发展过程中，经理了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是（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. CQ0CQ8为一循环队列，初态front=rear=5，进行下列操作：a, b, c, d入队；a, b出队，e, f, g, h, i, j, k, l, m入队，这时队的头、尾指示器状态为：front 7 ，rear 6 。12. 在以head为表头指针的带表头结点的单链表和循环链表中，判断链表为空的条件分别为 headnext=NULL 和_head=headnext13. 对于一组关键字41，62，34，67，89，54，76，22，93，8进行从小到大排序，写出其快速排序第一趟（一个关键字到位为一趟）排序后的序列： 8, 22, 34, 41, 89, 54, 76, 67, 93, 62 。14. 二叉排序树的查找递归算法:bool Find(BTreeNode* BST, int item) if (BST=NULL) return false; /查找失败 else if (item=BST-data) item=BST-data;/查找成功 return _; else if(itemdata) return Find(_,item); else return Find(_,item); /iftrue BST-left BST-right15. 可以使用SQL命令来操纵数据库，也可将SQL命令 嵌入 高级语言（如C, Pascal, Java等）程序中使用。三、判断题1. 层次模型可以直接表示n : m联系。 （ * ）2. 同一个关系的不同元组值可以相同。 （ * ）3. SQL属于关系数据库语言。 （ ）四、综合题1. 什么是数据的逻辑结构？什么是数据的物理结构？（略）2、 编写一个函数，把一个以整数作为结点的单链表转换成数组。其中数组长度要根据单链表长度动态建立，并编写主函数验证函数正确性。（略）3. 栈和队列的逻辑结构有何不同？链栈和链队列与普通单链表有何不同？（略）4. 循环队列是如何实现的？其队空和队满的条件各是什么？通过在逻辑上将顺序队看做首尾相接的结构，来实现循环队列。5. 二叉树链式存储结构和单链表有何异同点？相同点：都是链式存储，都有数据域；不同点：前者有两个指针域，后者只有一个指针域。6. 什么是满二叉树，什么是完全二叉树？（略）7. 什么是平均查找长度？比较顺序查找和折半查找的优缺点？（略）8. 编写一段程序，首先以学生信息为数据元素建立顺序表，其中学生信息包括学号、姓名、籍贯、专业、班级，顺序表按学号有序。程序可接收用户查询请求，其中按学号查询用折半查找实现，按姓名、籍贯、班级查询用顺序查找实现。按姓名、籍贯、班级查询时可能有多条满足条件的记录，这些记录都应显示出来。（略）9. 什么是排序？处理同样的元素集合时，排序和查找的算法复杂度有无差异，这种差异是如何形成的？处理同样的元素集合时，排序和查找的算法复杂度有差异，这是由于，查找算法的主要操作时比较两元素的关键字，其算法复杂度主要考察比较操作消耗的时间；而排序算法除比较操作外，移动元素也是其主要操作，因此其算法复杂度主要考察比较和移动两种操作消耗的时间。10. 阅读以下算法并回答问题。LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L&L-next) q=L；L=Lnext；p=L； S1： while(pnext) p=pnext； S2： pnext=q；qnext=NULL； return L； 请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能； （3）设链表表示的线性表为（a1,a2, ,an）,写出算法执行后的返回值所表示的线性表。解： （1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,an,a1）11. 请画出下图的邻接矩阵和邻接表。解：邻接矩阵：邻接表：12. 已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。解：EDCBIHJGFA13. 一个线性表为B=（12，23，45，57，20，3，78，31，15，36），设哈希表空间为H0H12，哈希函数为H（key）= key mod 13并用线性探测法解决冲突，请画出哈希表，并计算等概率情况下的平均查找长度。解：哈希表为：012345678910111278153574520312336121111114121上面最后一行为比较次数。平均查找长度：ASL=（1+1+1+1+1+1+1+1+4+2）/10 = 14/10 = 1.414. 假定允许每个仓库存放多个零件，每种零件也可在多个仓库中存放，而每个仓库中保存的零件都有库存数量。仓库的属性有：仓库号、面积、电话号码；零件的属性有：零件号、名称、规格、单价。根据上述说明画出E-R图。解：（注：上图中各实体、联系均有各自的属性，自行补充。）15. 假定一台机器可以由若干个工人操作，加工若干种零件，某个工人加工某种零件是在一台机器上完成的这道工序，而一个零件需要多道工序才能完成。用E-R图表示机器、零件和工人这三个实体之间的多对多联系。解：16. 假定有一个客户订货系统，允许一个客户一次（一张订单）预订多种商品，那么关系模式：订单（订单号、日期、客户编号、客户名、商品编码、数量）属于第几范式？为什么？解：属于第二范式。因为主属性为订单号，在此关系模式中，不存在部分函数依赖关系，但存在传递函数依赖关系。如：订单号传递函数决定客户名。17. 下列关系模式分别属于第几范式？为什么？（1） 关系： R(X, Y, Z)，函数依赖：XYZ（2） 关系： R(X, Y, Z)，函数依赖：YZ; XZY（3） 关系： R(X, Y, Z)，函数依赖：YZ; YX; XYZ（4） 关系： R(X, Y, Z)，函数依赖：XY; XZ（5） 关系： R(W, X, Y, Z)，函数依赖：XZ; WXY解：（1）第三范式 （2）第三范式 （3）第二范式 （4）第三范式 （5）第一范式（解此类题的关键