问答题名词解释：队列。【大连海事大学1996一、6(1分)】
问答题已知一棵二叉树按顺序方式存储在数组A[1，n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。【武汉大学2000年】
问答题已知一棵二叉树是以二叉链表的形式存储的，其结点结构说明如下： struct node{int data; ／／结点的数据场 struct node*left； ／／给出结点的左儿子的地址 struct node*right； ／／给出结点的右儿子的地址) 请在(1)、(2)二题的__________处进行填空，完成题目要求的功能。注意，每空只能填 一个语句，多填为0分。 (1)求出以T为根的二叉树或子树的结点个数。 int Size(struct node*T) {if(①)return 0 ； else—②一；} (2)求出以T为根的二叉树或子树的高度。注：高度定义为树的总的层次数。 int height(struct node*T) {if(T==NULL)⑤；else④；) 【上海交通大学2004三(10分)】
问答题设某二叉树结点结构为：TYPE bitreptr=^bnodetp；bnodetp=RECORD data：integer； 1child， rchild：bitreptr END；试编写算法，计算每层中结点data域数值大于50的结点个数，并输出这些结点的data域的数值和序号。【北京工业大学1998九(10分)】
问答题设有一个10阶对称矩阵A采用压缩存储方式(以行为主序存储：a
11
=1)，则a
85
的地址为__________。 【西安电子科技大学1999软件一、3(2分)】
问答题在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是__________。【厦门大学2002六、3(4分)】
问答题下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n个顶点V1，V2，…，Vn，用相邻矩阵A表示，边的权全是正数。请在下列画线处填上正确叙述。(1)若(Vi，Vj)是边，则A(i，j)的值等于__________，若(Vi，Vj)不是边，则A(i，j)的值是一个比任何边的权__________，矩阵的对角线元素全为0。(2)构造最小生成树过程中，若顶点Vi已包括进生成树，就把相邻矩阵的对角线元素A(i，i)置成__________，若(Vi，Vj)已包括进生成树，就把矩阵元素A(i，j)置成__________。(3)算法结束时，相邻矩阵中__________的元素指出最小生成树的__________。【山东工业大学1998二、4(6分)】
问答题在单链表、双向链表和单向循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删去?若可以，其时间复杂度各为多少? 【吉林大学2007二、1(3分)】
问答题已知连通图如下：(1)若从顶点B出发对该图进行遍历，在(1)的基础上分别给出本图的按深度优先搜索和按广度优先搜索的顶点序列；(2)写出按深度优先搜索的递归程序。【厦门大学200l三(12％分)】
问答题若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，则该树一共有__________个结点。【北京航空航天大学2006一、5(1分)】
问答题设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母 都在小写字母之前，并且同类字母之间的相对位置不变。(5分)例如，原有字符串为：AbcDEfghiJKlmn输出序列为：ADEJKbcfhilinn【华南理工大学2006三、1(5分)】
问答题阅读下列算法： void suan—fa(int n) {int i，j，k，s，x； for(s=0，i=0；i
问答题已知无向图采用邻接表存储方式，试写出删除边(i，j)的算法。【东南大学1999三(10分)】【北京邮电大学2006三(7分)】
问答题没有一个不带表头结点的单链表，表头指针为head。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针head指向原链表的最后一个结点。
问答题含9个叶子结点的3阶B一树中至少有多少个非叶子结点?含10个叶子结点的3阶B一树中至多有多少个非叶子结点?【东南大学2005一、1(5分)】【北京轻工业学院2000八(10分)】
问答题对于一个使用邻接表存储的有向图G，可以利用深度优先遍历方法，对该图中的所有顶点进行拓扑排序。其基本思想是：在遍历过程中，每访问一个顶点，就将其邻接到的顶点的入度减一，并对其未访问的、入度为0的邻接到的顶点进行递归。(1)给出完成上述功能的图的邻接表定义(结构)。(4分)(2)定义在算法中使用的全局辅助数组。(4分)(3)写出在遍历图的同时进行拓扑排序的算法。(10分)【东北大学1999五(1 8分)】【清华大学1997一(18分)】【中科院研究生院2003十一(15分)】
问答题任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有(m一1)个度为2，其余度为1。【西安电子科技大学2001计算机应用二、3(5分)】
问答题设有11个长度(即包含记录的个数)不同的初始归并段，它们所包含的记录个数分别为25，40，16，38，77，64，53，88，9，48，98。试根据它们做4路平衡归并，要求：(1)指出总的归并趟数；(3分)(2)构造最佳归并树；(8分)(3)根据最佳归并树计算每一趟及总的读记录数。(5分)【清华大学1997八(16分)】
问答题在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。编写一个算法完成下列功能：(1)建立有向图G的邻接表存储结构；(2)判断有向图G是否有根，若有，则打印出所有根结点的值。【东北大学2001五(15分)】【中国海洋大学2006九(15分)】
问答题设有算法：
void abc(Linklist＆H)
{／／链表无头结点；
r=H；p=r->next；
while(p)
{if(p一>datadata)P一>datar一>data；／／交换数据；
r=p；p=P一>next；
}
}／／abc
链表结点结构为(data，next)。