logo资料库

杭电计算机复试专业课面试必背.docx

发布时间：2022-06-22 发布人：admin 分类：说明书 资料大小：1.33M 资料格式：docx 举报 版权申诉
第1页 / 共25页
第2页 / 共25页
第3页 / 共25页
第4页 / 共25页
第5页 / 共25页
第6页 / 共25页
第7页 / 共25页
第8页 / 共25页
资料共25页，剩余部分请下载后查看
    1.邻接矩阵表示法 
    2.邻接表表示法
    3.十字链表（有向图的优化）
    4.邻接多重表
    IGRP协议（内部网关路由协议）
    EIGRP（增强内部网关路由协议）
    IS-IS协议（中间系统到中间系统路由协议）
    优点
    缺点
    数据结构 1. 排序算法中哪些最坏和平均的时间复杂度是一样的? 冒泡排序，简单选择排序，直接插入排序，归并排序，堆排序，基数排序。 2. 数据结构中排序最优和最差相同的排序算法？ 简单选择排序，归并排序，堆排序，基数排序。 3. 最小生成树的算法有哪些，举个例子说明； Prim 算法: Prim 算法基于一种贪心的思想，通过局部最优策略，每次将一条边加入所构建 的生成树中，加完 n-1 条边后，保证最后所得的生成树是整体最优的，即最小生 成树。 Kruskal 算法： Kruskal 算法同样是基于贪心策略，但是它和 Prim 算法不同的是，在算法过程 中它并不维护一个连通的分量，而是将多个连通分量合并到一起得到一颗生成树。 Kruskal 算法具体实现：此算法可以称为“加边法”，初始最小生成树边数为 0， 每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合 里。 (1) 把图中的所有边按代价从小到大排序；
    (2)把图中的 n 个顶点看成独立的 n 棵树组成的森林； (3)按权值从小到大选择边，所选的边连接的两个顶点 ui,vi,应属于两颗 不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。 (4) 重复(3),直到所有顶点都在一颗树内或者有 n-1 条边为止。 4. 最短路径的算法，弗洛伊德和迪杰斯特拉有什么不同，用于什么情况。 迪杰斯特拉(dijkstra)算法: Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算一个节 点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到 扩展到终点为止。Dijkstra 算法能得出最短路径的最优解，但由于它遍历计算 的节点很多，所以效率低。 弗洛伊德（Floyd）算法： 弗洛伊德（Floyd）算法是一个经典的动态规划算法。用通俗的语言来描述 的话，首先我们的目标是寻找从点 i 到点 j 的最短路径 算法描述：a.从任意一条单边路径开始。所有两点之间的距离是边的权，如 果两点之间没有边相连，则权为无穷大。 b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。 区别： 一个是单源最短路，一个是每对顶点的最短路。 迪杰斯特拉属于贪心算法，弗洛伊德属于动态规划 迪杰斯特拉不能算有负权的，弗洛伊德可以算有负权的。 时间复杂度不同，O(n2),O(n3) 5. 拓扑排序中用了哪些结构？ 有向无环图？ 拓扑排序的实现步骤： 在有向图中选一个没有前驱的(入度为零)顶点并且输出 从图中删除该顶点和所有出边（即以它为头的弧） 重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为 止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图 是否有环。 6. 简述一下二叉排序树； 二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree）， 亦称二叉搜索树。它或者是一棵空树； 或者是具有以下性质的二叉树： 1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； 3. 它的左右子树也分别为二叉排序树。 7. 简述一下线索二叉树
    对于 n 个结点的二叉树，在二叉链存储结构中有 n+1 个空链域，利用这些 空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称 为线索，加上线索的二叉树称为线索二叉树。 8. 二叉树与普通度为二的树的区别 度为 2 的树要求每个节点最多只能有两棵子树，并且至少有一个节点有 两棵子树。 二叉树的要求是度不超过 2，就是说度也可以是 1 或者 0。二叉树还有 一个重要特点，区分左右子树；普通的树不分左右子树。 9. 数据结构的 4 个结构，各有什么特点 集合结构：结构中的数据元素之间除了同属于一种类型外，无其他关系。 线性结构：结构中的数据元素之间存在一对一的关系。 树形结构：结构中的数据元素之间存在一对多的关系。 图状结构或是网状结构：结构中的数据元素之间存在多对多的关系。 10. 线性表存储结构有哪些，优点缺点？线性存储和链式存储的优缺点比较？ 线性表具有两种存储结构即顺序存储结构和链接存储结构。 顺序存储结构是一种物理结构，是按存储单元的顺序依次连续存放逻辑结构 中所有结点形成的结构。 逻辑上彼此相邻的结点，在存储器上的物理位置也 彼此比邻。 链式存储结构的结点是在元素数据存储的同时附加存储一个指针数据。 指针 的作用是指出该结点逻辑上的后继结点的存储位置。 优缺点： 线性表的顺序存储结构，需要开辟一个定长的空间，不可扩充容量，可以直 接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的 大量移动，因而降低效率。 而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间 关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作 较简单。 11. 散列表的建立方法？散列表会不会发生冲突，有哪些冲突解决的办法？ 哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直 接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置 来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的 数组叫做散列表。 哈希函数的构造方法： 1. 数字分析法 2. 平方取中法
    3. 去留余数法 4. 伪随机数法 5. 分段叠加法 处理冲突的方法： 1. 开放地址法 2. 再哈希法 3. 链地址法 4. 建立公共溢出区 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是 和基本表发生冲突的元素，一律填入溢出表 12. hash 表的特点，hash 表适合存储什么类型的数据? 散列表有两种用法：一种是 Key 的值与 Value 的值一样，一般我们称这种 情况的结构为 Set（集合）；而如果 Key 和 Value 所对应的内容不一样时，那 么我们称这种情况为 Map，也就是人们俗称的键值对集合。 根据散列表的存储结构，我们可以得出散列表的以下特点。 1) 访问速度很快 由于散列表有散列函数，可以将指定的 Key 都映射到一个地址上，所以在 访问一个 Key（键）对应的 Value（值）时，根本不需要一个一个地进行查找， 可以直接跳到那个地址。所以我们在对散列表进行添加、删除、修改、查找等任 何操作时，速度都很快。 2) 需要额外的空间 首先，散列表实际上是存不满的，如果一个散列表刚好能够存满，那么肯定 是个巧合。而且当散列表中元素的使用率越来越高时，性能会下降，所以一般会 选择扩容来解决这个问题。另外，如果有冲突的话，则也是需要额外的空间去存 储的，比如链地址法，不但需要额外的空间，甚至需要使用其他数据结构。 这个特点有个很常用的词可以表达，叫作“空间换时间”，在大多数时候，对于 算法的实现，为了能够有更好的性能，往往会考虑牺牲些空间，让算法能够更快 些。 3) 无序 散列表还有一个非常明显的特点，那就是无序。为了能够更快地访问元素， 散列表是根据散列函数直接找到存储地址的，这样我们的访问速度就能够更快， 但是对于有序访问却没有办法应对。 4) 可能会产生碰撞 没有完美的散列函数，无论如何总会产生冲突，这时就需要采用冲突解决方 案，这也使散列表更加复杂。通常在不同的高级语言的实现中，对于冲突的解决 方案不一定一样。 13. 图的存储 1. 邻接矩阵表示法 2. 邻接表表示法 3. 十字链表（有向图的优化）
    4. 邻接多重表 14. 图的深度和广度遍历是什么，工程上有什么实际应用？ 图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。 它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点 v 出发，首 先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图， 直至图中所有和 v 有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访 问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点 都被访问到为止。显然，深度优先搜索是一个递归的过程。 广度优先搜索算法(Breadth First Search)，又称为"宽度优先搜索"或"横向 优先搜索"，简称 BFS。 它的思想是：从图中某顶点 v 出发，在访问了 v 之后依次访问 v 的各个未曾 访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先 被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被 访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选 一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都 被访问到为止。 15. 如何在一个数组中找出两个数相加等于一个固定值的所有数对？ 1. 思路 1: 暴力穷举法：两层 for 循环 2. 思路 2：可以用 hash 表来存储数组中的元素，这样我们取得一个数后， 去判断 sum - val 在不在数组中，如果在数组中，则找到了一对二元组， 它们的和为 sum，该算法的缺点就是需要用到一个 hash 表，增加了空间 复杂度。 3. 思路 3：同样是基于查找，我们可以先将数组排序，然后依次取一个数 后，在数组中用二分查找，查找 sum -val 是否存在，如果存在，则找到 了一对二元组，它们的和为 sum，该方法与上面的方法相比，虽然不用 实现一个 hash 表，也没不需要过多的空间，但是时间多了很多。排序需 要 O(nLogn)，二分查找需要(Logn)，查找 n 次，所以时间复杂度为 O(nLogn)。 4. 思路 4：该方法基于第 2 种思路，但是进行了优化，在时间复杂度和空 间复杂度是一种折中，但是算法的简单直观、易于理解。首先将数组排 序，然后用两个指向数组的指针，一个从前往后扫描，一个从后往前扫 描，记为 first 和 last，如果 fist + last < sum 则将 fist 向前移动， 如果 fist + last > sum，则 last 向后移动。 16. 怎么确定单链表是一个环（数据结构）、 方法 1：穷举遍历 思路：首先从头节点开始，依次遍历单链表的每一个节 点。每遍历到一个新节点，就从头节点重新遍历新节点之前的所有节点，用新节 点 ID 和此节点之前所有节点 ID 依次作比较。如果发现新节点之前的所有节点当
    中存在相同节点 ID，则说明该节点被遍历过两次，链表有环；如果之前的所有 节点当中不存在相同的节点，就继续遍历下一个新节点，继续重复刚才的操作。 方法 2：哈希表缓存 首先创建一个以节点 ID 为键的 HashSet 集合，用来 存储曾经遍历过的节点。然后同样是从头节点开始，依次遍历单链表的每一个节 点。每遍历到一个新节点，就用新节点和 HashSet 集合当中存储的节点作比较， 如果发现 HashSet 当中存在相同节点 ID，则说明链表有环，如果 HashSet 当中 不存在相同的节点 ID，就把这个新节点 ID 存入 HashSet，之后进入下一节点， 继续重复刚才的操作。这个方法在流程上和方法一类似，本质的区别是使用了 HashSet 作为额外的缓存。 方法 3：快慢指针 首先创建两个指针 1 和 2（在 java 里就是两个对象引用）， 同时指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针 1 每次 向下移动一个节点，让指针 2 每次向下移动两个节点，然后比较两个指针指向的 节点是否相同。如果相同，则判断出链表有环，如果不同，则继续下一次循环。 此方法也可以用一个更生动的例子来形容：在一个环形跑道上，两个运动员在同 一地点起跑，一个运动员速度快，一个运动员速度慢。当两人跑了一段时间，速 度快的运动员必然会从速度慢的运动员身后再次追上并超过，原因很简单，因为 跑道是环形的。 17. 汉络塔 递归 if n!=0 then func(n-1, a, c, b) move a[n] to c func(n-1, b, a, c) endif ;预定值 ;将 n-1 个盘子由 a 移动到 b，以 c 为辅助柱子 ;将 a 上的最后一个盘子移动到 c ;将 n-1 个盘子由 b 移动到 c，以 a 为辅助柱子 ;完成 组成原理 1. 中断的过程是什么，断点的概念，什么是中断向量？ 中断全过程分为 5 个阶段： 中断请求、中断判优、中断响应、中断处理和中断返回 所谓断点就是程序被中断的地方 断点是人为设置的，意思就是让程序执行到此“停住”，不再往下执行，然后 主动权就交给调试者，进行调试。 中断标识码（中断类型号）：
    由硬件（通常是中断控制器）产生，以标识不同的中断源。 中断向量： 中断服务程序的入口地址。在某些计算机中，中断向量的位置存放一条跳转 到中断服务程序入口地址的跳转指令。 中断向量地址： 存储中断向量的存储单元地址 中断向量 是指早期的微机系统中将由硬件产生的中断标识码（中断源的识别 标志，可用来形成相应的中断服务程序的入口地址或存放中断服务程序的首 地址）。中断是指在计算机执行程序的过程中，当出现异常情况或者特殊请求 时，计算机停止现行的程序的运行，转而对这些异常处理或者特殊请求的处 理，处理结束后再返回到现行程序的中断处，继续执行原程序。 2. 中断有几种? 按照中断的功能来分,中断有以下五种类型： I/O 中断（输入输出中断）、外中断、硬件故障中断、程序性中断、访管中断 3. cpu 和外设之间数据交换有哪几种 1.程序查询方式。其特点是主机与 I/O 串行工作。CPU 启动 I/O 后，时刻查 询 I/O 是否准备好，若设备准备就绪，CPU 便转入处理 I/O 与主机间传送信 息的程序；若设备未做好准备，则 CPU 反复查询，“踏步”等待直到 I/O 准备 就绪为止。可见这种方式 CPU 效率很低。 2.程序中断方式。其特点是主机与 I/O 并行工作。CPU 启动 I/O 后，不必 时刻查询 I/O 是否准备好，而是继续执行程序。当 I/O 准备就绪时，向 CPU 发中断请求信号，CPU 在适当的时候响应 I/O 的中断请求，暂停现行程序为 I/O 服务。这种方式消除了“踏步”现象，提高了 CPU 的效率。 3.DMA 方式。其特点是主机与 I/O 并行工作，主机与 I/O 之间有一条直接 数据通路。CPU 启动 I/O 后，不必查询 I/O 是否准备好 4.通道方式。通道是一个具有特有功能的处理器，CPU 把部分权利下放给 通道，由它实现对外围设备的统一管理和外围设备与主存之间的数据交换， 大大提高了 CPU 的效率，但它是以花费更多的硬件为代价的。 5.I/O 处理机方式。它是通道方式的进一步发展，CPU 将 I/O 操作及外围 设备的管理权全部交给 I/O 处理机，其实质是多机系统，因而效率有更大提 高。 4. Cache 有几种地址映射方法，分别有什么优缺点？ 1.直接映射：主存的一块只能复制到 Cache 的一个特定行位置上去，主存的地址有高位 标记、字块地址、块内地址三个标记。这种映射关系实现简单，但是主存的块只能固定 地对应着某个缓存块，不够灵活，命中率低。较适合容量大的 Cache。 2.全相联映射：主存中的任一块都可以映像到 Cache 的任一块上，主存的地址有高位标 记、块内地址两个标记。机制灵活，命中率高，但所需要的逻辑电路较多，成本高。较 适合容量小的 Cache。 3.组相联映射：是前两中的折中。主存的地址有高位标记、组地址、块内地址三个标记。
    比直接映像灵活，命中率高，比全相联映射所需成本低。较适合容量小的 Cache。 5. cpu 有几种设计方式 CPU 设计的两种方法： 硬布线逻辑控制 微序列控制器（微程序控制） 计算机网络 1. 中断交换机，路由器和集线器三者的区别 路由器：（Router）是连接因特网中各局域网、广域网的设备。在路由器 中记录着路由表，它会根据信道的情况自动选择和设定路由，以最佳路径， 按前后顺序发送信号。发生在网络层。   交换机：（Switch）是一种用于电（光）信号转发的网络设备。它可以为 接入交换机的任意两个网络节点提供独享的电信号通路，把传输的信息送到 符合要求的相应路由上。发生在数据链路层。   集线器：（Hub）是指将多条以太网双绞线或光纤集合连接在同一段物理 介质下的设备。发生在物理层。 路由器和交换机的区别： 路由器 工作层次 网络层 转发依据 IP 地址 功能 宽带影响 共享宽带 连接不同的网络 连接局域网中的电脑 交换机 数据链路层 Mac 地址 独享宽带 集线器和交换机的区别： 交换机又称交换式集线器，它们俩很相似，都是基于 MAC 识别的，但是又 有本质上的区别。   工作层次 宽带影响 数据传输 传输模式 交换机 数据链路层 独享 有目的发送 全双工或半双工 集线器 物理层 共享 广播发送 半双工 2. 交换机能不能用在大型的网络中 能 3. IP 地址和 MAC 地址的区别 IP 地址 对于 IP 地址，即指使用 TCP/IP 协议指定给主机的 32 位地址。IP 地址由 用点分隔开的 4 个 8 八位组构成，如 192.168.0.1 就是一个 IP 地址，这 种写法叫点分十进制格式。IP 地址由网络地址和主机地址两部分组成，
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

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

    热门标签

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

    最新资料