试卷代号：1010 座位号 中央广播电视大学2006一2007学年度第二学期“开放本科"期末考试 计算机专业数据结构 试题 2007年7月 题 号 三 四 五 六 总分 分 数 得 分 评卷人 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1,若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 A.指针 B.引用 C.传值 D.常值 2.在二维数组中，每个数组元素同时处于( )个向量中。 A.0 B.1 C.2 D.n 3.已知单链表A长度为m,单链表B长度为n,它们分别由表头指针所指向，若将B整体 连接到A的末尾，其时间复杂度应为()。 A.(O(1) B.O(m) C.O(n) D.O(m+n) 4.假定-个链式队列的队头和队尾指针分别为fron1和rcar,则判断队空的条件为 ( ) A.front =rear B.front！=NULL (.rear！=NULL D.front =NULL .若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。 A.3,2,1 B.2,1,3 .3,1,2 D.1,3,2 71
试卷代号:1010 座位号口习 中央广播电视大学2006-2007学年度第二学期“开放本科”期末考试 计算机专业 数据结构 试题 zoos年 7月 题 号 四 五 六 总 分 分 数 }藏百-}评卷人 a一 厂一 {l 一、单项选择题 ，在括号内填写所选择的标号(每小题 2分 ，共 18分) !_ .若需要利用形参直接访问实参，则应把形参变量说明为( )参数。 八 指针 B.引用 C;.传值 I:).常值 2.在二维数组中，每个数组元素同时处于( )个向量中。 }. } k3. 1 〔，.2 l, n 3.已知单链表 A长度为 m，单链表 f3长度为 n，它们分别由表头指针所指向，若将 I3整体 连接到 fl的末尾 ，其时间复杂度应为( )。 }5,.()(1) (、 ()(Tl (") ( n} ) O(m一+n) .i 假定一个链式队列的队头和队尾指针分别为front和 rear，则判断队空的条件为 ( 八.front= = rear B. front 1 = NUI_L rear } = NtJLI. D. front= = }1U1.I, 若让元素 1,2,3依次进栈，则出栈次序不可能出现( )种情况 }. 3，2，1 a;", ，1，2 2，1，3 1，3，2
6.在一棵高度为5（假定树根结点的高度为0）的完全二叉树中，所含结点个数至少等于 () A.16 B.64 C.31 D.32 7.向具有个结点的二叉搜索树中插人一个结点的时间复杂度大致为()。 A.O(1) B.O(logzn C.O(n) D.O(nlogen) 8.具有n个顶点的有向图最多可包含有( )条有向边。 A.n-1 B.n C.n(n-1)/2 D.n(n-1) 9.图的广度优先搜索类似于树的( )遍历。 A.先根 B.中根 C.后根 D.层次 得 分 评卷人 二、填空题，在横线处填写合适的内容（每小题2分，共14分） 1.链表只适用于 查找。 2.设双向循环链表中每个结点的结构为(data,llink,rlink),则结点p的前驱结点的地 址为 3.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有 个结点。 4.假定一棵树的广义表表示为a(b,c,d(e,f),g(h)),则结点f的层数为 假定 树根结点的层数为0。 5.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的 继续搜索。 6.每次从第i至第n个元素中顺序挑选出一个最小元素，把它交换到第i个位置，此种排 序方法叫做 排序。 7.快速排序在最坏情况下的时间复杂度为 72
在一棵高度为 5(假定树根结点的高度为 o>的完全二叉树中，所含结点个数至少等于 A. 16 B. 64 C. 31 D. 32 向具有 n个结点的二叉搜索树中插人一个结点的时间复杂度大致为( A. O< 1) B. O(log2 n) C. 0(n) D. O(nlog2n) 具有 n个顶点的有向图最多可包含有( )条有向边 。 A. n一 1 B. n C. n(n一1)/2 图的广度优先搜索类似于树的( D. n ( n一1) )遍历。 先 根 后 根 「中根 .层次 得 分 评卷人 二、填空题 ，在横线处填写合适的内容(每小题 2分 ，共 14分) 1.链表只适用于 查找 。 2.设双向循环链表中每个结点的结构为(data, llink, rlink)，则结点 *P的前驱结点的地 址为 3.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有_ 个结点。 4.假定一棵树的广义表表示为a(b,c,d(e,f),g(h))，则结点f的层数为__ 。假定 树根结点的层数为。。 5.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要 向根的 继续搜索 。 6.每次从第 i至第 n个元素中顺序挑选出一个最小元素，把它交换到第 i个位置，此种排 序方法叫做 排序。 7.快速排序在最坏情况下的时间复杂度为_ 。 72
得分 评卷人 三、判断题，在每小题前面打对号表示正确或打又号表示错误（每小 题2分，共14分) ( )1.数据的逻辑结构与数据元素本身的内容和形式无关。 )2.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 )3.在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历 和按层遍历时具有相同的结果。 )4.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上 相同。 )5.邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 )6.在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个 数有关，而且与每一个子表中的对象个数有关。 )7.向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高 度减少1。 得 分 评卷人 四、运算题（每小题6分，共30分） 1.假定一棵二叉树广义表表示为a(b(c(,g)),d(e,f)),分别写出对它进行先序、中序和 后序遍历的结果。 先序： 中序： 后序： 2.有7个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点生成一棵霜夫 曼树，求出该树的带权路径长度。 带权路径长度： 3.已知图G=(V,E),其中 V=(a,b,c,d,e}, E={,,,,,,} 在该图的邻接表表示中，每个顶点单链表各有多少个边结点。 顶点： a b d 边结点数： 73
得 分 评卷人 三、判断题 ，在每小题前面打对号表示正确或打叉号表示错误 (每小 题 2分，共 14分) )1 )2 数据的逻辑结构与数据元素本身的 内容和形式无关 。 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历 和按层遍历时具有相同的结果。 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上 相同。 邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个 数有关 ，而且 与每一个子表中的对象个数有关。 向一棵 B树插入关键码的过程中.若最终引起树根结点的分裂 ，则新树比原树的高 度减 少 1 得 分 评卷人 四、运算题(每小题 6分 ，共 30分 ) 1.假定一棵二叉树广义表表示为:}.b(c(,g)>,d， ，,c，b} ，} 在该图的邻接表表示中，娜个一顶点单链表各有 多少个边结点。 顶点: a b c d 边结点数 :
4,已知一个AOV网的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7} E={,,,,,,}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照然点序号从小到大灰 序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列 拓扑序列： 5.已知有一个数据表为{30,16,20,15,38,12,44,53,46,18,26,86？.六进行并 的过程中每一趟排序后的数据表变化。 (0)[301620153812445346182686] (1) (2) (3) (4) 得分 评卷人 五、算法分析题（每小题6分，共12分） 1.该算法功能为：从表头指针为的、按值从小到大排列的有序链表中别除所有值相同 的多余元素，并释放被删结点的动态存储空间。阅读算法，在划有横线的上填写合适的内 容。 void purge_linkst(ListNode *&la) ListNode *p,*q; if(la==NULL)return; q=la;p=la->link; while(p){ if(p->data>q->data)(q=p;p=p->liuk: else q->link= delete(p); p= 74
4，已知一个 AOV网的顶点集 V和边集 G分别为: V二{0，1，2，3，4，5，6，7}; E_ { ， ，} 1，4二、，，}; 2，}; ，二一，，link; }}hilc Cp){ ifq一>data)(q=-- p;E}二车)一)link;、 fijf'{ 9一>link= _ ; delete(p); 石)= ; }
2.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (ElemType data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。下面函数的功 能是从二叉树BT中查找值为X的结点，若查找成功则返回结点地址，否则返回空。阅读算 法，在划有横线的上面填写合适的内容。 BinTreeNode BTF(BinTreeNode BT,ElemType x) if(BT==NULL)NULL; else if(BT->data==x) else BinTreeNode *t; if(t=BTF(BT->>left,x))return t; if(t= return t; return NULL; 分 评卷人 六、算法设计题（每小题6分，共12分） 1.Q是一个由其队尾指针和队列长度标识的循环队列，请写出插人一个元素的算法。 struct CyclicQueue /循环队列定义 { ClemType elem[M];/M为已定义过的整型常量 int rear: /rear指向队尾元素的后一个位置 int length; /length指示队列中元素个数 了； bool EnCQueue(CyclicQueue&Q,ElemType x); /Q是一个循环队列，若队列不满，则将x插入并返回true;否则返回false。 /在下面写出该函数的函数体 75
2.已知二叉树中的结点类型 Bin'TreeNode定义为: struct Bin"hreeNode{ElerType data;BinTreeNode*lef t，* right;}; 其中data为结点值域，left和 right分别为指向左、右子女结点的指针域。下面函数的功 能是从二叉树 B't中查找值为 X的结点，若查找成功则返回结点地址，否则返回空。阅读算 法，在划有横线的上面填写合适的内容。 BinTreeNode * I3TF(BinTreeNode*BT，ElemType x) if(B'I'= =NULL) NULL; else{ ifdata==x) ; else{ Bin'hreeNode * t; if(t=BTF(BT一> left，x))return t; if(t= )return t returnNULL: t 六、算法设计题(每小题 f>分，共 I2分) 1. Q是 一个由其队尾指针和队列长度标识 的循环队列 ，请写出插人一个元素的算法 ‘〕 structGyclir_Queue / 循环队列定义 Llcn1'I'ype elcnt经}] ; //1}-I为已定义过的整型常量 tnt ri}ar; 刀 rear指向队尾元素的后一个位置 int length; // length指示队列中元素个数 boot 11;nC;Queue(CyclicQueue} Q，ElemType x); //Q是一个循环队列 ，若队列不满 ，则将 x插入并返 回 true;否则返回 faked //在下面写出该函数的函数体 75
2.已知二叉搜索树中的结点类型BinTreeNode定义为： struct BinTreeNode (ElemType data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数BST指向 一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向BST树中插入值为 item的结点，要求若树中不存在item结点则进行插人并返回1表示插人成功，若树中已存在 item结点则不插入并返回0表示插人失败。 int Insert(BinTreeNode *&BST,const ElemType&.item); 76
2.已知二叉搜索树中的结点类型BinTreeNode定义为: struct BinTreeNode{ElemType data;BinTreeNode*left，*right;}; 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。参数 BST指向 一棵二叉搜索树的根结点。试根据下面的函数声明编写一个递归算法，向 Bsr树中插人值为 item的结点，要求若树中不存在 item结点则进行插人并返回 I表示插人成功，若树中已存在 item结点则不插人并返回 。表示插人失败。 int Insert(BinTreeNode*乙BST，const ElemType乙item);
试卷代号：1010 中央广播电视大学2006一2007学年度第二学期“开放本科”期末考试 计算机专业 数据结构试题答案及评分标准 (供参考) 2007年7月 一、单项选择题，在括号内填写所选择的标号（每小题2分，共18分） 1.B 2.C 3.B 4.D 5.C 6.D 7.B 8.D 9.D 二、填空题，在横线处填写合适内容（每小题2分，共14分）】 1.顺序 2.p->llink 3.1 4.2 5.右子树 6.直接选择 7.0(n2) 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题2分，共14分） 1.对 2.对 3.对 4.错 5.错 6.对 7.错 四、运算题（每小题6分，共30分） 1.先序：a,b,c,g,d,e,f /12分 中序：c,g,b,a,e,d,f /2分 后序：g,c,b,e,f,d,a /12分 2.带权路径长度：131 3.评分标准：每个数据对给1分，全对给6分。 顶点： a b e 边结点数：1 2 1 2 4.评分标准：若与答案完全相同得6分，若仍为一种拓扑序列则得3分，其他则酌情处 理。 拓扑序列：1,3,6,0,2,5,4,7 5.分步给分 (0)[301620153812445346182686] (1)[1630][1520][1238][4453][1846][2686] /1分 (2)[15162030][12384453][18264686] /11分 (3)[1215162030384453][18264686] /12分 (4)[121516182026303844465386] /2分 77
试卷代号:1010 中央广播电视大学2006-2007学年度第二学期“开放本科”期末考试 计算机专业 数据结构 试题答案及评分标准 (供参考) 200 年 7月 一、单项选择题，在括号内填写所选择的标号(每小题 z分，共 is分) 1. B 6. D 2. C 7. B 3. B 8. D 4. D 9. D 5. C 二、填空题，在横线处填写合适内容(每小题 2分，共 14分) 1.顺序 5.右子树 2. p一>llink 6.直接选择 3. 1 7. 0(n2) 4. 2 三、判断题 ，在每小题前面打对号表示正确或打叉号表示错误 (每小题 2分，共 14分 ) 1.对 2.对 3.对 4.错 5.错 6.对 7.错 四、运算题 (每小题 6分 .共 30分) 1.先序:a,b,c,g,d,e,f //2分 中序:c,g,b,a,e,d,f //2分 后序:g,c,b,e,f,d,a //2分 2.带权路径长度 :131 3.评分标准:每个数据对给 1分，全对给 6分。 顶点: a b c d e 边结点数: 1 1 2 1 2 4.评分标准:若与答案完全相同得 6分，若仍为一种拓扑序列则得 3分，其他则酌情处 理 。 拓扑序列:1,3,6,0,2,5,4,7 5.分步给分 (0)[30 16 20 15 38 12 44 53 46 18 26 86] (1)[16 30][15 20][12 38][44 53][18 46][26 86] //1分 (2)[15 16 20 30][12 38 44 53][18 26 46 86] //1分 (3)〔12 15 16 20 30 38 44 53][18 26 46 86] //2分 (4) [12 15 16 18 20 ?6 30 38 44 46 53 86] //2分
五、算法分析题（每小题6分，共12分） 1.p->link、q->link /每空3分 2.return BT,BTF(BT->right,x) /1每空3分 六、算法设计题（每小题6分，共12分） 评分标准：根据编程完整程度酌情给分。 1.bool EnCQueue(CyclicQueue&.Q,ElemType x); { if(Q.length==M)return false; //1分 Q.elem[Q.rear]=x; /12分 Q.rear=(Q.rear+1)%M; /14分 Q.length+十； /15分 return true; /16分 } 2.int Insert(BinTreeNode *BST,const ElemType&.item) if(BST==NULL)( BinTreeNode p=new BinTreeNode; p->data=item; p->left=p->right=NULL; BST=P; return l; } //3分 else if(item==BST->data)return 0; /4分 else if(item>data) return Insert(BST->>left,item); /5分 else return Insert(BST->right,item); /6分 } 说明：函数体中的三个else保留字均可以被省略。 78
五、算法分析题(每小题 6分，共 12分) l, p->link,q->link //每空 3分 2, return BT,BTF(BT->right, x) //每空3分 六、算法设计题(每小题 6分，共 12分) 评分标准:根据编程完整程度酌情给分。 l. boot EnCQueue(CyclicQueue乙Q, ElemType x); { if ( Q. length==M) return false; //i分 Q. elem[Q. rear〕二x; //2分 Q. rear=(Q. rear-f-1) %M; //4分 Qlength+斗一; 刀5分 return true; //6分 } 2. int Insert(BinTreeNode*乙BST, const ElemType乙item) 砚 if(BS'I =NULL){ BinTreeNode }- p-new BinTreeNode; p一>data= item; P一>left=}}一>right二NULL; BST=p; return 1; } else if(item==BST一>data) return 0 else if(item data) return Insert(BST一>left，item); else 刀3分 刀4分 刀5分 return Insert(BST一>right，item); } 说明 :函数体中的三个 else保 留字均可以被省略。 刀6分 78