一、选择题(30分)

1． 设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（ D ）。
(A) 20 (B) 30 (C ) 40 (D) 45

W=(2+3)*3+(4+5+6)*2=45

2．执行一趟快速排序能够得到的序列是（ A ）。
(A) [41，12，34，45，27] 55 [72，63]
(B) [45，34，12，41] 55 [72，63，27]
© [63，12，34，45，27] 55 [41，72]
(D) [12，27，45，41] 55 [34，63，72]

前面的比55小 后面的比55大

3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A ）。
(A) head==0 (B) head->next= =0
© head->next= =head (D) head!=0

有头结点的判空条件为头结点指向空，无头结点的判空条件为头结点为空。

4．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（A ）。
(A) 堆排序 (B) 冒泡排序 © 希尔排序 (D) 快速排序

堆排序不受数据初始状态影响而恒为O(nlog2n)

5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（B ）。
(A) 空或只有一个结点 (B) 高度等于其结点数
© 任一结点无左孩子 (D) 任一结点无右孩子

先序 MLR
后序 LRM
高度等于结点数

6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（ D ）。
(A) 堆排序 (B) 冒泡排序 © 快速排序 (D) 希尔排序

7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（ B ）。
(A) 3 (B) 4 © 5 (D) 6

log3n=40 n最小为4

8．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（ A）。
(A) O(n) (B) O(n2) © O(n1/2) (D) O(1og2n)

查找即读取元素，时间复杂度不论在链式线性表/顺序线性表，时间复杂度都为O( N)

9．二路归并排序的时间复杂度为（ C ）。
(A) O(n) (B) O(n2) © O(nlog2n) (D) O(1og2n)

归并排序的时间复杂度为nlog2n

10. 深度为k的完全二叉树中最少有（ B ）个结点。
    

2^(k-1)~2 ^k-1

11.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（C ）。
(A) front->next=s；front=s； (B) s->next=rear；rear=s；
© rear->next=s；rear=s； (D) s->next=front；front=s；

先将s指向队尾指针，然后让队尾指针指向s

12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（ ）。
(A) O(n+e) (B) O(n2) © O(ne) (D) O(n3)

无向图的邻接表的顶点数为n，非头结点数为e，所以时间复杂度为n+e

13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（ B）个叶子结点。
(A) 99 (B) 100 © 101 (D) 102

2*n-1=199，得n=100（n为叶子节点数）

14.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（ D ）。
(A) O(n) (B) O(n2) © O(nlog2n) (D) O(1og2n)

本题考查的是二分查找的时间复杂度

15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（ B ）。
(A) 第i行非0元素的个数之和 (B) 第i列非0元素的个数之和
© 第i行0元素的个数之和 (D) 第i列0元素的个数之和

入度为列，出度为行。

二、判断题

1、调用一次深度优先遍历可以访问到图中的所有顶点。（ ）

错。如果是无向的连通图或者有向的强连通图,是对的,对于无向的非连通图就不可能一次遍历访问到所有顶点了,对于有向的非强连通图则有可能对,有可能不对.

2、分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（ ）

对。索引分块查找就类似于图书馆的索引，我们先找到第几楼，再找第几个书架，然后再找书。
分块查找就是先找到目标所在的数据块，然后块内查找。因此跟表中元素个数和块中元素个数都有关。

3、冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（ ）

正确

4、满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ）

正确。满耳二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。

5、设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（ ）

错误。必须要有中

6、层次遍历初始堆可以得到一个有序的序列。（ ）

错误。要先进行堆排序。

7、设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（ ）

正确。
树转化为二叉树过程如下：
1.加线：各兄弟节点之间用虚线连接
2.去线：对各个节点仅保留它与最左孩子的连线，抹去它与其他孩子节点的连线
3.旋转：把虚线改为实线，顺时针旋转45度。
由于是树而不是森林，只有一个根节点，根节点无兄弟，故转换后只有左子树，右子树为空。

8、线性表的顺序存储结构比链式存储结构更好。（ ）

错。要分情况。

9、中序遍历二叉排序树可以得到一个有序的序列。（ ）

对。左根右，左边的都比根结点小，右边的都比根结点大。

10、快速排序是排序算法中平均性能最好的一种排序。（ ）

对。就平均时间而言，快速排序是目前被认为是最好的一种内部排序方法。——>《数据结构（C语言版）》，严蔚敏 吴伟民著

三、填空题

O（n）

2、设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为_________（设结点的指针
域为next）。

s->next=p->next;p->next=s

3、设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，< 3,2>，< 3,5>}，
则给出该图的一种拓扑排序序列__________。

(1，3，2，4，5) 画出图即可知

4、设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。

n-1.
对任意一个顶点，除了它自己之外的顶点有n-1个，这个顶点最多与其他n-1个顶点相连，此时度最多为n-1

5、设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。

129
N0=N2+1
N2=49
N=50+30+49=129

6、设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________。

为空是相等，满是Q.front==(Q.rear+1)%m

7、设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________。

p->lchild0&&p->rchild0

8、简单选择排序和直接插入排序算法的平均时间复杂度为___________。

O(n2)

9、快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。

O(nlog2n)， O(n)

10、散列表中解决冲突的两种方法是_____________和_____________。

开放地址法和链接法

四、算法设计题

１．设计在顺序有序表中实现二分查找的算法。

#include<bits/stdc++.h>
using namespace std;
struct record {int key;
};
int bisearch(struct record r[], int k) {int n;//有序表中的元素个数int low = 0, mid, high = n - 1;while (low <= high) {mid = (low + high) / 2;if (r[mid].key == k) return (mid + 1);else if (r[mid].key > k) high = mid - 1;else low = mid + 1;}return 0;
}

２．设计判断二叉树是否为二叉排序树的算法。

首先复习一下二叉排序树的知识点。
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
满足上述性质的树称为二叉排序树

#include<bits/stdc++.h>
using namespace std;
int minnumber = -11111;
int flag = 1;
typedef struct node {int key;struct node* left, * right;
} bitree;
void check(bitree* t) {if (t != 0) {//如果t非空check(t->left);//检查左子树if (minnumber > t->key)flag = 0;//左子树上的值都小于根结点 否则 flag置为0minnumber = t->key;//将根结点设置为最小值check(t->right);//所有右子树上的结点都大于根结点}
}

３．在链式存储结构上设计直接插入排序算法

void straightinsertsort(lklist *&head)
{lklist *s,*p,*q;int t;if (head==0||head->next==0) return;else{for(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next) if(s->data>p->data) break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next; s->next=p;t=p->data;p->data=s->data;s->data=t;}}} 
}