试卷代号：1010 座位号■ 中央广播电视大学2008一2009学年度第一学期“开放本科”期末考试 数据结构 试题 2009年1月 题 检 三 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 得分 1. 下面算法的时间复杂度为( )。 int f(unsigned int n) ( if (n==0 n==1)return 1; else return n f(n-1); A.0(1) B.O(n) C.0(n2) D.O(n!) 得分 2.在一个长度为的线性表中顺序查找一个值为x的元素时，在等概率的情况下， 查找成功时的平均查找长度为( A.n B.n/2 C.(n+1)/2 D.(n-1)/2 得分 3.已知L为一个单链表的表头指针，在表头插入结点p的操作是( )。 A.p=L;p->link=L; B.p->link=L;p=L; C.p->link=L;L=p; D.L=p;p->link=L; 得分 4.若有一个循环队列Q,队首和队尾指针分别为front的rear,则判断队列满的条件 为()。 A.Q.front==Q.rear; B.Q.front-Q.rear==MaxSize; C.Q.front+Q.rear==MaxSize; D.Q.front==(Q.rear+1)%MaxSize; 得分 5. 在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为()， 假定树根结点的编号为0。 A.2i B.2i-1 C.2i+1 D.2i+2 70
得分 6. 对长度为10的线性有序表A[10]进行折半查找，若查找到元素A[2]时成功，则 查找长度为( )。 A.1 B.2 C.3 D.4 得分 7. 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整过 程共具有( )种旋转类型。 A.1 B.2 C.3 D.4 得分 8.i 设一个有向图具有n个顶点和e条边，若采用邻接表作为其存储结构，则空间复 杂度为( )。 A.O(nXlogze) B.O(n+e) C.O(n') D.O(n2) 得分 9.在一棵m阶B树中，树根结点所包含的关键码个数至少为()。 A.1 B.2 C.m/2 D.m-1 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分】 得分州 10. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对 应一个非零元素的行号、列号和 得分州 11. 在单链表中逻辑上相邻的结点而在物理位置上 相邻。 得分 12.在一棵高度为2的四叉树中，最多含有 个结点，假定树根结点的高度 为0 得分 13. 在一个堆的顺序存储中，若一个元素的下标为（≥0），则它的右子女元素的下 标为 得分州 14. 根据一组记录(56,42,73,50,48,22)依次插入结点生成一棵AVL树时，当插入 到值为 的结点时首次出现不平衡，需要进行旋转调整。 得分 15. 当利用Kruskal算法求解-一个连通网的最小生成树时，只有当一条候选边的两 个端点不在同一个 分量时，才会被加入到最小生成树中。 得分 16. 在堆排序中，对n个记录建立初始堆需要调用 次筛运算的算 法。 7
得分 评卷人 三、判断题（在每小题后面括号内打对号表示叙述正确或打叉号表示 叙述错误。每小题2分，共14分) 得分 17. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。() 得分 18. 在用单链表表示的链式队列Q中，假定队头指针为Q一>front,队尾指针为 Q一>rear,则链队为空的条件为Q->front-==Q->rear。 () 得分 19. 一棵AVL树的所有叶结点不一定在同一层上。 () 得分 20. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，若对它分别进行中序 遍历和后序遍历，则具有相同的遍历结果。 () 得分 21.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。（ ) 得分 22.对一个用顶点表示活动的网络(AOV网)进行拓扑排序的结果是唯一的。 ) 得分 23.堆排序是一种稳定的排序方法。 得·分 评卷人 四、计算题（每小题6分，共30分】 得分 24.假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g),分别写出对其进行先 根、后根和按层遍历的结果。 先根： 后根： 按层： 得分 25.假定一个线性表为(38,52,25,74,68,16,30)，根据此表中的元素排列次序生成 一棵二又搜索树，求出该二叉搜索树中元素为25、74、68结点的层号。假定树根 结点的层号为1。 结点： 25 74 68 层号： 72
得分 26.已知一个数据集合为{28,12,16,49,34,30}，试把它调整为一个最大堆。 最大堆： 得分 27.已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5}: E={,,,,,,,}； 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点1出发进行 深度优先搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 得分 28.设散列表的长度m=7;散列函数为H(K)=K mod m,若采用线性探查法解决 冲突，待依次插入的关键码序列为{19,14,23,68,20}，分别求出查找23、68、20 时的搜索长度。 查找23、68、20的搜索长度： 得 分 评卷人 五、计算分析题（每小题6分，共12分）】 得分 29.设rear是以循环链表表示的队列的队尾指针，EnLQueue函数实现把x插人到 队尾的操作。阅读算法，在划有横线的上面填写合适的内容。 void EnLQueue(ListNode *rear,ElemType x) ListNode p; p=new ListNode; /p指向动态分配的结点空间 p->data=x; p->link= rear->link=p; }； 73
得分 30.假定HL为一个单链表的表头指针，K为一个待查找的值，请指出算法功能。 ListNode Unknown(ListNode HL,int K) if(HL==NULL)return NULL; if(HL->data==K)return HL; ListNode￥cp; cp=HL一>link; while(cp!=NULL) if(cp->data==K)return cp; else cp=cp->link; return NULL; 算法功能： 得分 评卷人 六、编写题（每小题6分，共12分） 得分 31. 试编写一个函数，在一个顺序表A中顺序查找出元素的最大值，由引用参数 Max带回。函数的原型如下： #include“SeqList.h” template void FindMaxMin(SeqList&A,int&.Max); 在编写此函数时可以使用顺序表类中定义的如下两个公有函数： int Length(); //求表的长度： int getData(int k); //提取第k个元素的值，0≤k&A,int&Max)/向下写出函 数体 74
得分 32.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (char data;BinTreeNode left,right;; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据 下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返 回0。算法中参数T1和T2分别指向这两棵二叉树的根结点。当两棵树的结 构完全相同并且对应结点的值也相同时才被认为相等。 int BTreeEqual(BinTreeNode T1,BinTreeNode T2); 75
试卷代号：1010 中央广播电视大学2008一2009学年度第一学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2009年1月 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18分） 1.B 2.C 3.C 4.D 5.C 6.C 7.D 8.B 9.A 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 10.值 11.不一定 12.21 13.2i+2 14.48 15.连通 16.n/2 三、判断题（在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分， 共14分)】 17./ 18.X 19.√ 20.√ 21.√ 22.X 23.X 四、计算题（每小题6分，共30分） 24.先根：a,b,e,c,f,h,i,j,g /12分 后根：e,b,h,i,j,f,g,c,a /12分 按层：a,b,c,e,f,g,h,i,j /2分 76
25.评分标准：每个数值对得2分，全对给6分 结点： 25 74 68 层号： 2 3 26.{49,34,30,12,28,16} 27.深度搜索序列：1,2,4,5,3 /3分 广度搜索序列：1,2,3,4,5 113分 28.查找23、68、20的搜索长度：1、2、3 //每个数据占2分 五、计算分析题（每小题6分，共12分） 29.rear->link,rear=p /每空3分 30.从HL单链表中顺序查找出值为K的结点，若查找成功则返回该结点的地址，否则返 回空。 六、编写题（每小题6分，共12分）】 31.请根据编程的完整程度酌情给分。 #include“SeqList..h” template void FindMaxMin(SeqListMax)Max=A.getData(i); /6分 32.请根据编程的完整程度酌情给分 int BTreeEqual(BinTreeNode T1,BinTreeNode T2) /若两棵树均为空则返回1表示相等 if(T1==NULL &&T2==NULL)return 1; //1分 /若一棵为空一棵不为空则返回0表示不等 77
else if(T1==NULL T2==NULL)return 0; /2分 /若根结点值相等并且左、右子树对应相等则两棵树相等 else if(T1->data==T2->data &&BTreeEqual(Tl->left,T2->left)&&. BTreeEqual(T1->right,T2->right))return 1; /5分 /若根结点值不等或左、右子树对应不等则两棵树不等 else return 0; /6分 } 另一个参考答案： int BTreeEqual(BinTreeNode T1,BinTreeNode T2) { /若两棵树均为空或实际上是同一棵树时返回1表示相等 if(T1==T2)return 1; /11分 /若一棵为空一棵不为空则返回0表示不等 if(T1==NULL T2==NULL)return 0; /2分 /若根结点值不等返回0表示不等 if(T1->data!=T2->data)return 0; /3分 //若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等 return BTreeEqual(T1->left,T2->left)&&.BTreeEqual(T1->right,T2- >right); } /16分 78