(NEW)厦门大学845数据结构历年考研真题汇编

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A.[68，11，18，69] [23，93，73]B.[68，11，69，23] [18，93，73]C.[93，73][68，11，69，23，18] √D.[68，11，69，23，18] [93，73]枢轴是73。

2.适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A.选择排序B.快速排序√C.希尔排序D.基数排序3.一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A.(38，40，46，56，79，84)B.(40，38，46，79，56，84)C.(40，38，46，56，79，84) √D.(40，38，46，84，56，79)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

4.下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A.快速排序√B.堆排序C.希尔排序D.冒泡排序5.将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A.拓扑排序B.快速排序√C.堆排序√D.基数排序√6.就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A.冒泡B.希尔插，AC.交换D.快速√7.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

我们的梦想，为成就更多人的梦想/ 2020厦门大学854结构力学（含结构动力学）考试范围（大纲）和参考书目由于厦门大学大部分专业课官方没有公布参考书目由此给很多考生带来了很大的不便，对此精都考研网整理了厦门大学往届研究生初试用书对应的辅导资料，同时摘录了厦门大学官方公布的考试科目考试范围以便同学查阅参考。

以下内容是【精都考研网】整理发布，每天及时发布最新考研资讯、考研经验、考研真题。

目前很多同学已加入2020厦门大学考研总群829573389，抓紧时间加入了解你所不知道的考研信息。

一、2019专业课考试范围（官网公布，20届的今年10月份公布）
含结构力学和结构动力学基础。

内容包括结构几何稳定性分析、结构的内力和位移求解、影响线、力法、位移法、矩阵位移法、结构动力学等
二、往届研究生初试参考用书：
龙驭球《结构力学Ⅰ》
龙驭球《结构力学Ⅱ》
三、往届研究生初试配套精编复习资料
厦门大学854结构力学（含结构动力学）复习全程通（全套资料目录清单）
复习全程通NO1（历年真题汇编）：2008-2014年7套考研真题
复习全程通NO2（教辅一本通）：2本：
龙驭球《结构力学Ⅰ》本专业研究生整理章节的重点笔记和章节典型题及答案解析
龙驭球《结构力学Ⅱ》本专业研究生整理章节的重点笔记和章节典型题及答案解析
复习全程通NO3（冲刺模拟套卷）：2套含答案解析
复习全程通NO4（非卖品，电子版赠送内容）：
1. 龙驭球《结构力学》课件讲义
2. 结构力学习题集
3. 结构的内力计算
以上资料可以上精都考研网或加厦大考研群了解。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】__________________________________________________________________________________________正确答案：(正确答案：成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。

计算方法参见上面58题(3)。

)2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】__________________________________________________________________________________________正确答案：(正确答案：装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)3.设散列表长度为14，散列函数，其中i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。

福建省考研计算机复习资料数据结构常考题解析数据结构作为计算机考研的重要内容之一，常常会出现在考试中，因此熟悉常考题型并进行解析对于备考非常必要。

本文将对福建省考研计算机专业的数据结构常考题进行解析，以助于考生的复习备考。

一、常见题型分析1. 单选题单选题是考研中常见的题型之一，通过从若干选项中选择一个正确答案来回答问题。

在数据结构中，单选题多涉及基本概念、算法和常见数据结构的应用等方面。

考生在准备时应重点复习这些方面的内容，以便能够准确地选择正确答案。

2. 多选题多选题要求考生从若干选项中选择多个正确答案，其中往往会夹杂有干扰选项。

对于这种题型，考生需具备较深入的理解和掌握，才能正确辨别出正确选项。

在复习过程中，考生应注重掌握数据结构相关知识的深度和广度，以提高自己的解题能力。

3. 填空题填空题在数据结构考试中也是常见的一种题型。

在这类题目中，考生需要在给定的空中填写一个或多个合适的内容，以完整答案。

对于这种类型的题目，考生需要熟悉各种数据结构的定义、特点和相关算法的实现，确保对每个填空的内容都能正确把握。

4. 算法设计题算法设计题是数据结构考试中的一种较难题型，要求考生具备一定的算法设计和实现能力。

在这类题目中，考生需要根据题目要求，设计出一个可行的算法，并给出相应的实现。

在复习过程中，考生应着重掌握常用算法的设计思想和实现过程，以及算法的优缺点和适用范围等方面的知识。

二、常考题解析1. 单选题常见的单选题有：（1）题目：对于一个长度为n的有序（非递减）序列，若要查找某个元素的位置，合适的算法是：A. 顺序查找B. 折半查找C. 插值查找D. 哈希查找解析：由于给定序列是有序的，所以可以采用折半查找算法，将查找的时间复杂度降低到O(logn)。

因此，正确答案是B。

2. 多选题常见的多选题有：（1）题目：下列哪些数据结构是非线性表？A. 数组B. 链表C. 栈D. 队列E. 树F. 图解析：线性表是一种数据结构，其中的元素按照一定的顺序排列。

厦门大学考研历年真题及答案解析聚创考研网汇集厦门大学各学院的专业考研真题等资料，同时与厦门大学专业课成绩前三名的各专业硕士研究生合作编写了研发的《厦门大学考研专业复习全书》及《全真模拟题解析》。

本书系统全面总结考研专业课知识，重难点分明，深度解析历年考研真题并进行命题预测，为考生节省大量宝贵的复习时间，帮助考生在扎实基础之上迅速提高专业课成绩，是今年考生从基础到冲刺阶段必备的考研专业课资料。

【亮点介绍】1.专业课深度解析部分从考研各知识点历年的考察频率和变化趋势，明确重要考点和参考书目的重要章节，从宏观试题分析、命题预测、全程规划建议、高分学长考研经验等角度直抵专业课考研资讯最前沿，准确把握专业课的考研规律。

2.核心考点解析部分根据官方参考书目编写，对教材内容进行精简整合，所有知识点均根据其历年考察的频率进行重要程度评估，并对真题考过的知识点进行明晰，免去考生自己查阅、分析的烦恼，深入探讨重点考点，精准洞察知识脉络。

部分难点附有重点提示和易出考试题型说明。

本部分内容对前几轮复习具有较大辅助作用，在考研后期复习阶段可脱离教材结合核心考点解析进行理解和记忆，提高考生的复习效率和复习效果。

3.历年真题及答案解析部分给出了专业课考试历年考研真题，内含详细而精准的参考答案。

聚创考研网根据厦门大学的每一年考试范围进行更新完善，年年相伴考研。

如需要完整版请联系微信mskaoyan购买。

【复习全书使用说明】一、复习全书（主要含核心考点和历年真题）的使用建议（一）复习第一招：按图索骥，宏观洞悉1.复习基础阶段：初步浏览及标识复习中的疑惑点，此阶段重在对整体知识内容留有印象，知晓重点，解决疑惑点；2.复习深化阶段：对应核心考点具体内容，增加标识，此阶段可对照具体内容的复习情况，把未熟练掌握内容进行标识及补充复习中发现的重要内容；3.复习冲刺阶段：可脱离参考书及复习全书中的核心考点解析部分，单独看框架和纲要回忆知识点并默写，以此查漏补缺，落实记忆。

第10章 排序排序排序一、选择题 1．某内排序方法的稳定性是指．某内排序方法的稳定性是指( )( )( )。

【南京理工大学【南京理工大学 1997 1997 1997 一、一、一、101010（（2分）】 A ．该排序算法不允许有相同的关键字记录该排序算法不允许有相同的关键字记录 B B B．．该排序算法允许有相同的关键字记录记录C ．平均时间为0（n log n n log n）的排序方法）的排序方法）的排序方法D D D．以上都不对．以上都不对．以上都不对2．下面给出的四种排序法中下面给出的四种排序法中( )( )( )排序法是不稳定性排序法。

排序法是不稳定性排序法。

【北京航空航天大学北京航空航天大学 1999 1999 1999 一、一、10 10 （（2分）】 A. A. 插入插入插入 B. B. B. 冒泡冒泡冒泡 C. C. C. 二路归并二路归并二路归并 D. D. D. 堆积堆积堆积 3．下列排序算法中，其中（．下列排序算法中，其中（ ）是稳定的。

）是稳定的。

）是稳定的。

【福州大学【福州大学 1998 1998 1998 一、一、一、3 (23 (2分)】A. A. 堆排序，冒泡排序堆排序，冒泡排序堆排序，冒泡排序B. B. B. 快速排序，堆排序快速排序，堆排序快速排序，堆排序C. C. 直接选择排序，归并排序直接选择排序，归并排序直接选择排序，归并排序D. D. D. 归并排序，冒泡排序归并排序，冒泡排序归并排序，冒泡排序4．稳定的排序方法是（．稳定的排序方法是（ ）） 【北方交通大学【北方交通大学【北方交通大学 2000 2000 2000 二、二、二、33（2分）】 A ．直接插入排序和快速排序．直接插入排序和快速排序 B B B．折半插入排序和起泡排序．折半插入排序和起泡排序．折半插入排序和起泡排序C ．简单选择排序和四路归并排序．简单选择排序和四路归并排序D D D．树形选择排序和．树形选择排序和shell 排序排序5．下列排序方法中，哪一个是稳定的排序方法？（．下列排序方法中，哪一个是稳定的排序方法？（ ） 【北方交通大学【北方交通大学【北方交通大学 2001 2001 2001 一、一、一、88（2分）】A ．直接选择排序．直接选择排序B B B．二分法插入排序．二分法插入排序．二分法插入排序C C C．希尔排序．希尔排序．希尔排序D D D．快速排序．快速排序．快速排序6．若要求尽可能快地对序列进行稳定的排序，则应选（．若要求尽可能快地对序列进行稳定的排序，则应选（A A ．快速排序．快速排序 B B B．归并排序．归并排序．归并排序 C C C．冒．冒泡排序）。

目录Ⅰ历年考研真题试卷 (1)厦门大学2011年招收攻读硕士学位研究生入学考试试卷 (2)厦门大学2012年招收攻读硕士学位研究生入学考试试卷 (5)厦门大学2013年招收攻读硕士学位研究生入学考试试卷 (7)厦门大学2014年招收攻读硕士学位研究生入学考试试卷 (10)厦门大学2015年招收攻读硕士学位研究生入学考试试卷 (133)厦门大学2016年招收攻读硕士学位研究生入学考试试卷 (16)厦门大学2017年招收攻读硕士学位研究生入学考试试卷 (20)Ⅱ历年考研真题试卷答案解析 (24)厦门大学2011年招收攻读硕士学位研究生入学考试试卷答案解析 (24)厦门大学2012年招收攻读硕士学位研究生入学考试试卷答案解析 (33)厦门大学2013年招收攻读硕士学位研究生入学考试试卷答案解析 (40)厦门大学2014年招收攻读硕士学位研究生入学考试试卷答案解析 (49)厦门大学2015年招收攻读硕士学位研究生入学考试试卷答案解析 (58)厦门大学2016年招收攻读硕士学位研究生入学考试试卷答案解析 (69)厦门大学2017年招收攻读硕士学位研究生入学考试试卷答案解析 (80)厦门大学2011年招收攻读硕士学位研究生入学考试试卷科目代码：844科目名称：自动控制原理招生专业：电气检测技术及仪器、控制理论与控制工程、系统工程、检测技术与自动化装置、模式识别与智能系统、核科学与工程、能效工程考生须知：答案必须使用墨（蓝）色墨水（圆珠）笔；不得在试卷（草稿）纸上作答；凡未按规定作答均不予评阅、判分1. 二阶系统的传递函数为23()23G s s s =+-试求该系统的 （a ）脉冲响应函数； （b ）直流增益；（c ）对阶跃响应的终值。

（15分） 2. 已知系统的开环传递函数为()(2)KG s s s =+，若要求峰值时间1p t =秒，超调量，确定在单位反馈情况下是否存在K 值同时满足这两个要求？试在S 平面上大致绘出满足要求的极点区域。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编3(总分66, 做题时间90分钟)6. 综合题1.数组A[1．．8，一2．．6，0．．6]以行为主序存储，设第一个元素的首地址是78，每个元素的长度为4，试求元素A[4，2，3]的存储首地址。

【厦门大学1998五、1(5分)】SSS_TEXT_QUSTI2.数组A中，每个元素A[i，f]的长度均为32个二进位，行下标从一1到9，列下标从1到11，从首地址S开始连续存放在主存储器中，主存储器字长为16位。

求：(1)存放该数组所需多少单元?(2)存放数组第4列所有元素至少需多少单元?(3)数组按行存放时，元素A[7，4]的起始地址是多少?(4)数组按列存放时，元素A[4，7]的起始地址是多少?【大连海事大学1996四、1(6分)】SSS_TEXT_QUSTI3.假设按低下标优先存储整型数组A(一3：8，3：5，一4：0，0：7)时，第一个元素的字节存储地址是100，每个整数占4字节，问A(0，4，一2，5)的存储地址是什么? 【清华大学1996三】SSS_TEXT_QUSTI4.设有五对角矩阵A=(aij )20*20，按特殊矩阵压缩存储的方式将其五条对角线上的元素存于数组A[-10：m]中，计算元素A[15，16]的存储位置。

【东北大学1999一、2(4分)】SSS_TEXT_QUSTI5.数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】SSS_TEXT_QUSTI6.设m×n阶稀疏矩阵A有t个非零元素，其三元组表表示为LTMA[t+1)，1．．3]，试问：非零元素的个数t达到什么程度时用LTMA表示A才有意义?【北京航空航天大学1998一、5(4分)】SSS_TEXT_QUSTI设有三对角矩阵(aij )n×n将其三条对角线上的元素逐行地存于数组B(1：3n一2)中，使得s[k]=ai，j，求：SSS_TEXT_QUSTI7.用i，j表示k的下标变换公式；SSS_TEXT_QUSTI8.若n=10 3，每个元素占用L个单元，则用B[K]方式比常规存储节省多少单元?【西安电子科技大学1996二、4(5分)】9.已知A为稀疏矩阵，试从空间和时间角度，比较采用两种不同的存储结构(二维数组和三元组表)完成求运算的优缺点。

一、选择题(单选)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. 循环队列存储在数组A[0..m]中，则入队时的队尾指针操作为（D）。

A. rear=rear+1B. rear=(rear+1)%(m-1)C. rear=(rear+1)%mD. rear=(rear+1)%(m+1)5. 在单链表中指针p所指的结点后插入新结点s有下列3个步骤：① s->data=x （赋值）② p->next=s③ s->next=p->next正确的步骤顺序为（B）。

A. ①②③B. ③②①C. ②①③D. 无正确答案6. 对于先序遍历和后序遍历结果相同的二叉树为（B）。

A. 一般二叉树B. 只有根结点的二叉树C. 根结点无左孩子的二叉树D. 根结点无右孩子的二叉树7. 若图的邻接矩阵是对称阵，则此图必然为（B）。

A. 有向图B. 无向图C. 连通图D. 有向图或无向图8. 关于哈夫曼树，下列描述正确的是（D）。

A. 一定是二叉排序树B. 是一棵完全二叉树C. 是一棵平衡二叉树D. 以上三种说法都不对9. 长度为12的按关键字有序的待查找序列，采用顺序存储，若用二分查找，则在等概率情况下，查找成功的ASL是（A ）。

A. 37/12B. 62/13C. 39/12D. 49/1210. 在数据管理技术的发展过程中，经理了人工管理阶段、文件系统阶段和数据库系统阶段。