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

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

2、C. d c a b eD. c b a e d 4.循环队列存储在数组 A0.m中，则入队时的 队尾指针操作为（D）。A. rear=rear+1 rear=（rea 叶1）%（m-1）C. rear=（rea 叶1）%mB.D.rear=（rea 叶1）%（m+1） p->next=s s->next=p->next正确的步骤顺序为（A.C.B ）。B.D.无正确答案5. 在单链表中指针p所指的结点后插入新结点s 有下列3个步骤： s->data=x （赋值）6. 对于先序遍历和后序遍历结果相同的二叉树 为（B ）。A. 一般二叉树B.只有根结点的二叉树C.根结点无

3、左孩子的二叉树D.根结点无右孩子的二叉树7. 若图的邻接矩阵是对称阵，则此图必然为（B ）。A.有向图B.无向图C.连通图D.有向图或无向图8. 关于哈夫曼树，下列描述正确的是（D ）。A. 一定是二叉排序树 完全二叉树C.是一棵平衡二叉树 种说法都不对B.是一棵D.以上三9. 长度为12的按关键字有序的待查找序列，米 用顺序存储，若用二分查找，则在等概率情况下， 查找成功的ASL是（A ）。A. 37/12B. 62/13C.39/12D. 49/1210. 在数据管理技术的发展过程中，经理了人工 管理阶段、文件系统阶段和数据库系统阶段。其 中数据独立性最高的阶段是（A ）oA.数据库系统B

4、.文件系统C.人工管理D.数据项管11.下列有关数据库的描述中，正确的是（C）A.数据库是一个DBF文件 库是一个关系C.数据库是一个结构化的数据集合 库是一组文件B.数据D.数据12.数据库设计中，将 模型的过程属于（C）。E-R图转换成关系数据A.需求分析阶段 阶段B.逻辑设计C.概念设计阶段 阶段D.物理设计13.将E-R图转换到关系模式时， 可以表示成（B ）。实体与联系都A.属性B.关系C.键D.域二、填空题1. 衡量算法的两个主要指标是 时间复杂度 和空间复杂度2. 线性表的顺序存储结构通过数组下标 来反映数据元素之间的逻辑关系。3. 链表是采用链式存储结构的线性表。进行 _插 入

5、_、删除操作时，使用链表比使用顺序存储 结构的效率高。4. 栈又称为 后讲先出 （线性）表，队列又称为先进先岀（线性）表。5. 二叉树的第 h层上最多含有的结点数为2h-1 。6. 高度为8的完全二叉树至少有64个叶子结 点。7. 有向图的邻接矩阵对称阵。8. 图的广度优先搜索算法中使用了 队 （辅助数据结构），以记录正在访问的这一层和上一层的顶点，以便于向下一层访问9. 二叉排序树的查找效率与二叉树的高度有关，在待查序列全顺序或全逆序 情况下查 找效率最低。10. 衡量查找算法优劣的指标是平均杳找长度(ASL)。11. CQOCQ8为一循环 队列，初态front=rear=5，进行下列操作：

6、 a, b, c, d 入队； a, b出队，e, f, g, h, i, j, k, l, m入队，这时队的头、 尾指示器状态为：front =7, rear =6。12. 在以head为表头指针的带表头结点的单链 表和循环链表中，判断链表为空的条件分别为 headf 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. 二叉排序树的查

7、找一一递归算法: bool F in d(BTreeNode* BST, i nt item)if (BST=NULL) return false; / 查找失败 else if (item=BST->data) item=BS>data; 查找成功 return ;else if(item<BST->returnFind(,item);elsereturnFind(,item);true BST->leftBST->right15. 可以使用SQL命令来操纵数据库，也可将SQL命令嵌入高级语言（如 C, Pascal, Java 等）程序中使用。三、判断题

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

9、相同点：都是链式存储，都有数据域； 不同点：前者有两个指针域，后者只有一个指针 域。6（略）么是满二叉树'什么是完全二叉树?查找么蠶均查找长度？比较顺序查找和折半 （略）贯、写业段级丿Hi、元素籍收用户查询请求；顺序表按号查询用折半序找实现，按姓名、籍贯、班级查询用顺序查找实现。 按姓名、籍贯、班级查询时可能有多条满足条件 的记录，这些记录都应显示出来。(略)9. 生么是排序?_处理同样的元素集合时排序/ 和查找的算法复杂度有无差异，这种差异是如何 形成的？处理同样的元素集合时，排序和查找的算法复杂 度有差异，这是由于，查找算法的主要操作时比 较两元素的关键字，其算法复杂度主要考察比较

10、 操作消耗的时间；而排序算法除比较操作外，移 动元素也是其主要操作，因此其算法复杂度主要 考察比较和移动两种操作消耗的时间。10. 阅读以下算法并回答问题。Lin kList myno te(L in kList L)/L是不带头结点的单链表的头指针if(L&&L-> next)S1:>n ext;S2 :>next=NULL ;p >next=q ; qq=L ; L=L >next; p=L ; while(p >next) p=p return请回答下列问题：(1) 说明语句S1的功能；(2) 说明语句组S2的功能；(3 )设链表表示的

11、线性表为 (別,律圣,an)，写出算法执行后的返回值所表示 的线性表。解：(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部， 作为新的尾结点(3)返回的线性表为(a2,a3,an,a1)11.请画出下图的邻接矩阵和邻接表解：邻接矩阵：邻接表：0 111010 10 1110 1110 10 10 111012.已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ EBCDAFHIGJ 结果。，试写出序棵二叉树的后序遍历是解: EDCBIHJGFA13. 一个线性表为 B= (12, 23, 45, 57, 20, 3, 78, 31, 15, 36),设哈希表空间为 H0H12,

12、哈希函数为H (key) = key mod 13并用线性探 测法解决冲突，请画出哈希表，并计算等概率情 况下的平均查找长度。解：哈希表为：0123456789 10 11 1278153574520312336121111114121上面最后一行为比较次数。平均查找长度：ASL=( 1+1+1+1+1+1+1+1+4+2)/10 = 14/10 = 1.414. 假定允许每个仓库存放多个零件，每种零件 也可在多个仓库中存放，而每个仓库中保存的零 件都有库存数量。仓库的属性有：仓库号、面积、 电话号码；零件的属性有：零件号、名称、规格、 单价。根据上述说明画出 E-R图。（注：上图中各实体、联

13、系均有各自的属性，自 行补充。）15. 假定一台机器可以由若干个工人操作，加工 若干种零件，某个工人加工某种零件是在一台机 器上完成的这道工序，而一个零件需要多道工序 才能完成。用E-R图表示机器、零件和工人这 三个实体之间的多对多联系。16. 假定有一个客户订货系统，允许一个客户一 次（一张订单）预订多种商品，那么关系模式： 订单（订单号、日期、客户编号、客户名、商品 编码、数量）属于第几范式？为什么？ 解：属于第二范式。因为主属性为订单号，在此 关系模式中，不存在部分函数依赖关系，但存在 传递函数依赖关系。女口：订单号传递函数决定客 户名。17. 下列关系模式分别属于第几范式？为什么？(1)关系：R(X, Y, Z)，函数依赖：XY Z(2)关系：R(X, Y, Z)，函数依赖：丫 乙XZY(3)关系：R(X, Y, Z)，函数依赖：丫 乙YX; XYZ(4)关系：R(X, Y, Z)，函数依赖：X Y;XZ(5)关系：R(W, X, Y, Z)，函数依赖：X Z;WX Y解：(1)第三范式(2) 第三范式(3) 第二范式(4) 第三范式(5) 第一范式