2015年中国计量学院806数据结构与操作系统考研试题研究生学考试试题考研真题
● 摘要
一、 单项选择题：1～40小题，每小题2分，共80分。在每小题给出的四个选项中，请选出一项最符合题目要求的。
1. 在下面的C 语言程序段中，加法操作的时间复杂度为（ ）。
int i, j, k, sum = 0;
for( i=0; i < n; ++i)
for( j=0; j < i*i; ++j)
sum++;
A．Ο(2n2) B．Ο(2n3) C．Ο(n3) D．Ο(n2)
2. 关于线性表的描述正确的是（ ）。
A．访问顺序表中第k 个元素的时间复杂度是Ο(N)
B．访问单链表中第k 个节点的时间复杂度是Ο(N)
C．把新数据插入到顺序表中第k 个位置的时间复杂度是Ο(1)
D．把新数据插入到单链表中第k 个位置的时间复杂度是Ο(1)
3. 关于队列描述正确的是（ ）。
A．用链表表示队列时，也不可以插队（插队指在队列中间插入新数据）
B．用环形数组表示队列时，可以循环使用数组，所以队列永远不会满
C．用数组表示队列时，数据入队的时间复杂度是Ο(N)
D．用数组表示队列时，数据出队的时间复杂度是Ο(N)
4. 关于栈描述正确的是（ ）。
A. 数据进出栈的原则是“先入先出”
B. 用数组表示栈时，栈的操作速度要比用链表表示的栈操作快
C. 用单链表表示栈时，出栈与入栈的时间复杂度是Ο(N)
D. 用数组表示栈时，出栈与入栈的时间复杂度是Ο(N)
5. 已知一颗完全二叉树的第6层有7个结点，则该完全二叉树总共有多少
个结点?（ ）。
A．40 B．39 C．38 D．37
6. 对下图从A 出发进行广度优先遍历，正确的是（ ）。
A．A B E C F D G H B．A D G H F C B E
C．A B C D E F G H D．A D C B G H F E
《数据结构与操作系统》试卷 第1页 共8页