淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 13
B．0 A．可以顺序存储 B. 数据元素是一个字符 C．可以链接存储 D. 数据元素可以是多个字符 6．串是( )。 A．少于一个字母的序列 B. 任意个字母的序列 C．不少于一个字符的序列 D. 有限个字符的序列 7． 串的长度是( )。 A．串中不同字母的个数 B. 串中不同字符的个数 C．串中所含的字符的个数 D. 串中所含字符的个数，且大于0 8． 设有S1=‘ABCDEFG’，S2=‘PQRST’，函数con(x，y)返回x和y串的连接串，subs(i，j)返回串S 的从序号I的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(S1，2，len(S2))，subs(S1，len(S2)，2))的结果是( )。 A．BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 9． 若某串的长度小于一个常数，则采用( )存储方式最为节省空间。 A．链式 B. 堆结构 C. 顺序表 二、填空题： 1．串是每个结点仅由一个字符组成的____________________。 2．在串中，SubString (“student”,5,0) 的结果是____________________。 3．假设S=“abcaabcaaabca”，T=“bca”，V=“x”，Replace (S,T,V)结果是__________。 4．在串中，对于StrCompare(S,T)基本操作，若S 6．串与线性表在逻辑结构上极为相似，区别仅在于_____________________________ ；在基本操作上差 别很大，线性表的基本操作大多数以_____________ 作为操作对象，而串的基本操作通常以______________________ 作为操作对象。 7．两个串相等的充分必要条件是____________________ 且_____________________________________。 8．空串是指_____________________，空格串是指____________________________。 9．串是一种特殊的线性表,其特殊性体现在_____________________________。 三、判断题 1．空串是由空白字符组成的串 （ ） 2．串的定长顺序结构是用一组地址连续的存储单元存储串值的字符序列，按照预定义的大小，为每个定 义的串变量分配一个固定长度的存储区。 ( ) 3．串的堆分配存储表示是用一组地址连续的存储单元存储串值的字符序列，但它们的存储空间是在程序 执行过程中动态分配得到的。 （ ） 4．串中StrInsert(&S,pos,T)基本操作是最小的操作子集 （ ） 5．串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。 （ ） 6．如果一个串中的所有字符均在另一串中出现，那么则说明前者是后者的子串。( ) 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 14 7．串类型的最小操作子集不能利用其他串操作来实现，反之，其他串操作（除串清除ClearString和串销 毁DestroyString外）均可在最小操作子集上实现。 ( ) 四、简答题 1．串是字符组成的，长度为1的串和字符是否概念相同？为什么？ 答： 五、算法设计题 1．设串s和串t采用顺序存储结构，编写函数实现串s和串t的比较操作，要求比较结果包括大于、小于和等于三种情况。 解： 2．输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计此文本中单词的个数。 成绩____________ 日期____________________ 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 15 第5章 数组和广义表 一、 单项选择题 1. 常对数组进行的两种基本操作是( )。 A. 建立与删除 B. 索引和修改 C. 对数据元素的存取和修改 D. 查找与索引 2. 二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要( )个字节；M数组的第8列和第5行共占( )个字节。 A. 90、114 B. 180、54 C. 240、60 D. 540、108 3. 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是( )。 A. 80 B. 100 C.240 D. 270 4. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为( )。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 5. 假设以行优先顺序存储三维数组R[6][9][6]，其中元素R[0][0][0]的地址为2100，且每个元素占4个存储单元，则存储地址为2832的元素是( )。 A． R[3][3][3] B．R[3][3][4] C．R[4][3][5] D．R[4][3][4] 6. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为( )。 A． 13 B．35 C．17 D．36 7. 对稀疏矩阵进行压缩存储目的是( )。 A． 便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 二、 填空题（将正确的答案填在相应的空中） 1. 已知二维数组A[m][n]采用行序为主方式存储，每个元素占k个存储单元，并且第一个元素的存储地址是LOC(A[0][0])，则A[i][j]的地址是_____________________________。 2. 二维数组A[10][20]采用列序为主方式存储，每个元素占一个存储单元并且A[0][0]的存储地址是200，则A[6][12]的地址是________________________。 3. 二维数组A[10..20][5..10]采用行序为主方式存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则A[18][9]的地址是____________________________________。 4．求下列广义表操作的结果： (1) GetTail[GetHead[((a,b),(c,d))]]; ________________________ (2) GetTail[GetHead[GetTail[((a,b),(c,d))]]] ________________________ 成绩____________ 日期____________________ 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 16 第6章 树和二叉树 一、 选择题： 1、在具有n个结点的完全二叉树中，结点i（i>1）的父结点是（ ） A．2i B．不存在 C．2i+1 D．? i/2? 2、有m个叶结点的哈夫曼树所具有的结点数为（ ） A．m B．m+1 C．2m D．2m - 1 3、下列陈述中正确的（ ） A．二叉树是度为2的有序树 B．二叉树中结点只有一个孩子时无左右之分 C．二叉树中必有度为2的结点 D．二叉树中最多只有两棵子树，并且有左右之分 4、以二叉链表作为二叉树的存储结构，在具有ｎ个结点的二叉链表中(n>0)，空链域的个数为（ ） A．2n - 1 B．n - 1 C．n + 1 D．2n + 1 5、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为（ ） A．99 B．98 C．50 D．48 6、在一棵具有五层的满二叉树中，结点总数为（ ） A．31 B．32 C．33 D．16 7、在一棵二叉树中，第5层上的结点数最多为（ ） A．8 B．15 C．16 D．32 8、由二叉树的（ ）遍历，可以惟一确定一棵二叉树 A．前序和后序 B．前序和中序 C．后序 D．中序 9、具有35个结点的完全二叉树的深度为（ ）。 A.5 B.6 C.7 D.8 10、已知一棵二叉树的先序遍历序列为EFHIGJK，中序遍历序列为HFIEJGK，则该二叉树根的右子树的根 是（ ）。 A．E B. F C. G D. J 11、由4个结点构造出的不同的二叉树个数共有（ ）。 A．8 B. 10 C．12 D．14 12、在完全二叉树中，如果一个结点是叶子结点，则它没有（ ）。 A.左孩子结点 B. 右孩子结点 C.左、右孩子结点 D.左、右孩子结点和兄弟结点 13、深度为6的二叉树最多有（ ）个结点。 A．64 B．63 C．32 D．31 14、二叉树使用二叉链表存储，若p指针指向二叉树的一个结点，当p->lchild=NULL时，则（ ）。 A． p结点左孩子为空 B．p结点有右孩子