广东数据结构自考试题及答案.docVIP

广东数据结构自考试题及答案

一、单项选择题（每题2分，共10题）

1.线性表采用顺序存储结构，访问第i个元素的时间复杂度为（）

A.O(1)B.O(n)C.O(logn)D.O(n2)

2.栈的特点是（）

A.先进先出B.先进后出C.随机进出D.只能进不能出

3.队列的“先进先出”特性是指（）

A.最早插入队列中的元素总是最后被删除

B.当同时进行插入、删除操作时，总是插入操作优先

C.每当有删除操作时，总是要先做一次插入操作

D.插入操作必须在删除操作之前进行

4.对n个记录的文件进行冒泡排序，所需要的辅助存储空间为（）

A.O(1)B.O(logn)C.O(n)D.O(n2)

5.具有n个顶点的无向图最多有（）条边。

A.n(n-1)B.n(n-1)/2C.n2D.n(n+1)/2

6.一棵完全二叉树中有1001个结点，其中叶子结点的个数是（）

A.499B.500C.501D.505

7.散列函数有一个共同性质，即函数值应当以（）概率取其值域的每个值。

A.最大B.最小C.平均D.同等

8.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（）存储方式最节省时间。

A.顺序表B.单链表C.双链表D.单循环链表

9.快速排序在最坏情况下的时间复杂度为（）

A.O(nlogn)B.O(n2)C.O(n)D.O(1)

10.二叉树的第i层上最多含有结点数为（）

A.2iB.2i-1C.2i-1D.2i-2

二、多项选择题（每题2分，共10题）

1.以下属于线性结构的有（）

A.栈B.队列C.二叉树D.图

2.顺序存储结构的优点有（）

A.存储密度大B.插入、删除操作效率高

C.可以随机存取D.逻辑上相邻的元素物理上也相邻

3.下列排序算法中，平均时间复杂度为O(nlogn)的有（）

A.快速排序B.归并排序C.堆排序D.冒泡排序

4.图的存储结构有（）

A.邻接矩阵B.邻接表C.十字链表D.邻接多重表

5.以下关于栈的描述正确的有（）

A.栈是一种操作受限的线性表B.栈只允许在一端进行插入和删除操作

C.栈的操作遵循先进先出原则D.栈可以用于表达式求值

6.对二叉树遍历的方式有（）

A.前序遍历B.中序遍历C.后序遍历D.层次遍历

7.哈希表冲突处理的方法有（）

A.开放定址法B.链地址法C.再哈希法D.建立公共溢出区

8.下列关于线性表的说法正确的是（）

A.线性表可以为空B.线性表中的元素必须是同一数据类型

C.线性表中元素的个数可以是无限的D.线性表的顺序存储结构和链式存储结构都可以随机访问

9.以下哪些是稳定的排序算法（）

A.冒泡排序B.插入排序C.归并排序D.选择排序

10.树的存储结构有（）

A.双亲表示法B.孩子表示法C.孩子兄弟表示法D.顺序存储法

三、判断题（每题2分，共10题）

1.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）

2.栈和队列都是限制存取点的线性结构。（）

3.二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树。（）

4.图的深度优先遍历和广度优先遍历都需要借助队列来实现。（）

5.快速排序在任何情况下的时间复杂度都是O(nlogn)。（）

6.哈希表是一种根据关键码值直接访问的数据结构。（）

7.对于一个有向图，若采用邻接矩阵存储，则第i行的非零元素个数等于顶点i的出度。（）

8.完全二叉树一定是满二叉树。（）

9.插入排序是一种稳定的排序算法。（）

10.线性表的链式存储结构不便于随机存取。（）

四、简答题（每题5分，共4题）

1.简述栈和队列的主要区别。

答：栈是先进后出，只允许在一端进行插入和删除操作；队列是先进先出，在一端插入，另一端删除。

2.简述二叉树的性质。

答：二叉树第i层最多有2i-1个结点；深度为k的二叉树最多有2k-1个结点；对任何二叉树，度为0的结点比度为2的结点多1个。

3.简述哈希表中处理冲突的开放定址法。

答：开放定址法就是当发生