试卷代号：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>,<b,a>,<c,b>,<c,d>,<d,e>,<e,a>,<e,c>} 在该图的邻接表表示中，每个顶点单链表各有多少个边结点。 顶点： a b d 边结点数： 73
得 分 评卷人 三、判断题 ，在每小题前面打对号表示正确或打叉号表示错误 (每小 题 2分，共 14分) )1 )2 数据的逻辑结构与数据元素本身的 内容和形式无关 。 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 在一棵二叉树中，假定每个结点只有左子女，没有右子女，则对它分别进行前序遍历 和按层遍历时具有相同的结果。 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上 相同。 邻接表表示只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个 数有关 ，而且 与每一个子表中的对象个数有关。 向一棵 B树插入关键码的过程中.若最终引起树根结点的分裂 ，则新树比原树的高 度减 少 1 得 分 评卷人 四、运算题(每小题 6分 ，共 30分 ) 1.假定一棵二叉树广义表表示为:}.b(c(,g)>,d<e,f))，分别写出对它进行先序、中序和 后)}}遍历的结果。 先序 : 中序: 后序 : 2.有 7个带权结点 ，其权值分别为 3,7,8,2,6,10,14，试以它们为叶子结点生成一棵霍夫 赞树，求出该树的带权路径长度。 带汉路径长度: 3.已知图 G-(V,L),其中 V二{a，b，。，(},e}， E={<a，b>，<b，a> ，,c，b} ，<c, d} 。<d, e} ，Ge，a,=，<'} e，(、〕>} 在该图的邻接表表示中，娜个一顶点单链表各有 多少个边结点。 顶点: a b c d 边结点数 :
4,已知一个AOV网的顶点集V和边集G分别为： V={0,1,2,3,4,5,6,7} E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6,<2,1,7, <5,7>,<6,7>}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照然点序号从小到大灰 序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的拓扑序列 拓扑序列： 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_ {< 0，2> ，< 1，3> ，} 1，4二、，<2，4>，}; 2，}; ，< 3，E'>二一，< :}，7- <5，7>，<6，7} }; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照竺点序 巴F,{.小到大山 认- 序链接的，则按主教材中介绍的进行拓扑排序的算法，写出得到的有i}卜序列 拓扑序列 : J.已知有一个数据表为{30，IG，2。，15，38，1之，‘}土，汤3，16，18·之。、，86，。少行出ii-行;i:} j1;。 }} 的过程 中每一趟排序后的数据表变化 。 (0) [30 16 20 15 38 12 .I<I }3 4f I8 26 8G二 t1) <2) (3) (4) 得 分 评卷人 五、算法分析题(每小题 fi分，共 7. 2分) 1 该算法功能为:从表头指针为 la的、按值从小到大排列的有序链表中删除所有伯相侧 的多余元素，并释放被删结点的动态存储空间。阅读算法，在划有棋线的 f . [}i城写合适的内 容 。 }}oid purge_linkst<Listi\'ode 之 1，) { ListNode *P，‘q; if (la= =NULIJ retu，一:1; q = la;p=1a一>link; }}hilc Cp){ if<p一)data>q一>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{ if<BT一>data==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