数据结构答案

1、第二阶段离线作业本次离线作业分为非知识和知识两部分内容。非知识部分满分为20 分：在课程论坛发表“期中学习感想”（20 分）知识部分满分为80 分：作业提交截止时间：本科2015 年 10 月 27 日 24时非知识部分在课程论坛发表“期中学习感想” （ 20 分），须包含以下几个方面的内容：数据结构课程的总体认识；学习计划的实际执行情况；学习过程的心得体会；在学习中的长处与不足；对辅导老师的建议。第四章串选择题1、设串的长度为n，则它的字串个数为。A nB n (n+1)C n (n+1)/2D n (n+1)/2+12、设串 S1=ABCDEFG，S2=PQRST，函数 con（ x,y）

2、返回 x 和 y 串的连接串， subs（ S， I，j）返回串 S 的从序号 i 字符开始的 j 个字符组成的字串，len（ S）返回串 S 的长度，则 con（ subs（ S1，2，len （ S2），subs（ S1， len（ S2）， 2）的结果串是。A BCDEFBBCDEFGC BCPQRSTD BCDEFEF3、设有两个串p 和 q，求 q 在 p 中首次出现的位置的运算称作。A连接B模式匹配C求子串D求串长4、串是一种特殊的线性表，其特殊性体现在。A可以顺序存储B数据元素是一个字符C 可以链接存储D数据元素可以是多个字符5、空串和空格串。A相同B不相同取6、以下叙述中正确的

3、是。A串是一种特殊的线性表B串的长度必须大于零C串中元素只能是字母D空串就是空白串填空题1、串的两种最基本的存储方式是和。2、设 S=iAM A TEACHER，其长度是。3、空格串是，其长度等于。4、空串是，其长度等于。5、两个串相等的充分必要条件是。第五章数组和广义表选择题11 、常对数组进行的两种基本操作时是。A建立与删除B索引和修改C对数据元素的存取和修改D查找和索引2 、二维数组A 中，每个元素的长度为3 个字节，行下标i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA开始连续存放在存储器内，该数组按列存放时，元素A47 的起始地址为。A SA+141BSA+180C S

4、A+222D SA+2253 、二维数组A 中，每个元素的长度为3 个字节，行下标i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA开始连续存放在存储器内，该数组按行存放时，元素A74 的起始地址为。A SA+141BSA+180C SA+222D SA+2254 、二维数组A 中，每个元素的长度为3 个字节，行下标i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA开始连续存放在存储器内，存放该数组至少需要的字节数为。A 80B 100C 240D 2705 、二维数组A 的成员是6 个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i 的范围从0 到 8，列

5、下标j 的范围从0 到 9，则存放M 至少需要个字节； M 数组的第8列和和第五行共个字节。A 90B 180C 240D 570E108F114G 54H 606 、下面说法不正确的是( )。A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构7、现有广义表Ls=(a,(a,b),d,e,(i,j,(),k), 则该广义表的长度是( ),深度是 ( )。A. 4B. 5C. 8D. 9E. 2F. 3G. 4H.5填空题1、二维数组 A20 10 采用行序列为主方式存储，每个元素占4 个存储单元，并且A105 的存储

6、地址是 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、树的基本

7、遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为线序遍历、中序遍历和后序遍历。这里，我们把树转化得到的二叉树叫做这棵树对应的二叉树。以下结论正2确的是。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C树的先根遍历序列与其对应的二叉树的中序遍历序列相同D以上都不对3、将一棵有100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为 1，则编号为49 的结点的左孩子的编号为_。A. 98B.99C. 50D. 484、由权值分别为3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为_。A. 2

8、4B.48C. 72D. 535、一棵度为3 的树中，度为3 的结点个数为2，度为 2 的结点个数为1，则度为0 的结点个数为 _A.4B.5C.6D.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 为结点权值，画出构造