一、单选题（共 10 道试题，共 50 分。）V
1. 在一个具有n个结点的有序单链表中删除一个结点并仍然有序的时间复杂度是（）。
A. O(1)
B. O(n)
C. O(n^2)
D. O(nlog2n)
满分：5 分
2. 以下数据结构中哪一个是非线性结构？（）
A. 队列
B. 线性表
C. 栈
D. 二叉树
满分：5 分
3. 进栈顺序为{a,b,c,d}的序列，出栈顺序不可能为（）。
A. dcba
B. cdab
C. adcb
D. abcd
满分：5 分
4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A. 必须是连续的
B. 一定是不连续的
C. 连续或不连续都可以
D. 部分地址必须是连续的
满分：5 分
5. 对线性表，在下列哪种情况下应当采用链表表示？（）
A. 经常需要随机地存取元素
B. 经常需要进行插入和删除操作
C. 表中元素的个数不变
D. 表中元素需要占据一片连续的存储空间
满分：5 分
6. 下面关于串的叙述错误的是（）。
A. 串是字符的有限序列
B. 串既可以采用顺序存储，也可以采用链式存储
C. 空串是由空格构成的串
D. 模式匹配是串的一种重要运算
满分：5 分
7. 在一个链队列中，若f, r分别为队首、队尾指针，则插入p所指结点的操作为（）。
A. p->next=f;f=p;
B. p->next=r;r=p;
C. r->next=p;r=p;
D. f->next=r;f=p;
满分：5 分
8. 设赋值语句的时间是单位时间，则下列算法的时间复杂度为（）： for (i = 0; i < n; i++){ for (j = 1, sum = a[0]; j <= i; j++) { sum += a[j];} cout<<”sum for subarray 0 through ”<<i<<” is ”<<sum<<endl;}
A. O(1)
B. O(n)
C. O(n^2)
D. O(n^3)
满分：5 分
9. 对于栈操作数据的原则是（）。
A. 后进先出
B. 先进先出
C. 后进后出
D. 不分顺序
满分：5 分
10. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（）。
A. 1 2 3
B. 3 1 2
C. 3 2 1
D. 2 3 1
满分：5 分
请同学及时保存作业,如您在20分钟内不作操作,系统将自动退出。
保存 交卷