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

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

2、perfect。专业题特别杂，看运气英语好的，能看懂句子成分的就不用准备英语了，下午去的同学，就随便准备一些英语问题，your family ,your un iversity ,why, and your outlook?可能会问，时间紧就不问了，簡述数据的逻辑结构和韧理结构的概念和两者的关系簡述数据的逻辑结构和韧理结构的概念和两者的关系 next,后把头结点摘下 L-next=NULL;遍历 p 的链表，头插法插入 L 表。遍历完出来 L 就是逆置的。排序一个顺序表，链表顺序表排序：2 路归并排序，堆排序，冒泡排序，插入排序。折半插入排序排序链表：我们假设递增有序，采用直接插入排序法。先构

3、造一个只有一 个数据节点的有序单链表，然后外层循环依次遍历源单链表剩余节点，直到遍 历结束，内层循环在有序单链表中比较大小查找合适节点插入。把一个有序单链表 A 插入另一个有序单链表 B,合成的 B 链表任然有序：扫描 A 链表，取下节点，扫描 B 链表找到合适节点插入，若发现 A 链表 空，则结束，若发现 A 链表不为空，B 链表为空，则直接将 A 中剩余节点放入 B 中。改进方法：当我从 A 中取下节点插入 B 后，记录该节点的值。下次扫描 B 链表找合适的位置时就不用每次从第一个节点扫描。把一个有序顺序表插入另一个有序顺序表，合成的顺序表任然有序：数据结构三要 素：逻辑结构，物理结构和数

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

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

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

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

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

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

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

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

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

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

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

15、表：在记录的存储位置和它的关键字之间建立一个确定的对应关系f 即哈希函数。使每个关键字和表中唯一的存储位置相对应，根据这个思想建立的表为 哈希表哈希表的做法其实很简单，首先要构造一个哈希函数，哈希函数的构造有 直接定址法，除留余数法，平方取中法等等。我们那除留余数法做例子在，这 个比较简单，也比较常用。关键字对一个不大于散列表长度的一个素数取余。取余结果就当作关键字的地址，关键字可以存放在数组里，（也可以存放 在二叉树） 构造这个散列表的过程中会遇到几个关键字映射到一个地址上面，也就产生了冲突。原因在于散列函数选取不当。处理冲突有 开放定址法：线性探测 查看下一个单元，链地址法：把所有同义词存

16、放在一个链表里。不过对链表查找效率会变 低，我们可以在链表上构建一平衡二叉树。Hashmap 是什么：稀疏矩阵？答：如果在矩阵中，多数的元素为 0,通常认为非零元素比上矩阵所有元 素的值小于等于 0.05 时，则称此矩阵为稀疏矩阵（sparse matr 议。AOE 网的始点和终点是什么？正常的 AOE 网只有一个始点和终点吗？ 答：关键路径（临界路径）：在 AOE 网络中从源点到汇点（结束顶点） 的最大路长度的路径。关键路径可以有多条起始点：入度为 0 的点 1 个 终点：仅有一个也叫做汇点 出度为 0关键路径上的活动为关键活动，带权有向图中若以顶点表示事件，有向边 表示活动，边上的权值表示

17、该活动持续的时间怎么能够判断判断一个图是连通还是非连通的？答：对于无向图来说，如果无向图联通的，那么从任意一个点出发，仅需 要一次遍历就能访问所有的点。如果是非联通的，则从任意一个顶点出发，一次遍 历只能访问此顶点所在联通分量的所有顶点，而剩余的节点无法通过这次遍历 访问。对于有向图来说，若从初始点到图中的每个顶点都有路径，那么一次遍历 就可以访问所有的点，否则可以借助深度优先遍历，如果能遍历所有的点，那他就是联通的有向图和无向图的联系，试各举一例说明？答：无向图可以看作每条边都有两个方向的有向图，写成邻接矩阵的形式 的话区别就很清楚；无向图的邻接矩阵一定是对称阵，而有向图则未必实际应用的区别

18、是有向图可以描述非对称的关系，但无向图不能.比如你认识 奥巴马，但是他不认识你 用图来表示人物关系时就将你和奥巴马之间连一条线，并且指向他.可以用来解决加快工程进度的问题。无向图和有向图都可以用来寻找最优路径。有向图解决最低路径成本问 题。无向图能解决的问题都能用有向图表示，但是无向图在对称的问题上往往更 容易，因为用有向图去表示无向图时需要用两倍的边数。堆排序的思想是什么？答：n 个关键字序列 KI，K2，Kn 称为堆，当且仅当该序列满足如下 性质（简称堆性质）：ki K2i 且 ki K2i 且 ki K2i+1（1 i n ext;L- next=NULL;while(p)q=p;p=p

19、-n ext;q-n ext=L-n ext;L-n ext=q;二分查找？答：二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能 好；其缺点是要求待查表为有序顺序表，不适合连式存储。且插入删除困难。 因此，折半查找方法适用于不经常变动而查找频繁的有序列表。查找思想：首先将待查数据和排好顺序的顺序表中间的那个元素比较大 小，假设是升序，如果比中间的大，那就缩小范围查找右半部分的。依次缩小 范围找到返回，找不到就没有。我们可以用一个判定树来描述。分块查找（索引顺序查找）结合二分查找和顺序查找的优点。把查找表分成若干个子块，块里面的元 素可以无序，但是块间要有序。在建立一个索引表，索引表

20、的组成：索引表含 有每个各块中第一个元素的地址和块中最大元素的值，索引表按照关键字有序 排序。分块查找中，首先在索引表中可以用顺序查找或者折半查找来确定待查元 素在哪块（哪个分区）；然后第二步在快内顺序查找（只能用）。二路归并的实质是什么？答：归并排序 基于分治算法，将两个或两个以上的有序表组合成一个新 的有序表。把待 n 个元素排序表看做 n 个子表组合而成，然后每两个子表归 并，得到长度为 2 的新的子表，然后在两两归并如此重复一直到合并成长度为 n 的有序表为止。2 路排序是一个稳定的排序算法，时间效率是 O（NlogN） 一个无序的单链表怎样能让它变得有序，简单说明一下算法？ 答：贪心

21、算法是什么，能给出正确的答案吗？答：贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前 看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的每一步 骤都是这个问题的局部最优解。贪心算法认为一个全局最优解可以同局部最优选择（贪心）来达到，thatmeans 当考虑到如何选择时，我们只考虑当前问题最佳的选择，而不考虑子问 题的结果。这一点也是和动态规划不同的地方，动态规划认为，每一步都要做 出选择，但这些选择却依赖于子问题的解，因此动态规划问题一般是自底向 上，从下到大处理问题。但在贪心算法中，我们所做的总是当前最佳，不考虑 之后有什么不妥的问题，至于它产生的问题，贪心继续贪心

22、的处理。所以他当 前所做出的选择会在一定程度上依赖于他曾经做出的决策， 而不是依赖于那些 尚未解决的子问题。 所以他通常是自顶向下处理子问题，不断的吧问题分解为 更小的问题。齐王：上等马 中等马下等马田忌：上等马中等马下等马简述一下迪杰斯特拉草法,解决单源点最短路径问题。比如说有点 ABCDE , A 是目标点。现在有两个 集合 M（左手比划， 用来放搜寻到距离 M 集合所含节点最短距离的节点， 初始 化放置目标点 A） 和 N（尚未找到最短路径的节点 BCDE，右手比划），俩个集 合都用数组来表示。现在第一次循环，从集合 M 出发，搜索 M 里面的所有节点（只有 A 一 个）能够到达的最短路

23、径节点，找到后将其放入 M 中（左手），并从 N、（右 手）中删除这个点。下一轮循环，从集合 M （假设现在哟了 A,B）出发，以最短路径到达集合 N 中的节点，假设 C。然后把 C 放入 M 中，并将其从 N 中删除。动态规划算法，典型运用？答：一、基本概念动态规划通过组合子问题的解而解决整个问题。分治算法则是把问题 分解成一些独立子问题，递归的求解各个子问题，然后合并子问题的解得到原 问题的解。然而动态规划适用于子问题不是独立的情况，也就是说各个子问题 之间是有联系的，不是独立出来（分治算法）的。在这种情况下，如果我们利 用分治，可能就会做许多不必要的动作，可能会重复的求解公共的子问题。所

24、 以动态规划要求每一个子问题只求解一次，记录这些子问题的解。二、基本思想与策略基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了 有用的信息。在求解任一子问题时， 列出各种可能的局部解， 通过决策保留那 些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个 子问题就是初始问题的解。由于动态规划解决的问题多数有重叠子问题这个特点，为减少重复计 算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组 中。与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后 得到的子问题往往不是互相独立

25、的（即下一个子阶段的求解是建立在上一 个子阶段的解的基础上，进行进一步的求解）。用于解决：数学三角形问题。或者在导航中选择最优路径问题。装配线问题：两条装配线执行相同的功能，但是装配速度不同。求解问题是确定在装配线 1 选择那些站点，装配线 2 选择那些站点使得汽车 通过工厂的时间最短。什么是多项式非确定性问题？答：是一个数学问题，我们所学的算法大多是多项式时间的算法，对于规 模 N 的输入，他们最坏情况运行时间就是NK时间，是否所有问题都可以在多项式时间内解决？，不是的。停机问题，理发师悖论这些。NP 完全问题，他的状态为止。NP 是多项式复杂程度非确定性问题（P 对 NP，P versus

26、 NP polyno mial versusnon determi nistic poly nom）l 是扌旨 1971 年 Leonid Lev in 和 Stephen Cook 提出的一个关于容易解答的问题（p 型）以及相反的难以解答的问 题（NP 型）的数学理论问题。P 问题：一个问题可以在多项式（0（nk）的时间复杂度内解决。NP 问题：一个问题的解可以在多项式的时间内被验证。大整数因式分解问 题-比如有人告诉你数 9938550 可以分解成两个数的乘积，你不知道到底对不 对，但是如果告诉你这两个数是 1123 和 8850,那么很容易就可以用最简单的计 算器进行验证。任何 P 型问

27、题都能够按照“多项式时代”解答（一个多项式包含许多项， 每个项又包括了一个变量或者是乘以一个系数的变量的幕。组成原理龄铀龄的瓯？渦说说交瓠技术？邮种交换技术传输单元砂是分组交换，其他电路交换和报文都是报文一个单元补码対补码対什么什么还夢有移玛呢？还夢有移玛呢？选择重传协议-计葺机组成原理：移码和补码的区别。原码：简单易懂，最大缺点就是加法运算复杂，异号相加麻烦（比较绝对 值，大数-小数）补码可以减法转换为加法，使得机器总可以做加法运算。补码的符号位同 数值位一起参加运算，也简化了运算器的结构。但是根据补码的定义，求负数 的补码还要做减法，于是出现了 反码（负数的补码就是在原码的基础上，符号 位

28、不变，其余位置取反后末尾加 1）。移码主要用于浮点数的阶码，使用移码 可以很方便的对浮点数的阶码比较运算，无论正负，从符号位开始，逐个位置 比较大小。而负数的补码，原码，反码却不能这样比较。浮点数表示方法浮点数由阶码 E，尾数M，阶码的底 R 三部分组成，尾数M是一个定点小 数，决定浮点数的有效值精度，一般用原码或者补码表示，阶码E 是一个定点整数（有正负号之分），阶码位数越长，表示的范围越广，一般用移码或者补 码。什么是中断？（外中断又称作硬中断 外设请求 和 内中断又叫做软中断，CPU 内部 数据溢出）由于某种原因导致 CPU 中止当前执行当前任务，转去对所发生的事 件的处理，当处理结束后

29、还能返回到中止发生的地方接着执行中止之前没有完 成的任务。中断意义：中断时计算机系统结构的一大变革，它是现代多道程序得以实 现的基础，因为进程间的切换时依靠中断处理。中断不仅提高了处理机的效 率，而且也使得外设和处理机并发工作。微程序控制器的基本思想计算机系统是按照一系列离散的步骤操作，一条指令可以分成一系列基本 操作：取指令，分析指令，和执行指令。这些步骤可以用软件的方法实现。每 条指令都可以用一段微程序来实现。硬布线控制器和微程序比较根本区别在于微操作信号的产生方法不同， 一个是微程序代码执行中在需 要的时间从控制存储器中读取，另一个是组合逻辑电路产生的信号。微程序控制器属于存储逻辑电路，

30、 硬布线属于时序及组合逻辑电路， 而且 设计比较复杂。微程序容易扩充和修改，硬布线非常不利于修改扩充。微程序多用于 Cisc，硬布线多用于 RiSC 系统。CPU 如何区分主存上的程序代码与数据的？答：在不同的周期区分，取指周期取指令流向控制器，执行周期取数据流 向运算器。计算机的乘法运算是怎么做的？除法运算呢？答：乘法通过加减法和移位运算指令来实现的，还可以通过编制程序实 现；而除法可以转换为乘法，乘法转成加法，减法也转成加法。cpu 的功能？答：CPU 是中央处理单元（Cntral Pocessing Uit 的缩写，它可以被简称做微 处理器（mcroprocessor）不过经常被人们直接

31、称为处理器 （processor）cpu 是计算机的核心，作用和大脑更相似，因为它负责处理、运算计算 机内部的所有数据，而主板芯片组则更像是心脏，它控制着数据的交换。cpu 的种类决定了你使用的操作系统和相应的软件。 CPU 主要由运算 器、控制器、寄存器组和内部总线等构成，是 PC 的核心，再配上储存器、输 入/输出接口和系统总线组成为完整的 PC。CPU 三大部分：运算器，cache 控制器CPU 有四个方面的基本功能：指令控制，操作控制，时间控制和数据加 工。CPU 中至少有 6 类寄存器：数据缓冲寄存器 DR，指令寄存器 IR,程序计数器 PC，数据地址寄存器 AR,通用寄存器 R0R

32、3,状态字寄存器 PSW。总线的结构，分类3 种，单总线，双总线，多总线。CPU 内部总线和外部总线和通信总线。并行总线和串行总线。总线的信息传输 3 种方式，并行串行和分时传输。运算器有什么组成，有什么功能有 ALU 算数逻辑单元，通用寄存器，数据缓冲寄存器 DR 和状态条件寄存 器 PSW 组成，他是数据加工处理部件，两大功能：1执行所有的算术运算，2. 执行所有的逻辑运算控制器由什么组成，有什么功能？程序计数器 PC，指令寄存器 IR，指令译码器 ID，操作控制信号形成部件，时序信号产生器，地址寄存器 AR，数据寄存器 DR控制器的功能：他能够完成协调和指挥整个计算机系统的操作，1 从指

33、令 cache 中取出一条 指令，并指出下一条指令的位置。2 对指令进行译码或测试，并产生相应的操 作控制信号，以便启动规定的动作，建立正确的数据通路；指挥并控制 CPU， 数据 cache 和输入输出设备间的数据流动的方向。ALU 的全称？答：ALU : Arithmetic Logic Unit，算术逻辑单元。定点运算器组成ALU 算数逻辑单元，数据缓冲寄存器，通用寄存器，多路转换器，标志寄 存器，内部总线等评价计算机的三个指标？答：1、机器字长：CPU 一次能并行处理的数据位数。2、主频：CPU 的时 钟周期。3、运算速度。4、存储的容量。5、存储周期。什么是寻址？基址寻址，变址寻址是什

34、么，作用是什么?答：寻址是数据恢复技术的基础，是定位数据和扇区的关键。寻址这个概 念比较抽象，简单的说是磁头在盘片上定位数据的一个过程。如果你想找到你 的计算机中的一个文件，你可能会在 Windows 中先打开我的电脑、分区、文件 夹，再打开你要找的文件。这是表面的寻找文件的过程，而磁头在盘片的寻找 过程就是寻址。基址寻址是将 CPU 中基址寄存器的内容，加上指令格式中的形式地 址而形成操作数的有效地址变址寻址是在通用寄存器中，有些寄存器可作为变址寄存器。把变址 寄存器的内容（通常是首地址）与指令地址码部分给出的地址（通常是位 移量）之和作为操作数的地址来获得所需要的操作数就称为变址寻址。根据

35、 Flynn 分类法，可以将计算机系统分为哪几类？答：四类。 单指令流单数据流机器（SISD）单指令流多数据流机器（SIMD）多指令流单数据流机器（MISD）多指令流多数据流机器（MIMD）计算机组成原理关于溢出？指的是运算结果超出了机器数的表示范围，就发生了溢出对于加减法运算来说，只有当同号两数相加或者异号两数相减才可能会 发生溢出 。两个正数相加，结果大于机器字长所能表示的最大正数，称正溢出两个负数相加，结果小于机器所能表示的最小负数，成福溢出本来结果是正的，溢出之后变成负的，叫做正溢出。判别溢出：根据运算结果的最高位进位和符号位的进位进行异或运算。倘 若异或结果为 0,即最高位进位和符号

36、位进位相同时，没有发生溢出，否则就 发生了溢出。 称之为单符号位判别第二种采用双符号位 称之为变形补码。任何正数符号位都是 00,任何负 数符号位都是11计算结果如果是 01,那么发生正溢出；如果是 10 则发生负溢 出。借助异或运算，两个符号位相同就没溢出。地址线，数据线是干什么的？答：地址线是用来传输地址信息用的。地址线传递地址机器指令和微指令？答：机器指令和微指令的关系归纳如下：1. 一条机器指令对应一个微程 序，这个微程序是由若干条微指令构成的。因此，一条机器指令的功能是若干 条微指令组成的序列来实现的。简而言之，一条机器指令所完成的操作划分成 若干条微指令来完成，由微指令进行解释和执

37、行。2.从指令与微指令，程序与微程序， 地址与微地址的一一对应关系上看， 前者与内存储器有关， 而后者与 控制存储器 （它是微程序控制器的一部分。微程序控制器主要由控制存储器、 微指令寄存器和地址转移逻辑三部分组成。其中，微指令寄存器又分为微地址 寄存器和微命令寄存器两部分）有关，与此相关也有相对应的硬设备。3.从一般指令的微程序执行流程图可以看出。每个CPU 周期就对于一条微指令。这就告诉我们怎么设计微程序，也将使得我们进一步体验到机器指令很微指令的关 系。什么是存储元，什么是存储单元，什么是存储单元地址？答：存储器是由大量寄存器组成的，其中每一个寄存器就称为一个存储单 元。它可存放一个有独

38、立意义的二进制代码。一个代码由若干位（bit）组成，代码的位数称为位长，习惯上也称为字长。存放一个机器字的存储单元叫做字 存储单元；相应的单元地址叫做字地址。存储元（Storage Unit）是存储器的最小存储单元，它的作用是用来存 放一位二进制代码 0 或 1。存储单元一般应具有存储数据和读写数据的功能，以8 位二进制作为一个存储单元，也就是一个字节。每个单元有一个地址，是一个整数编 码，可以表示为二进制整数。储单元地址在计算机中的存储器往往有成千上万个存储单元，为了使存入和取出不发生混淆，必须给每个存储单元一个唯一的固定编号。内中断和外中断区别？答：中断信号的来源不同，内中断信号源是内部的

39、，外中断的信号源来自 外部。答：指当出现需要时，CPU 暂时停止当前程序的执行转而执行处理新情况 的程序和执行过程。即在程序运行过程中，系统出现了一个必须由CPU 立即处理的情况，此时，CPU 暂时中止程序的执行转而处理这个新的情况的过程就叫 做中断。cache 和虚拟存储器结构（OS 的区别？答：工作环境不同：Cache 是介于 CPU 和主存之间的存储器，虚拟存储器是介 于主存和辅存之间的存储器。目的不同：虚拟存储器是为了从逻辑上实现内存扩充而引进的。而cache是为了缓解 CPU 和主存速度差异而引进的。实现方式不同：cache 用全硬件实现，虚拟存储器在主存和辅存之间用软件 实现。Ca

40、che 的命中率必须很高，一般要达到 90%以上，才能使访存的速度跟得 上 CPU 的速度。在 CPU 和 Cache 之间通常一次传送一个字块，字块的长度是 只有几十字节，而虚拟存储器访问速度要比 cache 慢得多，而且信息块划分方 案很多，有页、段等等，长度均在几百 几百 K 字节左右。，虚拟存储器的实现方两种请求分页和请求分段；请求分页是在分页系统上增加请求调页和页面置换功能形成的页式虚拟存储系统。cache 和虚拟存储都是基于时间局部性和空间局部性原理。Cache 的命中率和什么有关：程序自身结构 2.cache 的容量大小.cache 的组织方式和块的大小内存和 cache 分别是

41、什么区别？答：内存，是存储器，用于辅助 CPU 输入输出数据进行运算。cache，是- 种特殊的内存。因为 COU 速度和主存的速度不匹配，用少量的特别快的但特 别昂贵的内存来做缓存加速。CPU cache 主存 cpu-主存一辅存 的异同？答：根据概率统计，在 90%的时间内 CPU 只对 10%的内存进行访问。为 了提高速度，增加容量，降低成本，目前各类计算机中已经广泛采用多层次存 储器结构，即采用 DRAM组成高速缓存（cache memory 存放做常用的数九； 用 DRAM 组成内存，存放次常用的大量数据；将不常用的数据存放在虚拟内存（virtual memory）的硬盘中，除 CP

42、U 内部寄存器外，由上向下分三个层次，即高速缓存、主存和辅存。容量逐级增大，速度逐级降低，成本逐级减少。从 整个结构看分两个层次，即“主存一一辅存“和” Cache-主存“。内存有哪些引脚？答：各种内存条金手指引脚定义小全（72、144、168、152、184、200、240 线）内存的扩展方式?答：字拓展 增加存储器的容量片选线不一样，地址线，数据线都用一根线位拓展 增加同一个地址下的存储单元的位数地址线和片选线一样，不一样的数据线，低 8 位数据线和高 8 位数据线 2 根数据线字位同时拓展内存条的作用？答；内存用是用于暂时存放 CPU 中的运算数据，以及与硬盘等外部存储器 交换的数据。只

43、要计算机在运行中， CPU 就会把需要运算的数据调到内存中进 行运算， 当运算完成后 CPU再将结果传送出来，内存的运行也决定了计算机的 稳定运行。比如在使用 WPS 处理文稿时，在键盘上敲入字符时，它就被存入内 存中，选择存盘时，内存中的数据才会被存入硬(磁)盘。寄存器？答：寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存 贮部件，它们可用来暂存指令、数据和地址。在中央处理器的控制部件中，包 含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处理器的算术及逻辑部 件中，存器有累加器(ACC)。关于高速缓冲存储器的问题？答：高速缓存的出现就是因为处理器的高速读取数据的速度比

44、内存储器的 工作速度快太多高速缓存是一种比处理器慢比内存快介于二者之间的一种储存 装置。说一说 Cache，谈一谈 Wlan ？答：Cache 即高速缓冲存储器(CacheMemory)。CPU 在访问内存时，首先 判断所要访问的内容是否在 Cache 中，如果在，就称为“命中”，此时 CPU 直 接从 Cache 中调用该内容；否则，就称为“不命中”，CPU 只好去内存中调用所需的子程序或指令了。 CPU 不但可以直接从 Cache 中读出内容，也可以直接 往其中写入内容。由于 Cache 的存取速率相当快，使得 CPU 的利用率大大提 高，进而使整个系统的性能得以提升。WLAN，( wir

45、eless local area network) 无线局域网的意思，指应用无线通信技术将计算机设备互联起来，构成可以互相通信和实现资源共享的网络体系。虚拟存储器的思想是什么？答：虚拟存储器的基本思想是把作业地址空间和主存空间视为两个不同的 地址空间。虚拟存储器：在具有层次结构存储器的计算机系统中，自动实现部分装入 和部分替换功能，能从逻辑上为用户提供一个比物理贮存容量大得多，可寻址 的“主存储器”。虚拟存储区的容量与物理主存大小无关，而受限于计算机的 地址结构和可用磁盘容量。特点：虚拟内存的作用 内存在计算机中的作用很大，电脑中所有运行的程 序都需要经过内存来执行，如果执行的程序很大或很多，

46、就会导致内存消耗殆 尽。为了解决这个问题，Windows 中运用了虚拟内存技术，即拿出一部分硬盘 空间来充当内存使用，当内存占用完时，电脑就会自动调用硬盘来充当内存， 以缓解内存的紧张。计算机由什么组成？答：计算机由软件和硬件组成。由硬件系统和软件系统组成：硬件系统分 主机系统和外部设备。主机系统分中央处理器（CPU）、内存和主板。外部设 备分外部存储设备、输入设备、输出设备。软降系统分基本输入输/输出系统（BIOS）、系统软件、应用软件DMA 原理？他和中断的区别，通道的区别：答：DMAdirect Memory Access 直接存储器访问，简单来说，总线控制权 在 CPU “手上”，外设

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

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

49、不但减轻了 CPU 的负担，而且提高了 I/O 数据传 送速度。这种控制方式应用于块设备的数据传输。通道控制方式与 DMA 空制方式类似，也是一种以内存为中心，实现设 备与内存直接交换数据的控制方式。在通道控制方式中，CPL 只需发出启动指令，指出通道相应的操作和 I/O 设备，该指令就可以启动通道并使通道从内存 中调出相应的通道程序执行。与 DMA 相比，通道方式所需的 CPU 干预更少，并 且可以做到一个通道控制多台设备，从而进一步减轻了CPU 负担。什么是 CISC 和 RISC ?简述它们的特点和区别？答：CISC 的英文全称为“ Complex I nstructio n Set C

50、ompute”，即“复杂指 令系统计算机”，从计算机诞生以来，人们一直沿用CISC 指令集方式。RISC 的英文全称为“ Reduced Instruction Set Computer，即“精简指令集计算机”，是一种执行较少类型计算机指令的微处理器1、指令系统CISC计算机的指令系统比较丰富，有专用指令来完成特定的功能。因此，处理 特殊任务效率较高。RISC设计者把主要精力放在那些经常使用的指令上，尽量使它们具有简单高效的特色。对不常用的功能，常通过组合指令来完成。因此，在RISC 机器上实现特殊功能时，效率可能较低。但可以利用流水技术和超标量技术加以改进和 弥补。2、存储器操作CISC机器

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

52、7、用户使用CISC微处理器结构复杂，功能强大，实现特殊功能容易。RISC微处理器结构简单，指令规整，性能容易把握，易学易用。8、应用范围CISC机器则更适合于通用机。RISC由于 RISC 指令系统的确定与特定的应用领域有关，故RISC 机器更适合于专用机。流水线技术和超标量技术流水线允许同时运行多条指令，使这些指令运行在不同的阶段，使各 个部件都工作起来。超标量技术是在标量流水线基础上，采用资源重复利用，重复设置硬件资源，使一个时钟周期内能启动 n 条指令数据库SQL特点：综合统一，集数据查询，数据操作，数据定义数据控制功能于-体。高度非过程化，只提做什么，不提怎么做。面向集合的操作方式，

53、操作对象可以是集合，查找结果也可以是集 合既是独立的语言，还是一门嵌入式语言，嵌入到 C,C+ JAVA什么是函数依赖？举个例子。所谓函数依赖是指关系中一个或一组属性的值可以决定其它属性的值。 函 数依赖正如一个函数 y = f（x） 样，x 的值给定后，y 的值也就唯一地确定 了。如果属性集合 X 中每个属性的值构成的集合唯一地决定了属性集合X 中每个属性的值构成的集合，贝 U 属性集合丫函数依赖于属性集合 X，计为：X-Y。X 也 称之为决定因素。例：身份证号一姓名或者一个学生实体中有学号，性别，姓 名。给了学号就唯一确定了其他属性。非平凡函数依赖： 如果 X-Y，但是丫不属于 X 集合，

54、则 X-丫是非平凡函数依赖。完全函数依赖：在一个属性集合 U 中，如果 X-丫，并且对于 X 的真子集 X都不能确定丫，只有 X 才能确定丫，那么成丫对 X 完全函数依赖。否则称 之为部分函数依赖。例如（学号，课程号码）-（学生系别），是部分函数依赖。学号是X的子集和。（学号，专业号）-（学生成绩）是完全函数依赖。码的概念所谓码就是能唯一标识实体的属性，是整个实体集的性质，而不是单个实体的性质。它包括超码，候选吗，主码。候选码就是可以区别一个元组（即表中的一行数据）的属性或属性的集合，比如学生表student（id,name,age,sex,deptno）,其中的id是可以唯一标识一个元组的，

55、所以id是可以作为候选码的，既然id都可以做候选码了，那么id和name这两个属性的组合可不可以唯一区别一个元组呢？显然是可以的。此时的id可以成为码，id和name的组合也可以成为码，但是id和name的组合不能称之为候选 码，因为候选码的定义就是要求这组属性要对候选码完全函数依赖，不是部分函数依赖。什么是逻辑蕴含对于满足一组函数依赖F的关系模式R(U,F)，对于其中任何一个关系r都有函数依赖X确定Y,换句话说就是r里的任一元组t和s都有给定一个确定的tx=ss都有ty=sy，我们就说F逻辑蕴含X确定YAimstron公理的完备性的含义是什么公理的完备性的含义是什么。绐出求绐出求X属性闭包的

56、算滦属性闭包的算滦“如何证如何证明该算明该算法的正法的正确柱。确柱。 简迷数据庄中码的概念。简迷数据庄中码的概念。Armstrong 公理是什么，他的有效性含义和完备性含义说的是什么：这个公理系统包含三个推理 规则:自反律，增广律和传递律在关系模式中，F 所逻辑蕴含的函数依赖的全体称之为 F 的闭包F+有效性指的是：由数据依赖F出发根据Armstrong公理推导除了的每一个函数依赖都一定在中F+中。 r 绍， 老师面无喪情， 抽题， 我扌由到数捉库的”题目是什也事駆数依赣* 叽里呱啦答了一惟，老师又问件么是码，叽里呱啦后老师又问关爭表根据什么来简化，我说 根1 完备性：奉 F 闭包中的每一个函

57、数依赖，袖定可以有程 F 出发根据 Armstrong 公理推导出来旬速鷹就会越悵，惡杞衡裳杂程宸和实际需求后来划分，老师估计有点不高光。说可臥走了。文件系统的数据是面向某一个应用的，文件的共享性差，冗余度大，独立性差，文件的距离虽然有结构，但整体无结构，数据是某一个应用的私有资 源，只被这个系统或应用使用数据库的独立性包括物理独立性和逻辑独立性。物理独立性指的是用户的应用程序和数据库的物理存储是相互独立的， 怎 么存怎么放是由 DBMS 关心的，应用程序不需关心逻辑独立性指的是应用程序和数据库的逻辑结构是相互独立的，换句话 说，数据的逻辑结构改变，应用程序也可以不变。数据库中的数据面向整个组

58、织整个企业，不是某个应用。数据共享性高, 冗余度小。简遠数简遠数ts库中依輟遷辑蕴含的库中依輟遷辑蕴含的槪念。槪念。匸什么是概念模型，有什么作 Am概念模型是现实世界到机器世界的一个中间层次，用于信息世界的建模，是数据库设计人员进行数据库设计的有力工具，也是设计人员和用户进行交流 的语言。概念模型是各种数据模型的共同基础，我们用 ER 图描述概念模型。特点：能够真实反映出现实世界，包括事物之间的联系；易于用户理解，便于和设计人员交流；易于更改；易于向其他数据模型转换。关系模型的三个组成部分：关系数据结构，关系操作集合，关系完整性约 束三部分关系模型优缺点：关系模型建立在严格的数学概念基础上；关

59、系模型的概念单一，无论实体 还是实体间的联系，都用关系表示，对数据的检索和更新也是关系；关系模型 的存取路径对用户透明，有更高的数据独立性和安全性，同时也简化了程序员 的工作和数据库开发缺点：由于存取路径对用户隐蔽，查询效率低，不如其他模型。数据库关系模式中，为何要满足不同的模式，这样做可以解决什么问题？ 答：在一个关系模式中可能存在数据冗余， 某个数据重复出现浪费大量空 间的情况， 还可能出现更新异常，插入异常伤处异常这些情况。为什么会有这 种异常发生呢，就是这个模式中的函数依赖存在负面性质。所以要对关系模式 规范化处理，也就是根据函数间依赖情况划分不同范式，消除数据依赖中不合 适的地部分，

60、消除插入异常删除异常。怎么避免数据冗余：首先要知道数据冗余怎么产生的，最容易出现的就是：当同一条数据存储在两个或多个单独的位置时，这种情况特别容易产生数据冗余。还有，备份数 据也会产生数据冗余，错误的数据也会发生数据冗余。怎么避免 我们可以对数据进行规范化管理，采取更为严格的数据库范 式，比如 BCNF范式或者第四范式。逐步消除数据依赖中不合理的地方，设计 更为高效的数据库。或者还可以组织数据库的序列，对数据进行分类存储。项目数据库中大对象，如何存储文本？答：使用的是将文本当做字符串处理。数据库怎么加入新的数据？答: insert into笛卡尔积:笛卡尔积是域上的一种集合运算。域是一组具有相