《数据结构与算法》期末练习题 - 2010-2011-1 - 带答案

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 ((2)(3)顺序可变)

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)算法的时间复杂性;

2、堆与二元查找树的区别?

3、(判断题)

非空的二叉树一定满足:某结点若有左孩子,则其中序前驱一定没有右孩子. Yxm:正确 深度为k具有n个结点的完全二叉树,其编号最小的结点序号为 ?2?+1。Yxm:错误 在中序线索二叉树中,每一非空的线索均指向其祖先结点。Yxm:正确

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

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

k-2

(3)散列法(hashing);(4)索引文件。

与图的边数无关。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 =1,-1,2,-2,? ,?k(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]。

2

2

2

2

2

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、采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突,在数列地址空间[0..12]中对关键字序列22,41,53,46,30,13,1,67,51 (1)构造哈希表(画示意图);(2)装填因子;等概率下(3)成功的和(4)不成功的平均查找长度。 (1)

散列地址 关键字 比较次数 0 13 1 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

8、已知一个图如下,试画出其逆邻接链表。

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?为什么?

a c b e f d

13、栈的存储方式有哪两种?

联系客服:779662525#qq.com(#替换为@)