数据结构II试卷5.doc

数据结构II试卷5.doc[数据结构II模拟试题5 ]
一、单选题(每小题2分，共10小题，20分)
下面说法错误的是
算法原地工作的含义是指不需要任何额外的辅助空间
在相同的规模n下，复杂度0(n)的算法在时间上总是优于复杂度0(2")的算法
所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界
同一个算法，实现语言的级别越高，执行效率就越低
(1) B. (1), (2)
C. (1), (4) D. (3)
下列程序的时间复杂度为
i=0； s=0；
while (s<n)
{ i++;
s=s+i；
}
0 (乔) B. 0 (殛)
C. 0 (n) D. 0 (n2)
若线性表的插入和删除操作频繁地在表头或表尾位置进行，则更适宜采用的存储结构为


二维数组A [12] [18]采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150, 则元素A [9] [7]的地址为
A. 429 B. 432
C. 435 D. 438
设一个栈的输入序列为A, B, C, D,则借助一个栈所得到的输出序列不可能是
A. A, B, C, D B. D, C, B, A
C. A, C, D, B D. D, A, B, C
设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, 1, 1则T中的叶子数为
A. 5 B. 6
C. 7 D. 8
以下说法不正确的是
无向图中的极大连通子图称为连通分量
连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点
图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点
有向图的遍历不可采用广度优先搜索
&假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的 关键字时，所需进行的比较次数为
A. n~l
B.
n
C. n+1
D.
n+2
设置溢出区的文件是

B.
ISAM文件
C. VSAM文件
D.
顺序文件
己知一组关键字为{25,48,36,72,79,82,23,40,16,35},其中每相邻两个为有序子序列。对这些子序列进行一 趟两两归并的结果是
{25, 36, 48, 72, 23, 40, 79, 82, 16, 35}
{25, 36, 48, 72, 16, 23, 40, 79, 82, 35}
{25, 36, 48, 72, 16, 23, 35, 40, 79, 82}
{16, 23, 25, 35, 36, 40, 4& 72, 79, 82}
二、 填空题（每小题2分，共10小题，20分）
下面程序段中带下划线的语句的执行次数的数量级是（ ）。
i=l;
WHILE（i<n）
i： =i*2;
己知在结点个数大于1的单循环链表中，指针p指向表中某个结点，则下列程序段执行结束时，指针q指向结
点P的（ ）结点。
q=p;
while（q->next!=p）q=q-〉next;
已知substr（s, i, len）函数的功能是返回串s中第i个字符开始长度为len的子串，strlen