2021年厦门大学845数据结构考研精编资料

第九章集合一、选择题1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。

【北京航空航天大学 2000 一、8 （2分）】A． (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/23．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。

在此假定N为线性表中结点数，且每次查找都是成功的。

【长沙铁道学院 1997 四、3 (4分)】A.N+1B.2log2NC.logND.N/2E.Nlog2NF.N24. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学 1996 一、3 （2分）】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储5. 对线性表进行二分查找时，要求线性表必须（）【燕山大学 2001 一、5 （2分）】A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序6．适用于折半查找的表的存储方式及元素排列要求为( ) 【南京理工大学 1997 一、6 （2分）】A．链接方式存储，元素无序 B．链接方式存储，元素有序C．顺序方式存储，元素无序 D．顺序方式存储，元素有序7. 用二分（对半）查找表的元素的速度比用顺序法( ) 【南京理工大学 1998 一、11 （2分）】A．必然快 B. 必然慢 C. 相等 D. 不能确定8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减【南京理工大学 1997 一、7 （2分）】9. 具有12个关键字的有序表，折半查找的平均查找长度（）【中山大学 1998 二、10 （2分）】A. 3.1B. 4C. 2.5D. 510. 折半查找的时间复杂性为（）【中山大学 1999 一、15】A. O（n2）B. O（n）C. O（nlog n）D. O（log n）11．当采用分快查找时，数据的组织方式为 ( ) 【南京理工大学 1996 一、7 （2分）】A．数据分成若干块，每块内数据有序B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D. 数据分成若干块，每块（除最后一块外）中数据个数需相同12. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低【武汉交通科技大学1996 一、2(4分)】(1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置(2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。

Linux 设备驱动 Edition 3ByJonathan Corbet,Alessandro Rubini,Greg Kroah-Hartman由 quickwhale 翻译的简体中文版 V0.1.0 2006-6-2学习编程有几年了，感觉走了不少弯路，而不少的学弟学妹又在重蹈我当初的覆辙，不免有些痛心。

最近在网上也看了许多前辈们的经验建议，再结合自己的学习经历在这里谈谈基础的重要性，希望帮助大家少走些弯路。

什么是基础呢？就是要把我们大学所学的离散数学,算法与数据结构，操作系统，计算机体系结构，编译原理等课程学好,对计算机的体系,CPU本身,操作系统内核,系统平台,面向对象编程,程序的性能等要有深层次的掌握。

初学者可能体会不到这些基础的重要性，学习jsp,donet,mfc,vb的朋友甚至会对这些嗤之以鼻,但是一开始没学好基础就去学jsp或donet会产生很坏的影响,而且陷入其中不能自拔。

我上大二的时候还对编程没什么概念,就上了门C++也不知道能干什么，老师说MFC也不知道是什么东西，看别的同学在学就跟着学了,然后就了解到.net,j2ee,php是什么了，就觉得软件开发就是用这些了，而上的那些专业课又与我们学的sqlserver啊,css啊,ajax啊,毫无关系,就感慨啊，还不如回家自学去就为一个文凭吗？还不如去培训,浪费这么多钱.于是天天基本上没去上什么课,天天就在做网站,几个学期就做了三个网站。

感觉做这些网站就是学到些技巧，没什么进步,这些技巧就好比别人的名字,告诉你你就知道了,网上也都可以搜到。

那时候就觉得把.net学好就行了，搞j2ee的比较难，搞api编程就别想了，操作系统更是望尘莫及了。

后来随着学习的深入和看了网上许多前辈们的建议才对这些基础的重要性有所体会。

虽然.net或java的开发并不直接用到汇编,操作系统这些,但是不掌握这些基础是有很大问题的，因为你只知其然不知其所有然，在mfc和.net里面控件一拖什么都做好了，很方便，但是出了问题可能就解决不了，有些在网上搜都搜不到。

厦大计算机学硕考研科目厦门大学计算机学硕考研科目一、数据结构与算法分析数据结构与算法分析是计算机学硕考研中的重要科目之一。

它主要涉及到数据结构的基本概念、常见数据结构的实现与应用，以及算法设计与分析等内容。

在这门课程中，学生将学习到如何选择合适的数据结构来解决实际问题，并掌握常见算法的设计与实现方法。

同时，学生还将通过编写程序实践，提高自己的编程能力和问题解决能力。

二、操作系统原理操作系统原理是计算机学硕考研中的另一门重要科目。

它主要涉及到操作系统的基本概念、进程管理、内存管理、文件系统、设备管理等内容。

在这门课程中，学生将学习到操作系统的基本原理和工作原理，了解操作系统的组成和功能，以及常见的操作系统调度算法和内存管理算法。

通过学习操作系统原理，学生将掌握操作系统的设计与实现方法，并能够解决实际问题。

三、计算机网络计算机网络是计算机学硕考研中的另一门重要科目。

它主要涉及到计算机网络的基本概念、网络体系结构、网络协议、网络安全等内容。

在这门课程中，学生将学习到计算机网络的基本原理和工作原理，了解计算机网络的组成和功能，以及常见的网络协议和网络安全技术。

通过学习计算机网络，学生将能够设计和管理计算机网络，并解决实际网络问题。

四、数据库原理与应用数据库原理与应用是计算机学硕考研中的另一门重要科目。

它主要涉及到数据库的基本概念、数据库模型、数据库管理系统、数据库设计与实现等内容。

在这门课程中，学生将学习到数据库的基本原理和工作原理，了解数据库的组成和功能，以及常见的数据库设计方法和查询语言。

通过学习数据库原理与应用，学生将能够设计和管理数据库，并解决实际数据库问题。

五、软件工程软件工程是计算机学硕考研中的另一门重要科目。

它主要涉及到软件开发的基本概念、软件生命周期、软件需求分析、软件设计与实现、软件测试与维护等内容。

在这门课程中，学生将学习到软件工程的基本原理和方法，了解软件开发的过程和技术，以及常见的软件开发模型和开发工具。

2021数据结构考研数据结构与C语言考研名校考研真题一、名校考研真题解析为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是（）。

[2009年联考真题]A．栈B．队列C．树D．图【答案】B ！~【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。

栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。

由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。

100．设哈希表长M=14，哈希函数H（KEY）=KEY MOD 11。

表中已有4个结点：ADDR（15）=4，ADDR（38）=5，ADDR（61）=6，ADDR（84）=7，其余地址为空，如用二次探测再哈希法解决冲突，关键字为49的结点的地址是（）。

[东华大学考研真题]A．8B．3C．5D．9【答案】D ！~【解析】15，38，61，84用哈希函数H（key）=key%11计算后得地址:4,5,6,7 49计算后为5,发生冲突. 用二次探测再散列法解决冲突: 1:（key+1^2）%11=（49+1）%11=6,仍然发生冲突. 2:（key-1^2）%11=（49-1）%11=4,仍然发生冲突. 3:（key+2^2）%11=（49+4）%11=9,不再发生冲突.101．设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进入栈S。

若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是（）。

[2009年联考真题]A．1B．2C．3D．4【答案】C ！~【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。

在本题中，每个元素出栈S后立即进入队列Q，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。

.2021 年厦门大学 838 普通物理学（海洋与地球学院）考研精编资料一、厦门大学 838 普通物理学（海洋与地球学院）考研真题汇编及考研大纲1 ．厦门大学 838 厦门大学 838 普通物理学（海洋与地球学院） 2000-2004 、2006-2011 年考研真题；其中 2006-2007 有答案。

2. 厦门大学 838普通物理学考研大纲①2018年厦门大学838普通物理学考研大纲。

二、 2021 年厦门大学 838 普通物理学（海洋与地球学院）考研资料3 ．同济大学数学系《高等数学》考研相关资料（ 1 ）同济大学数学系《高等数学》 [ 笔记 + 课件 + 提纲 ]①厦门大学 838 普通物理学（海洋与地球学院）之同济大学数学系《高等数学》考研复习笔记。

②厦门大学 838 普通物理学（海洋与地球学院）之同济大学数学系《高等数学》本科生课件。

③厦门大学 838 普通物理学（海洋与地球学院）之同济大学数学系《高等数学》复习提纲。

（ 2 ）同济大学数学系《高等数学》考研核心题库（含答案）①厦门大学 838 普通物理学（海洋与地球学院）考研核心题库之同济大学数学系《高等数学》综合题精编。

（ 3 ）同济大学数学系《高等数学》考研模拟题 [ 仿真 + 强化 + 冲刺 ]① 2021 年厦门大学 838 普通物理学（海洋与地球学院）之高等数学考研专业课六套仿真模拟题。

② 2021 年厦门大学 838 普通物理学（海洋与地球学院）之高等数学考研强化六套模拟题及详细答案解析。

③ 2021 年厦门大学 838 普通物理学（海洋与地球学院）之高等数学考研考研冲刺六套模拟题及详细答案解析。

4 ．程守洙《普通物理学》考研相关资料（ 1 ）程守洙《普通物理学》 [ 笔记 + 课件 + 提纲 ]①厦门大学 838 普通物理学（海洋与地球学院）之程守洙《普通物理学》考研复习笔记。

②厦门大学 838 普通物理学（海洋与地球学院）之程守洙《普通物理学》本科生课件。

第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．冒．冒泡排序）。

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

一、专业课考试范围（官网公布）数据结构（100分）：绪论、线性表、栈、队列、串、数据和广义表、树与二叉树、图、查找、内部排序等操作系统基础（50分）：1、操作系统概述2、进程管理3、内存管理4、文件管理5、输入输出（I/O）管理 6、分布式操作系统基础二、往届研究生初试参考用书：汤子瀛《计算机操作系统》严蔚敏《数据结构》三、往届研究生初试配套精编复习资料厦门大学875数据结构与操作系统复习全程通（全套资料目录清单）复习全程通NO1（历年真题汇编）：2016新设科目故无真题，提供2017年考研真题和2018年回忆版考点题型，和厦门大学数据结构真题以及操作系统名校真题复习全程通NO2（教辅一本通）：2本汤子瀛《计算机操作系统》本专业研究生整理章节重点笔记和典型考题及答案解析严蔚敏《数据结构》本专业研究生整理章节重点笔记和典型考题及答案解析复习全程通NO3（冲刺模拟套卷）：4套含答案解析复习全程通NO4（非卖品，电子版赠送内容）：数据结构和操作系统的教学讲义厦门大学数据结构复习讲义厦门大学数据结构课件厦门大学数据结构期末试卷以上资料可以上精都考研网了解以上内容是【精都考研网】整理发布，每天及时发布最新考研资讯、考研经验、考研真题。

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

数据结构考研真题栈和队列第3章栈和队列⼀选择题1. 对于栈操作数据的原则是（）。

【青岛⼤学 2001 五、2（2分）】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。

当栈中元素为n个,作进栈运算时发⽣上溢,则说明该栈的最⼤容量为( ③ )。

为了增加内存空间的利⽤率和减少溢出的可能性,由两个栈共享⼀⽚连续的内存空间时,应将两栈的( ④ )分别设在这⽚内存空间的两端,这样,当( ⑤ )时，才产⽣上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中⼼点.B. 其中⼀个栈的栈顶到达栈空间的中⼼点.C. 两个栈的栈顶在栈空间的某⼀位置相遇.D. 两个栈均不空,且⼀个栈的栈顶到达另⼀个栈的栈底.【上海海运学院 1997 ⼆、1（5分）】【上海海运学院 1999 ⼆、1（5分）】3. ⼀个栈的输⼊序列为123…n，若输出序列的第⼀个元素是n，输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i【中⼭⼤学 1999 ⼀、9(1分)】4. 若⼀个栈的输⼊序列为1,2,3,…,n，输出序列的第⼀个元素是i，则第j个输出元素是（）。

A. i-j-1B. i-jC. j-i+1D. 不确定的【武汉⼤学 2000 ⼆、3】5. 若已知⼀个栈的⼊栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。

A. iB. n-iC. n-i+1D. 不确定【南京理⼯⼤学 2001 ⼀、1（1.5分）】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪⼀个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6【北⽅交通⼤学 2001 ⼀、3（2分）】7. 设栈的输⼊序列是1，2，3，4,则（）不可能是其出栈序列。

2020年招收攻读硕士学位研究生入学考试试题（A）********************************************************************************************招生专业与代码：计算机系统结构081201、计算机软件与理论081202、计算机应用技术081203、电子信息(专业学位)085400考试科目名称及代码：计算机基础综合848考生注意：所有答案必须写在答题纸（卷）上，写在本试题上一律不给分。

第一部分数据结构（75分）一、单项选择题(每题2分，共20分)1.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

A.单链表B.仅有头指针的单向循环链表C.双链表D.仅有尾指针的单向循环链表2.一个栈的输入序列为1，2，3...，n，若输出序列的第一个元素是n，那么输出第i（1<=i<=n）个元素是（）。

A.n-iB.iC.n-i+1D.不确定3.若一颗二叉树具有15个度为2的结点，10个度为1的结点，则度为0的结点个数是（）。

A.16B.25C.40D.不确定4.根据使用频率，为5个字符设计的哈夫曼编码不可能是（）。

A.000，001，010，011，1B.000，001，01，10，11C.00，100，101，110，111D.0000，0001，001，01，15.设a，b为一棵二叉树上的两个结点，在中序遍历时，a在b前面的条件是（）。

A.a在b的右方B.a在b的左方C.a是b的祖先D.a是b的子孙6.对一棵二叉排序树按（）遍历，可得到结点值从小到大的排序序列。

A.先序B.中序C.后序D.层次7.已知一个有序表为(5，13，19，21，37，56，64，75，80，88，92)，则折半查找64需要比较（）次。

A.1B.2C.3D.48.在一个图中，所有顶点的度数之和等于所有边数的（）倍。