logo资料库

科大软院面试问题整理.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：1.46M 资料格式：doc 举报 版权申诉
第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
资料共8页，全文预览结束
    一 数据结构 1 如何实现矩阵乘法 3 个二维数组+3 层 for 循环。 2 如何不借助辅助变量，交换两数的值。 加减法：a=a+b; b=a-b; a=a-b; 3 单链表就地逆置 将头结点摘下，然后从第一个结点开始，头插法建立单链表，直到最后一个结点为止。 4 单链表利用什么实现？ 指向结构体的结构体指针实现，每个结点分为数据域和指针域，除了最后一个结点，每个结点指针域 都指向下一个结点的地址，最后一个结点指针指向 NULL. 5 实现一个队列的方法？ （1）链式存储：改造一下单链表，加尾指针作为队列尾部插入结点相当于入队，头结点删除结点相当于 出队。 （2）顺序存储：利用循环队列。 留一个空位是为了判断队空队满，循环可以解决假溢出问题。 6 二叉排序树（二叉搜索树） 加了限制的二叉树，任意结点的左子树的所有结点都小于它，右子树的所有结点都大于它。二叉排序 树查找时间依赖于形状。 7 平衡二叉树？ 加了限制的二叉排序树，每个结点的左子树和右子树高度差不超过 1，使查找效率提高。 8 哈夫曼树？ 带权路径最小的树就是哈夫曼树，构造过程：将结点按权值排序，选最小的两个作为一个新节点。重 复这个过程。 9 折半查找算法 两个条件：（1）必须顺序存储（2）必须有序 利用中间位置将表分成前后两个子表。 二 操作系统 三 计算机网络 1 ipv4 的替代方案 Ipv6， 特点：（1）更大的地址空间，32 位增大到 128 位；（2）支持即插即用；（3）增加了安全性，身份 验证和保密功能是 ipv6 的关键特征。 Ipv4 向 ipv6 的过渡的两种策略：（1）双协议栈：使一部分主机或路由器装有两个协议栈，一个 ipv4 一个 ipv6；（2）隧道技术：将整个 ipv6 数据报封装到 ipv4 数据报的数据部分。 2 路由协议有哪些？ （1）路由信息协议 RIP，基于 UDP （2）开放最短路径优先协议 OSPF，基于 IP
    （3）边界网关协议 BGP，基于 TCP RIP 和 OSPF 的主要区别： RIP、OSPF、BGP 三者比较： 3 传输等待协议（流量控制、可靠传输与滑动窗口机制） 数据链路层的可靠传输使用确认和超时重传两种机制完成。 （1）单帧滑动窗口与停止等待协议，发送窗口=接收窗口=1 （2）多帧滑动窗口与后退 N 帧协议 GBN，1<=发送窗口<=2^n-1，接收窗口=1 （3）多帧滑动窗口与选择重传协议 SR，接收窗口<=发送窗口<=2^(n-1) 4 网络服务质量包括哪些？ *可用性:用户与网络连接的可靠性。 *传输延迟:两个参照点之间发送和接收数据包的时间间隔。 *可变延迟:也称为延迟抖动，指接收的一-组数据流中数据包之间的时间差异。 *吞吐量:网络中发送数据包的速率，可用平均速率或峰值速率表示。 *丢包率:在网络中传输数据包时丢弃数据包的最高比率。数据包丢失一般是由网络拥塞引起的。 5 网络信源、信道与信宿 信源：产生和发送数据的源头。 信宿：是接收数据的终点。 信道：是信号的传输媒介，一个信道可以看做一条线路的逻辑部件，一般用来表示向某一方向传送信 息的介质。 6 同步通信和异步通信
    7 数据链路停发机制（流量控制） 流量控制的基本方式是由接收方控制发送方发送数据是速率，常见的方式有两种：停止-等待协议和滑 动窗口协议。 8 OSI 模型中流量控制在第几层？ 在数据链路层、网络层和传输层。 9 电路交换、报文交换和分组交换的优缺点 电路交换： 优点：（1）通信时延小，（2）有序传输，（3）没有冲突，（4）适用范围广，（5）实时性强，（6） 控制简单。 缺点：（1）建立连接时间长，（2）线路独占，使用效率低；（3）灵活性差；（4）难以规 格化。 报文交换： 优点：（1）无需建立连接；（2）动态分配线路；（3）提高线路可靠性；（4）提高线路利用率；（5） 提供目标服务。 缺点：（1）会引起转发时延；（2）报文交换对报文的大小没有限制，这需要较大的缓冲空间。 分组交换： 优点：（1）无需建立时延；（2）线路利用率高；（3）简化了存储管理；（4）加速传输；（5）减 少了出错几率和重发数据量。 缺点：（1）存在传输时延；（2）需要传输额外的信息量；（3）当分组交换采用数据报服务时，可 能出现乱序、丢失或重复分组，分组到达目的结点时，要对分组按编号进行乱序等工作，增加了麻烦。若 采用虚电路，虽无失序问题，但有呼叫建立、数据建立和虚电路释放三个过程。 10 IEEE802.3 协议 通常指以太网。一种网络协议。描述物理层和数据链路层的 MAC 子层的实现方法。 以太网采用两项措施简化通信 （1）采用无连接的工作方式；（2）不对发送的数据帧编号，也不要求接收方发送确认，即以太网尽 最大努力交付数据，提供的是不可靠服务，对差错的纠正则由高层实现。
    11 TCP/IP 分层 ISO/OSI 分层 12 异步通信的信源和信宿没有时钟同步信号，怎么解决这个问题？ 采用曼彻斯特或者差分曼彻斯特。曼彻斯特编码将一个码元分成两个相等的间隔，前低后高表示 1， 前高后低表示 0；差分曼特斯特编码时前后相同为 1，相反为 0. 13 网络安全性有哪些方面，网络服务质量包括哪些方面？什么是 QoS？ QoS：（QualityofService）服务质量是一种安全控制机制，它提供了针对不同用户或者不同数据流采用 相应不同的优先级，或者是根据应用程序的要求，保证数据流的性能达到一定的水准。在正常情况下，如 果网络只用于特定的无时间限制的应用系统，并不需要 QoS，比如 Web 应用，但是对关键应用和多媒体应 用就十分必要。当网络过载或拥塞时，QoS 能确保重要业务量不受延迟或丢弃，同时保证网络的高效运行。 网络安全：是指网络系统的硬件、软件及其系统中的数据受到保护，不因偶然的或者恶意的原因而遭 受到破坏、更改、泄露，系统连续可靠正常地运行，网络服务不中断。网络安全从其本质上来讲就是网络 上的信息安全。从广义来说，凡是涉及到网络上信息的保密性、完整性、可用性、真实性和可控性的相关 技术和理论都是网络安全的研究领域。网络安全是一门涉及计算机科学、网络技术、通信技术、密码技术、 信息安全技术、应用数学、数论、信息论等多种学科的综合性学科。 14 OSI 参考模型和 TCP/IP 模型有几层，简述各层原理及作用，TCP/IP 有哪些协议？ OSI 物理层，透明的传输比特流。 数据链路层，两个相邻节点间的链路上，透明地传送帧中的数据，数据传送时，数据链路层将网络层 交下来的 IP 数据包组成帧，每个帧包括数据和必要控制信息，以使得接收端能够知道从哪开始和结束，进 行硬件地址寻址进行硬件地址寻址，还使接收端能检测到所收到的帧中有无差错，有就丢失。 网络层，为分组交换网上的不同主机提供通信服务，把运输层产生的报文段或用户数据报封装成分组， 关键问题是逻辑地址寻址，实现不同网络之间的路径选择。
    运输层，运输层负责端到端的通信，对一个主机同时运行的多个进程提供服务，这是复用，运输层把 收到的信息分别交付给上面应用层相应进程，为高层提供可靠透明有效的数据传输服务，实现进程到进程 的传输管理，差错控制，流量控制等。 会话层（Session Layer）：建立、管理、终止会话。（在五层模型里面已经合并到了应用层） 表示层（Presentation Layer）：数据的表示、安全、压缩。（在五层模型里面已经合并到了应用层） 应用层 (Application)： 网络服务与最终用户的一个接口。协议有：HTTP FTP TFTP SMTP SNMP DNS TCP/IP 协议不是 TCP 和 IP 这两个协议的合称，而是指因特网整个 TCP/IP 协议族。TFTP，HTTP，SNMP， FTP，SMTP，DNS，Telnet ，TCP，UDPIP，ICMP，OSPF，EIGRP，IGMP,RIP，PPP，MTU，ARP，RARP 15 滑动窗口 滑动窗口，在任意时刻发送方都维持一组连续连续的允许发送的帧的序号，称为发送窗口，同时接收 方页维持一组连续允许接受的帧序号，称为接受窗口，发送窗口用来对发送方进行流量控制，发送窗口大 小代表还没有收到对方确认情况下，发送方最多还可以发送多少数据帧，接受窗口为了控制可以接收哪些 数据帧而不可以接收哪些帧。当接收方收到的数据帧是接受窗口内的序号才收。不是丢弃。发送端每收到 一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口都没确认就停止发送，直到接收方发送来的 确认帧使窗口移动才可以发送。数据链路层滑动窗口大小是固定的。 16 简述电路交换、报文交换、分组交换，比较优缺点 电路交换：源节点和目的节点之间建立一专用通路，用于传送数据，包括建立连接，传输数据，断开 连接，优点：延迟小。缺点：利用率低 报文交换：将数据加上源地址，目的地址等信息，封装成报文，存储转发每个报文可以单独选择到达 目的节点的路径，有点利用率较好，缺点是增加了资源开销，和缓冲延迟，缓冲难以管理，因为报文大小 不确定。 分组转发：将数据分成较短的固定长度的数据块，每个块上加上目的地址，源地址等辅助信息组成分 组，以存储转发的方式传输，除具备报文的优点，还有缓冲易于管理，平均延迟更小。 17 什么是流量控制？在那几层有流量控制？ 数据链路层：流量控制设计对链路上的帧的发送速率的控制，以使接收方有足够的缓冲空间来接受每 一个帧。由接收方控制发送方的速率，常见方式有停止等待协议，发送方每发送一帧，都要等待接受对方 应答，之后才能发送下一帧，接收方每接受一帧都要反馈一个应答信号，如果没有应答一直等待，效率很 低。 滑动窗口，在任意时刻发送方都维持一组连续连续的允许发送的帧的序号，称为发送窗口，同时接收 方页维持一组连续允许接受的帧序号，称为接受窗口，发送窗口用来对发送方进行流量控制，发送窗口大 小代表还没有收到对方确认情况下，发送方最多还可以发送多少数据帧，接受窗口为了控制可以接收哪些 数据帧而不可以接收哪些帧。当接收方收到的数据帧是接受窗口内的序号才收。不是丢弃。发送端每收到 一个确认帧，发送窗口就向前滑动一个帧的位置，当发送窗口都没确认就停止发送，直到接收方发送来的 确认帧使窗口移动才可以发送。数据链路层滑动窗口大小是固定的。 自动重传请求 ARQ 有三种： 单帧滑动窗口（停止等待协议），可保证有序。后两种后退 N 帧 ARQ 和选择重传 ARQ 是滑动窗口与 请求重发的结合。由于窗口尺寸足够大，帧可以再线路上连续流动，又称连续 ARQ。 后退 N 帧 ARQ：接收窗口等于 1。允许发送方可以连续发送信息帧，但是，一旦某帧发生错误，必须重新 发送该帧及其后的 n 帧。这种方式提高了信道的利用率，但允许已发送有待于确认的帧越多，可能要退回 来重发的帧也越多。 选择重传 ARQ：当发送方接收到接收方的状态报告指示报文出错，发送方只发送传送发生错误的报文。 数据链路层可靠传输只有超时重传。传输层 TCP 连接中传送的数据流中每一个字节都编上一个序号，确认 号是期望收到对方的下一个报文段的数据的第一个字节的序号。超时重传和冗余确认（ACK），可以缩短 时间发送方收到同一个报文段的三个冗余确认，就重传，也成为快重传。 传输层 TCP 流量控制：接收方根据自己接受缓存的大小，动态调整发送方的发送窗口大小，这就是接 受窗口 rwnd，来限制发送方向网络注入报文的速率，同时发送方根据其对当前网络拥塞程序的估计而确定
    的窗口值，成为拥塞窗口 cwnd。rwnd 是接收方允许连续接收的最大能力，单位字节，发送法根据最新收 到的 rwnd 限制自己发送窗口大小。实际取 rwnd 和 cwnd 最小值。 传输层与数据链路层的流量控制区别在于，传输层定义了端到端用户之间的流量控制，数据链路层定义了 两个中间的相邻节点的流量控制。 18 计算机网络使用的通道共享技术有哪些？简述频分复用、时分复用、波分复用、码分复用。时分复用的 时隙怎么确定？频分复用如何避免各路信号间干扰? 介质访问控制：将使用介质的每个设备与来自同一信道上的其他设备通信隔离开，使资源合理分配给 网络上的设备，采用多路复用技术可以把多个输入通道的信息整合到一个复用通道，在接受端把收到的信 息分离出来传送到对应的输出通道。 频分复用 FDM：就是将用于传输信道的总带宽划分成若干个子频带(或称子信道)，每一个子信道传输 1 路信号。频分复用要求总频率宽度大于各个子信道频率之和，同时为了保证各子信道中所传输的信号互 不干扰，应在各子信道之间设立隔离带，这样就保证了各路信号互不干扰(条件之一)。频分复用技术的特 点是所有子信道传输的信号以并行的方式工作，每一路信号传输时可不考虑传输时延，因而频分复用技术 取得了非常广泛的应用。 时分复用 TDM：是采用同一物理连接的不同时段来传输不同的信号，也能达到多路传输的目的。同步 (Synchronous)时分多路复用 TDM,它的时间片是预先分配好的,而且是固定不变的,因此各种信号源的传输定 时是同步的。但是计算机数据传输的突发性，利用率不高。STDM 又称统计时分复用，异步时分多路复用， 当终端数据要传送时才会分配时间片，因此可以提高线路的利用率。 波分复用 WDM：就是光的频分复用，在一根光纤中传输多种不同波长的光信号，由于波长不同，所以各 路光信号互不干扰，最后在用波长分解复用器将各路波长分解出来。 码分复用 CDM：是靠不用的编码来区分各路原始信号的一种复用方式，是用一组包含互相正交的码字 的码组携带多路信号。每个发送者有自己不同的密码，接受者在接到不同信号，通过密码过滤掉自己无法 解码的信号，留下和自己密码对应的信号。码分多址，每个用户在同一时间使用同样的频带进行通信。 四 计算机组成原理及硬件相关 1 二极管和三极管的区别 二极管具有单向导通的特性，一般用在整流、稳压、续流等领域；而三极管是能起放大、振荡或开关等作 用的半导体电子器件。 2 芯片组，作用？ 芯片组是构成主板电路的核心，一定意义上讲，芯片组决定了主板的级别和档次。 芯片组分为北桥和南桥芯片，北桥用于 CPU，内存和显卡。南桥主要用于 IO。 五 数据库 1 数据模型包括：数据结构、数据操作和数据约束。 2 三层结构，两级映射 三层结构式外模式、模式、内模式。外模式是用户能够看见和使用的局部数据的逻辑结构和特征描述； 模式是数据库中全体数据的逻辑结构和特征的描述，是数据库系统模式结构的中间层；内模式是数据物理 结构和存储方式的描述。 外模式模式映像：模式发生改变，外模式模式映像发生改变，可使外模式不变，保证数据库的逻辑独 立性。 模式内模式映像：数据库的存储结构发生改变，模式内模式映像发生改变，可使模式不变，保证数据 和程序的物理独立性。 三级模式使用户能逻辑地抽象地处理数据而不关心数据在计算机内具体表示方式与存储方式，两级映 射保证了数据库系统有较高的逻辑独立性和物理独立性。
    3 数据库的三种类型 层次模型：树状结构 网状模型： 关系模型：二维表。 4 关系和关系模式 关系实质上就是二维表，关系模式就是对关系的描述。关系是动态的，关系模式是静态的。通俗来讲， 关系是一张二维表，关系模式就是表头。 5 事务的四大属性 ACID A 原子性 C 一致性 I 隔离性 D 持续性 6 数据库中的锁 保证事务的四个特性，进行加锁，加锁之后其他事务不能更新此类数据对象，不会产生数据不一致性。 写锁：别的事务不能读也不能写。读锁：别的事务能读不能写。 六 软件工程 七 编译原理 1 编译器和解释器？ 解释器就是一条一条的解释执行源语言，比如 php, js 就是典型的解释性语言。 编译器是把源代码整个编译成目标代码，执行时不再需要编译器，直接在支持目标代码的平台上运行，这 样执行效率比解释执行快很多。比如 C 语言代码被编译成二进制代码（exe 程序），在 windows 平台上执 行。 解释器：词法分析 -> 语法分析 -> 语义分析 -> 执行。 编译器：词法分析 -> 语法分析 -> 语义分析 -> 中间代码生成（编译器前端）- -> 中间代码 - -> 代码生成 -> 目标代码生成。（编译器后端） 2 翻译程序？分类？ 翻译程序：将某一种程序设计语言的程序（源程序）翻译成等价的另一种语言的程序（目标程序）的 程序称为翻译程序。 翻译程序从源语言类型或实现机制的角度可以分为汇编程序、编译程序和解释程序。 汇编程序：若源程序用汇编程序编写，经翻译生成机器语言表示的目标程序，该翻译程序称为汇编程 序。 编译程序：若源程序用高级语言编写，经翻译加工生成某个机器的汇编语言程序或者二进制代码程序， 该翻译程序称为编译程序。 解释程序：解释程序的工作模式是逐条语句分析执行，一旦第一条分析结束，源程序便开始运行并且 声称结果。 3 高级语言源程序的执行过程 需要编译程序支持的执行过程分别为编译阶段和运行阶段。编译阶段对整个源程序进行分析，翻译成 等价的目标程序；运行阶段则由所生成的目标程序连同运行系统（数据空间分配子程序、标准函数程序等） 接收程序的初始数据作为输入，运行后输出计算结果。
    4 与编译器有关的程序 编辑器 预处理器：可以删除注释、空白符、执行宏等，一个源程序甚至可能被分割成多个模块，分别存放于 独立的文件中，用预处理器可以把源程序聚合在一起。 编译器：将经过预处理的源程序转变为汇编语言程序（因为汇编语言程序比较容易输出和调试） 汇编器：产生可重定位的机器代码。 连接程序：将分别在不同的目标文件中编译或汇编的代码收集到一个可直接执行的文件中。 装入程序：可以处理所有与指定的基地址或者起始地址有关的可重定位的机器代码。 5 编译过程概述 词法分析、语法分析、语义分析与中间代码生成、代码优化及目标代码生成 5 个阶段。 词法分析：对输入符号串形式的源程序进行最初的加工处理。它依次扫描读入的源程序中每个字符， 识别出源程序中有独立意义的源程序单词，用某种特定的数据结构对它的属性予以表示和标注。词法分析 实际上是一种线性分析，词法分析阶段工作依据的是源语言的词法规则。 语法分析：在词法分析的基础上，依据源语言的语法规则，对词法分析的结果进行语法检查，并识别 出单词符号串所对应的语法范畴，类似于自然语言中对短语、句子的识别和分析。通常将语法分析的结果 表示为抽象的分析树和语法树。 语法分析和中间代码生成：依据源语言限定的语义规则对语法分析所识别的语法范畴进行语义检查并 分析其含义，初步翻译成与其等价的中间代码，语义分析是整个编译程序完成的最具有实质性的翻译任务。 代码优化：为了改进目标代码的质量而在编译过程中进行的工作。 目标代码生成：为编译程序的最后阶段，其任务是根据中间代码及编译过程中产生的各种表格的有关 信息，最终生成所期望的目标代码程序，一般为特定机器的机器语言代码或者汇编语言代码。 6 前端和后端 按照编译器是依赖于对源程序的操作还是依赖于对目标语言的操作，将其分为前端和后端两部分。这 与将编译器分为分析和综合两部分是一致的。前端重在语言结构的分析，完成词法分析，语法分析和语义 分析，一般与目标机无关，因此适用于自动生成。后端进行综合，实现语言意义的处理和优化，完成目标 代码生成，一般与目标机相关。如果在理想情况下将编译器严格分成这两部分，则中间语言是前端和后端 的分界和接口。
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料