清华大学《数据结构与算法》(3)

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。 本程序采用非递归的方法，设立一个堆栈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，且队头指针所指的单元闲置，则队满的条件是______________________________，队空的条件是_____________________________。

(rear+1)%m=front, front=rear 26、下面表达式树所对应的表达式的前缀表达式是_____________________________，后缀表达式是____________________________。

+*a-bc/de , abc-*de/+

人工实现转换：

? 中缀表达式：

? 第一步：按照运算符的优先级对所有的运算单位加括号：式子变成了：((a*(b-c))+(d/e)) ? 第二步：转换前缀与后缀表达式 ? 前缀：把运算符号移动到对应的括号前面，则变成了：+(*(a-(bc))/de)，把括号去掉：+*a-bc/de

前缀式子出现

? 后缀：把运算符号移动到对应的括号后面，则变成了：((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个结点的完全二叉树，其编号最小的结点序号为 ?2?+1。Yxm:错误 在中序线索二叉树中，每一非空的线索均指向其祖先结点。Yxm:正确

当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。Yxm：错误

用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个

k-2

数有关，而与图的边数无关。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） …… 此处隐藏：3120字，全部文档内容请下载后查看。喜欢就下载吧 ……