数据结构综合练习题
—、简答题：
1、简述堆栈和队列两种数据类型的异同点。
2、什么静态查找表和动态查找表。
3、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
4、分析稳定的排序和不稳定的排序方法。
5、图的存储结构有哪些？
6、简述度为2的树与二叉树的区别。
期末考试考上面其中两道简答题
二、画图题《期末考试重点题型，不要寄希望是原题，考题和下面练习题很相似〉
1、请把下图的树转换成二叉树。
2、已知某二叉树先序序列ABDFJGKCEHILM,中序序列BFJDGKAC HELIM,试画出
这棵二叉树。
3、根据给定的连通网图，采用Prim算法思想画出下图的最小生成树。
4、电文中字符A 、B 、C 、D 、E 、F 、G 、H 出现的概率分别为
5%,25%,7%,8%,14%,23%,3%,H%;试设计对应Huffman 树并给出各字符的前 缀编码。
5、如下图表示的树的结构。将此树转换成二叉树
6、根据下图所示的AOE 网，试求解其关键路径。
7、请对下面的无向带权图：
(1)写岀它的邻接矩阵。
(2)按普里姆算法求其最小生成树。
8对于右图所示的树：(1)写出先根遍历得到的结点序列；(2)写出按层遍历得到的结点序列；
三、程序分析写结果：
1、写岀下列程序段的输岀结果(栈的元素类型为char；字符
型)。
Void main()
{
Stack S;
Char x,y;
InitStack(S);
X= Push(S,x); Push(S,,a,); Push(S,y); Pop(S,x); Push(S,'t'); Push(S,x); Pop(S,x); Push(S,,s,); While(! StackEmpty(S)) {Pop(S,y); printf(y); }; Printf(x); } 2、写岀下列程序段的输岀结果(队列的元素类型为char；字 符型)。 Void main() { Queue Q; InitQueue(Q); char x='e；y=C; EnQueue(Q,'h'); EnQueue(Q,,r,); EnQueue(Q,y); DeQueue(Q.x); EnQueue(Q,x); DeQueue(Q.x); EnQueueCQ/a9); while(!QueueEmpty(Q)) { DeQueue(Q,y); printf(y); } printf(x); ) 3、简述以下算法的功能(栈和队列的元素类型均为int)。void algo3(Queue &Q){ Stack S; int d; InitStack(S); while(! QueueEmpty(Q)) { DeQueue (Q,d); Push(S,d); }； while(! StackEmpty (S)) { Pop(S,d); EnQueue (Q,d); 4、比较类试题 比较类试题 一、题型特征 比较是确定事物之间相同点和不同点的思维方法，它为客观、全面地认识事物提供了一个重要途径。高考题中比较类试题的设问方式主要有：比较图中……和……的差异(不同或异同)，分析……和……的共同特点(问题)，说明图示××和××的自然条件和类型的差异等。 二、应试策略（四步审题、三项联系、二定要点及格式是正确解答比较类试题的秘诀所在。） “四步审题”是关键：第一步审比较对象，审准对象可以在很大程度上避免答题时张冠李戴；第二步审比较要求，即审准题意要求找相同点还是不同点，还是异同点都找，或者要求通过比较进一步找原因；第三步审比较考点，如比较A、B 两地的气候类型及特征的异同点，其比较的考点是气候类型及特征，此步骤可避免跑题；第四步审比较角度，审准题目从什么角度、几个角度去比较，此步骤可避免漏掉答题的要点。 “三项联系”是答题依据：首先，联系题中图表和材料，它们是解决比较类问题最直接的依据；其次，联系所学教材知识点，即能迅速地理解题目设置的情境和需要解决的问题，与所学知识建立准确的联系，并从中提取出需要的知识点；最后，联系生活经验和常识，当学生实在想不起所学的教材知识点时，根据题意联系自己的生活经验和常识来答题往往也是很有效的。 “二定”是指根据分值定要点、根据内容定格式。根据分值定要点，要求学生养成要点化答题的习惯，看分给点，只有给足正确的要点，才有可能得足分；根据内容定格式是指采取要点纵列化或者采取列表比较，这要根据答题的内容来定。一般来说，比较异同时列表比较更直观些。 1、图a是世界某区域示意图，图b和图c分别是对应区域的景观和气候资料，据此完成下列问题。 1、有一课程管理系统，有如下特点：一个系可开设多门课程，但一门课只在一个系部开设，一个学生可选修多门课程，每门课可供若干学生选修，一名教师只教一门课程，但一门课程可有几名教师讲授，每个系聘用多名教师，但一个教师只能被一个系所聘用，要求这个课程管理系统能查到任何一个学生某门课程的成绩，以及这个学生的这门课是哪个老师所教的。 （1）请根据以上描述，绘制相应的E-R图，并直接在E-R图上注明实体名、属性、联系类型； （2）将E-R图转换成关系模型，画出相应的数据库模型图，并说明主键和外键。 （3）分析这些关系模式中所包含的函数依赖，根据这些函数依赖，分析相应的关系模式达到了第几范式。对这些关系模式进行规范化。 1、参考答案： 2、设某汽车运输公司数据库中有三个实体集。一是“车队”实体集，属性有车队号、车队名等；二是“车辆”实体集，属性有牌照号、厂家、出厂日期等；三是“司机”实体集，属性有司机编号、姓名、电话等。 车队与司机之间存在“聘用”联系，每个车队可聘用若干司机，但每个司机只能应聘于一个车队，车队聘用司机有“聘用开始时间”和“聘期”两个属性； 车队与车辆之间存在“拥有”联系，每个车队可拥有若干车辆，但每辆车只能属于一个车队； 司机与车辆之间存在着“使用”联系，司机使用车辆有“使用日期”和“公里数”两个属性，每个司机可使用多辆汽车，每辆汽车可被多个司机使用。 （1）请根据以上描述，绘制相应的E-R图，并直接在E-R图上注明实体名、属性、联系类型； （2）将E-R图转换成关系模型，画出相应的数据库模型图，并说明主键和外键。 （3）分析这些关系模式中所包含的函数依赖，根据这些函数依赖，分析相应的关系模式达到了第几范式。对这些关系模式进行规范化。 2、参考答案： 数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出 现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的 第九章相似比较 第一节结构比较 结构比较题型是从推理的形式或推理的方法上比较题干和选项之间的相同或不同，在做该类型题目时，不考虑内容的对错也不考虑题干本身的结构是否正确，只要抽象出题干与选项的推理结构和形式，并对其进行比较就能找到正确答案。 考题的典型问法有：“下面哪项与上述推理结构最相似？”；“哪一项与上文的论证方式是相同的？”；“以下哪项与上述推理的逻辑结构一致？” 1．【2016年真题】 注重对孩子的自然教育，让孩子亲身感受大自然的神奇与美妙，可促进孩子释放天性，激发自身潜能；而缺乏这方面教育的孩子容易变得孤独，道德、情感与认知能力的发展都会受到一定的影响。 以下哪项与以上陈述方式最为类似？（） A．脱离环境保护搞经济发展是“涸泽而渔”，离开经济发展抓环境保护是“缘木求鱼”。 B．只说一种语言的人，首次被诊断出患阿尔茨默症的平均年龄为76岁；说三种语言的人首次被诊断出患阿尔茨海默症的平均年龄约为78岁。 C．老百姓过去“盼温饱”，现在“盼环保”，过去“求生存”，现在“求生态”。 D．注重调查研究，可以让我们掌握第一手资料，闭门造车只能让我们脱离实际。 E．如果孩子完全依赖电子设备来进行学习和生活，将会对环境越来越漠视。 【答案】D 【解析】题干中的陈述方式是先陈述自然教育的优点，再补充陈述缺少自然教育的缺点， 即正面会得到一种结果，反面会得到另外一种结果。D项，先陈述注重调查研究的优点，再陈述不注重调查研究的缺点，与题干最为类似。 2．【2015年真题】 研究人员将角膜感觉神经断裂的兔子分为两组：实验组和对照组。他们给实验组兔子注射一种从土壤霉菌中提取的化合物。3周后检查发现，实验组兔子的角膜感觉神经已经复合；而对照组兔子未注射这种化合物，其角膜感觉神经都没有复合。研究人员由此得出结论：该化合物可以使兔子断裂的角膜感觉神经复合。 以下哪项与上述研究人员得出结论的方式最为类似？（） A．科学家在北极冰川地区的黄雪中发现了细菌，而该地区的寒冷气候与木卫二的冰冷环境有着惊人的相似。所以，木卫二可能存在生命。 B．绿色植物在光照充足的环境下能茁壮成长，而在光照不足的环境下只能缓慢生长。所以，光照有助于绿色植物的生长。 C．一个整数或者是偶数，或者是奇数。0不是奇数，所以，0是偶数。 D．昆虫都有三对足，蜘蛛并非三对足。所以，蜘蛛不是昆虫。 E．年逾花甲的老王戴上老花眼镜可以读书看报，不戴则视力模糊。所以，年龄大的人都要戴老花眼镜。 【答案】B 【解析】题干所用的方法是求异法，B项也是求异法，故答案为B项。A项为类比；C 项为选言证法；D项为演绎推理；E项为例证法。 3．【2011年真题】 一、选择题 1设有关系模式W(C,P,S,G,T,R),其中各属性的含义是:C 课程,P 教师, S 学生,G 成绩,T 时间,R 教室,根据语义有如下数据依赖集: D={C->P ,( S,C )->G , ( T , R)->C , (T , P)-> R,( T,S )->R} 关系模式W的一个关键字是( ) A (S ,C ) B ( T, R) C) (T ,P ) D) (T ,S ) 2 设有关系模式W（C，P，S，G，T，R），其中中各属性的 含义是：C课程，P教师，S学生。G成绩，T时间，R教室，根据主义有如下依据赖集：K={C→P，（S，C）→G，（T，R ）→C，（T，P）→R，（T，S）→R} 关系模式W的规范化程序最高达到（） A 1NF B 2NF C 3NF D BCNF 3规范化理论中分解（）主要消除其中多余的数据相关性。A关系运算 B 内模式 C外模式 D 视图 4现有职工关系W（工号，姓名，工程，定额），其中每一个工号（职工可能有同名）， 每个职工有一个工程，每个工程有一个定额，则关系W已达到（） A 1NF B2NF C3NF D4NF 5现有职工关系W（工号，姓名，工程，定额），其中每一 个职工有一个工号（职工可能有同名），每个职工有一个工程，每个工程有一个定额，则关系W已达到（） A1NF B2NF C3NF D4NF 6规范化理论是关系数据库进行逻辑设计的理论依据,根据这个理论，关系数据库中的关系必须满足：其每一属性都是（） A、互不相关的 B、不可分解的 C、长度可变的 D、互相关联的 7、在一个关系R中，若每个数据项都是不可再分割的，那 么关系R 一定属于（） A、1NF B、2NF C、3NF D、BCNF 8、根所关系数据库规范化理论，关系数据库的关系要满足 1NF，下面“部门”关系中，因（）属性而使它不满足1NF。 A、部门号 B、部门名 C、部门成员 D、 部门总经理 9、设有关系模式R（S，D，M）。其函数依赖集F={S->D， D->M}，则关系R的规范化程序至多达到（） A、1NF B、2NF C、3NF D、BCNF 10、下列关于函数依赖的叙述中，（）是不正确的 A、由X->Y,X->Z,有X->YZ B\由XY->Z,有 X->Z,Y->Z C、由X->Y,WY->Z,有xw->z D、由X->Y,Y->Z,有 上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。 数据结构实验报告(2015级)及答案 《数据结构》实验报告 专业__信息管理学院______ 年级__2015级___________ 学号___ _______ 学生姓名___ _ _______ 指导老师____________ 华中师范大学信息管理系编 I 实验要求 1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。 2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。 3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。 4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。 II 实验内容 实验一线性表 【实验目的】 1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。 3．熟练掌握线性表的综合应用问题。 【实验内容】 1．一个线性表有n个元素（n 的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现；比较两种方法的优劣。 2. 从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3．设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数）实现； ②在主函数中调用创建链表的函数创建一个单链表， 并调用该函数，验证算法的正确性。 LinkedList Exchange（LinkedList HEAD，p）∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 {q=head->next；∥q是工作指针，指向链表中当前待处理结点。 pre=head；∥pre是前驱结点指针，指向q的前驱。 while（q!=null && q!=p）{pre=q；q=q->next；} ∥ 练习题及答案 第一部分：选择题 一、单项选择题 1．DBS是采用了数据库技术的计算机系统。DBS是一个集合体，包含数据库、计算机硬件、软件和 A.系统分析员 B.程序员 C.数据库管理员 D.操作员 2．模型是对现实世界的抽象，在数据库技术中，用模型的概念描述数据库的结构与语义，对现实世界进行抽象。表示实体类型及实体间联系的模型称为 A.数据模型 B.实体模型 C.逻辑模型 D.物理模型 3．关系模型概念中，不含有多余属性的超键称为 A.候选键 B.对键 C.内键 D.主键 4．设R、S为两个关系，R的元数为4，S的元数为5，则与R S等价的操作是 A．σ3<6(R×S) B.σ3<2(R×S） C.σ3>6(R×S) D.σ7<2(R×S) 5．分布式数据库存储概念中，数据分配是指数据在计算机网络各场地上的分配策略，一般有四种，分别是集中式、分割式、全复制式和 A. 任意方式 B.混合式 C.间隔方式 D.主题方式 6．数据库系统中，类是指具有相同的消息，使用相同的方法，具有相同的变量名和 A. 变量值 B. 特征 C. 定义 D. 类型 7．随着计算机应用领域的扩大，第一代、第二代DBS不能适应处理大量的 A.格式化数据 B.网络数据 C.非格式数据 D.海量数据 9．数据库并发控制概念中，使用X封锁的规则称为 A.PS协议 B.PX协议 C.PSC协议 D.两段封锁协议 10.在数据库操作过程中事务处理是一个操作序列，必须具有以下性质：原子性、一致性、隔离性和 A.共享性 B.继承性 C.持久性 D.封装性 11．面向对像模型概念中，类可以有嵌套结构。系统中所有的类组成一个有根的 A.有向无环图 B.有向有环图 C.无向有环图 D.无向无环图 12．在教学管理系统中，有教师关系T（T＃，NAME），学生关系S（S＃，NAME），学生成绩关系S(S＃，NU)。其中T＃表示 题型卷08 判断比较类综合题 考点定位：判断是什么、属于什么、怎么样。名词比较。特征比较。 1. (2015·经典模拟·浙江嘉兴)根据下列材料，完成问题。 西辽河流域地处我国农牧交错带，年降水量约375 mm，灌溉农业较为发达，素有“北方粮仓”之称。 指出该地区农牧界线的空间变化，并据此判断该地区农业土地利用类型面积的变化。 2．(2015·经典模拟·辽宁五校协作体期中考试)阅读甲、乙两座山脉的自然带垂直分布示意图，回答(1)～(3)题。 不同地区的气候、土壤、生物等地理要素，随着地理位置和地势的变化呈现出规律性的演变，从而形成纷繁复杂而又有规律的自然景观。 (1)比较甲图和乙图山脉自然带带谱的主要差异，并判断哪幅图的山脉所处纬度位置较低。 (2)概述甲图中各自然带在山脉南、北坡出现的高度的差异，并说明原因。 (3)乙图中，山脉在海拔4 000以上的南、北坡，坡度基本相同，气温大致相当，但南坡的雪线却低于北坡，说明其原因。 3．(2015·经典模拟·四川遂宁)读英国地形图，完成下列问题。 判断图中A、B两地哪一地区小麦种植业比较发达，并分析原因。 4．(2015·经典模拟·浙江嘉兴)读世界某区域简图，比较该国西部地区降水的南北差异，并从地形、大气环流角度分析其原因。 5．(2014·江苏南京市、盐城市一模)满洲里是中俄最大的贸易口岸。读满洲里口岸贸易产品构成图，回答下列问题。 比较该口岸进出口贸易产品构成的差异，并从产业结构、资源状况方面分析形成差异的原因。 6．(2015·经典模拟·浙江省六校)读我国局部地区≥10℃等积温线分布图，比较包头、唐山两地积温差异。 7．(2015·经典模拟·黑龙江双鸭山)阅读材料，回答问题。 材料一甲河是我国东南沿海的河流，流域内拥有较丰富的水、土地、矿产、生物、旅游等资源。流域内的东南部以三角洲平原、台地、丘陵为主，中部以台地、丘陵为主，西北部则为山地、丘陵。 材料二下图是甲河流域示意图。 XX大学 信息与计算科学专业 2008级《数据结构》集中上机 设计题目：迷宫求解（非递归求解）设计时间：2010-2011学年第一学期 目录 一、实验内容 (2) 二、需求分析 (2) 三、总体设计 (2) （一）存储结构 (2) （二）流程图 (3) 四、详细设计 (3) （一）基本算法解析 (3) （二）为实现算法，需要的象的数据类型 (4) (三)函数的调用关系 (5) （四）算法时间、空间复杂度 (5) 五、代码 (5) 六、运行结果分析 (10) （一）迷宫路径探索成功 (10) （二）迷宫路径未找到的情况 (13) （三）程序的优缺点与改进 (13) 七、参考文献 (14) 八、心得体会 (14) 一、实验内容 任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出。 二、需求分析 1、可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求使用非递归算法。 2、用户可以根据自己的需求进行输入所需的迷宫，其中1表示迷宫的墙壁，0表示迷宫的通路，从而建立迷宫。 3、可以自行输入迷宫的入口和出口坐标。 4、程序执行的命令包括： （1）构造栈函数。其中包括了构造空栈InitStack；压入新数据元素Push；栈顶元素出栈Pop。 （2）构造求迷宫路径函数。其中定义了二维数组maze[M][N]存取迷宫数据；输出找到的通路MazePath。 （3）建立一个迷宫initmaze。其中包括输入迷宫行数列数以及各行各列；加一圈围墙并输出迷宫。 三、总体设计 （一）存储结构： 首先用二维数组存储迷宫数据，迷宫数据由用户输入。 一个以链表结构作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）形式输出，其中（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向（东南西北所用代表数字，自行定义）。 1．从入口出发，顺着某一个方向进行探索，若能走通，继续往前走，否则沿原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到但没能到达出口，则所设置的迷宫没有通路。 迷宫的入口点的下标（a,b），出口点的下标（m,n）。为方便，可在迷宫周围加一周障碍。对于迷宫的任意位置，均可约定有东西南北4个方向可以走通。经过的位置把0变成-1，输出迷宫路径。 2本程序有三个模块; （1）主程序模块 （2）三个模块即其对象，实现栈链表抽象数据类型 （3）迷宫存储迷宫，寻路径，输出迷宫。 数据库原理与应用练习题及参考答案 一、选择题 1.一下关于关系的说法正确的是（ A ） A.一个关系就是一张二维表 B.在关系所对应的二维表中，行对应属性，列对应元组。 C.关系中各属性不允许有相同的域。 D.关系的各属性名必须与对应的域同名。 2.关系数据表的关键字可由（ D ）属性组成。 A.一个 B.两个 C.多个 D.一个或多个 3.进行自然连接运算的两个关系（ A ） A.至少存在一个相同的属性名 B.可不存在任何相同的属性名 C.不可存在个相同的属性名 D.所有属性名必须完全相同 4.概念结构设计是整个数据库设计的关键，它通过对用户需求进行综合、归纳与抽象，形成一个独立于具体DBMS的（ B ）。 A.数据模型 B.概念模型 C.层次模型 D.关系模型 5.Access 2010 数据库具有很多特点，下列叙述中，正确的是（ B ）。 A. Access 2010数据表可以保存多种数据类型，但是不包括多媒体数 B. Access 2010可以通过编写应用程序来操作数据库中的数据 C. Access 不能支持 Internet/Intranet 应用 D. Access 2010 使用切换面板窗体管理数据库对象 6.数据表的基本对象是（ A ） A.表 B.查询 C.报表 D.窗体 7.利用Access 2010 创建数据库文件，其扩展名是（ B ） A.mdb B.accdb C.xlsx D. acc 8.启动Access 2010 后，最先显示的是什么界面（ C ） A.数据库工作界面 B.“打开”窗口 C. Backstage D导航窗格 9.在 Access 数据库对象中，不包括的是（ B ） A.表 B.向导 C.窗体 D.模块 10.表的组成内容包括（ C ） A.查询和字段 B.报表和字段 C.字段和记录 D.记录和窗体 11.在 Access 2010 数据库的表设计视图中，不能进行的操作是（ A ） A.修改字段类型 B.设置索引 C.增加字段 D.删除记录 【通用版】高考地理综合题区域比较类答题模板 考查方式 以两个或两个以上的区域地理环境要素分布图或材料为命题切入点，考查不同区域之间的地理差异、地理特征差异形成的原因、区域可持续发展中的问题及治理措施等。 二、设问形式 常见设问形式有“比较图中……和……的差异(异同)”“分析……和……的共同特点(问题)”“说明图示……和……的自然条件和类型的差异”等。 三、答题思路 “三步比较”回答区域比较类试题 1、细致审题确定比较对象 审比较对象，避免答题时张冠李戴；审比较考点，如比较AB两地气候特征的异同，可避免跑题；审比较要求，即审准题意要求找相同点还是不同点，还是异同点都找，或者要求通过比较找原因；审比较角度，审准题目从什么角度、几个角度去回答，可避免漏掉答题的要点；注意设问的分值，养成要点化答题的习惯，看分给点。 2、确立比较的类型与思维模式 (1)名词比较类：应先搞清名词的含义，包括的内容，针对内容进行分析比较。如：比较两地的气候特征，须知道比较气候类型，气温和降水特点 (2)区域特征比较类：应先对区域进行综合分析，然后根据要求对分析内容有选择性地列举比较。这类试题重在分析，次在比较。所以，区域的综合分析显得尤为重要，区域的综合分析主要从自然地理和人文地理两个方面进行。 3、巧妙比较，简洁作答 三项联系是答题的依据： A、联系题中图表和材料，他们是解决比较类问题最直接的依据 B、联系所学教材知识点，即能迅速理解题目设置的情景和需要解决的问题，与所学知识建立准确的联系，并从中提取需要的知识点 C、联系生活经验和常识，当学生实在想不起来所学教材知识点时，根据题意联系自己的生活经验和常识来答题往往也是有效的 答题模板 实验报告（一） 一、实验目的： 1．掌握VC6.0开发环境下C/C++程序的编辑、编译和运行。 2．通过实验回顾复习C语言中关于结构体、指针等知识的应用。 3．了解学习数据结构的主要方法和课程的主要知识框架。 二、实验环境： 个人电脑、Windows XP、VC6.0或以上版本。 三、实验内容、程序代码、程序测试运行界面 1．设计一个程序，输出所有小于等于n（n为一个大于2的正整数）的素数。要求：（1）每行输出10个素数；（2）尽可能采用较优的算法。 2．编写一个程序，计算任一输入的正整数的各位数字之和，并分析算法的时间复杂度。 3．编写一个程序，判断一个字符串是否为“回文”（顺读和倒读都一样的字符串称为“回文”），并分析算法的时间复杂度。 四、心得体会与建议 实验报告（二） 一、实验目的： 1．熟练掌握线性表的顺序存储结构的概念及各种基本操作的C语言实现。 2．熟练掌握线性表的链式存储结构中的单链表的概念及各种基本操作的C 语言实现。 3．了解双向链表及循环链表的基本操作。 二、实验环境： 个人电脑、Windows XP、VC6.0或以上版本。 三、实验内容、程序代码、程序测试运行界面 1．编写一个程序，实现顺序表的各种基本运算（假设顺序表的元素类型为char），并在此基础上设计一个程序完成如下功能： （1）初始化顺序表L； （2）采用尾插法依次插入元素a，b，c，d，e； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素a的位置； （8）在第4个位置上插入元素f； （9）输出顺序表L； （10）删除L的第3个元素； （11）输出顺序表L； （12）释放顺序表L。 程序代码如下： 1.设有关系模式 R(A, B, C, D,E)，其上的函数依赖集 F={A→BC, CD→E, B→D, E→A} 试计算 ①A+、B+； ②求出 R的所有候选码（3分） 2. 要建立关于系、学生、班级等信息的一个关系数据库。规定：一个系有若干专业、每个专业每年只招一个班，每个班有若干学生，一个系的学生住在同一个宿舍区，一个系只有一个系名，一个系名也只给一个系用。 描述学生的属性有：学号、姓名、出生年月、系名、班号、宿舍区。 描述班级的属性有：班号、专业名、系名、人数、入校年份。 描述系的属性有：系号、系名、系办公室地点、人数。 试给出上述数据库的关系模式；写出每个关系的最小依赖集（即基本的函数依赖集，不是导出的函数依赖）；指出是否存在传递函数依赖；对于函数依赖左部是多属性的情况，讨论其函数依赖是完全函数依赖还是部分函数依赖，指出各关系的候选键、外部关系键，进行范式判断。 3.某医院病房计算机管理中需要如下信息： 科室：科名，科地址，科电话，医生姓名 病房：病房号，床位号，所属科室名 医生：姓名，职称，所属科室名，年龄，工作证号 病人：病历号，姓名，性别，诊断，主管医生，病房号 其中，一个科室有多个病房、多个医生，一个病房只能属于一个科室，一个医生只属于一个科室，但是可以负责多个病人的诊治，一个病人的主管医生只有一个。 完成如下设计 （1）请根据需求信息设计该系统的E-R图； （2）请将E-R图转换为关系模式； （3）指出转换结果中每个关系模式的主码（用直下划线）和外码（用曲下划线）。 4. 商品销售系统 假定一个销售公司的业务涉及如下基本实体： (1)职工：职工号、姓名、性别电话、住址； (2)商品：商品编号、商品名称、型号、供货商、进货单价、库存数量、销售 单价； (3)供货商：制造商编号、制造商名称、联系电话、通信地址； (4)客户：客户编号、客户名称、联系电话、通信地址。 《比较文学》练习测试题库 一、填空题： 1、比较文学的研究范围，一是；二是 2、真正意义上的比较文学产生于世纪末。它的出现与当时整个社会的经济、文化环境有着密切关系。 3、从比较文学的眼光看，我国文学的发展历史是一个不断与世界各国文学、、、的历史。 4、法国学者基亚认为比较文学实际上是史。 5、季羡林先生说过，从全世界文学艺术的历史来看，文艺理论真能持之有故，言之成理，确有创见而又能自成体系的只有三个地方，一个是，一个是，一个是从古代希腊、罗马一直到今天欧洲国家所在的广大地区。 6、在《长篇诗在中国何以不发达》一文中以一种宏观的视野，从传统文化、民族性格等方面探讨了缺类问题。 7、比较文学就是要突破各种学术研究的界限，“打通”整个文化领域，使文学研究进入了性研究的新阶段。 8、从积极的意义上看，东西方文化的沟通常常是在中实现的。 9、置身于接受者的立场，探讨作家作品的源流，分析它们所受到的各国文学的影响，这一研究被称为。 10、比较诗学是一门从跨文化的角度对、的比较研究。 11、比较文学是一门跨越民族，，文化和的文学研究。 12、比较文学要求在研究中国文学时，应以为背景，以为参照系统，认识和评价自己。 13、丹纳《艺术哲学》中提出的制约文学发展的三大要素中与达尔文进化论的“外界条件”相对应的是和。 14、文学理论对音乐的借鉴体现在对音乐和的吸收上。 15、在西方历史上，古希腊哲学家首创的哲学专题论文引起了哲学和文学的分化。 16、钱钟书先生曾倡导法，它不仅表现在文学范围内地域、时代、文类诸界限的打破，而且推向整个文化领域，体现为各个学科门类的汇通。 17、是比较文学研究的重点之一。 18、1848年，马克思、恩格斯在一书中使用了“世界文学”这个概念。 19、18世纪下半叶和19世纪初叶席卷全欧的文学思潮为比较文学的诞生准备了文学土壤。 试题（一） 一、填空题 1．在关系模式R中，能函数决定所有属性的的属性组，称为模式R的候选码。2．当合并局部E-R图时可能出现的冲突有属性冲突，命名冲突和结构冲突。3．设计概念模型通常采用自底向上的方法。 4．事务是数据库操作的逻辑工作单位，事务中的操作要么都做，要么都不做，是指它的原子性特性。 5．恢复技术的基本原理是建立数据冗余，最常用的技术是数据转储和登记日志文件。6．数据库的并发操作引发的问题包括丢失修改、读脏数据和不可重复读。常用的并发控制的方法是封锁。 二、综合题 1．设有关系模型R(U,F)，其中U={ABCDEG},F={BG→C,BD→E,DG→C,DAG→CB,AG→B,B→D} (1)求出关系模式的候选码。 (2)此关系模式最高属于哪级范式。 答案：（1）AG AG={AGBDCE} （2）2NF 3．学校有若干个系，每个系有各自的系号、系名和系主任；每个系有若干名教师和学生，教师有教师号、教师名和职称属性，每个教师可以担任若干门课程，一门课程只能由一位教师讲授，课程有课程号、课程名和学分，并参加多项项目，一个项目有多人合作，且责任轻重有个排名，项目有项目号、名称和负责人；学生有学号、姓名、年龄、性别，每个学生可以同时选修多门课程，选修有分数。 （1）请设计此学校的教学管理的E-R模型。（第一章试题中已做） （2）将E-R模型转换为关系模型。 答案： （1） （2）系（系号，系名，系主任） 教师（教师号，教师名，职称，系号） 学生（学号，姓名，年龄，性别，系号） 项目（项目号，名称，负责人） 课程（课号，课程名，学分，教师号） 选修（课号，学号，分数） 负责（教师号，项目号，排名） 试题（二） 一、填空题 1．数据库的三级模式是指内模式、___________________、外模式。（模式） 2．____________________是现实世界在人们头脑中的反映，是对客观事物及其联系的一种抽象描述。（概念世界） 3．数据模型由三部分组成：模型结构、数据操作、__________________。（完整性规则）4．一种数据模型的特点是：有且仅有一个根结点，根结点没有父结点；其它结点有且仅有一个父结点。则这种数据模型是__________________________。（层次模型） 5．能唯一标识一个元组的属性或属性组成为________________。（候选码） 7. SQL语言一种标准的数据库语言, 包括数据查询、数据定义、数据操纵、___________四部分功能。（数据控制） 8. 视图是从其它________________________或视图导出的表。（基本表） 姓名： 学号： 班级： 2010年12月15日 实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、； 2、以线性表的各种操作（建立、插入、删除、遍历等）的实现为重点； 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现； 4、通过本章实验帮助学生加深对C语言的使用（特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作）。 【实验内容】 约瑟夫问题的实现：n只猴子要选猴王，所有的猴子按1,2，…，n编号围坐一圈，从第一号开始按1,2…，m报数，凡报到m号的猴子退出圈外，如此次循环报数，知道圈内剩下一只猴子时，这个猴子就是猴王。编写一个程序实现上述过程，n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成，严禁抄袭。 3、上的实验报告有如下部分组成： ①实验名称 ②实验目的 ③实验内容：问题描述：数据描述：算法描述：程序清单：测试数据 算法： #include 【试题研究】高考地理压轴突破之综合题答题建模——比较类 一、设问形式 比较是确定事物之间相同点和不同点的思维方法，它为客观、全面地认识事物提供了一个重要途径。高考题中比较类试题的设问方式主要有：比较图中……和……的差异（不同或异同），分析……和……的共同特点（问题），说明图示的自然条件和类型的差异等。 例题1 甲、乙两国历史悠久，读下图并结合所学知识回答问题。 （1）比较图中a、b两河的水文特征； （2）①②两城市分别为甲、乙两国的首都，对比分析其不同的区位条件。 图中信息：甲图：国界；未定国界；首都；河流；沙漠；纬度；经度； 乙图：国界；首都；河流；海岸线；纬度；经度； 设问立意：此题要求对比分析a、b两河的水文特征和两首都的区位条件。由甲、乙两图的经纬度和河流分布可以判断出甲国为巴基斯坦，其首都为伊斯兰堡；乙国为孟加拉国，其首都为达卡。a河是印度河，b河是恒河。 思维线路：第（1）题，河流的水文特征应从流量、汛期（径流的季节变化）、含沙量、结冰期和水能蕴藏量等方面回答。 第（2）题，城市区位条件比较要结合当地情况，从气候、地形、水文、资源、交通等多个方面进行分析。 参考答案：（1）相同点：ab两河的汛期都出现在夏季，都没有结冰期；不同点：a河流流量小， 含沙量大；b河流量大，上游水能丰富。 （2）①城位于内陆高原地区，气候凉爽，交通便利；②城位于河口三角洲，地形平坦，靠近河流，全年高温，有旱、雨季。 二、思维建模 比较类问题的四步审题是关键： 第一步审比较对象，审准对象可以在很大程度上避免答题时张冠李戴； 第二步审比较要求，即审准题意要求找相同点还是不同点，还是异同点都找，或者要求通过比较进一步找原因； 第三步审比较考点，如比较A、B两地的气候类型及特征的异同点，其比较的考点是气候类型及特征，此步骤可避免跑题； 第四步审比较角度，审准题目是从什么角度、几个角度去比较，此步骤可避免漏掉答题的要点。 另外要根据分值定要点、根据内容定格式。根据分值定要点，要求学生养成要点化答题的习惯，看分给点，只有给足正确的要点，才有可能得足分；根据内容定格式是指采取要点纵列比较，这要根据答题的内容来定。一般来说，比较异同时列表比较更直观些。 比较类设问一般有两类： 1、名词比较类。 其基本思维模式是：首先搞清名词的含义，包括的主要内容，然后针对内容进行分析、对比。 2、区域特征比较类 其基本思维模式是：先对区域进行综合分析，然后根据要求对分析内容有选择性地列举比较。这类试题重在分析，次在比较。所以，区域的综合分析显得尤为重要；区域的综合分析主要从自然和人文地理两方面进行。 模板典例 地理要素比较要素 华北水利水电大学数据结构实验报告 2017～2018学年第二学期2017级计算机科学与技术（专升本）专业班级：学号：姓名： 实验一线性表及其应用 一、实验目的： 1．掌握用C/C++语言调试程序的基本方法。 2．掌握线性表的基本运算，如插入、删除等。 二、实验内容： 1．编写一个程序，实现顺序表的各种基本运算，在此基础上完成如下功能： （1）初始化顺序表L。 （2）依次在顺序表L中插入元素a、b、c、e。 （3）输出顺序表L。 （4）输出顺序表L的长度。 （5）输出顺序表L的第3个元素。 （6）输出元素a的位置。 （7）在第4个元素之前插入元素f。 （8）输出顺序表L。 （9）删除第3个元素。 （10）输出顺序表L。 2．编写一个程序，实现以下功能，L1=（x1，x2，…，x n），L2=(y1，y2，…，y m)，它们是两个线性表（L1和L2中的值都不重复），采用带头结点的单链表存储，设计一个算法合并L1和L2，结果存放在线性表L3中，要求如下： L3=(x1，y1，x2，y2，…，x m，y m，x m+1，…，x n) 当m n时 L3=(x1，y1，x2，y2，…，x n，y n，y n+1，…，y m) 当m>n时 L3仍采用单链表存储，算法的空间复杂度为O（1）。 （1）建立两个单链表L1和L2并输出。 （2）将合并L1和L2为L3。 （3）输出单链表L3。 三、实验要求： 1．完成程序设计并上机调试通过。 2．撰写实验报告，提供实验结果和数据。 3．写出算法设计小结和心得。 四、程序源代码： 五、程序运行情况（采用截图方式给出运行结果） 六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等） 注：内容一律使用宋体五号字，单倍行间距 2019年天津公务员考试：巧解申论“比较型” 综合分析题 2019年天津公务员考试：巧解申论比较型综合分析题。综合分析题可以说是申论笔试中的必考题型，也是广大考生难易把握的题目。 一、何为比较型综合分析题 所谓比较型综合分析题，指的是对于两种不同做法、观点的对比分析，例如比较中美两国教育方式的异同、分析F市T 市垃圾收费制度的不同、对两地农村土地政策进行评析。命题人往往从一个相同主题下，对于不同做法和不同观点进行题目命制，需要考生对不同的做法、不同的观点有一个明确的认知和对比，进而能够进一步的分析问题、得出结论。 二、比较型综合分析题的基本作答思路 第一步：概括比较对象。概括对象从数量来说一般是两者，需要用简练的语言对两者的不同做法或观点进行提炼。 第二步：比较相同不同。详细梳理材料，比较两者在具体做法，例如动机、手段、结果;核心思想，例如原因、影响、结论等方面的相同要点和不同要点。 第三步：作出最后结论。总分总结构的综合分析题一般结尾都需要落实观点，也就是针对材料中的问题谈谈对策。对策要有针对性、可行性和操作性。 三、通过真题进行完整演示 【2015年江苏公务员考试真题】 给定资料中描述了农村政策实施过程中的一些事例，请对这些事例进行评析。(15分)。 要求：分析透彻，观点正确。篇幅不超过250字。 参考答案： (概括比较对象)事例分别为：盛光农业园区流转农民土地，分租出去种草莓;X市新园区圈地发展生态酒店农家乐，让土地大面积撂荒，抬高土地租金。 (比较相同不同)盛光农业园区的做法值得鼓励。其为出租户建棚、通水电、提供技术支持，带动农民种草莓，不仅增加了农民收入，还解决了部分剩余劳动力。X市新园区的做法应该禁止。其目的不是务农，而是跑马圈地，虽然提高了农民收入，但既违背了国家政策，又破坏了土地流转市场秩序。 (作出最后结论)农村土地经营权流转，要坚持最严格的耕地保护制度，切实保护基本农田。政府应加强规范引导和用途管制，使其有序流转。 综合分析题的本质就是在归纳概括材料要点的基础上加一点逻辑，这个逻辑一般是指总分总、亮明观点-分析论证-得出结论的作答思路。与此同时，各位考生在掌握了比较型综合分析作答框架的基础上，也不要忽视解释型、关系型等综合分析题的复习。4、比较类试题
数据库设计综合练习题及答案
数据结构课程实验指导书
管理类联考综合能力考试历年真题与典型题详解—逻辑分册-相似比较(圣才出品)
数据库练习题
计10--数据结构专题实验rev2
数据结构实验报告(2015级)及答案
(完整版)数据库综合练习题及答案
【推荐】新课标2016年高考地理复习试题：题型卷08 判断比较类综合题 Word版含答案
数据结构集中上机实验报告
数据库原理及应用 练习题及参考答案
【通用版】高考地理综合题 区域比较类 答题模板(含练习题及答案)
《数据结构》2012级实验报告模板..
数据库综合题习题
比较文学练习题库参考答案
数据库综合模拟试题
数据结构实验报告
(试题研究)高考地理 压轴突破综合题答题建模 比较类
《数据结构》实验一
天津公务员考试：巧解申论“比较型”综合分析题.doc
相关主题
文本预览