2011 年 10月全国高等教育自学考试《数据结构导论》真题试题_2011 年 10月全国高等教育自学考试《数据结构导论》真题试题及答案

本套试卷集合了考试编委会的理论成果。专家们为考生提供了题目的答案，并逐题进行了讲解和分析。每道题在给出答案的同时，也给出了详尽透彻的解析，帮助考生进行知识点的巩固和记忆，让考生知其然，也知其所以然，从而能够把知识灵活自如地运用到实际中去。

1. 设栈 S和队列 Q的初始状态为空，元素 e1，e2，e3，e4，e5 和 e6 依次通过栈 S，元素退栈后即进入队列 Q，若 6个元素的出队序列是 e2，e4，e3，e6，e5，e1，则栈 S的容量至少为 ( )

A.2

B.3

C.4

D.6

2. 设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为 ( )

A.线性表的顺序存储结构

B.队列

C.线性表的链式存储结构

D.栈

下列程序段的时间复杂度为 ( )
i=0 ；s=0；
While （s<n）
{i++ ；
S=s+i ；
}

C.O(n)

4. 设 A是 n×n 的对称矩阵，将 A的对角线及对角线上方的元素 A ij (1 ≤i,j ≤n,i ≤ j) 以列优先顺序存放在一维数组元素 B［ 1］至 B［n(n+1)/2 ］中，则元素 A ij (i ≤j) 在 B中的位置为 ( )

A.i(i-l)/2+j

B.j(j-l)/2+i

C.j(j-l)/2+i-1

D.i(i-l)/2+j-1

5. 在有向图 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 的路径