西北大学851数据结构2014年考研专业课真题试卷

格式：pdf
大小：496.44 KB
文档页数：2

下载文档原格式

西北大学信息科学与技术学院851数据结构[专业硕士]历年考研真题专业课考试试题

第一部分历年考研真题汇编
2002年西北大学信息科学与技术学院449数据结构[专业硕士]考研真题
2001年西北大学信息科学与技术学院数据结构[专业硕士]考研真题（回忆版）
第二部分兄弟院校真题汇编
2011年厦门大学845数据结构考研真题
2009年厦门大学845数据结构考研真题
目录
第一部分历年考研真题汇编 2002年西北大学信息科学与技术学院449数据结构[专业硕士]考研真题 2001年西北大学信息科学与技术学院数据结构[专业硕士]考研真题（回忆版）
第二部分兄弟院校真题汇编 2011年厦门大学845数据结构考研真题 2009年厦门大学845数据结构考研真题 2008年厦门大学845数据结构考研真题 2006年厦门大学496数据结构考研真题
Hale Waihona Puke 2008年厦门大学845数据结构考研真题
2006年厦门大学496数据结构考研真题

西北民族大学数据结构题库(1)

20.是对客观事物的符号表示，能被计算机处理的符号总称。
21.数据的存储结构通常包括数据的_________存储和_________存储。
22.数据的逻辑结构可形式地用一个二元组S＝(D，R)来表示，其中D是__________，R是__________。
23.所有插入和删除都在表的一端进行的线性表称为。
C 、两个串的长度相等，并且两个串包含的字符相等。
D、两个串的长度相等，并且对应位置上的字符相等。
19.已知广义表L=(a,(b,c)),其表头是( )。
A.aB.bC.(a,b)D.(c,d)
20.广义表((a,b),c,d)的表尾是( )。
A.aB.bC.(a,b)D.(c,d)
21.树最适合用来表示( )。
34.设广义表L=（a，（a，b），d，e,（（i，（j）），k）），则L的深度是,表头为，表尾是。
35.空格串是指由__________符所组成的字符串。
36.数据结构包括_________三个方面。
37.当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应该采用__________存储结构
D.77
5.无向图G=（V,E），其中：V={(a,b),(a,e),(a,c),(b,e),(e,f),(f,d),(e,d)},在下面的5个序列中，符合深度优先遍历的序列有多少？（）
（1）a e b d f c（2）a c f d e b（3）a e d f c b（4）a e f d c b（5）a e f d b c
C.p->next=p->next
D.p=p->next->next
3.设高度为15的二叉树上只有度为0和1的结点，则此类二叉树中所包含的结点数至少为（）。

2014考研计算机真题及答案解析(详细)

有数据发送；乙每收到一个数据段都会发出一个接收窗口为 10 KB 的确认段。若甲在 t 时刻
发生超时时拥塞窗口为 8 KB，则从 t 时刻起，不再发生超时的情况下，经过 10 个 RTT 后，
甲的发送窗口是（）。
A． 10 KB
B．12 KB
C．14 KB
D．15 KB
39．下列关于 UDP 协议的叙述中，正确的是（）。
C．14.0 秒
D．16.8 秒
13．若 x=103,y=-25，则下列表达式采用 8 位定点补码运算实现时，会发生溢出的是
（）。
A． x+y
B．-x+y
C．x-y
D．-x-y
14．float 型数据通常采用 IEEE 754 单精度浮点格式表示。假定两个 float 型变量 x 和 y 分别
存放在 32 位寄存器 f1 和 f2 中，若(f1)=CC90 0000H,(f2)=B0C0 0000H,则 x 和 y 之间的关系
A．状态端口和控制端口可以合用同一个寄存器
B．I/O 接口中 CPU 可访问的寄存器称为 I/O 端口
C．采用独立编址方式时，I/O 端口地址和主存地址可能相同
D．采用统一编址方式时，CPU 不能用访存指令访问 I/O 端口
22．若某设备中断请求的响应和处理时间为 100 ns，每 400 ns 发出一次中断请求，中断响应
3．循环队列存放在一组数组 A[0..M-1]中，end1 指向队头元素，end2 指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳 M-1 个元素，初始时为
空。下列判断队空和队满的条件中，正确的是（）。
A．队空：end1 = = end2；队满：end1 = = (end2+1) mod M

2014计算机考研真题(操作系统部分)

2014年计算机学科研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲Ⅰ. 考试性质计算机学科专业基础综合考试是为高等院校和科研院所招收计算机科学与技术学科的硕士研究生而设置的具有选拔性质的联考科目，其目的是科学、公平、有效地测试学生掌握计算机科学与技术学科大学本科阶段专业基础知识、基本理论、基本方法的水平和分析问题、解决问题的能力，评价的标准是高等院校计算机科学与技术学科优秀本科毕业生所能达到的及格或及格以上水平，以利于各高等院校和科研院所择优选拔，确保硕士研究生的招生质量。

Ⅱ. 考查目标计算机学科专业基础综合考试涵盖数据结构、计算机组成原理、操作系统和计算机网络等学科专业基础课程。

要求考生系统地掌握上述专业基础课程的基本概念、基本原理和基本方法，能够综合运用所学的基本原理和基本方法分析、判断和解决有关理论问题和实际问题。

Ⅲ. 考试形式和试卷结构一、试卷满分及考试时间本试卷满分为150分，考试时间为180分钟二、答题方式答题方式为闭卷、笔试三、试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分Ⅳ. 考查内容操作系统【考查目标】1. 掌握操作系统的基本概念、基本原理和基本功能，理解操作系统的整体运行过程。

2. 掌握操作系统进程、内存、文件和I/O管理的策略、算法、机制以及相互关系。

3. 能够运用所学的操作系统原理、方法与技术分析问题和解决问题，并能利用C语言描述相关算法。

一、操作系统概述（一）操作系统的概念、特征、功能和提供的服务（二）操作系统的发展与分类（三）操作系统的运行环境1. 内核态与用户态2. 中断、异常3. 系统调用（四）操作系统体系结构二、进程管理（一）进程与线程1. 进程概念2.进程的状态与转换3.进程控制4.进程组织5.进程通信共享存储系统，消息传递系统，管道通信。

西北大学2016年数据结构考研真题851与参考答案

5.已知关键字集合：{19，13，20，11，23，27，16，30}，分别写出简单选择排序和直接插入排序的前三趟排序结果。
四、编写算法[每小题10分，共20分]
1.某顺序表中的元素为整型，设第一个元素为key。编写尽可能高效的算法，将小于等于key的元素全部放在其前面，大于key的元素全部放在其后面。
2.在二叉排序树中查找关键字为key的结点。若找到，返回该结点的地址；否则返回NULL。
五、编写算法[共15分]
对带头结点的单链表Head进行简单选择排序，排序后结点值从小到大排序。
六、编写算法[共15分]
某有向图采用邻接表存储，编写算法输出该图的拓扑序列。
2.折半查找的前提条件是什么？
3.在图的遍历过程中，访问标志数组visited[]如何防止结点被遗漏访问和重复访问的？
4.简述排序的稳定性，列举至少2个稳定的排序算法和2个不稳定排序算法。
二、分析[每小题10分，共30分]
1.若一个具有n个结点、k条边的非连通无向图是一个森林（n〉k），则该森林包含多少棵树？
西北大学2016年招收攻读硕士学位研究生试题与参考答案
科目名称：数据结构科目代码：851
适用专答在本试题上的答案一常无效。
【注】算法描述可采用类语言描述，写清注释。
一、简答[每小题5分，共20分]
1.栈、队列和字符串都是限定性线性表，它们各自有什么限定？
2.设有10000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则快速排序、简单选择排序、堆排序、直接插入排序、归并排序中，哪些排序方法效率较高，简要说明理由。
3.分析冒泡排序的最好情况和最坏情况性能。
三、构造结果[每小题10分，共50分]

2014计算机考研真题完整版

2014考研统考计算机基础综合真题解析一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

2、假设栈初始为空，将中缀表达式a/b-(c*d+e*f)/g 转化为等价后缀表达式过程中，当扫描到f 时，栈中的元素依次为：A 、+（*-B 、+（-*C 、/+(*-*D 、/+-*涉及考点：考察中缀和后缀表达式的转化，并考察栈这种数据结构4、如下图二叉树进行中序线索化，则元素X 的左、右线索指向的元素为A 、 ecB 、 eaC 、 dcD 、 ba涉及考点：中序线索化二叉树，找出左右线索5、森林F 转化为对应二叉树T ，则F 的叶结点个数是（）A 、T 的叶结点个数B 、T 中度为1的结点个数C 、T 的左孩子指向为空的个数D 、T 的右孩子指向为空的个数涉及考点：森林转化为二叉树做法：第一，断开除最左孩子的孩子节点，第二，连接孩子节点中各兄弟节点，第三，将树顺时针旋转45度第四，同理处理其他树。

第五，将所有树按照先后顺序依次作为右子树连接。

6、5个元素有4种编码方案，下列不是前缀编码的是A 、01,0000,0001,001,1B 、011,000,001,010,1 ac bdx eC、000,001,010,011,100D、0,100,110,1110,1100涉及考点：字符的前缀编码8、用哈希（散列）方法处理冲突（碰撞）时可能发生堆积（聚集)现象，则下列会直接受到堆积现象影响的是A、存储效率B、散列函数C、载运因子D、平均查找长度涉及考点：哈希（三列）方法处理冲突堆积现象影响的因素9、存一棵具有15个关键词的4阶B树，则含有关键词的结点可能有A、5B、6C、10D、15涉及考点：B树10、用希尔排序法，对一列数据序列排序时，若第一次排序结果为：9,1,4,13,7,8,20,23,15，则该排序可能的间隔是：A、2B、3C、4D、5涉及考点：希尔排序法中的间隔11、下列最不可能是快速排序第二轮的结果是A、2,3,5,4,6,7,9B、2,7,5,6,4,3,9C、3,2,5,4,7,6,9D、4,2,3,5,7,6,9涉及考点：快速排序法12、程序P在装置M执行时间为20秒，编译优化后，P执行的指令数是以前的70%，但CPI 为以前的1.2倍，则现在P在M上的执行时间为A、8.4秒B、11.7秒C、14.0秒D、16.8秒涉及考点：cpu计算时间的计算方法。

西北大学数据结构考试试题

2000年A卷一、简答问题：（每小题4分，共16分）1．四类数据结构2．线性结构与非线性结构有何差别？3．简述算法的定义与特性。

4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打。

1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树：若它的左子树非空，则根结点的值大于其左孩子的值，若它的右子树非空，则根结点的值大于其右孩子的值。

2．（）索引顺序表的特点是块内可无序，块间要有序。

3．（）子串是主串中任意个连续字符组成的序列。

4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。

5．（）快速排序的枢轴元素可以任意选定。

三、单项选择题：(每小题1分，共4分)1．栈S最多能容纳4个元素。

现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列?A)E、D、C、B、A、F B)B、C、E、F、A、DC)C、B、E、D、A、F D)A、D、F、E、B、C2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：A、98B、99C、50D、483. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是：A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9}B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30}4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。

与森林F对应的二叉树根结点的右子树上的结点个数是：A）M1 B）M1+M2 C）M3 D）M2+M3四、填空题：(每小题2分,共 20分)1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选2．N个结点的二叉树采用二叉链表存放，共有空链域个数为3．单链表与多重链表的区别是4．在各种查找方法中，平均查找长度与结点个数无关的是5．深度为6（根层次为1）的二叉树至多有个结点。

西北大学计算机专硕研究生入学考试历年真题

西北大学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 ）。

《数据结构》历年考研真题及解答

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

西北大学计算机专硕研究生入学考试历年真题图文稿

西北大学计算机专硕研究生入学考试历年真题集团文件发布号：（9816-UATWW-MWUB-WUNN-INNUL-DQQTY-西北大学2015年招收攻读硕士学位研究生试题(回忆版) 科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。