完整版19云南大学历年计算机专业复试题.docx

1、完整版19云南大学历年计算机专业复试题数据结构云南大学 抽两道题并答题。从一个大盒子里面抽俩，每个纸条上面的题目只有1个。根据回答情况追问，复试去的早的话，如果早上，那么老师问的比较多。学硕最长30分钟（前几个进去的同学）。专硕最短不到10分钟。老师如果感觉一天复试不完那么就会压缩时间，每个同学进入房间 自我介绍（有的是中文，有的是英文），英语抽提，一个题有100多个单词，特别短，生词不多，read and translate 翻译结束英语就结束了。接下来是专业问题抽提了。俩指头宽度的纸片，20多厘米长。塞满一个塑料盒子，叠着的。这篇文章里面的题能碰到1个就nice了。我就碰到了一个，是我瞄到

2、一张没有完全折叠好的纸片，我熟悉那个问题所以perfect。专业题特别杂，看运气英语好的，能看懂句子成分的就不用准备英语了，下午去的同学，就随便准备一些英语问题，your family ,your university ,why, and your outlook?可能会问，时间紧就不问了，逆置一个顺序表，链表顺序表逆置:由于顺序表是连续存储的,循环表厂的一半，交换第一个和最后一个元素。i 交换 length-i，每做一次循环，i+。逆置一个链表： 先保存第一个数据节点，p=L-next,后把头结点摘下 L-next=NULL; 遍历p的链表，头插法插入L表。遍历完出来L就是逆置的。 排序一个

3、顺序表，链表顺序表排序：2路归并排序，堆排序，冒泡排序，插入排序。折半插入排序排序链表：我们假设递增有序，采用直接插入排序法。先构造一个只有一个数据节点的有序单链表，然后外层循环依次遍历源单链表剩余节点，直到遍历结束，内层循环在有序单链表中比较大小查找合适节点插入。把一个有序单链表A插入另一个有序单链表B，合成的B链表任然有序：扫描A链表，取下节点，扫描B链表找到合适节点插入，若发现A链表空，则结束，若发现A链表不为空，B链表为空，则直接将A中剩余节点放入B中。改进方法：当我从A中取下节点插入B后，记录该节点的值。下次扫描B链表找合适的位置时就不用每次从第一个节点扫描。把一个有序顺序表插入另一

4、个有序顺序表，合成的顺序表任然有序：数据结构三要素：逻辑结构，物理结构和数据的运算逻辑结构：指的是元素之间的逻辑关系，和数据怎么存储无关。逻辑结构一般分为线性结构和非线性结构线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系物理结构，也叫做存储结构。如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；算法：，求解特定问题步骤的描述，他是指令的有限序列如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据 有穷，确定，可行性，输入 输出52数组和线性表都是一组类型相同的数据元素的有序集合，而广

5、义表的数据元素可以有不同的结构，广义表的元素可以是子表，而子表的元素还可以是广义表，数组是顺序存储的，链表既可以顺序又可以链式，广义表一般用链式存储广义表是一个多层次结构，他有长度（最外层包含元素个数）和深度（包含括弧的重数）的概念，一个广义表可以为其他广义表共享，而数组没有这个概念，数组有了名字，那他就有了一块连续的存储空间,不能被其他数组抢占和共享。线性表也可以共享，只要一个表中某个元素的后继是另一块表的一个元素，那就可以共享了。广义表可以是递归的表，链表也有循环单链表和循环双链表。在存储结构上，单链表可以有头结点，单链表的节点有指针域和数据域组成，数字没有这个概念，只有值，但是数组有下标

6、，广义表的表节点由三个域组成，标志域，指示表头的指针域(hp)和指向下一个元素的指针域（tp）。什么是堆？什么是栈？什么是队列？有何区别？栈：只允许一端进行插入删除，的线性表。他的特点是先进去的后出来。队列：是一种操作受限的线性表，他只允许在一端口插入，另一端口删除。特点是先进先出。 栈和队列都不允许随便读取或者删除中间的元素。堆的特征是什么，如何利用堆进行排序堆是一个完全二叉树。而且最大元素存放在根节点，任意一个非根节点，他的值小于或者等于双亲节点的值 ，这是大根对，小根堆与之相反堆排序第一步：构造一个初始堆，关键在于筛选。对于大根堆来说，就是若双亲节点的关键字小于左右子女的话，那就选取一个

7、大子女和双亲交换。从下向上依次交换知道根节点为最大。初始大根堆建好了第二步：输出堆顶节点，用堆底元素填充根节点，输出的元素放在底部。因为堆我们用的是数组存储，输出元素一般在数组末尾。 此时我们破坏了大根堆，所以要调整这个堆，这个堆已经不再包含输出元素，尽管输出元素还在堆上，但是堆是数组存储的，把根节点（一般比较小）向下和子女交换以维持大根堆性质。第三部 再次输出根节点，重复上述步骤知道堆仅仅剩下一个元素为止。数据结构中图的存储中，邻接矩阵和邻接表的优缺点？答：图有邻接矩阵和邻接表两种存储方式 所谓邻接矩阵就是，用一维数组存储图的顶点信息，用二维数组存储图的边的信息（各个顶点之间的关系。）所谓邻

8、接表，就是用顺序存储的方式存储图的顶点，用连式存储存依附于此顶点的边。优缺点：邻接矩阵清晰明了，容易看出各个顶点是否有边相连。而邻接表则不能给人清晰的表示，他要在响应的节点对应的边表查找节点。 但是邻接矩阵的存储效率比较差，如果图比较稀疏，那么矩阵就会有很大存储单元被浪费了，而我们的邻接表由于采用链式存储存储边的关系，所以避免了这种浪费。 在查找边的个数方面，邻接矩阵要检测整个矩阵，时间是O(n)而邻接表很容易找出所有的邻边，只用读取对应顶点的邻接表就行了。在有向图求初度和入度方面，采用邻接矩阵，第一行非零元素个数就是顶点V1的出度，第一列非零个数就是V1的入度。而邻接表在求出度方面只需遍历边

9、表中节点个数，在求入度方面要遍历整个表。十字链表是有向图的一中链式存储结构，包括弧节点(狐尾虎头，两个弧链域，弧头相同的在一个链表，狐尾相同的在一个链表)和顶点节点(数据域和两个链域，一个表示弧的起点(out)，一个表示弧的终点(in)，所以容易求节点的入度和出度。一个图的十字链表不是唯一的，但一个十字链表确定一个图。邻接多重链表是无向图的链式存储结构程序的健壮性？答：对于不规范的输入能够做出反应而不会产生奇怪的费解的输出结果。数据结构中排序的稳定性？答：对于待排序列中的值相等的元素来说比如a1= a2 ，如果排序结果没有改变这些值相等元素的相对位置，还是a1在前a2在后面。那么算法就是稳定的

10、任意两个节点的最短路径？答：迪杰斯特拉算法最小生成树：在图所有生成树中，代价最小的生成树称为最小生成树。他包含图的所有顶点，并且包含尽可能少的边最小生成树不是唯一的，可以有多个，当图中边的权值互不相等，那么最小生成树就是唯一的。最小生成树的权值之和是唯一的，他的边数是顶点个数减去1构造生成树的算法：普利姆算法O(V2),适合求解边多，点少的图和克鲁斯卡尔O(ElogE)算法，适合求解边少，点多的图。欧拉图： 具有欧拉回路的图就是欧拉图。欧拉回路是 图中经过每条边切仅仅一次经过的回路叫做欧拉回路。那些图有欧拉回路？ 1 无向图中，当且仅当图是连通图，而且图没有奇数度的顶点。 2 有相图，当且仅当

11、图是联通的，且所有的顶点的入度=初度。哈密顿图 有哈密顿回路的图。哈密顿回路 经过每个顶点一次且仅仅一次的初级回路。 哈密顿通路 经过每个顶点一次且仅一次的通路。哈密顿图必然是连通图。在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小最小生成树算法，生成树边的权重之和最小。什么是最小连通子图？既要保存图联通，又要保持图的边数最少。一个联通图的生成树是图的最小连通图。他包含图的所有顶点，包含尽可能少的边。如果砍去其中任意一条，都会让树变成非联通图。如果给他增加一条边，那就形成图的一条回路。如何产生最小连通图？ 那不

12、就是生成树么，生成树有深度优先遍历和广度优先遍历算法；最小生成树有两种算法，克鲁斯卡尔和普里姆算法。 But无向图的极大联通子图是无向图的联通分量。 有向图的极大联通子图叫做有向图的强联通分量。 怎样防止出现环？第一中方法要拓扑排序方法。在一个有向图中，我们采用拓扑排序，拓扑排序要求如果某个节点出现在另一个节点的前面如 先A后B，那么接下来的排序中就不用该出现先B后A的路径。对有向图的拓扑排序，如果发现不存在拓扑排序，或者是排序没走完，剩下的图中不存在前驱的顶点，那就说明图中有环。第二种方法：求关键路径。关键路径本身就要求无环，一个工程的某个节点不能既是下一个节点开始的前提条件，又是下一个节点

13、的产出；求关键路径也要求拓扑排序所以也可以来判断有没有环路。第三种方法：采用图的深度优先遍历算法。一条深度遍历路线中如果某个节点被第二次访问到，那就有环，因为深度优先路径是一条单链，访问过的节点保存下来就不应该再次被访问。拓扑排序和偏序，全序的关系：选课，课程之间有先后关系，制定选课顺序过程就是拓扑排序的过程。选课关系中有课程先后的关系，也有课程间没有特定顺序的关系，但是不允许出现1221这种互相矛盾的关系也就是环路。有向无环图两个顶点不存在环路，必然满足偏序关系。 如果任意两个课程之间只有先后关系，并且没有换，那就是全序关系。原来的偏序变成了全序。排序算法1 2 3 4，大小关系确定，唯一的

14、，则这个序列满足全序关系。表现在拓扑排序中就是每个顶点间都具有全序关系，则拓扑排序结果唯一。若是偏序的关系，那就不唯一了。有向无环图在实际生活中的应用例子？日常导航嘛。区块链领域。什么是哈希表？如何构建哈希表？在构建哈希表过程中，会遇到什么问题，如何解决？答：哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构，他建立了关键字和存储地址之间的一种直接映射关系。怎么构建哈希表：在记录的存储位置和它的关键字之间建立一个确定的对应关系f即哈希函数。使每个关键字和表中唯一的存储位置相对应，根据这个思想建立的表为哈希表哈希表的做法其实很简单，首先要构造

15、一个哈希函数，哈希函数的构造有直接定址法，除留余数法，平方取中法等等。我们那除留余数法做例子在，这个比较简单，也比较常用。关键字对一个不大于散列表长度的一个素数取余。取余结果就当作关键字的地址，关键字可以存放在数组里，（也可以存放在二叉树）构造这个散列表的过程中会遇到几个关键字映射到一个地址上面，也就产生了冲突。原因在于散列函数选取不当。处理冲突有 开放定址法：线性探测 查看下一个单元，链地址法：把所有同义词存放在一个链表里。不过对链表查找效率会变低，我们可以在链表上构建一平衡二叉树。Hashmap是什么：稀疏矩阵？答：如果在矩阵中，多数的元素为0，通常认为非零元素比上矩阵所有元素的值小于等于

16、0.05时，则称此矩阵为稀疏矩阵（sparse matrix）。AOE网的始点和终点是什么？正常的AOE网只有一个始点和终点吗？答：关键路径（临界路径）：在AOE网络中从源点到汇点（结束顶点）的最大路长度的路径。关键路径可以有多条起始点：入度为0的点 1个 终点：仅有一个也叫做汇点 出度为0关键路径上的活动为关键活动，带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间怎么能够判断判断一个图是连通还是非连通的？答：对于无向图来说，如果无向图联通的，那么从任意一个点出发，仅需要一次遍历就能访问所有的点。 如果是非联通的，则从任意一个顶点出发，一次遍历只能访问此顶点所在联通

17、分量的所有顶点，而剩余的节点无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，那么一次遍历就可以访问所有的点，否则可以借助深度优先遍历，如果能遍历所有的点，那他就是联通的有向图和无向图的联系,试各举一例说明？答：无向图可以看作每条边都有两个方向的有向图，写成邻接矩阵的形式的话区别就很清楚；无向图的邻接矩阵一定是对称阵,而有向图则未必实际应用的区别是有向图可以描述非对称的关系,但无向图不能.比如你认识奥巴马,但是他不认识你,用图来表示人物关系时就将你和奥巴马之间连一条线,并且指向他.可以用来解决加快工程进度的问题。无向图和有向图都可以用来寻找最优路径。有向图解决最低路径成

18、本问题。无向图能解决的问题都能用有向图表示,但是无向图在对称的问题上往往更容易,因为用有向图去表示无向图时需要用两倍的边数。堆排序的思想是什么?答：n个关键字序列Kl，K2，Kn称为堆，当且仅当该序列满足如下性质(简称堆性质)：(1)kiK2i且kiK2i+1或(2)KiK2i且kiK2i+1(1iFLOOR(n/2)若将此序列所存储的向量R1.n看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。知道一棵树的先序和后序能不能确定它?要证明.答：不能，必须知道中序。这是因为同样的前序遍历和后序遍历序

19、列，可以对应不同的二叉树。完全二叉树的性质：度数为1的节点只有1个或者1个没有。叶子节点只可能在最大两层出现，而且对于最大层次中的叶子节点，依次排列在该层最左边的位置。若有N个元素，则：N为奇数，每个分支节点都有左右子女； N为偶数，则n/2的节点只有做子女，没有有子女。如何判断完全二叉树：采用层次遍历，根据完全二叉树的性质，如果遍历遇到了一个空节点，那么在这一层中该节点的后面就不应该再有空节点。如果有，就不是。平衡二叉树树的任一节点的左子树和右子树的深度之差（平衡因子）不超过1.平衡二叉树的节点平衡因子只能是-1,0,1他的平均查找长度为O(logN)。（赫夫曼）哈夫曼树？答：给定n个权值作

20、为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。带权路径长度：从树的根节点出发到任意节点的路径长度（经过的边数）与该节点上权值的乘积 叫做该节点的带权路径长度。树的带权路径长度：树中所有叶子节点的带权路径长度之和叫做该树的带权路径长度一般用于数据压缩处理，对于频度高的数据字符赋短编码 ，频率较低的赋以长编码线索二叉树二叉树线索化的实质就是对非线性结构的线性化。为的是加快查找节点前驱和后继的速度。由于二叉链表存储的二叉树中存在大量空指针，我们用这些空链域存放指向

21、其直接前驱和直接后继的指针。在遍历二叉树的时候，检查当前节点左右指针域是否为空，若为空，则把他们改为指向前驱节点或者后继节点的线索。在中序线索二叉树中，如何找节点的直接前驱？在后序线索二叉树中，如何找节点的直接前驱？计算机如何实现线索二叉树的遍历1.先说中序线索查找前驱节点：在中序线索树中找结点*p的中序直接前驱，也就是*p节点的左线索，查找他的左子树，如果他的左子树空，那么他的左线索就是他的直接前驱。 倘若左子树不为空，有左孩子，那就从他的左孩子开始查找，寻找左孩子的右子树，当右子树为空的节点就是他的直接前驱 自己画个图看看就知道了2.再说后序线索查找前驱节点：如果节点p有子女，那么他的右子

22、女就是他的直接前驱。3. 如果节点p没有右子女，但是有左子女，那么他的左子女就是他的前驱。 如果节点p是个叶子节点，那么他的左线索就是他的直接前驱4. ！链表设置头结点作用：不设头结点时候，删除其他节点没什么问题，但是删除第一个节点就会有问题，第一个节点要特殊化处理。引入头结点使第一个节点和其他节点的处理可以统一化，写代码就不用判断了树的遍历种类，确定一棵树的方法？答：前序遍历、中序遍历和后序遍历，层序遍历。知道前序遍历和中序遍历可以确定一棵树；知道后序遍历和中序遍历可以确定一棵树。树是否可以用顺序存储，如何存储？答：可以。顺序存储的话，就是存储在数组中，数组的下标就是二叉树的结点位置（层次结

23、构），i的两个孩子结点在数组中的位置是2i（左孩子）和2i+1（右孩子）。堆排序、快速排序和归并排序，哪个辅助存储空间最少，哪个平均速度最快，哪个稳定？答：除了快速排序之外（快排的最佳情况和平均运行时间很接近），其他排序的最坏情况和平均情况都是一样的时间复杂度。用一个递归树来表示，每次划分排序均匀情况下，递归树的深度LOG(N+1)，每一层的代价是O（N），这样总的代价就是N(logN)选择排序：简单选择排序和堆排序的空间复杂度都是O(1)，因为他只使用常数个辅助空间。简单选择排序的时间复杂度（即元素间的比较次数，就算有序的，元素顶多不用移动，但还是免不了要11比较）和最初序列状态无关，始终是

24、O(N2)。快速排序思想是基于分治算法的，即分解（分解为俩个数组），处理（通过递归调用快速排序），合并（这里俩个数组是就地排序，不用合并），是对冒泡的改进。当元素基本有序（正序或者逆序），他就退化为冒泡排序O（N2）;冒泡是相邻两个比较交换，而快排不是比较相邻的，故排序算法不稳定。他选取一个元素做为参考，比他大的放在左边，比他小的放在右边。然后再分别对左右两个子序列递归地排序，需要一个递归工作栈来保存每一层递归调用的必要信息，最好情况的时间复杂度是nlog（n）,最好情况的空间复杂度是logN,最坏情况下的空间复杂度O(N)。快排的运行时间取决于划分的平衡,而划分是否对称和选择哪一个元素进行划

25、分有关。如果划分对称的化，就与归并算一样，如果不对称，就和插入排序一样慢了。 但若初始序列基本有序，则插入排序时间性能最好，而快排最差O(N2)最坏情况，划分不对称下，假设每一次递归调用都出现了不对称，出现了划分两个区域，一块n-1个，另一块没有元素，那么每一次递归调用都花费O(N)，最终每一层叠加起来就是N2了。树和图之间的区别？答：树是图，图不一定是树，树是图的子集树有一个根节点，图没有树可以递归遍历，图要看情况树有层次划分，图没有树的非根节点必定有一个父节点，图不一定树是一种“层次”关系，图是“网络”关系，图可以有环，而树不允许。树可以是空的，但是图不允许空。静态链表的数据结构？答：静态

26、链表是借助数组来描述线性表的链式存储结构。他也有指针域和数据域。所不同的是他是用游标代替指针来指示节点在数组中的相对位置。而且他的插入删除也不需要移动数组元素。只用修改指针就行了。我们几个人围成一圈，从某个人开始数数，数到3的人OUT，说一下这个算法？答：这个可以用循环链表实现。两个有序的链表A，B。如何把B的节点插入A链表，使之仍是有序的表？答：依次取B链表的节点，分别与A链表的节点的关键字比较，找到合适的位置插入即可。数据结构顺序表有哪些缺点，如何逆置一个链表？答：顺序表的优点是便于随机存储，缺点是不便于插入删除等操作，因为插入删除一个元素需要移动其后的所有元素，但是链表不存在这个问题，链

27、表只要改变指针就行，时间复杂度小，所以链表于顺序表恰恰相反，优点是便于插入删除等操作，缺点是随机存储没有顺序表方便。void linklist_oppse(LinkList &L)LinkList p,q;p=L;p=p-next;L-next=NULL;while(p)q=p;p=p-next;q-next=L-next;L-next=q;二分查找？答：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序顺序表，不适合连式存储。且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。查找思想：首先将待查数据和排好顺序的顺序表中间的那个元素比

28、较大小，假设是升序，如果比中间的大，那就缩小范围查找右半部分的。依次缩小范围找到返回，找不到就没有。我们可以用一个判定树来描述。分块查找（索引顺序查找）结合二分查找和顺序查找的优点。把查找表分成若干个子块，块里面的元素可以无序，但是块间要有序。在建立一个索引表，索引表的组成：索引表含有每个各块中第一个元素的地址和块中最大元素的值，索引表按照关键字有序排序。分块查找中，首先在索引表中可以用顺序查找或者折半查找来确定待查元素在哪块（哪个分区）； 然后第二步在快内顺序查找（只能用）。二路归并的实质是什么？答：归并排序 基于分治算法，将两个或两个以上的有序表组合成一个新的有序表。把待n个元素排序表看做

29、n个子表组合而成，然后每两个子表归并，得到长度为2的新的子表，然后在两两归并如此重复一直到合并成长度为n的有序表为止。2路排序是一个稳定的排序算法，时间效率是O(NlogN)一个无序的单链表怎样能让它变得有序，简单说明一下算法？答：贪心算法是什么，能给出正确的答案吗？答：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的每一步骤都是这个问题的局部最优解。贪心算法认为一个全局最优解可以同局部最优选择（贪心）来达到，that means，当考虑到如何选择时，我们只考虑当前问题最佳的选择，而不考虑子问题的结果。这一点也是和动态规

30、划不同的地方，动态规划认为，每一步都要做出选择，但这些选择却依赖于子问题的解，因此动态规划问题一般是自底向上，从下到大处理问题。但在贪心算法中，我们所做的总是当前最佳，不考虑之后有什么不妥的问题，至于它产生的问题，贪心继续贪心的处理。所以他当前所做出的选择会在一定程度上依赖于他曾经做出的决策，而不是依赖于那些尚未解决的子问题。所以他通常是自顶向下处理子问题，不断的吧问题分解为更小的问题。齐王：上等马 中等马 下等马田忌： 上等马 中等马 下等马解决单源点最短路径问题。比如说有点ABCDE，A是目标点。现在有两个集合M(左手比划，用来放搜寻到距离M集合所含节点最短距离的节点，初始化放置目标点A)

31、和N（尚未找到最短路径的节点BCDE，右手比划），俩个集合都用数组来表示。现在第一次循环，从集合M出发，搜索M里面的所有节点（只有A一个）能够到达的最短路径节点，找到后将其放入M中（左手），并从N、（右手）中删除这个点。下一轮循环，从集合M（假设现在哟了A,B）出发，以最短路径到达集合N中的节点，假设C。然后把C放入M中，并将其从N中删除。动态规划算法，典型运用？答：一、基本概念 动态规划通过组合子问题的解而解决整个问题。分治算法则是把问题分解成一些独立子问题，递归的求解各个子问题，然后合并子问题的解得到原问题的解。然而动态规划适用于子问题不是独立的情况，也就是说各个子问题之间是有联系的，不是独立出来（分治算法）的。在这种情况下，如果我们利用分治，可能就会做许多不必要的动作，可能会重复的求解公共的子问题。所以动态规划要求每一个子问题只求解一次，记录这些子问题的解。二、基本思想与策略 基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一