试卷代号：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