数据结构习题(,,).docVIP

第四章 串 一．选择题 1．若串S=software,其子串的数目是（ ） A．8 B．37 C．36 D．9 2．设有两个串 p和q,求q在p中首次出现的位置的运算称作（　） A．连接　　 B．模式匹配 　　C．求串长　　 D．求子串 3．设字符串 S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为 （　） A．A BCDEF 　　B．BCDEFG 　　C．BCDPQRST 　D．?BCDEFEF 4．下面的说法中，只有（ ）是正确的 A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串 5．两个字符串相等的条件是（ ） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为 ，nextval函数值为 。 2．子串的长度为 。 第五章 数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（ ） A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（　　） A. B. C. D. 二． 解答题 已知一个6行5列的稀疏矩阵中非零元的值分别为：-90，41，-76，28，-54，65，-8，它们在矩阵中的列号依次为：1，4，5，1，2，4，5。当以带行表的三元组表作存储结构时，其行表中的值依次为0，0，2，2，3，5（行列下标均从1开始），写出该稀疏矩阵。 第六章 树和二叉树 一．选择题 1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（ ） A. 栈 B. 队列 C. 树 D. 图 2．设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ） A．5 B．6 C．7 D．8 3．已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（ ） A. 0 B. 1 C. 48 D. 49 4．树的先根序列等同于与该树对应的二叉树的（ ） A．先序序列 B．中序序列 C．后序序列 D．层序序列 5. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为（ ） A．n-1 B．n C．n+l D．2n 6. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 7. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T中的叶子数为（ ） A．5 B．6 C．7 D．8 8．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ） A．M1 B．M1+M2 C．M3 D．M2+M3 9．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（ ） A． 250 B． 500 C．254