试卷代号：1010
中央广播电视大学2006—2007学年度第一学期“开放本科”期末考试
计算机专业 数据结构 试题
一、单项选择题，在括号内填写所选择的标号
1．输出一个二维数组b[m][n]中所有元素的时间复杂度为( )。
A．（）(n) B．（）(m十n)
C．（）(n2) D．（）(m*n)
2．在一个长度为n的顺序存储的有序表中搜索值为x元素时，其时间效率最高的算法的时间复杂度为( )。
3．当利用大小为n的数组顺序存储一个栈时，假定用top= =n表示栈空，则向这个栈插入一个元素时，首先应执行( )语句修改top指针。
A．top++； B. top--；
C．top=0； D．top；
4．在一棵树中，( )没有前驱结点。
A．树枝结点 B. 叶子结点
C. 树根结点 D．空结点
5．已知一棵树的边集表示为{<A，B>，<A，C)，<B，D>，<C，E>，<C，F>，<C，G>，<F，H>，<F，I>}，则该树的深度为( )。假定树根结点的深度为0。
A． 2 B． 3
C． 4 D． 5
6．n个顶点的连通图中至少含有( )条边。
A．n一1 B．n
C．n(n—1)／2 D. n(n一1)
7．设无向图的顶点个数为n．则该图最多有( )条边。
A．n一1 B．n(n一1)／2
C．n(n+1)／2 D．n(n一1)
8．在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的( )的值相同。
A. 关键码 B．非关键码
C. 散列函数 D．某个域
9．散列函敷应该有这样的性质，即函数值应当以( )概率取其值域范围内的每——个值。
A．最大 B. 最小
C. 平均 D．同等
二、填空属
1．面向对象的特征应包括对象、类、——、多态、消息通信等。
2．在单链表中设置表头附加结点的作用是在插入和删除表中任一个元素时的操作都——
3．若设顺序栈的最大容量为MaxSize，top==-l表示栈空，则判断栈满的条件是top== ——
4．在一棵高度为5的完全二叉树中，最多包含有——个结点。假定树根结点的高度为0。
5. 在一个最大堆中，堆顶结点的值是所有结点中的——。
6．具有n个顶点的连通无向图的—棵生成树中含有——条边。
7．在一棵5阶B树中，每个结点最多含有——个关键码。
三、判断属
( )1. 线性表若采用链式存储表示，在删除时不需要移动元素。
( )2．若让元素1，2，3依次进栈，任何时候都允许元素出栈，则出栈次序1，3，2是不可能出现的情况。
( )3．一个广义表((a)，((h)，c)，(((d))))的长度为3，深度为4。
( )4．二叉树是一棵无序树。
( )5．对于关键码互不相同的一组记录，若生成二叉搜索树时插入记录的次序不同则将得到不同形态的二叉搜索树。
( )6．存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下或上三角部分。
( )7．在散列存储中采取开散列(链地址)法解决冲突时，其装载因子的取值一定在(0，1)之间。
四。运算
提示：在进行每题运算时，最好先在草稿纸上根据题意画出对应的图形，这样更直观和简便。
1．假定一棵普通树的广义表表示为。(b(e)，r(f( h ,i ,j)，g))，分别写出先根、后根、按层遍历的结果。
先根：
后根：
按层：
2．假定一个线性序列为(38，52，25，74，68，16，30，54，90，72)，根据此线性序列中元素的排列次序生成的一棵二叉搜索树，求出对该二叉搜索树进行查找38，74，68，30，72等元素时的查找长度(即比较次敷)。
|
待查元素
|
38
|
74
|
68
|
30
|
72
|
|
比较次数
|
|
|
|
|
|
3．已知——棵二叉搜索树的广义表表示为：28(12(，16)，49(34(30)，72(63)))，求出从中依次删除72，12，28结点后，得到的--X搜索树的广义表表示．假定每次删除双支结点时是用它的中序后继结点的值来取代，接着删除其中序后继结点。
广义表表示：
4．已知一个图的顶点集V和边集G分别为：
V=(1，2，3，4，5，6)；
E={<1，2>，<1，3>，<2，42>，<2，5>，<3，4．7，<4，5>，<4，6>，<5，1>，<5，3>，<6，5>}；
假定该图采用邻接矩阵表表示，试按照遍历算法写出：
(1)从顶点2出发进行深度优先搜索所得到的顶点序列，
(2)从顶点2出发进行广度优先搜索所得到的顶点序列。
(1)
(2)
5．设散列表的长度m：7，散列函数为H(K)=K mod m，若采用线性探查法解决冲突，待依次插入的关键码序列为{19，14，23，68，20，84}，分别求出查找23，68，84时的搜索长度。
查找23，68，84的搜索长度：
五、算法分析题
1．设单链表结点的结构为LNode＝(data，link)，阅渎下面的函数，指出它所实现的功能
算法功能；
六、算法设计
1. 已知f为单链表的表头指针，单链表中的结点结构为(data，link)，并假定每个结点的
值均为大于。的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若单链表为空则返回数值0。
int Max(Link Node * f)；
2. 设Q是一个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明写出从此队列中删除一个元素的算法。
／／循环队列定义
／／若队列非空则删除队头元素并由引用参数x带回，同时返回t rue,否则若队列为空则返回false。
试卷代号：1010
中央广播电视大学2006—2007学年度第一学期“开放本科”期末考试
计算机专业 数据结构 试题答案及评分标准
一、单项选择题
1. D 2．C 3．B 4． C 5. B
6．A 7．B 8．C 9． D
二、填空题，
1．继承
2．相同
3．MaxSixe一1
4． 63
5．最大值
6．n—l
7． 4
三、判断题，
1．对 2．错 3．对 4．错 5. 对
6．对 7．错
四、运算题
1．先根:a,b,e,c,f,h,i,j,g
电大2006—2007年第一学期“开放本科”计算机专业数据结构试题由成人自学网整理，请点击电大2006—2007年第一学期“开放本科”计算机专业数据结构试题搜索更多相关内容。