- 在一个长度为n的顺序表的任意位置插入一个新元素的渐进时间复杂度为（）
A. O（n） B. O（n/2） C. O（1） D. O（n的平方）
答案： A
解析：顺序表的存储方式可以理解为链表，（过程为：遍历一遍，插入），所以时间复杂度为O(n) - 设有一个长度为n的顺序表，要在第i（从1开始）个元素之前（也就是插入元素作为新表的第i个元素），则移动元素个数为（ ）。
A. n-i+1
B. n-i
C. n-i-1
D. i
答案： A. n-i+1
举例： 1,2,3,4,5. 要在第i = 2 的位置插入新元素，则则需要移动2,3,4,5共四个数，也就是n-i+1
- 稀疏矩阵一般的压缩存储方式有两种，即 （）
A. 二维数组和三维数组
B. 三元组和散列
C. 三元组和十字链表
D. 散列和十字链表
答案： C
解析：背下来
- 在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动 （） 个元素
A. n-i
B. n-i+l
C. n-i-1
D. i
答案： A. n-i
举例： 1,2,3,4,5. 要在第i = 2 的位置删除元素，则则需要移动3, 4, 5三个数字，就是n-i
5. 若数组A[0…m-1][0…n-1]按列优先顺序存储，则a[i][j]地址为（ ）。 A. LOC(a00)+[j*m+i] B. LOC(a00)+[j*n+i] C. LOC(a00)+[(j-1)*n+i-1] D. LOC(a00)+[(j-1)*m+i-1]
答案： A. LOC(a00)+[j*m+i]
举例： 根据二维数据结构可知，MxN的矩阵，有M行N列，则行宽为N，列宽为M。因此，
列优先存储，存储结构为 [列数 * 列宽 + 行数]
行优先存储，存储结构为 [行数 * 行宽 + 列数]
设栈的初始状态为空，当字符序列 "a3_" 作为栈的输入时，输出长度为 3 的且 可以用作 C 语言标识符的字符串序列有（）个 A. 3 B. 4 C. 5 D. 6
答案： A
举例： 首先，栈的顺序是先进后出
【字符序列为a3_ 】
1)a入栈，再出栈，然后3入栈，再出栈，—入栈，再出栈 序列是a3_
2)a入栈，再出栈,然后3,—入栈，再出栈，序列是a_3
3)a入栈，3入栈，再出栈，a出栈， —入栈，再出栈 序列是3a_
4) a入栈，3入栈，再出栈, —入栈,序列是3_a
5) a入栈，3入栈,_入栈，序列是_3a
其次，C语言的标识符不能以数字开头，去除3a_和3_a 答案为3
补充：卡特兰数公式，出栈情况求和：h(n)=C(2n,n)/(n+1) (n=0,1,2,…)
