试卷代号：1010 座位号■■ 中央广播电视大学2011一2012学年度第二学期“开放本科”期末考试 数据结构试题 2012年7月 题 号 二 三 四 五 总分 分 数 得分 评卷人 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1.下面算法的时间复杂度为( )。 int f(unsigned int n){ if(n==0 n==1)return 1; else return n f(n-1); A.0(1) B.O(n) C.O(n2) 'D.O(n!) 2.在一个长度为的线性表中顺序查找一个值为x的元素时，在等概率的情况下，查找 成功时的平均查找长度为()。 A.n B.n/2 C.(n+1)/2 D.(n-1)/2 3.已知L是一个单链表的表头指针，在表头插人结点p的操作是()。 A.p=L;p->link=L; B.p-link=L;p=L; C.p->link=L;L=p; D.L=p;p->link=L; 81
试卷代号 座位号 中央广播电视大学 11 2012 年度 学期 开放本科 末考 数据结构试题 2012 年7 总分 分数 得分|评卷人 -、单项选择题，在括号内填写所选择的标号{每小题 2分，共 8分) 1.下面算法的时间复杂度为( )。 int f( unsigned int n) { if(n= =0 II n= = 1) return 1; else return 赞f(n-1) ; A. 0 (1 ) c. 0(n2 ) B. O(n) '0. O(n!) 2. 线性 序查找一 在等概率 况下 成功时的平均查找长度为( )。 A. ri C. (n+1)/ 2 B. n/2 D. (n 1) / 3. 知L 个单链 )。 A. p=L; 1ink= L; B. p-- 二>link=L; p=L; c. 1ink=L; L=p; D. L=p; 1ink=L; 81
4.在一棵二叉树的链接存储中，每个存储结点至少要包含( )个指针域。 A.1 B.4 C.3 D.2 5.在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为()， 假定树根结点的编号为0。 A.2i B.2i-1 C.2i+1 D.2i+2 6.对长度为10的线性有序表A[10]进行折半查找，若查找到元素A[1]时成功，则查找 长度为()。 A.1 B.2 C.3 D.4 7.若一棵二又树共有5层结点，则最后一层的结点数最多为( )个结点。 A.4 B.8 C.32 D.16 8.设一个有向图具有n个顶点和e条边，若采用邻接表作为其存储结构，则空间复杂度 为()。 A.O(nXlogze) B.O(n+e) C.O(n) D.O(n2) 9.在一棵m阶B树中，树根结点所包含的关键码个数至少为( )。 A.1 B.2 C.m/2 D.m-1 82
4. 少要 )个指针域。 ABCD 5. 结点 左子 女结 ) , 假定树根结点的编号为 0。 A. 2i B. 2i-1 C. 2i+1 D. 2i+2 6. 对长度 为10 有序表A[10]进行折半查找 素A[l] 查找 长度为( )。 A. 1 C. 3 B. 2 D. 4 7. 二叉树共有5 层结 则最后一 多为 )个结点。 nLPO ABCD 8. 向 图 顶点 条边 采用 结构 为(\)。 A. O(nX!ogze) B. O(n+e) C. O(n) D. O(nZ ) 9. 在一 阶B 所包 码个数至少 )。 A. 1 B. 2 C. m/2 D. 82
得分 评卷人 二、判断题，在每小题后面的括号内打对号（√）表示叙述正确或打叉 号(×)表示叙述错误（每小题2分，共14分） 10.栈和队列都是运算受到限制的线性表。() 11.用字符数组存储长度为n的字符串，该数组长度至少为n。（) 12.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 () 13.邻接矩阵最适用于稀疏图的表示，邻接表最适用于稠密图的表示。() 14.对一个无向连通图进行一次深度优先搜索遍历时可以访问到图中的所有顶点。 ) 15.在索引顺序结构的搜索中，对索引表只可以采取顺序搜索，不可以采用折半搜索。 ( ) 16.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 ) 得 分 评卷人 三、填空题，在横线处填写合适的内容（每小题2分，共14分） 17.在队列数据结构中，对数据操作的特点是先进 18.设顺序栈的最大容量为MaxSize,top==一1表示栈空，则判断栈满的条件是top= 19.在一棵高度为4的完全二叉树中，最多包含有 个结点。假定树根结点的高 度为0。 20.在一个最大堆中，堆顶结点的值是所有结点中的 21.具有n个顶，点的连通图的生成树含有 条边。 22.在对个结点进行的堆排序中，对任意一个分支结点进行调整（筛）运算的时间复杂 度为 23.,假定一个线性表的关键码序列为(12,23,74,55,63,45)，若按key%3条件进行划分， 使得同一余数的元素成为一个子表，则元素74所在子表的长度为 83
得分|评卷人 二、判断题，在每小题后面的括号内打对号 .J )表示叙述正确或打叉 )表示叙述错误{每小题 2分，共 4分} 10. 算受到 限制 性表 ) 1. 字符 存储 字符 该数组长度至 ( ) 12. 在用 链表表 链式 队头 仅在链尾 ( ) 13. 邻接 用 于稀疏 表示 邻接表最 图 的 表示 ) 14. 连通 深度优 搜索遍历时可 ( ) 15. 搜索 序搜索 不可 半搜索 ( ) 16. 图 中 各个顶 ( ) 得分 i评卷人 三、填空题，在横线处填写合适的内容(每小题 2分，共 4分) 17. 对数据操 个结点。假定树根结点的高 18. 设顺 最大容 为MaxSize top = =一 判 断 条件 op -、 19. 在一 为4 全二 含 有 度为 20. 大堆 堆顶结 1. 成树 22. 在对 对任 意一 调 整 运算 度为 23. 假定 性表 键码序列 为(12 ，23 ，74 ，55 ，63 ，4 按key%3 条件进行 使得同一余数的元素成为一个子表，则元素 4所在子表的长度为 83
得分 评卷人 四、运算题（每小题8分，共40分） 24.假定一棵二叉树的广义表表示为A(B(,D(G)),C(E,F)),分别写出对它进行先序、 中序和按层遍历的结果。 先序： 中序： 按层： 25.已知一个有序表(15,26,34,39,45,56,58,63,74,76,83,94)顺序存储于一维数组 [12]中，根据折半搜索过程填写成功搜索下表中所给元素34、56、58、63时的比较次数。 元素 34 56 58 63 比较次数 26.假定一个线性表为(56,27,34,95,73,16,50,62)，根据此线性表中元素次序生成一棵 二叉搜索树，分别求出该二叉搜索树中的分支结点数和叶子结点数。 分支结点数： 叶子结点数： 27.已知一个带权图的顶点集V和边集G分别为： V={0,1,2,3,4,5}; E={(0,1)19,(0,2)21,(0,3)14,(1,2)16,(1,5)5,(2,4)11,(3,4)18,(4,5)62: 试根据普里姆算法，从顶点0出发，求出其最小生成树，在下面横线上填写依次得到的最 小生成树中的每条边。 84
得分|评卷人 四、运算题{每小题 8分，共 0分} 24. 假定一棵二 广义表表 D(G» ,C(E, F» 行先 中序和按层遍历的结果。 先序: 中序 按层: 25. 有序 表 (15 ，26 ，34 ，39 ，56 ，58 ，63 ，74 ，76 ，94) 存储 一 维 a[12] 根据 半搜 程填 索下 素34 、56 、58 、63 的 比 次数 元素 I 56 I 58 I 63 比较次数 26. 定一 线性表为(56 ，27 ，34 ，95 ，73 ，16 ，50 ，62) 根据此线 二叉搜索树，分别求出该二叉搜索树中的分支结点数和叶子结点数。 分支结点数: 叶子结点数: 27. 知一个带权 边集 V={0 ,1 ,2 ,3 ,1 ,5} ; ., nhu' , , Tin6 , qJ , 42A , , ' , PO , , TI , nu , nL , nu , QU , E { AU 试根据普里姆算法，从顶点 O出发，求出其最小生成树，在下面横线上填写依次得到的最 小生成树中的每条边。 , , , , 84
28.设散列表的长度m=7;散列函数为H(K)=K mod m,给定的关键码序列为{19,14， 23,40,68},并假定采用的闭散列表为HT[],采用的解决冲突的方法为线性探查法，求出在 最后得到的散列表中，关键码19、40和68的存储位置和对应的查找长度。 元素： 19 40 68 存储位置： 查找长度： 得分 评卷人 五、算法分析题（每小题7分，共14分）》 29.该算法功能为：从表头指针为la的、按值从小到大排列的有序链表中删除所有值相同 的多余元素（只保留一个结点），并释放被删结点的动态存储空间。阅读算法，在划有横线的上 面填写合适的内容。 void purge-linkst(ListNode *&la) { ListNode p,*q; if(la==NULL)return; q=la;p=la->link; while(p){ if(p->data>q->data)(q=p;p=p->link;} else{ /删除并回收p结点 q->link= delete(p); p三 85
得分|评卷人 五、算法分析题(每小题 7分，共 4分} 29. 从表头指针为la 值从 序链 删 除 的多余元素(只保留一个结点) ，并释放被删结点的动态存储空间。阅读算法，在划有横线的上 面填写合适的内容。 void purge-linkstCListNode &. la) ListNode 铃p 铃q; ifCIa= = NULL) return; ; \ q=la; p=la一>link; whileCp) { f(p 一>data>q 一>data) {q=p; p=p一>link;} else { / /删除并回收 一>link= deleteC p) ; p= 85
30.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (ElemType data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功 能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算 法，在划有横线的上面填写合适的内容。 BinTreeNode BTF(BinTreeNode BT,ElemType x) if(BT==NULL)NULL; else{ if(BT->data==x) else BinTreeNode t; if(t=BTF(BT->left,x))return t; if(t= return t; return NULL; } 86
30. 型BinTreeNode 定义 struct BinTreeNode {ElemType data; BinTreeNode 铃left ，祷 gh 其中 a为结点值域，left 和right 针域 下 面 能是从二叉树 T中查找值为 X的结点，若查找成功则返回结点地址，否则返回空。阅读算 法，在划有横线的上面填写合适的内容。 BinTreeNode铸BTF(BinTreeNode 铃BT ElemType x) if(BT= =NULL) NULL; else { f(BT 一>data==x) else { BinTreeNode 秘t; 86 f( (B left , x)) return t; if(t= ) return t; return NULL;
试卷代号：1010 中央广播电视大学2011一2012学年度第二学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2012年7月 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1.B 2.C 3.C 4.D 5.C 6.B 7.D 8.B 9.A 二、判断题，在每小题后面的括号内打对号（√）表示叙述正确或打叉号(×)表示叙述错误（每 小题2分，共14分) 10./(对) 11.×(错) 12.√/（对） 13.×(错) 14./(对) 15.×(错) 16./(对) 三、填空题，在横线处填写合适的内容（每小题2分，共14分） 17.先出 18.MaxSize-1 19.31 20.最大值 21.R-1 22.O(log2n) 23.2 四、运算题（每小题8分，共40分） 24.先序：A,B,D,G,C,E,F /13分 中序：B,G,D,A,E,C,F /13分 按层：A,B,C,D,E,F,G /12分 25.元素 34 56 58 63 比较次数 2 1 34 //得分 2分2分2分 2分 87
试卷代号 中央广播电视大学 11 2012 学年 第二学 开放 末考 数据结构试题答案及评分标准 (供参考) 2012 年7 一、单项选择题，在括号内填写所选择的标号(每小题 2分，共 8分} 1. B 6. B 2. C 7. D 3. C 8. B 4. D 9. A 5. C 二、判断题，在每小题后面的括号内打对号 .J )表示叙述正确或打叉号( X )表示叙述错误(每 小题 2分，共 4分} 10. .J (对) 11. X( 12. .J (对) 13. X (错) 14. .J (对) 15. X (错) 16. .J (对) 三、填空题，在横线处填写合适的内容(每小题 2分，共 14分) 17. 18. MaxSize-1 19. 31 20 21. i'l,- 1 22. 23. 2 四、运算题(每小题 8分，共 0分) 24. 序:A ，B ，D ，G ，C ，E ，F //3 中序 1/3 按层 //2 25. 34 56 58 63 比较次数 /1得分 2 1 3 4 分2 分2 分2 87
26.分支结点数：5 /4分 叶子结点数：3 //4分 27.(0,3)14,(3,4)18,(4,5)6,(5,1)5,(4,2)11 /得分：2分 2分 2分 1分 1分 28. 元素： 19 40 68 存储位置： 5 6 1 查找长度： 1 2 得分： 3分 3分 2分 五、算法分析题(7分，共14分) 评分标准：每小题对一空得4分，全对得7分。 29.p->link、q->link 30.return BT,BTF(BT->right,x) 88
26. 支结 114 叶子结点数 114 27. (0 ,3)14 , (3 ,4)18 , (4 ,5)6 , (5 , 1)5 , (4 ,2)11 II得分 28. 19 40 68 5 6 l 1 2 4 元素 存储位置 查找长度 得分 五、算法分析题 7分，共 14分} 评分标准:每小题对一空得 4分，全对得 7分。 29. l i nk li 30. return BT 、BTF(BT一>right 88