做题笔记

2018-9-5

在Unix系统中，若一个进程退出时，其子进程还在运行（没有被杀死），则这些子进程会变成孤儿进程（Orphan Process），请问孤儿进程会被以下哪一个系统进程接管？
答案：init
僵尸进程：当一个进程完成它的工作终止之后，它的父进程需要调用wait()或者waitpid()系统调用取得子进程的终止状态。如果没调用，子进程的描述符还保留在系统中，那这个子进程就是僵尸进程。
孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
孤儿进程最后会被init接管，而僵尸进程会继续占用资源。

如果二叉树T2是由树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的 。
答案：先序。简单画个abc就找到了。

已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个 L中 不存在的元素，则 关键字的 比较次数最多是（）
答案：5
一种直观的办法：

设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到Hash表中需要做几次线性探测？
答案：n*(n-1)/2，为什么是n-1呢
tm的问的是叫线性探测，测一下隔壁的才叫线性探测？所以第一次线性探测数为0？

在RHEL5系统中使用vi编辑文件report.txt时，要自下而上查找字符串“2006”，应该在命令模式下使用（ ）
从上往下查找，就像坐滑滑梯-------/
从下往上查找，就需要倒挂金钩了-------？

long → float 竟然无须强制转换

使用useradd创建用户时和主目录相关的参数是()
-p 设定帐号的密码
-d 指定用户的主目录
-m 自动建立用户的主目录
-M 不要自动建立用户的主目录

2018-9-4

若串S=’software’，其子串数目为(包括空串)：
答案：37。software本身属于子串

在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）

将森林F转换为对应的二叉树T，F中叶结点的个数等于 （）
T中左孩子指针为空的结点个数

MySQL主从架构的主数据库中不可能出现的日志为：
答案：中继日志。（睁大眼看清楚问的是主数据库）

设有6个结点的无向图，该图至少应有（）条边，才能确保是一个连通图？
答案：11
这里需要确保，而不是至少。那么假设他不是连通图，只有五个点连通。五个点连通最多就是10条线，那加多一条就必须六个点，因此11。

文件aaa的访问权限为rw-r--r--,现要增加所有用户的执行权限和同组用户的写权限，下列哪些命令是正确的？
答案：chmod 775 aaa
第一个rwx表示所有者，第二个表示组第三个表示处理所有者和组的其他人
首先是764，但是要求全部人（不止其他人）有执行权限，所以第二个和第三个都要加1。

2018-8-30

下面排序算法中， 算法可能会出现下面情况：初始数据有序时，花费的时间反而最多
快速排序，因为快排会按照大小将数组分为两半，有序的话分就不均匀了

已知表tbl中字段land_ID建有索引，字段cust_id建有唯一索引，下列语句查询逻辑相同，其中执行效率最优的是
答案D。免在 where 子句中使用 or 来连接条件，否则将导致引擎放弃使用索引而进行全表扫描

A：
SELECT * FROM tbl
WHERE land_id > 750
or (cust_id=180 or cust_id=560)
 
B:
SELECT * FROM tbl
WHERE (cust_id=180 or cust_id=560)
or land_id > 750
 
C：
SELECT * FROM tbl WHERE land_id > 750
UNION
SELECT * FROM tbl WHERE cust_id = 180
UNION
SELECT * FROM tbl WHERE cust_id = 560
 
D:
SELECT * FROM tbl WHERE land_id > 750
UNION
( SELECT * FROM tbl WHERE cust_id = 180
UNION ALL
SELECT * FROM tbl WHERE cust_id = 560)

采用哈希表组织100万条记录，以支持字段A快速查找，则（）
错：上可以在常数时间内找到特定记录：不要听b树瞎bb，怎么可能
对：式哈希曼最坏查找时间复杂度是O（n）：拉链式哈希就是通过链来解决冲突的哈希

下列哪个是合法的 Java 标识符？（ ）
只有英文，数字，下划线和$，而且数字不能做开头

2018-8-29

已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行____次探测。
答案是n(n+1)/2。第一个探测一次，发现没有冲突，ok。第二个第一次发现有冲突，第二次没有，ok。因此第n个要探测n次。所以1+2……n=n(n+1)/2。

若关系R的候选键都是由单属性构成的, 且每个非主属性完全函数依赖于候选键,那么R的模 式是（）
又忘了范式的标准了
1NF：不能有表中表；
2NF：符合1NF，非主属性完全依赖于码（去除部分函数依赖）
3NF：符合2NF，非主属性直接依赖于码（去除传递函数依赖）
BCNF：符合3NF，主属性不依赖于主属性。
虽然每个非主属性完全函数依赖于候选键，但是是完全函数依赖的同时也可能是传递函数依赖呀

JDBC驱动程序分为几种类型？（）
看了也不知道是啥的四种：jdba-odbc桥接、本地API驱动、网络协议驱动和本地协议驱动

以下关于栈的说法错误的是：
在栈空的情况下，一定不能作出栈操作，否则产生溢出：这是下溢出
栈一定是顺序存储的线性结构：还可以是链表

2018-8-28

有ABCDEF 六个城市，每一个城市都和其他所有城市直接相连，问从A——B有多少种连接方式，路径不允许在两个城市之间往返
想漏了，老以为会经过全部城市

A-?-B:4
A-?-?-B:4*3
A-?-?-?-B:4*3*2
A-?-?-?-?-B:4*3*2*1

下列叙述中正确的是（ ）
在栈中，栈顶指针的动态变化决定栈中元素的个数
错误：
在循环队列中，队尾指针的动态变化决定队列的长度
栈的栈低指针不动，入栈时头指针+1。循环队列中，头尾指针共同决定长度。

数组A[0..5,0..6]的每个元素占5个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是()
列优先，那就是一列一列数，而不是一行一行。所以是第六列，每列6个元素，在第36个元素里，所以1000+36×5=1180。但是！但是！求的是第36个元素的起始地址而不是结束地址，所以还要1180-8=1175。

若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（ 　 ）存储方式最节省运算时间和存储空间。
答案是双向链表而不是仅有尾指针的单循环链表
尾指针也是指向next=null，还是要遍历到最后

Servlet的生命周期可以分为初始化阶段，运行阶段和销毁阶段三个阶段，以下过程属于初始化阶段是（）。
加载Servlet类及.class对应的数据
创建ServletConfig对象
创建Servlet对象

2018-8-23

下列哪一个Transact-SQL语句能够实现收回user2查询基本表T的权限（）
REVOKE SELECT ON T FROM user2，Transact-SQL意思是那些非查询语句的意思？GRANT是授权，REVOKE是撤权，SELECT是操作，在表T对于用户user2

线性表是具有 n 个（）的有限序列(n>0)
线性表是由0到多个数据元素组成，数据元素由多个数据项组成

单链表中，增加一个头结点的目的是为了 。
答案：方便运算的实现！？！有头结点统一了空队列与非空队列的处理

DBMS包括DBS和DB？
数据库(DB)：长期存放在计算机内的有组织的可共享的数据集合
数据库管理系统(DBMS)：完成数据库的建立、使用和维护功能
数据库系统(DBS)
数据库+数据库管理系统
（应用系统+数据库管理员 +用户）
数据库管理员(DBA)：除DBMS完成外，还需专门的人员来完成，这些人被称为DBA

下列叙述中正确的是（ ）。
错误：循环链表是循环队列的链式存储结构
循环队列是把数组弄成一个环（？！）循环队列是改进的顺序队列

求解最短路径的Floyd算法的时间复杂度为()
Floyd算法的基本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过若干个节点X到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点X，我们检查Dis(AX) + Dis(XB) < Dis(AB)是否成立，如果成立，证明从A到X再到B的路径比A直接到B的路径短，我们便设置Dis(AB) = Dis(AX) + Dis(XB)，这样一来，当我们遍历完所有节点X，Dis(AB)中记录的便是A到B的最短路径的距离。

int n;//n为节点个数
for(int i=0; i<n; ++i ){
    for (int j=0; j<n; ++j ){
        for ( int k=0; k<n; ++k ){
            if ( Dis[i][k] + Dis[k][j] < Dis[i][j] ){
                // 找到更短路径
                Dis[i][j] = Dis[i][k] + Dis[k][j];
            }
        }
    }
}

linux提供了一种机制可以保证只要父进程想知道子进程结束时的状态信息， 就可以得到。这种机制就是: 在每个进程退出的时候,内核释放该进程所有的资源,包括打开的文件,占用的内存等。但是仍然为其保留一定的信息(包括进程号the process ID,退出状态the termination status of the process,运行时间the amount of CPU time taken by the process等)。直到父进程通过wait / waitpid来取时才释放。
孤儿进程：一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
僵尸进程：一个进程使用fork创建子进程，如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。这种进程称之为僵死进程。
僵死进程并不是问题的根源，罪魁祸首是产生出大量僵死进程的那个父进程，所以，解决方法就是kill那个父进程，于是僵尸进程就可以被init进程接收，释放。

2018-8-22

表达式“X=A+B*（C--D）/E”的后缀表示形式可以为
答案：XABCD-*E/+=
一种好厉害，但还是不知道怎么做这题的方法：

这里我给出一个中缀表达式~ 
a+b*c-(d+e) 
第一步：按照运算符的优先级对所有的运算单位加括号~ 
        式子变成拉：((a+(b*c))-(d+e)) 
第二步：转换前缀与后缀表达式 
        前缀：把运算符号移动到对应的括号前面 
              则变成拉：-( +(a *(bc)) +(de)) 
              把括号去掉：-+a*bc+de  前缀式子出现 
        后缀：把运算符号移动到对应的括号后面 
              则变成拉：((a(bc)* )+ (de)+ )- 
              把括号去掉：abc*+de+-  后缀式子出现

第二种方法如图

层次模型必须满足的一个条件是（ ）。
除了根节点，有且仅有一个结点为父结点（树来的？）

Web程序通常采用MVC架构来设计，数据库相关操作属于（）？
实锤，Model

常见的数据模型是（）
常用的数据模型：概念模型、逻辑模型、物理模型
常用的逻辑模型：层次模型、网状模型、关系模型

T(n)=1(n<=1),T(n)=25T(n/5)+n^2,T(n)复杂度是多少？
答案O(n^2logn)。像这种题，不会算就代特殊值，例如5（并不特殊。。。）

2018-8-21

以下哪个算法可以判断出一个有向图中是否有回路
拓扑排序：由于拓扑排序要求图无回路，看图好像就是一路走下去遍历全部节点一样

反映现实世界中实体及实体间联系的信息模型是
E—R模型，而不是关系模型。关系模型与层次模型、网状模型相对应

关系中行、列次序的交换性质是
行、列均可交换（怕什么呢？为什么我无端端记得有一个不能调换，其实并不是）

ICMP协议位于
物理层：RJ45、CLOCK、IEEE802.3（中继器、集线器）
数据链路层：PPP 、FP 、HDIC、 VLAN 、MAC（网桥、交换机）
网络层：IP、ICMP、ARP、RARP、OSPF、 IPX 、RIP 、IGRP（路由器）
传输层：TCP 、UDP 、SPX
会话层：NFS、SQL 、 NETBIOS 、RPC
表示层：JPEG 、MPEG、 ASII
应用层：FTP、 DNS 、Telnet、 SMTP 、HTTP、 WWW、 NFS

子模式DDL用来描述
外模式（子模式）：用户能看到处理的数据结构
概念模式（模式）：处理全局的数据结构，包括数据之间的约束、联系
内模式：描述储存上的数据结构

由权值为29,12,15,6,23的五个叶子节点构造的哈夫曼树为,其带权路径长度为
哈夫曼树的带权路径长度的计算方法是，累加全部节点的-节点值×（当前层数-1）

当建立连接时，下面哪一个数据包发送顺序是正确的TCP握手协议过程
SYN、SYN+ACK、ACK

2018-8-20

关于因特网中路由器和广域网中结点交换机叙述错误的是
对的：
路由器用来互连不同的网络（不同网段？），结点交换机只是在一个特定的网络中工作（同网段？）。
路由器专门用来转发分组，结点交换机还可以连接上许多主机。
路由器根据目的网络地址找出下一跳（即下一个路由器），而结点交换机则根据目的站所接入的交换机号找出下一跳（即下一个结点交换机）。
错的：
路由器和结点交换机都使用统一的IP协议。
路由器在网络层，网络层最重要但不唯一是ip协议。交换机在数据链路层，使用以太网协议

ARP协议是ip映射到MAC，RARP是MAC映射到ip

若事务T对数据R已加X锁，则其它事务对R
S锁是共享锁，X锁是独占锁

表的设计视图方式中，不可以（）。
既然是叫设计的视图，那对字段的增删改都可以，而删除一条记录则不行

vi编辑文件时，要将某文本文件第1行到5行的内容复制到文件中的指定位置
将光标移到第1行，在vi命令模式下输入5yy,然后将光标移到制定位置，按p键
使用末行命令1，5y，然后将光标移到制定位置，按p键

在linux网络编程中,以下关于socket描述符正确的是:
对的：
socket存在两种模式:阻塞和非阻塞
系统调用read从socket中读取数据时,当read返回0的时候,表示socket中数据读取完毕
如果socket设置成非阻塞模式,当socket的输入缓冲区没有可读数据时,read操作会返回错误
错的：
在阻塞socket上调用write函数发送数据,函数返回时,表示数据已经发送出去