2010福建专升本计科类真题(11)

专升本,福建,计算机,全套,软件工程,入学考试

（C）n+1

（D）0

10、设单链表的类型定义如下：

typedefstruct node{

int element;

struct node *next;

}LinkNode *p,*s;

设p指向链表中某一个结点，将s指向的结点插入到p结点之后的操作是：（）

（A）p->next=s; s->next=p->next;

（B）s->next=p->next; p->next=s;

（C）s->next=p; p->next=s;

（D）p->next=s->next; s->next=p;

11、对于快速排序算法，下列说法正确的是（）

（A）初始序列基本有序的情况，快速排序的性能较差

（B）快速排序算法最好情况下的时间复杂度是O(n*n)

（C）快速排序所需要的附加空间复杂度是O(1)

（D）快速排序是一种选择排序方法

12、设某个图的邻接表如图2，根据该临界表执行从顶点A出发的广度优先搜索算法，则经历的结点顺序为（）

（A）ABCDE

（B）AEDBC

（C）ABCED

（D）ACBDE

二、填空题（本大题共6小题，每空2分，共16分）

13、各时间复杂度表达式为：n!、n*n、log2n、n，按照渐进阶从低到高的顺序排列，则排在第一位的表达式是__________

14、对同样的一组数据，合并、简单选择、直接插入和堆排序中，__________排序对内存容量要求最大。

15、一个无向图的连通分支定义为该图的__________连通子图，任何连通图有__________个连通分支。

16、一棵二叉树有11个度为0的结点，可以知道该二叉树中度为2的结点个数为__________个。

17、设循环队列中对头和队尾指针分别为front、rear，其中队头指向队列第一个元素的前一个位置，队尾指向最后一个元素，那么当front和rear的关系为__________，说明循环队列为空。

18、二叉树是有限结点的集合，这个集合要么是空集，要么是由一个根结点和两棵分别称为__________和__________的互不相交的二叉树组成。