---

记录最近两天碰到的笔试题目。

1、URL和URI的区别？

URI(Universal Resource Identifier)是通用资源标识符，Web上的每种可用资源，比如图像、视频、HTML文档等都由一个通用资源标识符进行定位，即URI是采用一种特定语法标识一个资源的字符串。
URI通常由3部分构成：访问资源的命名机制；存放资源的主机名；资源名称。比如http://www.blog.cn/text/ziyuan1.html/，其中http表示这是一个可以通过http协议访问的资源，主机是www.blog.cn，资源名称/text/ziyuan1.html。

URL(Uniform Resource Locator)统一资源定位符，是URI的一个子集，可以唯一地标志一个资源在网络上的位置，采用URL可以用一种统一的格式来描述各种信息资源。URL是URI概念的一种实现方式。
URL一般格式为：protocol://hostname[:port]/path/[;parameters][?query]#fragment，第一部分是协议，第二部分是存有该资源的主机地址(有时也包括端口号)，第三部分是主机资源的具体地址。

区别：尽管URI和URL都定义了资源是什么，但URL还定义了如何访问该资源。

2、TCP半连接队列和全连接队列的区别？

• 半连接队列(syn队列)：客户端发送SYN包，服务端收到后回复SYN+ACK后，服务端进入了SYN_RCVS状态，此时内核会将连接存储到半连接队列。
• 全连接队列(accept队列)：当服务器端收到客户端的ACK后，内核将连接从半连接队列中取出，添加到全连接对列中，服务端进入ESTABLISHED状态。服务器调用accept()函数时会返回队列头的连接给用户进程。

3、单工、半双工、全双工？

• 单工只支持数据在一个方向上传输。
• 半双工允许数据在两个方向上传输，但是在某一时刻只允许数据在一个方向上传输。
• 全双工允许数据同时在两个方向上传输，能够同时发送和接收数据，就像平常打电话一样，说话的同时也能听到对方的声音。

4、CAS无锁队列的实现原理？

在多线程高并发编程的时候，最关键的问题是保证临界区的对象的安全访问，通常是用加锁来处理，枷锁本质上是将并发转变为串行来实现，但是这样势必会影响吞吐量。对于并发控制而言，锁是一种悲观策略，会阻塞线程执行，而无锁是一种乐观策略，它会假设对资源的访问是不冲突的，既然不冲突，线程也就不需要阻塞。
无锁的策略采用CAS来鉴别线程冲突，一旦检测到冲突，线程就会多次尝试操作直到没有冲突为止。

CAS：Compare And Swap，比较和交换，主要是通过处理器的指令来保证操作的原子性，它包含三个操作数：V表示变量内存地址，A表示旧的预期值，B表示准备设置的新值。

CAS的语义是：我认为V中的值是A，如果是，那么将A更新为B，否则不修改，并被告知Ｖ的值实际为多少。

当多个线程尝试使用CAS更新一个变量时，只有其中一个线程能更新变量的值，而其他线程都失败，失败的线程并不会挂起，而是被告知这次竞争中失败，并且可以再次尝试。

5、解释下段页式存储管理方式？

分段管理：很方便按照逻辑模块实现信息的共享和保护，但是如果段过长，不易分配，并且会产生外部碎片。
分页管理：内存利用率高，不会产生外部碎片，只有少量的页内碎片，但是不方便按照逻辑模块实现信息的共享和保护。
段页式管理：程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。

6、交换和路由的区别？

• 交换机工作在数据链路层，用来隔离冲突域，连接的设备同属于一个子网，负责子网内部的通信。而路由器工作在网络层，用来隔离子网，连接的设备分属不同子网，工作范围是多个子网之间，负责网络之间的通信。
• 交换机转发数据依据MAC地址，而路由转发数据依据IP地址。

7、封装的含义？

封装指的是把内部实现细节包装起来，不允许外部程序直接访问，而是通过类提供的方法来对隐藏的信息进行操作和访问。

8、代码实现单链表的排序？

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    public ListNode sortInList (ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode left = sortInList(head);
        ListNode right = sortInList(tmp);
        ListNode h = new ListNode(0);
        ListNode res = h;
        while(left != null && right != null){
            if(left.val < right.val){
                h.next = left;
                left = left.next;
            }else{
                h.next = right;
                right = right.next;
            }
            h = h.next;
        }
        h.next = left!=null?left:right;
        return res.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

9、寻找字符串中第一个的只出现一次的字符？

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Map<Character,Integer> map = new LinkedHashMap<Character,Integer>();
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(map.containsKey(c)){
                map.put(c,map.get(c)+1);
            }else{
                map.put(c,1);
            }
        }
         for(Character c:map.keySet()){
             if(map.get(c) == 1){
                 System.out.println(c.charValue());
                 return ;
             }
         } 
        System.out.println(-1);
        return ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

10、在有继承时，为什么基类的析构函数是虚函数？

如果基类不设置称为虚函数，当删除基类指针指向的派生对象时候，就会调用基类的析构函数，不会调用子类的析构函数，造成子类对象释放不完全，内存泄漏。
因此要把基类析构函数设置为虚函数，这样删除的时候，会先调用子类析构函数，再调用基类析构函数。

11、什么是线程安全？

当多个线程访问一个对象时，如果不用考虑这些线程在运行时环境下的调度和交替执行，也不需要进行额外的同步，或者在调用方法进行任何其他的协调操作，调用这个对象的行为都可以获得正确的结果，那这个对象就是线程安全的。

12、代码实现线程安全的单例模式？

public class Singleton {
    private static Singleton instance;
    private Singleton() {}
    public static synchronized Singleton getInstance() {
        if (instance == null) {
            instance = new Singleton();
        }

        return instance;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12

public class Singleton{
    private Singleton instance;
    private static final Lock lock = new ReentrantLock();
    private Singleton(){}
    public static Singleton getInstance(){
        lock.lock();
        try{
            if(instance == null)
                instance = new Singleton();
            return instance;
           }finally{
               lock.unlock();
           }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15