数据结构答案.doc

第二阶段离线作业第二阶段离线作业本次离线作业分为非知识和知识两部分内容。l 非知识部分满分为20分： 在课程论坛发表“期中学习感想”（20分）l 知识部分满分为80分：作业提交截止时间：本科2015年10月27日24时 非知识部分在课程论坛发表“期中学习感想”（20分），须包含以下几个方面的内容： 数据结构课程的总体认识； 学习计划的实际执行情况； 学习过程的心得体会； 在学习中的长处与不足； 对辅导老师的建议。第四章 串选择题1、设串的长度为n，则它的字串个数为 。AnBn (n+1)Cn (n+1)/2Dn (n+1)/2+12、设串S1=ABCDEFG，S2=PQRST，函数con（x,y）返回x和y串的连接串，subs（S，I，j）返回串S的从序号i字符开始的j个字符组成的字串，len（S）返回串S的长度，则con（subs（S1，2，len（S2），subs（S1， len（S2），2）的结果串是 。ABCDEFBBCDEFGCBCPQRSTDBCDEFEF3、设有两个串p和q，求q在p中首次出现的位置的运算称作 。A连接B模式匹配C求子串D求串长4、串是一种特殊的线性表，其特殊性体现在 。A可以顺序存储B数据元素是一个字符C 可以链接存储D数据元素可以是多个字符5、空串和空格串 。A相同B不相同取6、以下叙述中正确的是 。A串是一种特殊的线性表B串的长度必须大于零C串中元素只能是字母D空串就是空白串填空题1、串的两种最基本的存储方式是 和 。2、设S=iAMATEACHER，其长度是 。3、空格串是 ，其长度等于 。4、空串是 ，其长度等于 。5、两个串相等的充分必要条件是 。第五章 数组和广义表选择题1、常对数组进行的两种基本操作时是 。A建立与删除B索引和修改C对数据元素的存取和修改D查找和索引2、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A47的起始地址为 。ASA+141BSA+180CSA+222DSA+2253、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A74的起始地址为 。ASA+141BSA+180CSA+222DSA+2254、二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数为 。A80B100C240D2705、二维数组A的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M至少需要 个字节；M数组的第8列和和第五行共 个字节。A90B180C240D570E108F114G54H606、下面说法不正确的是( )。A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构7、现有广义表Ls=(a,(a,b),d,e,(i,j,(),k),则该广义表的长度是( ),深度是( )。A. 4 B. 5 C. 8 D. 9 E. 2 F. 3 G. 4 H.5填空题1、二维数组A20 10采用行序列为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A89的地址是 。2、二维数组A1020采用列序列为主方式存储，每个元素占1个存储单元，并且A00的存储地址是200，则A612的地址是 。3、二维数组Amn采用行序列为主方式存储，每个元素占k个存储单元，并且A00的存储地址是LOC（A00），则Aij的地址是 。4、已知广义表A=（a），则A的表头为_。5、广义表A= (a,(a,b),(a,b),c),则它的深度为_，它的长度为_。第六章 树和二叉树选择题1、 树最适合用来表示 。A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据 2、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为线序遍历、中序遍历和后序遍历。这里，我们把树转化得到的二叉树叫做这棵树对应的二叉树。以下结论正确的是 。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C树的先根遍历序列与其对应的二叉树的中序遍历序列相同D以上都不对 3、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为_。A. 98 B.99 C. 50 D. 484、由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A. 24 B.48 C. 72 D. 535、一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为_A.4 B.5 C.6 D.7解答题1、 一棵含有N个结点的K叉树，可能达到的最大深度和最小深度各为多少？简答题1、 二叉树的性质。2、 由于元素插入的次序不同，所构成的二叉排序树也有不同的状态，请画出一棵含有1，2，3，4，5，6六个结点且以1为根，深度为4的二叉排序树。3、 设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该二叉树。4、 以数据集4,5,6,7,10,12,18为结点权值，画出构造的哈弗曼