试卷代号：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={,,,,,,,}； 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点】出发进行 深度优先搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 得分 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出发进行 深度优先搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列: 广度优先搜索序列: 画 二」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 void FindMaxMin(SegList&A,int&.Max); 在编写此函数时可以使用顺序表类中定义的如下两个公有函数： int Length(); /求表的长度； int getData(int k); //提取第k个元素的值，0≤k&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 void FindMaxMin(SegList&A，int& Max); 在编写此函数时可以使用顺序表类中定义的如下两个公有函数 : int Length(); //求表的长度; int getData(int k) ; //提取第 k个元素的值，0簇k&- A, int& Max) //向下写出函 数 体
得分 32.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (char data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右予女结点的指针域。根据 下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回1否则返 回0。算法中参数T1和T2分别指向这两棵二叉树的根结点。当两棵树的结 构完全相同并且对应结点的值也相同时才被认为相等。 int BTreeEqual(BinTreeNode T1,BinTreeNode T2); 75
}得州 {32.已知二叉树中的结点类型B1nTreeNode定义为: struct BinTreeNode{char data; BinTreeNode*left，* right;}; 其 中 data为结点值域 ，left和 right分别为指 向左 、右子女结点的指针域。根据 下面函数声明编写出判断两棵二叉树是否相等的算法，若相等则返回 1否则返 回 0。算法中参数 T1和T2分别指向这两棵二叉树的根结点。当两棵树的结 构完全相同并且对应结点的值也相同时才被认为相等。 int BTreeEqual(BiriTreeNode二T1，BinTreeNode*T2);
试卷代号：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.V 20. 21.√ 22.X 23.X 四、计算题（每小题6分，共30分） 24.先根：a,b,e,c,f,h,i,j,g /2分 后根：e,b,h,i,j,f,g,c,a /2分 按层：a,b,c,e,f,g,h,i,j /2分 76
试卷代号:1010 中央广播电视大学2008-2009学年度第一学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2009年 1月 一、单项选择题(在括号内填写所选择的标号。每小题 2分，共 18分) 1. 13 6.C 2. C 3. C 4. D 5. C 7. D 8.B 9. A 二、填空题(在横线处填写合适的内容。每小题 2分，共 14分) 10.值 11.不一定 12. 21 13. 21十 2 14. 48 三、判断题(在每小题后面括号 内打对号表示叙述正确或 打叉号表示叙述错误。每小题 2分. 共 14分 ) 17.丫 22.X 18.火 23.X 19.了 20.了 21_.了 四、计算题(每小题 6分，共 30分) 24.先根 :a,b,e,e,f,h9i,j,g 刀2分 后根 :e9b,h,i,j,f9g,c,a 刀2分 按层 :a,b,c,e,f,g,h,i,j //2分
25.评分标准：每个数值对得2分，全对给6分 结点： 25 74 68 层号： 2 3 4 26.{49,34,30,12,28,16} 27.深度搜索序列：1,2,4,5,3 /3分 广度搜索序列：1,2,3,4,5 /3分 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(SeqList&.A,int&.Max) Max=A.getData(0); /1分 for(int i=1;i>Max)Max=A.getData(i); /6分 } 32.请根据编程的完整程度的情给分 int BTreeEqual(BinTreeNode T1,BinTreeNode T2) /若两棵树均为空则返回1表示相等 if(T1==NULL &&T2==NULL)return l; /1分 //若一棵为空一棵不为空则返回0表示不等 77
25.评分标准:每个数值对得2分，全对给6分 结点: 层 号 : 26.{49，34，30，12，28，16} 27.深度搜索序列 :1,2,4,5,3 //3分 广度搜索序列:1,2,3,4,5 //3分 28.查找 23,68,20的搜索长度:1,2,3 刀每个数据占2分 五、计算分析题(每小题 6分，共 12分》 29. rear- >Iink,rear=p //每空3分 30.从 HL单链表 中顺序查找出值为 K的结点 ，若查找成功则返回该结点的地址，否则返 回空。 六、编写题 (每小题 6分.共 12分) 31.请根据编程的完整程度酌情给分。 #include" SeqLIst. b" template void FindMaxMin(SegList衣A, int& Max) { Max=A. getData(0); //1分 for(int i=1;iMax) Max=A. getData(i); //6分 32.请根据编程的完整程度酌情给分 int BTreeEqual(BinTreeNode二 T1, BinTreeNode * T2) /若两棵树均为空则返回 1表示相等 if(T1二二NULL && T2=二NULL) return 刀 1分 //若一棵 为空一棵不为空则返回 0表示不等
else if(T]==NULI T2==NULL)return 0; /12分 /若根结点值相等并且左、右子树对应相等则两棵树相等 else if(T1->data==T2->>data &.&BTreeEqual(T1->left,T2->left)8.&. BTreeEqual(TI->>right,T2->>right))return 1; /15分 /若根结点值不等或左、右子树对应不等则两棵树不等 else return 0; /6分 另一个参考答案： int BTreeEqual(BinTreeNode Tl,BinTreeNode T2) //若两棵树均为空或实际上是问一棵树时返回1表示相等 if(T]==T2)return 1; //1分 /若一棵为空一棵不为空则返回0表示不等 if(T1==NULL T2==NULL)return 0; 112分 //若根结点值不等返回0表示不等 if(Tl->data!=T2->data)return 0; /3分 //若根结点值相等则两棵树是否相等取决于它们的左、右子树是否对应相等 return BTreeEgual(Tl->left,T2->left)&&.BTreeEqual(T1->right,T2- >right); /6分 78
elseif(’1’1今=NIJI，1，}!‘1’2二=NUI矛1洲)relurno 刀2分 //若根结点值相等并 比左 、右子树对应相等则两棵树相等 。15、、if(‘1’1一》〔1:，1、，==’1’2一》〔1:，t:，吕.吕B‘1、reel二q。:，1(’1’1一>1。fl，‘1’2一>Ieft)尽.尽 B’1、r、、el二qual(1、1一二>rlg正It，’1、2一)right))retllrrll 刀5分 /若根结点值不等或左、右子树对应不等则两棵树不等 elsereturno 刀6分 另一个参考答案: in之B飞、rceE(子ual(Bin‘1’reeNode、 丁’1，Bin，l’reeNode* 了’2) //若两棵树均为空或实际上是同一棵树时返回1表示相等 if(TI= = 1’2)ret:lrtl 刀1分 //若一棵为空一棵不为空则返 回 。表示不等 if(，J、1==NUIJIJ{}1’2==NUI沙IJ)returno //2分 //若根结点值不等返回 。表示不等 if(‘1’1一>dala!=’1’2一)(lata)returno 刀 3分 //若根结点值相等则两棵树是否相等取决于它们的左 、右子树是否对应相等 re，urnBI’reeEqual(‘1’1一>left，’rZ一>left)乙aBTreeEqual(TI一>:ight，1’2一 >rigl飞t); 刀 6分 78