资源描述：
《数据结构域算法设计-第四-六章+串、数组、树作业(参考答案)教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
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’。给出下
