19云南大学历年计算机专业复试题

数据结构云南大学抽两道题并答题。从一个大盒子里面抽俩，每个纸条上面的题目只有1个。根据回答情况追问，复试去的早的话，如果早上，那么老师问的比较多。学硕最长30分钟（前几个进去的同学）。专硕最短不到10分钟。老师如果感觉一天复试不完那么就会压缩时间，每个同学进入房间自我介绍（有的是中文，有的是英文），英语抽提，一个题有100多个单词，特别短，生词不多，readandtranslate翻译结束英语就结束了。接下来是专业问题抽提了。俩指头宽度的纸片，20多厘米长。塞满一个塑料盒子，叠着的。这篇文章里面的题能碰到1个就nice了。我就碰到了一个，是我瞄到一张没有完全折叠好的纸片，我熟悉那个问题所以perfect。专业题特别杂，看运气英语好的，能看懂句子成分的就不用准备英语了，下午去的同学，就随便准备一些英语问题，yourfamily,youruniversity,why,andyouroutlook?可能会问，时间紧就不问了，逆置一个顺序表，链表顺序表逆置:由于顺序表是连续存储的,循环表厂的一半，交换第一个和最后一个元素。i交换length-i，每做一次循环，i++。逆置一个链表：先保存第一个数据节点，p=L-next,后把头结点摘下L-next=NULL;遍历p的链表，头插法插入L表。遍历完出来L就是逆置的。排序一个顺序表，链表顺序表排序：2路归并排序，堆排序，冒泡排序，插入排序。折半插入排序排序链表：我们假设递增有序，采用直接插入排序法。先构造一个只有一个数据节点的有序单链表，然后外层循环依次遍历源单链表剩余节点，直到遍历结束，内层循环在有序单链表中比较大小查找合适节点插入。把一个有序单链表A插入另一个有序单链表B，合成的B链表任然有序：扫描A链表，取下节点，扫描B链表找到合适节点插入，若发现A链表空，则结束，若发现A链表不为空，B链表为空，则直接将A中剩余节点放入B中。改进方法：当我从A中取下节点插入B后，记录该节点的值。下次扫描B链表找合适的位置时就不用每次从第一个节点扫描。把一个有序顺序表插入另一个有序顺序表，合成的顺序表任然有序：数据结构三要素：逻辑结构，物理结构和数据的运算逻辑结构：指的是元素之间的逻辑关系，和数据怎么存储无关。逻辑结构一般分为线性结构和非线性结构线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系物理结构，也叫做存储结构。如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；算法：，求解特定问题步骤的描述，他是指令的有限序列如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据有穷，确定，可行性，输入输出52数组和线性表都是一组类型相同的数据元素的有序集合，而广义表的数据元素可以有不同的结构，广义表的元素可以是子表，而子表的元素还可以是广义表，数组是顺序存储的，链表既可以顺序又可以链式，广义表一般用链式存储广义表是一个多层次结构，他有长度（最外层包含元素个数）和深度（包含括弧的重数）的概念，一个广义表可以为其他广义表共享，而数组没有这个概念，数组有了名字，那他就有了一块连续的存储空间,不能被其他数组抢占和共享。线性表也可以共享，只要一个表中某个元素的后继是另一块表的一个元素，那就可以共享了。广义表可以是递归的表，链表也有循环单链表和循环双链表。在存储结构上，单链表可以有头结点，单链表的节点有指针域和数据域组成，数字没有这个概念，只有值，但是数组有下标，广义表的表节点由三个域组成，标志域，指示表头的指针域(hp)和指向下一个元素的指针域（tp）。什么是堆？什么是栈？什么是队列？有何区别？栈：只允许一端进行插入删除，的线性表。他的特点是先进去的后出来。队列：是一种操作受限的线性表，他只允许在一端口插入，另一端口删除。特点是先进先出。栈和队列都不允许随便读取或者删除中间的元素。堆的特征是什么，如何利用堆进行排序堆是一个完全二叉树。而且最大元素存放在根节点，任意一个非根节点，他的值小于或者等于双亲节点的值，这是大根对，小根堆与之相反堆排序第一步：构造一个初始堆，关键在于筛选。对于大根堆来说，就是若双亲节点的关键字小于左右子女的话，那就选取一个大子女和双亲交换。从下向上依次交换知道根节点为最大。初始大根堆建好了第二步：输出堆顶节点，用堆底元素填充根节点，输出的元素放在底部。因为堆我们用的是数组存储，输出元素一般在数组末尾。此时我们破坏了大根堆，所以要调整这个堆，这个堆已经不再包含输出元素，尽管输出元素还在堆上，但是堆是数组存储的，把根节点（一般比较小）向下和子女交换以维持大根堆性质。第三部再次输出根节点，重复上述步骤知道堆仅仅剩下一个元素为止。数据结构中图的存储中，邻接矩阵和邻接表的优缺点？答：图有邻接矩阵和邻接表两种存储方式所谓邻接矩阵就是，用一维数组存储图的顶点信息，用二维数组存储图的边的信息（各个顶点之间的关系。）所谓邻接表，就是用顺序存储的方式存储图的顶点，用连式存储存依附于此顶点的边。优缺点：邻接矩阵清晰明了，容易看出各个顶点是否有边相连。而邻接表则不能给人清晰的表示，他要在响应的节点对应的边表查找节点。但是邻接矩阵的存储效率比较差，如果图比较稀疏，那么矩阵就会有很大存储单元被浪费了，而我们的邻接表由于采用链式存储存储边的关系，所以避免了这种浪费。在查找边的个数方面，邻接矩阵要检测整个矩阵，时间是O(n)而邻接表很容易找出所有的邻边，只用读取对应顶点的邻接表就行了。在有向图求初度和入度方面，采用邻接矩阵，第一行非零元素个数就是顶点V1的出度，第一列非零个数就是V1的入度。而邻接表在求出度方面只需遍历边表中节点个数，在求入度方面要遍历整个表。十字链表是有向图的一中链式存储结构，包括弧节点(狐尾虎头，两个弧链域，弧头相同的在一个链表，狐尾相同的在一个链表)和顶点节点(数据域和两个链域，一个表示弧的起点(out)，一个表示弧的终点(in))，所以容易求节点的入度和出度。一个图的十字链表不是唯一的，但一个十字链表确定一个图。邻接多重链表是无向图的链式存储结构程序的健壮性？答：对于不规范的输入能够做出反应而不会产生奇怪的费解的输出结果。数据结构中排序的稳定性？答：对于待排序列中的值相等的元素来说比如a1=a2，如果排序结果没有改变这些值相等元素的相对位置，还是a1在前a2在后面。那么算法就是稳定的任意两个节点的最短路径？答：迪杰斯特拉算法最小生成树：在图所有生成树中，代价最小的生成树称为最小生成树。他包含图的所有顶点，并且包含尽可能少的边最小生成树不是唯一的，可以有多个，当图中边的权值互不相等，那么最小生成树就是唯一的。最小生成树的权值之和是唯一的，他的边数是顶点个数减去1构造生成树的算法：普利姆算法O(V2),适合求解边多，点少的图和克鲁斯卡尔O(ElogE)算法，适合求解边少，点多的图。欧拉图：具有欧拉回路的图就是欧拉图。欧拉回路是图中经过每条边切仅仅一次经过的回路叫做欧拉回路。那些图有欧拉回路？1无向图中，当且仅当图是连通图，而且图没有奇数度的顶点。2有相图，当且仅当图是联通的，且所有的顶点的入度=初度。哈密顿图有哈密顿回路的图。哈密顿回路经过每个顶点一次且仅仅一次的初级回路。哈密顿通路经过每个顶点一次且仅一次的通路。哈密顿图必然是连通图。在n个城市之间建造通信网络，至少要架设n-1条通信线路，而每两个城市之间架设通信线路的造价是不一样的，那么如何设计才能使得总造价最小最小生成树算法，生成树边的权重之和最小。什么是最小连通子图？既要保存图联通，又要保持图的边数最少。一个联通图的生成树是图的最小连通图。他包含图的所有顶点，包含尽可能少的边。如果砍去其中任意一条，都会让树变成非联通图。如果给他增加一条边，那就形成图的一条回路。如何产生最小连通图？那不就是生成树么，生成树有深度优先遍历和广度优先遍历算法；最小生成树有两种算法，克鲁斯卡尔和普里姆算法。But无向图的极大联通子图是无向图的联通分量。有向图的极大联通子图叫做有向图的强联通分量。怎样防止出现环？第一中方法要拓扑排序方法。在一个有向图中，我们采用拓扑排序，拓扑排序要求如果某个节点出现在另一个节点的前面如先A后B，那么接下来的排序中就不用该出现先B后A的路径。对有向图的拓扑排序，如果发现不存在拓扑排序，或者是排序没走完，剩下的图中不存在前驱的顶点，那就说明图中有环。第二种方法：求关键路径。关键路径本身就要求无环，一个工程的某个节点不能既是下一个节点开始的前提条件，又是下一个节点的产出；求关键路径也要求拓扑排序所以也可以来判断有没有环路。第三种方法：采用图的深度优先遍历算法。一条深度遍历路线中如果某个节点被第二次访问到，那就有环，因为深度优先路径是一条单链，访问过的节点保存下来就不应该再次被访问。拓扑排序和偏序，全序的关系：选课，课程之间有先后关系，制定选课顺序过程就是拓扑排序的过程。选课关系中有课程先后的关系，也有课程间没有特定顺序的关系，但是不允许出现1221这种互相矛盾的关系也就是环路。有向无环图两个顶点不存在环路，必然满足偏序关系。如果任意两个课程之间只有先后关系，并且没有换，那就是全序关系。原来的偏序变成了全序。排序算法1234，大小关系确定，唯一的，则这个序列满足全序关系。表现在拓扑排序中就是每个顶点间都具有全序关系，则拓扑排序结果唯一。若是偏序的关系，那就不唯一了。有向无环图在实际生活中的应用例子？日常导航嘛。区块链领域。什么是哈希表？如何构建哈希表？在构建哈希表过程中，会遇到什么问题，如何解决？答：哈希表（Hashtable，也叫散列表），是根据关键码值(Keyvalue)而直接进行访问的数据结构，他建立了关键字和存储地址之间的一种直接映射关系。怎么构建哈希表：在记录的存储位置和它的关键字之间建立一个确定的对应关系f即哈希函数。使每个关键字和表中唯一的存储位置相对应，根据这个思想建立的表为哈希表哈希表的做法其实很简单，首先要构造一个哈希函数，哈希函数的构造有直接定址法，除留余数法，平方取中法等等。我们那除留余数法做例子在，这个比较简单，也比较常用。关键字对一个不大于散列表长度的一个素数取余。取余结果就当作关键字的地址，关键字可以存放在数组里，（也可以存放在二叉树）构造这个散列表的过程中会遇到几个关键字映射到一个地址上面，也就产生了冲突。原因在于散列函数选取不当。处理冲突有开放定址法：线性探测查看下一个单元，链地址法：把所有同义词存放在一个链表里。不过对链表查找效率会变低，我们可以在链表上构建一平衡二叉树。Hashmap是什么：稀疏矩阵？答：如果在矩阵中，多数的元素为0，通常认为非零元素比上矩阵所有元素的值小于等于0.05时，则称此矩阵为稀疏矩阵（sparsematrix）。AOE网的始点和终点是什么？正常的AOE网只有一个始点和终点吗？答：关键路径（临界路径）：在AOE网络中从源点到汇点（结束顶点）的最大路长度的路径。关键路径可以有多条起始点：入度为0的点1个终点：仅有一个也叫做汇点出度为0关键路径上的活动为关键活动，带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间怎么能够判断判断一个图是连通还是非连通的？答：对于无向图来说，如果无向图联通的，那么从任意一个点出发，仅需要一次遍历就能访问所有的点。如果是非联通的，则从任意一个顶点出发，一次遍历只能访问此顶点所在联通分量的所有顶点，而剩余的节点无法通过这次遍历访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，那么一次遍历就可以访问所有的点，否则可以借助深度优先遍历，如果能遍历所有的点，那他就是联通的有向图和无向图的联系,试各举一例说明？答：无向图可以看作每条边都有两个方向的有向图，写成邻接矩阵的形式的话区别就很清楚；无向图的邻接矩阵一定是对称阵,而有向图则未必实际应用的区别是有向图可以描述非对称的关系,但无向图不能.比如你认识奥巴马,但是他不认识你,用图来表示人物关系时就将你和奥巴马之间连一条线,并且指向他.可以用来解决加快工程进度的问题。无