公共基础知识练习题剖析.docx

公共基础知识练习题 第一章 数据结构和算法 一、选择题 1. 算法的时间复杂度是指 A) 运行时算法程序所占的内存容量 B) 算法程序运行的时间 C) 算法程序中语句条数 D) 算法程序执行过程中基本运算的次数 2. 下列关于栈的叙述中正确的是 A) 只能在栈顶插入元素，而不能删除元素 B) 可以插入元素，也能删除元素 C) 插入元素时需要移动栈中所有的元素 D) 删除元素时需要移动栈中所有的元素 3. 下列数据结构中具有记忆作用的是 A) 带链栈 B) 循环队列 C) 有序线性表 D) 二叉树 4. 数据结构分为逻辑结构和存储结构，下列数据结构中不属于存储结构的是 A) 顺序表 B) 循环链表 C) 队列 D) 循环队列 5. 设有如图所示的二叉树则对该二叉树中序遍历的结果是 A) FCADBEG B) ACBDFGE C) ABDCGEF D) ACBDFEG 6. 下列叙述中正确的是 A) 数据的逻辑结构与存储结构是一一对应的 B) 算法的空间复杂度是指算法程序的长度 C) 算法的效率只与所处理数据的规模有关,而与数据的存储结构无关 D) 上述三种说法都不对 7. 下面对于线性链表的描述中正确的是 A) 存储空间不一定是连续且各元素的存储顺序是任意的 B) 存储空间不一定连续且前件元素一定存储在后件元素的前面 C) 存储空间必须连续，且前件元素一定存储在后件元素的前面 D) 存储空间必须连续，且各元素的存储顺序是任意的 8. 对下列二叉树进行中序遍历的结果是 A) YHXPDT B) XYHDPT C) HYPTDX D) XYDHPT 9. 在深度为6的满二叉树中，度为2的结点个数为 A) 64 B) 63 C) 32 D) 31 10. 下列关于栈的叙述中正确的是 A) 在栈中只能插人数据 B) 在栈中只能删除数据 C) 栈是先进先出的线性表 D) 栈是先进后出的线性表 11. 在最坏情况下，下列各排序方法的比较次数正确的是 A) 冒泡排序为n/2 B) 插入排序为n(n+1)/2 C) 选择排序为n/2 D) 快速排序为n(n-1)/2 12. 将7个数据进行插入排序，在最坏情况下需要比较的次数是 A) 42 B) 6 C) 7 D) 21 13. 设有如图所示的二叉树,则对该二叉树前序遍历的结果是 A) FCADBEG B) ACBDFCE C) ABDCCEF D) ACBDFEC 14. 下面描述中正确的是 A) 程序就是软件 B) 软件开发不受计算机系统的限制 C) 软件既是逻辑实体，又是物理实体 D) 软件是程序、数据与相关文档的集合 15. 对长度为n的线性表进行顺序查找，在最坏情况下所需要的比较次数为 A) log2n B) n／2 C) n D) n+1 16. 下列叙述中正确的是 A) 线性表是线性结构 B) 栈与队列是非线性结构 C) 线性链表是非线性结构 D) 二叉树是线性结构 17. 下列数据结构中，插入时不需要移动其他元素的是 A) 有序线性表 B) 无序线性表 C) 栈和队列 D) 以上三种都不是 18. 将6个数据进行插入排序，在最坏情况下需要比较的次数是 A) 30 B) 6 C) 7 D) 15 19. 数据的存储结构是指 A) 数据所占的存储空间量 B) 数据在计算机中的顺序存储方式 C) 存储在外存中的数据 D) 以上三种说法都不对 20. 一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为 A) 221 B) 219 C) 231 D) 229 21. 下列数据结构中，插入时不需要移动其他元素的是 A) 有序线性表 B) 无序线性表 C) 循环队列 D) 以上三种都不是 22. 下列叙述中正确的是 A) 同一个数据结构不管是采用何种存储方式，其所占的存储容量一定是相同的。 B) 同一个数据结构采用不同的存储方式，其所占的存储容量一般是不同的。 C) 同一个有序表不管是采用何种存储方式，都可以使用二分查找法。 D) 同一个有序表不管是采用何种存储方式，都不能使用二分查找法。 23. 将6个数据进行快速排序，在最坏情况下需要比较的次数是 A) 15 B) 5 C) 6 D) 30 24. 下列叙述中正确的是 A) 所有形态的二叉树都只能采用链式存储结构 B) 循环队列是队列的一种存储方式 C) 栈只能采用顺序存储结构 D) 循环队列与循环链表都