本题将会在比赛结束后统一评测
单选题
1
下列排序方法中，稳定的排序方法是____。
A．选择排序 B. 快速排序 C．冒泡排序 D. 堆排序
2
若在有序序列中采用折半查找方法进行查找，用来描述该查找过程的“判定树”的形状与____有关。
A．序列中元素的值
B．序列中元素的排列次序
C．序列中元素的类型
D．序列中元素的个数
3
有一无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,d),(c,f),(f,d),(e,c)}，则下面的顶点序列中____是该图深度优先遍历的一个正确的输出序列。
A. a,b,e,c,d,f
B. a,c,f,e,b,d
C. a,e,b,f,c,b
D. a,e,c,f,d,b
4
一有向带权图如下图所示，若采用迪杰斯特拉（Dijkstra）算法求源点a到其他各顶点的最短路径，得到的各最短路径的目标顶点顺序是____。
A. b, c, d, e, f
B. b, c, f, e, d
C. c, e, b, d, f
D. b, c, f, d, e
5
下列说法中，错误的是____。
A, 具有 n 个点的无向连通图的邻接矩阵至少有 2n-1 个非零元素
B. 若有向图采用邻接表的存储方式，则其第i个链表中边结点个数是第i个顶点的出度。
C. 对于给定的带权连通无向图，从某源点到图中各顶点的最短路径构成的生成树可能是该图的最小生成树。
D. 包含具有n个顶点的连通图G的全部n个顶点,仅包含其n-1条边的极小连通子图称为G的一个生成树。
6
以下删除链表中 p 指针所指结点的下一个结点的语句正确的是____。
A. free(p->link); p->link = NULL;
B. p->link = p->link->link; free(p->link);
C. free(p->link); p->link = p->link->link;
D. q = p->link; p->link = q->link; free(q);
7
栈和队分别是什么类型的数据结构？
A. 先进先出 先进后出
B. 先进后出 先进先出
C. 后进先出 随机读取
D. 随机读取 后进后出
8
若五个元素的出栈序列为 1,2,3,4,5，则下列出栈序列不可能是该栈的入栈序列的是____。
A. 1,2,3,4,5
B. 3,2,1,5,4
C. 2,3,1,4,5
D. 1,2,4,3,5
9
若有以下说明和语句:
struct elevator{
int id;
int floor;
struct {
char name[20];
char tar;
} passenger;
};
struct elevator elevators[2] = {{1, 2, {"Red", 'q'}}, {4, 5, {"X_ele", 'e'}}};
struct elevator *p = elevators;
则以下对语句与输出不符的是
A. printf("%d\n", (p+1)->id);，输出 4
B. printf("%d\n", strlen(p->passenger.name));，输出 3
C. printf("%c\n", *((*p).passenger.name+2));，输出 e
D. printf("%c\n", (*(p+1)).passenger.tar);，输出 e
10
设 p 指针指向单链表（单链表长度为n）中的某个结点（p!=NULL）,若只知道指向该单链表第一个结点的指针和 p 指针，则在 p 指针所指结点之前和 p 指针所指结点之后插入一个结点的时间复杂度分别是。
A. 和
B. 和
C. 和
D. 和
填空题
11
设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6、e7依次进栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2、e3、e6、e7、e5、e4，e1，则栈S的容量与队列Q的容量之和至少应该是____。
12
设有一组记录的关键字为{6, 42, 27, 19, 28, 17, 43, 10, 45, 26, 31, 21, 39, 9}，⽤用链地址法构造散列列表，散列列函数为 H(key)=key MOD 13，则散列列地址为 6 的链中有____个结点。
13
已知二叉树的前序序列为：ABCDEFGHIJ，中序序列为：ACEDFBIHJG，则其后序序列为____。
14
若用一个大小为20的数组（下标从0开始）来实现循环队列，且当前rear和front的值分别为18和10，当从队列中出队两个元素，再入队五个元素后，rear和front的值分别为____。
15
对于上图所示的无向连通图，若采用普里姆（Prim）算法求其最小生成树，假设第一个选择加入最小生成树的顶点为V2，则最后一条加入最小生成树的边的权值为____。
16
表达式 a+b/(c-d)-e*f 的后缀表达式是____。
17
若以 {2, 3, 4, 8, 12, 13} 作为叶子结点的权值构造哈夫曼树，则其带权路径长度是____。
18
若一颗完全二叉树最深层有 14 个叶子节点，则其至少有____个度为 1 的节点。
19
假设采⽤用快速排序算法按照从小到大的顺序对 10 个数据元素进⾏行行排序，这 10 个数据的初始状态为 (44, 32, 19, 31, 47, 26, 34, 48, 30, 26)，若第⼀次选⽤用第一个数据 44 作为分界元素，则第一趟排序后，分界元素 44 前有____个数据元素。
20
如果输入的序列是 e1,e2,e3,e4,e5,e6,e7,e8,e9，如果使用多个队列，使其出队的序列为 e8,e4,e2,e5,e3,e9,e1,e6,e7，则至少需要____个这样的队列。（要求：输入的元素可以选择进入任何一个队列，但是每个队列都需要遵循先入先出的原则。）
