问答题
问答题请回答下列关于堆(Heap)的一些问题。【清华大学2000五(12分)】
问答题若按层次顺序将一棵有n个结点的完全二叉树的所有结点从1到n编号，那么结点i没有右兄弟的条件为__________。【北京工业大学2005二、2(3分)】
问答题已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。(1)画出可利用空间表的初始状态。(2)画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。(3)画出在回收3个占用块之后可利用空间表的状态。【清华大学1998三(15分)】【同济大学1999】
问答题在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：(7，10，10，21，30，42，42，42，51，70)将变为(7，10，21，30，42，51，70)。【北京工业大学1996年】
问答题设二叉树结点结构为：(1eR，data，bf，right)。定义二叉树结点的平衡因子bf(T)=h
L
一h
R
，写一递归算法确定二又树tree中各结点的平衡因子bf,同时返回二叉树tree中非叶子结点的个数。【东南大学2005三(10分)】
问答题希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法，试举例说明。
问答题我们知道，对于n个元素组成的线性表进行快速排序时，所需进行的比较次数与这n个元素的初始排序有关。问：
问答题以下程序的功能是把一个输入字符串倒序输出，请找出并改正其中的错误。 void reverse(char*s){ int len=strlen(S)； char*dest=new char[1en]； int i=0 ; while(1en-一!=0){ } printf(…)； return 0； }【北京大学2008三(10分)】
问答题以三元组表存储的稀疏矩阵A、B非零元个数分别为m和n。试用类Pascal语言编写时间复杂度为O(m+n)的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。【北京工业大学1997三(10分)】
问答题设双向循环链表中结点的数据域、前驱和后继指针域分别为data、pre和next，试写出在指针P所指结点之前插入一S结点的C语言描述语句。【北京科技大学2001一、3(2分)】
问答题一个n阶矩阵A[0…n-1，0…n-1]采用一维数组s[0…n*n-1]按行序为主序，存放其上三角各元素，编写一个算法求出S[k]在A[i][j]中的位置和A[i][j]在S[k]中的位置。
问答题编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：它们已用val域链接成循环链表。非零元的结点形式也同上，每一行(列)的非零元由right(down)域把它们链接成循环链表，该行(列)的表头结点即为该行(列)循环链表的表头。【上海大学1998五(16分)】
问答题带头结点的双循环链表L为空表的条件是：__________。【北京理工大学2000二、1(2分)】【青岛大学2002三、1(2分)】
问答题将算术表达式((a+b)+c
*
(d+e)+f)
*
(g+h)转化为二叉树。【天津大学2003一、3(8分)】【东南大学2003二(7分)】【东北大学2000三、1(4分)】≠
问答题设散列函数H(k)=k mod 7，散列表的地址空间为0～6，对关键字序列{32，13，49，18，22，38，21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。【西安电子科技大学1999计算机应用一、5(5分)】
问答题一棵左子树为空的二又树在先序线索化后，其中的空链域的个数为__________。【厦门大学2002六、1(4分)】
问答题将一组数据元素按哈希函数H(key)散列到哈希表HT(0：m)中，用线性探测法处理冲突H(key)+1，H(key)+2，…，H(key)一1)，假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。【北京邮电大学2001五、2(10分)】
问答题对于一个具有n个结点的二叉树，当它为一棵(1)二叉树时具有最小高度，当它为一棵(2)时，具有最大高度。【哈尔滨工业大学2001一、3(2分)】
问答题设输入文件保存以下记录：14，22，7，24，15，16，11，100，10，9，20，12，90，17。现采用置换-选择方法生产初始归并段，并假设内存工作区可同时容纳5个记录，请画出选择的过程。