对于每一个已经扩展了的节点，AO*算法都有一个指针，指向该节点的后继节点中，耗散值大的那个连接符。

第1题：

第2题：

第3题：

某二叉树如图所示，若进行顺序存储（即用一维数组元素存储该二叉树中的节点且通过下标反映节点间的关系，例如，对于下标为i的节点，其左孩子的下标为2i、右孩子的下标为2i+1），则该数组的大小至少为 （请作答此空） ；若采用三叉链表存储该二叉树（各个节点包括节点的数据、父节点指针、左孩子指针、右孩子指针），则该链表的所有节点中空指针的数目为 （ ） 。

A.6
B.10
C.12
D.15

答案：D

解析：

采用顺序存储结构存储二叉树时，一般的二叉树也必须按照完全二叉树的形式存储，需要填上一些不存在的"虚节点"。题中二叉树的高度为4，需要的存储空间为24-1=15，如下：

可见，空指针的数目为8。

第4题：

当连接符全部为1－连接符时，局部图就是一个路径，选择一个耗散值最小的局部图扩展，与从OPEN表中选择一个f值最小的节点扩展是一致的。

第5题：

在搜索解图的过程中，若解图的耗散值记为k（n，N），则若n是一个外向连接符指向后继节点{n1，…，ni}，并设该连接符的耗散值为Cn，则k（n，N）＝（）

• A、Cn
• B、k（n1，N）+…+k（ni，N）
• C、0
• D、Cn+k（n1，N）+…+k（ni，N）

第6题：

在AO*算法中，已知h（n）函数对一个已知与或图中各节点的假想估值如下：h（n0）＝3，h（n1）＝2，h（n2）＝4，h（n3）＝4，h（n4）＝1，h（n5）＝1，h（n6）＝2，h（n7）＝h（n8）＝0（目标节点）。且k-连接符的耗散值为k。假设此时n5刚被扩展成n6、n7和n8三个节点。一个1－连接符指向n6，一个2－连接符指向n7和n8。下列说法正确的是（）

• A、n5的修正耗散值q=3，指针指向1－连接符。
• B、n5的修正耗散值q=2，指针指向2－连接符。
• C、n5的修正耗散值q=3，指针指向2－连接符。
• D、n5的修正耗散值q=2，指针指向1－连接符。

第7题：

下列关于Route-polic的描述中，正确的是（）？

• A、如果Route-polic中定义了一个以上的节点，各节点中至少应该有一个节点的匹配模式是permit
• B、在Route-polic的一个节点中，必须至少包含一个if-match子句
• C、在一个Route-polic中，不同节点之间的关系为或
• D、在Route-polic的同一节点中，不同if-match子句之间的关系为与

第8题：

DOM节点树上每一个节点都有子节点。

第9题：

第10题：

第11题：

第12题：

第13题：

第14题：

第15题：

在一般图搜索算法中，当对某一个节点n进行扩展时，n的后继节点可分为三类，请举例说明对这三类节点的不同的处理方法。

第16题：

关于极小极大搜索方法，下列说法正确的是（）

• A、当轮到我方走棋时，首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节点的评价函数值。
• B、然后从d-1层节点开始逆向计算。
• C、对于我方要走的极大节点取其子节点中的最大值为该节点的值
• D、对于对方要走的极小节点取其子节点中的最小值为该节点的值。
• E、一直到计算出根节点的值为止，获得根节点取值的那一分枝，即为所选择的最佳走步。

第17题：

在AO*算法中，已知h（n）函数对一个已知与或图中各节点的假想估值如下：h（n0）＝3，h（n1）＝2，h（n2）＝4，h（n3）＝4，h（n4）＝1，h（n5）＝1，h（n6）＝2，h（n7）＝h（n8）＝0（目标节点）。且k-连接符的耗散值为k。假设此时n5刚被扩展成n6、n7和n8三个节点。一个1－连接符指向n6，一个2－连接符指向n7和n8。则有关能解节点的说法正确的是（）

• A、n7和n8是能解节点，n5不是能解节点。
• B、n7和n8是不能解节点，n5是能解节点。
• C、n7、n8和n5都是能解节点。
• D、n7、n8和n5都是不能解节点。

第18题：

单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个节点。

第19题：

要想删除1个链表中的节点，必须的操作包括：（）

• A、判断该节点是否是头节点
• B、删除该节点
• C、将前1节点的指针指向被删除节点的后1节点
• D、将被删除节点的指针设为空

第20题：

第21题：

第22题：

第23题：