1 / 5 第四章串一．选择题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 开始）（）2 / 5 A.00405000000000706080 B.00000004053000706080C.00405000073000006080 D.00000304050000706080二． 解答题已知一个 6 行 5 列的稀疏矩阵中非零元的值分别为：-90，41， -76，28，-54，65，-8，它们在矩阵中的列号依次为：1，4，5，1，2， 4，5。当以带行表的三元组表作存储结构时，其行表中的值依次为0，0，2，2， 3，5（行列下标均从1 开始），写出该稀疏矩阵。3 / 5 第六章树和二叉树一．选择题1．如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）A. 栈B. 队列C. 树D. 图2．设树 T 的度为 4，其中度为1， 2，3 和 4 的结点个数分别为4，2，1，1 则 T 中的叶...
