公共基础习题.docx

公共基础习题.docx公共基础知识****题
数据结构与算法****题
填空题
在深度为7的满二叉树中，度为2的结点个数为___63
算法的复杂度主要包括 复杂度和空间复杂度。答：时间
设一棵完全二叉树共有500个结点，则在该二叉树中有 个叶子结点。答：250
在先左后右的原则下，根据访问根结点的次序，二叉树的遍历可以分为三种：前序 遍历、遍历和后序遍历。答：中序
在最坏情况下，冒泡排序的时间复杂度为。答：
n(n-1 )/2#n* (n-1 )/2#O(n(n-1 )/2)#O(n*(n-1)/2)
数据结构包括数据的 结构和数据的存储结构。答：逻辑
栈的基本运算有三种：入栈、退栈和。答：读栈顶兀素、读栈顶的兀素、读 出栈顶元素
实现算法所需的存储单元多少和算法的工作量大小分别称为算法的 o答：
空间复杂度和时间复杂度
数据结构包括数据的逻辑结构、数据的 以及对数据的操作运算。答：存储
结构
算法的基本特征是可行性、确定性、和拥有足够的情报。答:有穷性
顺序存储方法是把逻辑上相邻的结点存储在物理位置 的存储单元中。答：相
邻
在最坏情况下，堆排序需要比较的次数为。答：O(nlog2n)
二、 选择题
下列叙述中正确的是(B)
算法的效率只与问题的规模有关，而与数据的存储结构无关
算法的时间复杂度是指执行算法所需要的计算工作量
数据的逻辑结构与存储结构是一一对应的
算法的时间复杂度与空间复杂度一定相关
下列对队列的叙述正确的是(D)
队列属于非线性表
队列按“先进后出”原则组织数据
队列在队尾删除数据
队列按“先进先出”原则组织数据
算法中，对需要执行的每一步操作，必须给出清楚、严格的规定，这属于算法的(C)
()
正当性
可行性
确定性
有穷性
某二叉树中有n个度为2的结点，则该二叉树中的叶子结点数为(A)
n+1
n-1
2n
n/2
对下列二叉树进行前序遍历的结果为(C)
DYBEAFCZX
YDEBFZXCA
ABDEYCFXZ
ABCDEFXYZ
下面叙述正确的是。(C)
算法的执行效率与数据的存储结构无关
算法的空间复杂度是指算法程序中指令(或语句)的条数
算法的有穷性是指算法必须能在执行有限个步骤之后终止
以上三种描述都不对
以下数据结构中不属于线性数据结构的是 o (C)
队列
线性表
二叉树
栈
在一棵二叉树上第5层的结点数最多是。(B)
8
16
32
15
算法的时间复杂度是指 o (C)
执行算法程序所需要的时间
算法程序的长度
算法执行过程中所需要的基本运算次数
算法程序中的指令条数
T列叙述中正确的是 o (A)
线性表是线性结构
栈与队列是非线性结构
线性链表是非线性结构
二叉树是线性结构
设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为- (B)
349
350
255
351
算法的空间复杂度是指 o (D)
算法程序的长度
算法程序中的指令条数
算法程序所占的存储空间
算法执行过程中所需要的存储空间
T列关于栈的叙述中正确的是。(D)
在栈中只能插入数据
在栈中只能删除数据
栈是先进先出的线性表
栈是先进后出的线性表
在深度为5的满二叉树中，叶子结点的个数为。(C)
32
31
16
15
数据的存储结构是指- (B)
数据所占的存储空间量
数据的逻辑结构在计算机中的表示
数据在计算机中的顺序存储方式
存储在外存中的数据
在下列选项中，哪个不是…个算法一般应该具有的基本特征 - (C)
确定性
可行性
无穷性
拥有足够的情报
希尔排序法属于哪一种类型的排序法 o (B)
交换类排序法
插入类排序法
选择类排序法
建堆排序法
下列关于队列的叙述中正确的是 o (C)
在队列中只能插入数据
在队列中只能删除数据
队列是先进先出的线性表
队列是先进后出的线性表
对长度为N的线性表进行顺序查找，在最坏情况下所需要的比较次数为 o(B)
N+l
N
(N+l)/2
N/2
在计算机中，算法是指 o (C)
查询方法
加工方法
解题方案的准确而完整的描述
排序方法
栈和队列的共同点是 o (C)
都是先进后出
都是先进先出
只允许在端点处插入和删除元素
没有共同点
巳知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是
。(A)
cedba
acbed
decab
deabc
在下列几种排序方法中，要求内存量最大的是- (D)
插入排序
选择排序
快速排序
归并排序
数据结构中，与所使用的计算机无关