B

[解析] 在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征。
   本题主要考查双向链表的插入算法中的指针的变化过程。虽然4个选项中的语句相同，但顺序不同，根据双向链表的结构特点可知选项B的操作顺序是正确的，其他3个选项的指针修改顺序不能完成在^*p结点之后插入结点^*q的操作。

A

[解析] 在顺序表中删除元素需要移动较多元素，而在单链表上执行同样的操作不需要移动元素。

A

[解析] 利用栈底位置不变的特性，可让两个顺序栈共享一个一维数据空间，以互补余缺，实现方法是：将两个栈的栈底位置分别设在存储空间的两端，让它们的栈顶各自向中间延伸。这样，两个栈的空间就可以相互调节，只有在整个存储空间被占满时才发生上溢，这样一来产生上溢的概率要小得多。

B

[解析] 出队1个元素后，front=(front+1)%MAXQSIZE，front的值是4；入队两个元素后，rear=(rear+2)%MAXQSIZE，rear的值是2。

B

[解析] 利用逐点插入法建立二叉排序树是从空树开始，通过查找，将每个结点作为一个叶子插入。按题目中数据的输入次序建立的二叉排序树如下图所示，查找元素30的比较次数为5次。
   

C

[解析] 将二叉树的性质4推广到完全三叉树即可得出正确答案。
   含有n个结点的完全三叉树的高度是。

C

[解析] 在无向图中，如果从一个顶点v_i到另一个顶点v_j(i≠j)有路径，则称顶点v_i和v_j是连通的。如果图中任意两顶点都是连通的，则称该图是连通图。所以具有n个顶点的连通无向图至少有n-1条边。
   具有n个顶点的连通无向图至少有n-1条边，具有n个顶点的强连通有向图至少有n条弧。

C

[解析] 按照散列函数h(key)=key%7和线性探测方法解决冲突，将线性表(38，25，74，63，52，48)散列存储在散列表A[0..6]中，如下图所示。
   那么，
   

B

[解析] 长度为12的折半查找判定树中有13个外结点，如下图所示。
   对于长度为12的有序表，折半查找失败时的平均查找长度为：
   ASL=(4×3+5×10)/13=62/13
   

B

[解析] 选项A快速排序每趟趟排序后，轴值将在其最终位置上；选项C堆排序每趟排序后，堆顶记录将在其最终位置上；选项D起泡排序每趟排序后，最大值(或最小值)记录将在其最终位置上。只有选项B希尔排序不具备这个特点。

D

[解析] 小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于的结点上。

C

[解析] 机器字长是计算机内部一次可以处理的二进制数的位数。
   机器字长是指参与运算的数的基本位数，它是由加法器、寄存器的位数决定的，所以机器字长一般等于内部寄存器的大小。字长标志着精度，字长越长，计算的精度就越高。

D

[解析] 5位二进制定点小数，用补码表示时，最小负数表示为1.0000。
   若真值为纯小数，它的补码形式为X_s．X₁X₂…X_n，其中X_s表示符号位。当X_s=1，X₁～X_n均等于0时，X为最小负数(绝对值最大的负数)，其真值等于-1。
   选项A为正数，选项B为反码表示时的最小负数，选项C为原码表示时的最小负数。

C

[解析] 变形补码即双符号位补码，所以并不可以避免溢出。定点数和浮点数运算都可能产生溢出，但溢出判断有区别。两个正数相加时并不一定产生溢出，只有当相加之后的结果超过数的表示范围才产生溢出。
   选项B和C完全相反，所以可以确定其中有一个是正确的。

B

[解析] 由于Cache存放的是主存活跃块的副本，所以不能认为总容量为两个层次容量的简单相加。
   从CPU的角度来看，n种不同的存储器(M₁～M_n)在逻辑上是一个整体。其中：M₁速度最快、容量最小、位价格最高；M_n速度最慢、容量最大、位价格最低。整个存储系统具有接近于M₁的速度，相等或接近M_n的容量，接近于M_n的位价格。
   A为干扰项，容易误选，需注意。

B

[解析] 命中率=4800/(4800+200)=0.96，平均访问时间=0.96×10+(1-0.96)×50=11.6ns，效率=10/11.6=0.862。
   命中率H定义为CPU产生的逻辑地址能在M₁中访问到的概率。在一个程序执行期间，设N₁为访问M₁的命中次数，N₂为访问M₂的次数。
   
   两级存储层次的等效访问时间T_A根据主存的启动时间有：
   假设Cache访问和主存访问是同时启动的，T_A=H×T_A1+(1-H)×T_A2
   假设Cache不命中时才启动主存，T_A=H×T_A1+(1-H)×(T_A1+T_A2)=T_A1+(1-H)×T_A2
   存储层次的访问效率
   先求出命中率，接着求出平均访问时间，最后求出Cache-主存系统的效率。

C

[解析] 对于大多数计算任务来说，RISC机编写的程序会比CISC机编写的程序更长，这是因为RISC的指令都比较简单，CSIC中的一条复杂指令所完成的功能在RISC中可能要用几条指令才能实现，对于同一个源程序，显然RISC的指令条数要比CISC的多。
   CISC和RISC的区别见下表。

表
	CISC	RISC
指令系统	复杂，庞大	简单，精简
指令数目	一般大于200条	一般小于100条
指令字长	不固定	等长
寻址方式	一般大于4	一般小于4
可访存指令	不加限制	只有LOAD/STORE指令
各种指令执行时间	相差较大	绝大多数在一个周期内完成
通用寄存器数量	较少	多
控制方式	绝大多数为微程序控制	绝大多数为硬布线控制

   此题很容易选错，主要是一看到RISC，往往想到指令数目少，但这里是指完成某一个计算任务的指令条数，而不是指令系统中的指令数目。

B

[解析] 微程序存放在只读的控制存储器中。
   微程序是由微指令组成的，用于描述机器指令，微程序实际上是机器指令的实时解释器，是由计算机的设计者事先编制好并存放在控制存储器中的，一般不提供给用户。对微程序控制的计算机涉及两个层次：一个是机器语言或汇编语言程序员所看到的传统机器层，包括：机器指令、工作程序和主存储器；另一个是机器设计者看到的微程序层，包括：微指令、微程序和控制存储器。

D

[解析] 立即寻址方式就可以在取指周期从内存取到操作数；在直接映射方式下，一旦发生块冲突是不需要替换策略的；动态存储器的刷新是与读写操作没有关系的。
   有关叙述与主存相关，但不局限于主存。
   首先确定各个命题的正确性，然后再在各个选项中选择。

C

[解析] 时钟周期为主频的倒数。对于CPU主频为1.04GHz的5级指令流水线，CPU执行100条指令的时间为，实际吞吐率为1.0×10⁹条指令/秒。
   流水线的实际吞吐率TP一般明显低于最大吞吐率TP_max。设一m段流水线的各段经过时间均为Δt₀，则需要T₀=mΔt₀的流水建立时间，之后每隔Δt₀就可流出一条指令，完成n个任务的解释共需时间T=mΔt₀+(n-1)Δt₀，流水线的实际吞吐率为
   

B

[解析] RAID1称为镜像磁盘阵列，数据盘和检测盘的数量是1:1的关系，所以磁盘利用率为50%。
   RAID可以分为6个级别，即RAID0～RAID5，如下表所列。在RAID1～RAID5的几种方案中，不论何时有磁盘损坏，都可以随时拔出损坏的磁盘再插入好的磁盘(需要硬件上的热插拔支持)，数据不会受损，失效盘的内容可以很快地重建，重建的工作由RAID硬件或RAID软件来完成。

表
RAID级别	名称	数据 磁盘数	可正常工作的 最多失效磁盘数	检测 磁盘数
RAID0	无冗余无校验的磁盘阵列	8	0	0
RAID1	镜像磁盘阵列	8	1	8
RAID2	纠错海明码磁盘阵列	8	1	4
RAID3	位交叉奇偶校验的磁盘阵列	8	1	1
RAID4	块交叉奇偶校验的磁盘阵列	8	1	1
RAID5	无独立校验盘的奇偶校验磁盘阵列	8	1	1

C

[解析] 顺序存储存储器连续读出4个字需要4个存储周期，而交叉存储存储器连续读出4个字，由于采用分时启动的方法，只需要一个存储周期加上三个总线传输周期的时间。现字长为64位，交叉存储器连续读出4个字的信息总量q=64位×4=256位，交叉存储器连续读出4个字所需的时间t=T+(4-1)τ=200ns+3×50ns=350ns=3.5×10^-7s，所以交叉存储器的带宽W=q/t=256÷(3.5×10^-7)=73×10⁷(位/秒)。
   多模块交叉存储器是线性编址的，地址在各模块中有两种安排方式，分别是高位交叉编址(顺序方式)和低位交叉编址(交叉方式)。
   高位交叉编址的多模块存储器用地址码的高位区分存储模块，地址码的低位选择存储单元。低位交叉编址的多模块存储器用地址码的低位区分存储模块，地址码的高位选择存储单元。在低位交叉存储器中，连续的地址分布在相邻的模块中，而同一模块内的地址都是不连续的。这种存储器采用分时启动的方法，可以在不改变每个模块存取周期的前提下，提高整个主存的速度。
   题干中的存储器容量的大小对解题没有影响。

B

[解析] 本题考查操作系统的接口，操作系统有两种接口，命令输入和系统调用，而命令输入又可以分为命令行和图形用户界面。命令行是在终端或命令输入窗口中输入操作和控制计算机的规定的命令，既可以一条一条输入，也可以组织成一批命令，逐条自动执行，称为批处理命令。图形用户接口是我们熟知的图标和菜单形式。系统调用是我们编写程序过程中，需要计算机所做的操作，一般要按固定格式来调用。

B

[解析] 本题考查交互式操作系统的调度设计准则。在交互式系统中，调度的准则主要是提高处理机的利用率，公平调度，减少用户响应时间，满足用户的习惯操作等，吞吐量在交互式系统中并不是一个调度的重要指标，而是在批处理作业调度时才需要考虑的一个指标。

C

[解析] 本题考查死锁解除的各种方法。在死锁解除的各种方法中，代价最小的是剥夺死锁进程的资源，待系统缓解了再恢复死锁进程的运行。其次是将死锁的进程还原，重新申请分配资源，但是并不是所有进程都可以还原，这需要程序员在编程时进行配合。终止死锁的进程要付出一定的代价，至少需要重新开始运行死锁的进程，前期工作变得无效。最极端的是重启系统，代价最大，要尽量避免。

B

[解析] 本题主要考查关于进程和线程之间资源共享的知识点。在引入线程的操作系统中，线程是进程中的一个实体，是系统独立调度和分派的基本单位。但是线程自己基本上不拥有系统资源，所以它不是资源分配的基本单位，它只拥有一部分在运行中必不可少的与处理机相关的资源，如线程状态、寄存器上下文和栈等，它同样有就绪、阻塞和执行三种基本状态。它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程i同一个进程中的多个线程之间可以并发执行。内核线程由操作系统根据内部需求进行创建和撤销，通过系统调用为用户所用。内核线程依赖于操作系统内核的运行，因此操作系统知道内核线程的存在。内核线程的运行主要完成操作系统内核服务的操作，当一个线程发起系统调用而阻塞时，不会影响其他线程的运行。内核线程与进程一起获得相同的时间配额，所以，用户进程多调用内核线程会获得更多的处理机时间，缺点是线程功能不能由用户随心所欲地编写。

A

[解析] 本题考查cache与页式存储管理结合下的时间计算。根据题意，页式寻址方式的过程是这样的，当执行到一个逻辑地址时，MMU首先将页号分离，将得到的页号与cache中的32个页表项比较(同时进行)，若页表项命中，则取出页表项与页内地址相加，形成指令或数据的物理地址，花费5ns，据此地址，然后到内存中取得对应的指令或数据，送到CPU中执行或计算。若不能在cache命中，那么CPU会启动cache更新程序，将新的页表项从内存复制到cache，花费100ns，然后，重复上述地址转换过程，又花去5ns，得到物理地址，再去内存取指令或数据。根据题意，要求得到页框号，也就是物理地址的过程小于20ns，那么设cache的命中率为x，列关系式：
   5*x+(1-x)*(5+100)=20
   解得x为85%。因此，装入cache的页表项应大于1000*85%=850项，这样可以保证获得页框号的时间小于20ns。
   本题若问，一个指令双字的执行时间是多少时，需要考虑的事情就比较复杂。例如系统的字长是否是32位，32位的系统执行一个双字的时间是1次寻址，16位系统就需要2次寻址。8位系统的就需要4次寻址。另外，采用什么内存管理机制，页式和段式都是执行1次指令寻址需要访问内存2次，段页式需要3次。还要看cache的容量多大，指令是否在cache中等，所以，内存管理中寻址时间的计算与CPU结构和cache的运行模式息息相关，考生应结合计算机组成原理，妥善解决此类问题。

B

[解析] 分页是由操作系统自动完成的，一个操作系统一旦设计完成，其存储管理系统的结构就已经确定，分页还是分段，页面大小等在设计操作系统的过程中已经确定，当一个程序被创建为进程，并分配资源，其页面的大小自动分割完成，对用户是透明的，对编译程序和链接装配程序透明(在相同的系统里)。只有操作系统可以感知页面的存在，在内存管理过程中，操作系统要为用户进程分配内存，回收内存。所以操作系统是页面最直接的接触者，它将页面从计算机系统中到用户(包括程序员)进行了隔离。

A

[解析] 多级索引的逻辑并不复杂，二级间接索引表最多有256张，但是并没有用满。只用了255张，而且第255张中也没有全部用足256条表项。计算时加以仔细小心，一般不会有太多变化，但是对多级索引的方法一定要掌握。
   (1)直接索引为8*1K=8K，一级间接索引为(1K/4B)*1K=256K；
   二级间接索引为(1K/4B)*(1K/4B)*1K=65536K。
   (2)最大的文件将所有存储块占用，则需要65536K+256K+8K=65800K。

B

[解析] 本题考查考生对最短寻道时间优先算法和电梯算法的理解。最短寻道时间优先算法(SSTF)：96→75→73→120→126→184→25→12共计306道。电梯算法，前一次在90，当前在96，表示移动方向为磁道增大方向，故：96→120→126→184→75→73→25→12共计260道。计算时注意磁头的当前位置和运行方向。

B

[解析] 文件的物理结构中，主要使用的是连续结构、链接结构和索引结构(Hash结构实际上与索引结构类似)。在索引结构的文件中，必须要用专门的存储块来存放索引指针，即表示文件内容存放的地址。所以，当访问该文件时，必须首先去读取该文件的索引表，才能知道相应的逻辑文件块在外存上的存放地址。逻辑文件块与物理文件块是一一对应关系，不能在一个记录中存放多个地址。而索引表中只存放地址指针，不存放文件内容。对于单一索引结构，不像混合索引中存在直接索引指针，它只记录直接指向索引表的地址，所以不会有文件首块的地址出现。其他参数在文件控制块中均为必要的信息，对索引结构也适用。

A

[解析] 设备控制的数据结构中，系统设备表(SDT)在整个操作系统中只有一张，记录了系统中所有的外部设备。经系统设备表找到需使用的外部设备，则数据结构指针指向设备控制表(DCT)，这个数据表每个设备一张，记录了设备的特性和状态。每个设备有可能有不止一个控制器，所以从设备控制表会指向多张(至少一张)控制器控制表(COCT)，里面存放了控制器的控制参数，如果该设备是通道的话，则会指向多张通道控制表(CHCT)。

A

[解析] 本题考查OSI模型的层次关系，在协议的控制下，两个对等实体间的通信使得本层能够向上一层提供服务，同时要实现本层协议，还需要使用下层所提供的服务。本层的服务用户只能看见服务而无法看见下面的协议。下层的协议对上层的服务用户是透明的。也就是下一层要为上一层提供服务，并为上一层数据进行封装，因此答案为A，这里选项B和C的说法正好相反，应该是第N层将从第N+1层接收的信息增加了一个头，第N+1层利用第N层提供的服务。

A

[解析] 本题考查电路交换、分组交换、报文交换的特点和优缺点，主要有两种考查方式：一、直接考查某一种(或多种)交换方式的特点，是非选择判断题目；二、给定应用背景，交换方式的选择问题，这种方式比较灵活，间接性考查三种交换的优缺点，难度大。这里是针对第一种考查，电路交换是面向连接的，一旦连接建立，数据便可以通过连接好的物理通路到达接收端，因此传输时延小；由电路交换面向连接的特性，可知传送的分组必定是按序到达的；但在电路交换中，通信双方始终独自占用带宽，线路利用率很低，因此答案是A。

B

[解析] 本题考查滑动窗口的机制，发送方可连续发送k帧而无需对方应答，但需要将已发出但尚未收到确认的帧保存在发送窗口中，以备由于出错或丢失而准备重发。接收方按正确的次序接受和递交数据帧，并返回确认信息。接收方可能因为一帧出错，不能正确接受并递交主机，对后面连续发送来的n帧均丢失，这就是累积确认的概念。本题收到了2号帧的确认后，即0，1，2号帧已经正确接收，因此窗口向右移动3个帧，目前已经发送了3号帧，因此可连续发送的帧数是窗口大小一已经发送的帧数，即4-1=3，答案是B。
   在滑动窗口协议中，每一个要发送的帧都包含一个序号，范围是从0到某个最大值，最大值通常是2ⁿ-1，n为帧序号的长度。滑动窗口协议的要点是，任何时刻发送进程要维护一组帧序号，对应于一组已经发送但尚未被确认的帧，这些帧称为落在发送窗口内；类似地，接收进程也要维护一组帧序号，对应于一组允许接收的帧，这些帧称为落在接收窗口内。
   发送窗口中的序号代表已发送但尚未确认的帧，其中窗口下沿代表最早发送但至今尚未确认的帧。当发送窗口尚未达到最大值时，可以从网络层接收一个新的分组，然后将窗口上沿加1，并将新的上沿序号分配给新的帧；当收到对窗口下沿帧的确认时，窗口下沿加1。由于每一个帧都有可能传输出错，所以发送窗口中的帧都必须保留在缓冲区里以备重传，直至收到确认为止。当发送窗口达到最大值时，停止从网络层接收数据，直到有一个缓冲区空出来为止。
   接收窗口中的序号代表允许接收的帧，任何落在窗口外的帧都被丢弃，落在窗口内的帧存放到缓冲区里。当收到窗口下沿帧时，将其交给网络层，并产生一个确认，然后窗口整体向前移动一个位置。和发送窗口不同，接收窗口的大小是不变的，总是保持初始时的大小。接收窗口大小为1，意味着数据链路层只能顺序接收数据，当接收窗口大于1时不是这样，但无论如何，数据链路层必须按顺序将数据递交给网络层。

B

[解析] 本题考查IP分组分片原理和传输机制，IP分组可以被路径中的路由器分片，并在目的主机进行重组。当路由器准备将IP分组发送到网络上，而该网络又无法将整个分组一次发送时，路由器必须将该IP分组分成小块(亦即分组片)，使其长度能满足这一网络对数据分组的限制。IP分组可以独立地通过各个路径发送，使得分片后的IP分组直至到达目的地主机才可能汇集到一起，并且甚至不一定以原先的次序到达。这样，所有进行接收的主机都要求支持重组能力，因此IP分组可以在主机和路由器进行分片，但重组只能在目标主机上完成，答案是B。

C

[解析] 本题考查层次路由与OSPF路由协议，如果将区域看成一个节点，则OSPF是以主干区域(area 0.0.0.0)为顶点，其他区域为终端的星形拓扑结构。标准区域可以接收链路更新信息和路由总结。存根区域是不接受自治系统以外的路由信息的区域。如果需要自治系统以外的路由，它使用默认路由0.0.0.0。完全存根区域不接受外部自治系统的路由以及自治系统内其他区域的路由总结，需要发送到区域外的报文则使用默认路由0.0.0.0。不完全存根区域类似于存根区域，但是允许接收以LSAType7发送的外部路由信息，并且要把LSAType7转换成LSAType5。因此答案是C。

A

[解析] 本题考查默认路由的配置，路由器还可采用默认路由以减少路由表所占用的空间和搜索路由表所用的时间。这种转发方式在一个网络只有很少的对外连接时是很有用的。本题中主机地址是一个标准的A类地址，其网络地址为11.0.0.0。选项Ⅰ的网络地址为11.0.0.0，选项Ⅱ的网络地址为11.0.0.0，选项Ⅲ的网络地址为12.0.0.0，选项Ⅳ的网络地址为13.0.0.0，因此和主机在同一个网络是选项Ⅰ和Ⅱ，因此答案为A。

B

[解析] 本题考查交换机中地址映射表的原理，主要与路由器的路由表进行区分，路由表可以由人为配置静态路由，也可以通过动态协议建立，而对于交换机，映射表只能在数据转发中进行动态学习建立，并且每个表项都有定时器，具体是收到一帧后先进行自学习。查找转发表中与收到帧的源地址有无相匹配的项目。如没有，就在转发表中增加一个项目(源地址、进入的接口和时间)。如有，则把原有的项目进行更新，因此答案为B。

D

[解析] 本题考查FTP协议的工作原理，首先服务器打开熟知端口(端口号为21)，使客户进程能够连接上，并等待客户进程发出连接请求。客户端首先建立控制连接，控制连接在整个会话期间一直保持打开，FTP客户发出的传送请求通过控制连接发送给服务器端的控制进程，但控制连接不用来传送文件。然后下载数据的时候建立数据连接，这里实际用于传输文件的旧式是“数据连接”。服务器端的控制进程在接收到FTP客户发送来的文件传输请求后就创建“数据传送进程”和“数据连接”，用来连接客户端和服务器端的数据传送进程。数据传送进程实际完成文件的传送，在传送完毕后关闭“数据传送连接”并结束运行。可见，本题中客户端建立TCP连接和断开TCP连接的次数都是2次，因此答案是D。

关键路径：v₁  v₂  v₅  v₇；v₁  v₄  v₅ v₇。见表1。

表1
事件	V1	V2	V3	V4	V5	V6	V7
最早发生时间	0	3	2	6	7	5	10
最晚发生时间	0	3	3	6	7	6	10

　 关键活动：a₁ a₂ a₄ a₈ a₉，见表2。

表2
活动	a1	a2	a3	a4	a5	a6	a7	a8	a9	a10
最早开始时间	0	0	0	3	3	2	2	6	7	5
最晚开始时间	0	0	1	3	4	5	3	6	7	6
时间余量	0	0	1	0	1	3	1	0	0	1

[解析] AOE网中从源点到终点的最大路径长度(这里的路径长度是指该路径上的各个活动所需时间之和)的路径称为关键路径。关键路径长度是整个工程所需的最短工期。关键路径上的活动称为关键活动。要缩短整个工期，必须加快关键活动的进度。
   寻找关键活动时所用到的几个参量的定义。
   假设第i条弧为＜j，k＞，dut(＜j，k＞)为弧＜j，k＞上的权值。
   (1)事件的最早发生时间ve[k]=从源点到顶点悬的最长路径长度。
   ve(源点)=0；
   ve(k)=Max{ve(j)+dut(＜j，k＞)}
   (2)事件的最迟发生时间v1[j]=从顶点j到汇点的最短路径长度。
   vl(汇点)=ve(汇点)；
   vl(j)=Min{vl(k)-dut(＜j，k＞)}
   (3)活动i的最早开始时间e(i)=ve(j)。
   (4)活动i的最晚开始时间l(i)=vl(k)-dut(＜j，k＞)。
   e[i]=l[i]的活动就是关键活动，关键活动所在的路径就是关键路径。

   int found=FALSE;
   Bitree*Find_Near_Ancient(Bitree T, Bitree p, Bitree q) {
                                                    //求二叉树T中结点p和q的最近共同祖先
       Bitree pathp[100], pathq[100];               //设立两个辅助数组暂存从根到p，q的路径
       Findpath(T, p, pathp, 0);
       found=FALSE;
       Findpath(T, q, pathq, 0);                    //求从根到p，q的路径放在pathp和pathq中
       for(i=0; pathp[i]= =pathq[i]&&pathp[i]; i++) ;
                                                    //查找两条路径上最后一个相同结点
       return pathp[--i];
   }
   void Findpath(Bitree T, Bitree p, Bitree path[], int i) { //求从T到P路径的递归算法
     if(T= =p)  {
       found=TRUE;                                  //找到
       return;
     }
     path[i]=T;                                     //当前结点存入路径
     if(T-＞　lchild)
         Findpath(T-＞　lchild, p, path, i+1);      //在左子树中继续寻找
     if(T-＞　rchild && ! found)
         Findpath(T-＞　rchild, p, path, i+1);      //在右子树中继续寻找
     if(! found)
         path[i]=NULL;                              //回溯
   }

[解析] 本题也可叙述为求*p和*q两个结点的最小子树。
   遍历访问到*p时，将*p结点的祖先保存到数组pathp中，再遍历访问到*q时，将*q结点的祖先保存到数组pathq中，将数组pathp与数组pathq的结点依次(从0开始)比较，找到最近的共同祖先。