计算机二级考试练习题.docxVIP

计算机二级考试练习题

选择题

1.以下哪种数据结构不属于线性结构？

A.栈

B.队列

C.二叉树

D.线性表

答案：C。线性结构的特点是数据元素之间存在一对一的线性关系。栈和队列都是特殊的线性表，属于线性结构。线性表本身也是线性结构。而二叉树是树形结构，数据元素之间是一对多的关系，不属于线性结构。

2.以下关于算法的时间复杂度，说法正确的是？

A.时间复杂度是指算法执行所需要的具体时间

B.时间复杂度是指算法执行所需要的基本运算次数

C.时间复杂度是指算法中所有语句的执行次数之和

D.时间复杂度是指算法在最坏情况下的执行时间

答案：B。算法的时间复杂度是指算法执行所需要的基本运算次数，它反映了算法的执行效率随问题规模增长的变化趋势，而不是具体的执行时间，也不是所有语句执行次数之和，虽然最坏情况时间复杂度是时间复杂度分析的一种，但不能简单说时间复杂度就是最坏情况下的执行时间。

3.在数据库系统中，数据的物理独立性是指？

A.数据库与数据库管理系统的相互独立

B.用户程序与数据库中数据的逻辑结构相互独立

C.用户程序与存储在磁盘上数据库中的数据是相互独立的

D.应用程序与数据库中数据的存储结构相互独立

答案：D。数据的物理独立性是指应用程序与数据库中数据的存储结构相互独立，即当数据的存储结构改变时，应用程序不用改变。数据的逻辑独立性是指用户的应用程序与数据库的逻辑结构是相互独立的，即当数据的逻辑结构改变时，用户程序也可以不变。

4.以下哪种排序算法的平均时间复杂度为$O(nlogn)$？

A.冒泡排序

B.插入排序

C.快速排序

D.选择排序

答案：C。冒泡排序、插入排序和选择排序的平均时间复杂度都是$O(n^2)$，而快速排序的平均时间复杂度为$O(nlogn)$。

填空题

1.计算机中常用的存储单位有字节（Byte），1KB=______Byte。

答案：1024。在计算机中，1KB=1024Byte，1MB=1024KB，1GB=1024MB等。

2.若一个栈的输入序列为1,2,3,4，那么不可能的输出序列是______（写出一个即可）。

答案：4,1,2,3。对于栈的操作，后进先出。当4第一个出栈时，说明1、2、3、4都已入栈，此时出栈顺序只能是4、3、2、1，所以4,1,2,3是不可能的输出序列。

3.在关系数据库中，一个关系就是一个______。

答案：二维表。关系数据库采用关系模型，一个关系对应一张二维表，表中的行称为元组，列称为属性。

4.设二叉树的前序遍历序列为ABCDE，中序遍历序列为BADCE，则后序遍历序列为______。

答案：BDECA。根据前序遍历（根左右）和中序遍历（左根右）可以确定二叉树的结构。前序遍历的第一个元素A是根节点，在中序遍历中A左边的B是左子树节点，右边的DCE是右子树节点。然后对左子树和右子树分别重复上述过程，构建出二叉树后，得到后序遍历（左右根）序列为BDECA。

判断题

1.数组是一种静态数据结构，一旦定义其大小就不能改变。（）

答案：正确。数组在定义时需要指定大小，在程序运行过程中其大小通常不能动态改变，属于静态数据结构。

2.数据库管理系统是数据库系统的核心。（）

答案：正确。数据库管理系统（DBMS）负责对数据库进行管理，包括数据的定义、存储、查询、更新等操作，是数据库系统的核心组成部分。

3.所有的递归算法都可以转换为非递归算法。（）

答案：正确。递归算法是通过函数自身调用实现的，很多递归算法可以使用栈等数据结构将其转换为非递归算法，只是实现的复杂度和难度可能不同。

4.线性表的顺序存储结构比链式存储结构更节省存储空间。（）

答案：错误。线性表的顺序存储结构需要预先分配连续的存储空间，可能会存在空间浪费的情况；而链式存储结构是动态分配存储空间，只有在需要时才分配节点空间，相对更灵活，在某些情况下可能更节省存储空间。

解答题

1.简述冒泡排序的基本思想，并写出其Python代码实现。

答案：冒泡排序的基本思想是：重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

以下是Python代码实现：

```python

defbubble_sort(arr):

n=len(arr)

foriinrange(n):

forjinrange(0,ni1):

ifarr[j]arr[j+1]: