alibaba——研发/算法笔试题2

3、进程阻塞的原因不包括(A)

A、时间片切换

B、等待I/O

C、进程sleep

D、等待解锁

答:linux基础知识。

解析:只要理解进程的概念就OK。A

知识补充

进程是一个可并发执行的程序,在一个数据集合上的一次运行过程。它是系统进行资源分配和调度的一个独立单位。

进程的特征:动态性、并发性、独立性、异步性,系统为每一个进程设立一个进程控制块——PCB。

进程与程序的区别:1)、程序是进程的静态文本,进程是执行程序的动态过程;2)、一个进程可以执行一个或多个程序,几个进程可以同时执行一个程序;3)、程序可作为软件资源长期保存,进程只是一次执行过程,是暂时的;4)、进程是系统分配调度的独立单位,能与其他进程并发执行。

进程状态及其演变:进程执行的间断性,决定了进程可能具有多种状态。事实上,运行的进程可能具有就绪状态、执行状态、阻塞状态三种基本状态。

进程的三种基本状态演变图如下图所示:

alibaba——研发/算法笔试题2

当进程已分配到除CPU以外的所有必要资源时,它便处于就绪状态,一旦获得CPU,便立即执行。已获得CPU的进程进入执行状态。正在执行的进程,由于发生某个事件而暂时无法执行时,便放弃处理机而进入阻塞状态。由于执行的进程变为阻塞状态后,调度程序立即把处理机分配给另一个就绪进程;因此,阻塞进程的事件消失后,进程不会立即恢复到执行状态,而转变为就绪状态,重新等待处理机。

在实际系统中,进程还有其它几个状态。有的系统有时希望能人为地把进程挂起,使之处于静止状态,以便研究其执行情况或对它进行修改。下图示出了具有挂起状态的进程状态演变图。

alibaba——研发/算法笔试题2

进程控制块PCB:(Process Control Block)这是为使多个程序能并发执行而为每个程序所配置的一个数据结构,其中存放了用于描述该进程情况和控制进程运行所需的全部信息。


4、设只含根结点的二叉树高度为1,现有一颗高度为h(h>1)的二叉树上只有出度为0和出度为2的结点,则此二叉树中所包含的结点数至少为(B)个。

A、2^h-1

B、2h-1

C、2h

D、2h+1

答:数据结构基础知识。

解析:如果每个节点出度要么为0要么为2,那么也就是要么自己为叶子,要么自己拥有左右儿子。那么什么情况下节点最少呢?直接沿着一条路下去保持出度为2,直到高度达到h,那么此时节点总数:2h-1。故选B。

知识补充

二叉树是每个节点最多有两个子树的有序树。深度是对于二叉树整体来说的,二叉树的深度就是距离根节点最大的层数。结点指二叉树中一个个的点。

指父结点下面有几个孩子结点。度分为入度出度,一般都是对于单个结点来说的;入度 (in-degree) :以某顶点为弧头,终止于该顶点的弧的数目称为该顶点的入度。出度 (out-degree) :以某顶点为弧尾,起始于该顶点的弧的数目称为该顶点的出度。

前序:根结点第一个访问,然后访问左、右孩子;后序:根结点最后访问,开始先访问左、右孩子;中序:根结点第二个访问,最先访问左孩子,最后访问右孩子。

举例说明:如下图所示

alibaba——研发/算法笔试题2

图中的0、1、2、3、4、5、6就是结点;针对结点1,他下面有两个孩子3、4,所以说结点1的度为2;针对结点4,他下面一个孩子都没有,所以说结点4的度为0;前序序列:0134256,后序序列:3415620,中序序列:3140526。

下面给出数据结构中的入度和出度算法(C语言)

Status Get_Degree(ALGraph &G)//计算入度和出度
{ 
	int i;
	ArcNode *t;
	for(i=0; i<G.vexnum;i++)
	{
  		G.vertices[i].InDegree=0;
  		_______(G.vertices[i].OutDegree=0)_______;
 	}
 	for(i=0; _______(i<G.vexnum)_______;i++)
	{
  		t=G.vertices[i].firstarc;
  		if (t!=NULL)
		{
   			G.vertices[i].OutDegree++;
   			G.vertices[t->adjvex].InDegree++;
   			while (t->nextarc!= _______(NULL)_______) 
			{
    				t= t->nextarc;
    				G.vertices[i].OutDegree++;
    				G.vertices[t->adjvex].InDegree++;
   			}
  		}
 	}
 	return OK;
}//Get_Degree





上一篇:alibaba——研发/算法笔试题1


下一篇:NPOI自定义单元格RGB背景色