数据结构答案归纳.pdf

第二阶段离线作业第二阶段离线作业本次离线作业分为非知识和知识两部分内容非知识部分满分为20 分：在课程论坛发表“期中学习感想”（20 分）知识部分满分为80 分：作业提交截止时间：本科2015 年 10 月 27 日 24 时非知识部分在课程论坛发表“期中学习感想” （20 分） ，须包含以下几个方面的内容：数据结构课程的总体认识；学习计划的实际执行情况；学习过程的心得体会；在学习中的长处与不足；对老师的建议第四章 串选择题1、设串的长度为n，则它的字串个数为A n Bn (n+1) C n (n+1)/2 Dn (n+1)/2+1 2、设串 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） ）的结果串是A BCDEF BBCDEFG CBCPQRST DBCDEFEF 3、设有两个串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 的起始地址为A SA+141 BSA+180 CSA+222 DSA+225 3、二维数组A 中，每个元素的长度为3 个字节，行下标i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA开始连续存放在存储器内，该数组按行存放时，元素A74 的起始地址为。

A SA+141 BSA+180 CSA+222 DSA+225 4、二维数组A 中，每个元素的长度为3 个字节，行下标i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA开始连续存放在存储器内，存放该数组至少需要的字节数为A 80 B100 C240 D270 5、二维数组A 的成员是6 个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i 的范围从0 到 8，列下标j 的范围从0 到 9，则存放M 至少需要个字节； M 数组的第8列和和第五行共个字节A 90 B180 C240 D570 E108 F114 G54 H60 6、下面说法不正确的是( )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. 48 4、由权值分别为3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为_A. 24 B.48 C. 72 D. 53 5、一棵度为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为结点权值，画出构造的哈弗曼树，计算其带权路径长度5、 假设一棵二叉树如下图所示，求：第二阶段离线作业（1）该二叉树的深度；（2）该二叉树的先序序列（3）该二叉树的中序序列；（4）该二叉树的后续序列根据二叉树的定义，具有三个结点的二叉树有5 中不同形态，请将它们分别画出来。