内容发布更新时间 : 2024/12/26 23:37:12星期一 下面是文章的全部内容请认真阅读。
要求：所有的题目的解答均写在答题纸上，需写清楚题目的序号。每张答题纸都要写上姓名和学号。
一、单项选择题（每小题2分，共20小题，共计40分）
1、设n是描述问题规模的非负整数，下面程序片段的时间复杂度为（ ）。 x=1;
while (x<=n) x=5*x; A. O(log5n)
B.O(n)
C.O(nlog5n)
D.O(n5)
2、顺序表和链表相比存储密度较大，这是因为（ ）。 A.顺序表的存储空间是预先分配的
B.顺序表不需要增加指针来表示元素之间的逻辑关系 C.链表中所有节点的地址是连续的
D.顺序表中所有元素的存储地址是不连续的
3、在长度为n（n≥1）的循环双链表L中，在尾节点之后插入一个新节点的时间复杂度为（ ）。
A. O(n2)
B.O(n)
C. O(1)
D.O(nlog2n)
4、设栈的输入序列是1、2、3、4，则（ ）不可能是其出栈序列。
A.1，2，4，3 B.2，1，3，4 C.1，4，3，2 D.4，3，1，2 5、当用一个数组data[0..n-1]存放栈中元素时，栈底最好（ ）。 A. 设置在data[0]或data[n-1]处 B.设置在data[n-1]处 C. 设置在data[0]处 D.设置在data数组的任何位置
6、在数据处理过程中常需要保存一些中间数据，如果先保存的数据先处理，则使用（ ）来保存这些数据。
A.线性表 B. 队列 C. 栈 D.单链表
7、在环形队列中，元素的排列顺序（ ）。 A.与队头和队尾指针的取值有关 B.与元素值的大小有关 C.由元素进队的先后顺序确定 D.与存放队中元素的数组大小有关 8、将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。 A.100 B.40 C.80 D.55 9、设目标串为s，模式串为是t，在KMP模式匹配中，next[4]=2的含义是（ ）。 A.表示t4字符前面最多有2个字符和开头的2个字符相同 B.表示s4字符前面最多有2个字符和开头的2个字符相同 C.表示目标串匹配失败的位置是i=4 D.表示模式串匹配失败的位置是j=2
10、由权值分别为9、2、7、5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长
度为（ ）。
A.23
B.44 C.37 D.27
11、对于无向图的邻接矩阵来说，（ ）。
A.第i行上、第i列上非零元素总数等于顶点i的度数 B.矩阵中的非零元素个数等于图中的边数
C.第i行上的非零元素个数和第i列的非零元素个数一定相等 D.邻接矩阵中非全零行的行数等于图中的顶点数
12、有一个顶点编号为0～4的带权有向图G，现用Floyd算法求任意两个顶点之间的最短路径，在算法执行的某时刻，已考虑了0～2的顶点，现考虑顶点3，则以下叙述中正确的是（ ）。
A.只可能修改从顶点0～2到顶点3的最短路径 B.只可能修改从顶点3到顶点0～2的最短路径 C.只可能修改从顶点0～2到顶点4的最短路径 D.所有两个顶点之间的路径都可能被修改
13、适合于折半查找的数据组织方式是（ ）。 A.以顺序表存储的有序线性表 B.以顺序表存储的线性表 C.以链表存储的有序线性表 D. 以链表存储的线性表
14、对含有n个元素的顺序表采用顺序查找方法，不成功时的比较次数是（ ）。 A. 1
B. n
C. n-1
D. n+1
15、在一棵平衡二叉树中，每个节点的平衡因子的取值范围是（ ）。 A. 1～2 B. -2～2 C. -1～1 D. 0～1
16、在一棵m阶B-树中删除一个关键字会引起合并，则该节点原有（ ）个关键字。 A. 1 B. ?m/2? C. ?m/2?+1 D. ?m/2?-1 17、以下关于哈希查找的叙述中正确的是（ ）。 A.哈希查找中不需要任何关键字的比较
B.采用拉链法解决冲突时，查找每个元素的时间是相同的 C.哈希表在查找成功时的平均查找长度仅仅与表长有关
D.哈希表的装填因子等于表中填入的记录数除以哈希表的长度
18、以下排序方法中，（ ）在初始序列已基本有序的情况下，排序效率最高。 A.二路归并排序 B. 快速排序 C. 直接插入排序 D.堆排序 19、如要在1000个整数中找出前10个最小的整数，在以下排序方法中最好采用（ ）。 A.直接插入排序 B. 冒泡排序 C.二路归并排序 D. 希尔排序 20、有n个十进制整数进行基数排序，其中最大的整数为5位，则基数排序过程中临时建立的队数个数是（ ）。
A.10
B.n
C.5
D.2
二、问答题（共4小题，共计35分）
1、（8分）已知一棵二叉树的先序遍历序列为ABDGHCEIF，它的中序遍历序列是BGDHAEICF，请构造出这棵二叉树，并给出其层次遍历序列。
2、（8分）一棵二叉排序树的结构如图1所示，其中各结点的关键字依次为32～40，请标出各结点的关键字。
图1 一棵二叉排序树的结构
3、（8分）一组记录关键字为（5，11，7，2，3，17），利用堆排序方法建立初始大根堆，给出你建立的初始大根堆对应的关键字序列。
4、（11分）对于一个带权连通无向图G，可以采用Prim算法构造出从某个顶点v出发的最小生成树，问该最小生成树一定包含从顶点v到其他所有顶点的最短路径吗？如果回答是，请予以证明；如果回答不是，请给出反例。
三、算法设计题（共2小题，共计25分）
1. （15分）有两个递增有序表，所有元素为整数，均采用带头结点的单链表存储，结点类型定义如下：
typedef struct node {
int data;
struct node *next;
} LinkNode;
设计一个尽可能高效的算法，将两个递增有序单链表ha、hb合并为一个递减有序单链表hc，要求算法空间复杂度为O(1)。
2、（10分）设二叉树中每个结点存放单个字符，其结点类型如下：
typedef struct node { char data;
struct node *lchild，*rchild; } BTNode;
设计一个算法求其中单分支的结点个数。