试卷代号：1010 座位 中央广播电视大学2009一2010学年度第二学期“开放本科”期末考试 数据结构 试题 2010年7月 题 号 二 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 1.输出一个二维数组b[m][n]中所有元素的时间复杂度为()。 A.O(n) B.O(m+n) C.0(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.top=0; D.top=1; 4.在一棵树中，(（ )没有前驱结点。 A.树枝结点 B.叶子结点 C.树根结点 D.单分支结点 71
试卷代号 座位号 中央广播电视大学 2010 学期 开放本科 数据结构试题 2010 年7 题号 /-i- 总分 分数 得分 i评卷人 -、单项选择题(在括号内填写所选择的标号。每小题 分} 1.输出一个二维数组 ]中所有元素的时间复杂度为( )。 A. 0(0) B. O(m+o) C. 0(02 ) D. Oem 2. 长度 序存 序表 最好 为( )。 A. 00) C. O(lOg 20 ) B. O(Jn) D. 0(0) 3. 利用 为n 存储 假定用top==n表示钱空 个战 入一个元素时，首先应执行( )语句修改 o p A. top 十 十 C. top=O; 4. 棵树 ( )没有前驱结点。 A. 枝结 C. B. topD. top= 1; B.叶子结点 D. 71
5.已知一棵树的边集表示为{,,,,, ,,},则该树的深度为()。假定树根结点的深度为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.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与( )有关。 A.n B.m C.n/m D.n*m 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.在链表中进行数据元素的插入和删除不需要移动结点，只需要改变相应结点的 的值。 2.队列是一种限定在表的一端插入，而在另一端删除的线性表，它又被称为 表。 3.如果一个过程直接地调用自己，则称这个过程是一个 的过程。 4.假定一棵三叉树（即度为3的树）的结点个数为25，则它的最小高度为 。假定 树根结点的高度为0。 72
5. 棵 树 为{ , , , , , ,， F， }，则该树的深度为( )。假定树根结点的深度为0。 A. 2 R 3 C4 D.5 6. 个顶 连通 少含有 )条边。 A. n-1 R n C. n(n-I)/ 2 D. n(n-I) 7. )条边。 A. n-1 C n(n I) B. n(n-I)/ 2 D. n(n-I) 8. 采用 链接法 每一 地址 链接 个表项的( )的值都相同。 A. 关键码B. 关键 数D. 9. 对存 个元 进行搜 搜索长度 )有关。 A. n C. n/m 得分|评卷人 B. m D. 祷m 二、填空题(在横线处填写合适的内容。每小题 2分，共 4分} 的过程。 。假定 1.在链表中进行数据元素的插入和删除不需要移动结点，只需要改变相应结点的 的值。 2. 是 一 种 定 在 表 一 端 删 除 性 表 称 为 表。 3. 果一 过程 调用 个过程是 4. 为3 个数为25 则 它 树根结点的高度为 0。 72
5.在一个堆的顺序存储中，若一个元素的下标为i(≥0)，则它的左子女元素的下标为 6.根据n个元素建立一棵二叉搜索树的时间复杂度大致为 7.快速排序在最坏情况下的空间复杂度为 得 分 评卷人 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉 号“×”表示叙述错误。每小题2分，共14分) 1.在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。（) 2.用非递归方法实现递归算法时一定要使用临时数据栈。() 3.在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行中序遍历和 后序遍历，将具有相同的结果。() 4.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的 降序排列存放，则可得到最小的平均搜索长度。() 5.快速排序算法在平均情况下的时间复杂度为O(nlog2n)。() 6.直接选择排序是一种不稳定的排序方法。() 7.在具有n个结点的二叉树的链接存储中，所有结点的指针域的总数小于2个。 得 分 评卷人 四、运算题（每小题6分，共30分】 1.假定一棵普通树的广义表表示为a(b(e),c(f,g,d),试分别写出对其进行先根和按层 遍历的结果。 先根： 按层： 2.假定一维数组a[10]中存储着有序表(15,26,34,39,45,56,58,63,74,76)，试根据折半 搜索所对应的判定树，给出该判定树中叶子结点数，以及在等概率情况下的平均搜索长度。 叶子结点数： 平均搜索长度： 73
5. 个元 为i(i~O) ，则它的左子女元素的下标为 6. 个元 建立 二叉搜 杂度 7. 在最坏 况下 复杂 得分|评卷人 三、判断题(在每小题后面的括号内打对号"~ "表示叙述正确或打叉 "表示叙述错误。每小题 2分，共 4分) 1.在一个顺序存储的循环队列中，队头指针指向队头元素的后一个位置。( ) 2. 用非递 现递 要使 数据 ) 3. 在一 二叉 子女 没有右 进行 序遍 后序遍历，将具有相同的结果。( ) 4. 行顺 各元 索棋 不 等 各元 应按 索概 降序排列存放，则可得到最小的平均搜索长度。( ) 5. 速排 算法在平均 杂度为O(nlog ) 6. 直接选择排 一种不稳定 ) 7. 有n 个结 叉树 链接 针域 于2n ( ) 得分|评卷人 四、运算题{每小题 6分，共 0分) 1.假定一棵普通树的广义表表示为 (时， c(f， g， ，试分别写出对其进行先根和按层 遍历的结果。 先根: 按层: 2. 一维 组a[10] 表(15 ，26 ，34 ，39 ，45 ，56 ，58 ，63 ，74 ，76) 根据 搜索所对应的判定树，给出该判定树中叶子结点数，以及在等概率情况下的平均搜索长度。 叶子结点数: 平均搜索长度: 73
3.已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5}; E={(0,1),(1,2),(1,3),(2,4),(2,5),(3,5)} 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点2出发进行深度优先 搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 4.已知一个带权图的顶点集V和边集G分别为： V={0,1,2,3,4,5}; E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(4,5)8}; 试根据迪克斯特拉(Dijkstra)算法求出从顶点O到其余各顶点的最短路径长度。 顶点： 最短路径长度： 1 2 3 4 5 0 5.已知有一个数据集合为{30,18,20,15,38,12,44,53,46,86}，给出进行归并排序的过 程中每一趟排序后的数据表变化。 (0)[30182015381244534686] (1) (2) (3) (4) 74
3. 图 的 集V 集G V={O ,1 ,2 ,3 ,4 ,5}; E={(O (1 ，2) (1 ，3) ，(2 ，(2 ，(3 ，5)}; 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点2出发进行深度优先 搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列: 广度优先搜索序列: 4. 带权 集V 集G V={O ,1 ,2 ,3 ,4 ,5}; E={(O ，1)19 ，(O ，2)10 ，(O ，3)14 ，2)6 ，(1 ，5，)5 ，(2 ，3)26 ，(2 ，4)15 ，(4 ，5)8}; 试根据迪克斯特拉 )算法求出从顶点O到其余各顶点的最短路径长度。 顶点: 最短路径长度: O 1 2 3 4 5 O FD PO , o o qL , n 0 nu14nu qu 74
得 分 评卷人 五、算法分析题（每小题8分，共16分） 1.指出下面算法的功能，假定f为单链表的表头指针，在算法中的getLink()函数返回结 点指针域link的值，getData()函数返回结点数据域data的值。 ElemType FF(ListNode f) { if(f==NULL)return 0; else return FF(f->getLink())+f->getData(); } 算法功能： 2.该算法功能为：从表头指针为L的单链表中删除与X值相同的所有结点。单链表中 的结点结构为(data,link)。阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode *L,int X) if(L==NULL)return; ListNode p,pl,p2; p=pl=new ListNode; p1->link=p2=L; while (p2) if(p2->data==X)(pl->link=p2->link;delete p2; else pl-p2; L=p->link; delete p; 75
得分|评卷人 五、算法分析题{每小题 8分，共 6分} 1.指出下面算法的功能，假定 f为单链表的表头指针，在算法中的 )函数返回结 点指针域 li k的值， )函数返回结点数据域 a的值。 ElemType FF(ListNode f) if(f= = NULL) return 0; else return FF(f 一>getLink())+f一>getDataO; 算法功能: 2. 该算 能为 指针 为L 单链表 与X 单链表 的结点结构为 a， link) 在划有横线 写合 void purge_linkst(ListNode &. L, int X) if(L= =NULL) return; ListNode 铃p 祷pI 势p2; p=pl =new ListNode; pI 一>link=p2=L; while (p2) if(p2一>data==X) {pI 一>link=p2 link; delete p2; else { pl=p2; L=p一>link; delete p; 75
得 分 评卷人 六、算法设计题(8分) 已知f为单链表的表头指针，单链表中的结点结构为(data,link),并假定每个结点的值均 为大于0的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最小值，若单链 表为空则返回数值0。 int Min(LinkNode￥f); 76
得分|评卷人 六、算法设计题 8分) 已知 单链 结构 ，并假定每个结点的值均 为大于 O的整数。根据下面函数声明写出递归算法，返回单链表中所有结点的最小值，若单链 表为空则返回数值 0。 int Min(LinkNode 76
试卷代号：1010 中央广播电视大学2009一2010学年度第二学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2010年7月 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18分） 1.D 2.A 3.B 4.C 5.B 6.A 7.B 8.C 9.C 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.指针域 2.先进先出 3.递归 4.3 5.2i+1 6.O(nlogzn) 7.0(n) 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉号“X”表示叙述错误。每 小题2分，共14分) 1.错 2.错 3.对 4.对 5.对 6.对 7.错 四、运算题（每小题6分，共30分】 1.先根：a,b,e,c,f,g,d 113分 按层：a,b,c,e,f,g,d /3分 2.叶子结点数：3/3分 平均搜索长度：29/10 /13分 3.深度搜索序列：2,1,0,3,5,4 /3分 广度搜索序列：2,1,4,5,0,3 /13分 77
试卷代号 中央广播电视大学 0 0 2010 数据结构试题答案及评分标准 (供参考) 2010 年7 -、单项选择题{在括号内填写所选择的标号。每小题 l. D 6. A 2. A 7. B 3. B 8. C 4. C 9. C 5. B 二、填空题(在横线处填写合适的内容。每小题 1.指针域 2. 进先 3. 4. 3 5. 2i 十1 6. 0(nlog2n) 7. O(n) 三、判断题{在每小题后面的括号内打对号..J 正确 或打叉号 叙述 小题 1.错 .错 .对 .对 .对 .对 .错 四、运算题(每小题 1.先根 //3 按层 //3 2. 子结 数:3 //3 平均搜索长度 9 / //3 3. 深度 列:2 ，1 ，0 ，3 ，5 ，4 //3 广度搜索序列 //3 77
4.每个数据1分，全对给6分。 顶点： 0 1 2 3 4 5 0 16 10 14 25 最短路径长度： 21 5.分步给分，共6分 (0)[30182015381244534686] (1)[1830][1520][1238][4453][4686] /1分 (2)[15182030][12384453][4686] //1分 (3)[1215182030384453][4686] /12分 (4)[12151820303844465386] /2分 五、算法分析题（每小题8分，共16分） 1.求出并返回链表f中所有结点的值之和。 2.p2=pl->link、p2=p2->link(或p2=pl->link) /每空4分 六、算法设计题(8分)】 评分标准：按注释酌情给分。 int Min(LinkNode f) if(f==NULL)return 0; /1分 if(f->link==NULL)return f->data; /2分 int temp=Min(f->link); /4分 if(f->datadata; /6分 else return temp; //8分 78
O 1 2 3 4 5 O 16 10 14 25 21 4. 个数据1 给6 顶点: 最短路径长度 5. 步给 共6 (0) link 、p2=p2 一>link( 或p2=pl 一>link) 六、算法设计题 8分) 评分标准:按注释酌情给分。 int 1in(LinkNode f) if(f==NULL) return 0; //1 f(f一>link==NULL) return 一>data; / /2 int temp=Min(f一>link); //4 if(f一>datadata; / /6 else return temp; / /8 78 //每空 4分