1 《数据结构》 一． 选择题（从下列答案选项中选出一个正确答案，每小题2 分) 1. 在计算机中存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ ）。 A．逻辑结构 B．顺序存储结构 C．链式存储结构 D. 以上都对 2. 线性表就是顺序表，这种说法（ ）。 A．正确 B．错误 3. 若已知一个栈的入栈序列是1, 2, 3, 4, 5，不可能得到的输出序列是（ ）。 A．2,3,4,1,5 B． 5,4,1,3,2 C．2,3,1,4,5 D．1,5,4,3,2 4. 串的逻辑结构与（ ）的逻辑结构不同。 A. 栈 B. 队列 C. 树 D. 线性表 5. 如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（） A. 正确 B. 错误 6. 设有两个串P 和Q，求Q 在P 中首次出现的位置的操作称为（ ）。 A.连接 B.模式匹配 C.求子串 D.求串长 7. 已知模式串t=“abcaabbcabcaabdab”，该模式串的nex t 数组值为（ ）。 A. -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 B. 0，1，0，0，1，1，2，0，0，1，2，3，4，5，6，0，1 C. -1，0，0，0，1，1，2，0，0，1，2，3，4，5，6，7，1， D. -1，0，0，0，1，1，2，3，0，1，2，3，4，5，6，0，1 8. 设有一个10 阶的对称矩阵 A，采用压缩存储方式，以行序为主存储，a11 为第一个元素，其存储地址为1，每个元素占 1 个地址空间，则a85 的地址为（ ）。 A. 13 B. 33 C. 18 D. 40 9. 若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种说法（ ）。 A. 正确 B. 错误 10. 树形结构的特点是：一个结点可以有（）。 A、多个直接前趋 2 B、多个直接后继 C、多个前趋 D、一个后继 11. 在一棵高度为 h 的满三叉树中，结点总数为（） A、3h-1 B、(3h-1)/2 C、(3h-1)/3 D、3h 12. 设森林 T 中有 4 棵树，结点个数依次为 n 1, n 2, n 3, n 4，当把森林 T 转换成一棵二叉树后，二叉树根结点的右子树上有（ ）个结点。 A．n 1-1 B．n 1 C．n 1+n 2+n 3 D．n 2+n 3+n 4 13. 任何一个无向连通图的最小生成树（ ）。 A．只有一颗 B．有一颗或多棵 C．一定有多棵 D．可能不存在 14. 一个无向连通图的生成树是含有该连通图的全部顶点的（）。 A、极小连通子图 B、极小子图 C、极大连通子图 D、极大子图 15. 在一个有向图的邻接表或逆邻接表中，如...
