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

1、、选择题（单选）1 .关于数据元素，下列描述 不正确的是（D）。A.数据元素可以包含多个数据项。B.数据结构的算法大多以数据元素为基本操作单位。C.数据元素一般代表某种现实世界中的对象。D.数据元素必须有一个关键字。2 .循环链表head的尾结点指针p的特点是（A）。A. p->next=headB. p->next=head->nextC. p=headD. p=head->next3.设一个栈的输入序列是a,b,c,d,e ,则下列序列是栈的合法输出序列的是（D）。A. e a b c dB. d e a c bC. d c a b eD. c b a e d4.循

2、环队列存储在数组A0.m中，则入队时的队尾指针操作为（D）。A. rear=rear+1B. 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.无正确答案A. 一般二叉树B.只有根结点的二叉树C.根结点无左孩子的二叉树D.根结点无右孩子的二叉树7 .若图的邻接矩阵是对称阵，则此图必然为（B）。A.有向图B.无向图C.连通图D

3、.有向图或无向图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.数据库是一

4、个关系C.数据库是一个结构化的数据集合D.数据库是一组文件12 .数据库设计中，将 E-R图转换成关系数据模型的过程属于（C）。A.需求分析阶段B.逻辑设计阶段C.概念设计阶段D.物理设计阶段A.属性B.关系C.键 D.域二、填空题1 .衡量算法的两个主要指标是时间复杂度 和 空间复杂度 。2 .线性表的顺序存储结构通过数组下标来反映数据元素之间的逻辑关系。3 .链表是采用链式存储结构的线性表。进行 插入、删除 操作时,使用链表比使用顺序存储结构的效率高。4 .栈又称为 后进先出（线性）表，队列又称为先进先出（线性）表。5 .二叉树的第h层上最多含有白结点数为2 h-1。6 .高度为8的完全二

5、叉树至少有 64 个叶子结点。7 .有向图的邻接矩阵 不是对称阵。8 .图的广度优先搜索算法中使用了队（辅助数据结构），以记录正在访问的这一层和上一层的顶点，以便于向下一层访问。9 .二叉排序树的查找效率与二叉树的高度 有关,在待查序列全顺序或全逆序情况下查找效率最低。10 .衡量查找算法优劣的指标是平均查找长度（ASD 。11 . CQ0CQ8为一循环队列，初态 front=rear=5 ,进行下列操作：a, b, c, d 入队；a, b出队，e, f, g, h, i, j, k, l, m入队，这时队的头、尾指示器状态为：front = J7, rear12 .在以head为表头指针的

6、带表头结点的单链表和循环链表中，判断链表为空的条件分别为 head f next=NULL 和_head=headf next13 .对于一组关键字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; 可以使用SQL命令来操纵数据库，也可将SQL命令嵌入高级语言（如

7、C, Pascal, Java 等）程序中使用。三、判断题1 .层次模型可以直接表示n : m联系。 （* ）2 .同一个关系的不同元组值可以相同。（* ）3 . SQL属于关系数据库语言。（,）四、综合题1.什么是数据的逻辑结构什么是数据的物理结构（略）2、编写一个函数，把一个以整数作为结点的单链表转换成数组。其中数组长度要根据单链表长度动态建立，并编写主函数验证函数正确性。（略）3 .栈和队列的逻辑结构有何不同链栈和链队列与普通单链表有何不同（略）4 .循环队列是如何实现的其队空和队满的条件各是什么通过在逻辑上将顺序队看做首尾相接的结构，来实现循环队列。5 .二叉树链式存储结构和单链表有何

8、异同点相同点：都是链式存储，都有数据域；不同点：前者有两个指针域，后者只有一个指针域。6 .什么是满二叉树，什么是完全二叉树（略）7 .什么是平均查找长度比较顺序查找和折半查找的优缺点（略）8 .编写一段程序，首先以学生信息为数据元素建立顺序表，其中学生信息包括学号、姓名、籍贯、专业、班级，顺序表按学号有序。程序可接收用户查询请求，其中按学号查询用折半 查找实现，按姓名、籍贯、班级查询用顺序查找实现。按姓名、籍贯、班级查询时可能有多 条满足条件的记录，这些记录都应显示出来。（略）9 .什么是排序处理同样的元素集合时，排序和查找的算法复杂度有无差异，这种差异是如何形成的处理同样的元素集合时，排序

9、和查找的算法复杂度有差异，这是由于，查找算法的主要操作时比较两元素的关键字， 其算法复杂度主要考察比较操作消耗的时间；而排序算法除比较操作外，移动元素也是其主要操作，因此其算法复杂度主要考察比较和移动两种操作消耗的时间。10 .阅读以下算法并回答问题。LinkList mynote(LinkList L)请画出下图的邻接矩阵和邻接表O(解：邻接矩阵:0 111010 10 1110 1110 10 10 1110邻接表：12.已知一棵二叉树的前序遍历的结果序列是ABECDFGHJ中序遍历的结果是 EBCDAFHIG J试写出这棵二叉树的后序遍历结果。解：EDCBIHJGFA13 . 一个线性表

10、为 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 =14 .假定允许每个仓库存放多个零件，每种零件也可在多个仓库中存放，而每个仓库中保存的零件都有库存数量。仓库的属性有：仓

11、库号、面积、电话号码；零件的属性有：零件号、名称、规格、单价。根据上述说明画出E-R图。仓库- n后m 零件解：L(注：上图中各实体、联系均有各自的属性，自行补充。)15 .假定一台机器可以由若干个工人操作，加工若干种零件，某个工人加工某种零件是在一台机器上完成的这道工序，而一个零件需要多道工序才能完成。用E-R图表示机器、零件和工人这三个实体之间的多对多联系。解：巨卜叵 口叵16 .假定有一个客户订货系统，允许一个客户一次 (一张订单)预订多种商品，那么关系模式：订单(订单号、日期、客户编号、客户名、商品编码、数量)属于第几范式为什么解：属于第二范式。因为主属性为订单号，在此关系模式中，不存在部分函数依赖关系，但存在传递函数依赖关系。如：订单号传递函数决定客户名。17 .下列关系模式分别属于第几范式为什么(1) 关系：R(X, Y, Z),函数依赖：XY Z(2) 关系：R(X, Y, Z),函数依赖：Y Z; XZ Y(3) 关系：R(X, Y, Z),函数依赖：Y Z; Y X; X YZ(4)关系：R(X, Y, Z),函数依赖：X Y; X Z(5) 关系：R(W, X, Y, Z),函数依赖：X Z; WX Y解：(1)第三范式(2)第三范式(3)第二范式(4)第三范式(5)第一范式(解此类题的关键， 在于根据题目给出的函数依赖关系，分