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

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

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

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

4、链表找合适的位置时就不用每次从第一个节点扫描。把一个有序顺序表插入另一个有序顺序表，合成的顺序表任然有序：数据结构三要素：逻辑结构，物理结构和数据的运算逻辑结构：指的是元素之间的逻辑关系，和数据怎么存储无关。逻辑结构一般分为线性结构和非线性结构线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系物理结构，也叫做存储结构。如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；算法：，求解特定问题步骤的描述，他是指令的有限序列如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据 有穷，确定，可行性

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

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

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

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

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

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

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

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

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

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

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

16、在矩阵中，多数的元素为0，通常认为非零元素比上矩阵所有元素的值小于等于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他

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

21、度。由于二叉链表存储的二叉树中存在大量空指针，我们用这些空链域存放指向其直接前驱和直接后继的指针。在遍历二叉树的时候，检查当前节点左右指针域是否为空，若为空，则把他们改为指向前驱节点或者后继节点的线索。在中序线索二叉树中，如何找节点的直接前驱？在后序线索二叉树中，如何找节点的直接前驱？计算机如何实现线索二叉树的遍历先说中序线索查找前驱节点：在中序线索树中找结点*p的中序直接前驱，也就是*p节点的左线索，查找他的左子树，如果他的左子树空，那么他的左线索就是他的直接前驱。 倘若左子树不为空，有左孩子，那就从他的左孩子开始查找，寻找左孩子的右子树，当右子树为空的节点就是他的直接前驱 自己画个图看看就

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

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

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

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

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

31、距离M集合所含节点最短距离的节点，初始化放置目标点A)和N（尚未找到最短路径的节点BCDE，右手比划），俩个集合都用数组来表示。现在第一次循环，从集合M出发，搜索M里面的所有节点（只有A一个）能够到达的最短路径节点，找到后将其放入M中（左手），并从N、（右手）中删除这个点。下一轮循环，从集合M（假设现在哟了A,B）出发，以最短路径到达集合N中的节点，假设C。然后把C放入M中，并将其从N中删除。动态规划算法，典型运用？答：一、基本概念 动态规划通过组合子问题的解而解决整个问题。分治算法则是把问题分解成一些独立子问题，递归的求解各个子问题，然后合并子问题的解得到原问题的解。然而动态规划适用于子问题

32、不是独立的情况，也就是说各个子问题之间是有联系的，不是独立出来（分治算法）的。在这种情况下，如果我们利用分治，可能就会做许多不必要的动作，可能会重复的求解公共的子问题。所以动态规划要求每一个子问题只求解一次，记录这些子问题的解。二、基本思想与策略 基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。 由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计算，

33、对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。用于解决：数学三角形问题。或者在导航中选择最优路径问题。装配线问题：两条装配线执行相同的功能，但是装配速度不同。求解问题是确定在装配线1选择那些站点，装配线2选择那些站点使得汽车通过工厂的时间最短。什么是多项式非确定性问题？答：是一个数学问题，我们所学的算法大多是多项式时间的算法，对于规模N的输入，他们最坏情况运行时间就是NK时间，是否所有问题都可以在多项式时间内

34、解决？，不是的。停机问题，理发师悖论这些。NP完全问题，他的状态为止。NP是多项式复杂程度非确定性问题（P对NP，P versus NP，polynomial versus nondeterministic polynomial）是指1971年Leonid Levin和Stephen Cook提出的一个关于容易解答的问题（p型）以及相反的难以解答的问题（NP型）的数学理论问题。P问题：一个问题可以在多项式（O(nk)）的时间复杂度内解决。NP问题：一个问题的解可以在多项式的时间内被验证。大整数因式分解问题-比如有人告诉你数可以分解成两个数的乘积，你不知道到底对不对，但是如果告诉你这两个数是11

35、23和8850，那么很容易就可以用最简单的计算器进行验证。任何P型问题都能够按照“多项式时代”解答（一个多项式包含许多项，每个项又包括了一个变量或者是乘以一个系数的变量的幂。组成原理 是分组交换，其他电路交换和报文都是报文一个单元原码:简单易懂，最大缺点就是加法运算复杂，异号相加麻烦（比较绝对值，大数-小数）补码可以减法转换为加法，使得机器总可以做加法运算。补码的符号位同数值位一起参加运算，也简化了运算器的结构。但是根据补码的定义，求负数的补码还要做减法，于是出现了反码（负数的补码就是在原码的基础上，符号位不变，其余位置取反后末尾加1）。移码主要用于浮点数的阶码，使用移码可以很方便的对浮点数的

36、阶码比较运算，无论正负，从符号位开始，逐个位置比较大小。而负数的补码，原码，反码却不能这样比较。浮点数表示方法浮点数由阶码E，尾数M，阶码的底R三部分组成，尾数M是一个定点小数，决定浮点数的有效值精度，一般用原码或者补码表示，阶码E是一个定点整数（有正负号之分），阶码位数越长，表示的范围越广，一般用移码或者补码。什么是中断？（外中断又称作硬中断 外设请求 和 内中断又叫做软中断，CPU内部数据溢出）由于某种原因导致CPU中止当前执行当前任务，转去对所发生的事件的处理，当处理结束后还能返回到中止发生的地方接着执行中止之前没有完成的任务。中断意义：中断时计算机系统结构的一大变革，它是现代多道程序得

37、以实现的基础，因为进程间的切换时依靠中断处理。中断不仅提高了处理机的效率，而且也使得外设和处理机并发工作。微程序控制器的基本思想计算机系统是按照一系列离散的步骤操作，一条指令可以分成一系列基本操作: 取指令，分析指令，和执行指令。这些步骤可以用软件的方法实现。每条指令都可以用一段微程序来实现。硬布线控制器和微程序比较根本区别在于微操作信号的产生方法不同，一个是微程序代码执行中在需要的时间从控制存储器中读取，另一个是组合逻辑电路产生的信号。微程序控制器属于存储逻辑电路，硬布线属于时序及组合逻辑电路，而且设计比较复杂。微程序容易扩充和修改，硬布线非常不利于修改扩充。微程序多用于Cisc，硬布线多用

38、于RiSC系统。CPU如何区分主存上的程序代码与数据的？答：在不同的周期区分，取指周期取指令流向控制器，执行周期取数据流向运算器。计算机的乘法运算是怎么做的？除法运算呢？答：乘法通过加减法和移位运算指令来实现的，还可以通过编制程序实现；而除法可以转换为乘法，乘法转成加法，减法也转成加法。cpu的功能？答：CPU是中央处理单元(Cntral Pocessing Uit)的缩写，它可以被简称做微处理器（mcroprocessor)，不过经常被人们直接称为处理器(processor)。 cpu是计算机的核心，作用和大脑更相似，因为它负责处理、运算计算机内部的所有数据，而主板芯片组则更像是心脏，它控制

39、着数据的交换。 cpu的种类决定了你使用的操作系统和相应的软件。CPU主要由运算器、控制器、寄存器组和内部总线等构成，是PC的核心，再配上储存器、输入/输出接口和系统总线组成为完整的PC。CPU三大部分：运算器，cache，控制器CPU有四个方面的基本功能：指令控制，操作控制，时间控制和数据加工。CPU中至少有6类寄存器： 数据缓冲寄存器DR，指令寄存器IR，程序计数器PC，数据地址寄存器AR，通用寄存器R0R3，状态字寄存器PSW。总线的结构，分类3种，单总线，双总线，多总线。 CPU内部总线和外部总线和通信总线。 并行总线和串行总线。 总线的信息传输3种方式，并行串行和分时传输。 运算器有

40、什么组成，有什么功能有ALU算数逻辑单元，通用寄存器，数据缓冲寄存器DR和状态条件寄存器PSW组成，他是数据加工处理部件，两大功能：1.执行所有的算术运算，2.执行所有的逻辑运算控制器由什么组成，有什么功能？程序计数器PC，指令寄存器IR，指令译码器ID，操作控制信号形成部件，时序信号产生器，地址寄存器AR，数据寄存器DR控制器的功能：他能够完成协调和指挥整个计算机系统的操作，1.从指令cache中取出一条指令，并指出下一条指令的位置。2.对指令进行译码或测试，并产生相应的操作控制信号，以便启动规定的动作，建立正确的数据通路；指挥并控制CPU，数据cache和输入输出设备间的数据流动的方向。A

41、LU的全称？答：ALU：Arithmetic Logic Unit，算术逻辑单元。定点运算器组成ALU算数逻辑单元，数据缓冲寄存器，通用寄存器，多路转换器，标志寄存器，内部总线等 评价计算机的三个指标？答：1、机器字长：CPU一次能并行处理的数据位数。2、主频：CPU的时钟周期。3、运算速度。4、存储的容量。5、存储周期。什么是寻址？基址寻址，变址寻址是什么，作用是什么？答：寻址是数据恢复技术的基础，是定位数据和扇区的关键。寻址这个概念比较抽象，简单的说是磁头在盘片上定位数据的一个过程。如果你想找到你的计算机中的一个文件，你可能会在Windows中先打开我的电脑、分区、文件夹，再打开你要找的文

42、件。这是表面的寻找文件的过程，而磁头在盘片的寻找过程就是寻址。基址寻址是将CPU中基址寄存器的内容，加上指令格式中的形式地址而形成操作数的有效地址变址寻址是在通用寄存器中，有些寄存器可作为变址寄存器。把变址寄存器的内容（通常是首地址）与指令地址码部分给出的地址（通常是位移量）之和作为操作数的地址来获得所需要的操作数就称为变址寻址。根据Flynn分类法，可以将计算机系统分为哪几类？答：四类。 单指令流单数据流机器(SISD)单指令流多数据流机器(SIMD)多指令流单数据流机器(MISD)多指令流多数据流机器(MIMD)计算机组成原理关于溢出？指的是运算结果超出了机器数的表示范围，就发生了溢出 对

43、于加减法运算来说，只有当同号两数相加或者异号两数相减才可能会发生溢出 。两个正数相加，结果大于机器字长所能表示的最大正数，称正溢出两个负数相加，结果小于机器所能表示的最小负数，成福溢出本来结果是正的，溢出之后变成负的，叫做正溢出。判别溢出：根据运算结果的最高位进位和符号位的进位进行异或运算。倘若异或结果为0，即最高位进位和符号位进位相同时，没有发生溢出，否则就发生了溢出。 称之为单符号位判别第二种采用双符号位 称之为变形补码。任何正数符号位都是00，任何负数符号位都是11.计算结果如果是01，那么发生正溢出；如果是10则发生负溢出。借助异或运算，两个符号位相同就没溢出。地址线，数据线是干什么的

44、？答：地址线是用来传输地址信息用的。地址线传递地址机器指令和微指令？答：机器指令和微指令的关系归纳如下：1. 一条机器指令对应一个微程序，这个微程序是由若干条微指令构成的。因此，一条机器指令的功能是若干条微指令组成的序列来实现的。简而言之，一条机器指令所完成的操作划分成若干条微指令来完成，由微指令进行解释和执行。2.从指令与微指令，程序与微程序，地址与微地址的一一对应关系上看，前者与内存储器有关，而后者与控制存储器（它是微程序控制器的一部分。微程序控制器主要由控制存储器、微指令寄存器和地址转移逻辑三部分组成。其中，微指令寄存器又分为微地址寄存器和微命令寄存器两部分）有关，与此相关也有相对应的硬

45、设备。3.从一般指令的微程序执行流程图可以看出。每个CPU周期就对于一条微指令。这就告诉我们怎么设计微程序，也将使得我们进一步体验到机器指令很微指令的关系。什么是存储元，什么是存储单元，什么是存储单元地址？答：存储器是由大量寄存器组成的，其中每一个寄存器就称为一个存储单元。它可存放一个有独立意义的二进制代码。一个代码由若干位（bit）组成，代码的位数称为位长，习惯上也称为字长。存放一个机器字的存储单元叫做字存储单元；相应的单元地址叫做字地址。 存储元（Storage Unit）是存储器的最小存储单元，它的作用是用来存放一位二进制代码0或1。存储单元一般应具有存储数据和读写数据的功能，以8位二进

46、制作为一个存储单元，也就是一个字节。每个单元有一个地址，是一个整数编码，可以表示为二进制整数。储单元地址在计算机中的存储器往往有成千上万个存储单元，为了使存入和取出不发生混淆，必须给每个存储单元一个唯一的固定编号。内中断 和外中断区别？答：中断信号的来源不同，内中断信号源是内部的，外中断的信号源来自外部。答：指当出现需要时，CPU暂时停止当前程序的执行转而执行处理新情况的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU立即处理的情况，此时，CPU暂时中止程序的执行转而处理这个新的情况的过程就叫做中断。cache和虚拟存储器结构（OS）的区别？答：工作环境不同：Cache是介于CP

47、U和主存之间的存储器，虚拟存储器是介于主存和辅存之间的存储器。目的不同：虚拟存储器是为了从逻辑上实现内存扩充而引进的。而cache是为了缓解CPU和主存速度差异而引进的。实现方式不同：cache用全硬件实现，虚拟存储器在主存和辅存之间用软件实现。Cache的命中率必须很高，一般要达到90%以上，才能使访存的速度跟得上CPU的速度。在CPU和Cache之间通常一次传送一个字块，字块的长度是只有几十字节，而虚拟存储器访问速度要比cache慢得多，而且信息块划分方案很多，有页、段等等，长度均在几百几百K 字节左右。，虚拟存储器的实现方两种 请求分页和请求分段；请求分页是在分页系统上增加请求调页和页面

48、置换功能形成的页式虚拟存储系统。 cache和虚拟存储都是基于时间局部性和空间局部性原理。Cache的命中率和什么有关：程序自身结构2.cache的容量大小.cache的组织方式和块的大小内存和cache分别是什么区别？答：内存，是存储器，用于辅助CPU输入输出数据进行运算。cache，是一种特殊的内存。因为COU速度和主存的速度不匹配，用少量的特别快的但特别昂贵的内存来做缓存加速。CPU cache 主存 cpu-主存辅存 的异同？答：根据概率统计，在90%的时间内CPU只对10%的内存进行访问。为了提高速度，增加容量，降低成本，目前各类计算机中已经广泛采用多层次存储器结构，即采用DRAM组

49、成高速缓存（cache memory）存放做常用的数九；用DRAM组成内存，存放次常用的大量数据；将不常用的数据存放在虚拟内存（virtual memory）的硬盘中，除CPU内部寄存器外，由上向下分三个层次，即高速缓存、主存和辅存。容量逐级增大，速度逐级降低，成本逐级减少。从整个结构看分两个层次，即“主存辅存“和”Cache主存“。内存有哪些引脚？答：各种内存条金手指引脚定义小全（72、144、168、152、184、200、240线） 内存的扩展方式？答：字拓展 增加存储器的容量 片选线不一样，地址线，数据线都用一根线位拓展 增加同一个地址下的存储单元的位数 地址线和片选线一样，不一样的数

50、据线，低8位数据线和高8位数据线 2根数据线字位同时拓展 内存条的作用？答；内存用是用于暂时存放CPU中的运算数据，以及与硬盘等外部存储器交换的数据。只要计算机在运行中，CPU就会把需要运算的数据调到内存中进行运算，当运算完成后CPU再将结果传送出来，内存的运行也决定了计算机的稳定运行。比如在使用WPS处理文稿时，在键盘上敲入字符时，它就被存入内存中，选择存盘时，内存中的数据才会被存入硬（磁）盘。寄存器？答：寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和地址。在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处

51、理器的算术及逻辑部件中，存器有累加器(ACC)。关于高速缓冲存储器的问题？答：高速缓存的出现就是因为处理器的高速读取数据的速度比内存储器的工作速度快太多.高速缓存是一种比处理器慢比内存快介于二者之间的一种储存装置。说一说Cache，谈一谈Wlan？答：Cache(即高速缓冲存储器(Cache Memory)。CPU在访问内存时，首先判断所要访问的内容是否在Cache中，如果在，就称为“命中”，此时CPU直接从Cache中调用该内容；否则，就称为“不命中”，CPU只好去内存中调用所需的子程序或指令了。CPU不但可以直接从Cache中读出内容，也可以直接往其中写入内容。由于Cache的存取速率相当

52、快，使得CPU的利用率大大提高，进而使整个系统的性能得以提升。WLAN，（wireless local area network） 无线局域网的意思，指应用无线通信技术将计算机设备互联起来，构成可以互相通信和实现资源共享的网络体系。虚拟存储器的思想是什么?答：虚拟存储器的基本思想是把作业地址空间和主存空间视为两个不同的地址空间。虚拟存储器：在具有层次结构存储器的计算机系统中，自动实现部分装入和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的地址结构和可用磁盘容量。特点：虚拟内存的作用 内存在计算机中的作用很大

53、，电脑中所有运行的程序都需要经过内存来执行，如果执行的程序很大或很多，就会导致内存消耗殆尽。为了解决这个问题，Windows中运用了虚拟内存技术，即拿出一部分硬盘空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。计算机由什么组成？答：计算机由软件和硬件组成。由硬件系统和软件系统组成：硬件系统分主机系统和外部设备。主机系统分中央处理器（CPU）、内存和主板。外部设备分外部存储设备、输入设备、输出设备。软降系统分基本输入输/输出系统（BIOS)、系统软件、应用软件DMA原理？他和中断的区别，通道的区别:答：DMA direct Memory Access 直接存

54、储器访问，简单来说，总线控制权在CPU“手上”，外设无权直接访问内存，需要CPU参与，但DMA控制器从CPU那“偷出”几个时钟来控制总线，让外设可以直接访问内存，这样外设的读写就不需要CPU参与，降低了CPU的占用率。DMA是直接存储器存取。DMA传输将数据从一个地址空间复制到另外一个地址空间。当CPU初始化这个传输动作，即，CPU向磁盘控制器发送一个命令，启动DM传送命令。整个传输动作本身是由DMA控制器来实行和完成。传输结束后，由DMA发送一个中断信号给CPU。在实现DMA传输时，是由DMA控制器直接掌管总线，因此，存在着一个总线控制权转移问题。即DMA传输前，CPU要把总线控制权交给DM

55、A控制器，而在结束DMA传输后，DMA控制器应立即把总线控制权再交回给CPU。 它与中断方式的主要区别在于，DMA方式只需要CPU在开始和完成传输时进行干预，其它时候不需要CPU干预。中断驱动方式在每个数据需要传输时中断CPU，而DMA方式则是在所要求传送的一批数据全部传送结束时才中断CPU。中断驱动方式数据传送是在中断处理时由CPU控制完成的，而DMA方式则是在DMA控制器的控制下完成的。DMA控制方式与通道控制方式有什么不同？答：在DMA控制方式中，DMA控制器控制设备和主存之间成批地进程数据交流，而不用CPU干预。这样不但减轻了CPU的负担，而且提高了I/O数据传送速度。这种控制方式应用

56、于块设备的数据传输。 通道控制方式与DMA控制方式类似，也是一种以内存为中心，实现设备与内存直接交换数据的控制方式。在通道控制方式中，CPU只需发出启动指令，指出通道相应的操作和I/O设备，该指令就可以启动通道并使通道从内存中调出相应的通道程序执行。与DMA相比，通道方式所需的CPU干预更少，并且可以做到一个通道控制多台设备，从而进一步减轻了CPU负担。什么是CISC和RISC ？简述它们的特点和区别？答：CISC的英文全称为“Complex Instruction Set Computer”，即“复杂指令系统计算机”，从计算机诞生以来，人们一直沿用CISC指令集方式。RISC的英文全称为“R

57、educed Instruction Set Computer”，即“精简指令集计算机”，是一种执行较少类型计算机指令的微处理器1、指令系统CISC计算机的指令系统比较丰富，有专用指令来完成特定的功能。因此，处理特殊任务效率较高。RISC设计者把主要精力放在那些经常使用的指令上，尽量使它们具有简单高效的特色。对不常用的功能，常通过组合指令来完成。因此，在RISC 机器上实现特殊功能时，效率可能较低。但可以利用流水技术和超标量技术加以改进和弥补。2、存储器操作CISC机器的存储器操作指令多，操作直接。RISC对存储器操作有限制，使控制简单化。3、程序CISC汇编语言程序编程相对简单，科学计算及复

58、杂操作的程序社设计相对容易，效率较高。RISC汇编语言程序一般需要较大的内存空间，实现特殊功能时程序复杂，不易设计。4、中断CISC机器是在一条指令执行结束后响应中断。RISC机器在一条指令执行的适当地方可以响应中断。5、CPUCISCCPU包含有丰富的电路单元，因而功能强、面积大、功耗大。RISCCPU包含有较少的单元电路，因而面积小、功耗低。6、设计周期CISC微处理器结构复杂，设计周期长。RISC微处理器结构简单，布局紧凑，设计周期短，且易于采用最新技术。7、用户使用CISC微处理器结构复杂，功能强大，实现特殊功能容易。RISC微处理器结构简单，指令规整，性能容易把握，易学易用。8、应用

59、范围CISC机器则更适合于通用机。RISC由于RISC指令系统的确定与特定的应用领域有关，故RISC 机器更适合于专用机。流水线技术和超标量技术流水线允许同时运行多条指令，使这些指令运行在不同的阶段，使各个部件都工作起来。超标量技术是在标量流水线基础上，采用资源重复利用，重复设置硬件资源，使一个时钟周期内能启动n条指令。数据库SQL特点：综合统一，集数据查询，数据操作，数据定义 数据控制功能于一体。 高度非过程化，只提做什么，不提怎么做。 面向集合的操作方式，操作对象可以是集合，查找结果也可以是集合 既是独立的语言，还是一门嵌入式语言，嵌入到C,C+ JAVA什么是函数依赖？举个例子。所谓函数

60、依赖是指关系中一个或一组属性的值可以决定其它属性的值。函数依赖正如一个函数 y = f(x) 一样，x的值给定后，y的值也就唯一地确定了。如果属性集合X中每个属性的值构成的集合唯一地决定了属性集合X中每个属性的值构成的集合，则属性集合Y函数依赖于属性集合X，计为：XY。X也称之为决定因素。例：身份证号姓名或者一个学生实体中有学号，性别，姓名。给了学号就唯一确定了其他属性。非平凡函数依赖： 如果XY，但是Y不属于X集合，则XY是非平凡函数依赖。完全函数依赖：在一个属性集合U中，如果XY，并且对于X的真子集X都不能确定Y，只有X才能确定Y，那么成Y对X完全函数依赖。否则称之为部分函数依赖。例如（学