牛客网刷题笔记(持续更新)

设哈希表长为14,哈希函数为h(key)=key%11。表中现有数据15、38、61和84,其余位置为空,如果用二次探测再散列处理冲突,则49的位置是

答案是9

处理的冲突的一种方式
开放定址法:Hi=(H(key)+di)MOD m,其中H(key)为哈希函数;m为哈希表长;di为增量序列,可有以下三种取法:

  1. di=1,2,3,……m-1,称为线性探测再散列;
  2. di=1\^2,-1\^2,2\^2,-2\^2…….k\^2,-k\^2,(k<=m/2),称为二次探测再散列
  3. di=伪随机数序列,称伪随机探测再散列

当前的数据15、38、61、84分别占了坑4、5、6、7,而49将占坑5,根据二次探测冲突处理法,尝试d=1、-1、4,而6,4均已经被占,所以选择d=4,即5+4=9,答案选择9

若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是

答案是11

根据节点数可得$n_2+n_1+n_0=n$,根据分支数b=n-1和$b=n_22+n_1$可得$n_22+n_1+1=n$,联立可得$n_0=n_2+1$

已知一棵有2011个结点的树,其叶结点个数为116,该树对应的二叉树中无右孩子的结点个数是

答案是1896

对应二叉树中无右孩子的的结点个数 = 有子节点的的结点数 + 1

基于哈希的索引和基于树的索引有什么区别

  1. hash索引仅满足“=”、“IN”和“<=>”查询,不能使用范围查询
  2. hash索引无法被用来进行数据的排序操作
  3. 对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用
  4. Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高

网络协议的3个要素:语法、语义、时序

语法 用来规定信息格式;数据及控制信息的格式、编码及信号电平等。

语义 用来说明通信双方应当怎么做;用于协调与差错处理的控制信息。

定时 (时序)定义了何时进行通信,先讲什么,后讲什么,讲话的速度等。比如是采用同步传输还是异步传输!

已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果:tail(head(tail(C))) =( )

答案:(A)

head():返回列表的第一个元素

tail():返回列表的删去第一个元素之后的剩余列表

tail(C) = ((b,A), B)

head(tail(C)) = (b, A)

tail(head(tail(C))) = (A)

head返回的是元素(去掉最外层括号),tail返回的是集合(保留括号)。

以下哪种http状态下,浏览器会产生两次http请求(A. 304 B.404 C.302 D.400)

答案:302

304:客户端申请的资源存在,但是条件不满足

302:临时重定向

404:NOT FOUND

400:存在语法错误

301:永久重定向

网络的基本分类有两种:一种是根据网络所使用的传输技术,另一种是

网络的基本分类有两种:一种是根据网络所使用的传输技术,另一种是覆盖范围与规模

https://www.nowcoder.com/questionTerminal/147508ce18e04ec788ccd618ce40d81b

来源:牛客网

1、根据网络所使用的传输介质不同,网络传输技术也会存在一定的差异,总的来说,可分为基于有线传输技术的网络和无线传输技术的网络,分别对应于有线信道和无线信道。一般我们接触到的有线介质有:RJ45的电口、光口等等;无线的传输有:长波,短波、微波等,我们的手机、Wi-Fi都属于无线传输。

2、根据网络的覆盖范围和规模,对网络的划分一般都是局域网、城域网、广域网。

3、对于网络的拓扑结构,我们一般都是在局域网中讨论,因为达到城域网级别的时候,拓扑结构非常复杂,很难再描述出来;所以拓扑结构一般是局域网的划分方式,比如星型、树型、环型、总线型等等。

SQL语言中,SELECT语句的执行结果是(元组集合)

z+=x>y?++x:++y的值是

赋值运算最后做

STL一级容器

vector,deque,list

二级容器:set,multiset,map,multimap

一级容器是指:容器元素本身是基本类型,非组合类型

三级模式间存在两种映像

模式与子模式间,模式与内模式间

外模式/模式映像:当模式改变时,由数据库管理员对各个外模式/模式的映像做相应的改变,可以使外模式保持不变。应用程序是依据数据的外模式编写的,从而应用程序不必修改,保证了数据与程序的逻辑独立性,简称数据逻辑独立性。 模式/内模式映像:当数据库的存储结构改变时,由数据库管理员对模式/内模式映像做相应的改变,可以使模式保持不变,从而应用程序也不必改变,保证了数据与程序的物理独立性,简称数据物理独立性。

ping www.mi.com,哪种协议没有被使用

TCP用不到

  • ping 首先将域名转换为ip地址,用到了DNS
  • 获取ip地址后,数据链路层是根据MAC地址传输的,所以要用ARP解析服务,获取MAC地址
  • ping功能是测试另一台主机是否可达,程序发送一份ICMP回显请求给目标主机,并等待返回ICMP回显应答,(ICMP主要是用于ip主机、路由器之间传递控制信息,控制信息是指网络通不通,主机是否可达)

设有关系模式EMP(职工号,姓名,年龄,技能)。假设职工号唯一,每个职工有多项技能,则EMP表的主码是

答案:职工号和技能

唯一的职工号无法唯一确定一个元组,必须和技能一起确定

TCP/IP建立连接过程

Tcp/Ip有3次握手:第一次握手:客户端向服务器端发送SYN包(syn=j),进入SYN_SEND状态,等待服务器确认。第二次握手:服务器收到SYN包,确认SYN,此时syn=j+1,同时发送一个SYN包(syn=k)即SYN+ACK包,此时服务器进入SYN_RECV状态;第三次握手:客户端收到SYN+ACK包,向服务器发送ACK确认包,此时客户端和服务器端均进入ESTABLISHED状态。

其中有一个半连接状态:服务器维护一个半连接队列,该队列卫每个客户端SYN包开设一个条目,标明服务器已经接到SYN包,并向客户端发出确认,这些条目表示的连接处于SYN_RECV状态,得到客户端的确认后进入ESTABLISHED状态。

私有IP地址

私有IP地址范围:
A: 10.0.0.0~10.255.255.255 即10.0.0.0/8
B:172.16.0.0~172.31.255.255即172.16.0.0/12
C:192.168.0.0~192.168.255.255 即192.168.0.0/16

办公室通过拨号的方式接入internet, web服务器IP地址为192.168.0.100, 现在需要把web服务器发布在internet中,需要的配置是

答案:路由器配置NAT和DDNS配置

ddns和dns相同点 是都保持ip和域名的kv关系,只不过前者ip变化很快,而dns更新记录又很慢,为了让用户及时正确地访问服务,那么就需要ddns,本题一个关键点是内网,内网地址一般是dhcp获取的,所以是动态的,需要借助ddns的帮助,叫做内网穿透动态域名解析服务

若X是二叉树中序线索树中一个有左孩子的结点,且X不为根,则X的前驱为

答案:X的左子树中最右节点

不一定是叶节点,节点可能还有一个左儿子叶节点

int a=21,b=11; printf(“%d\n”,–a+b,–b+a); 输出结果是

答案:30

printf()函数是从右往左计算表达式的

因特网基本服务功能是

  1. 远程登录服务Telnet
  2. 文件传送服务FTP
  3. 电子邮件服务E-mail
  4. 电子公告板系统BBS
  5. 万维网WWW

feof( fp)的函数返回值

如果文件结束返回非0值,否则返回0

FTP文件传输协议的端口

两个端口:20为数据端口,21为控制端口

在64位机器上用gcc编译以上代码,求sizeof(A),sizeof(B)分别是多少

gcc下的默认对齐数是4不是最大长度,也就是说,即使有double存在的情况下,对齐也是4个字节对齐。

例如B,double占8个字节,short本来占2个字节,但是下一个是int所以占4个字节,int占4个字节,char原本占1个字节,为了保证对齐数是4的倍数,所以最后的那个char也占了4个字节。这个是gcc编译器的规则。综上所述:8+4+4+4=20 所以要选择D选项。

“查询”设计视图窗口分这上下部分,下部分为

上部分为:“字段列表区”,用来显示所选择的所有字段。

下部分为:“设计网络“,由一些字段列和一些已命名的列组成。

printf(“%5s”, “abcdefg”)

%5s:右对齐5位,最少输出5位,不足时左侧补空格

%-5s:左对齐5位,最少输出5位,不足时右侧补空格

%.5s:最多输出5位

extern “C”是强迫c++编译器对函数名进行修饰的时候采用c命名约定

这样,在c++写的程序中就可以使用已经用c编译器编译好的obj或者lib了

printf(“%d\n”, y–);

输出的y原值,然后y–

由多个源文件组成的C程序,经过编辑、预处理、编译、链接等阶段会生成最终的可执行程序。下面哪个阶段可以发现被调用的函数未定义

答案:链接

1.编辑:也就是编写C/C++程序。

2.预处理:相当于根据预处理指令组装新的C/C++程序。经过预处理,会产生一个没有宏定义,没有条件编译指令,没有特殊符号的输出文件,这个文件的含义同原本的文件无异,只是内容上有所不同。

3.编译:将预处理完的文件进行一系列词法分析、语法分析、语义分析及优化后,产生相应的汇编代码文件。

4.链接:通过链接器将一个个目标文件(或许还会有库文件)链接在一起生成一个完整的可执行程序。 链接程序的主要工作就是将有关的目标文件彼此相连接,也就是将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来,使得所有的这些目标文件成为一个能够被操作系统装入执行的统一整体。在此过程中会发现被调用的函数未被定义。

数据段分为data段(初始化且不为0的static和global数据)和bss段(未初始化或已初始化为0的static和global数据)

fseek函数

fseek函数的第三个参数有3个值可选:0表示文件的开始处,1表示当前位置,2表示文件尾:位移量为负,表示将文件位置指针往前移动。

单精度浮点数和双精度浮点数的有效位数

  1. 一个浮点数由三部分组成:符号位S、指数部分E(阶码)以及尾数部分M。
  2. 单精度浮点数(float)总共用32位来表示浮点数,其中尾数用23位存储,加上小数点前有一位隐藏的1(IEEE754规约数表示法),2^(23+1) = 16777216。因为 10^7 < 16777216 < 10^8,所以说单精度浮点数的有效位数是7位。考虑到第7位可能的四舍五入问题,所以单精度最少有6位有效数字(最小尺寸)。
  3. 同样地:双精度浮点数(double)总共用64位来表示浮点数,其中尾数用52位存储,2^(52+1) = 9007199254740992,10^16 < 9007199254740992 < 10^17,所以双精度的有效位数是16位。同样四舍五入,最少15位。

printf(“a\bre\’hi\’y\\\bou\n”);输出结果是

答案:re’hi’you

注意\b是退格符,输出时将光标往左边回退一个位置

\\表示\符号

内联函数在编译时做参数类型检查

下列程序的输出是(19)

宏是纯文本替换,所以编译之后,运行时的实际代码为5*3+4=19

下列程序的输出是

答案:ffffffff,ff

%02x表示输出最少2位,不足补0

有符号数-1扩展到32位ffffffff

无符号数-1转为255,正数拓展补0,最少输出2位所以输出ff

要使模拟消息能够在数字信道上传输,需要使用(脉码调制)技术

脉码调制是对 模拟信号 进行处理、量化、编码后转换为数字信号的一种调制方式。

调制的目的是把要传输的 模拟信号数字信号 变换成适合信道传输的信号,解调为调制的反过程

哪些sql语句查询能较好的利用索引

答案:a、d

索引主要作用是提高查询的效率

但有一些情况索引将失效或效率不高(情况有很多,这里列举常见的几种, 假设在字段name上建立了索引):

1、使用了运算符!=,以及关键字not in, not exist等,认为产生的结果集很大,往往导致引擎不走索引而是走全盘扫描

2、对索引字段使用了函数,如where substr(name, 1, 3)=‘mark’, 导致索引无效

3、使用like和通配符,第一个字符是%将导致索引失效,如where name like “%ark“ (A正确)(注意是第一个字符是模糊)

order by与索引

首先利用where进行数据查询,这一步是免不了的,至于这一步有没有利用索引暂时不考虑,关键是在获取所有符合的记录后还需要进行排序,看看order by是如何利用索引的。

如果order by中的字段有建立索引,同时:

1、该字段没有出现在where中,则在排序的时候需要正常排序,默认order by是升序排序, 故索引没有对排序产生有利帮助 (B,C错误)

2、该字段同时同时出现在where中,则在获取记录后不进行排序,而是直接利用索引, 效率变高。(D正确)

group by 与 order by类似

局域网的协议结构一般不包括(网络层)

IEEE 802局域网参考模型只对应OSI参考模型的数据链路层与物理层,它将数据链路层分为逻辑链路控制子层和介质访问控制子层。所以局域网的协议结构一般不包括网络层。

QQ与TCP和UDP

wireshark抓包,QQ默认用的是UDP和腾讯自己的QICQ协议,但是QQ登录的时候选择TCP选项,也用到了TCP协议;微信主要是TCP协议

TCP支持的应用协议主要有:Telnet、FTP、SMTP等;UDP支持的应用层协议主要有:NFS(网络文件系统)、SNMP(简单网络管理协议)、DNS(主域名称系统)、TFTP(通用文件传输协议)等

c++模板类

  1. 可用来创建动态增长和减小的数据结构
  2. 它是类型无关的,因此具有很高的可复用性
  3. 它在编译时而不是运行时检查数据类型,保证了类型安全
  4. 它是平台无关的,可移植性
  5. 可用于基本数据类型

滑动窗口协议——发送窗口的最大值

有序接收:

发送窗口 + 接收窗口 $\leqslant 2^n$,而接收窗口的最小值是1,所以发送窗口的最大值为$2^{n}-1$

无序接收

无序接收,.发送的可能是乱序的,这就要求接收窗口有很大的尺寸来容纳乱序的序列.也就是说接收窗口至少要和发送窗口一样大.

因此为$2^n/2=2^{n-1}$

因为接收窗口若小于发送窗口,那么接收窗口就不知道收到的到底是下一条呢,还是重传的了

网络协议的3个要素:语法、语义和时序(同步)

(1) 语义.语义是解释控制信息每个部分的意义.它规定了需要发出何种控制信息,以及完成的动作与做出什么样的响应.

(2) 语法.语法是用户数据与控制信息的结构与格式,以及数据出现的顺序.

(3) 时序.时序是对事件发生顺序的详细说明.(也可称为“同步”)

人们形象地把这三个要素描述为:语义表示要做什么,语法表示要怎么做,时序表示做的顺序

路由器,交换机,集线器实现的最高功能层

集线器是一个多端口的中继器,工作在物理层。以太网交换机是一个多端口的网桥,工作在数据链路层。路由器是网络层设备,它实现了网络模型的下三层,即物理层、数据链路层和网络层。题中R1、Switch和Hub分别是路由器、交换机和集线器,实现的最高层功能分别是网络层(即3)、数据链路层(即2)和物理层(即1)

在c++中,为了让某个类只能通过new来创建(即如果直接创建对象,编译器将报错),应该

答案:将析构函数设为私有

编译器在为类对象分配栈空间时,会先检查类的析构函数的访问性,其实不光是析构函数,只要是非静态的函数,编译器都会进行检查。如果类的析构函数是私有的,则编译器不会在栈空间上为类对象分配内存。因此,将析构函数设为私有,类对象就无法建立在栈(静态)上了,只能在堆上(动态new)分配类对象

mysql导出数据的命令

mysqldump -u 用户名 -p 数据库名 > 导出的文件名

内存分配

程序占用三种类型的内存:静态内存、栈内存、堆内存

静态内存:

用来保存局部static对象、类static数据成员以及定义在任何函数之外的变量

栈内存:

用来保存定义在函数内的非static对象。
分配在静态内存或栈内存中的对象由编译器自动创建和销毁。对于栈对象,仅在其定义的程序块运行时才存在;static对象在使用之前分配,在程序结束时销毁。

堆内存:

在程序运行时分配。动态对象的生存周期由程序(用户)来控制

下面代码会输出

答案:4

&a和a都指向数组首元素的地址,不同的是a就是a+0,而&a+1相当于a[]数组类型的指针加1,此时指针加到数组的末尾,所以*ptr指向的是末尾

文件系统在内存中维护唯一的一张(文件分区表),其中保存了系统所有已打开文件的FCB

ARP协议数据单元封存在(以太帧)中发送

1.关于ARP概念

– ARP完成了ip地址到mac地址的映射。是因为在实际网络的链路上传送数据帧时,最终必须使用硬件地址。

– 其工作原理是:当主机a向主机b发送数据报时,要先在其arp高速缓存中查看有无主机b的ip地址。找到后,查出其对应的mac地址,并写入mac帧,通过局域网将此mac帧发往此mac地址

– 由于arp“看到了”ip地址,所以它工作在网络层。

2.那些可能你们不明白的操作

– ip地址是在网络层使用的地址,硬件地址是在数据链路层使用的地址。mac帧是由ip数据报分组封装成的,所以数据链路层看不见数据报分组中的ip地址。每次路由转发,ip分组在每个网络中都被路由器解封装和重新封装。这也是为什么不能使用mac地址跨网络通信。(每次重新封装后的mac地址都在不断的变化。)

– 对网络层而言,数据链路层的基本任务是将源机器中来自网络层的数据传输到目标机器的网络层。

– 在网络层由于路由器的隔离,ip网络无法通过广播方式依靠mac地址来完成跨网络的寻址,因此只使用ip地址来完成寻址。

– 在ip分组通过路由转发找到目标网络后,改为在目标网络LAN中通过数据链路层的mac地址以广播方式寻址。从而提高了路由选择效率。

在FTP中,控制信息和传输的文件数据可以使用同一个套接字

FTP是文件传输协议的缩写,包含了两个通道,一个叫控制通道,一个叫数据通道。 控制通道:控制通道是和FTP服务器进行沟通的通道,连接FTP,发送FTP指令都是通过控制通道来完成的。 数据通道:数据通道是和FTP服务器进行文件传输或者列表的通道。 大家可能会问,为什么FTP协议需要两个通道呢? 我举一个简单的例子,当我们用FTP客户端比如FTPRush下载FTP上的文件的时候,通常会加入好几个目录和文件到队列窗口,那么当下载开始的时候,队列里面的第二个文件怎么知道该被传输呢?这就是控制通道的用处了,当下载文件的时候,FTP客户端会 等待FTP服务器返回指令,这个指令就是通过控制通道来完成的,当数据通道的传输完成以后,FTP客户端就会接收到来自控制通道的指令,这样FTP客户端就可以知道这个文件已经传输完成或者失败,进行下一个传输了

FTP两个端口,20端口用于传输数据,21端口用于连接

A、B、C类地址

A类地址:1.0.0.0~126.255.255.254

B类地址:128.0.0.0~191.255.255.255

C类地址:192.0.0.0~223.255.255.255

数据库的三个模式

数据库系统由外模式、模式和内模式构成。

  • 外模式是数据库用户能够看见和使用的局部数据的逻辑结构和特征的描述,是数据库用户的数据视图;
  • 模式也称逻辑模式,是数据库中全体数据的逻辑结构和特征的描述,是所有用户的公共数据视图。
  • 内模式也称存储模式,是数据物理结构和存储方式的描述

操作系统中的故障

事务故障:事务未达到预期终点

系统故障:造成系统停止运转需重启的任何事件

介质故障:磁盘损坏、磁头碰撞等

B树的节点的分支数

B-树的阶数m决定了节点的分支数[m/2的上整,m],但是有两个例外,一个是叶节点,另外一个是根节点,根节点至少两个分支

内存分配方式

1) 从静态存储区域分配。内存在程序编译的时候就已经分配好,这块内存在程序的整个运行期间都存在。例如全局变量,static 变量。

2) 在栈上创建。在执行函数时,函数内局部变量的存储单元都可以在栈上创建,函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集。

3) 从堆上分配,亦称动态内存分配。程序在运行的时候用malloc 或new 申请任意多少的内存,程序员自己负责在何时用free 或delete 释放内存。动态内存的生存期由程序员决定,使用非常灵活,但问题也最多。

数据库的基本特点:

(1)数据可以共享(或数据结构化)

(2)数据独立性

(3)数据冗余小,易扩充

(4)统一管理和控制

n个结点的线索二叉树上含有的线索数为

答案:n+1

线索二叉树中每个节点有两个指针域。
若二叉树有n个节点,则有n-1条边,所以这n-1个条边占掉了n-1个指针域。
故剩下的2n-(n-1)=n+1个指针域(包括空指针)就是线索数

TTL

生存时间(TTL):长度8比特, 最大值为255。当IP包进行传送时,先会对该字段赋予某个特定的值。用来控制数据报在网络中存在的时间。目前TTL的值并不代表时间,而是代表经由路由器的个数。数据报每经过一台路由器时,路由器将TTL值减1,一旦TTL=0,系统就丢弃该数据报,并返回错误信息。这样避免了路由出现环路时数据报在路由器之间无休止地循环

冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中,CPU区分它们的依据是

答案:指令周期的不同阶段

虽然指令和数据都是以二进制形式存放在存储器中,但CPU可以根据指令周期的不同阶段来区分是指令还是数据通常在取指阶段取出的是指令,在执行阶段取出的是数据。本题容易误选A(指令操作码的译码结果),需要清楚的是,CPU只有在确定取出的是指令之后,才会将其操作码送去译码,因此,不可能依据译码的结果来区分指令和数据

重载函数在调用时选择的依据中,错误的是

A. 参数个数 B. 参数类型 C. 函数名字 D. 函数类型

答案:D

不能把返回值作为函数重载的条件,原因是编译器在编译时不会去判断函数的返回类型,函数只有调用后,编译器才会去验证返回类型,所以返回值不能作为函数重载的依据

在中继系统中,中继器处于(物理层)

中继器:物理层,信号的转发

网桥:数据链路层,帧的转发

路由器:网络层,不同网络直接的路由转发

网关:网络层以上

设计多道批处理系统时,首先要考虑的是(系统效率和吞吐量)

单道批处理注重顺序性

多到批处理方式为了提高资源利用率和吞吐量,周转时间长,无交互能力

分时系统为了实现人机交互,特点是多路性独立性及时性和交互性

实时系统最明显的特征是实时性和可靠性

hash冲突解决方法:拉链法和开放定址法

与开放定址法相比,拉链法有如下几个优点: (1)拉链法处理冲突简单,且无堆积现象,即非同义词决不会发生冲突,因此平均查找长度较短; (2)由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况; (3)开放定址法为减少冲突,要求装填因子α较小,故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1,且结点较大时,拉链法中增加的指针域可忽略不计,因此节省空间; (4)在用拉链法构造的散列表中,删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表,删除结点不能简单地将被删结点的空间置为空,否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中,空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作,只能在被删结点上做删除标记,而不能真正删除结点。

装填因子定义为:α=填入表中的元素个数哈希表的长度

α是哈希表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小

文件的结构

文件的逻辑结构: 1.连续结构 2.多重结构 3.转置结构 4.顺序结构

文件的物理存储: 1.顺序结构 2.链接结构 3.索引结构

数据库的数据项之间和记录之间都存在联系

快速排序的空间复杂度

时间复杂度平均,最坏退化为冒泡为

空间复杂度:如果就地快速排序,空间为O(1),但是递归调用需要空间 递归调用最优情况:(每一次都平分数组),最坏情况为O(n)(退化为冒泡)

数组指针和指针数组

int(*n)[10]:是数组指针,只要是指针就是4个字节

int* n[10]:指针数组

进程间的通信方式

管道: 管道中还有命名管道和非命名管道之分, 非命名管道只能用于父子进程通讯,命名管道可用于非父子进程,命名管道就是FIFO,管道是先进先出的通讯方式。FIFO是一种先进先出的队列。它类似于一个管道,只允许数据的单向流动。每个FIFO都有一个名字,允许不相关的进程访问同一个FIFO,因此也成为命名管。

消息队列: 是用于两个进程之间的通讯,首先在一个进程中创建一个消息队列,然后再往消息队列中写数据,而另一个进程则从那个消息队列中取数据。需要注意的是,消息队列是用创建文件的方式建立的,如果一个进程向某个消息队列中写入了数据之后,另一个进程并没有取出数据,即使向消息队列中写数据的进程已经结束,保存在消息队列中的数据并没有消失,也就是说下次再从这个消息队列读数据的时候,就是上次的数据!!!

信号量: 不能传递复杂消息,只能用来同步

共享内存: 只要首先创建一个共享内存区,其它进程按照一定的步骤就能访问到这个共享内存区中的数据,当然可读可写

有向图和无向图各点的度

无向图的边数组(邻接矩阵)是对阵矩阵。各顶点的度为邻接矩阵中对应行的元素之和

有向图的各顶点的度为出度加上入度之和。出度为对应顶点所在行的所有元素之和,入度为对应顶点所在列的所有元素之和

作业从提交到后备状态的变化由进程创建原语完成。作业从提交到运行状态的转换由作业调度程序完成。

HUB集线器

  • 集线器工作在物理层,只能使计算机之间互联,可以构成小的局域网,共享冲突域
  • 集线器不具有路由功能,而路由器具有集线器的功能
  • HUB也叫集线器,而地址翻译是网络层的功能,集线器不具有该功能
  • 集线器不隔离冲突域,同一集线器下的主机属于同一个冲突域

在 TCP/IP 协议族的层次中,解决计算机之间通信问题是在(网络层)

用DFS遍历一个无环有向图,并在DFS算法退栈返回时打印相应的顶点,则输出的顶点序列是(逆拓扑有序)

如果是队列:拓扑有序
如果是栈:逆拓扑有序

需要网管手动配置的路由项

静态路由是指由用户或网络管理员手工配置的路由信息。当网络的拓扑结构或链路的状态发生变化时,网络管理员需要手工去修改路由表中相关的静态路由信息。

直接路由是指路由器各网络接口所直连的网络之间进行通信所使用的路由。直接路由是在配置完路由器网络接口的IP地址后自动生成的,因此,如果没有对这些接口进行特殊的限制,这些接口所直连的网络之间就可以直接通信。

缺省路由是一种特殊的路由,可以通过静态路由配置,某些动态路由协议也可以生成缺省路由,如OSPF和IS-IS。在小型互连网中,使用缺省路由可以减轻路由器对路由表的维护工作量,从而降低内存和CPU的使用率。

动态路由是指路由器能够自动地建立自己的路由表,并且能够根据实际情况的变化适时地进行调整。

所以静态路由和缺省路由由网管手动配置。

地址转换方式

1.页式地址转换:用户作业的地址空间被分割成若干大小相等的区域,称作页或页面。相应的,将内存的存储空间也分为也页大小相等的区域,称作块(Page Frame)。在作业分配存储空间时,总是以块为单位分配,简单说就是将任意页分配到任意块中。(注意:作业调度时必须一次将全部页一次调度,故内存中块不足时等待)
2.段式地址转换:简单与页式相区别在于段式按照逻辑关系将作业进行分段,使每一段逻辑关系完整,不会像页式那样,可能由于页面大小固定的原因,使一个作业被分成两半、多半。段式中,每段被分配一个连续的存储空间,各段之间是独立的,每段均有自己的地址。
3.静态重定位:在装入作业时,将作业中指令地址和数据地址全部转换为绝对地址。
4.动态重定位:在装入作业时不进行转换,而是在执行过程中将每一条指令都由硬件的地址转换机构转换成绝对地址。

死锁

产生死锁的原因主要是:

(1) 因为系统资源不足。

(2) 进程运行推进的顺序不合适。

(3) 资源分配不当等。

产生死锁的四个必要条件:

(1)互斥条件:一个资源每次只能被一个进程使用。

(2)请求与保持条件:一个进程因请求资源而阻塞时,对已获得的资源保持不放。

(3)不剥夺条件:进程已获得的资源,在末使用完之前,不能强行剥夺。

(4)循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

避免死锁:

死锁的预防是通过破坏产生条件来阻止死锁的产生,但这种方法破坏了系统的并行性和并发性。

死锁产生的前三个条件是死锁产生的必要条件,也就是说要产生死锁必须具备的条件,而不是存在这3个条件就一定产生死锁,那么只要在逻辑上回避了第四个条件就可以避免死锁。

避免死锁采用的是允许前三个条件存在,但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链,从而避免死锁。该方法支持多个进程的并行执行,为了避免死锁,系统动态的确定是否分配一个资源给请求的进程。

常用的避免死锁的方法:

1、有序资源分配法

2、银行家算法

解决死锁问题的策略:

1、条件一:互斥条件

条件一念一否定的,因为资源的互斥性是由其自身的性质决定的。但是可以采用虚拟设备技术能排除非共享设备死锁的可能。

2、条件二:不剥夺条件

很难实现。系统一般让资源占有者自己主动释放资源,而不是采用抢占的方式。

3、条件三:占有并等待

在资源分配策略上可以采取静态的一次性资源分配的方法来保证死锁不可能发生,这是一种很保守的静态预防死锁的方法,但是资源利用率低下。

4、条件四:环路条件

在进行资源分配前检查是否会出现环路,预测是否可能发生死锁,只要有这种可能就不予以分配。即采用动态分配资源的方法。

总结来看解决死锁的策略有以下几个:

1、采用资源静态分配方法预防死锁。

2、采用资源动态分配、有效的控制分配方法来避免死锁。

3、当死锁发生时检测出死锁,并设法修复。

系统中有多个阻塞进程不一定是发生了死锁,如果阻塞进程之间相互等待,即为死锁。要强调 阻塞进程 + 相互等待。

四个必要条件,即形成死锁,这四个条件必然成立,但反过来说这四个条件成立却不一定形成死锁,所以B是错的

存储密度

存储密度=单链表数据项所占空间/结点所占空间

顺序表的空间全部用来存储数据,没有浪费空间,所以每个元素的存储密度为1

链表的每个结点除了存放数据元素,还要附加一个指示元素之间逻辑关系的指针,每个元素并非全部用来存储数据项,因此存储密度肯定小于1

删除异常和插入异常

关系规范化中的删除异常是指不该删除的数据被删除,插入异常是指应该插入的数据未被插入。

折半查找树

折半查找树的特点就在于其中序遍历是一个升序序列,因此相比于在以往的序列中进行二分查找,折半查找二叉树的优点在于不用自己去找中点,而是直接将要查找的关键字与根节点相比,小的话再和根节点的左子节点(又是相应的左子树中点,很方便吧!!)比较,大的话则是和根节点的右子节点比较

向上或向下取整的问题,也就是说如果升序序列是偶数个,那么中点应该偏左多右少还是左少右多。但是很显然应该进行一个统一

上下文切换

  1. 内存管理上下文。 包括加载页表、刷出地址转换后备缓冲器,向内存管理单元提供新的信息。
  2. 页表切换,这就是重新装载全局页表,用于给进程安装一个新的虚拟地址空间。
  3. 由于进程的栈都在内核态,所以切换内核态堆栈上下文数据。
  4. 硬件上下文,主要部分就是进程和CPU的任务状态寄存器,就是TSS中的字段。在这里CPU为了减轻很多切换的工作,很多地方都是如果有必要,就切换,就是所谓的惰性原则。

相联存贮器是按什么进行寻址的存贮器

答案:内容指定方式

相联存储器(associative memory),也称为按内容访问存储器(content addressed memory)或简称为TLB(Translation Lookaside Buffer) 它是一种不根据地址而是根据存储内容来进行存取的存储器,可以实现快速地查找块表

关键路径

若在带权的有向图中,以顶点表示事件,以有向边表示活动,边上的权值表示活动的开销(如该活动持续的时间),则此带权的有向图称为AOE网

定义:从源点到汇点具有最大长度的路径。这个概念要清楚,一个工程不一定有一条关键路径,可能会有多条。 关键路径是以拓扑排序为基础的 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 一个事件的最迟开始时间为以该事件为头的弧的活动最迟开始时间与该活动的持续时间的差 关键活动一定位于关键路径上

一个扇区平均存取时间

存取时间=寻道时间+延迟时间+传输时间

存取一个扇区的平均延迟时间为旋转半周的时间,传输时间为

GET和POST的区别

HTTP定义了与服务器交互的不同方法,最基本的是GET和POST

GET与POST方法有以下区别:

(1)在客户端, Get 方式在通过 URL 提交数据,数据 在URL中可以看到;POST方式,数据放置在HTML HEADER内提交。 (2)GET方式提交的数据最多只能有1024字节,而POST则没有此限制(3)安全性问题。正如在( 1 )中提到,使用 Get 的时候,参数会显示在地址栏上,而 Post 不会。所以,如果这些数据是中文数据而且是非敏感数据,那么使用 get ;如果用户输入的数据不是中文字符而且包含敏感数据,那么还是使用 post 为好。 (4)安全的和幂等的。所谓安全的意味着该操作用于获取信息而非修改信息。幂等的意味着对同一 URL 的多个请求应该返回同样的结果。完整的定义并不像看起来那样严格。换句话说, GET 请求一般不应产生副作用。从根本上讲,其目标是当用户打开一个链接时,她可以确信从自身的角度来看没有改变资源。比如,新闻站点的头版不断更新。虽然第二次请求会返回不同的一批新闻,该操作仍然被认为是安全的和幂等的,因为它总是返回当前的新闻。反之亦然。 POST 请求就不那么轻松了。 POST 表示可能改变服务器上的资源的请求。仍然以新闻站点为例,读者对文章的注解应该通过 POST 请求实现,因为在注解提交之后站点已经不同了(比方说文章下面出现一条注解)。

(1).首先是”GET方式提交的数据最多只能是1024字节”,因为GET是通过URL提交数据,那么GET可提交的数据量就跟URL的长度有直接关系了。而实际上,URL不存在参数上限的问题 ,HTTP协议规范没有对URL长度进行限制。这个限制是特定的浏览器及服务器对它的限制。IE对URL长度的限制是2083字节(2K+35)。对于其他浏览器,如Netscape、FireFox等,理论上没有长度限制,其限制取决于操作系统的支持。

注意这是限制是整个URL长度,而不仅仅是你的参数值数据长度。

(2).理论上讲,POST是没有大小限制的,HTTP协议规范也没有进行大小限制,说“POST数据量存在80K/100K的大小限制”是不准确的,POST数据是没有限制的,起限制作用的是服务器的处理程序的处理能力

指针变量赋值

指针变量是用来指示一个内存地址的变量,因此只能将地址赋给指针变量,而不能是整数或浮点数 整数通过强制类型转换后可赋值给指针变量, 要注意转换后的类型要和指针指向的类型一致,并且这个整数的位长不能超过指针的位长

强迫性中断和自愿中断

强迫性中断:这类中断事件不是正在运行程序所期待的,而是由某种事故或外部请求信号所引起的。

自愿中断:自愿中断是运行程序所期待的事件,这种事件是由运行程序请求操作系统服务而引起的。

按功能所分的五大类中断中,输入输出中断、外中断、机器故障中断、程序性中断属于强迫性中断。访管中断属于自愿中断。

return 后面括号里的表达式的值即是此函数的值。请问这句话的说法是正确的吗?

答案:错误

当return后面表达式值的类型与函数的类型不一致时,需要强制类型转化

DBMS 提供 DML 实现对数据的操作。可以独立交互 使用的 DML 称为

数据操纵子语言通常分为两类:一类是嵌入主语言,由于这种语言本身不能独立使用,故称为宿主型的语言;另一类是交互式命令语言,由于这种语言本身能独立使用,故又称为自主型或自含式语言

mutex值

mutex > 0时,其值表示可用资源数,mutex < 0时,其绝对值表示等待使用资源的进程数

处理外部中断时,应该由操作系统保存的是

外部中断处理过程,PC值由中断隐指令自动保存,而通用寄存器内容由操作系统保存

为了保证代码的异常安全性,应该避免在析构函数中抛异常

构造函数抛出异常后,已经构造的成员对象会被逆序析构,申请的内存资源会被资源释放,不会调用析构函数。而且构造函数抛出异常是唯一表明构造失败的方法 effective C++“条款08:别让异常逃离析构函数”指出来如果析构函数抛出异常,对于vector<Widget>这样的一个对象数组,如果第一个Widget析构有异常抛出,这时候还要销毁数组中剩下的Widget否则会造成内存泄漏,但是如果剩下的Widget析构时也抛出异常,就会两个异常同时存在,程序如果不是结束执行就会产生不明确行为。即使不是使用容器或数组,在析构函数中抛出异常也可能导致程序过早结束或不明确行为

迭代器失效

向容器中添加或者删除元素的操作可能会使指向容器元素的迭代器失效,失效的迭代器将不指向任何元素。 一般有两种情况无法通过迭代器++操作遍历整个STL容器; 无法通过迭代器存取迭代器所指向的内存。

利用二叉链表存储树,则根节点的右指针是(空)

二叉链表各节点的左指针指向孩子,右指针指向兄弟,而根节点没有兄弟,所以右指针指向空

在计算机网络中,能将异种网络互联起来,实现不同网络协议互相转换的网络互连设备是(网关)

网关和路由器最大的区别是是否连接相似的网络。如果连接相似的网络,则称为路由器。而连接不相似的网络,称为网关

抢占式进程调度和非抢占式进程调度

可抢占式调度引起系统的开销更大

可抢占式调度是严格保证任何时刻,让具有最高优先级的进程占有处理机运行,因此增加了处理机调度的时间,引起为退出处理机的进程保留现场,为占有处理机的进程恢复现场等时间(和空间)开销增大

非抢占式(Non-preemptive):让进程运行直到结束或阻塞的调度方式(容易实现,适合专用系统,不适合通用系统) 抢占式(Preemptive):允许将逻辑上可继续运行的在运行过程暂停的调度方式,可防止单一进程长时间独占CPU(系统开销大)

三次握手的序列号

客户端:发送X

服务端:发送Y, 确认X+1

客户端:发送X+1(1000),确认Y+1(2000)

C++语言中不能重载的运算符

. .* :: ?: sizeof typeid
记忆:带点的符号不能重载

常见的周知端口号

协议端口号
FTP20/21
SSH22
TELNET23
SMTP25
DNS53
HTTP80
HTTPS443
WWW8080

抖动

抖动是指请求分页存储系统中,由于页面置换算法设计不当或者进程分配的物理页面数量太少,造成刚被淘汰的页面很快又被调入,如此反复,使得大量的CPU时间花费在页面置换上的现象

进程和线程

进程是具有一定独立功能的程序关于某个数据集合上的一次运行活动,进程是系统进行资源分配和调度的一个独立单位

线程是进程的一个实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位.线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器,一组寄存器和栈),但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源

主要区别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间,一个进程崩溃后,在保护模式下不会对其它进程产生影响,而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量,但线程之间没有单独的地址空间,一个线程死掉就等于整个进程死掉,所以多进程的程序要比多线程的程序健壮,但在进程切换时,耗费资源较大,效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作,只能用线程,不能用进程

字段就是属性,行是元组,关系模式即是二维表,表格表示实体类型与实体之间的联系

++(a++)表达式

错误的写法,a++操作通过临时量返回其值(右值),该值是一个常量,不能被修改

A *a = new A[10] delete []a

构造函数和析构函数都分别执行10次

子网掩码与IP地址求子网

子网掩码与IP地址相与得出子网

实时操作系统的两大特性

实时系统最重要的两个性质就是实时性和可靠性。实时性是指系统能及时响应外部件的请求;并在规定时间内完成对该事件的处理;高可靠性是指系统本身要安全可靠,因为像生产过程的实时控制、航空订票等实时事务系统,信息处理的延误或丢失往往会带来不堪设想的后果

算法的特性

1.有限性:有限步骤之内正常结束,不能形成无穷循环 2.确定性:算法中的每一个步骤必须有确定含义,无二义性得以实现 3.输入:有0个或多个输入 4.输出:至少有一个输出 5.可行性:原则上能精确进行,操作可通过已实现基本运算执行有限次完成

删除表中的所有数据

:是删除表中的数据,删除速度比delete更快,无法撤回(回退)

$truncate\ table\ book:删除数据表中的数据,可以回退,可添加where 子句

关于视图的说法

视图是一种查看数据表中数据的方式,视图具有一组命名的属性和相应的属性值,除非是索引视图,否则视图不占用任何物理存储空间

多级队列和多级反馈队列

多级队列:该算法将系统中的进程就绪队列从一个拆分为若干个,将不同类型或性质的进程固定分配在不同的就绪队列,不同的就绪队列采用不同的调度算法,一个就绪队列中的进程可以设置不同的优先级,不同的就绪队列本身也可以设置不同的优先级。

多级队列调度算法由于设置多个就绪队列,因此对每个就绪队列就可以实施不同的调度算法,因此,系统针对不同用户进程的需求,很容易提供多种调度策略。

多级反馈队列:1)设置多个就绪队列。在系统中设置多个就绪队列,并未每个队列赋予不同的优先级。第一个队列的优先级最高,第二个次之,其余的优先级逐个降低。该算法为不同的队列中的进程所赋予的执行时间片的大小也各不相同,在优先级愈高的队列中,其时间片就愈小。2)每个队列都采用FCFS算法。3)按队列优先级调度

NAT

在计算机网络中,网络地址转换(英语:Network Address Translation,缩写为NAT),也叫做网络掩蔽或者IP掩蔽(IP masquerading),是一种在IP封包通过路由器或防火墙时重写源IP地址或目的IP地址的技术。这种技术被普遍使用在有多台主机但只通过一个公有IP地址访问因特网的私有网络中。 NAT 是作为一种解决IPv4地址短缺以避免保留IP地址困难的方案而流行起来的。 支持端口转换的NAT又可以分为两类:源地址转换和目的地址转换NAT。前一种情形下发起连接的计算机的IP地址将会被重写,使得内网主机发出的数据包能够到达外网主机。后一种情况下被连接计算机的IP地址将被重写,使得外网主机发出的数据包能够到达内网主机。实际上,以上两种方式通常会一起使用以支持双向通信。

发表评论

电子邮件地址不会被公开。