试卷代号：1010 座位号■ 中央广播电视大学2008一2009学年度第二学期“开放本科”期末考试 数据结构 试题 2009年7月 题 号 二 三 四 五 六 总 分 分数 得分 评卷人 一、单项选择题（在括号内填写所选择的标号，每小题2分，共18分） 1.当一个作为实际参数传递的对象占用的存储空间较大并且需要修改时，则对应的形参 应说明为()。 A.基本类型 B.引用型 C.传值型 ·D.常值引用型 2.在一个长度为的顺序表的任一位置插入一个新元素的时间复杂度为()。 A.O(n) B.O(n/2) C.0(1) D.O(n2) 3.栈的插人和删除操作在( )进行 A.栈顶 B.栈底 C.任意位置 D.中间位置 4.已知一个广义表为A(a,b,c),(d,e,fD),从A中取出原子e的运算是()。 A.Tail(Head(A)) B.Head(Tail(A)) C.Head(Tail(Head(Tail(A)))) D.Head(Head(Tail(Tail(A)))) 5.在一棵二叉树的链接存储中，每个存储结点至少要包含( )个指针域。 A.1 B.2 C.3 D.4 71
试卷代号:1010 座位号口二」 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试 数据结构 试题 2009年 7月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题 (在括号内填写所选择的标号 ，每小题 2分 ，共 18分) 1.当一个作为实际参数传递的对象占用的存储空间较大并且需要修改时，则对应的形参 应说明为( )。 A.基本类型 B.引用型 C.传值型 D.常值引用型 2.在一个长度为 n的顺序表的任一位置插人一个新元素的时间复杂度为( )。 A. O (n) B. O(n/2) C. O(1) D. O (n2) 3.栈的插人和删除操作在( )进行。 A.栈顶 B.栈底 C.任意位置 D.中间位置 4.已知一个广义表为 A((a,b,c),(d,e,f))，从 A中取出原子 e的运算是( )。 A. Tail(Head(A)) B. Head(Tail(A)) C. Head(Tail(Head(Tail(A)))) D. Head (Head (Tail (Tail (A)))) 5.在一棵二叉树的链接存储中，每个存储结点至少要包含( )个指针域。 A. 1 B. 2 C. 3 D. 4 71
6.有向图中的一个顶点的度数等于该顶点的()。 A.入度 B.出度 C.入度与出度之和 D.(入度十出度)/2 7.与邻接矩阵相比，邻接表更适合于存储( )。 A.无向图 B.连通图 C.稀疏图 D.稠密图 8.在通常情况下，查找数据较快的方法是( )查找方法。 A.顺序 B.折半 C.二叉树 D.散列 9.在一棵m阶B树中，每个结点所包含的子树个数最多为( )个。 A.m/2 B.m-1 C.m D.m+1 得 分 评卷人 二、填空题（在横线处填写合适的内容，每小题2分，共14分）】 1.在单链表中设置表头附加结点的作用是在插入和删除表中任一个元素时的操作都 2.设顺序栈的最大容量为MaxSize,top==一1表示栈空，则判断栈满的条件是top== 3.在一棵高度为4的完全二叉树中，最多包含有 个结点。假定树根结点的高度 为0。 4.在一个最大堆中，堆顶结点的值是所有结点中的 5.具有n个顶点的连通图的生成树含有 条边。 6.在对个结点进行的堆排序中，对任意一个分支结点进行调整（筛）运算的时间复杂度 为 7.假定一个线性表的关键码序列为(12,23,74,55,63,40,82,36)，若按ky%3条件进行 划分，使得同一余数的元素成为一个子表，则元素74所在子表的长度为 72
6.有向图中的一个顶点的度数等于该顶点的( )。 A.人度 B.出度 C.人度与出度之和 D.(人度十出度)/2 7.与邻接矩阵相比，邻接表更适合于存储( )。 A.无 向图 B.连通图 C.稀疏图 D.稠密图 8.在通常情况下，查找数据较快的方法是( )查找方法。 A.顺序 B.折半 C.二叉树 D.散列 9.在一棵 m 阶 B树 中，每个结点所包含的子树个数最多为( )个 。 A. m/2 B. m一1 C. m D. m + 1 得 分 评卷人 二、填空题(在横线处填写合适的内容 ，每小题 2分 ，共 14分 ) 在单链表 中设 置表头附加结点的作用是在插人 和删除表 中任 一个元素 时 的操作 都 2.设顺序栈的最大容量为 Ma xSize, top= = -1表示栈空，则判断栈满的条件是 top= = 3.在一棵高度为 4的完全二叉树 中，最多包含有 个结点。假定树根结点的高度 为 0 4.在一个最大堆 中，堆顶结点的值是所有结点 中的 5.具有n个顶点的连通图的生成树含有_ 条边。 6.在对 n个结点进行的堆排序中，对任意一个分支结点进行调整(筛)运算的时间复杂度 7.假定一个线性表的关键码序列为(12,23,74,55,63,40,82,36)，若按key 0a3条件进行 划分，使得同一余数的元素成为一个子表，则元素 74所在子表的长度为_ 。 72
得 分 评卷人 三、判断题（在每小题前面打对号表示正确或打叉号表示错误，每小 题2分，共14分) )1.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 )2.链式栈与顺序栈相比，一个明显的优点是通常不会出现栈满的情况。 )3.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被 调整到堆顶位置为止。 ( )4.在一棵二叉树中，假定每个结点只有右子女，没有左子女，则对它分别进行前序遍历 和后序遍历时，将具有相同的结果。 )5.向具有n个结点的堆中插人一个元素的时间复杂度为O(n)。 )6.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近， 则得到的将是最优二叉搜索树。 )7.对一个有向图进行拓扑排序，一定可以将图中的所有顶点排列成一个线性有序的拓 扑序列。 得分 评卷人 四、运算题（每小题6分，共30分）】 1.已知一棵二叉树的中序和后序序列如下，求出该二叉树的所有分支结点数和叶子结点数。 中序序列：c,b,d,e,a,g,f 后序序列：c,e,d,b,g,f,a 分支结点数： 叶子结点数： 2.已知图G=(V,E),其中 V=(a,b,c,d,e) E={,,,,,,,} 假定该图采用邻接表作为存储结构，每个顶点邻接表是按照顶点ASCⅡ码值的次序链接 的，试分别写出从顶点开始进行深度和广度搜索遍历所得到的顶点序列。 深度搜索顶点序列： 广度搜索顶点序列： 73
得 分 评卷人 三、判断题 (在每小题前面打对号表示正确或打叉号表示错误 ，每小 题 2分，共 14分) ) 1.在顺序表 中，逻辑上相邻 的元素在物理位置上不一定相邻。 )2.链式栈与顺序栈相 比，一个 明显的优点是通常不会出现栈满的情况 。 )3.当向一个最小堆插人一个具有最小值 的元素时，该元素需要逐层 向上调整 ，直 到被 调整到堆顶位置为止。 )4.在一棵二叉树中，假定每个结点只有右子女 ，没有左子女，则对它分别进行前序遍历 和后序遍历时，将具有相同的结果 。 )5.向具有 n个结点的堆中插人一个元素的时间复杂度为 O(n)a )6.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近， 则得到的将是最优二叉搜索树 。 )7.对一个有向图进行拓扑排序，一定可以将图中的所有顶点排列成一个线性有序的拓 扑序列。 得 分 评卷人 R.运算题 (每小题 6分 .共 30分) 1.已知一棵二叉树的中序和后序序列如下，求出该二叉树的所有分支结点数和叶子结点数 。 中序序列:c,b,d,e,a,g,f 后序序列:c,e,d,b,g,f,a 分支结点数 : 叶子结点数: 2.已知图 G= (V, E)，其中 V= (a, b, c, d, e) E= ( ， ， ， ， ， ， ， } 假定该图采用邻接表作为存储结构，每个顶点邻接表是按照顶点 ASCII码值的次序链接 的，试分别写出从顶点 a开始进行深度和广度搜索遍历所得到的顶点序列。 深度搜索顶点序列 : 广度搜索顶点序列 :
3.已知一个带权图的顶点集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,(3,4)18,(4,5)6}; 试根据迪克斯特拉(Dijkstra)算法求出从顶点O到其余各顶点的最短路径，在下表中填写 对应的路径长度。 顶点： 0 2 3 4 5 路径长度： 0 4.设散列表的长度m=7,散列函数为H(K)=K mod m,若采用线性探查法解决冲突， 待依次插入的关键码序列为{19,14,23,68,20,84}，分别求出查找14、20、84时的搜索长度。 查找14、20、84的搜索长度分别为： 5.已知一个数据集合为{36,25,30,62,40,53,46}，试把它调整为一个最大堆。 最大堆： 得 分 评卷人 五、算法分析题（每小题6分，共12分） 1.该算法功能为：从表头指针为L的单链表中删除与X值相同的所有结点。单链表中的 结点结构为(data,link)。阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode *L,int X) { if(L==NULL)return; ListNode *p,pl,p2; p=pl=new ListNode; pl->link=p2=L; while (p2) if(p2->data==X)(pl->link=p2->link;delete p2;p2=pl->link;) else L=p->link; delete p; 74
3.已知一个带权图的顶点集 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，(3,4)18，(4,5)6}; 试根据迪克斯特拉(Dijkstra)算法求出从顶点 。到其余各顶点的最短路径，在下表中填写 对应的路径长度。 顶点 : 路径长度 : 0 1 2 3 4 5 0 { 一 ! } } 4.设散列表的长度 m=7，散列函数为 H(K)=K mod m，若采用线性探查法解决冲突， 待依次插人的关键码序列为{19,14,23,68,20,84}，分别求出查找 14,20,84时的搜索长度。 查找 14,20,84的搜索长度分别为: 5.已知一个数据集合为{36,25,30,62,40,53,461，试把它调整为一个最大堆。 最 大堆 : 得 分 评卷人 五、算法分析题(每小题 6分 ，共 12分) 1.该算法功能为 :从表头指针为 L的单链表中删除与 X值相 同的所有结点。单链表中的 结点结构为(data, link)。阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode二aL, int X) { if(L==NULL) return; ListNode，P,‘PI，‘p2; p=p1=new ListNode; pl一>link=p2=L; while (p2) if (p2一>data==X){PI一>link=p2一>link; delete p2;p2=pl一>link;} else{ ; ;} L=p一>link; delete p; }
2.指出下面算法的功能 int unknown(int A[],int n){ if(n==1)return A[0]; int temp=unknown(A,n-1); if(A[n-1]>temp)return A[n-1];else return temp; } 算法功能： 得 分 评卷人 六、算法设计题（每小题6分，共12分】 l.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (char data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声 明编写出求一棵二叉又树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指 向这棵二叉树的根结点。 int BTreeLeafCount(BinTreeNode BT); 2.假定下面函数reArrange通过扫描一遍data数组达到重新排列数据的目的，使得所 有负值数据位于所有非负值和0值数据之前。请补充完整reArrange函数体中遗漏部分，使 其能够完成所要求的功能。 template void reArrange(T data[],int size)( int i=0,j=size-1; T temp; while(ii)j--; if(i<j) //在下面空行添加f语句的内容 i++;j-一 75
2.指出下面算法的功能 int unknown(int A[]，int n){ if(n==1)return A[0]; int temp=unknown(A，n一1); if(A[n一1]>temp) return A[n一1];else return temp; 算法功能: 得 分 评卷人 六、算法设计题(每小题 6分 ，共 12分 ) 1.已知二叉树中的结点类型 BinTreeNode定义为: struct BinTreeNode{char data; BinTreeNode*left，二right;}; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声 明编写 出求一棵二叉树中叶子结点总数的算法 ，该总数值由函数返回。假定参数 BT初始指 向这棵二叉树的根结点。 int BTreeLeafCount(BinTreeNode*BT); 2.假定下面函数 reArrange通过扫描一遍 data数组达到重新排列数据的 目的，使得所 有负值数据位于所有非负值和 。值数据之前。请补充完整 reArrange函数体中遗漏部分，使 其能够完成所要求的功能。 template void reArrange(T data[]，int size){ int 1=0,j=size一1; T temp; while(i=0 &.&j>i) j一一; if(i<j)( 刀在下面空行添加 if语句的内容 } i++ ;j一 一 ;
试卷代号：1010 中央广播电视大学2008一2009学年度第二学期“开放本科"期末考试 数据结构 试题答案及评分标准 (供参考) 2009年7月 一、单项选择题（在括号内填写所选择的标号，每小题2分，共18分） 1.B 2.A 3.A 4.C 5.B 6.C 7.C 8.D 9.C 二、填空题（在横线处填写合适的内容，每小题2分，共14分）】 1.相同 2.MaxSize-1 3.31 4.最大值 5.n-1 6.O(1og2n) 7.2 三、判断题（在每小题前面打对号表示正确或打叉号表示错误，每小题2分，共14分） 1.X 2.√ 3.V 4.X 5.X 6.V 7.X 四、运算题（每小题6分，共30分】 1.分支结点数：4、叶子结点数：3 /1全对给6分，否则0分 2.深度搜索顶点序列：a,b,d,e,c 1/3分 广度搜索顶点序列：a,b,d,e,c /3分 3.评分标准：对1个给1分，全对给6分。 顶点： 0 1 2 3 4 5 路径长度： 01610.142521 4.查找23、68、84的搜索长度分别为：1、3、4 //每个数据占2分 5.最大堆：{62,40,53,25,36,30,46) 76
试卷代号:1010 中央广播电视大学2008-2009学年度第二学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2009年 7月 一、单项选择题 (在括号内填写所选择的标号 ，每小题 2分 ，共 18分) 1.B 6.C 2.A 3.A 7.C 8.D 二、填空题(在横线处填 写合适的内容 ，每小题 2分 ，共 1.相 同 4.C 9. C 14分) 5.召 2. MaxSize一 1 3. 31 4.最大值 5. n一 1 6. O(1092n) 7. 2 三、判断题(在每小题前面打对号表示正确或打叉号表示错误，每小题2分，共 14分) 1.火 2.丫 3.侧 4.只 5.又 6.丫 7.X 四、运算题(每小题 6分，共 30分) 1.分支结点数:4、叶子结点数:3 /全对给6分，否则。分 2.深度搜索顶点序列:a,b,d,e,c //3分 广度搜索顶点序列:a,b,d,e,c //3分 3.评分标准:对 1个给 1分，全对给 6分。 顶点 : 路径长度: 4.查找 23, 5.最大堆 : 0 1 2 3 4 5 1。}16}10!14!25}21 68,84的搜索长度分别为:1,3,4 {62，40，53，25，36，30，46} 刀每个数据占2分
五、算法分析题（每小题6分，共12分） l.pl=p2、p2=p2->link(或p2=pl->link) /每空3分 2.求出并返回数组A[n]中n个数据的最大值。 六、算法设计题（每小题6分，共12分） 1.评分标准：根据编程酌情给分。 int BTreeLeafCount(BinTreeNode BT) if(BT==NULL)return 0; /1分 else if(BT->left==NULL &BT->right==NULL)return 1; 113分 else return BTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);//6 说明：函数体中的两个else保留字可以省略 2.评分标准：根据编程酌情给分。 temp=data[j];data]=data[i];data[i]=temp; //6分 77
五、算法分析题(每小题 6分，共 12分) 1. PI=p2,p2=p2一>link(或 p2“PI一>link) 2.求出并返回数组 A[n〕中二个数据的最大值。 六、算法设计题(每小题 6分，共 12分) 1.评分标准:根据编程酌情给分。 int BTreeLeafCount (BinTreeNode* BT) //每空 3分 if (BT= =NULL) return 0; elseif (BT一>left=二NULL & -&BT一>right= =NULL) return 1; else return BTreeLeafCount(BT一>left) +BTreeLeafCount(BT一>right) } 说明:函数体 中的两个 else保 留字可以省略 2.评分标准:根据编程酌情给分。 temp= data[j];data[j]“data[i];data[i]=temp; //1分 //3分 刀6分 刀6分
