(1)t->rchild!=null (2)t->rchild!=null (3)N0++ (4)count(t->lchild) (5)count(t->rchild)
18、利用筛选法将关键字序列(37，66，48，29，31，75)建成的大根堆为(____ ____)。
75, 66, 48, 29, 31, 37
19、对长度为20的有序表进行二分查找的判定树的高度为________。 5
20、阅读下列程序说明和程序，填充程序中的______
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：
（1）把根结点放入堆栈。
（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。
（3）重复（2）直到堆栈为空时为止。 typedef struct node *tree;
struct node{int data; tree lchild,rchild;}
exchange(tree t)
{tree r,p; tree stack [500]; int tp=0; (1)_______ while (tp>=0)
{(2)_______
if((3)_______)
{r=p->lchild; p->lchild=p->rchild; p->rchild=r stack[(4)_______]=p->lchild; stack[++tp]=p->rchild; } }}
(1)stack[tp]=t (2) p=stack[tp--] (3)p (4)++tp
21、排序(sorting)有哪几种方法_______________，_____________，____________，_____________，____________。
直接插入排序，冒泡排序，快速排序，希尔排序，归并排序，基数排序，堆排序等 22、下面程序段的时间复杂度为______________。（用O估计） FOR i:=1 TO n DO FOR j:=i TO n DO s=s+j; O（n*n）
23、非线性结构包括______________和_________________。 树，图 24、判断带头结点的双向循环链表L是否对称相等的算法如下所示，请在划线处填上正确的语句
FUNCTION equal(l:pointer) :boolean; VAR p,q:pointer; result: Boolean;
BEGIN result =true ; p:= l^.link; q:=l^.pre ;
WHILE (p<>q) AND ((1)_______)DO
IF p^.data=q^.data THEN BEGIN (2)___; (3)____; END； ELSE result=false ; return(result); END;
(1)result; (2)p:=p^.link; (3) q:=q^.pre （（２）（３）顺序可变）
25、用一维数组r[0. .m-1]表示顺序存储的循环队列，设队头和队尾指针分别是front 和rear，且队头指针所指的单元闲置，则队满的条件是______________________________，队空的条件是_____________________________。 Front=rear, rear+1=front
26、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀表达式是____________________________。
+*a-bc/de , abc-*de/+
27、已知中序遍历bt所指二叉树算法如下，s为存储二叉树结点指针的工作栈，请在划线处填入一条所缺语句。
PROC inorder (bt:bitreptr);
inistack(s); (1)_______; WHILE NOT empty(s) DO
[WHILE gettop(s)<>NIL DO push(s,gettop(s)↑.lchild); (2)_______; IF NOT empty(s) THEN [visit (gettop(s)^); p:=pop(s); (3)_______ ] ]
ENDP;{inorder}
(1)push(s,bt) （2）pop(s) （3）push(s,p^.rchild) // p的右子树进栈 28．对有向图进行拓扑排序，若拓扑排序不成功，则说明该图_________________。下面有向图的一个拓扑有序序列是______________________________。
存在回路，123456798 29、由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100
typedef struct Node
{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv)
{ TNODE *root;
if(argc<3) exit 0;
strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }
TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL;
ptr->info=(1)_______;
for((2)_______ ; rpos ptr->llink=restore(ppos+1, (4)_______,k ); ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k); return ptr; } postorder(TNODE*ptr) { if(ptr=NULL) return; postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info); } (1)*ppos // 根结点 （2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1 三 简答题 1、名词解释：（1）抽象数据类型；（2）算法的时间复杂性； （3）散列法(hashing)；（4）索引文件。 2、堆与二元查找树的区别? 3、(判断题) 非空的二叉树一定满足：某结点若有左孩子，则其中序前驱一定没有右孩子. Yxm:正确 深度为k具有n个结点的完全二叉树，其编号最小的结点序号为 ?2k-2?+1。Yxm:错误 在中序线索二叉树中，每一非空的线索均指向其祖先结点。Yxm:正确 当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。Yxm：错误 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。Yxm:正确 广度遍历生成树描述了从起点到各顶点的最短路径。Yxm：错误 连通图上各边权值均不相同，则该图的最小生成树是唯一的。Yxm:正确 一个有向图的邻接表和逆邻接表中结点的个数可能不等。Yxm：错误 4、如下所示的是一个带权无向图，带框的数字表示相应边的权，不带框的数字表示顶点号。用prime 算法求最小生成树时，如果已确定的边为(5,4),则，下一条边应在哪几条边中选取？选取哪一条？ 1 7 2 5 3 8 6 4 4 5 1 3 5 2 4 3 yxh：（4,6） 5、如何衡量hash函数的优劣？简要叙述hash表技术中的冲突概念，并指出三种解决冲突的方法。 评价哈希函数优劣的因素有：能否将关键字均匀影射到哈希空间上，有无好的解决冲突的方法，计算哈希函数是否简单高效。由于哈希函数是压缩映像，冲突难以避免。 散列表存储中解决碰撞的基本方法： ① 开放定址法 形成地址序列的公式是：Hi=（H（key）+di）% m，其中m是表长，di是增量。根据di取法不同，又分为三种： a．di =1，2，?，m-1 称为线性探测再散列，其特点是逐个探测表空间，只要散列表中有空闲空间，就可解决碰撞，缺点是容易造成“聚集”，即不是同义词的关键字争夺同一散列地址。 b．di =12，-12，22，-22，? ，?k2（k≤m/2） 称为二次探测再散列，它减少了聚集，但不容易探测到全部表空间，只有当表长为形如4j+3（j为整数）的素数时才有可能。 c．di =伪随机数序列，称为随机探测再散列。 ② 再散列法 Hi=RHi（key） i=1，2，?，k，是不同的散列函数，即在同义词产生碰撞时，用另一散列函数计算散列地址，直到解决碰撞。该方法不易产生“聚集”，但增加了计算时间。 ③ 链地址法 将关键字为同义词的记录存储在同一链表中，散列表地址区间用H[0..m-1]表示，分量初始值为空指针。凡散列地址为i（0≤i≤m-1）的记录均插在以H[i]为头指针的链表中。这种解决方法中数据元素个数不受表长限制，插入和删除操作方便，但 增加了指针的空间开销。这种散列表常称为开散列表，而①中的散列表称闭散列表，含义是元素个数受表长限制。 ④ 建立公共溢出区 设H[0..m-1]为基本表，凡关键字为同义词的记录，都填入溢出区 O[0..m-1]。 6、有一棵哈夫曼树共有5 个叶子结点其权值分别为0.1,0.25,0.08,0.21,0.9,试画出该哈夫曼树。假设该叶子分别表示a,b,c,d,e，分别给出五个叶子对应的哈夫曼编码。 yxh：a(1110),b(10),c(1111),d(110)，e(0) 7、采用哈希函数Ｈ（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51 （1）构造哈希表（画示意图）；（2）装填因子；等概率下（3）成功的和（4）不成功的平均查找长度。 （1） 散列地址 0 关键字 13 比较次数 1 8、已知一个图如下，试画出其逆邻接链表。 1 22 1 2 3 53 1 4 1 2 5 6 41 1 7 67 2 8 46 1 9 10 51 1 11 12 30 1 （2）装填因子=9/13=0.7 （3）ASLsucc =11/9 （4）ASLunsucc =29/13 1 2 3 4 9、若一个栈的输入序列是1,2,3??，n, 其输出序列为p1,p2,??pn, 若 p1=n，则pi为多少？ yxh：i=n-i+1 10、非空的二叉树的中根遍历序列中，根的右子树的所有结点都在根结点的后边，这说法对吗？ 11、已知二叉树的中根遍历序列为abc，试画出该二叉树的所有可能的形态。 12、已知一个图如图所示，如从顶点a出发进行按深度优先遍历，可否得到序列acebdf ?为什么？若按广度优先遍历，能否得到序列abedfc?为什么？