北华大学数据结构考研真题及答案.docVIP

北华大学数据结构考研真题及答案

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

1.数据结构中，与所使用的计算机无关的是数据的（）。

A.存储结构

B.物理结构

C.逻辑结构

D.物理和存储结构

2.线性表的顺序存储结构是一种（）。

A.随机存取的存储结构

B.顺序存取的存储结构

C.索引存取的存储结构

D.散列存取的存储结构

3.栈和队列的共同特点是（）。

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素

D.没有共同点

4.深度为5的完全二叉树的结点数不可能是（）。

A.15

B.16

C.17

D.18

5.若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点（）。

A.只有e

B.有e、b

C.有e、c

D.无法确定

6.对n个关键字进行快速排序，最大递归深度为（）。

A.n

B.n/2

C.log2n

D.nlog2n

7.下列排序方法中，平均时间复杂度为O(nlogn)且空间复杂度为O(1)的是（）。

A.快速排序

B.堆排序

C.归并排序

D.冒泡排序

8.哈希表的平均查找长度主要取决于（）。

A.哈希表的大小

B.数据元素的个数

C.哈希函数和处理冲突的方法

D.装填因子

9.数据的逻辑结构在计算机存储空间中的存放形式称为数据的（）。

A.存储结构

B.物理结构

C.顺序结构

D.链式结构

10.已知一个有序表为(12,18,24,35,47,50,62,83,90,115,134)，当用折半查找法查找值为90的元素时，查找成功的比较次数为（）。

A.1

B.2

C.3

D.4

答案：1.C2.A3.C4.A5.A6.C7.B8.C9.A10.C

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

1.以下属于数据结构的是（）。

A.线性表

B.栈

C.队列

D.树

2.线性表的基本操作有（）。

A.插入

B.删除

C.查找

D.排序

3.栈的基本操作有（）。

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.方便查找

答案：1.ABCD2.ABCD3.ABCD4.ABCD5.ABCD6.ABCD7.ABCD8.ABCD9.ABD10.AB

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

1.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。（）

2.线性表的顺序存储结构中，逻辑上相邻的元素物理上也相邻。（）

3.栈是一种先进先出的线性表。（）

4.队列是一种先进后出的线性表。（）

5.二叉树中每个结点的度不能大于2。（）

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

7.快速排序在最坏情况下时间复杂度为O(n^2)。（）

8.归并排序的空间复杂度为O(n)。（）

9.哈希表的平均查找长度与装填因子无关。（）

10.顺序存储结构的缺点是插入和删除操作效率低。（）

答案：1.√2.√3.×4.×5.√6.×7.√8.√9.×10.√

简答题（总4题，每题5分）

1.简述线性表顺序存储和链式存储的优缺点。

顺序存储优点是存储密度大、可随机存取；缺点是插入删除效率低。链式存储优点是插入删除效率高、无需连续空间；缺点是存储密度小、不可随机存取。

2.简述栈和队列的区别。

栈是先进后出，队列是先进先出。栈只有一个入口和出口，队列有一个入口和一个出口。

3.简述二叉树前序、中序、后序遍历的递