问答题在某二叉树上进行前序、中序遍历后发现该二叉树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质?为什么?【上海交通大学2003五(10分)】
问答题试设计一个C算法(或C程序)：用单链表作存储结构，以回车符为结束标志，输入一个任意长度的字符串；然后判断该字符串是否为“回文”(正向读和反向读时，串值相同的字符串称为“回文”)，输出信息“Yes”或“No”；最后删除字符串并释放全部空间。例如：若输入“ABCDl2321DCBA”，是回文，则输出“YeS”；若输入“ABCDl23DCBA”，不是回文，则输出“No”。要求：定义相关数据类型，不得使用数组(顺序表)作字符串的存诸结构和辅助存储空间。假定字符串的长度为n，试分析上述算法的时间复杂度。【华中科技大学2004五(10分)】
问答题由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序中所缺的语句。
#define MAX 100
typedef struct Node
{char info；struct Node*llink，*rlink；)TNODE；
char pred[MAX]，inod[MAX];
main(int argc，int**argv)
{TNODE*rootj
if(argcinfo=(1) ;
for((2) ；rposllink=restore(ppos+1，(4) ，k)；
ptr->rlink=restore((5) +k，rpos+l，n一1一k);
return ptr；
}
postorder(TNODE*ptr)
{if(ptr=NULL)return；
postorder(ptr->iiink)；
postorder(ptr一>rlink)；
printf(“％c”，ptr一>info);
}
【中科院计算所2000三(10分)】
问答题特殊矩阵和稀疏矩阵哪一种压缩存储后失去随机存取的功能?为什么? 【北京邮电大学2001三、1(5分)】
问答题二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部(注：向量d可视为循环表)，其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分二路插入。编写实现二路插入排序算法。【北京工业大学1998八(10分)】
问答题下列程序段search(a，n，k)在数组a的前n(n≥1)个元素中找出第k(1≤k≤n)小的值。这里假设数组a中各元素的值都不相同，请填上适当的语句使得整个程序完整。
define NAXN 100
int a[MAXN]，n，k；
int search(int a[]， int n， int k)
{intlow，high，i，j，m，t；
k--，low=0； j=high；
do(t=a[ltow]；i=low j=high；
do{while(i=a[j])i++；
if(i
问答题下列程序判断字符串s是否对称；对称则返回1，否则返回0；如f“abba”)返回1，f“abab”)返回0。 int f((1) ) {int i=0，j=0； while(8[j])(2) ； for(J一一； i
问答题线性表L=(a
1
，a
2
，…，a
n
)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是__________。【北方交通大学2001二、9】
问答题在二叉树中查找值为x的结点，试编写算法(用c语言)打印值为x的结点的所有祖先，假设值为x的结点不多于一个。【上海交通大学1998年】
问答题简要叙述B树(有些教材中称为B一树)与B+树的区别。【南京航空航天大学1999六(5分)】
问答题设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序?如果能，请列出其比较过程；如果不能，则说明原因。【北方交通大学1996五(10分)】
问答题设顺序表中的数据元素递增有序，编写一算法将元素X插人到顺序表的适当位置上，并保证该表的有序性。
问答题假定有k个关键字互为同义词，若用线性探测法将这k个关键字存入散列表中，至少需要进行多少次探测?【厦门大学2006四、2(25／3分)】
问答题在长度为n线性表中插入一个元素，采用顺序存储结构的复杂度为__________；采用链式存储结构的复杂度为__________ 。【北京理工大学2006十、2(1分)】
问答题n阶对称阵(aij)n×n，采用压缩存储放于一维数组F[m]中。从F[0]开始存储，给出矩阵的压缩存储方式及任一矩阵元素aij(O<=i，j<=n-1)的地址计算公式，并求算m。
问答题在二又树的前序遍历和中序遍历的递归算法中，最后一个递归调用语句在调用时所保留的参数有什么作用?如何清除最后这个递归语句?【北京邮电大学1994三(8分)】
问答题设计一非递归算法采用深度优先搜索对无向图进行遍历，并对算法中的无向图的存储结构予以简单说明。【大连理工大学2003二、1(45／3分)】【北京邮电大学1994十(15分)】
问答题倒排序文件的主要优点在于__________。【山东工业大学1995一、3(1分)】
问答题设一棵二叉树用二叉链表表示，求该树的高度。【南京航空航天大学2004二、2(12分)】【北京理工大学2000四3(4)】【北京轻工业学院1997一(15分)】
问答题假设二叉树采用链接存储结构进行存储，t指向根结点，s所指结点为任意一个给定的结点，编写一个求出从根结点到p所指结点之间路径的函数。