试卷代号：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.O(1) B.O(n) C.O(n2) D.O(n!) 得分 2.在一个长度为的线性表中顺序查找一个值为×的元素时，在等概率的情况下， 查找成功时的平均查找长度为()。 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
试卷代号:1010 座位号口口 中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试 数据结构 试题 2009年 1月 题 号 四 五 六 总 分 分 数 得 分 评卷人 一、单项选择题 (在括号内填写所选择的标号。每小题 2分。共 18 分) F% 3二」1·下面算法的时间复杂度为( int f (unsigned int n) if (n= 二0 else return !! n=“1) return 1; n‘f(n一1); } A. O(1) C. 0(n2) B. O(n) D. O(n!) 0州 】2.在一个长度为 n的线性表中顺序查找一个值为 x的元素时，在等概率的情况下 ， 查找成功时的平均查找长度为( )。 A. n C. (n+ 1)/2 B. n/2 D. (n一i)/2 Fpf -}二]3·已知L为一个单链表的表头指针，在表头插人结点‘p的操作是( p一>link=L; P=L B. D. A. p=L; p一>link=L; L=p; L=p; 卜导州 14. C. p一>link=L; 若有一个循环队列Q，队首和队尾指针分别为 front p一>link=L; 的 rear，则判断队列满的条件 f I}州 卜 为( )。 A. Q. front=“Q. rear; B. Q. front一Q. rear==MaxSize; C. Q. front+Q. rear==MaxSize; D. Q. front二=(Q. rear+1)%MaxSize; 在一棵完全二叉树中，若编号为 i的结点存在左子女，则左子女结点的编号为( )， 假定树根结点的编号为 。。 A. 2i B. 2i一 1 C. 2i+ 1 . D. 21+ 2
得分 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.设一个有向图具有n个顶点和€条边，若采用邻接表作为其存储结构，则空间复 杂度为( ) 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 在一个堆的顺序存储中，若一个元素的下标为i(≥0)，则它的右子女元素的下 标为 得分州 14.根据一组记录(56,42,73,50,48,22)依次插人结点生成一棵AVL树时，当插入 到值为 的结点时首次出现不平衡，需要进行旋转调整。 得分 15. 当利用Kruskal算法求解-一个连通网的最小生成树时，只有当一条候选边的两 个端点不在同一个 分量时，才会被加入到最小生成树中。 得分 16. 在堆排序中，对n个记录建立初始堆需要调用 次筛运算的算 法。 71
k4州 卜 }得州 卜 0" I 18. 对长度为 10的线性有序表 A[1叼进行折半查找，若查找到元素 A[2〕时成功，则 查找长度为( )。 A. 1 B. 2 C. 3 D. 4 向一棵 AVL树插人元素时 ，可能引起对最小不平衡子树 的调整过程 ，此调整过 程共具有( )种旋转类型。 A. 1 B. 2 C. 3 D. 4 设一个有向图具有 n个顶点和e条边，若采用邻接表作为其存储结构，则空间复 杂度为( )。 A. O(nX loge) B. O (n十e) C. O (n`) D. O (n2) 区 习9.在一棵m阶”树中，树根结点所包含的关键码个数至少为( A. 1 C. m/2 2 m 一 1 且 D. 得 分 评卷人 二、填空题(在横线处填写合适的内容。每小题 2分，共 14分) 卜州 }10. 11 12 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对 应一个非零元素的行号、列号和 在单链表中逻辑上相邻的结点而在物理位置上 相邻。 在一棵高度为2的四叉树中，最多含有_ 个结点，假定树根结点的高度 为 0。 13.在一个堆的顺序存储中，若一个元素的下标为 i(i>0)，则它的右子女元素 的下 标为 14.根据一组记录(56,42,73,50,48,22)依次插人结点生成一棵 AVL树时，当插入 到值为_ 的结点时首次出现不平衡，需要进行旋转调整。 15.当利用 Kruskal算法求解一个连通网的最小生成树时，只有当一条候选边的两 个端点不在同一个_ 分量时，才会被加人到最小生成树中。 16.在堆排序中，对n个记录建立初始堆需要调用 _次筛运算的算 法 。 71 画画 画 画 画 哑
得 分 评卷人 三、判断题（在每小题后面括号内打对号表示叙述正确或打叉号表示 叙述错误。每小题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
得 分 评卷人 三、判断题(在每小题后面括号内打对号表示叙述正确或打又号表示 叙述错误。每小题 2分 .共 14分 ! 17。线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。 ( ) 18。在用单链表表示的链式队列 Q中，假定队头指针为 Q - > front，队尾指针为 Q->rcar，则链队为空的条件为 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结点的层号。假定树根 结点的层号为 to 结点 : 层 号 :
得分 26.已知一个数据集合为{28,12,16,49,34,30}，试把它调整为一个最大堆。 最大堆： 得分27.已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5}; E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>,<5,3 >}； 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点】出发进行 深度优先搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 得分 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
14"1 1 26.已知一个数据集合为{28,12,16,49,34,30 ，试把它调整为一个最大堆。 最大堆 : 画 二口27.已知一个图的顶点集V和边集r删为: V二{1，2，3,4，5}; E= {< 1，2> ，< 1，3> ，<2，4> ，< 2，5> ，< 3，4> ，< 4，5> ，< 5，1> ，< 5，3 > }; 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点 1出发进行 深度优先搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列: 广度优先搜索序列: 画 二」28.设散列表的长度m=7;散列函数为H(K)一Kmodm，若采用线性探查法解决 冲突，待依次插人的关键码序列为{19,14,23,68,20}，分别求出查找 23,68,20 时的搜索长度 。 查找 23,68,20的搜索长度 : 得 分 评卷人 五 、计算分析题 (每小题 6分，共 12分) 巨到二」29.设~是以循环链表表示的队列的队尾指针，EnLQueue函数实现把x插人到 队尾的操作。阅读算法，在划有横线的上面填写合适的内容。 void EnLQueue(ListNode*&. rear, ElernType x) ListNode*p; p=new ListNode; p一> data =x; p一> link二 rear一>link= p; }}P指向动态分配的结点空间
得分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 <class T> void FindMaxMin(SegList<int>&A,int&.Max); 在编写此函数时可以使用顺序表类中定义的如下两个公有函数： int Length(); /求表的长度； int getData(int k); //提取第k个元素的值，0≤k<A.Length()。 void FindMaxMin(SeqList<int>&A,int&Max)/向下写出函 数体 74
随州 }30.假定 H1.为一个单链表的表头指针，K为一个待查找的值，请指出算法功能。 ListNode * Unknown (List Node * HL, int K) if(HL=二NULL) return NULL; if(HL一>data二=K) return HL; List Node *cp; cp= HL一>link; while(cp!=NULL) if(cp一>data==K) return cp; else cp=cp一>link; return NULL; 算法功能 得 分 评卷人 六、编写题(每小题 6分，共 12分) PiT州 }31.试编写一个函数，在一个顺序表 A中顺序查找出元素的最大值，由引用参数 Max带回。函数的原型如下: #include "SegList. h" template <class T> void FindMaxMin(SegList<int>&A，int& Max); 在编写此函数时可以使用顺序表类中定义的如下两个公有函数 : int Length(); //求表的长度; int getData(int k) ; //提取第 k个元素的值，0簇k<A. Length(). void FindMaxMin(SegList<int>&- A, int& Max) //向下写出函 数 体