试卷代号：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.已知一棵树的边集表示为{,,,,,,,},则该树的深度为( )。假定树根结点的深度为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>,,,,,}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出发进行深度优先搜索所得到的顶点序列； (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_ { ， ， ，G 3,4> ， ， ， ，G 5，3 > ，G6，5>}; 假定该图采用邻接矩阵表表示，试按照遍历算法写出: (1)从顶点 2出发进行深度优先搜索所得到的顶点序列; 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
得 分 评卷人 六、算法设计题(2小题，每小题6分，共12分) 1.已知f为单链表的表头指针，单链表中的结点结构为(data,link),并假定每个结点的 值均为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若 单链表为空则返回数值0。 int Max (LinkNode *f); 2.设Q是…个由其队尾指针和队列长度标识的循环队列，按照下面队列定义和函数声明 写出从此队列中删除-一个元素的算法。 //循环队列定义 struct CyclicQueue { El、mType elem[M]: //M为已定义过的整型常量 int rear; //rear指向队尾元素的后一个位置 int length; //length指示队列中元素个数 }； //若队列非空则删除队头元素并由引用参数x带回，同时返回true;否则若队列为空则返 回false。 bool DelCQueue (CyclicQueue&.Q,ElemType&.x); 76
得 分 评卷人 六、算法设计题 (2小题 ，每小题 6分.共 12分) l、已知 f为单链表的表头指针，单链表中的结点结构为(data, link)，并假定每个结点的 值均为大于。的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最大值，若 单链表为空则返回数值 。。 int Max iLinkNode * f); 2.设 Q是一个由其队尾指针和队列长度标识的循环队列 ，按照下面队列定义和函数声明 写出从此队列 中删除一个元素的算法 。 /循环 队列定义 siruct Cyc}licQueue El.:rn"type elem[M]: 嘴rat in a-e往r; length; /M 为已定义过的整型常量 /%rear指向队尾元素的后一个位置 //length指示队列中元素个数 //若队列非空则删除队头元素并由引用参数 x带回，同时返回 true;否则若队列为空则返 回 falseo boot DelCQueue (CyclicQueue& Q, ElemTypet} x);
试卷代号：1010 中央广播电视大学2006一2007学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 2007年1月 一、单项选择题，在括号内填写所选择的标号{9小题，每小题2分，共18分) 1.D 2.C 3.B 4.C 5.B 6.A 7.B 8.C 9.D 二、填空题，在横线处填写合适内容(7小题，每小题2分，共14分) 1.继承 2.相同 3.MaxSize-1 4.63 .最大值 6.n-1 7.4 三、判断题，在每小题前面打对号表示正确或打叉号表示错误(7小题，每小题2分，共14分) 1.对 2.错 3.对 4.错 5.对 6.对 7.错 四、运算题(5小题，每小题6分，共30分) l.先根：a,b,e,c,f,h,i,j,g 112分 后根：e,b,h,i,j,f,g,c,a /12分 按层：a,b,c,e,f,g,h,i,j /2分 2.评分标准：对1个数值给1分，全对给6分 待查元素：38 74 68 3072 比较次数：】 43 5 77
试卷代号 :1010 中央广播电视大学2006--2007学年度第一学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 2007年 1月 一、单项选择题 ，在括号内填写所选择的标号(9小题 ，每小题 2分 ，共 18分) 2.C- 3. B 4. C 5. B 6.A }. B g. c 9.n 二、填空题。在横线处填写合适内容(7小题，每小题 2分，共 i}分) 继承 相 同 M axSiu} 63 最大值 n一 1 7. 4 三、判断题 ，在每小题前面打对号表示正确或打叉号表示错误(7小题 ，每小题 2分 .共 14分) 1.对 6.对 2、错 7.错 3，对 4.错 5.又寸 四、运算题(5小题，每小题 6分，共 30分) 1.先根:a,b,e,c,f,h,i,j,} Ill分 后根:e,b,h,i,j,f,g,c,a l/2分 按层:a,b,c,e,f,g,h,i,j //2分 2.评分标准:对 1个数值给 1分，全对给 6分 待查元素:38 74 68 30 72 比较次数:1 3 4 3 5
3.30(16,49(34,63) 4.(1)2,4,5,1,3,6 /3分 (2)2,4,5,6,1,3 1/3分 5.查找23,68,84的搜索长度：1,2,4 /每个数据占2分 五、算法分析题(2小题，每小题6分，共12分) 1.计算单链表的长度或计算单链表中结点的个数。 2.逆序排列以first为表头指针的单链表中的所有结点并返回新的表头指针。 六、算法设计题(2小题，每小题6分，共12分) 1.评分标准：按注释酌情给分。 int Max (LinkNode *f) if (f==NULL)return 0; /11分 if (f-link==NULL)return f->data;//2 int temp=Max (f->link); /4分 if (f->data>temp)return f->>data; //5分 else return temp; /16分 2.评分标准：按注释酌情给分。 bool DelCQueue (CyclicQueue&.Q,ElemType&.x) if (Q.length==0)return false; /1分 x=Q.elem[(Q.rear-Q.length+M)%M们； 14分 Q.length--; /15分 return true; /16分 78
3. 30(16，49(34，63)) 4.(1)2，4，5，1，3，6 (2)2，4，5，6，1，3 //3分 //3分 5.查找 23,68,84的搜索长度:1,2,4 /每个数据占 2分 五、算法分析题(2小题 ，每小题 6分 ，共 12分 ) 1.计算单链表的长度或计算单链表中结点的个数。 2.逆序排列以 first为表头指针的单链表中的所有结点并返回新的表头指针一。 六、算法设计题(2小题 ，每小题 6分，共 12分 ) 1.评分标准:按注释酌情给分。 int Max CLinkNode *f) if (f=-NULL) return 0; if(f一二>link二 二NUI_I)return f一> data int temp-Max(f一)link); if (f一>data> temp) return f一>data; e工se return temp; /}l分 ;j;?分 i!}1分 //5分 刀e>分 2.评分标准 :按注释酌情给分。 bool lelCQueue (CyclicQueue& Q, EtemType& x) if(Q, length==0) return false; x二Q. elem [}Q. rear一Q. length-}-M) io1V1] Q, length一一; return true: //1分 /}}分 //}分 //6分