试卷代号：1010 座位■■ 中央广播电视大学2009一2010学年度第一学期“开放本科”期末考试 数据结构试题 2010年1月 题号 二 三 四 五 六 总 分 分 数 得分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 1.下面程序段的时间复杂度为()。 for(int i=0;i<m;i++) for(int j=0;j<n;j++)a[i]]=i*j; A.0(m2) B.O(n2) C.O(m n) D.O(m+n) 2.在二维数组中，每个数组元素同时处于( .)个向量中。 A.0 B.1 C.2 D.n 3.设有两个串t和p,求p在t中首次出现的位置的运算叫做( ）。 A.求子串 B.模式匹配 C.串替换 D.串连接 4.利用双向链表存储线性表的优点是( )。 A.便于单向进行插入和删除的操作 B.便于双向进行插入和删除的操作 C.节省空间 D.只便于插入操作，不便于删除操作 74
试卷代号 :1010 座位号口口 中央广播电视大学2009-2010学年度第一学期“开放本科”期末考试 数据结构 试题 2010年 1月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题(在括号内填写所选择的标号。每小题 2分，共 18 分) 1.下面程序段的时间复杂度为( ) for(int i=0;K m; i++) for(int j二0;j<n; j++)a[i][j] = i，j; A. O < z) C. O(m * n) B. O (n') D. O(m+n) 2.在二维数组中，每个数组元素同时处于( _)个向量中。 A.0 B. 1 C. 2 D. n 3.设有两个串t和 P，求 P在 t中首次出现的位置的运算叫做( A.求子串 B.模式匹配 C.串替换 D.串连接 4.利用双向链表存储线性表的优点是( )。 A.便于单向进行插人和删除的操作 B.便于双向进行插人和删除的操作 C.节省空间 D.只便于插人操作，不便于删除操作
5.设链式栈中结点的结构为(data,link),且top是指向栈顶的指针。若想在链式栈的 栈顶插入一个由指针s所指向的结点，则应执行( )操作。 A.top->link=s; B.s->link=top->link;top->link=s; C.s->link=top;top=s; D.s->link=top;top=top->link; 6.一棵具有12个结点的完全二叉树的高度为( ),假定空树的高度为一1。 A.3 B.4 C.5 D.6 7.向具有n个结点的堆中插人一个新元素的时间复杂度为()。 A.O(1) B.O(n) C.O(log2n) D.O(nlog2 n) 8.在一棵AVL树中，每个结点的平衡因子的取值范围是( A.-11 B.-2~2 C.1~2 D.01 9.一个有n个顶点和n条边的无向图一定是( )的 A.连通 B.不连通 C.无回路 D.有回路 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.在类的继承结构中，位于上层的类叫做基类或父类，而位于下层的类叫做派生类或 类。 2.设链栈中结点的结构为(data,link),栈顶指针为top,当从该链栈删除一个结点时，应 把 的值赋给top。 3.广义表的 定义为广义表中括号被嵌套的最大重数。 4.在一棵高度为3的完全二叉树中，最少含有 个结点。假定树根结点的高度为0。 75
5.设链式栈中结点的结构为(data, link)，且 top是指向栈顶的指针。若想在链式栈的 栈顶插人一个由指针 s所指向的结点，则应执行( )操作。 A. top一>link=s; B. s一>link=top一>link; top一>link=s; C. s一>link= top;top=s; D. s一>link= top;top=top一>link; 6.一棵具有12个结点的完全二叉树的高度为( )，假定空树的高度为一to A. 3 B. 4 C. 5 D. 6 7.向具有 n个结点的堆中插人一个新元素的时间复杂度为( )。 A.- O(1) B. O(n) C. O(log2n) D. 0(n1092n) 8.在一棵 AVL树中，每个结点的平衡因子的取值范围是( )。 A.一 1- 1 B.- 2- 2 C. 1- 2 D. o一 1 9.一个有 n个顶点和 n条边的无向图一定是( )的。 A.连 通 C.无回路 B.不连通 D.有回路 得 分 评卷人 二、填空题(在横线处填写合适的内容。每小题 2分，共 14分) 1.在类的继承结构中，位于上层的类叫做基类或父类，而位于下层的类叫做派生类或 类 。 2.设链栈中结点的结构为(data, link) ,栈顶指针为 top，当从该链栈删除一个结点时，应 把 的值赋给 top o 3.广义表的_ 定义为广义表中括号被嵌套的最大重数。 4.在一棵高度为3的完全二叉树中，最少含有_ 个结点。假定树根结点的高度为。。 75
5.从有序表(12,18,30,43,56,78,82,95)中折半搜索56元素时，其搜索长度为 6.具有n个顶点的连通图中至少含有 条边。 7.假定一个数据集合为{46,79,56,38,40,84}，则在构成的最大堆（即大根堆）中，其堆顶 元素为 得 分 评卷人 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉 号“×”表示叙述错误。每小题2分，共14分) 1.线性表若采用链式存储表示时，具存储结点的地址可连续也可不连续。（) 2.在用单链表表示的链式队列Q中，假定队头指针为Q一>front,队尾指针为Q一> rear,则链队为空的条件为Q一>front-==Q->rear。（) 3.一棵AVL树的所有叶结点不一定在同一层上。() 4.在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，若对它分别进行中序遍历和 后序遍历，则具有相同的遍历结果。() 5.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。() 6.对一个用顶点表示活动的网络(AOV网)进行拓扑排序的结果是唯一的。() 7.堆排序是一种稳定的排序方法。() 得 分 评卷人 四、运算题（每小题6分，共30分）】 1.已知一棵二叉树的中序和后序序列如下，求该二叉树的根结点和左、右子树中的结点 数。 中序序列：c,b,d,e,a,g,f 后序序列：c,e,d,b,g,f,a 根结点： 左子树中的结点数： 右子树中的结点数： 76
5.从有序表 (12, 18, 30, 43, 56, 78, 82, 95)中折半搜索 56元素 时，其搜索长度为 .具有 n个顶点的连通图中至少含有 条边。 .假定一个数据集合为{46,79,56,38,40,84}，则在构成的最大堆(即大根堆)中，其堆顶 元素为 得 分 评卷人 三、判断题 (在每小题后面的括号内打对号“丫”表示叙述正确或打叉 号“X”表示叙述错误。每小题2分，共14分) 1.线性表若采用链式存储表示时，具存储结点的地址可连续也可不连续。( ) 2.在用单链表表示的链式队列 Q中，假定队头指针为 Q- > front，队尾指针为 Q-> rear，则链队为空的条件为 Q->front==Q->rear.( ) 3.一棵 AVL树的所有叶结点不一定在同一层上。( ) 4.在一棵二叉树中，假定每个结点只有左孩子，没有右孩子，若对它分别进行中序遍历和 后序遍历，则具有相同的遍历结果。( ) 5.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。( ) 6.对一个用顶点表示活动的网络(AOV网)进行拓扑排序的结果是唯一的。( ) 7.堆排序是一种稳定 的排序方法。( ) 得 分 评卷人 四、运算题(每小题 6分.共 30分) 1.已知一棵二叉树的中序和后序序列如下 ，求该二叉树 的根结点和左 、右子树 中的结点 数 中序序列:c,b,d,e,a,g,f 后序序列:c,e,d,b,g,f,a 根结点: 左子树中的结点数: 右子树中的结点数 :
2.假定一组记录为(40,28,16,56,50,32,38)，从空树起按次序插入每个记录生成一棵二 叉搜索树，求出该树中的双支结点数和叶子结点数。 双支结点数： 叶子结点数： 3.已知一个图的顶点集V和边集G分别为： V={0,1,2,3,4,5}; E={(0,1),(1,2),(1,3),(2,4),(2,5),(3,5)}; 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点1出发进行深度优先 搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 4.已知一个带权图的顶点集V和边集G分别为： V={0,1,2,3,4}; E={(0,1)15,(0,2)2,(0,3)4,(1,2)10,(1,4)5,(2,3)8,(2,4)11,(3,4)12}: 试根据克鲁斯卡尔算法求出最小生成树，在下面填写依次得到的各条边。 5.已知一个数据表为{48,25,56,32,40,66}，写出在建立最大堆的过程中，依次对相应元 素进行调整（筛）运算的结果。 (0)482556324066 (1) (2) (3) 77
2.假定一组记录为(40,28,16,56,50,32,38)，从空树起按次序插人每个记录生成一棵二 叉搜索树，求出该树中的双支结点数和叶子结点数。 双支结点数: 叶子结点数 : 3.已知一个图的顶点集 V和边集 G分别为: V={0，1，2，3,4，5}; E={(0，1)，(1,2)，(1，3)，(2,4)，(2，5)，(3,5)}; 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点 1出发进行深度优先 搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列 : 广度优先搜索序列 : 4.已知一个带权图的顶点集 V和边集G分别为: V={0，1,2，3,4}; E={(0，1)15，(0，2)2，(0，3)4，(1，2)10，(1,4)5，(2，3)8，(2，4)11，(3，4)12}; 试根据克鲁斯卡尔算法求 出最小生成树 ，在下面填写依次得到的各条边。 5.已知一个数据表为(48,25,56,32,40,60，写出在建立最大堆的过程中，依次对相应元 素进行调整(筛)运算的结果。 (0) 48 25 56 32 40 66 、 产 、 ，产 1 1 9 口 / J、 了矛 、 (3)
得分 评卷人 五、算法分析题（每小题8分，共16分） 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; /pl成为p2的前驱结点，p2指向L中的待处理结点 while (p2) if(p2->data==X)(p1->link=p2->link;delete p2;p2=p1->link;} else ；} L=p->link; delete p; 2.指出下面算法的功能 int unknown(int A],int n){ if(n==1)return AC0]; int temp=unknown(A,n-1); if(A[n-1]>temp)return A[n-1];else return temp; 算法功能： 78
得 分 评卷人 五 、算法分析题 (每小题 8分 ，共 16分 ) 1.该算法功能为:从表头指针为 L的单链表中删除与 X值相同的所有结点。单链表中 的结点结构为(data, link)。阅读算法，在划有横线的上面填写合适的内容。 void purge_linkst(ListNode*&L, int X) if(L==NULL) return; ListNode * p, * p1，* p2; p=p1=new ListNodt!; PI一>link=p2=L; while (p2) //pl成为 p2的前驱结点，p2指向 L中的待处理结点 if (p2一>data二=X) (pl一>link= p2一>link; delete p2;p2=p1一>link; else{ ; ;} L=p一>link; delete p; 2.指出下面算法的功能 int unknown(int A[]，int n){ if( int n==1) return A [O]; temp=unknown(A, n一1); if (A[n一1]>temp) return A[n-1];else return temp; 算法功能: 78
得分 评卷人 六、算法设计题(8分)】 设Q是一个由其队尾指针和队列长度标识的循环队列，请写出插入一个元素的算法。 struct CyclicQueue/循环队列定义 ElemType elem[M]; /M为已定义过的整型常量 int rear; /rear指向队尾元素的后一个元素位置 int length; /length指示队列中元素个数 } bool EnCQueue(CyclicQueue&.Q,ElemType x); /Q是一个循环队列，若队列不满，则将x插人并返回true;否则返回false。 /在下面写出该函数的函数体 79
得 分 评卷人 六、算法设计题(8分) 设 Q是一个由其队尾指针和队列长度标识的循环队列，请写出插人一个元素的算法。 struct CyclicQueue //循环队列定义 ElemType elem[M]; //M为已定义过的整型常量 int rear; // rear指向队尾元素的后一个元素位置 int length; // length指示队列中元素个数 }; bool EnCQueue(CyclicQueue&- Q, ElemType x); 刀Q是一个循环队列，若队列不满，则将 x插人并返回true;否则返回false. //在下面写出该函数的函数体
试卷代号：1010 中央广播电视大学2009一2010学年度第一学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2010年1月 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18分）】 1.C 2.C 3.B 4.B 5.C 6.A 7.C 8.A 9.D 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.子 2.top->link 3.深度 4.8 5.3 6.n-1 7.84 三、判断题（在每小题后面的括号内打对号“/”表示叙述正确或打叉号“X”表示叙述错误。每 小题2分，共14分) 1.对 2.错 3.对 4.对 5.对 6.错 7.错 四、运算题（每小题6分，共30分】 1.根结点：；左子树中的结点数：4；右子树中的结点数：2；/每空2分 2.双支结点数：2叶子结点数：3 /1每空3分 3.深度搜索序列：1,0,2,4,5,3 /3分 广度搜索序列：1,0,2,3,4,5 /13分 4.(0,2)2,(0,3)4,(1,4)5,(1,2)10 /全对6分，否则酌情给分 5.(0)482556324066 80
试卷代号:1010 中央广播电视大学2009-2010学年度第一学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2010年 1月 一、单项选择题(在括号内填写所选择的标号。每小题 2分.共 18分) 1. C 6. A 2. C 3. B 4. B 5. C 7. C 8. A 9. D 二、填空题 (在横线处填写合适的 内容。每小题 2分 .共 14分 ) 1.子 .top一>link .深度 4. 8 5. 3 6. n一 1 7. 84 三、判断题(在每小题后面的括号内打对号“丫”表示叙述正确或打叉号“X”表示叙述错误。每 小题 2分，共 14分) 1.对 2.错 3.对 4.对 5.对 6.错 7.错 四、运算题(每小题 6分，共 30分) 1.根结点:a;左子树中的结点数:4;右子树中的结点数:2; /每空 2分 2.双支结点数 :2叶子结点数 :3 刀每空 3分 3.深度搜索序列 广度搜索序列 :1，0,2，4，5，3 :1，0,2，3，4，5 //3分 刀3分 (0,2)2,(0,3)4,(1,4)5,(1,2)10 //全对 6分，否则酌情给分 (0) 48 25 56 32 40 66
(1)482566324056 /12分 (2)484066322556 /12分 (3)664056322548 .//2分 五、算法分析题（每小题8分，共16分） 1.pl=p2、p2=p2->link(或p2=pl->link) ·/每空4分 2.求出并返回数组A[n]中n个元素的最大值。 六、算法设计题(8分) 评分标准：根据编程完整程度酌情给分。 bool EnCQueue(CyclicQueue&.Q,ElemType x); { if(Q.length==M)return false; /2分 Q.elem[Q.rear]=x; /14分 Q.rear=(Q.rear+1)%M; /6分 Q.length++; /17分 return true; /18分 } 81
(1) 48 25 66 32 40 56 //2分 (2) 48 40 66 32 25 56 //2分 (3)66 40 56 32 25 48 //2分 五、算法分析题 (每小题 8分 ，共 16分) 1. pl=p2,p2=p2一>link(或 p2=p1一>link) ·//每空 4分 2.求出并返回数组 A[n」中n个元素的最大值。 六、算法设计题(8分 ) 评分标准:根据编程完整程度酌情给分 。 bool EnCQueue(CyclicQueueue- Q, ElemType x); if (Q. length==M) return false; Q. elem[Q. rear]=x; Q. rear= (Q. rear+1) %M; Q. length十+; return true; 刀2分 刀4分 //6分 刀7分 刀8分