第一部分
1.在一个单链表中，已知指针p 指向其中的某个结点，若在该结点前插入一个由指针s 指向的结点，则需执行（）。

A．s->next = p->next; p->next = s; B．p->next = s; s->next = p; C． r = p->next; p->next = s; s->next = r; D．仅靠已知条件无法实现
2.设顺序表长度为n，从表中删除元素的概率相等。

则在平均情况下，从表中删除一个元素需要移动
的元素个数是（）。

A．(n−1)/2 B．n/2 C．n(n − 1)/2 D．n(n + 1)/2
3.在一个具有n 个单元的顺序栈中，假定以高端（即第n−1 单元）作为栈底，以top 为栈顶指针，则当作出栈运算时，top 变化为（）。

A．top 不变 B．top = 0 C．top-- D．top ++
4.若一个栈以向量V[n]存储，设栈空时，栈顶指针top 为n−1，则下面x 进栈的正确操作是（）。

A．top = top + 1；V[top] = x B．V[top] = x；top = top + 1
C．top = top − 1；V[top] = x D．V[top] = x；top = top − 1
5.经过以下栈运算后，x 的值是（）。

InitStack(s); Push(s, a); Push(s, b);
Pop(s, x); Push(s, c); Pop(s, x); GetTop(s, x);
A. a B．b C．c D．d
6.若一棵二叉树有126 个节点，在第7 层（根结点在第1 层）的结点个数至多有（）。

A．32 B．64 C．63 D．不存在第7 层
7.具有n 个顶点的有向图的边最多有（）。

A．n B．n(n−1) C．n(n+1) D．n2
8.设连通图G 的顶点数为n，则G 的生成树的边数为（）。

A．n B．n−1 C．2n D．2n−1
9.散列查找中k 个关键字具有同一哈希值，若用线性探测法将这k 个关键字对应的记录存入哈希表中，至少要进行（）次探测。

A．k B．k + 1 C．k(k + 1)/2 D.1 + k(k + 1)/2
10.一组记录的关键字为(45，80，55，40，42，85)则利用堆排序的方法建立的初始堆为（）。

A．(80，45，55，40，42，85) B．(85，80，55，40，42，45)
C．(85，80，55，45，42，40) D．(85，55，80，42，45，40)
11. 假设某文件经内部排序得到100 个初始归并段，若要使多路归并三趟完成排序，则应取归并的路数至少为多少？（）。

A．2 B．3 C．4 D．5
第二部分
1. 判断带头结点的线性链表L 是否为空的条件是（）。

A．L.elem=NULL B．L.length = 0 C．L->next=NULL D．L = NULL
2. 设有多项式A 和B 的项数分别为m 和n ，均采用单链表表示，进行A 加B 运算的时间复杂度为（）。

A．O(m )（当m>n 时） B．O(n)（当n>m 时） C．O(m + n) D．O(m *n)
3.若用一个大小为6 的数组来实现循环队列，且当前rear 和front 的值分别为0 和3。

当从队列中删除一个元素，再加入两个元素后，rear 和front 的值分别为（）。

A．1 和5 B．2 和4 C．4 和2 D．5 和1
4.在具有n 个单元的顺序存储的循环队列中，假定front 和rear 分别为队头指针和队尾指针，则队空的条件为（）。

A．rear==front B．(rear+1)%n==front
C．(rear−1)%n=front D．(front+1)%n==rear
5.将一个A[1..100，1..100]的三对角矩阵以行序为主存入一维数组B[1..298]中，元素a[66，65] B 数组中的位置k 等于（）。

A．198 B．197 C．196 D．195
6.由3 个结点可以构造出（）种不同形态的二叉树。

A．3 B．4 C．5 D．6
7.无向图G 是一个连通图，有9 条边，则该图的顶点个量至少为（）。

A．4 B．5 C．6 D．7
8.采用顺序检索的方法检索长度为n 的线性表，则检索每个元素的平均比较次数为（）。

A．n B．n2 C．(n + 1)/2 D．log2(n + 1)
9.表长为25 的散列表，如果采用除留余数法，即按公式H(key) = key mod p 建立哈希函数，则最适宜的p 取值应为（）。

A．23 B．24 C．25 D．26
10.一组记录的关键字为{20，15，14，18，21，36，40，10}，则利用快速排序的方法，以第一个记录为基准得到一次划分结果是（）。

A．10，15，14，18，20，40，36，21 B．10，15，14，18，20，36，40，21 C．10，15，14，20，18，40，36，21 D．15，10，14，18，20，36，40，21
11. 以下关于排序方法的描述，不正确的是（）。

A．排序是将一组记录的任意序列，调整为按关键字“有序”的序列
B．排序方法都是不稳定的
C．排序方法可以分为内部排序和外部排序
D．排序中需要比较关键字的大小
第三部分
1.对于线性链表，在p 所指向的结点后插入由q 指向的新结点的语句序列是（）。

A．p->next = q; q ->next = p->next; B．q = p->next; p->next = q;
C．q->next = p->next; p->next = q; D．p = p->next; q->next = p;
2.向一个栈顶指针为h 的带头结点链栈中插入指针s 所指的结点时，应执行的语句序列是（）。

A．h→next = s； B．s->next = h；
C．s→next = h；h = h→next； D．s→next = h→next；h→next = s；
3.设有一个栈，元素的进栈次序为A，B，C，D，E，下列中不可能的出栈序列是（）。

A．A，B，C，D，E B．B，C，D，E，A
C．E，A，B，C，D D．E，D，C，B，A
4.在一个无头结点的链队列中，假定front 和rear 分别为队头和队尾指针，则删除一个结点的主要操作为（）。

A．front = front→next B．rear = rear→next
C．rear = front→next D．front = rear→next
5.若用一维数组保存一个深度为5、结点个数10 的二叉树，数组的长度至少为（）。

A．10 B．16 C．31 D．64
6.假定在一棵二叉树中，双分支结点数为15 个，单分支结点数为30 个，则叶子结点数
为（）个。

A．15 B．16 C．17 D．47
7.在有向图G 的拓扑序列中，若顶点V i 在顶点V j 之前，则下列情形不可能出现的是（）。

A．G 中有弧<V i，V j> B．G 中有一条从V i 到V j 的路径
C．G 中没有弧<V i,V j> D．G 中有一条从V j 到V i 的路径
8.在对长度为n 的顺序存储的有序表进行折半查找，对应的折半查找判定树的高度为（）。

A．n B．n2 C．log2(n + 1) − 1 D．(n + 1)/2
9.若对n 个元素进行堆排序，则在初始建堆的过程中需要进行（）次筛选。

A．1 B．⎣n/2⎦C．(n−1)/2 D．n
10.有一组数据（15，9，7，8，20，−1，7，4），用堆排序的筛选方法建立的初始堆为（）。

A．−1，4，8，9，20，7，15，7 B．−1，7，15，7，4，8，20，9
C．−1，4，7，8，20，15，7，9 D．A、B、C 均不是
11. 假设一次I/O 的物理块大小为150，每次可对750 个记录进行内部排序，那么，对含有150000 个记录的磁盘文件进行4-路平衡归并排序时，需进行（）次I/O 筛选。

A．5000 B．10000 C．15000 D．20000。