问答题不受待排序初始序列的影响，时间复杂度为O(N 2 )的排序算法是__________，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是__________。 【中国人民大学2001一、3(2分)】

问答题已知长度为12的表{Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)。(1)试按表中元素的次序依次插入一棵初始为空的二叉排序树，请画出插入之后的二叉排序树，并求在等概率情况下查找成功的平均查找长度。(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此表进行折半查找成功的平均查找长度。(3)按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。【中国矿业大学2000七(10分)】

问答题设树T采用孩子兄弟链表表示，编写程序，计算树T的度，并写出算法思想。【南京航空航天大学2005七(10分)】

问答题数组A[0．8，1．．10】的元素是6个字符组成的串，则存放A至少需要多少字节?A的第8列和第5行共占多少字节?若A按行优先方式存储，元素A[8，5]的起始地址与当A按列优先方式存储时的哪个元素的起始地址一致?【厦门大学2000五、3(14％／3分)】

问答题一棵高度为h的满m叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有m棵非空子树。如果按层次自顶向下，同一层自左向右，顺序从1开始对全部结点进行编号，试问：

问答题一最小最大堆(minmaxheap)是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小(或最大)。如图所示为一最小最大堆。(1)画出在上图中插入关键字为5的结点后的最小最大堆。(2)画出在上图中插入关键字为80的结点后的最小最大堆。(3)编写一算法实现最小最大堆的插入功能。假定最小最大堆存放在数组中，关键字为整数。(4)用C实现上述算法。【浙江大学1996八(26分)】

问答题数据的逻辑结构是指__________。【北京邮电大学2001二、l(2分)】

问答题设数组a[1．．50，1．．80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45，68]的存储地址为(1)；若以列序为主序顺序存储，则元素a[45，68]的存储地址为(2)。【华中理工大学2000一、5(2分)】

问答题若一棵二叉树中有24个叶结点，有28个仅有一个孩子的结点，则该二叉树中总共有多少个结点?【厦门大学2006二、1(20／3分)】

问答题有人说，采用折半查找法一定比采用顺序查找法的时间效率高，你认为如何？请说明你的理由。

问答题对于一个有序顺序表来说，折半查找是否任何时候都比顺序查找快?为什么?【上海交通大学2005三(6分)】

问答题请用类C或用类Pascal语言编写算法：键树，又称数字查找树。它是一棵度为≥2的树，树中的每个结点中不是包含一个或几个关键字，而是只含有组成关键字的符号。编写一个在键(trie)树T上查找关键字等于给定值KEY的记录的算法。若查找成功，返回指向该记录的指针；否则返回空指针。【上海大学2002七、2(10分)】

问答题已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是__________。【合肥工业大学2000三、3(2分)】

问答题设一棵二叉树的结点定义为structBinTreeNode{ElemTypedata；BinTreeNode*leftchild，*rightchild；)现采用输入广义表表示建立二叉树。具体规定如下：(1)树的根结点作为由子树构成的表的表名放在表的最前面。(2)每个结点的左子树和右子树用逗号隔开。若仅有右子树没有左子树，逗号不能省略。(3)在整个广义表表示输入的结尾加上一个特殊的符号(例如“#”)表示输入结束。例如，对于如右图所示的二叉树，其广义表表示为A(B(G))，E(G)，C(F)。此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母(假设以字母作为结点的值)，则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女(当k=1)或右子女(当k=2)链接到其双亲结点上。若遇到的是左括号“(”，则表明子表的开始，将k置为1；若遇到的是右括号“)”，则表明子表结束。若遇到的是逗号“，”，则表示以左子女为根的子树处理完毕，应接着处理以右子女为根的子树，将k置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下：MakeEmpty(s)置空栈Push(s，p)元素p进栈Pop(s)退栈Top(s)存取栈顶元素的函数下面给出了建立二叉树的算法，其中有5个语句缺失，请阅读此算法并把缺失的语句补上。(每空3分)VoidcreatBinTree(BinTreeNode*istreamins(1s)；／／把串1s定义为输入字符串流对象ins；charch;ins>>ch；／／从ins顺序读入一个字符while(ch!="#"){／／逐个字符处理，直到遇到.#.为止swich(ch){case"("：(1);k=1;break;case")"：pop(s);break；case","：(2);break;default：p=newBinTreeNode(3)；p一>leftchild=NULL；p一>rightchild=NULL；if(BT==NULL)(4);elseif(k==1)top(s)一>1eftchild=p；elsetop(s)一>rightchild=p；}(5)；}}【清华大学2001六(15分)】

问答题将下列由三棵树组成的森林转换为二叉树(只要求给出转换结果)。【南京航空航天大学1998一(10分)】

问答题已知非空二叉树采用顺序存储结构，结点的数据信息依次存放于一维数组BT[O．．n—1]中(假设每个结点的数据信息为一个非O整数；若数组元素值为0，则表示该元素对应的结点在二叉树中不存在)。请写一算法，生成该二叉树的二叉链表结构。

问答题广义表(O，(a)，(b，(c，d)f))的深度为__________。【电子科技大学2014一、2(1分)】

问答题设一棵二叉树T采用二叉链表表示，编写一个算法，判断T是否是完全二叉树。

问答题设有浮点数，x=25×(+9/16)，y=23×(-13/16)，阶码用4位(含1位符号位)补码表示，尾数用5位(含1位符号位)补码表示，求真值x/y=?要求写出完整的浮点运算步骤，并要求直接用补码加减交替法完成尾数除法运算。

问答题一线性表存储在带头结点的双向循环链表中，L为头指针。对如下算法： (1)说明该算法的功能。(2)在空缺处填写相应的语句。 void unknown (BNODETP*L) (p=L一>next；q=p一>next；r=q->next； while(q!=L) {while (p!=L) ＆＆ (p一>data>q一>data)p=p->prior； q一>prior一>next=r；(1) ； q一>next=p一>next；q一>prior=p； (2)；(3)；q=r；p=q一>prior； (4); } }【北京理工大学1999第二部分数据结构[7](8分)】