1、传达优良word版文档 ，期望对您有协助，可双击去掉！西北大学2015年接收攻读硕士学位研讨生试题(回想版)类别称号:数据规划 类别代码:851适用专业:核算机技能、软件工程 共2页答案请答在答题纸上，答在本试题上的答案一概无效。一、简答 每小题6分，共30分1、简述四类根柢的数据逻辑联络，并用图标明。2、简述数组、广义表归于线性表缘由。3、算法的界说及特性。4、啥是平衡二叉排序树？平衡因子的取值规模是啥？5、简述平稳排序意义，给出两种平稳排序办法以及两种不平稳排序办法称号并证明。二、分析与办法选择 每小题10分，共30分1、减半查找法对待查找的列表哪两个需求？答:有必要选用次序存储规划；必

2、须按要害词巨细有序摆放。2、 分析快速排序的功能（最佳情况、最坏情况）。3、 关于二叉树结点度数的核算。（紧记二叉树的5条性质，会计算二叉树及k叉树有关的核算。）三、规划成果 每小题8分，共40分1、已知一棵二叉树的前序序列及后序序列，给出其对应的二叉树。补白:西大历年试卷都是给出前序序列、中序序列或许中序序列、后序序列，写出对应的二叉树，这种题型极好做，且成果给出的二叉树仅有。可是2015年试题给出的是已知前序序列、后序序列，求对应的二叉树，这题咱们平常几乎都没做过，可是其实也不难，一般给出前序序列、后序序列，规划的二叉树不是仅有的，可是这次考题设置的奇妙，最终给出的成果二叉树大约是仅有的。

3、这道题具体我也不记住了，横竖有点难，我也花了很长时刻最终才做出来的。2、图的两种存储规划及标明、深度优先查找遍历、广度优先查找遍历、最小生成树的生成。3、顺次输入（26，30，15，10，28，19，18，22），规划二叉排序树，并核算等概率情况下的查找成功的均匀查找长度。4、画出10个元素的减半断定树，并核算等概率情况下查找成功的均匀查找长度。5、最小生成树生成的两种算法:普里姆算法、克鲁斯卡尔算法。四、编写算法 每小题10分，共20分1、以单链表作存储规划完成线性表的就地逆置算法，即在原表的存储空间将线性表（）逆置为（）。（记住不太理解了，横竖就是耿国华数据规划第2章习题中的一道程序题。）

4、2、在中序条理树中找结点前驱（或在中序条理树中找结点后继）。（讲义上的源程序。）五、编写算法 共15分这道题忘掉了。横竖我这道题不太会做，可是也程序写的满满的。记住即便不会做，也得写，写的满满的较好。只需你写教师都给分，估量给个10来分吧。假定你不答，空着的话，就只能得0分了。6、 编写算法 共15分编写算法，完成哈希链表的存储，哈希函数是h(k)=k%p，哈希表长为m，p为小于等于m的最大素数。处置冲突的办法选用线性勘探再散列。补白:我这道题也不太会做，可是也程序写的满满的。记住即便不会做，也得写，写的满满的较好。只需你写教师都给分，估量给个10来分吧。假定你不答，空着的话，就只能得0分了。

5、西北大学2014年接收攻读硕士学位研讨生试题类别称号:数据规划 类别代码:852适用专业:核算机技能、软件工程 共2页答案请答在答题纸上，答在本试题上的答案一概无效。一、简答 每小题6分，共30分1、简述四类根柢的数据逻辑联络，并用图标明。2、特别矩阵的紧缩原则有哪些？3、啥是平衡二叉排序树？平衡因子的取值规模是啥？4、具有n个结点的k叉树，若选用k叉树链表存储，则空链域有多少个？（写出求解进程）。5、递归进层时需要做哪些事？二、分析与办法选择 每小题10分，共30分1、在10000个元素中，欲找出10个最大的元素，选用哪些排序办法较好。简述缘由。2、在一个连通无向图上，欲求极点vi到极点

6、vj（）的最短简略途径，应选用深度优先遍历仍是广度优先遍历？简述缘由。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个元素的减半判

7、定树，并核算等概率情况下查找成功的均匀查找长度。5、已知要害词集结:50，52，85，22，96，17，36，55，以第一个要害词中轴元素，写出一趟快速排序的成果。四、编写算法 每小题10分，共30分1、编写算法void adjust(linklist l)，其功用是:以第一个元素为基准，将小于该元素的结点悉数放到前面，大于该元素的结点悉数放到这今后。2、需求循环行列不丢掉一个空间悉数都能得到使用，设置一个标志域tag，以tag为0或1来区别头尾指针相一起的列状况的空与满，请编写与此规划相应的出队算法。3、二叉树选用二叉链表规划存储，编写算法完成计算二叉树中的结点个数。五、编写算法 共15分二叉

8、树选用二叉链表规划存储，编写完成二叉树后序条理化的算法。六、编写算法 共15分编写算法，由顺次输入的极点数、弧数和各极点信息、弧信息树立有向图的邻接表存储规划。西北大学2013年接收攻读硕士学位研讨生试题类别称号:数据规划 类别代码:852适用专业:核算机技能、软件工程 共2页答案请答在答题纸上，答在本试题上的答案一概无效。注 算法描绘选用类言语，算法应加上必要的注释一、简答疑问 （共30分，每小题5分）1、线性规划与非线性规划的不一样。2、阐明在图的遍历中，设置造访标志数组的作用。3、简述数组和字符串归于线性表的缘由。4、算法特性与算法时刻凌乱度。5、数据类型与笼统数据类型。6、简述平稳排序含

9、义，给出一种不平稳排序办法称号并证明。二、办法选择 （共10分，每小题5分）1、设有10000个无序元素，需求找出前30个最大元素，鄙人列排序办法（归并排序、基数排序、快速排序、堆排序、刺进排序）中哪些办法最佳，为啥？2、在一个待排序的序列中，只需很少量元素不在自个究竟的正确方位上，但离他们的正确方位都不远，简述应运用哪种排序办法最佳。三、规划成果:（共40分，每小题8分）1、给定叶结点权值:（3，4，5，6，7，8，9），规划哈夫曼树，并核算其带权途径长度。2、已知一二叉树中序序列为bdcaef，前序序列为abcdef，给出其对应的二叉树。3、已知二维数组a100200选用行序为主方法存储

10、，每个元素占k个存储单元，已知a00的存储地址是1500，给出a6080的存储地址。4、给出12个结点的减半断定树，并核算其在等概率情况下的均匀查找长度。5、在地址空间012的散列区中，对以下要害词序列:（jan，feb，apr，may，jun，jul，aug，sep，oct）建哈希表，设哈希函数为h(x)=i/2，其间i为要害词中的第一个字母在字母表中的序号，处置冲突可选用线性勘探法或链地址法之一，需求规划哈希表，并求出在等概率的情况下查找成功与不成功的均匀查找长度。四、编写算法 （20分）datanext设主串s和子串t别离以单链表存储，t和s中的每个字符均用一结点标明（如图）。完成在链式

11、存储方法下的方法匹配，即求子串t在主串s中初度呈现的方位指针。五、编写算法 （20分）已知二叉排序树按二叉链表方法存储，树中结点各纷歧样，欲得到一个由小到大的结点值递加序列，编写算法抵达需求成果。六、编写算法 （20分）无向图选用邻接表方法存储，编写出广度优先遍历造访的算法。七、编写语句 （10分）在前序条理树中要找出x结点的后继结点。ltaglcdatartagrc西北大学2012年接收攻读硕士学位研讨生试题类别称号:数据规划 类别代码:852适用专业:核算机技能、软件工程 共2页答案请答在答题纸上，答在本试题上的答案一概无效。注 算法描绘可选用类言语，并加上必要的注释一、简答疑问 【30

12、分，每小题6分】1、简述数组、广义表归于线性表缘由。2、算法特性与算法时刻凌乱度。3、线性规划与非线性规划的不一样。4、图遍历中设置造访标志数组的作用。5、数据类型的意义与作用。二、办法选择 【20分，每小题10分】1、只想得到n个元素序列中第k个最大元素之前的有些递减有序序列（kn），列出2种速度快的办法称号与缘由。2、在数轴上有n个彼此不交的相邻区间，每个区间下、上界都是整数，按区间方位从左到右顺次编号为1n。试问:要查找某个给定值x地址区间，你认为应选择啥办法查找最快，简述缘由。三、写出需求成果 【共40分，每小题8分】1、已知核算阿克曼递归函数界说如下:akm(int m，int n)

13、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结点的前驱结点，请写出有关函数界说。ltaglcda

14、tartagrc5、已知一棵二叉树，其间序序列bdaec，后序序列dbeca，规划该二叉树。四、编写算法 【15分】要务完成在链式存储方法下的方法匹配。datanext已知主串s和子串t别离以单链表存储，t和s中每个字符均用一结点标明（如图）即求:子串t在主串s中初度呈现的方位指针。五、编写算法 【共30分，每小题15分】（1）需求二叉树按二叉链表存储，写树立一棵二叉树的算法。15分（2）编写输出二叉树中的非叶子结点的算法。15分六、编写算法 【15分】已知有n个结点的无向图，选用邻接表规划存储，需求编写算法完成广度优先查找战略遍历图中一切极点。西北大学2011年接收攻读硕士学位研讨生试题科

15、目称号:数据规划 类别代码:849适用专业:核算机技能、软件工程 共2页答案请答在答题纸上，答在本试题上的答案一概无效。注 编写程序可选用c言语； 算法描绘选用类言语，应加上必要的注释； 一切答案均需求写在答题纸上。一、简答疑问 （每小题6分，共30分）1、四类数据规划称号及其联络图示。2、为啥说数组和广义表是线性表的推广？3、算法的界说与特性。4、数据类型与笼统数据类型。5、图遍历算法中设置造访标志数组的作用。二、办法选择 （每小题10分，共20分）1、快速排序办法的最坏最佳情况是啥，扼要分析阐明理由。2、二叉排序树中结点各纷歧样，欲得到一个由大到小的结点值递减序列，你认为应中选用啥方

16、法，便可得到需求成果，简述缘由。三、规划成果 （每小题8分，共40分）1、给定叶结点权值:（2，3，5，6，9，11），规划哈夫曼树，并核算其带权途径长度。2、已知一二叉树中序序列bdcaef，前序序列abcdef，给出其对应的二叉树。3、已知二维数组amn选用行序为主方法存储，每个元素占k个存储单元，已知a11（设开始下标为1）的存储地址是100，给出aij的存储地址算式。4、在地址空间012的散列区中，对以下要害词序列:（jan，feb，apr，may，jun，jul，aug，sep，oct）建哈希表，设哈希函数为h(x)=i/2，其间i为要害词中的第一个字母在字母表中的序号，处置冲突可选

17、用线性勘探法或链地址法之一，需求规划哈希表，并求出在等概率的情况下查找成功与不成功的均匀查找长度。5、给出求n阶hanoi塔的函数界说如下:hanoi(int n，char x，char y，char z)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、已知二叉树选用二叉链表存储，需求编写算法，结束核算出二叉树中吨蔼

18、0、度为1的结点数目。 15分五、编写程序 （15分）要务完成如下功用:1、键盘输入n个有序整数，树立数组存储；2、输入要害词key，结束减半查找的功用。六、编写算法 （15分）已知二叉树选用二叉链表存储，编写算法完成按层次遍历二叉树。西北大学2010年接收攻读硕士学位研讨生试题类别称号:数据规划 类别代码:848适用专业:核算机技能、软件工程 共2页答案请答在答题纸上，答在本试题上的答案一概无效。注 编写程序可选用c言语， 算法描绘选用类言语，算法应加上必要的注释； 一切答案均需求写在答题纸上。一、简答疑问 共30分，每小题6分1、简述字符串、栈归于线性表缘由。2、线性规划与非线性规划的不一样

19、。3、算法界说与算法特性。4、数据类型与笼统数据类型。5、图遍历中设置造访标志数组的作用。二、办法选择 共20分，每小题10分1、阐明平稳排序意义，并给出一种不平稳排序办法的称号与证明。2、在一个连通无向图上，欲求从一点到另一点（）所经结点数目短途径，在深度优先查找、广度优先查找、从一点到其他各极点的最短途径算法中，你认为最佳选择哪种办法为基础，简述缘由。三、规划成果 共40分，每小题8分1、规划10个结点的减半断定树，并核算查找成功的均匀查找长度。2、已知一二叉树中序序列为bdaec，后序序列为dbeca，给出其对应的二叉树。3、已知n阶下三角矩阵a（即当ij时，有），依照紧缩存储的思维，可

20、以主对角线以下一切元素（包括主对角线上的元素）顺次存放于一维数组b中。请从第一列初步，选用行序为主序，给出在b中止定元素存放方位的公式。4、二叉排序树选用二叉链表方法存放，树中结点值各纷歧样，欲得到一个由小到大的结点值递加序列，简述处置办法思路。5、给出求n阶hanoi塔的函数界说如下:hanoi(int n，char x，char y，char z)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分要

21、务完成如下功用:将数组c1:n中一切奇数移到偶数之前，需求时刻凌乱度为o(n)。五、编写算法 共30分，每小题15分（1）写一个树立二叉树的算法，需求二叉树按二叉链表存储。（2）已知二叉树用二叉链表存储，需求写出算法，完成该二叉树支配子树交流。fchdatansib六、编写算法 15分树选用孩子兄弟存放，结点规划为其间fch标明指向第一个孩子，nsib标明指向下一个兄弟。编写算法，需求由根初步逐层输出树中的各条边，边输出格局为（）。例:adcbfeg输出为:ab，ac，ad，be，bf，cg。西北大学2014年接收攻读硕士学位研讨生试题类别称号:软件工程学科专业基础归纳 类别代码:844适用专

22、业:核算机体系规划 核算机使用技能 共2页 信息平安 软件工程数据规划试题（75分）一、简答疑问 （共15分，每小题5分）1、简述行列、广义表归于线性表缘由。2、排序平稳性的界说及证明不平稳排序的办法举例。3、简述图的两类存储称号及规划暗示。二、写出需求成果 （共20分，每小题5分）1、设哈希表长度为11，哈希函数h(k)=(k的第一字母在字母表中的序号)mod 11，若输入次序为（d，ba，tn，m，ci，i，k，x，ta），处置冲突办法为线性勘探再散列或链地址法，需求规划哈希表，并求出等概率情况下查找成功与不成功的均匀查找长度。2、设有5000个无序元素，仅需求找出前10个最小元素，鄙人列

23、排序办法（归并排序、冒泡排序、快速排序、堆排序、刺进排序）中哪些办法快，为啥？3、已知一棵二叉树，其间序序列dbcafge，前序序列abdcefg，规划该二叉树。4、用于通讯的电文由8个字母a，b，c，d，e，f，g，h构成，各字母在电文中呈现的频率别离为5，25，3，6，10，11，36，4。试为这8个字母方案哈夫曼编码，并核算给出该电文编码的总长度（wpl带权途径长度）。三、编写算法 （共10分）已知二叉树选用二叉链表规划存放，需求计算二叉树中吨蔼1结点个数和度为2的结点个数。四、编写算法 （共15分）1、键盘输入一组非零的整数序列，最终输入零为结束标志，需求根据输入树立一棵二叉排序树算

24、法，选用二叉链表方法存放。 （10分）2、给出按由大到小次序输出此二叉排序树中结点值的算法。 （5分）五、编写算法 （共15分）已有无向图选用邻接表规划存储，需求按广度优先查找战略编写求出一切连通子图的生成树（生成树中的边用（）格局输出）。西北大学2013年接收攻读硕士学位研讨生试题类别称号:软件工程学科专业基础归纳 类别代码:844适用专业:核算机体系规划 核算机使用技能 共2页 注 编写程序可选用c言语， 算法描绘选用类言语，算法应加上必要的注释。数据规划试题（75分）一、简答疑问 （共15分，每小题5分）1、简述数据类型和笼统数据类型的意义与联络。2、简述数组、广义表归于线性表缘由。3、

25、阐明在图的遍历中，设置造访标志数组的作用。二、写出需求成果 （共20分，每小题5分）1、已知一棵二叉树，其间序序列dbcafge，后序序列dcbgfea，规划该二叉树。2、快速排序办法的最坏最佳情况是啥，扼要分析阐明理由。3、已知要害词序列为:（75，33，52，41，12，88，66，27）哈希表长为10，哈希函数为:h(k)=k mod 7，处置冲突用线性勘探再散列法，需求规划哈希表，并求出等概率下查找成功与不成功的均匀查找长度。4、给定叶结点权值:（3，4，5，6，7，8，9），规划哈夫曼树，并核算其带权途径长度。三、编写程序 （共10分）键盘输入n个有序值树立线性表（），按减半查找战略完成查找给定值为key的元素。四、编写算法 （共15分）已知有n个结点的无向图，选用邻接表规划存储，需求由根初步逐层输出连通子图中一切生成树中的各条边，边输出格局为（）。五、编写算法 （共15分）1、树立一棵二叉树，需求以二叉链表存储规划存储。 （5分）2、需求判别二叉树是不是是一棵二叉排序树。 （10分）