全国2012年1月自考《数据结构导论》试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )
A.集合 B.线性结构
C.树形结构 D.图状结构
2.下面算法程序段的时间复杂度为( )
for ( int i=0; i<m; i++)
for ( int j=0; j<n; j++)
a［i］［j］=i*j;
A. O(m2) B. O(n2)
C. O(mn) D. O(m+n)
3.线性结构是( )
A.具有n（n≥0）个表元素的有穷序列 B.具有n（n≥0）个字符的有穷序列
C.具有n（n≥0）个结点的有穷序列 D.具有n（n≥0）个数据项的有穷序列
4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是( )
A. O(1) B. O( )
C. O(log2n) D. O(n)
5.关于串的叙述，正确的是( )
A.串是含有一个或多个字符的有穷序列
B.空串是只含有空格字符的串
C.空串是含有零个字符或含有空格字符的串
D.串是含有零个或多个字符的有穷序列
6.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是( )
A.1243 B. 1432
C. 2134 D.4312
7.队列是( )
A. 先进先出的线性表 B. 先进后出的线性表
C. 后进先出的线性表 D.随意进出的线性表
8.10阶上三角矩阵压缩存储时需存储的元素个数为( )
A.11 B.56
C.100 D.101
9.深度为k（k≥1）的二叉树，结点数最多有( )
A.2k 个 B.(2k -1)个
C.2k-1个 D.(2k+1)个
10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( )
A. 11 B.13
C. 23 D. 25
