试卷代号：1010 座位号■■ 中央广播电视大学2006一2007学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题 2007年1月 题号 三 四 五 六 总 分 分数 得 分 评卷人 一、单项选择题，在括号内填写所选择的标号(9小题，每小题2分， 共18分)】 l,输出一个二维数组b[m][n]中所有元素的时间复杂度为( )。 A.O(n) B.O(m+n) C.O(n2) D.O(m n) 2.在一个长度为的顺序存储的有序表中搜索值为x元素时，其时间效率最高的算法的 时间复杂度为( )。 A.O(1) B.O(n) C.O(log2n) D.O(n) 3.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插 入一个元素时，首先应执行( )语句修改top指针。 A.top++; B.top--; C.t0p=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 71
试卷代号:polo 座位号仁工] 中央广播电视大学2006-2007学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题 2007年 1月 题 号 四 五 尸、 总 分 分 数 得 分 评卷人 一、单项选择题，在括号内填写所选择的标号(9小题，每小题 2分， 共 18分 ) 1.输出一个二维数组 b仁m]巨n口中所有元素的时间复杂度为( )。 A.0(n) I3. 0(m十n) C. O (n2) D. 0(m ‘n) 2.在一个长度为 n的顺序存储的有序表中搜索值为 x元素时，其时间效率最高的算法的 时间复杂度为( )。 A. O (1) B. O (} ) C. O(log2n) D. 0(n) 3.当利用大小为 n的数组顺序存储一个栈时，假定用 top=-n表示栈空，则向这个栈插 入一个元素时，首先应执行( )语句修改 top指针。 A. top-I- }-; I3. top一一; C. top=0; I), top; 4.在一棵树中，( )没有前驱结点。 A.树枝结点 13.叶子结点 C.树根结点 D.空结点 5.已知一棵树的边集表示为{GA,I3>,<A,C>,<13,D>,<C,E>,<C,F?,<C,G >,}F,H>,CF,I>}，则该树的深度为( )。假定树根结点的深度为Oo A. 2 l3. 3 C. 4 U. 5 71
6.n个顶点的连通图中至少含有( )条边。 A.n-1 B.n C.n(n-1)/2 D.n(n-1) 7.设无向图的顶点个数为n,则该图最多有( )条边。 A.n-】 B.n(n-1)/2 C.n(n+1)/2 D.n(n-1) 8.在采用开散列法解决冲突时，每一个散列地址所链接的同义词子表中各个表项的 ( )的值相同。 A.关键码 B.非关键码 C.散列函数 D.某个域 9.散列函数应该有这样的性质，即函数值应当以( )概率取其值域范围内的每一个 值。 A.最大 B.最小 C.平均 D.同等 得 分 评卷人 二、填空题，在横线处填写合适内容(7小题，每小题2分，共14分) 1.面向对象的特征应包括对象、类、 、多态、消息通信等。 2.在单链表中设置表头附加结点的作用是在插人和删除表中任-个元素时的操作都 9 3.若设顺序栈的最大容量为MaxSize,top==一1表示栈空，则判断栈满的条件是top= 4.在一棵高度为5的完全二叉树中，最多包含有 个结点。假定树根结点的高度 为0。 5,在一个最大堆中，堆顶结点的值是所有结点中的 6.具有n个顶点的连通无向图的一棵生成树中含有 条边。 7.在一棵5阶B树中，每个结点最多含有 个关键码。 72
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.关键码 I3.非关键码 C.散列函数 D.某个域 9.散列函数应该有这样的性质 ，即函数值应 当以( )概率取其值 域范围内的每一个 值 最大 平均 最小 同等 得 分 评卷人 二、填空题，在横线处填写合适内容(7小题 ，每小题 2分，共14分} .面向对象的特征应包括对象 、类 、 、多态 、消息通信等。 .在单链表 中设置表头附加结点 的作用 是在 插人和删 除表中任一 个元 素时的操作都 若设顺序栈的最大容量为 MaxSize, top= _ -1表示栈空，则判断栈满的条件是top= 4.在一棵高度为 5的完全二叉树中，最多包含有 个结点。假定树根结点的高度 为 0 .在一个最大堆 中，堆顶结点的值是所有结点 中的 具有 n个顶点的连通无 向图的一棵生成树 中含有 条边。 在一棵 5阶 }3树 中，每个结点最多含有 个关键码
得 分 评卷人 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(7小 题，每小题2分，共14分)】 )1.线性表若采用链式存储表示，在删除时不需要移动元素。 )2.若让元素1,2,3依次进栈，任何时候都允许元素出栈，则出栈次序1,3,2是不可能 出现的情况。 )3.一个广义表(a),(h),c),(d)))的长度为3，深度为4。 )4.二叉树是一棵无序树。 )5.对于关键码互不相同的一组记录，若生成二叉搜索树时插人记录的次序不同则将得 到不同形态的二叉搜索树。 )6.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下或上三角部分。 )7.在散列存储中采取开散列（链地址）法解决冲突时，其装载因子的取值一定在(0,1) 之间。 得 分 评卷人 四、运算题(5小题，每小题6分，共30分) 提示：在进行每题运算时，最好先在草稿纸上根据题意画出对应的图形，这样更直观和简 便。 L.假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),分别写出先根、后根、按层遍 历的结果。 先根 后根： 按层： 73
得 分 评卷 人 三、判断题。在每小题前面打对号表示正确或打叉号表示错误(7小 题 ，每小题 2分 ，共 14分} )l.线性表若采用链式存储表示，在删除时不需要移动元素。 )2.若让元素 1,2,3依次进栈 ，任何时候都允许元素出栈 ，则 出栈 次序 1,3,2是不可能 出现的情况 。 )3.一个广‘义表((a),((b),c),(((cl))))的长度为 3，深度为40 )4.二叉树是一棵无序树 。 )5.对于关键码互不相同的一组记录 ，若生成二叉搜索树时插人 记录的次序不同则将得 到不同形态的二叉搜索树 。 )6.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下或上三角部分。 )7.在散列存储中采取开散列(链地址)法解决冲突时，其装载因子的取值 一定在(0 , 1,) 之间 。， 得 分 评卷人 四、运算题 (5小题 ，每小题 6分，共 30分) 提示 :在进行每题运算时，最好先在草稿纸上根据题意画出对应的图形 ，这样更直观和简 l.假定一棵普通树的广义表表示为 a(b(e),c(f(b,i,i),g))，分5ill1写出先根、后根、按层遍 历的结果。 先根 : 后根 : 按层 :
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结点后，得到的二叉搜索树的广义表表示。假定每次删除双支结点时是用它 的中序后继结点的值来取代，接着删除其中序后继结点。 广义表表示： 4.已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5,6}; E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<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的搜索长度： 得 分 评卷人 五、算法分析题(2小题，每小题6分，共12分) l.设单链表结点的结构为LNode=(data,link),阅读下面的函数，指出它所实现的功能 int AA(LNode Ha){/Ha为指向带表头附加结点的单链表的表头指针 int n=0; LNode p=Ha->link; while (p){ 74
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结点后，得到的二叉搜索树的广义表表示。假定每次删除双支结点时是用它 的中序后继结点的值来取代，接着删除其中序后继结点。 广义表表示: 4.已知一个图的顶点集 V和边集 G分别为: V=王1，2，3,4，5，6}; E_ {< 1，2> ，< 1，3} ，< 2，4> ，< 2，5> ，G 3,4> ，<4,5> ，< 4，6> ，<5，1> ，G 5，3 > ，G6，5>}; 假定该图采用邻接矩阵表表示，试按照遍历算法写出: (1)从顶点 2出发进行深度优先搜索所得到的顶点序列; <2)从顶点 2出发进行广度优先搜索所得到的顶点序列。 (1) (2) 5，设散列表的长度m=7，散列函数为 H<K)=K mod m，若采用线性探查法解决冲突，待 依次插入的关键码序列为{19,14,23,68,20,84}，分别求出查找 23,68,$4时的搜索长度。 查找 23,68,84的搜索长度: 得 分 评卷人 五、算法分析题 (2小题，每小题 6分 ，共 12分 ) 1.设单链表结点的结构为 LNode=(data, link)，阅读下面的函数，指出它所实现的功能 int AA (LNode } Ha){ //Ha为指向带表头附加结点的单链表的表头指针 int n=Q; LNode * p= Ha一>link; while (p){
n+; p=p->link; return(n); } 算法功能： 2.阅读下列算法，写出算法功能。 LinkNode BB (LinkNode first) /first为单链表的表头指针 if (first==NULL first->link==NULL)return first; LinkNode p=first,rl=first->link; p->link=NULL; while(rl！=NULL){ ListNode r2=r1->link; rl->link=p; p=rl; r1=r2; return p; 算法功能： 75
n+ 十 P=P一>link; return(n); 算法功能 : 2.阅读下列算法，写出算法功能。 LinkNode * BB (LinkNode * first) //first为单链表的表头指针 if (first==Ni.1LL }} first一>link==NULL,) return first; LinkNode * p=first，* r1=first一>link; P一>link=NULL; while (r1!=NULL){ ListNode } r2=r1一> link; r1一>link=p; p=r1; r1=r2; return p 算法功能 : 75