2010安徽省C与数据结构链表包过题库

1、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)

2、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别 B）一个平均值

C）一个最大值 D）一个均方值

3、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A）。

A）直接选择排序 B）直接插入排序

C）快速排序 D）起泡排序

4、下面程序段的时间复杂度是( A )。

s =0;

for( i =0; i

for(j=0;j

s +=B[i][j];

sum = s ;

A） O(n2) B） O(n)

C） O(m*n) D）O(1)

5、在数据结构中，从逻辑上可以把数据结构分为（ C ）。

A）动态结构和静态结构 B）紧凑结构和非紧凑结构

C）线性结构和非线性结构 D）内部结构和外部结构

6、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。

A）top不变 B）top=0 C）top-- D）top++

7、数据结构中，在逻辑上可以把数据结构分成（ B ）。

A）动态结构和静态结构

B）线性结构和非线性结构

C）紧凑结构和非紧凑结构

D）内部结构和外部结构

8、二叉树第i(i≥1)层上至多有（ C ）结点。

A）2i B）2i C）2i-1 D）2i-1

9、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。

A）顺序表B）双链表C）带头结点的双循环链表 D）单循环链表

10、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]

C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]

11、（ C ）在进行插入操作时，常产生假溢出现象。

A）顺序栈 B）循环队列

C）顺序队列 D）链队列

12、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]

C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]

13、与无向图相关的术语有（ C ）。

A）强连通图 B）入度

C）路径 D）弧

14、n个顶点的图的最小生成树必定（ D ），是不正确的描述。 A）不唯一 B）权的总和唯一

C）不含回路 D）有n条边

15、n个顶点的图的最小生成树必定（ D ），是不正确的描述。A）不唯一 B）权的总和唯一

C）不含回路 D）有n条边