下载文档原格式
文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持2015年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题： 140 小题，每小题 2 分，共 80 分。
下列每题给出的四个选项中，只 有一个选项符合题目要求。
请在答题卡上将所选项的字母涂黑。
1．已知程序如下： int s(int n) {return (n<=0) ? 0 : s(n-1) +n;}void main() { cout<< s(1); }程序运行时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息一次对应的是 A ． main()->S(1)->S(0) B ． S(0)->S(1)->main() C ． main()->S(0)->S(1)D ． S(1)->S(0)->main()2． 先序序列为 a,b,c,d 的不同二叉树的个数是 A ． 13B ．14C ．15D ．163．下列选项给出的是从根分别到达两个叶节点路径上的权值序列，能属于同一棵哈夫 曼树的是序序列。
下列关于该平衡二叉树的叙述中，正确的是5. 设有向图 G=(V,E)，顶点集 V={V o ,V i ,V 2,V 3}，边集 E={<v 0,v i >,<v 0,v 2>,<v o ,v 3>,<v i ,v 3>}, 若从顶点 V 0 开始对图进行深度优先遍历，则可能得到的不同遍历序列个数是A. 2 B . 3C . 4D . 56.求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(kruskal )算法第二次选 中但不是普里姆( Prim )算法(从 V 4开始)第 2 次选中的边是A. (V1,V3)B . (V1,V4)C . (V2,V3)D . (V3,V4)A ． 24， 10， 5 和 24，10，7 C ．24，10，10 和 24， 14，114．现在有一颗无重复关键字的平衡二叉树B ．24，10，5 和 24， 12，7 D ．24，10，5 和 24，14，6( AVL 树) ,对其进行中序遍历可得到一个降A .根节点的度一定为 2 C .最后插入的元素一定是叶节点B .树中最小元素一定是叶节点 D .树中最大元素一定是无左子树文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持7. 下列选项中，不能构成折半查找中关键字比较序列的是A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，450&已知字符串S为“ abaabaabacacaabaabcc模式串t为“ abaabc '采用KMP算法进行匹配，第一次出现“失配”(s[i] != t[i]) 时，i=j=5, 则下次开始匹配时，i 和j 的值分别是A．i=1，j=0 B．i=5，j=0 C．i=5 ，j=2 D．i=6，j=29．下列排序算法中元素的移动次数和关键字的初始排列次序无关的是A .直接插入排序B .起泡排序C .基数排序D .快速排序10．已知小根堆为8，15，10，21，34，16，12，删除关键字8之后需重建堆，在此过程中，关键字之间的比较数是A. 1B. 2C. 3D. 411.希尔排序的组内排序采用的是()A .直接插入排序B .折半插入排序C .快速排序D .归并排序12.计算机硬件能够直接执行的是()I.机器语言程序n.汇编语言程序川.硬件描述语言程序A. 仅I B .仅I n C .仅I 川D. In出13.由 3 个“ 1 ”和5 个“ 0”组成的8位二进制补码, 能表示的最小整数是()A.-126 B . -125C. -32D. -314.下列有关浮点数加减运算的叙述中, 正确的是()I.对阶操作不会引起阶码上溢或下溢n.右规和尾数舍入都可能引起阶码上溢川.左规时可能引起阶码下溢I V 尾数溢出时结果不一定溢出A.仅n 川 B .仅inv C .仅I川V D. In川V15.假定主存地址为32 位，按字节编址，主存和Cache 之间采用直接映射方式，主存块大小为4 个字，每字32位，采用回写( Write Back )方式，则能存放4K 字数据的Cache 的总容量的位数至少是()A. 146kB. 147KC. 148KD. 158K16.假定编译器将赋值语句“x=x+3;转换为指令” add xaddt, 3,其'中xaddt是x对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，文档来源为:从网络收集整理.word 版本可编辑.欢迎下载支持且Cache使用直写(Write Through )方式，则完成该指令功能需要访问主存的次数至少是()文档来源为 :从网络收集整理 .word 版本可编辑 .欢迎下载支持A ． 0B ．1C ．2D ．317．下列存储器中，在工作期间需要周期性刷新的是() A ． SRAMB ．SDRAMC ．ROMD ．FLASH18．某计算机使用 4 体交叉存储器，假定在存储器总线上出现的主存地址(十进制)序 列为 8005， 8006，8007， 8008，8001，8002，8003，8004，8000，则可能发生发生缓存冲 突的地址对是()B ．8002、8007C ．8001、 8008D ．8000、8004 19．下列有关总线定时的叙述中，错误的是()A •异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制20. 若磁盘转速为 7200转/分，平均寻道时间为 8ms,每个磁道包含1000个扇区，则访 问一个扇区的平均存取时间大约是 ( )A. 8.1ms B . 12.2msC . 16.3msD . 20.5ms21. 在采用中断I/O 方式控制打印输出的情况下，CPU 和打印控制接口中的I/O 端口之 间交换的信息不可能是 ( )A .打印字符B .主存地址C .设备状态D .控制命令22. 内部异常(内中断)可分为故障(fault)、陷阱(trap)和终止(abort)三类。
2020 年西北大学 845 计算机专业基础综合（计算机网络与数据结构 , 各占50% ）考研精品资料一、重点名校考研真题汇编1．重点名校考研真题汇编①重点名校：计算机网络 2010-2018年考研真题汇编（暂无答案）②重点名校：数据结构2016-2018年考研真题汇编（暂无答案）二、 2020年西北大学 845计算机专业基础综合考研资料2．谢希仁、吴功宜《计算机网络》考研相关资料（ 1）谢希仁、吴功宜《计算机网络》[笔记+课件+提纲]①西北大学 845计算机专业基础综合之谢希仁、吴功宜《计算机网络》考研复习笔记。
②西北大学845计算机专业基础综合之谢希仁、吴功宜《计算机网络》本科生课件。
③西北大学845计算机专业基础综合之谢希仁、吴功宜《计算机网络》复习提纲。
（ 2）谢希仁、吴功宜《计算机网络》考研核心题库（含答案）①西北大学 845计算机专业基础综合考研核心题库之谢希仁、吴功宜《计算机网络》选择题精编。
②西北大学845计算机专业基础综合考研核心题库之谢希仁、吴功宜《计算机网络》简答题精编。
③西北大学845计算机专业基础综合考研核心题库之谢希仁、吴功宜《计算机网络》综合题精编。
（ 3）谢希仁、吴功宜《计算机网络》考研模拟题[仿真+强化+冲刺]①2020年西北大学845计算机专业基础综合之计算机网络考研专业课六套仿真模拟题。
②2020年西北大学845计算机专业基础综合之计算机网络考研强化六套模拟题及详细答案解析。
③2020年西北大学845计算机专业基础综合之计算机网络考研冲刺六套模拟题及详细答案解析。
3．耿国华《数据结构》考研相关资料（ 1）耿国华《数据结构》[笔记+课件+提纲]①西北大学 845计算机专业基础综合之耿国华《数据结构》考研复习笔记。
②西北大学845计算机专业基础综合之耿国华《数据结构》本科生课件。
③西北大学845计算机专业基础综合之耿国华《数据结构》复习提纲。
（ 2）耿国华《数据结构》考研核心题库（含答案）①西北大学 845计算机专业基础综合考研核心题库之耿国华《数据结构》选择题精编。
西北大学1999年研究生入学考试试题地理信息系统一、名词解释（共16分）1、地理信息2、拓朴结构3、空间数据编码4、数字地形模型（DTM）二、问答题（8个小题中任选7个，每小题均为10分，共计70分）1、在栅格数据结构中的点、线、面状几何图形是如何表示的？2、地理信息系统的数据模型包括哪些互相联系的方面？试举例说明。
3、什么是四叉树（或四元树）编码？它有哪些主要的优缺点？4、限制矢量数据结构表示身体图形精度的重要客观因素有哪些方面？5、在GIS应用系统中，数字模型起着什么作用？都有些什么特点？6、简述地理信息系统和遥感能够结合起来相辅相成的原因。
7、建立一个地理信息系统之初的可行性研究主要应包括哪些工作？8、什么是GIS数据库？与一般数据库相比较，它有哪些特点？三、计算（14分）完成矢量数据到栅格数据的转换。
已知转换图件的区域范围是Xmin=36589.41m,ymin=31324.51m;Xmax=40426.54m,ymax=31324.51m.全图网格矩阵总行数I=400，总列数J=700，试求某点状要素P（37631.08，30319.81）所在网格的行位置i 和列位置j.2001年研究生入学考试试题地理信息系统一、名词解释（共30分）1、投影转换2、空间数据拓朴关系3、元数据4、空间数据内差5、TIN6、ComGIS7、缓冲区分析8、NSDI9、DEM分辨率10、数字地球二、问答题（70分）1、试述空间数据库的概念、组织方式及特点。
（15分）2、属性数据编码的原则、内容与方法是什么？（15分）3、说明GIS中多层面信息叠置分析的基本方法及地学意义。
（20分）4、说明基于DEM进行地面水文信息提取的原理与方法，该方法的优点及存在的主要问题是什么？（20分）西北大学研究研究生入学考试试题2003年研究生入学考试试题名词解释：1：DLG2：局部拟合内插：3：航空相片投影差4：高斯——克里格投影5：几何特征点6：空间数据投影变换7：地物光谱8：信息融合问答题：1；何为元数据，元数据的功能和建立的原则、方法是什么？2：何为地学分析模型，如何才能在GIS中利用地学分析模型实现空间分析的目标？3：说明GIS软件的基本功能构成，并以三种常用GIS软件系统为例，说明各自的特点和优缺点。
2018年西北大学学硕814真题一、名词解释（每题5分，共20分）1、深度报道2、可穿戴终端3、新媒体新闻专题4、媒体组合二，简答题（在下列5道题中任选4道题，每题10分，共40分）1、批评性新闻的采写应该注意哪些问题？2、简述新媒体时代新传播的复合性。
3、网站与客户端新闻标题制作应该注意哪些特殊规律？4、创意发想过程采用水平思考法，应遵循哪些基本原则？5、长尾营销的出现受哪些因素的影响，其中社会化媒体的作用是什么？三、论述与评析题（在下列3道题中任选2道题，每题20分，共40分）1、新媒体融合报道背景下，新闻产品生产的各个环节，如信源获取，传播渠道，新闻加工，个性化服务的都发生着变化和创新，请结合实例谈谈其变化。
2、试论述人工智能技术对新闻生产和推送产生的影响。
3、2017年爱奇艺暑假档推出全新网络综艺节目《中国有嘻哈》，小众性的嘻哈音乐与嘻哈文化逐渐引起了更多的关注。
请评析《中国有嘻哈》节目受欢迎的原因。
四、写作题材料：据人力资源和社会保障部网站消息，日前，人社部、中组部、教育部、财政部、共青团中央联合印发《高校毕业生基层成长计划》。
人社部市场司负责人表示，《计划》提出，将基层高校毕业生纳入当地人才政策扶持范围，符合条件的提供住房、医疗、子女就读、落户、职称申报等方面配套支持。
各级各类人才表彰奖励项目进一步向基层一线倾斜，将基层高校毕业生纳入表彰奖励对象范围。
该负责人介绍称，《高校毕业生基层成长计划》主要面向以各种形式在基层服务工作的高校毕业生，力争用10年左右的时间，通过强化教育培训、实践锻炼、职业发展、管理服务等全链条的扶持措施，建设一支结构合理、素质优良、作风过硬的基层青年人才队伍。
通过建立分层次、多渠道的基层优秀青年后备人才选拔体系，有计划、有重点地遴选一批具有坚定政治信念、现代管理理念和管理能力的基层管理人才，一批具有钻研精神、专业知识水准和实践经验的基层专业技术人才，一批具有创新精神、市场意识和经营管理能力的基层创新创业人才。
西北大学2015年招收攻读硕士学位研究生试题(回忆版)科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
一、简答 [每小题6分，共30分]1、简述四类基本的数据逻辑关系，并用图表示。
2、简述数组、广义表属于线性表原因。
3、算法的定义及特性。
4、什么是平衡二叉排序树？平衡因子的取值范围是什么？5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。
二、分析与方法选择 [每小题10分，共30分]1、折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。
2、分析快速排序的性能（最好情况、最坏情况）。
3、关于二叉树结点度数的计算。
（牢记二叉树的5条性质，会计算二叉树及K 叉树相关的计算。
）三、构造结果 [每小题8分，共40分]1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。
备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。
但是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。
这道题具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。
2、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树的生成。
3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。
4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。
5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法。
四、编写算法 [每小题10分，共20分]1、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（n a a a ,,,21 ）逆置为（11,,,a a a n n ）。
科目名称：数据结构适用专业：计算机技术、软件工程答案请答在答题纸上，答在本试题上的答案一律无效。
一、 简答［每小题6分，共30分］1、 简述四类基本的数据逻辑关系，并用图表示。
2、 简述数组、广义表属于线性表原因。
3、 算法的定义及特性。
4、 什么是平衡二叉排序树？平衡因子的取值范围是什么？5、 简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并 证明。
二、 分析与方法选择［每小题10分，共30分］1、 折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。
2、 分析快速排序的性能（最好情况、最坏情况）。
3、 关于二叉树结点度数的计算。
（牢记二叉树的5条性质，会计算二叉树及 K 叉树相关的计算。
）三、 构造结果［每小题8分，共40分］1、 已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。
备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列， 写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。
但是 2015年 试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都 没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯 一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。
这道题 具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。
2、 图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生 成树的生成。
3、 依次输入（26, 30，15, 10, 28，19, 18，22），构造二叉排序树，并计算等 概率情况下的查找成功的平均查找长度。
4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。
科目代码：851 共2页5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法四、编写算法 [ 每小题 10分，共 20 分]1、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表( a1,a2, ,a n )逆置为( a n,a n 1, , a1 )。
西北大学的计算机专业一直是学校的优势学科，大三的时候，我就决定有机会一定要继续留在这里继续攻读研究生，继续深造，为自己今后走向社会再添一笔筹码。
政治参考资料：李凡《政治新时器》和配套题，线上视频课考研前，就对政治的复习有一个清楚的认识，也知道自己在类似哲学理论方面比较欠缺，所以计划考研时，就认真对政治的复习做了规划，在书店泡了一天，把市面上的参考资料都大致看了一遍，进行了对比，最后才根据自己的需要选择了合适的参考资料。
根据我自己在学习中比较慢热的个性，所以早早决定开始过一遍资料，首先用到的就是《政治新时器》，这本参考资料比较厚实，内容也比较全面，也可以作为后期复习中的参考来查阅，第一遍的复习，我主要是围绕着这本书进行的，从头到尾不放过任何一个知识点，每天给自己定一个小目标，完成计划的复习任务，政治复习中有些理论方面的知识确实比较无聊，讲的也比较空洞，没有关系，先过一遍，脑海中有一个具体的构架还让分类，再用后续的复习过程把内容填满就可以。
有了第一遍基础知识做铺垫，第二遍复习时就可以引入练习题了，我买了一本李凡600题进行练习，看书的时候感觉什么都看懂了，一做题才发现很多知识点根本没有掌握，遇到不会或者做错的题目时，回过来再翻翻书，找到对应的知识点，熟读、熟记，更容易掌握，也知道这个知识点一般的考察范围了。
通过习题掌握了知识点后，就可以开展实战模拟练习了，可以找来历年的真题，在特定的时间内，给自己规定完成一定的练习量，模拟考场上情景，一直到考前，让我们一直保持对考题的敏感性。
除了选择题通过练习可以巩固外，大题更需要们来背诵进行加强，押题卷中的大题都可以用来进行考前背诵，给考试是答大题积累一些素材。
资料：《一本单词》、《木糖英语真题手译版》、历年真题，蛋核英语公众号除了专业课外，公共课里面我最喜欢的课程就是英语了，女孩天生对学语言有一种天赋，我自己认为我的英语语感还是很不错的，所以对英语学习，也是比较积极，没有觉得这是一项任务，而当成自己的爱好来学。
西北大学计算机专硕研究生入学考试历年真题集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY-西北大学2015年招收攻读硕士学位研究生试题(回忆版) 科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
一、简答 [每小题6分，共30分]1、简述四类基本的数据逻辑关系，并用图表示。
2、简述数组、广义表属于线性表原因。
3、算法的定义及特性。
4、什么是平衡二叉排序树平衡因子的取值范围是什么5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。
二、分析与方法选择 [每小题10分，共30分]1、折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。
2、分析快速排序的性能（最好情况、最坏情况）。
3、关于二叉树结点度数的计算。
（牢记二叉树的5条性质，会计算二叉树及K叉树相关的计算。
）三、构造结果 [每小题8分，共40分]1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。
备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。
但是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。
这道题具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。
2、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树的生成。
3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。
4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。
5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法。
西北大学2015年招收攻读硕士学位研究生试题(回忆版)科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
一、简答 [每小题6分，共30分]1、简述四类基本的数据逻辑关系，并用图表示。
2、简述数组、广义表属于线性表原因。
3、算法的定义及特性。
4、什么是平衡二叉排序树？平衡因子的取值范围是什么？5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。
二、分析与方法选择 [每小题10分，共30分]1、折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。
2、分析快速排序的性能（最好情况、最坏情况）。
3、关于二叉树结点度数的计算。
（牢记二叉树的5条性质，会计算二叉树及K 叉树相关的计算。
）三、构造结果 [每小题8分，共40分]1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。
备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。
但是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。
这道题具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。
2、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树的生成。
3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。
4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。
5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法。
四、编写算法 [每小题10分，共20分]1、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（n a a a ,,,21 ）逆置为（11,,,a a a n n ）。
（记得不太清楚了，反正就是耿国华《数据结构》第2章习题中的一道程序题。
）2、在中序线索树中找结点前驱（或在中序线索树中找结点后继）。
（课本上的源程序。
）五、编写算法 [共15分]这道题忘记了。
反正我这道题不太会做，但是也程序写的满满的。
记住即使不会做，也得写，写的满满的较好。
只要你写老师都给分，估计给个10来分吧。
如果你不答，空着的话，就只能得0分了。
六、编写算法 [共15分]编写算法，实现哈希链表的存储，哈希函数是H(k)=k%p ，哈希表长为m ，p 为小于等于m 的最大素数。
处理冲突的方法采用线性探测再散列。
备注：我这道题也不太会做，但是也程序写的满满的。
记住即使不会做，也得写，写的满满的较好。
只要你写老师都给分，估计给个10来分吧。
如果你不答，空着的话，就只能得0分了。
西北大学2014年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
一、简答 [每小题6分，共30分]1、简述四类基本的数据逻辑关系，并用图表示。
2、特殊矩阵的压缩原则有哪些？3、什么是平衡二叉排序树？平衡因子的取值范围是什么？4、具有n个结点的k叉树，若采用k叉树链表存储，则空链域有多少个？（写出求解步骤）。
5、递归进层时需要做哪些事？二、分析与方法选择 [每小题10分，共30分]1、在10000个元素中，欲找出10个最大的元素，采用哪些排序方法较好。
简述原因。
2、在一个连通无向图上，欲求顶点vi到顶点vj（vjvi ）的最短简单路径，应采用深度优先遍历还是广度优先遍历？简述原因。
3、分析冒泡排序的性能（最好情况、最坏情况）。
三、构造结果 [每小题6分，共30分]1、已知一棵二叉树的前序遍历的结果是ABDCEGF，中序遍历的结果是BDAEGCF，试画出这课二叉树，并将其转换为相应的森林。
2、假设T是一棵高度为5的二叉树，T中只有度为0和度为2的结点，给出：（1）T树可能的最大结点数，并画出这样的一棵二叉树。
（2）T树可能的最小结点数，并画出这样的一棵二叉树。
3、依次输入（26，30，15，10，28，19，18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。
4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。
5、已知关键字集合：{50，52，85，22，96，17，36，55}，以第一个关键字中轴元素，写出一趟快速排序的结果。
四、编写算法 [每小题10分，共30分]1、编写算法void Adjust(LinkList L)，其功能是：以第一个元素为基准，将小于该元素的结点全部放到前面，大于该元素的结点全部放到其后。
2、要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag，以tag为0或1来区分头尾指针相同时的列状态的空与满，请编写与此结构相应的出队算法。
3、二叉树采用二叉链表结构存储，编写算法实现统计二叉树中的结点个数。
五、编写算法 [共15分]二叉树采用二叉链表结构存储，编写实现二叉树后序线索化的算法。
六、编写算法 [共15分]编写算法，由依次输入的顶点数、弧数和各顶点信息、弧信息建立有向图的邻接表存储结构。
西北大学2013年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 算法描述采用类语言，算法应加上必要的注释一、简答问题（共30分，每小题5分）1、线性结构与非线性结构的差别。
2、说明在图的遍历中，设置访问标志数组的作用。
3、简述数组和字符串属于线性表的原因。
4、算法特性与算法时间复杂度。
5、数据类型与抽象数据类型。
6、简述稳定排序含义，给出一种不稳定排序方法名称并证明。
二、方法选择（共10分，每小题5分）1、设有10000个无序元素，要求找出前30个最大元素，在下列排序方法（归并排序、基数排序、快速排序、堆排序、插入排序）中哪些方法最好，为什么？2、在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，简述应使用哪种排序方法最好。
三、构造结果：（共40分，每小题8分）1、给定叶结点权值：（3，4，5，6，7，8，9），构造哈夫曼树，并计算其带权路径长度。
2、已知一二叉树中序序列为BDCAEF，前序序列为ABCDEF，给出其对应的二叉树。
3、已知二维数组A[100][200]采用行序为主方式存储，每个元素占K个存储单元，已知A[0][0]的存储地址是1500，给出A[60][80]的存储地址。
4、给出12个结点的折半判定树，并计算其在等概率情况下的平均查找长度。
5、在地址空间0—12的散列区中，对以下关键字序列：（Jan，Feb，Apr，May，Jun，Jul，Aug，Sep，Oct）建哈希表，设哈希函数为H(X)=i/2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。
四、编写算法（20分）设主串s和子串t分别以单链表存储，t和s中的每个字符均用一结点表示（如图）。
实现在链式存储方式下的模式匹配，即求子串t在主串s中第一次出现的位置指针。
五、编写算法（20分）已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列，编写算法达到要求结果。
六、编写算法（20分）无向图采用邻接表方式存储，编写出广度优先遍历访问的算法。
七、编写语句（10分）在前序线索树中要找出X结点的后继结点。
西北大学2012年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 算法描述可选用类语言，并加上必要的注释一、简答问题【30分，每小题6分】1、简述数组、广义表属于线性表原因。
2、算法特性与算法时间复杂度。
3、线性结构与非线性结构的差别。
4、图遍历中设置访问标志数组的作用。
5、数据类型的含义与作用。
二、方法选择【20分，每小题10分】1、只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（K<<N），列出2种速度快的方法名称与原因。
2、在数轴上有n个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1—N。
试问：要查找某个给定值x所在区间，你认为应选择什么方法查找最快，简述原因。
三、写出要求结果【共40分，每小题8分】1、已知计算阿克曼递归函数定义如下：Akm(int m，int n){if(m==0) return(n+1)；else if(n==0) return(akm(m-1，1));else return(akm(m-1，akm(m，n-1)))；}请给出执行Akm(2，1)时，递归调用顺序及执行结果。
2、已知关键字序列为：（75，33，52，41，12，88，66，27）哈希表长为10，哈希函数为：H(K)=K MOD 7，解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。
3、给定权值{8，12，4，5，26，16，9}，构造一棵哈夫曼树，并计算其带权路径长度。
4、在中序线索树中，要找出X 结点的前驱结点，请写出相关函数定义。
5、已知一棵二叉树，其中序序列BDAEC ，后序序列DBECA ，构造该二叉树。
四、编写算法 【15分】要求实现在链式存储方式下的模式匹配。
已知主串s 和子串t 分别以单链表存储，t 和s 中每个字符均用一结点表示（如图）五、编写算法 【共30分，每小题15分】（1）要求二叉树按二叉链表存储，写建立一棵二叉树的算法。
[15分]（2）编写输出二叉树中的非叶子结点的算法。
[15分]六、编写算法 【15分】已知有N 个结点的无向图，采用邻接表结构存储，要求编写算法实现广度优先搜索策略遍历图中所有顶点。
西北大学2011年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：849适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。
[注] 编写程序可选用C语言；算法描述采用类语言，应加上必要的注释；所有答案均要求写在答题纸上。
一、简答问题（每小题6分，共30分）1、四类数据结构名称及其关系图示。
2、为什么说数组和广义表是线性表的推广？3、算法的定义与特性。
4、数据类型与抽象数据类型。
5、图遍历算法中设置访问标志数组的作用。
