北航算法与数据结构复习题

北航算法与数据结构复习题

北航《算法与数据结构》复习题

单选题（每小题2分，总分10分）

1、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（D ）

A、必需是联系的

B、部分地址必须是连续的

C、一定是不连续的

D、连续不连续都可以

2、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以什么为标准操作（B）

A、条件判断

B、结点移动

C、算术表达式

D、赋值语句

3、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B ）

A、p->next=s;s->next=p->next;

B、s->next=p->next;p->next=s;

C、p->next=s;p->next=s->next;

D、p->next=s->next;p->next=s;

4、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（C ）

A、(2,5,12,16)26(60,32,72)

B、(5,16,2,12)28(60,32,72)

C、(2,16,12,5)28(60,32,72)

D、(5,16,2,12)28(32,60,72)

5、稀疏矩阵的压缩存储方法是只存储（A ）

A、非零元素 B、三元组（i,j, aij）

C、aij

D、i,j

1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（A）排序法。

A、插入

B、选择

C、希尔

D、二路归并

2、用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（D ）

A、一定都是同义词

B、一定都不是同义词

C、都相同

D、不一定都是同义词

3、将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为（D ）

A、42

B、40

C、21

D、20

4、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B ）

A、不确定

B、n-i+1

C、I

D、n-i

5、设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（C）个

A、k+1

B、2k

C、2k-1

D、2k+1

判断题（每小题1分，总分10分）(A==对，B==错)

6、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。（B）

7、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大（B）

8、任何一棵二叉树都可以不用栈实现前序线索树的前序遍历（A）

9、在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。（B ）

10、线索二叉树中的每个结点通常包含有5个数据成员。（A ）

11、从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为选择排序（B ）

12、在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序（A ）

13、不是所有的AOV网都有一个拓朴序列（A ）

14、对于前序遍历和中序遍历结果相同的二叉树为所有结点只有右孩子的二叉树（A ）

15、邻接多重表示法对于有向图和无向图的存储都适用（A ）

6、在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。（A ）

7、排序算法中的比较次数与初始元素序列的排列无关（B ）

8、队列逻辑上是一个下端和上端既能增加又能减少的线性表（A ）。 9、对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。（A ）

10、给定一棵树，可以找到唯一的一棵二叉树与之对应（A ）

11、字符串是一种线性表，其特殊性表现在它的数据元素是一个字符（A ）

12、由权值为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度44 （A ）

13、判断一个表达式中左右括号是否匹配，采用栈实现较为方便（A ）

14、算法在发生非法操作时可以作出处理的特性称为健壮性（A）

15、快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少（B ）

多选题（每小题2分，总分10分）

16、对于单链表表示法，以下说法正确的是（ABC ）

A、指向链表的第一个结点的指针，称为头指针

B、单链表的每一个结点都被一个指针所指

C、任何结点只能通过指向它的指针才能引用

D、尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表

17、对有序表的查找方式有以下几种（ABC ）

A、折半查找

B、斐波那契查找

C、插值查找

D、二叉树查找

18、递归过程中要保存的信息包括（ABC ）

A、返回地址

B、本次调用中与形参结合的实参值

C、本次递归调用中的局部变量值

D、执行结果

19、以下说法正确的是（ABD ） A、二叉树可以是空集

B、二叉树的任一结点至多有两棵子树

C、二叉树与树具有相同的树形结构

D、二叉树的子树有次序之分

20、以下说法正确的是（ABD ）

A、对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）

B、读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构

C、在链表上实现读表元运算的平均时间复杂性为O（1）

D、插入、删除操作在链表上的实现可在O（1）时间内完成

16、以下不稳定的排序方法是（ACD ）

A、快速排序

B、冒泡排序

C、希尔排序

D、堆排序

17、以下说法正确的是（ABD ）

A、直接插入排序的空间复杂度为O(1)

B、快速排序附加存储开销为O(log2n)

C、堆排序的空间复杂度为O(n)

D、二路归并排序的空间复杂度为O(n)

18、图的存储结构有（ABCD ）

A、邻接矩阵

B、邻接表

C、数组表示法

D、十字链表

19、属于插入排序的排序方法有（ABC ）

A、直接插入排序

B、对半插入排序

C、渐减增量排序 D、冒泡排序

20、二叉树的遍历方式有（ABC ）

A、先序遍历

B、中序遍历

C、后序遍历

D、线索遍历

简答题（每小题15分，总分30分）

1、类C语言与标准C语言的主要区别是什么?

类C语言只是在C语言编程过程中的一个思路的编写过程

2、请用类C语言描述链串的类型定义。

*[fhl注释：]代码后面的文字是解释说明，如果题目不要求解释，可以不写。

3、叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结点的作用。

链表里有“头指针”变量,它存放一个地址,该地址指向一个元素。链表里的每个元素称为“节点”。

头指针是指向链表中第一个结点的指针。head是头指针，而不是头结点，它只占用4字节大小空间(如果是32位)

头节点是链表中第一个有效的节点，而不是用来存储第一个节点地址的头节点

首结点是指链表中存储第一个数据元素的节点。

头结点是在首节点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元节

点，其作用主要是为了方便对链表的操作。它可以对空表、非空表一级首元节点的操作技能型统一处理。

4、简述二次探测法解决冲突的基本思想。 二次探查采用的形式如下：

h(k,i)=(h’(k)+c1i+c2i)modm

其中h’是一个辅助散列函数，c1和c2为辅助常数，i=0,1,…m-1。处事的探查位置为T[h’(k)],后续的探查位置要在此基础上加上一个偏移量，该偏移量是以二次的方式依赖于探查号i的。如果两个关键字的初始探查位置是相同的，那么他们的后续二次探查的序列也是相同的。这种性质会导致一种程度较轻的群集现象，成为二次群集。

简单地说就是遇到冲突,就以n^2,n=1,2,...的序列探查,如果找到首个没有冲突的位置,就插入,否则继续探查.

5、算法的设计要求有哪些？

1、正确性

2、可读性；

3、健壮性

4、效率与低存储量需求

6、图的存储有几种方式？

1、数组表示法

2、邻接表表示法

3、十字链表

4、链接多重表

7、简述开散列表的组织方式及类型定义

8、简述循环队列的类型定义 9、简述闭散列表的类型定义

分析题（每小题20分，总分40分）

1、编程实现单链表的测长。

答案：

/*单链表的测长*/

int length(node *head)/*返回单链表长度*/

{

int len = 0;

node *p;/*新建一个节点指针*/

p = head->next;/*指针指向头节点的下一个节点*/

while(p != NULL)/*遍历链表*/

{

len++;

p = p->next;

}

return len;

}

/*由于链表末尾节点的next指针被置为NULL，

因此可以使用while循环进行遍历链表所有节点，

当遇到NULL时结束循环*/

2、完成以下递归算法，它将二叉树中所有结点的左、右子树相互