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

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

2、条性质，会计算二叉树及K叉树相关的计算。）三、构造结果每小题8分，共40分1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。备注：西大历年试卷都是给出前序序列、中序序列或者中序序列、后序序列，写出对应的二叉树，这种题型很好做，且结果给出的二叉树唯一。但是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题我们平时几乎都没做过，但是其实也不难，往往给出前序序列、后序序列，构造的二叉树不是唯一的，但是这次考题设置的巧妙，最后给出的结果二叉树应该是唯一的。这道题具体我也不记得了，反正有点难，我也花了很长时间最后才做出来的。2、图的两种存储结构及表示、深度优先搜索遍历、广度优先

3、搜索遍历、最小生成树的生成。3、依次输入（26,30，15,10,28，19,18，22），构造二叉排序树，并计算等概率情况下的查找成功的平均查找长度。4、画出10个元素的折半判定树，并计算等概率情况下查找成功的平均查找长度。5、最小生成树生成的两种算法：普里姆算法、克鲁斯卡尔算法四、编写算法每小题10分，共20分1、以单链表作存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（al7a2"f,an）逆置为（an,an丄,a1）°（记得不太清楚了，反正就是耿国华数据结构第2章习题中的一道程序题。）2、在中序线索树中找结点前驱（或在中序线索树中找结点后继）。（课本上

4、的源程序。）五、编写算法共15分这道题忘记了。反正我这道题不太会做，但是也程序写的满满的。记住即使不会做，也得写，写的满满的较好。只要你写老师都给分，估计给个10来分吧。如果你不答，空着的话，就只能得0分了。六、编写算法共15分编写算法，实现哈希链表的存储，哈希函数是H（k）=k%p，哈希表长为mP为小于等于m的最大素数。处理冲突的方法采用线性探测再散列。备注：我这道题也不太会做，但是也程序写的满满的。记住即使不会做，也得写，写的满满的较好。只要你写老师都给分，估计给个10来分吧。如果你不答，空着的话，就只能得0分了。科目代码：852共2页科目名称：数据结构适用专业：计算机技术、软件工程答案请

5、答在答题纸上，答在本试题上的答案一律无效。一、简答每小题6分，共30分1、简述四类基本的数据逻辑关系，并用图表示。2、特殊矩阵的压缩原则有哪些？3、什么是平衡二叉排序树？平衡因子的取值范围是什么？4、具有n个结点的k叉树，若采用k叉树链表存储，则空链域有多少个？（写出求解步骤）。5、递归进层时需要做哪些事？二、分析与方法选择每小题10分，共30分1、在10000个元素中，欲找出10个最大的元素，采用哪些排序方法较好。简述原因。2、在一个连通无向图上，欲求顶点vi到顶点vj（vivj）的最短简单路径，应采用深度优先遍历还是广度优先遍历？简述原因。3、分析冒泡排序的性能（最好情况、最坏情况）。三、

6、构造结果每小题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，以第一个关

7、键字中轴元素，写出一趟快速排序的结果。四、编写算法每小题10分，共30分1、编写算法voidAdjust(LinkListL)，其功能是：以第一个元素为基准，将小于该元素的结点全部放到前面，大于该元素的结点全部放到其后。2、要求循环队列不损失一个空间全部都能得到利用，设置一个标志域tag，以tag为0或1来区分头尾指针相同时的列状态的空与满，请编写与此结构相应的出队算法。3、二叉树采用二叉链表结构存储，编写算法实现统计二叉树中的结点个数。五、编写算法共15分二叉树采用二叉链表结构存储，编写实现二叉树后序线索化的算法。六、编写算法共15分编写算法，由依次输入的顶点数、弧数和各顶点信息、弧信息建立

8、有向图的邻接表存储结构。精品文档西北大学2013年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：852适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。注算法描述采用类语言，算法应加上必要的注释一、简答问题（共30分，每小题5分）1、线性结构与非线性结构的差别。2、说明在图的遍历中，设置访问标志数组的作用。3、简述数组和字符串属于线性表的原因。4、算法特性与算法时间复杂度。5、数据类型与抽象数据类型。6简述稳定排序含义，给出一种不稳定排序方法名称并证明。二、方法选择（共10分，每小题5分）1、设有10000个无序元素，要求找出前30个最大元素，在下列排

9、序方法（归并排序、基数排序、快速排序、堆排序、插入排序）中哪些方法最好，为什么？2、在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，简述应使用哪种排序方法最好。三、构造结果：（共40分，每小题8分）1、给定叶结点权值：（3,4,5,6,7,8,9），构造哈夫曼树，并计算其带权路径长度。2、已知一二叉树中序序列为BDCAEJF前序序列为ABCDEJF给出其对应的二叉树。3、已知二维数组A100200采用行序为主方式存储，每个元素占K个存储单元，已知A00的存储地址是1500,给出A6080的存储地址。4、给出12个结点的折半判定树，并计算其在等概率情况下的

10、平均查找长度。5、在地址空间012的散列区中，对以下关键字序列：（Jan,Feb,Apr,MayJun,Jul,Aug,Sep,Oct）建哈希表，设哈希函数为H（X）=i/2，其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一,要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。精品文档西北大学2012年招收攻读硕士学位研究生试题四、编写算法（20分）dataNext设主串s和子串t分别以单链表存储，t和s中的每个字符均用一结点表示（如图）。实现在链式存储方式下的模式匹配，即求子串t在主串s中第一次出现的位置指针。五、编写算法（20分）已知二

11、叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列，编写算法达到要求结果。六、编写算法（20分）无向图采用邻接表方式存储，编写出广度优先遍历访问的算法。七、编写语句（10分）在前序线索树中要找出X结点的后继结点。LtagLcDataRtagRc科目代码：852共2页科目名称：数据结构适用专业：计算机技术、软件工程答案请答在答题纸上，答在本试题上的答案一律无效。注算法描述可选用类语言，并加上必要的注释一、简答问题【30分，每小题6分】1、简述数组、广义表属于线性表原因。2、算法特性与算法时间复杂度。3、线性结构与非线性结构的差别。4、图遍历中设置访问标志数组的作用。

12、5、数据类型的含义与作用。二、方法选择【20分，每小题10分】1、只想得到N个元素序列中第K个最大元素之前的部分递减有序序列(Kv<N,列出2种速度快的方法名称与原因。2、在数轴上有n个彼此不交的相邻区间，每个区间下、上界都是整数，按区间位置从左到右依次编号为1N。试问：要查找某个给定值x所在区间，你认为应选择什么方法查找最快，简述原因。三、写出要求结果【共40分，每小题8分】1、已知计算阿克曼递归函数定义如下：Akm(intm，intn)if(m=0)return(n+1)；elseif(n=0)return(akm(m-1，1);elsereturn(akm(m-1，akm(mn-1

13、)；请给出执行Akm(2,1)时，递归调用顺序及执行结果。2、已知关键字序列为：(75,33,52，41，12,88，66,27)哈希表长为10,哈希函数为：H(K)=KMOD7解决冲突用线性探测再散列法，要求构造哈希表，并求出等概率下查找成功与不成功的平均查找长度。3、给定权值8,12,4,5,26,16,9，构造一棵哈夫曼树，并计算其带权路径长度。4、在中序线索树中，要找出X结点的前驱结点，请写出相关函数定义。LtagLcDataRtagRc5、已知一棵二叉树，其中序序列BDAEC后序序列DBECA构造该二叉树四、编写算法【15分】要求实现在链式存储方式下的模式匹配。已知主串s和子串t分别

14、以单链表存储，t和s中每个字符均用一结点表示（如图）dataNext即求：子串t在主串s中第一次出现的位置指针五、编写算法【共30分，每小题15分】（1）要求二叉树按二叉链表存储，写建立一棵二叉树的算法。15分（2）编写输出二叉树中的非叶子结点的算法。15分六、编写算法【15分】已知有N个结点的无向图，采用邻接表结构存储，要求编写算法实现广度优先搜索策略遍历图中所有顶点。精品文档西北大学2011年招收攻读硕士学位研究生试题科目名称：数据结构科目代码：849适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。注编写程序可选用C语言；算法描述采用类语言，应加上必要的

15、注释；所有答案均要求写在答题纸上。一、简答问题（每小题6分，共30分）1、四类数据结构名称及其关系图示。2、为什么说数组和广义表是线性表的推广？3、算法的定义与特性。4、数据类型与抽象数据类型。5、图遍历算法中设置访问标志数组的作用。二、方法选择（每小题10分，共20分）1、快速排序方法的最坏最好情况是什么，简要分析说明理由。2、二叉排序树中结点各不相同，欲得到一个由大到小的结点值递减序列，你认为应当采用什么方法，便可得到要求结果，简述原因。三、构造结果（每小题8分，共40分）1、给定叶结点权值：（2,3,5,6,9,11），构造哈夫曼树，并计算其带权路径长度。2、已知一二叉树中序序列BDCA

16、E,前序序列ABCDEF给出其对应的二叉树。3、已知二维数组AMN采用行序为主方式存储，每个元素占K个存储单元，已知A11（设起始下标为1）的存储地址是100,给出Aij的存储地址算式。4、在地址空间012的散列区中，对以下关键字序列：（Jan,Feb,Apr,MayJun,Jul,Aug,Sep,Oct）建哈希表，设哈希函数为H（X）=i/2,其中i为关键字中的第一个字母在字母表中的序号，处理冲突可选用线性探测法或链地址法之一，要求构造哈希表，并求出在等概率的情况下查找成功与不成功的平均查找长度。精品文档西北大学2010年招收攻读硕士学位研究生试题5、给出求N阶hanoi塔的函数定义如下：h

17、anoi(intn,charx,chary,charz)if(n=1)move(x,1,z)elsehanoi(n-1,x,z,y)；move(x,n,z)；hanoi(n-1,y,x,z)；请写出执行hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程四、编写算法（每小题15分，共30分）1、编写建立二叉树算法，要求二叉树按照二叉链表方式存储。15分2、已知二叉树采用二叉链表存储，要求编写算法，完成计算出二叉树中度为0、度为1的结点数目。15分五、编写程序（15分）要求实现如下功能：1、键盘输入N个有序整数，建立数组存储;2、输入关键字key，完成折半查找的功能。六、编写

18、算法（15分）已知二叉树采用二叉链表存储，编写算法实现按层次遍历二叉树科目名称：数据结构科目代码：848适用专业：计算机技术、软件工程共2页答案请答在答题纸上，答在本试题上的答案一律无效。注编写程序可选用C语言，算法描述采用类语言，算法应加上必要的注释；所有答案均要求写在答题纸上。一、简答问题共30分，每小题6分1、简述字符串、栈属于线性表原因。2、线性结构与非线性结构的差别。3、算法定义与算法特性。4、数据类型与抽象数据类型。5、图遍历中设置访问标志数组的作用。二、方法选择共20分，每小题10分1、说明稳定排序含义，并给出一种不稳定排序方法的名称与证明。2、在一个连通无向图上，欲求从一点Vj

19、到另一点Vj（M=Vj）所经结点数目短路径，在深度优先搜索、广度优先搜索、从一点到其余各顶点的最短路径算法中，你认为最好选择哪种方法为基础，简述原因。三、构造结果共40分，每小题8分1、构造10个结点的折半判定树，并计算查找成功的平均查找长度。2、已知一二叉树中序序列为BDAEC后序序列为DBECA给出其对应的二叉树。3、已知n阶下三角矩阵A（即当i<j时，有aj=0），按照压缩存储的思想，可以主对角线以下所有元素（包括主对角线上的元素）依次存放于一维数组B中请从第一列开始，采用行序为主序，给出在B中确定元素aj存放位置的公式。4、二叉排序树采用二叉链表方式存放，树中结点值各不相同，欲得

20、到一个由小到大的结点值递增序列，简述处理方法思路。5、给出求N阶hanoi塔的函数定义如下：hanoi(intn,charx,chary,charz)if(n=1)move(x,1,z)elsehanoi(n-1,x,z,y)；move(x,n,z)；hanoi(n-1,y,x,z)；请写出执行hanoi(3,a,b,c)时递归函数的实在参量变化及move的搬动过程四、编写程序共15分要求实现如下功能：将数组C1:n中所有奇数移到偶数之前，要求时间复杂度为O（n）五、编写算法共30分，每小题15分（1）写一个建立二叉树的算法，要求二叉树按二叉链表存储。（2）已知二叉树用二叉链表存储，要求写出算

21、法，实现该二叉树左右子树交换六、编写算法15分树采用孩子一兄弟存放,fchdatansib其中fch表示指向第一个孩子，nsib表示指向下一个兄弟编写算法，要求由根开始逐层输出树中的各条边，边输出格式为（心，匕）例:输出为：ABAC,ADBE,BF,CG精品文档西北大学2014年招收攻读硕士学位研究生试题科目名称：软件工程学科专业基础综合科目代码：844适用专业：计算机系统结构计算机应用技术共2页信息安全软件工程数据结构试题（75分）一、简答问题（共15分，每小题5分）1、简述队列、广义表属于线性表原因。2、排序稳定性的定义及证明不稳定排序的方法举例。3、简述图的两类存储名称及结构示意。二、写

22、出要求结果（共20分，每小题5分）1、设哈希表长度为11,哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11,若输入顺序为（D,BATNMCl，I，K，X，TA），处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功与不成功的平均查找长度。2、设有5000个无序元素，仅要求找出前10个最小元素，在下列排序方法（归并排序、冒泡排序、快速排序、堆排序、插入排序）中哪些方法快，为什么？3、已知一棵二叉树，其中序序列DBCAFGE前序序列ABDCEF,G构造该二叉树。4、用于通信的电文由8个字母a，b，c，d，e，f，g，h组成，各字母在电文中出现的频率分别为5,25,3，6，10，11,36，4。试为这8个字母设计哈夫曼编码，并计算给出该电文编码的总长度（WP带权路径长度）。三、编写算法（共10分）已知二叉树采用二叉链表结构存放，要求统计二叉树中度为1结点个数和度为2的结点个数。四、编写算法（共15分）1、键盘输入一组非零的整数序列，最