2003年10月北京自考“数据结构”试卷

文章作者 100test 发表时间 2007:05:15 12:14:25
来源 100Test.Com百考试题网

课程代码：02331

第一部分 选择题 (共20分)

一、单项选择题 (本大题共8小题，每小题2分，共16分)

1.某算法的空间花费s(n)=100nlog2n 0.5n1.5 1000n 2000,其空间复杂度为 [ ]
　　A.O(1) B.O(n)
C.O(n1.5) D.O(nlog2n)

2.在单项链表中删除一个指定结点的后继的时间复杂度为 [ ]
　　A.O(n) B.O(nlog2n)
C.O(1) D.O(√n)

3.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [ ]
　　A.O(1) B.O(√n)
C.O(nlog2n) D.O(n)

4.对长度为n的字符串进行字符定位运算的时间复杂度为 [ ]
A.O(1) B.O(√n)
C.O(nlog2n) D.O(n)

5.广义表的深度是 [ ]
A.广义表中子表个数 B.广义表括号个数
C.广义表展开后所含的括号层数 D.广义表中元素个数

6.高度为h(h>0)的二叉树最少有________个结点 [ ]
A.h B.h-1
C.h 1 D.2h

7.n个顶点的带权无向连通图的最小生成树包含________个顶点 [ ]
A.n-1 B.n
C.n/2 D.n 1

8.冒泡排序在最好情况下时间复杂度为 [ ]
　　A.O(1) B.O(nlog2n)
C.O(n) D.O(n2)

9.采用拉链法解决冲突的散列表中，查找的平均查找长度 [ ]
A.直接与关键字个数有关 B.直接与装填因子a有关
C.直接与表的容量有关 D.直接与散列函数有关

10.经常修改的索引文件宜采用________做索引。
A.二叉排序树 B.满二叉树
C.多叉树 D.B 树

第二部分 非选择题 (共80分)

二、填空题 (本大题共10小题，每空2分，共20分)

11.某算法需要的辅助空间为s(n)=10log2n 2000/n 5，则该算法的空间复杂度为_______________。
12.在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为_______________。
13.设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头指针front的修改是_______________。
14.串中所含字符个数称为该串的_______________。
15.tail(tail(a,b))=_______________。
16.n(n>0)个结点二叉树对应的森林最多包含_______________棵非空树。
17.深度为n(n>0)的二叉树最多有_______________个结点。
18.n(n>0)个结点、(n-1)条边的连通无向图中，顶点度数最大值为_______________。
19.堆排序的空间复杂度_______________。
20.倒排文件有_______________和主文件构成。

三、简答题 (本大题共5小题，每小题6分，共30分)

21.设有函数：
void fuc(int n)
{int i.
for(i=1.i*i*i<=n.i )
prinft("%d",i*i*i).
}
函数fuc饿时间复杂度是多少？

22.把1、2、3、4依次进栈（栈初始为空），任何时刻（只要栈不空），都可以出（退）栈，试写出所有可能的出栈序列（如1234）。

23.若一二叉树有2度结点100个，则其叶结点有多少个？该二叉树可以有多少个1度顶点？

24.请画出广义表D的图形表示
D=(D,(a,b),((a,b),c),())

25.有向图（带权）G如下所示：
试给出用迪杰斯特拉（Dijkstra）算法求上图A到其它各顶点最短路径得到的数组P各元素值（A、B、C、D、E、F编号依次是1、2、3、4、5）。

四、理解题 (本大题共2小题，每小题6分，共12分)

26.指出下面函数f的功能及返回值的含义。
int f(char s1[],char s2[])
{
int i=0,j=0.
while(s1[i]