下载文档原格式
湖南大学考研真题,湖南大学研究生入学考试真题湖南大学马克思主义学院西方哲学史2004——2006，2008，2010马克思主义哲学原理2008,2010政治学原理2006，2008中国共产党思想政治工作史论2006，2008自然辩证法原理2000科学技术史2005岳麓书院西方哲学史2004——2006，2008,2010中国哲学史2008教育学专业基础综合（全国统）2007——2009历史学专业基础（全国统考试卷）2007——2009中国思想史2000经济与贸易学院经济学原理2003——2006，2008——2010西方经济学2001——2003经济学2000——2001经济学综合（含微观经济学、宏观经济学）2005——2010经济学综合（含宏观经济学、财政学）2006数据结构2002——2004，2006，2008数据结构与PASCAL 2000——2001计算机组成与体系结构2006，2008计算机组成原理2001管理学与管理系统工程2001管理学原理（管理科学与工程、工商管理专业）2002——2006，经营管理与市场营销2003经营决策和市场营销2001国际贸易理论与实务2001国际贸易学2001高等代数2002——2010数学分析1999——2010环境工程微生物学2001——2008金融学院金融学基础（联考）2002——2010经济学2000——2001经济学原理2003——2006，2008——2010西方经济学2001——2003会计学院经济学综合（含微观经济学、宏观经济学）2005——2010 经济学综合（含宏观经济学、财政学）2006中级财务会计学2008——2010财务会计学2007财务会计与财务管理2003——2004管理学综合（含管理学原理、财务会计学）2005（西方经济学2001——2003经济学2000——2001经济学原理2003——2006，2008——2010统计学院经济学综合（含微观经济学、宏观经济学）2005——2010 经济学综合（含宏观经济学、财政学）2006统计学2001，2003——2005，2008——2010西方经济学2001——2003经济学2000——2001经济学原理2003——2006，2008——2010高等代数2002——2010数学分析1999——2010数据结构2002——2004，2006，2008数据结构与PASCAL 2000——2001计算机组成与体系结构2006，2008计算机组成原理2001管理学与管理系统工程2001管理学原理（管理科学与工程、工商管理专业）2002——2006，2008——2010法学院专业综合一（含民法、刑法）2005——2010专业综合二（含法理学、宪法学）2005——2010综合考试（宪法学与行政法学专业）2004综合考试（国际法学专业）2004综合考试（法学理论专业）2004综合考试（刑法学、经济法学、环境与资源保护法学专业）2004 法学理论2004法学综合考试（民商法学专业）2003法学综合考试（刑法学、经济法学专业）2003国际经济法2004经济法学2003——2004民法学2002，2004民商法2003商法学2002宪法2004刑法学2002——2004中国环境法2004政治与公共管理学院政治学原理2006，2008,2010西方政治思想2008管理学原理（公共管理专业）2006——2010公共行政学2005——2010行政管理学2004政府经济学2004综合考试（行政管理专业）2004物理与微电子科学学院量子力学2004——2005，2008——2010普通物理2004——2005，2008——2010电子技术基础1999——2000，2002——2006，2008——2010 电子技术基础（818物）2010物理化学（理）2000——2010物理化学（工）2000 2009 2010有机化学（理）2000——2010材料科学基础2006，2008——2010材料物理化学2008半导体物理2008细胞生物学2004——2005，2007——2008生物化学2004——2005，2007——2009教育学专业基础综合（全国统）2007——2009 教育科学研究院教育学专业基础综合（全国统）2007——2009 管理学原理（教育经济与管理专业）2004管理学原理（公共管理专业）2006——2010 教育技术概论2004——2005教育学2003——2008体育学院体育学基础综合2008运动训练学2006中国语言文学学院语言学概论与写作2007——2010现代汉语2007——2010文学理论与写作2006，2008中外文学史2006，2008中国古代文学史2005中国现当代文学史2005专业基础综合（中国古代文学专业）2004——2005比较文学与外国文学2005外国语学院二外日语2002——2010二外法语2001，2003——2004，2008——2010二外德语2001，2004，2008——2010二外俄语2008基础英语（含词汇、语法、阅读、写作）2001——2010英语语言文学专业基础(含英语语言学基础、英美文学基础知识、英语国家概况、英汉互译)2007——2010专业基础综合课2004——2005专业英语2002——2003，2006语言学基础（语言学基础知识）2004——2010二外英语2000，2008基础日语2008日本语言文学专业基础2008小论文(日)2000读解与日汉互译2000新闻与传播学院新闻传播史论2004——2005，2008——2010新闻传播实务2004——2005，2008——2010大众传播理论（B）2005传播学理论2007A设计艺术学院设计艺术史论2008——2010专业设计2008——2010设计史及其理论2003——2006设计基础2006（2006有评分标准）产品设计基础2003——2005环境艺术表现技法2003，2005——2006建筑史1997——2006（2006有答案）[注：1997-2001年称“建筑历史”，其中1998年共2页，缺第2页]数学与计量经济学院高等代数2002——2010数学分析1999——2010化学化工学院物理化学（理）2000——2010物理化学（工）20002009高分子化学2008有机化学（理）2000——2010有机化学（药）2008——2010药学生化2008无机化学2001无机化学（工）2000无机化学（理）2000分析化学（含仪分）2000——2001化工原理2000——2001材料物理化学2008生命科学与技术研究院细胞生物学2004——2005，2007——2010 生物化学2004——2005，2007——2010 物理化学（理）2000——2009物理化学（工）20002009有机化学（理）2000——2010无机化学2001无机化学（工）2000无机化学（理）2000分析化学（含仪分）2000——2001化工原理2000——2001材料物理化学2008环境科学与工程学院环工原理2001，2004——2008环境毒理学2004——2008环境工程微生物学2001——2008环境毒理学与工程微生物学2009环境化学2001——2003，2005大气污染控制工程2001水污染控制工程2001力学与航空航天学院材料力学2002——2010结构力学1997——2011流体力学1999——2010机械原理1999——2006，2008——2010水分析化学与微生物学2008机械控制工程基础2001——2003控制工程基础2005机械与汽车工程学院机械原理1999——2006，2008——2010机械控制工程基础2001——2003控制工程基础2005（复试试题）微机原理及应用2003——2010微机原理（机械电子工程）2000——2001电路1999——2009电子技术基础1999——2000，2002——2006，2008——2010数据结构2002——2004，2006，2008数据结构与PASCAL 2000——2001计算机组成与体系结构2006，2008计算机组成原理2001自动控制原理1998——2000结构力学1997——2010流体力学1999——2010高等代数2002——2009数学分析1999——2009材料力学2002——2009工程热力学2008——2010水分析化学与微生物学2008电气与信息工程学院微机原理及应用2003——2010微机原理（机械电子工程）2000——2001电路1999——2011信号与系统2000，2002——2003，2006——2009电子技术基础1999——2000，2002——2006，2008——2010 电子技术基础2010（物）自动控制原理1998——2000智能仪器2008通信专业综合课2004——2005材料科学与工程学院结构力学1997——2010流体力学1999——2010材料力学2002——2010材料科学基础2006，2008——2009材料物理化学2008环境工程微生物学2001——2008）水分析化学与微生物学2008机械原理1999——2006，2008——2010机械控制工程基础2001——2003控制工程基础2005（复试试题）物理化学（理）2000——2011物理化学（工）20002009计算机与通信学院信号与系统2000，2002——2003，2006——2010 电路1999——2011数字电路与逻辑设计2008——2010半导体物理2008微机原理及应用2003——2010微机原理（机械电子工程）2000——2001电子技术基础1999——2000，2002——2006，2008——2010电子技术基础2010（物）数据结构2002——2004，2006，2008数据结构与PASCAL 2000——2001计算机组成与体系结构2006，2008计算机组成原理2001操作系统2001离散数学2001计算机专业综合课（含C语言、数据结构、离散数学、计算机组成原理）2004——2005通信专业综合课2004——2005高等代数2002——2010数学分析1999——2010软件学院数据结构2002——2004，2006，2008数据结构与PASCAL 2000——2001软件工程2008半导体物理2008计算机组成与体系结构2006，2008计算机组成原理2001操作系统2001计算机专业综合课2004——2005数字电路与逻辑设计2008——2009离散数学2001高等代数2002——2009数学分析1999——2009）信号与系统2000，2002——2003，2006——2009微机原理及应用2003——2009微机原理（机械电子工程）2000——2001电路1999——2009电子技术基础1999——2000，2002——2006，2008——2009电子技术基础2010（物）建筑学院建筑设计1998——2002，2005——2008，2010建筑学基础2010建筑构造1997——2004建筑知识综合（建筑历史与建筑构造）2005——2006，2008建筑史1997——2006（2006有答案）[注：1997-2001年称“建筑历史”，其中1998年共2页，缺第2页]土木工程学院结构力学1997——2010水分析化学与微生物学2008流体力学1999——2010（交通工程学2008——2010混凝土结构2003——2005桥梁工程2003——2005工商管理学院管理学原理（管理科学与工程、工商管理专业）2002——2006，2008——2010管理学与管理系统工程2001经营管理与市场营销2003经营决策和市场营销2001运筹学与统计学2000——2001生物医学工程中心微机原理及应用2003——2010微机原理（机械电子工程）2000——2001材料力学2002——2010细胞生物学2004——2005，2007——2008,2010生物化学2004——2005，2007——2010信号与系统2000，2002——2003，2006——2010数据结构2002——2004，2006，2008 数据结构与PASCAL 2000——2001计算机组成与体系结构2006，2008计算机组成原理2001操作系统2001计算机专业综合课2004——2005高等代数2002——2010数学分析1999——2010物理化学（理）2000——2010物理化学（工）20002009有机化学（理）2000——2010材料物理化学2008高分子化学2008。
湖南大学考研资料01-05数据结构真题2002 年招收攻读硕士学位研究生入学考试命题专用纸招生专业:计算机科学与应用技术考试科目:数据结构试题编号:418注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效)－、单选题（每小题2分，共20分）1.在一个具有n个结点的有序单链表中插入一个新的结点使得单链表仍然有序的时间复杂度为A.O(logn)B.O(1)C.O(n2)D.O(n)2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间。
A.单向链表B.双向链表C.单循环链表D.顺序表3.用单链表表示的链式队列的队头在链表的位置。
A.链头B.链尾C.链中4.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用顺序实现编号。
A.前序遍历B.中序遍历C.后序遍历D.层序遍历5.己知一算术表达式的中缀形式为A+ B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为。
A.-A+B*C/DEB.-A+B*CD/EC.- + *ABC/DED.- +A*BC/DE6.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对的二叉排序树以后，查找元素35要进行次元素间的比较。
A.4B.5C.7D.107.对于一个具有n个顶点和e条边的图，来用邻接矩阵表示的空间复杂度为。
A.O(n)B.O(e)C. O(n2)D. (n+e)8.设连通图G的顶点数n，则G的生成树的边数为。
A.nB.n-1C.2n D，2n-19.下列排序算法中，算法可能出现下面的情况:在最后一趟排序开始之前，所有元素都不在最终的位置上。
A.堆排序B.冒泡排序C.快速排序D.插入排序10.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m 前的条件是A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙二、判断题（判断下列各小题的叙述是否正确，若正确打“√”，否则打“×”，每小题1分，共10分）1. 线性表中每个元素都有一个前驱和一个后继。
湖南大学研究生入学考试专业课历年真题湖南大学电气与信息工程学院自动控制原理历年真题湖南大学马克思主义学院马克思发展史、共产党思想政治教育史真题湖南大学教育科学研究院管理学原理、教育学历年真题湖南大学法学院管理学原理、公共行政学历年真题湖南大学法学院政治学原理、西方政治思想历年真题湖南大学信息科学与工程学院数据结构、数据库系统基础历年真题湖南大学电气与信息工程学院智能仪器、电路、电子技术历年真题湖南大学物理与微电子科学学院数字与模拟、电磁场历年真题湖南大学物理与微电子院普通物理、量子力学、电动力学等历年真题湖南大学建筑学院城市规划与基础历年真题湖南大学机械学院工程力学、机械原理、材料、流体力学历年真题湖南大学机械学院机械、材料力学、生产管理、电路一历年真题湖南大学土木工程学院土力学、交通工程学历年真题湖南大学化学化工学院物理化学(理）习题库及答案湖南大学化学化工学院有机化学（理）习题库及答案湖南大学中国语言文学学院文学理论和写作、语言学概论与写作真题湖南大学新闻传播与影视艺术学院新闻传播史论、新闻传播实务真题湖南大学经济与贸易学院经济学原理（微观、宏观经济学）历年真题湖南大学体育学院体育学基础综合（含运动生理学、体育概论）真题湖南大学生物学院生物化学、细胞生物学历年真题湖南大学法学院综合一(法理学、宪法)、综合二(民法、刑法)真题湖南大学金融与统计学院经济学基础、统计学历年真题湖南大学教育科学研究院教育学专业基础综合历年真题湖南大学岳麓书院西方哲学史、中国哲学史、考古学通论历年真题湖南大学马克思主义学院西方哲学史、马克思主义哲学原理历年真题湖南大学工商管理学院应用统计基础、管理学原理、财务会计学真题湖南大学材料科学与工程学院材料科学基础、物理化学（工）真题湖南大学外国语与国际教育学院日语、德语、法语、基础英语真题湖南大学信息科学与工程学院数字电路与逻辑设计、电子技术真题湖南大学电气与信息工程学院智能仪器、电路历年真题湖南大学设计艺术学院设计艺术史论、专业设计A历年真题湖南大学物理与微电子计算机应用基础、现代教育技术历年真题湖南大学数学与计量经济学院数学分析、高等代数历年真题湖南大学建筑学院建筑学基础历年真题湖南大学环境科学与工程学院环境毒理学与环境工程微生物真题湖南大学机械学院材料力学、机械原理、结构、流体力学历年真题湖南大学土木工程学院结构力学、流体力学历年真题湖南大学化学化工学院有机化学、物理化学历年考研真题（理）。
1 •试述数据、数据库、数据库系统、数据库管理系统的概念。
2.使用数据库系统有什么好处？3.试述文件系统与数据库系统的区别和联系。
4.试述数据库系统的特点。
5.数据库管理系统的主要功能有哪些？6.试述数据模型的概念、数据模型的作用和数据模型的三个要素。
7.试述概念模型的作用。
8.定义并解释概念模型中以下术语：实体，实体型，实体集，属性，码，实体联系图（E-R图）9.试述网状、层次数据库的优缺点。
10.试述关系模型的概念，定义并解释以下术语：（1）关系（2）属性（3）域（4）元组（5）主码（6）分量（7）关系模式11•试述关系数据库的特点。
12•试述数据库系统三级模式结构，这种结构的优点是什么？13.定义并解释以下术语：DDL、DML14.什么叫数据与程序的物理独立性？什么叫数据与程序的逻辑独立性？为什么数据库系统具有数据与程序的独立性？15•试述数据库系统的组成。
16.DBA的职责是什么？17.系统分析员、数据库设计人员、应用程序员的职责是什么？18.试述关系模型的三个组成部分。
19.试述关系数据语言的特点和分类。
20.定义并理解下列术语，说明它们之间的联系与区别：（1）域，笛卡尔积，关系，元组，属性（2）主码，候选码，外部码（3）关系模式，关系，关系数据库21•试述关系模型的完整性规则。
在参照完整性中，为什么外部码属性的值也可以为空？什么情况下才可以为空？22.等值连接与自然连接的区别是什么？23.代数的基本运算有哪些？如何用这些基本运算来表示其他的关系基本运算？24•试述SQL语言的特点。
25.试述SQL的定义功能。
26.用SQL语句建立第2章习题5中的四个表。
27.针对上题中建立的四个表试用SQL语言完成第2章习题5中的查询。
28.针对习题3中的四个表试用SQL语言完成以下各项操作：（1）找出所有供应商的姓名和所在城市。
（2）找出所有零件的名称、颜色、重量。
（3）找出使用供应商S1所供应零件的工程号码。
考研数据结构试题及答案一、选择题（每题2分，共10分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 栈C. 数组D. 队列答案：C2. 下列关于图的描述中，错误的是：A. 图是由顶点和边组成的B. 图中的边可以是无向边或有向边C. 图中任意两个顶点之间有且只有一条边D. 图可以是无向的或有向的答案：C3. 哈希表的冲突可以通过以下哪种方法来解决？A. 链地址法B. 排序C. 插入排序D. 选择排序答案：A4. 在二叉树的遍历算法中，先访问根节点，然后遍历左子树，最后遍历右子树，这种遍历方式被称为：A. 前序遍历B. 中序遍历C. 后序遍历D. 层序遍历答案：A5. 在排序算法中，时间复杂度为O(nlogn)的算法是：A. 冒泡排序B. 快速排序C. 插入排序D. 选择排序答案：B二、填空题（每题2分，共10分）1. 在二叉搜索树中，对于任意节点，其左子树中的所有节点的值都比该节点的值________。
答案：小2. 堆是一种特殊的完全二叉树，其中每个节点的值都大于或等于其子节点的值的堆被称为________。
答案：最大堆3. 在图的遍历中，深度优先搜索（DFS）使用的数据结构是________。
答案：栈4. 动态数组在进行插入操作时，如果数组已满，通常需要进行________操作。
答案：扩容5. 快速排序算法在最坏情况下的时间复杂度是________。
答案：O(n^2)三、简答题（每题5分，共20分）1. 请简述什么是递归，并举例说明递归在数据结构中的应用。
答案：递归是一种方法，它允许函数调用自身来解决问题。
在数据结构中，递归常用于遍历树和图，例如二叉树的前序、中序和后序遍历。
2. 描述排序算法中的稳定性和不稳定性，并给出一个稳定性排序算法的例子。
答案：稳定性排序算法是指在排序过程中，相等的元素的相对顺序不会改变。
不稳定性排序算法则可能改变相等元素的相对顺序。
湖南省考研计算机科学与技术复习资料数据结构重要考点解析湖南省考研计算机科学与技术复习资料：数据结构重要考点解析数据结构是计算机科学与技术中的重要基础课程，它研究数据之间的关系以及数据的组织和存储方式。
在湖南省考研计算机科学与技术的复习中，数据结构是一个重要的考点。
本文将对湖南省考研计算机科学与技术中数据结构的重要考点进行深入解析和讲解。
一、线性表线性表是数据结构中最基本的一种数据结构，它的特点是数据元素之间存在一对一的关系。
在湖南省考研计算机科学与技术中，线性表是一个重要的考点。
在复习中，应重点掌握线性表的基本概念、基本操作以及线性表的顺序存储和链式存储实现方式。
此外，还需要了解线性表的各种应用场景和典型算法题。
二、栈与队列栈和队列是线性表的扩展，它们是非常常用的数据结构，在湖南省考研计算机科学与技术中也是一个重要的考点。
在复习中，需要详细了解栈和队列的基本概念、基本操作以及它们的顺序存储和链式存储实现方式。
此外，还需要掌握栈和队列的应用场景和典型算法题，例如逆波兰表达式和迷宫问题等。
三、树与二叉树树是一种非常重要的非线性数据结构，在湖南省考研计算机科学与技术中，树和二叉树是一个重要的考点。
复习中需要了解树和二叉树的基本概念、树和二叉树的遍历方式，以及树和二叉树的存储结构。
此外，还需要掌握树和二叉树的各种应用场景和典型算法题，例如二叉排序树和哈夫曼树等。
四、图图是由节点和边组成的非线性数据结构，在湖南省考研计算机科学与技术中，图也是一个重要的考点。
在复习中，需要了解图的基本概念、图的存储结构以及图的遍历方式。
此外，还需要掌握图的各种应用场景和典型算法题，例如最短路径和最小生成树等。
五、排序与查找排序与查找是数据结构中常用的算法，在湖南省考研计算机科学与技术中也是一个重要的考点。
复习中需要掌握各种排序算法（如插入排序、快速排序、堆排序等）和查找算法（如顺序查找、二分查找等）的原理和实现方式。
此外，还需要了解排序算法和查找算法的时间复杂度和空间复杂度，并能够进行算法的分析和比较。
第1章绪论一、填空题01、【操作对象】【关系和运算】02、【数据元素】【关系】03、【逻辑结构】【存储结构】【运算】04、【线性结构】【非线性结构】05、【一对一】【一对多】【多对多】06、【没有】【没有】07、【前驱】【1】【后续】【任意多个】08、【任意多个】09、【顺序】【链式】【索引】【散列】10、【集合】【线性结构】【树形结构】【图状结构】11、【插入】【删除】【修改】【查找】【排序】12、【时间】【空间】13、【时间复杂度】【空间复杂度】14、【映射】15、【有穷性】【确定性】【可行性】16、【n+1】【n】【n(n+3)/2】【n(n+1)/2】17、【n(n+1)(n+2)/6】【O(n3)】18、【O(n2 log)】19、【O(nn2 log)】20、【O(22log n)】21、【(n+3)(n-2)/2】22、【n(n-1)/2】二、判断题01-05、×××√×06-10、×√×××11-12、√×三、单项选择题B01 BD02 A03 C04 C05A06 C07 B08 A09 C10B11 A12 C13 D14 A15C16四、分析下面各程序段的时间复杂度01、O（nm ）02、O（2n）03、答：O（2n）04、答：O（n3 log）五、设有数据逻辑结构S=(D,R)，试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？01、此图为线性结构d1→d2→d3→d4d1—无直接前驱，是首结点d4—无直接后继是尾结点02、此图为树形结构d1—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点03、此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点六、简述题01、什么是数据结构?答：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。
湖南省考研计算机科学与技术复习资料数据结构精讲与习题解析湖南省考研计算机科学与技术复习资料：数据结构精讲与习题解析一、引言数据结构作为计算机科学与技术领域中的重要学科，是计算机算法设计和应用的基础。
在湖南省考研计算机科学与技术的复习中，数据结构也是一个重点和难点。
本文旨在对湖南省考研计算机科学与技术中数据结构这一知识点进行精讲与习题解析，为考生提供复习资料和学习指导。
二、数据结构概述1. 数据结构的定义和概念数据结构是计算机存储、组织数据的方式，包括线性结构、树形结构和图形结构等。
数据结构是解决实际问题的工具，可以提高算法的效率和数据的操作性。
2. 数据结构的分类常见的数据结构包括数组、链表、栈、队列、树、图等。
不同的数据结构适用于不同的问题场景，需要根据实际情况选择合适的数据结构。
三、线性结构1. 数组数组是一种最基本的数据结构，具有连续的内存空间和相同的数据类型。
可以通过下标访问元素，具有随机访问的特点。
介绍数组的定义、初始化和基本操作。
2. 链表链表是一种非连续的数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。
链表可以分为单向链表、双向链表和循环链表等。
介绍链表的定义、插入、删除和查找等基本操作。
四、树形结构1. 二叉树二叉树是一种特殊的树形结构，每个节点最多有两个子节点。
介绍二叉树的定义、遍历和常见的应用场景。
2. 平衡二叉树平衡二叉树是一种特殊的二叉树，左右子树的高度差不超过1，可以提高树的搜索效率。
介绍平衡二叉树的定义、插入和删除等操作。
五、图形结构1. 图的表示图是一种非线性的数据结构，由顶点和边组成。
介绍图的邻接矩阵和邻接表两种表示方法，以及它们的优缺点。
2. 图的遍历介绍图的深度优先搜索（DFS）和广度优先搜索（BFS）两种遍历方法，以及它们的应用场景和算法实现。
六、习题解析根据湖南省考研计算机科学与技术的真题和模拟题，选取代表性的数据结构习题进行解析，包括题目分析、解题思路和代码实现。
最新计算机全国考研数据结构试卷一（练习题含答案）打印版.doc数据结构试卷1一、单选题1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
A．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为n） D. O（n2） A. O（1） B. O（n） C. O（1og29.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、_________、_________和_________。
Source：http://210.43.96.230:10007/Course/Index.htm第 1 页（共4 页）确的）1、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）（Ａ）i （Ｂ）n=i （Ｃ）n-i+1 （Ｄ）不确定2、线性表若采用链式存储结构时，要求内存中可用存储单元的地址: （）（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（）（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序4、具有n(n>0)个结点的完全二叉树的深度为（）。
(Ａ) ⎡log2(n)⎤ (Ｂ) ⎣log2(n)⎦ (Ｃ) ⎣log2(n)⎦+1 (Ｄ) ⎡log2(n)+1⎤5、有n个顶点e条边的无向图G,它的邻接表中的表结点总数是（）。
(A) 2n (B)n (C) 2e (D) e6、静态查找表与动态查找表二者的根本差别在于（）（A）它们的逻辑结构不一样（B）施加在其上的操作不同（C）所包含的数据元素的类型不一样（D）存储实现不一样7、连通图G中有n个顶点,G的生成树是（）连通子图.(A)包含G的所有顶点 (B)包含G的所有边(C)不必包含G的所有顶点 (D)必须包含G的所有顶点和所有的边8、设有5000个无序的元素，希望用最快的速度挑选出其中前50 个最大的元素，最好选用（）法。
（A）冒泡排序（B）快速排序（C）堆排序（D）基数排序9、下面的排序算法中，（）是不稳定的？（A）希尔排序（B）冒泡排序（C）直接插入排序（D）基数排序10、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。
因为散列函数不是一对一的关系，所以选择好的（）方法是散列文件的关键。
2002 年招收攻读硕士学位研究生入学考试命题专用纸招生专业:计算机科学与应用技术考试科目:数据结构试题编号:418注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效)－、单选题（每小题2分，共20分）1.在一个具有n个结点的有序单链表中插入一个新的结点使得单链表仍然有序的时间复杂度为A.O(logn)B.O(1)C.O(n2)D.O(n)2.若线性表最常用的操作是存取第i个元素及其前驱的值，则采用存储方式节省时间。
A.单向链表B.双向链表C.单循环链表D.顺序表3.用单链表表示的链式队列的队头在链表的位置。
A.链头B.链尾C.链中4.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一双亲的左、右孩子中，左孩子的编号小于右孩子的编号，则可采用顺序实现编号。
A.前序遍历B.中序遍历C.后序遍历D.层序遍历5.己知一算术表达式的中缀形式为A+ B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为。
A.-A+B*C/DEB.-A+B*CD/EC.- + *ABC/DED.- +A*BC/DE6.利用逐点插入法建立序列（50，72，43，85，75，20，35，45，65，30）对的二叉排序树以后，查找元素35要进行次元素间的比较。
A.4B.5C.7D.107.对于一个具有n个顶点和e条边的图，来用邻接矩阵表示的空间复杂度为。
A.O(n)B.O(e)C. O(n2)D. (n+e)8.设连通图G的顶点数n，则G的生成树的边数为。
A.nB.n-1C.2n D，2n-19.下列排序算法中，算法可能出现下面的情况:在最后一趟排序开始之前，所有元素都不在最终的位置上。
A.堆排序B.冒泡排序C.快速排序D.插入排序10.设n，m为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是A.n在m右方B.n是m祖先C.n在m左方D.n是m子孙二、判断题（判断下列各小题的叙述是否正确，若正确打“√”，否则打“×”，每小题1分，共10分）1. 线性表中每个元素都有一个前驱和一个后继。
2. 顺序表中逻辑关系上相邻的两个元素在物理位置上也相邻。
3. 在栈为空的情况下，不能作出栈操作，否则会产生“下溢”。
4. 对广义表A=（a，（b，c），d）的运算head（tail（A））的结果不是b。
5. 图G的一棵最小生成树的代价未必小于G的其他任何一棵生成树的代价。
6. 若从某顶点开始对含有n个顶点的有向图G迸行深度优化先遍历，所得到的遍历序列唯一，则可断定起弧数为n－1。
7. 二叉树不能存储在数组中。
8. 理想情况，在散列表中查找一个元素的时间复杂度为O(1)。
9. 最优二叉树是A VL树（平衡二叉树）10.序列（101，88，46，70，34，39，45，58，66，10）是堆。
二、填空题（每空2分，共20分）1. 在有n个元素的顺序表中，如果要删除第i个元素（1≤i≤n）,那么有个元素必须向表头方向移动。
2.栈的插入和删除只能在栈顶一端进行，后进栈的元素必定先被删除，所以栈又被称为表。
3.已知一棵完全二叉树的第八层有8个结点（根结点在第0层），则该完全二叉树的叶结点数是。
4.具有64个结点的完全二又树共有层。
5.设n行n列的下三角矩阵A已压缩到一维数组s[1..n*(n+1)/2]中，若按行序为主存储，则元素A[i,j]在S中的存储位置是。
6.要将序列{50，16，23，68，94，70，73}建成堆，只需把16与相互交换。
7.具有n个顶点的有向连通图最多有条边，最少有条边。
8.冒泡排序算法在最佳情况下的元素交换次数为。
9.插入、选择、冒泡、快速排序算法中，排序趟数与序列的原始状态有关的排序方法是。
四、解析题（第1小题6分，第2、4小题各8分，第3小题10分，共32分）1. 请解答下列关于堆的一些问题:1.堆的存储表示是顺序的还是链接的。
2.没有一个最小堆，即堆中任意元素的关键码均大于它的左子女和右子女的关键码。
其具有最大值的元素可能在什么地方？3.对n个元素进行建初始堆的过程中，最多做多少次数据比较（不用大O表示法）？2. 一棵二叉树的先序、中序、后序序列如下，其中一部分未标示出，请构造出该二叉树。
先序序列: C D E G H I K中序序列: C B F A J K I G后序序列: E F D B J I H A3. 一项工程P曲Pl，P2，P3，P4，P5，P6六个子工程组成，这些工程之间有下列关系:P1＞P2，Pl＞P3，Pl＞P4，P2＞P3，P2＞P5，P3＞P6，P4＞P6，P5＞P6。
其中符号“＞”表示先于关系，例如:Pl＞P3表示只有Pl完成之后才能进行P3的工作。
请给出工程P的四种可能的施工顺序。
4. 设按如下所述在有序的线性表中查我X:先将X与表中的第4j(j=1，2，3，…)项进行比较，若相等，由查找成功:否则，由某次比较求得比X大的一项4K之后续而和4K-2，然后和4K-3或4K-1项进行比较，直到查找成功。
试画出当表长n＝16时的判定树，并求其平均查找长度（考虑查找元素在等概率的情况下）。
五、算法设计题（可用类PASCAL、C或你所熟悉的高级语言设计算法，第1小题8分，第2小题10分，共18分）1.设计一个函数返回指向一棵二叉树的T的后序序列的第一个结点的指针，要求采用非递归形式，并且不用栈。
2.设计一算法，实现第四大题中第4小题所给出的查找方法。
2003 年招收攻读硕士学位研究生入学考试命题专用纸招生专业:计算机应用技术、计算机软件与理论、软件工程硕士考试科目:数据结构试题编号:418(450)注: 答题（包括填空题、选择题）必须答在专用答题纸上，否则无效一、单项选择题（每小题1分，共15分）1.两个各有n个元素的有序列表并成一个有序表，其最少的比较次数是A.nB.2n-1C.2nD.n-12.设循环队列中数组的下标范围是0~ n-1，f表示队首元素的前驱位置，r表示队尾元素的位置，则队列中元素个数为。
A.r-fB.r-f+1C.(r-f+1)mod nD.(r-f+n)mod n3.一个5行6列的二维数组s采用从最后一行开始，每一行的元素从右至左的方式映射到一维数组a中，s和a的下标均从0开始，则s[3][3]在a中的下标是。
A.7B. 8C. 9D. 104.设只含根结点的二叉树的高度为1，则高度为n的二叉树中所含叶子结点的个数最多为个。
A.2nB.nC.2n -1D.2n-15.设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为个（设只含根结点的二叉树的高度为1）。
A.2h B 2h-1 C.2h+1 D.h+16.对一棵二叉检索树进行得到的结点序列是一个有序序列。
A.前序周游B. 中序周游C.后序周游D. 层次周游7.一棵前序序列为1，2，3，4的二叉树，其中序序列不可能是。
A.4,1,2,3B.4,3,2,1C.2,4,3,1D.3,4,2,18.下列编码中不是前缀码。
A.{00，01，10，11}B.{0,1,00,11}C.{0，10，110，111}D.{10，110，1110，1111}9.在含n个顶点和e条边的有向图的邻接矩阵中，零元素的个数为 .A.eB.2eC.n2-eD.n2-2e10.具有n个顶点和e条边的图的深度优先搜索算法的时间复杂度为A.O(n)B.O(n3)C.O(n2)D.O(n+e)11.如果具有n个顶点的图是一个环，则它有棵生成树。
A.nB.n+lC.n-lD.2n12堆排序算法在平均情况下的时间复杂度为。
A.O(n) B.O(nlogn) C.O(n2)D.O(logn)13.在待排序数据已基本有序的前提下，下述排序方法中效率最高的是。
A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序14.在理想情况下，散列表中查找元素所需的比较次数为。
A.nB.OC.n/2D.115.在一棵m阶B树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是。
A.mB.m+1C.m—lD.m/2二、判断题(判断下列各题是否正确，若正确，在括号内打“√”，否则打“╳”；每小题1分，共10分)1.已知指针curr指向链表中的某结点，执行语句curr=curr->next；不会删除该链表中的结点。
( )2.若二叉树的叶结点数为1，则其高度等于结点数(仅含根结点的二叉树高度为1)。
（）3.按中序周游二叉树时，某个结点的直接后继是它的右子树中第一个被访问的结点。
( )4.完全二叉树的某结点若无左孩子，则它必是叶结点。
( )5.向二叉检索树中插入一个新结点，需要比较的次数不可能大于此二叉树的高度。
( )6.对一个堆按层次周游，一定能得到一个有序序列。
( )7.一棵树中的叶子结点数一定等于其对应的二叉树中的叶子结点数。
( )8.将一棵树转换为二叉树表示后，该二叉树的根结点没有右子树。
( )9.任何有向图的结点都可以排成拓扑序列，而且拓扑序列不唯一。
( )10.快速排序在最差情况下的时间复杂度是0(n2)，此时它的性能并不比冒泡排序更好。
( )三、填空题（每空2分，共20分）1.具有100个结点的完全二叉树的叶子结点树为。
2.由权值分别为3，9，6，2，8的叶子结点生成一棵哈夫曼树，它的外部带权路径长度为＿＿＿。
3.对含n个结点的完全二叉树按自上而下，从左到右的顺序结点编号（从0开始），则编号最小的叶子结点的编号是。
4.n个顶点的连通无向图的邻接矩阵至少有个非零元素。
5.在有序表A[1..20]中，若需查找的元素位于A[12]，则采用折半查找算法所比较的元素的下标依次为6.要将序列{60，10，8，40，90，70，100}建成堆，只需把8与相交换。
7.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为。
8.已知广义表L=（（a，b，c），（d，e，f）），则运算head(tail(head(tail(L))))的结果是.9.模式串P=“abaa”的next函数值序列为。
10.一个两层100阶的B+树，最多可以有条记录四、解析题（共55分）1.对二叉树中结点进行按层次顺序（每一层从左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。
现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。
（7分）2.证明若二叉排序树中的一个结点存在两个孩子，则（8分）1它的中序后继结点没有左孩子。
2它的中序前趋结点没有右孩子。
3.对下面的带权无向图采用prim算法从顶点1开始构造最小生成树。
（写出假如生成树顶点集合S和选择边Edge的顺序）（10分）19 1082 34 5 6 711 8④⑤⑥S: 顶点号Edge: (顶点，顶点，权值)1 （，，）1 （，，）1 （，，）1 （，，）1 （，，）1 （，，）4.已知一组关键字序列为:（17，31，13，11，20，35，25，8，4，11，24，40，27），按照依次插入结点的方法生成一棵平衡二叉排序树。
