1、第二阶段离线作业第二阶段离线作业本次离线作业分为非知识和知识两部分内容。 非知识部分满分为 20 分： 在课程论坛发表“期中学习感想” （20 分） 知识部分满分为 80 分：作业提交截止时间：本科 2015 年 10 月 27 日 24 时 非知识部分在课程论坛发表“期中学习感想” （20 分） ，须包含以下几个方面的内容： 数据结构课程的总体认识； 学习计划的实际执行情况； 学习过程的心得体会； 在学习中的长处与不足； 对辅导老师的建议。第四章 串选择题1、设串的长度为 n，则它的字串个数为 。An Bn (n+1) Cn (n+1)/2 Dn (n+1)/2+12、设串 S1=ABCDE
2、FG，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） ）的结果串是 。ABCDEF BBCDEFG CBCPQRST DBCDEFEF3、设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作 。A连接 B模式匹配 C求子串 D求串长4、串是一种特殊的线性表，其特殊性体现在 。A可以顺序存储 B数据元素是一个字符C 可以链接存储 D数据元素可以是
3、多个字符5、空串和空格串 。A相同 B不相同取6、以下叙述中正确的是 。A串是一种特殊的线性表 B串的长度必须大于零C串中元素只能是字母 D空串就是空白串填空题1、串的两种最基本的存储方式是 和 。2、设 S=i AMA TEACHER，其长度是 。第二阶段离线作业3、空格串是 ，其长度等于 。4、空串是 ，其长度等于 。5、两个串相等的充分必要条件是 。第五章 数组和广义表选择题1、常对数组进行的两种基本操作时是 。A建立与删除B索引和修改C对数据元素的存取和修改D查找和索引2、二维数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址
4、SA 开始连续存放在存储器内，该数组按列存放时，元素 A47的起始地址为 。ASA+141 BSA+180 CSA+222 DSA+2253、二维数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在存储器内，该数组按行存放时，元素 A74的起始地址为 。ASA+141 BSA+180 CSA+222 DSA+2254、二维数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在存储器内，存放该数组至少需要的字节数为 。A80 B100 C240
5、 D2705、二维数组 A 的成员是 6 个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标 i 的范围从 0 到 8，列下标 j 的范围从 0 到 9，则存放 M 至少需要 个字节；M 数组的第8 列和和第五行共 个字节。A90 B180 C240 D570E108 F114 G54 H606、下面说法不正确的是( )。A. 广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C. 广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构7、现有广义表 Ls=(a,(a,b),d,e,(i,j,(),k),则该广义表的长度是( ),深度是( )。A. 4 B. 5 C. 8
6、 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),则它的
7、深度为_ ，它的长度为_。第六章 树和二叉树选择题1、 树最适合用来表示 。A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据 D元素之间无联系的数据 2、树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为线序遍历、中序遍历和后序遍历。这里，我们把树转化得到的二叉树叫做这棵树对应的二叉树。以下结论正确的是 。A树的先根遍历序列与其对应的二叉树的先序遍历序列相同B树的后根遍历序列与其对应的二叉树的后序遍历序列相同C树的先根遍历序列与其对应的二叉树的中序遍历序列相同D以上都不对 3、将一棵有 100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号
8、为 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为结点权值，画出构造的哈弗曼树，计算其带权路径长度。第二阶段离线作业5、 假设一棵二叉树如下图所示，求：（1 ） 该二叉树的深度；（2 ） 该二叉树的先序序列（3 ） 该二叉树的中序序列；（4 ） 该二叉树的后续序列。根据二叉树的定义，具有三个结点的二叉树有 5 中不同形态，请将它们分别画出来。
