北航大学考研真题及答案.docVIP

北航大学考研真题及答案

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

1.以下哪种不属于数据结构的逻辑结构？

A.线性结构

B.树形结构

C.顺序结构

D.图形结构

2.算法的时间复杂度主要取决于？

A.问题规模

B.数据量

C.程序语句数量

D.硬件性能

3.链表中删除一个节点的时间复杂度是？

A.O(1)

B.O(n)

C.O(logn)

D.O(n^2)

4.栈的特点是？

A.先进先出

B.后进后出

C.先进后出

D.随机进出

5.队列的操作遵循？

A.先进先出

B.后进后出

C.先进后出

D.随机进出

6.深度为5的完全二叉树最少有多少个节点？

A.15

B.16

C.31

D.32

7.对有序数组进行二分查找的时间复杂度是？

A.O(1)

B.O(n)

C.O(logn)

D.O(n^2)

8.以下哪个排序算法不稳定？

A.冒泡排序

B.选择排序

C.插入排序

D.归并排序

9.哈希表的平均查找长度取决于？

A.哈希函数

B.哈希表大小

C.装填因子

D.以上都是

10.数据结构中存储数据的基本单位是？

A.数据项

B.数据元素

C.数据对象

D.数据类型

答案：1.C2.A3.A4.C5.A6.B7.C8.B9.D10.B

多项选择题（每题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.ABC2.ABCD3.AB4.ABCD5.ABC6.ABC7.AB8.ABCD9.ABCD10.ABCD

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

1.数据结构中逻辑结构相同，存储结构也一定相同。（）

2.算法的时间复杂度和空间复杂度一定成正比。（）

3.链表中节点的存储地址一定是连续的。（）

4.栈和队列都是特殊的线性表。（）

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

6.对无序数组只能进行顺序查找。（）

7.快速排序是稳定的排序算法。（）

8.哈希表一定不会产生冲突。（）

9.数据元素是数据的最小单位。（）

10.算法可以没有输入。（）

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

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

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

顺序存储优点是存储密度大，缺点是插入删除效率低；链式存储优点是插入删除灵活，缺点是存储密度小，需额外指针空间。

2.简述深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的区别。

深度优先有哪些信誉好的足球投注网站沿着一条路径深入，直到无法继续或找到目标；广度优先有哪些信誉好的足球投注网站按层次依次扩展节点。

3.简述排序算法中选择排序的基本思想。

每次从未排序序列中选择最小（大）元素，与未排序序列的第一个元素交换。

4.简述哈希表的基本原理。

通过哈希函数将关键字映射为哈希地址，存储在哈希表中，通过哈希函数和冲突解决方法快速查找数据。

讨论题（总4题，每题5分）

1.讨论数据结构在软件开发中的重要性。

数据结构是软件的基础，合理的数据结构可提高程序效率、降低复杂度，便于数据的组织、存储和操作，影响软件性能和可维护性。

2.讨论不同排序算法在不同场景下的应用。

如对少量数据可选用简单的插入排序；对大量数据且要求稳定性可选用归并排序；对平均情况效率高可选用快速排序等。

3.讨论哈希冲突对哈希表性能的影响及解决方法的合理性。

哈希冲突会降低查找效率，解决方法如开放定址法、链地址法等，各有优缺点，合理选择可平衡性能与资源开销。

4.讨论线性结构和非线性结构在