做在答题纸上,在试题纸上做解答按零分处理。数据结构的3.docVIP

做在答题纸上,在试题纸上做解答按零分处理。数据结构的3 1、敏而好学，不耻下问——孔子 　　请将所有答案做在答题纸上，在试题纸上做解答按零分处理 数据结构的算法试题可使用C或C++语言的风格描述 　一．单项选择题 (本大题共10小题，每小题2分，共20分) 将答案选项与题目编号写在答题纸上，错选或未选均无分 1. 将长度为 n 的单链表接在长度为 m 的单链表之后的算法时间复杂度为 ( ) A. O( n ) B. O( 1 ) C. O( m ) D. O( m + n ) 2. 设数组 data[ m ] 作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 的值为 ( ) A. front = front + 1 B. front = ( front + 1 ) % ( m - 1 ) C. front = ( front - 1 ) % m D. front = ( front + 1 ) % m 3. 一个非空广义表的表头 ( ) A. 不可能是子表 B. 只能是子表 C. 只能是原子 D. 可以是原子或子表 4. 堆排序在最坏的情况下的时间复杂度是 ( ) 　　A. O( log2 n ) B. O( log2 n2 ) 　　C. O( nlog2 n ) D. O( n2 ) 5. 设 G1 = ( V1, E1) 和 G2 = ( V2, E2 ) 为两个图，如果V1 ? V2，E1 ? E2，则称 ( ) A. G1是G2 的子图 B. G2 是G1 的子图 C. G1 是 G2 的连通分量 D. G2 是 G1 的连通分量 6. 在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为 ( ) A. 4 B. 5 C. 6 D. 7 7. 设一个有n 个顶点和 e 条弧的有向图用邻接表表示，则删除与某顶点vi 相关的所有弧的时间复杂度是 A. O( n ) B. O( e ) C. O( n + e ) D. O( n* e) 8. 算法指的是 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 9. 若派生类的成员函数不能直接访问基类中继承来的某个成员，则该成员一定是基类中的 A. 私有成员 　　B. 公有成员 C. 保护成员 D. 保护成员或私有成员 10. 在C++程序中，对象之间的相互通信通过 A. 继承实现 　 　B. 调用成员函数实现 C. 封装实现 D. 函数重载实现 二． 填空题 ( 本大题共16小题，除第26小题5分外，其余每小题2分，共35分) 不写解答过程，将正确答案与题目编号写在答题纸上 11. 仅允许在同一端进行插入删除的线性表称为 12. 在一个长度为 n 的顺序表中第 i 个元素 ( 1 ? i ? n ) 之前插入元素时，需向后移动 元素个数是 13. 在串S =structure 中，以 t 为首字符的子串有 个 14. 在拓扑排序中，拓扑序列的第一个顶点必定是 的顶点 15. 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 　　 无关，是独立于计算机的 16. 在含n 个顶点和 e 条边的无向图的邻接矩阵中，零元素的个数为 　　 17. 设用S 和 X 分别表示进栈和出栈操作， 则对输入序列a, b, c, d和e 进行一系列栈操作 SSXSXSSXXX 之后，得到的输出序列为 　　 18. 对表长为n 的顺序表进行分块查找，若以顺序查找确定块，且每块的长度为s， 则在等概率查找的情况下，查找成功时的平均查找长度为 　　 19. 已知一棵完全二叉树中共有768 个结点，则该树中共有 　　 个叶子结点 20. 设一个9阶的上三角矩阵A 按列优先顺序压缩存储在一维数组B 中，其中B[0] 存储矩阵中第一个元素a1,1, 则B[31] 中存放的元素是 　　 ( 注：矩阵元素下标从1起计) 21. C++支持的两种多态性分别是 多态性和 多态性 22. 定义类的动态对象数组时，系统只能够自动调用该类的 构造函数对其进行初始化 23. 初始化类模板时，相对于它的每个参数要提供 24. 面向对象程序设计的 机制提供了重复利用