logo资料库

云南大学2019计算机专业复试题.docx

发布时间：2022-06-22 发布人：admin 分类：说明书 资料大小：0.86M 资料格式：docx 举报 版权申诉
第1页 / 共102页
第2页 / 共102页
第3页 / 共102页
第4页 / 共102页
第5页 / 共102页
第6页 / 共102页
第7页 / 共102页
第8页 / 共102页
资料共102页，剩余部分请下载后查看
    数据结构
    组成原理
    数据库
    计算机网络：
    操作系统
     软件工程
    离散数学，线性代数，编译原理
    编程题
    数据结构 云南大学 抽两道题并答题。从一个大盒子里面抽俩，每个纸条上面的题目只有 1 个。 根据回答情况追问，复试去的早的话，如果早上，那么老师问的比较多。学硕最长 30 分钟 （前几个进去的同学）。专硕最短不到 10 分钟。老师如果感觉一天复试不完那么就会压缩 时间，每个同学进入房间 自我介绍（有的是中文，有的是英文），英语抽提，一个题有 100 多个单词，特别短，生词不多，read and translate 翻译结束英语就结束了。接下来是专业 问题抽提了。俩指头宽度的纸片，20 多厘米长。塞满一个塑料盒子，叠着的。 这篇文章里面的题能碰到 1 个就 nice 了。我就碰到了一个，是我瞄到一张没有完全折 叠好的纸片，我熟悉那个问题所以 perfect。 专业题特别杂，看运气 英语好的，能看懂句子成分的就不用准备英语了，下午去的同学，就随便准备一些英语 问题，your family ,your university ,why, and your outlook?可能会问，时间紧就不问了， 逆置一个顺序表，链表 顺序表逆置:由于顺序表是连续存储的,循环表厂的一半，交换第一个和最后一个 元素。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 这种互相矛盾的关系也就是环路。有向无环
    图两个顶点不存在环路，必然满足偏序关系。 如果任意两个课程之间只有先后 关系，并且没有换，那就是全序关系。原来的偏序变成了全序。排序算法 1 2 3 4，大小关系确定，唯一的，则这个序列满足全序关系。表现在拓扑排序中就是 每个顶点间都具有全序关系，则拓扑排序结果唯一。若是偏序的关系，那就不唯 一了。 有向无环图在实际生活中的应用例子？ 日常导航嘛。区块链领域。 什么是哈希表？如何构建哈希表？在构建哈希表过程中，会遇到什么问题， 如何解决？ 答：哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直 接进行访问的数据结构，他建立了关键字和存储地址之间的一种直接映射关系。 怎么构建哈希表： 在记录的存储位置和它的关键字之间建立一个确定的对应关系 f 即哈希函 数。使每个关键字和表中唯一的存储位置相对应，根据这个思想建立的表为哈希 表 哈希表的做法其实很简单，首先要构造一个哈希函数，哈希函数的构造有直 接定址法，除留余数法，平方取中法等等。我们那除留余数法做例子在，这个比 较简单，也比较常用。关键字对一个不大于散列表长度的一个素数取余。 取余结果就当作关键字的地址，关键字可以存放在数组里，（也可以存放在 二叉树）构造这个散列表的过程中会遇到几个关键字映射到一个地址上面，也就 产生了冲突。原因在于散列函数选取不当。 处理冲突有 开放定址法：线性探测 查看下一个单元， 链地址法：把所有同义词存放在一个链表里。不过对链表查找效率会变低， 我们可以在链表上构建一平衡二叉树。 Hashmap 是什么： 稀疏矩阵？ 答：如果在矩阵中，多数的元素为 0，通常认为非零元素比上矩阵所有元素 的值小于等于 0.05 时，则称此矩阵为稀疏矩阵（sparse matrix）。 AOE 网的始点和终点是什么？正常的 AOE 网只有一个始点和终点吗？ 答：关键路径（临界路径）：在 AOE 网络中从源点到汇点（结束顶点）的最 大路长度的路径。关键路径可以有多条
    起始点：入度为 0 的点 1 个 终点：仅有一个也叫做汇点 出度为 0 关键路径上的活动为关键活动，带权有向图中若以顶点表示事件，有向边表 示活动，边上的权值表示该活动持续的时间 怎么能够判断判断一个图是连通还是非连通的？ 答：对于无向图来说，如果无向图联通的，那么从任意一个点出发，仅需要 一次遍历就能访问所有的点。 如果是非联通的，则从任意一个顶点出发，一次遍历 只能访问此顶点所在联通分量的所有顶点，而剩余的节点无法通过这次遍历访问。 对于有向图来说，若从初始点到图中的每个顶点都有路径，那么一次遍历就 可以访问所有的点，否则 可以借助深度优先遍历，如果能遍历所有的点，那他就是联通的 有向图和无向图的联系,试各举一例说明？ 答：无向图可以看作每条边都有两个方向的有向图，写成邻接矩阵的形式的 话区别就很清楚；无向图的邻接矩阵一定是对称阵,而有向图则未必 实际应用的区别是有向图可以描述非对称的关系,但无向图不能.比如你认 识奥巴马,但是他不认识你,用图来表示人物关系时就将你和奥巴马之间连一条 线,并且指向他.可以用来解决加快工程进度的问题。 无向图和有向图都可以用来寻找最优路径。有向图解决最低路径成本问题。 无向图能解决的问题都能用有向图表示,但是无向图在对称的问题上往往更 容易,因为用有向图去表示无向图时需要用两倍的边数。 堆排序的思想是什么? 答：n 个关键字序列 Kl，K2，…，Kn 称为堆，当且仅当该序列满足如下性 质(简称堆性质)： (1) ki≤K2i 且 ki≤K2i+1 或(2)Ki≥K2i 且 ki≥K2i+1(1≤i≤FLOOR(n/2)) 若 将此序列所存储的向量 R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是 满 足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于) 其左右孩子(若 存在)结点的关键字。 知道一棵树的先序和后序能不能确定它?要证明. 答：不能，必须知道中序。这是因为同样的前序遍历和后序遍历序列，可以 对应不同的二叉树。 完全二叉树的性质： 度数为 1 的节点只有 1 个或者 1 个没有。
    叶子节点只可能在最大两层出现，而且对于最大层次中的叶子节点，依次排 列在该层最左边的位置。 若有 N 个元素，则：N 为奇数，每个分支节点都有左右子女； N 为偶数，则 n/2 的节点只有做子女，没有有子女。 如何判断完全二叉树：采用层次遍历，根据完全二叉树的性质，如果遍历遇 到了一个空节点，那么在这一层中该节点的后面就不应该再有空节点。如果有， 就不是。 平衡二叉树 树的任一节点的左子树和右子树的深度之差（平衡因子）不超过 1.平衡二 叉树的节点平衡因子只能是-1,0,1 他的平均查找长度为 O(logN)。 （赫夫曼）哈夫曼树？ 答：给定 n 个权值作为 n 的叶子结点，构造一棵二叉树，若带权路径长度达 到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫 曼树是带权路径长度最短的树，权值较大的结点离根较近。 带权路径长度：从树的根节点出发到任意节点的路径长度（经过的边数）与 该节点上权值的乘积 叫做该节点的带权路径长度。 树的带权路径长度：树中所有叶子节点的带权路径长度之和叫做该树的带权 路径长度 一般用于数据压缩处理，对于频度高的数据字符赋短编码 ，频率较低的赋 以长编码 线索二叉树 二叉树线索化的实质就是对非线性结构的线性化。为的是加快查找节点前驱 和后继的速度。
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料