中央广播电视大学2007—2008学年度第一学期"开放本科"期末考试
计算机专业 数据结构 试题
2008年1月
一,单项选择题,在括号内填写所选择的标号(每小题2分,共1日分)
1.下面程序段的时间复杂度为( ).
for(int i=0;i
B.s一>link=top一>link;top一>link=s;
C.s一>link=top;top=s;
D.s一>link=top;top=top一>link;
6. 一棵具有35个结点的完全二叉树的高度为( ).假定空树的高度为一1.
A. 5 B. 6
C. 7 D. 8
7.向具有n个结点的堆中插入一个新元素的时间复杂度为( ).
A.O(1) B.O(n)
C O(log2n) D.O(nlog2n)
8.在一棵AVL树中,每个结点的平衡因子的取值范围是( ).
A.一l~1 B.一2~2
C.1~2 D.0~1
9.一个有n个顶点和n条边的无向图一定是( )的.
A. 连通 B.不连通
C.无回路 D.有回路
二,填空题,在横线处填写合适的内容(每小题2分,共14分)
1.数据结构包括 ,存储结构和对数据的运算这三个方面.
2.一维数组所占川的空间是连续的.但数组元素不一定顺序存取,通常是校元素的
存取的.
3.将一个n阶刘称矩阵的L三角部分或下三角部分压缩存放于—个 维数组中,则该一维数组需要至少具有 个元素.
4.对于一棵具有n个结点的树.该树中所有结点的度数之和为 .
5.在—棵高度为3的理想平衡二叉树中,最少含有 个结点,假定树根结点的高度为o.
6.假定对长度n=50的有序表进行折半搜索,则对应的判定树中最底层的结点数为
个.
7.用邻接矩阵存储图,占用的存储空间与图中的 数有关.
三,判断题,在每小题前面打对号表示正确或打叉号表示错误(每小
题2分,共"分)
( )1.算法和程序都应具有下面一些特征:有输入,有输出,确定性,有穷性,有效性.
( )2.用字符数组存储长度为n的字符串,数组长度至少为n+1.
( )3.在用循环单链表表示的链式队列中,可以不没队头指针,仅在链尾设置队尾指针.
( )4.邻接矩阵适用于稀疏图的表示,邻接表适用于稠密图的表示.
( )5.对一个无向连通图进行—次深度优先搜索遍历时可以访问到图中的所有顶点.
( )6.在索引顺序结构的搜索中,对索引表只可以采取顺序搜索,不可以采用折半搜索.