全国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