问答题(1)试找出满足下列条件的二叉树：1)先序序列与后序序列相同2)中序序列与后序序列相同3)先序序列与中序序列相同4)中序序列与层次遍历序列相同(2)已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG和DEBHIFGCA，画出这棵二叉树。【东北大学1999六(4分)】【东南大学2000一、4(6分)】
问答题已知一带头结点的递增有序单链表，请在原结点上将其倒序。【南京航空航天大学2004二、4(12分)】
问答题循环队列是队列的一种__________存储结构。【南京理工大学2005二、10(1分)】
问答题在进行入栈运算时应先判别栈是否(1)；在进行出栈运算时应先判别栈是否(2)；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为(3)。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的(4)分别设在内存空间的两端，这样只有当 (5)时才产生溢出。【山东工业大学1 994一、1(5分)】
问答题证明：置换一选择排序法产生的初始归并段的长度至少为m(m是所用缓冲区的长度)。【西安电子科技大学1996二、5(5分)】
问答题下列程序是归并排序的递归算法。【北京交通大学2006七、1(6分)】
#define maxsize 1000
#define 13．13．10
#include
int r[rm+1]，r2[rm+1]；／／r[0]闲置
int a[10]={17，1，23，77，51，1_3，3 9，11，19，1 5)；
void merge(int r[]， int low， int m， int high， int r2[] )
{int i， j，k； k：i；10w； j=m+1；
while(im)
while(j<=high)
{r2[k]=r[j]；j++；k++；}
else
while(i<=m)
{r2[k]=r[i]； i++；k++j}
}
void mergesort(int r[]， int r1[]， int：low， int high)
{int：m，r2 Inn+1]；
if(low==high)
r1[low]=r[1 ow]；
el8e
{ (2) ;
mergesort(r，r2，low，m)；
mergesort( (3) )；
merge(2：2，low，m，high，r1)；
}
}
main()
{int i；
for(i=0；i<=9;i++)
r[i+1];a[i]；
mergesort(r，r2，1，3．0)；
for(i=1；i<=10；i++)
print：f(“ ％d”，r2[i]);
printf(“＼n”)；
}
问答题一元稀疏多项式以循环单链表按降幂排列，结点有三个域，系数域coef，指数域exp和指针域next。现对链表求一阶导数，链表的头指针为ha，头结点的exp域为一1。【南京理工大学2000年】
问答题一个数据结构在计算机中的__________称为存储结构。【华中理工大学2000一、1(1分)】
问答题一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标为“的结点的第f个孩子的下标以及结点下标为1，的结点的父母结点的下标。【北京邮电大学2001四、4(5分)】
问答题若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是__________。【西 安电子科技大学2001软件一、3(2分)】【厦门大学2002六、2(4分)】【中南大学2005二、8(2分)】
问答题两个栈共享空间时栈满的条件__________。【中山大学1998一、3(1分)】【北京邮电大学2006一、3(2分)】
问答题已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用二分法查找90时，需__________次查找成功，查47时，需__________次查找成功，查100时，需__________次才能确定不成功。【南京理工大学2000二、7(4．5分)】
问答题按图的广度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点V
i
到顶点V
j
的路径(i≠j)。【中山大学1997五(10分)】
问答题已知深度为h的二叉树采用顺序存储结构_已存放于数组BT[1．2
h
一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(1ehild，data，rehild)，根结点所在链结点的指针由T给出。【北京航空航天大学2007年】
问答题如果具有n个顶点的图是一个环，则它有__________棵生成树。【中南大学2005二、9(2分)】
问答题设散列表为HT[0.12]即表的大小为m=13。现采用链地址法解决冲突。若插入的关键字序列为{2，8，31，20，19，18，53，27}。
问答题给定权W1，W2，…，Wm。说明怎样来构造一个具有最小的加权路径长度的k叉树。试对于权1，4，9，16，25，36，49，64，8l，100来构造最优的三叉树，并给出其最小加权路径长度。【北方交通大学1994四(12分)】
问答题对n个元素的序列进行起泡排序时，最少的比较次数是__________。【东华大学2003一、3(1分)】
问答题直接插入排序用监视哨的作用是__________。【南京理工大学2001二、8(2分)】
问答题假设一个单循环链表，其结点含有三个域pre、data、link。其中data为数据域；pre为指针域，它的值为空指针(NIL)；link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。 【西安电子科技大学1999软件五(10分)】