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

1、西北大学 2015 年招收攻读硕士学位研究生试题(回忆版)科目名称：数据结构科目代码：851适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。一、简答 每小题 6 分，共 30 分1、简述四类基本的数据逻辑关系，并用图表示。2、简述数组、广义表属于线性表原因。3、算法的定义及特性。4、什么是平衡二叉排序树？平衡因子的取值范围是什么？5、简述稳定排序含义，给出两种稳定排序方法以及两种不稳定排序方法名称并证明。10301、折半查找法对待查找的列表哪两个要求？答：必须采用顺序存储结构；必须按关键字大小有序排列。2、分析快速排序的性能（最好情况、最坏情况。3、关于二叉

2、树结点度数的计算。（牢记二叉树的 5 条性质，会计算二叉树及 K叉树相关的计算。）三、构造结果 每小题 8 分，共 40 分1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。20152、图的两种存储结构及表示、深度优先搜索遍历、广度优先搜索遍历、最小生成树的生成。3、依次输入263015102819182概率情况下的查找成功的平均查找长度。4105、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法。四、编写算法 每小题 10 分，共 20 分1、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a a12,an）逆置为（an,a,an 11（记得不太清楚了，

3、反正就是耿国华数据结构第 2 章习题中的一道程序题。）2、在中序线索树中找结点前驱（或在中序线索树中找结点后继（）五、编写算法 共 15 分这道题忘记了。反正我这道题不太会做，但是也程序写的满满的。记住即使100六、编写算法 共 15 分编写算法，实现哈希链表的存储，哈希函数是 H(k)=k%p，哈希表长为 m，p为小于等于 m 的最大素数。处理冲突的方法采用线性探测再散列。100西北大学 2014 年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。一、简答 每小题 6 分，共 30 分1、简述四类

4、基本的数据逻辑关系，并用图表示。2、特殊矩阵的压缩原则有哪些？3、什么是平衡二叉排序树？平衡因子的取值范围是什么？4nkk？（出求解步骤。5、递归进层时需要做哪些事？二、分析与方法选择 每小题 10 分，共 30 分1、在10000 个元素中，欲找出10 个最大的元素，采用哪些排序方法较好。简述原因。2、在一个连通无向图上，欲求顶点vi到顶点vivj）的最短简单路径，采用深度优先遍历还是广度优先遍历？简述原因。3、分析冒泡排序的性能（最好情况、最坏情况。三、构造结果 每小题 6 分，共 30 分1ABDCEGF，BDAEGCF， 试画出这课二叉树，并将其转换为相应的森林。2T5，T02（1）T

5、（2）T3、依次输入263015102819182概率情况下的查找成功的平均查找长度。4105、已知关键字集合：50，52，85，22，96，17，36，55，以第一个关键字中轴元素，写出一趟快速排序的结果。四、编写算法 每小题 10 分，共 30 分1、编写算法 void Adjust(LinkList L)，其功能是：以第一个元素为基准，将小于该元素的结点全部放到前面，大于该元素的结点全部放到其后。2、要求循环队列不损失一个空间全部都能得到利用，设置一个标志域 tag，tag01出队算法。3、二叉树采用二叉链表结构存储，编写算法实现统计二叉树中的结点个数。五、编写算法 共 15 分二叉树采

6、用二叉链表结构存储，编写实现二叉树后序线索化的算法。六、编写算法 共 15 分编写算法，由依次输入的顶点数、弧数和各顶点信息、弧信息建立有向图的邻接表存储结构。西北大学 2013 年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。注 算法描述采用类语言，算法应加上必要的注释一、简答问题 （3051、线性结构与非线性结构的差别。2、说明在图的遍历中，设置访问标志数组的作用。3、简述数组和字符串属于线性表的原因。4、算法特性与算法时间复杂度。5、数据类型与抽象数据类型。6、简述稳定排序含义，给出一种不稳

7、定排序方法名称并证明。二、方法选择 （共 10 分，每小题 5 分）1、设有10000 个无序元素，要求找出前30 个最大元素，在下列排序方法（归并排序、基数排序、快速排序、堆排序、插入排序）中哪些方法最好，为什么？2、在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，简述应使用哪种排序方法最好。（共40分，每小题8分）1、给定叶结点权值（3456789径长度。23A100200KA001500，A6080的存储地址。4、给出 12 个结点的折半判定树，并计算其在等概率情况下的平均查找长度。5012， Jun，Jul，Aug，Sep，Oct）建哈希表，设哈

8、希函数为H(X)=i/2，其中i四、编写算法 （20 分）sttsdataNext（如图dataNextts置指针。五、编写算法 （20 分）已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列，编写算法达到要求结果。六、编写算法 （20 分）无向图采用邻接表方式存储，编写出广度优先遍历访问的算法。七、编写语句 （10 分）在前序线索树中要找出 X 结点的后继结点。LtagLtagLcDataRtagRc西北大学 2012 年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一

9、律无效。注 算法描述可选用类语言，并加上必要的注释一、简答问题 【30 分，每小题 6 分】1、简述数组、广义表属于线性表原因。2、算法特性与算法时间复杂度。3、线性结构与非线性结构的差别。4、图遍历中设置访问标志数组的作用。5、数据类型的含义与作用。二、方法选择 【20 分，每小题 10 分】1NK22n1Nx应选择什么方法查找最快，简述原因。4081、已知计算阿克曼递归函数定义如下：Akm(int m，int n)if(m=0)return(n+1)；else if(n=0)return(akm(m-1，1); elsereturn(akm(m-1，akm(m，n-1)；请给出执行 Akm

10、(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，构造一棵哈夫曼树，并计算其带权路径长度。LtagLcLtagLcDataRtagRc5、已知一棵二叉树，其中序序列 BDAEC，后序序列 DBECA，构造该二叉树。四、编写算法 【15 分】要求实现在链式存储方式下的模式匹配。st，tsdataNextdataNext即求：子串 t 在主串 s

11、中第一次出现的位置指针。五、编写算法 【共 30 分，每小题 15 分】要求二叉树按二叉链表存储，写建立一棵二叉树的算法。15编写输出二叉树中的非叶子结点的算法。15六、编写算法 【15 分】N先搜索策略遍历图中所有顶点。西北大学 2011 年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：849适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。注 编写程序可选用 C 语言；算法描述采用类语言，应加上必要的注释； 所有答案均要求写在答题纸上。一、简答问题 （每小题 6 分，共 30 分）1、四类数据结构名称及其关系图示。2、为什么说数组和广义表是线性表的

12、推广？3、算法的定义与特性。4、数据类型与抽象数据类型。5、图遍历算法中设置访问标志数组的作用。二、方法选择 （每小题 10 分，共 20 分）1、快速排序方法的最坏最好情况是什么，简要分析说明理由。2、二叉排序树中结点各不相同，欲得到一个由大到小的结点值递减序列，你认为应当采用什么方法，便可得到要求结果，简述原因。三、构造结果 （每小题 8 分，共 40 分）1、给定叶结点权值235611长度。2、已知一二叉树中序序列 BDCAEF，前序序列 ABCDEF，给出其对应的二叉树。3AMNKAij式。4、在地址空间 012 的散列区中，对以下关键字序列：（Jan，Feb，Apr，May，Jun，

13、Jul，Aug，Sep，Oct）建哈希表，设哈希函数为i功与不成功的平均查找长度。5Nhanoihanoi(int n，char x，char y，char z)if(n=1)elsehanoi(n-1，x，z，y)； move(x，n，z)； hanoi(n-1，y，x，z)；move四、编写算法 （每小题 15 分，共 30 分）1、编写建立二叉树算法，要求二叉树按照二叉链表方式存储。 15 分2、已知二叉树采用二叉链表存储，要求编写算法，完成计算出二叉树中度为0、度为 1 的结点数目。 15 分（15要求实现如下功能：1、键盘输入 N 个有序整数，建立数组存储；2、输入关键字 key，完

14、成折半查找的功能。六、编写算法 （15 分）已知二叉树采用二叉链表存储，编写算法实现按层次遍历二叉树。西北大学 2010 年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：848适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。注 编写程序可选用 C 语言，所有答案均要求写在答题纸上。3061、简述字符串、栈属于线性表原因。2、线性结构与非线性结构的差别。3、算法定义与算法特性。4、数据类型与抽象数据类型。5、图遍历中设置访问标志数组的作用。20101、说明稳定排序含义，并给出一种不稳定排序方法的名称与证明。2、在一个连通无向图上，欲求从一点Vi到另一点

15、V （Vji V ）所经结点数目短j你认为最好选择哪种方法为基础，简述原因。三、构造结果 共 40 分，每小题 8 分1、构造 10 个结点的折半判定树，并计算查找成功的平均查找长度。2BDAEC，DBECA，给出其对应的二叉树。3nA（ijaij0，按照压缩存储的思想，可以主对角线以下所有元素（包括主对角线上的元素）BBaij存放位置的公式。4、二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得到一个由小到大的结点值递增序列，简述处理方法思路。5Nhanoihanoi(int n，char x，char y，char z)if(n=1)elsehanoi(n-1，x，z，y)； mov

16、e(x，n，z)； hanoi(n-1，y，x，z)；move四、编写程序 共 15 分要求实现如下功能：将数组 C1:n中所有奇数移到偶数之前，要求时间复杂度为 O(n)。五、编写算法 共 30 分，每小题 15 分写一个建立二叉树的算法，要求二叉树按二叉链表存储。fchdatafchdatansib树采用孩子兄弟存放，结点结构为其中 fch 表示指向第一个孩子，nsib 表示指向下一个兄弟。编写算法，要求由根开始逐层输出树中的各条边，边输出格式为（K K 。ij例：ABCDEFG输出为：AB，AC，AD，BE，BF，CG。西北大学 2014 年招收攻读硕士学位研究生试题科目名称：软件工程学

17、科专业基础综合科目代码适用专业：计算机系统结构 计算机应用技术共2页信息安全软件工程数据结构试题（75）一、简答问题 （1551、简述队列、广义表属于线性表原因。2、排序稳定性的定义及证明不稳定排序的方法举例。3、简述图的两类存储名称及结构示意。二、写出要求结果 （共 20 分，每小题 5 分）111H(K)=(K)MOD若输入顺序为DBATNMCIIKXTA，处理冲突方法为线性探测再2500010（并排序、冒泡排序、快速排序、堆排序、插入排序）中哪些方法快，为什么？3DBCAFGE，ABDCEFG，构造该二叉树。485，25，3，6，10，11，36，48。三、编写算法 （共 10 分）12

18、四、编写算法 （共 15 分）1、键盘输入一组非零的整数序列，最后输入零为结束标志，要求根据输入建立一棵二叉排序树算法，采用二叉链表方式存放。 （10 分）2、给出按由大到小顺序输出此二叉排序树中结点值的算法。 （5 分）五、编写算法 （共 15 分）已有无向图采用邻接表结构存储，要求按广度优先搜索策略编写求出所有连通子图的生成树（生成树中的边用（V ij）格式输出。西北大学 2013 年招收攻读硕士学位研究生试题科目名称：软件工程学科专业基础综合科目代码适用专业：计算机系统结构 计算机应用技术共2页注 编写程序可选用 C 语言，算法描述采用类语言，算法应加上必要的注释。数据结构试题（75）一、简答问题 （共 15 分，每小题 5 分）1、简述数据类型和抽象数据类型的含义与关系。2、简述数组、广义表属于线性表原因。3、说明在图的遍历中，设置访问标志数组的作用。二、写出要求结果 （共 20 分，每小题 5 分）1DBCAFGE，DCBGFEA，构造该二叉树。2、快速排序方法的最坏最好情况是什么，简要分析说明理由。3、已知关键字序列为：（75，33，52，41，12，88，66，27）哈希