search

xiyoulaoyuanjia / blog

记录与总结 and else？
5 stars 2 forks source link

sohu_For2013 #3

Closed xiyoulaoyuanjia closed 11 years ago

xiyoulaoyuanjia commented 11 years ago

原文在这里

注意原文答案有一些错误

_第6题目:^ 表示异或_

_第7题:二叉树是一种树形结构，每个节点至多有两颗子树，下列一定是二叉树的是（）_

A. 红黑树
B. B树
C. AVL树
D. B+树

红黑树是一种自平衡的二叉树 它是在1972年由鲁道夫.贝尔 发明的..他称它为 "对称二叉B树" (由这里我们可以看出B树不是对称的也不是二叉的...) 它可以在O(log n)时间内插入,查找,和删除..这里n是树中元素的数目 参考 wiki

B树 概括起来说是一个节点可以有多余2个子节点的二叉排序树 wiki

B+树 wiki上面解释的不清楚.有时间在看呀..

AVL树 AVL 数是最先发明的自平衡二叉树 在AVL数中任何相邻的两个子树的高度相差不超过1.

通过上面简短的分析可知..上面的答案显而易见..AC

_第8题: a[m][n] == ((a+m)+n)

xiyoulaoyuanjia commented 11 years ago

_第九题:序列16， 14， 10， 8， 7， 9， 3， 2， 4， 1的说法下面哪一个正确（)_

A. 是大顶堆
B. 是小顶堆
C. 不是堆
D. 是二叉排序树

本题目答案 A 如何从一个序列判断是 大还是小堆呢?

关于这个问题可以看看 堆的定义

父节点总是大于或者等于(小于或者等于子节点 小顶堆)子节点 成为 大顶堆 上面是定义,但是如何存贮这种数据结构呢? 为了便于找到父节点的(左右)子节点,常常使用数组存贮.并且规定第n个 节点的子节点分别在 2n 与 2n+1的位置....(根节点从1开始)

上面题目这样考感觉很不爽.. 好吧...16 的子节点此次为 14.与10 14的自己点以此为 8 7 此次类推可得..是大顶堆

_10. 输入若已经是排好序的，下列排序算法最快的是（）_

A. 插入排序
B. Shell排序
C. 合并排序
D. 快速排序

本题目答案选A

快速排序在 排好序的情况下是最慢的......

shell 排序?

合并排序?

shell 排序? 也就是希尔排序...因为其算法设计者的名字为 Donald shell 所以也成为shell 排序..

合并排序...把两个有序的合并为一个有序的..

11.一种既有利于短作业又兼顾长期作业的调度方法是（）。

A. 先来先服务
B. 均衡调度
C. 最短作业优先
D. 最高响应比优先

B

操作系统的这几种调度方式谁能讲解一下哈?

先来先服务: 按作业进入后备队的先后顺序,让先来的作业优先被选中..缺点是 短时间执行的作业如果排在长时间执行的作业之后,会导致长时间不能得到执行..吞吐率下降...

均衡调度: 根据系统运行情况和作业属性把作业分类.轮流从不同的类型中挑选作业..目标是合理的利用系统的各种资源.这里包括 io 资源与 cpu资源

这里提供一个例子:

把等待作业分为如下队列:

  • cpu密集型队列
  • IO 密集型作业
  • 计算量与IO均衡的作业.

调度的时候可以考虑系统的情况从上面的队列中选中作业..

最短作业优先:这里指优先选中运行时间最短的作为下一次的服务对象..可以提高系统的吞吐量..

最高响应比优先: 这里优先处理最高响应比 所以需要定义 最高响应比: 作业周转时间/作业运行时间=(作业等待时间+作业运行时间)/作业运行时间=1+(作业等待时间)/作业运行时间

12.同一进程下的线程可以共享（）

A. stack
B. data section
C. register set
D. thread ID

data section

这里补充几点...

  • 同一进程下线程 共享的有 进程的代码段..进程的公共变量. 进程打开的文件描述符..进程的信号处理函数..进程的当前目录与进程的用户id进程的组id
  • 同一进程下线程独有的有: 线程id(线程的标识) 栈, register set 的值..错误返回码. 线程的信号屏蔽码

同一进程下的线程的堆 这个肯能不一定... 有共享也有没有共享 共享堆需要考虑同步机制...

13.系统中的“颠簸”是由（）引起的。

A. 内存容量不足
B. 缺页率高
C.交换信息量大
D. 缺页率反馈模型不正确

颠簸是计算机操作系统中的"抖动" 的术语... A.B 都会发生这种情况..但是主要原因是D

14.8瓶酒一瓶有毒，用人测试。每次测试结果8小时后才会得到，而你只有8小时的时间，最少需要（）人测试

A. 2
B. 3
D. 4
D. 6

主动关闭的一端会出现 TIME_WAIT 状态吗? 还有复习 TIME_WAIT 状态那章经典的状态图

Time_wait 的出现有两点 1.是为了防止下图出现的情况的:

TCP 协议定义的在主动连接的一方socket将进入 time_wait 状态,持续时间为 2msl(max segment lefttime)

msl windows下默认为4分钟,The Internet host requirements document suggests a using 2 minutes as the MSL, but some implementations use values as small as 30 seconds[8].

time_wait 还有另外一点值得注意:

To implement TCP's full-duplex connection termination reliably

这个怎么理解呢?

可以考虑这种情况..

  • A 向B 发送 Final A的状态从 estalished 到 Fin_wait_1
  • B 收到 A的 Final 状态从 established 到 closed_wait 并且发送 ACK 给 A
  • A 收到 B的 ACK 状态从 fin_wait_1 到 Fin_wait_2 并且什么都不发..(此种模式相当于单双工)
  • B 把 需要发给A的都发完了之后 需要 发送 Final 到 A(结束这种单双工模式) 此时 状态从 closed_wait 到 Last_ACK 等待
  • A 收到 B 发送的 FINAL 之后 给B 发送 ACK

___注意 此时是问题的关键 假设A 给B 发送完ACK 之后直接转换到 CLOSED 状态,A发给B的ACK 由于网络原因

丢失了.. B等待了很长时间没有受到 ACK 会重发 FINAL给 A 此时如果刚好有一个新连接 则会回一个RST B收到则会 发生错误.. 我们再来考虑 如果 A 发完了 ACK 之后 状态转移到 TIME_WAIT 则当 B 重新发的

FINAL 到时则会重新发送一个ACK 则会避免上面说的这种问题___

关于 time_wait 这里推荐一篇文章

这里补充一点 关于TCP状态图的 知识 感觉之前看的基本上都忘光了...

这里面一共有11 个状态

客户端 不可以调用bind吗?

事实上应该来说 服务器与客户端都可以调用bind的.

关于bind 的几点说明

  • bind 时不指明 端口号则会 随机分配一个未占用的端口
  • 端口 1-1024 一般用来系统使用..所以申请1-1024 之间需要 root权限

这里需要总结一下常见的socket 开发的一般步骤分为服务器端与客户端:

这幅图很好说明了.网络编程的一般过程

服务器端

  • socket 建立网络套接字 
#include <sys/socket.h>
int socket (int family, int type, int protocol);

其中 family 取值:

type的取值 :

protocol的取值:

例如 sockfd=socket(AF_INET,SOCK_STREAM,0);

  • 绑定网络套接字与 地址
#include <sys/socket.h>
int bind (int sockfd, const struct sockaddr *myaddr, socklen_t addrlen);

例如 bind(sockfd,(struct sockaddr*)&my_addr,sizeof(struct sockaddr));

  • 监听端口:
#include <sys/socket.h>
#int listen (int sockfd, int backlog);

为了便于理解上面的 backlog 可以看如下一幅图:

对于一个确定的 sockfd 网络套接字 内核有两个队列

  • 未完成三次握手请求的队列 which contains an entry for each SYN that has arrived from a client for which the server is awaiting completion of the TCP three-way handshake. 这些 sockets 处于 SYN_RCVD 的状态.
  • 连接已经正常建立了.处于 established 的状态 .

上诉 backlog参数标示 上面两个队列的个数之和.. 细节可以参考 UNP1

  • accept 函数阶段
# include<sys/socket.h>
int accept accept(int socked,struct sockaddr * cliaddr,socklen_t * addrlen)

客户端

客户端比较简单.基本上就是建立套接字 就可以直接 connect了..

  • socket 与server相同
  • connect
#include <sys/socket.h>
int connect(int sockfd, const struct sockaddr *servaddr, socklen_t addrlen);

注意这里 client端没有bind ..

TCP 如何进行flow control流量控制的?

TCP 使用 滑动窗口来进行流量控制..当一个新的连接建立时,连接双方都会有一个缓冲区来存储双方发送的数据. 并且会把窗口的大小发送给对方..当数据到达时.接收双方确认并且会把缓冲区所剩大小(窗口)发送给对方..对方通过查看接收到的窗口的值来改变发送速率.

xiyoulaoyuanjia commented 11 years ago

  1. 87的100次幂除以7的余数是多少（）

    A. 1
B. 2
C. 3
D. 4
答：D

这道题如果只有原文作者的一种答案,真心有点恶心...

(3^n)%7 依次为1，3，2，6，4，5 1.3 ..循环 这个...无语..

二: 简单题:

  • 进程与线程的区别:
  • 多线程有什么优点缺点.
  • 多进程有什么优点缺点,与 多线程相比较的区别?

进程可以看成是一个程序的执行实例.从内核来看它是担当分配系统资源的基本单位.

线程可以看成进程的一个执行流,它是cpu调度与分配的基本单位,它是比进程能更小独立运行的基本单位..一个进程 包括几个线程..

多线程与多进程都具有的优缺点是

  • 提高系统的响应时间.. 这个对于图像应用程序来说尤其有用.. 例如把耗时较长的放到一个单独的线程当中
  • 使多系统cpu能有效的得到利用...这里当多线程的数量少于cpu的时候操作系统可以保证多线程运行在不同的cpu中
  • 改善程序结构...把较长的程序可以利用多线程等技术更改为 较容易条例清楚的程序..

多线程与多进程相比较有如下不同:

  • 多线程与多进程相比较是一个非常节约的多任务..启动一个多进程需要 独立的地址空间..很多的表来维护代码段 数据段等 众多资源..但是线程可以共用地址段..共享大部分数据..
  • 多线程之间的切换也比多进程要快很多..一般来说要快上30倍以上,当然不同的环境可能一样..
  • 多线程之间的通信也比多进程的通信要方便的多..由于线程 可以共享进程中的大多数内容..所以通过共享的内容来通信要方便的多...而多进程由于彼此之间是相对独立的程序.通信就相比较而言要复杂的多..

多进程的 优点..:

  • 多进程由于彼此之间是相对独立的 这也就保证了程序之间的 健壮性..即一个程序崩溃不会导致另一个崩溃.. 多线程之间往往容易发生这样子的事情.
  • 多线程由于 需要访问公共的资源会导致一些 同步的问题..而多进程则不会出现这样的问题...
  • 迭代与递归的形式反转一个单链表