试卷代号：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.已知一棵树的边集表示为{<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.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与( )有关。 A.n B.m C.n/m D.n*m 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.在链表中进行数据元素的插入和删除不需要移动结点，只需要改变相应结点的 的值。 2.队列是一种限定在表的一端插入，而在另一端删除的线性表，它又被称为 表。 3.如果一个过程直接地调用自己，则称这个过程是一个 的过程。 4.假定一棵三叉树（即度为3的树）的结点个数为25，则它的最小高度为 。假定 树根结点的高度为0。 72
5. 棵 树 为{<A B> , <A, C> , <B, D> , <C, E> , <C, F> , <C,G> ,<F >， 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