数据结构试题库答案(7)

(262) 已知二叉树的二叉链表存储表示，指出建立如图所示树的结构时输入的字符序列。

A B D E F C typedef struct BiTNode { char data;

struct BiTNode *lchild,*rchild; } BiTNode;

void CreateBiTree( BiTNode *T) { char ch; scanf(&ch);

if(ch= =‘ ‘) T=NULL;

else{ T=(BiTNode *)malloc(sizeof(BiTNode)); while (T==NULL)

G T=(BiTNode *)malloc(sizeof(BiTNode)); T–>data=ch;

CreateBiTree(T–>lchild); CreateBiTree(T–>rchildd); } }

AB?D??CE?FG???? (263)

已知二叉树的二叉链表存储表示，写出中序遍历的递归算法。

typedef struct BiTNode { char data;

struct BiTNode *lchild,*rchild; } BiTNode,*BiTree;

void inorder( BiTNode *p) { if (p!=NULL)

{ inorder(p–>lchild); printf(“%c”,p–>data) inorder(p–>rchild); } } (264)

阅读下面的程序，分别指出程序中三个for循环、整个程序以及语句

scanf(\的功能。

void funcgraph(MGraph &G) {

int i,j,k,w;

char v1,v2;

printf(\scanf(\printf(\for (i=0;i

scanf(\

for (i=0;i

for (j=0;j

G.arcs[i][j]=0;

for (k=0;k

printf(\scanf(\i=LocateVex(G,v1); j=LocateVex(G,v2);

G.arcs[i][j]=w; G.arcs[j][i]=w;

} }

第一个for循环：将图中的顶点输入到数组G.vexs[i]； 第二个for循环，初始化邻接矩阵；

第三个for循环，将图中边信息存入数组G.vexs[i]中； 本程序的功能是：创建图的邻接矩阵；

scanf(\：语句的功能输入定点数和图中的边数。

设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题：

（1） 画出哈希表的示意图；

（2） 若查找关键字63，需要依次与哪些关键字进行比较？

（3） 若查找关键字60，需要依次与哪些关键字比较？

（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解： （1）画表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 30 31 46 17 47 32 17 63 49 24 40 10 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次； 对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次， 所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55