




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
一、选择题(单选).关于数据元素,下列描述不正确的是(D)。A.数据元素可以包含多个数据项。B.数据结构的算法大多以数据元素为基本操作单位。C.数据元素一般代表某种现实世界中的对象。D.数据元素必须有一个关键字。.循环链表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.eabcd B.deacbC.dcabe D.cbaed4.循环队列存储在数组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).在单链表中指针p所指的结点后插入新结点s有下列3个步骤:s->data=x(赋值)p->next=ss->next=p->next正确的步骤顺序为(B)。A.①②③ B.③②①C.②①③ D.无正确答案.对于先序遍历和后序遍历结果相同的二叉树为(B)。A.一般二叉树 B.只有根结点的二叉树C.根结点无左孩子的二叉树 D.根结点无右孩子的二叉树.若图的邻接矩阵是对称阵,则此图必然为(B)。A.有向图 B.无向图C.连通图 D.有向图或无向图.关于哈夫曼树,下列描述正确的是(D)。A.一定是二叉排序树 B.是一棵完全二叉树C.是一棵平衡二叉树 D.以上三种说法都不对9.长度为12的按关键字有序的待查找序列,采用顺序存储,若用二分查找,则在等概率情况下,查找成功的ASL是(A)。A.37/12 B.62/13 C.39/12 D.49/12.在数据管理技术的发展过程中,经理了人工管理阶段、文件系统阶段和数据库系统阶段。其中数据独立性最高的阶段是(A)。A.数据库系统 B.文件系统C.人工管理 D.数据项管理.下列有关数据库的描述中,正确的是(C)。A.数据库是一个DBF文件 B.数据库是一个关系C.数据库是一个结构化的数据集合 D.数据库是一组文件.数据库设计中,将E-R图转换成关系数据模型的过程属于(C)。A.需求分析阶段 B.逻辑设计阶段C.概念设计阶段 D.物理设计阶段.将E-R图转换到关系模式时,实体与联系都可以表示成(B)。A.属性 B.关系C.键 D.域二、填空题.衡量算法的两个主要指标是时间复杂度和空间复杂度。.线性表的顺序存储结构通过数组下标来反映数据元素之间的逻辑关系。.链表是采用链式存储结构的线性表。进行插入、删除操作时,使用链表比使用顺序存储结构的效率高。.栈又称为后进先出(线性)表,队列又称为先进先出(线性)表。.二叉树的第h层上最多含有的结点数为 2h-1 。.高度为8的完全二叉树至少有6^个叶子结点。.有向图的邻接矩阵不是 对称阵。.图的广度优先搜索算法中使用了队 (辅助数据结构),以记录正在访问的这一层和上一层的顶点,以便于向下一层访问。.二叉排序树的查找效率与二叉树的 高度有关,在待杳序列全顺序或全逆序情况下查找效率最低。.衡量杳找算法优劣的指标是平均杳找长度(ASL)。.CQ[0]〜CQ[8]为一循环队列,初态front=rear=5,进行下列操作:a,b,c,d入队;a,b出队,e,f,g,h,i,j,k,l,m入队,这时队的头、尾指示器状态为:front=7,rear=6。.在以head为表头指针的带表头结点的单链表和循环链表中,判断链表为空的条件分别为headfnext==NULL和head==head-next.对于一组关键字{41,62,34,67,89,54,76,22,93,8}进行从小到大排序,写出其快速排序第一趟(一个关键字到位为一趟)排序后的序列:8,22,34,41,89,54,76,67.93.62。.二叉排序树的查找一一递归算法:boolFind(BTreeNode*BST,intitem){if(BST==NULL)returnfalse;〃查找失败else{if(item==BST->data){item=BST->data;/查找成功return;}elseif(item<BST->data)returnFind(,item);elsereturnFind(,item);}//if}trueBST->leftBST->right.可以使用SQL命令来操纵数据库,也可将SQL命令嵌入高级语言(如C,Pascal,Java等)程序中使用。三、判断题.层次模型可以直接表示n:m联系。 (*).同一个关系的不同元组值可以相同。(*).SQL属于关系数据库语言。 (V)四、综合题1.什么是数据的逻辑结构?什么是数据的物理结构?(略)2、编写一个函数,把一个以整数作为结点的单链表转换成数组。其中数组长度要根据单链表长度动态建立,并编写主函数验证函数正确性。(略).栈和队列的逻辑结构有何不同?链栈和链队列与普通单链表有何不同?
(略).循环队列是如何实现的?其队空和队满的条件各是什么?通过在逻辑上将顺序队看做首尾相接的结构,来实现循环队列。.二叉树链式存储结构和单链表有何异同点?相同点:都是链式存储,都有数据域;不同点:前者有两个指针域,后者只有一个指针域。.什么是满二叉树,什么是完全二叉树?(略).什么是平均查找长度?比较顺序查找和折半查找的优缺点?(略).编写一段程序,首先以学生信息为数据元素建立顺序表,其中学生信息包括学号、姓名、籍贯、专业、班级,顺序表按学号有序。程序可接收用户查询请求,其中按学号查询用折半查找实现,按姓名、籍贯、班级查询用顺序查找实现。按姓名、籍贯、班级查询时可能有多条满足条件的记录,这些记录都应显示出来。(略).什么是排序?处理同样的元素集合时,排序和查找的算法复杂度有无差异,这种差异是如何形成的?处理同样的元素集合时,排序和查找的算法复杂度有差异,这是由于,查找算法的主要操作时比较两元素的关键字,其算法复杂度主要考察比较操作消耗的时间;而排序算法除比较操作外,移动元素也是其主要操作,因此其算法复杂度主要考察比较和移动两种操作消耗的时间。.阅读以下算法并回答问题。LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){S1:S2:q=L;L=L—>next;p=L;while(p—>next)p=p—>next;p—>next=q;qS1:S2:returnL;)请回答下列问题:(1)说明语句S1的功能;(2)说明语句组S2的功能;(3)设链表表示的线性表为何电,…,an),写出算法执行后的返回值所表示的线性表。解:(1)查询链表的尾结点(2)将第一个结点链接到链表的尾部,作为新的尾结点(3)返回的线性表为(a2,a3,…,an,a1).请画出下图的邻接矩阵和邻接表。解:邻接矩阵:一0111010101110111010101110邻接表:.已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试写出这棵二叉树的后序遍历结果。解:EDCBIHJGFA
A.一个线性表为B=(12,23,45,57,20,3,78,31,15,36),设哈希表空间为H[0]〜H[12],哈希函数为H(key)=keymod13并用线性探测法解决冲突,请画出哈希表,并计算等概率情况下的平均查找长度。A解:哈希表为:TOC\o"1-5"\h\z0123456789 10 11 1278 15 3 57 45 20 31 23 36 121 1 1 1114 1 2 1上面最后一行为比较次数。平均查找长度:ASL=(1+1+1+1+1+1+1+1+4+2)/10=14/10=1.4.假定允许每个仓库存放多个零件,每种零件也可在多个仓库中存放,而每个仓库中保存的零件都有库存数量。仓库的属性有:仓库号、面积、电话号码;零件的属性有:零件号、名称、规格、单价。根据上述说明画出E-R图。仓库一库存J>—ni-零件解:(注:上图中各实体、联系均有各自的属性,自行补充。)解:.假定一台机器可以由若干个工人操作,加工若干种零件,某个工人加工某种零件是在-台机器上完成的这道工序,而一个零件需要多道工序才能完成。用E-R图表示机器、零件和工人这三个实体之间的多对多联系。 ,TA-n/)一ni—机器-n m-零件解:.假定有一个客户订货系统,允许一个客户一次(一张订单)预订多种商品,那么关系模式:订单(订单号、日期、客户编号、客户名、商品编码、数量)属于第几范式?为什么?解:属于第二范式。因为主属性为订单号,在此关系模式中,不存在部分函数依赖关系,但存在传递函数依赖关系。如:订单号传递函数决定客户名。.下列关系模式分别属于第几范式?为什么?关系:R(X,YZ),函数依赖:XY3Z关系:R(X,YZ),函数依赖:Y3Z;XZ3Y关系:R(X,YZ),函数依赖:Y3Z;Y3X;X3YZ
关系:R(X,YZ),函数依赖:X^Y;XfZ关系:R(W,X,YZ),函数依赖:XfZ;WXfY解:(1)第三范式(
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 重庆市人民医院质控标准掌握考核
- 中国喷涂项目创业计划书
- 2025第二人民医院布加综合征诊疗考核
- 忻州市人民医院身体塑形技术考核
- 2025年下半年广东广州市白云区人民政府京溪街道办事处招聘合同制工作人员11人易考易错模拟试题(共500题)试卷后附参考答案
- 鄂尔多斯市人民医院护士绩效管理考核
- AI技术在中学心理健康教育课程中的应用探析
- 北京市人民医院杂交手术技术领导力考核
- 2025年下半年广东广州市国土房管局越秀区分局属下事业单位招考1易考易错模拟试题(共500题)试卷后附参考答案
- 2025年下半年广东工业和化部电信研究院广州智慧城市研究院招考易考易错模拟试题(共500题)试卷后附参考答案
- 油田闲置资产盘活方案(3篇)
- 公司视频发布管理办法
- 西宁市供热管理暂行办法
- 鲈鱼健康养殖技术
- 2025人教版八年级数学课后辅导计划
- 2025年贵州省中考物理试题【含答案、解析】
- 特殊气候条件下施工安全保障措施与应对策略
- 2025年贵州省中考英语真题含答案
- 2025年广东中考数学试卷试题真题及答案详解(精校打印版)
- 箱变基础施工工艺流程
- 监控设备改造方案(3篇)
评论
0/150
提交评论