资源描述:
《数据结构域算法设计-第四-六章+串、数组、树作业(参考答案)教案》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第四-六章串、数组、树作业一、判断正误:(每小题1分,共5分)正确在()内打√,否则打×。1.(√)子串是主串中任意个连续字符组成的序列。2.(×)线性结构只能用顺序结构存放,非线性结构只能用链表存放。3.(√)完全二叉树的某结点若无左孩子,则它必是叶结点。4.(√)二叉树有五种基本形态。5.(√)由树的中序表示和前序表示可以导出树的后序表示。6.(√)将一棵树转换为二叉树表示后,该二叉树的根结点没有右子树。7.(√)采用二叉树来表示树时,树的先根次序遍历结果与其对应的二叉树的前序遍历结果是一样的。8.(×)在Huffman树中,权值较大的叶子结点离根较远。9.(×)用一维
2、数组存储二叉树时,是以先根遍历的次序存储结点。二、填空题1.已知二维数组A[0..10][0..20]采用行序为主方式存储,每个元素占2个存储单元,并且A[0][0]的存储地址是1024,则A[6][18]的地址是1312(1024+2*(6*21+18))。2.深度为5的二叉树最多有_____31___个结点(根结点层数为1)。3.高度为h的完全二叉树最少有2h-1个结点。4.二叉树的先序遍历序列为:EFHIGJK,中序遍历序列为:HFIEJKG,则该二叉树根的右子树的根是:G。5.N个结点的二叉树,采用二叉链表存放,空链域的个数为N+1。6.填空完成下面中序遍历二叉树的
3、非递归算法:voidInOrder(BiTreeroot){InitStack(&S);p=____root_____;while(_____p________
4、
5、!IsEmpty(S)){while(p!=NULL){Push(&S,__p___);p=_____p->lchild_________;}if(____!IsEmpty(S)___________){Pop(&S,__p_____);Visit(p->data);p=___p->rchild____________;}}}三、选择题1.表达式a*(b−c)+d的后缀表达式是(B)。A)abcd*−+B)abc
6、−*d+C)abc*−d+D)+−*abcd2.对于有N个结点高度为K的满二叉树(结点编号为1到N,根结点的层数为1),其第K层上最后1个结点的编号为(D)。A)2KB)2K−1C)B)2K−1−1D)2K−13.将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号最大的非叶结点的编号为:(C)。A)48B)49C)50D)514.在下列存储形式中,哪一个不是树的存储形式?(D)。A)双亲表示法B)孩子链表表示法C)孩子兄弟表示法D)顺序存储表示法5.某二叉树结点的中序序列为:A、B、C、D、E、F、G,后序序列为:B、D
7、、C、A、F、G、E,则其左子树中结点数目为:(C)。A)3B)2C)4D)56.从供选择的答案中,选出应填入下面叙述内的最确切的解答,把相应编号写在对应栏内。有一个二维数组A,行下标的范围是0到8,列下标的范围是1到5,每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。存储数组A的最后一个元素的第一个字节的地址是A。若按行存储,则A[3,5]和A[5,3]的第一个字节的地址分别是B和C。若按列存储,则A[7,1]和A[2,4]的第一个字节的地址分别是D和E。供选择的答案A~E:①28②44③76④92⑤108⑥116⑦
8、132⑧176⑨184⑩188答案:A=⑧B=③C=⑤D=①E=⑥7、从供选择的答案中,选出应填入下面叙述内的最确切的解答,把相应编号写在对应栏内。有一个二维数组A,行下标的范围是1到6,列下标的范围是0到7,每个数组元素用相邻的6个字节存储,存储器按字节编址。那么,这个数组的体积是A个字节。假设存储数组元素A[1,0]的第一个字节的地址是0,则存储数组A的最后一个元素的第一个字节的地址是B。若按行存储,则A[2,4]的第一个字节的地址是C。若按列存储,则A[5,7]的第一个字节的地址是D。供选择的答案A~D:①12②66③72④96⑤114⑥120⑦156⑧234⑨276
9、⑩282(11)283(12)288答案:A=(12)B=⑩C=③D=⑨8.将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号为:(A)A)98B)99C)50D)489.设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是:(D)A)M1B)M1+M2C)M3D)M2+M3四、综合题1.设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。给出下