




文档简介
试卷代号:1252座位号CD 中央广播电视大学2013-2014学年度第一学期“开放本科“期末考试 数据结构本)试题 2014年1月 题号|一|二|三|四|总分| |分数IIIIII |得分|评卷人 11一、单项选择题每小题2分,共30分 1.在数据结构和算法中,与所使用的计算机有关的是()。 A.数据元数间的抽象关系且数据的存储结构 C.算法的时间复杂度D.数据的逻辑结构 2.对顺序表,以下叙述中正确的是 A.用一组地址连续的存储单元依次存放线性表的数据元素 B.各个数据元素的首地址是连续的 C数据元素不能随机访问 D.插入操作不需要移动元素 3.设有一个长度为25的顺序表,要删 除第10个元素(下标从1开始),需移动元素的个 、数为()。 A.9 C. 15 B.10 D.16 4.设单向链表中,指针p指向结点A,若要删除A的直接后继,则所需修改指针的操作为 ()。 A.p一next=p-next一next; c.p=p一next-next; B.p=p一next; D.p一next=p; 1091 5.元素1,3,5 ,7按顺序依次进钱,按该校的可能输出序列依次人队列,该队列的可能输 出序列是().(进找出钱可以交替进行 A.7,5,3.1 C.7,5,1.3 B.7,3,1 ,5 D.5,1.3,7 6.对一个战顶指针为top的链钱进行进校操作,设P为待进榜的结点,则执行()。 A.p=top一next;top=topnext;B.p-next=top; C.p一next=top;top=p;D.top=p; 7.设有一个18阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组B中(数组下标从1开始).则数组中第33号元素对应于矩阵中的元素是()。 (矩阵中的第1个元素是al.l) A.a1.6 C.a9.2 B.alO.S D.as.s 8.设有一个17阶的对称矩阵A.采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组B中数组下标从1开始).则矩阵中元素alO.6在一维数组B中的下标是()。 矩阵中的第1个元素是al.l) A.45.B.18 C.51D.53 9.串函数StrCmp(“ABCd“,“ABCD勺 的值为()。 A.OB.一1 C.1D.3 10.一棵采用链式存储的二叉树中有n个指针域为空4该二叉树共有()个结点。 A.n十1 C.n-l B.n D.n一2 11.设一棵哈夫曼树共有n个非叶结点,则该树有()个结点。 A.2n C.2n-1 B.2n+2 D.2n+l 12.一棵结点数31next=p一next;(p一next)一prior=q;然后再用语句q一prior=p; 和语句 20.在一个单向链表中,要删除p所指结点的直接后继结点.则可以用操作 (用一条语句 21.向一个钱顶指针为top的链战中插入一个p所指结点时,可执行 操作。(填两条语句,结点的指针域为next) 22.在一个带头结点的链队中,设front和rear分别为 队头和 队尾指针,则删除一个结点 的操作为p=front一next;=p一next;(结点的指针域为 next,p为辅助用指针 23.设有n阶对称矩阵A,用一维数组s压缩存储A的下三角元素,S的下标从零开始,最 后一个元素的下标为27,则n=(矩阵中的第1个元素是al,l) 24.一棵3度的树,其中3度结1个,2度结2个,1度结2个,则该树共有个叶 结点. 25.一棵有7个叶结点的二叉树,其1度结点数的个数为2,则该树共有个 结点 26.如图2所示的二叉树,其中序遍历序列为 图2 1094 27.二叉排序树或者是一棵空树,或者是一棵具有下列性质的二叉排z若它的左子树非 空,则左子树的所有结点的值都小于它的根结点的值$若它的右子树非空,Jt右子的所有结点 的值都大于(若允许结点有相同的值,则大于等于它的根结点的值。这种说法是-“的。 回答正确或不正确 |得分|评卷人| III 三、综合题每小题10分,共30分 28.(1)以3,4,5,8,9,10作为叶结点的权,构造一棵哈夫曼树。 (2)给出相应权重值叶结点的哈夫曼编码。 (3)一棵晗夫曼树有2n-1个结点,它是共有多少个权童值构造而成的?简述理由? 29.(1)简述拓扑排序的步骤。 (2)说明有向图的拓扑序列不一定是唯一的原因. (3)如何利用拓扑排序算法判定图是否存在回路。 (4)设有向图G如下,写出首先删除顶点1的3种拓扑序列。 图3 30.设有序表为(21,22 ,23 ,24 ,25 ,26,27 ,28,29 ,30,31,32),元素的下标从O 开始。 (1)说出有哪几个元素需要经过4次元素间的比较才能成功查到。 (2)画出对上述有序表进行折半查找所对应的判定树(树结点用数值表示 (3)设查找元素为5,需要进行多少次元素间 的比较才能确定不能查到。 (4)求在等概率条件下,成功查找的平均比较次数? 1095 |得分|评卷人! III 四、程序填空题每空2分,共16分 31.以下程序是快速排序的算法 设待序的记录序列存放在astart,aendJ中,按记录的关键宇进行快速排序,先进行 一次划分,再分别进行递归调用 void quicksort ( NODEa,intstart,intend) 5 J , 且 且 n A NODEmid; if(start= end ) return; i=start; j=end; mid=ai; whileOmid.key) ifOdata=x; p-next=NULL; rear= 1097 试卷代号:1252 中央广播电视大学2013-2014学年度第一学期“开放本科“期末考试 数据结构本试题答案及评分标准 (供参考) 2014年1月 一、单项选择题每小题2分,共30分 1.B2.A3.C 6. C7. D8. C l1.D12.A13.A 二、填空题每题2分,共24分 16.逻辑 17.元素间的比较O(n) 18.25 19.p一next=q; 20.p一next=p一next一next; 21.p一next=top;top=p; 22.front一next 23.7 24.5 25.15 26.512389746 27.不正确 三、综合应用题每小题10分,共30分 28.(1) 4.A 9.C 14. B 5.A 10. C 15. A 图4 1098 (2)30000 40001 5001 1001 810 911 (3)n个,因为非叶结点数比叶结点数少一个,而权值个数z叶结点数 29.(1)循环执行以下两步 选择一个度为O的顶点并输出 从网中删除此结点及所有出边 (2)因为选择一个度为O的顶点时不一定是唯一的 (3)由顶点活动网构造拓扑序列的过程中,输出结点后,余下的结点均有前驱 (4)152364152634156234 30.(1)5 (2) 罔5 (3)3 (4)ASL=(l+2铸2+3铃4+5铸的112=37/12 四、程序填空题每空2分,共16分 31.(1)i十+; (2)i十 十p (3)aCi=ai; (4)j一-; (5)(a,i+1,end) ; 32.(l)malloc(sizeof(structnode (2)rear一next=p (3)p 1099 试卷代号:125 2座位号CD 国家开放大学(中央广播电视大学)2014年春季学期“开放本科“期末考试 数据结构(本)试题 2014年7月 |题号|一|二|三|四|总分| |分数IIIIII |得分|评卷人 11-、单项选择题每小题2分,共30分) 1.结构中的元素之间存在一对多的关系是()。 A.集合B.线性结构 C树形结构D.图状结构 2.对不带头结点的单向链表,判断是否为空的条件是()(设头指针为head)。 A. head= =NULL C.head一next=head B.head一next=NULL D. head =NULL 3.在一个不带头结点的单循环链表中,p、q分别指向表中第一个结点和尾结点,现要删 除第一个结点,可用的语句是()。 A.p=q一next;p=p-next; c.p一next=q- next;q=p; B.p一next=q;p=p一next; D.p=p一next;q-next=p; 4.一个校的进技序列是1,2 ,3 ,4,5,则钱的不可能输出序列是()(进找出战可以交替 进行)。 A.12345 C.45321 B.43512 D.54321 5.-个队列的人队序列是2,4, 6,8,按该队列的输出序列使各元素依次入钱,该枝的可能 输出序列是()。 A.8,6 ,4 ,2 C.8,4 ,2 ,6 B.6,2 ,4 ,8 D.8,2 ,4 ,6 1033 6.在一个链队中,假设f和r分别为队头和队尾指针,已生成一个结点p,要为结点p赋 值x,并入队的运算为()。 A.p一data=x;p一next=NULL;f-next=p;f=p; B.p一data=x;p一next=NULL;r一next=p;r=p; C.p一data=x;p一next=r;r=s; D.p一data=x;p一next=f;f=s; 7.设有一个25阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组B中(数组下标从1开始),则矩阵中元素.a7.6在一维数组B中的下标是()。 (矩阵中的第1个元素是旬.1) A.34B.14 C.260.27 8.以下程序段的结果是c的值为()。 chara5= “1236789“,int铃p=a,intc=O; while(祷p+)c十 +; A.8_B.7 C.100.12 9.一棵有23个结点,采用链式存储的二叉树中,共有()个指针域为空。 A.24B.25 C.23D.45 10.在一棵二叉树中,若编号为i的结点是其双亲结点的左孩子,则双亲结点的顺序编号 为()。 A.i/2B.2i-1 C.2i+1D.i/2-1 11.设一棵哈夫曼树共有2n十1个叶结点,则该树有()个叶结点。 A. n一l C.n+l B.n 0.2n 12.已知如图1所示的一个图,若从顶点a出发,按深度优先搜索法进行遍历,则可能得 到的一种顶点序列为()。 图1 1034 A. abecdf C. aebcfd B.aefebd D. aedbfc 13.已知如图2所示的一个图,若从顶点B出发,按广度优先法进行遍历,则 可能得到 的 一种顶点序列为()。 0-毛 图2 A.BADEHCFG B.ADEHCGF e.BADECHFG D.BADEHCFG 14.一组记录的关键宇序列为(46,38 ,56 ,40,79,84),利用快速排序,以第一个关键字为 分割元素,经过一次划分后结果为()。 A.40,38 ,46,79 ,56 ,84 B.40,38,46,5679,84 C.40,38 ,46,84 ,56 ,79 D.38,40 ,46 ,56 ,79 ,84 15.在有序表21,23 ,28 ,33 ,43,屿,46,73,77,78,的,99,106中,用折半查找值43时,经 ()次比较后查找成功。 A.6 e.8 |得分|评卷人| III B.3 D.4 二、填空题(每小题2分,共24分) 16.本书中介绍的树形结构和属非线性结构。 17.设有一个长度为18的顺序表,要在第4个元素之前插入2个元素(也就是插入元素 作为新表的第5个和第4个元素).则最少要移动元素的个数为 1035 18.在双向链 表中,要删除p所 指的结点,可以先用语句句一prior)一next= p一next;然再用语句 19.在一个单向链表中p所指结点之后插人一个s所指向的结点时,应执行s一next= p-next;和的操作。 20.一个钱和一个队列的输入序列都为abcdefg,它们可能有相同 的输出序列 吗? 。(若没有则回答没有,若有则写出序列,进找出钱可以交替进行) 21.从一个钱顶指针为top的链战中取钱顶元素,用d保存楼顶元素的值,可执行 。(结点的数据域为data) 22.循环链队列中,设front和rear分别 为 队头和 队尾指针,(最多元素为MaxSize,),判 断循环链队列为空的条件是为真。 23.对稀疏矩阵进行压缩存储,可采用三元组表,设a是稀疏矩阵A相应的三元组表类型 (结构体类型)变量,a中的一个成员项是三元组类型的结构体数组data,按书中定义,若 a.dataO.i=2;a.data0.j=3;a.dataOJ.v=16;它提供的A数组的相关信息有 24.设有一棵深度 为5的完全二叉树,该树共有20个结点,第 五层上有 点。(根所在结点为第1层) 25.中序遍历树可得到个有序序列。 26.如图1所示的二叉树,其后序遍历序列为 图1 27.给定-组权重值,构造哈夫曼树,哈夫曼树的高度一定是唯一的,这种说法是 的。(回答正确或不正确) 1036 个叶结 |得分|评卷人| III 三、综合题(每小题10分,共30分) 28.(1)说明什么是顶点活动网(AOV网)和拓扑序列 (2)设有向图G如下,写出3种拓扑序列, (3)在图G中增加一条边,使图G仅有一条拓扑序列 图3 29.如下是一棵二叉排序树,AI,A2,A9代表1,2,3,9中各个不同数字, (1)给出对该树中序遍历的结果 (2)A3,A5 ,A7的值各为多少? (3)请在该树中再插入一个结点9.5作为叶结点,并使它仍然是一棵二叉排序树 A7 图4 30.(1)设有查找表17,26,14,16,15,30,18,19,28,依次取表中数据构造一棵二叉排序树。 (2)对上述二叉树给出后序遍历的结果 (3)对上述二叉树给出中后序遍历的结果 (4)在上述二叉树中查找元素15共要进行多少次元素的比较? 1037 |得分|评卷人| III 四、程序填空题每空2分,共16分) 31.以下函数是二叉排序树的查找算法,若二叉树为空,则返回根结点的指针,否则,返回 值是指向树结点的结构指针p(查找成功p指向查到的树结点,不成功p指向为NULL)完成 程序中的空格 typedefstructBnode intkey; structBnode蒋left; structBnode祷right; Bnode; Bnode头BSearch(Bnode祷bt,intk) /提bt用于接收二叉排序树的根结点的指针,k用以接收要查找的关键字诀 / Bnode秘p; if(bt= return(bt); p=bt; while(p一key! if(kkey) else 1038 if(p=NULL)break; return(); 32.设有一个头指针为head的不带头结点单向链表,p 、q是指向链表中结点类型的指针 变量,p指向链表中结点a,(设链表中没有结点的数据域与结点a的数据域相同),写出相关 语句 (1)使该单向链表成为单向循环链表 (2)插入结点S,使它成为a结点的直接前驱 q=p;x=p-data; while ( q一next=head; q=p;p=p-next; while(p一data!=x) q=p; s一next=p; )q=q一next; 1039 试卷代号:1252 国家开放大学(中央广播电视大学)2014年春季学期“开放本科“期末考试 数据结构(本)试题答案及评分标准 (供参考) 2014年7月 -、单项选择题(每小题2分,共30分 1.C2.A3.D 6. B7. D8. B 11.C12.D13.C 4. B 9. A 14.B 5. A 10.A 15.B 二、填空题(每题2分,共2 4分 16.图状结构 17.15 18.(p一next)一prior=p一prior; 19.p-next=s; 20.abcdefg 21.d=top-data; 22.front=rear 23.A的第一个非零元素的下标为2,3,元素为16 24.5 25.二叉排序 26.519876432 27.不正确 三、综合应用题每小题10分,共30分) 28.(1)用顶点表示活动,边表示活动间先后关系的有向图称为顶点活动网 在顶点活动网中,若不存在回路,则所有活动可排列成个线性序列,使每个活动的所有 前驱活动都排在该活动的前面,称此序列为拓扑序列 (2)abdc adbcdabc (3)在b和d间添加有向边 29.(1)A7 A4 A8 A2 AS A9 Al A3 A6 123456789 1040 (2)8 5 1 (3) 图5 30.(1)见图6 (2)15,16,14,19,18,28,30,26,17 (3)14,15,16,17,18,19,26,28,30 (4) 4 图6 四、程序填空题每空2分,共16分 31.(1)NULL (2)k (3)p=p一left (4)p=p一right (5)p 32.(1)q一next!=NULL (2)p=p一next; (3)q一next=s; 1041 试卷代号:1252座位号E口 国家开放大学(中央广播电视大学)2014年秋季学期“开放本科“期末考试 数据结构(本)试题 2015年1月 E 三 一、单项选择题(每小题2分,共30分) 1.一种逻辑结构在存储时()。 A.只要存储数据元素间的关系 c.可采用不同的存储结构 2.对链表,以下叙述中正确的是( A.不能随机访问任一结点 B.结点占用的存储空间是连续的 c.插入删除元素的操作一定要移动结点 B.只能采用一种存储结构 D.只要存储数据元素的值 D.可以通过下标对链表进行直接访问 3.线性表在存储后,如果相关操作是:要求已知第i个结点的位置访问该结点的前驱结 点,则采用()存储方式是不可行的。 A.单链表B.双链表 c.单循环链表D.顺序表 4.校和队列的共同特点是()。 A.都是先进后出B.元素都可以随机进出 D.都是先进先出c.只容许在端点处插入和删除元素 1028 5.元素2,4,6,8按顺序依次进枝,按该拢的可能输出序列依次入队列,该队列的可能输 出序列是()(进找出校可以交替进行)。 A.8,6,2,4 C. 6,2,4,8 B.8,4,2,6 D. 8,6,4,2 6.在一个不带头结点的链队中,假设f和r分别为队头和队尾指针,则从该对列中删除一 个结点并把结点的值保存在变量x中的运算为)。 A.x=rdata;r=rnext; B.r=rnext; x=rdata C. x=fdata;=fnext; D. f=fnext; x=fdata 7.设有一个20阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储 到一维数组B中(数组下标从1开始),则数组中第38号元素对应于矩阵中的元素是()。 (矩阵中的第1个元素是旬,1) A. alO,g B. a7,6 C. a9,2 D. ag,5 8.在C语言中,分别存储“S“和s,各需要占用()字节。 A.一个和两个B.两个 c.一个D.两个和一个 9.一棵有n个结点,采用链式存储的二叉树中,共有)个指针域被有效使用(即指针 域为非空)。 A. n+1 C. n-1 B.n D.口一2 10.在一棵二叉树中,若编号为i的结点存在双亲结点,则双亲结点的顺序编号为)。 A. i/2. 0 C. 2i十1 B. i/2向下取整 D.i十2 11.设一棵哈夫曼树共有2n十1个结点,则该树有()个非叶结点。 A.n c.n一1 B. n十1 D.2n 12.一棵完全二叉树共有4层,且第4层上有2个结点,该树共有( (根为第一层)。 A.5 C.3 B.4 D.9 )个非叶子结点 1029 13.如图1所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则可能得到的 一种顶点序列为()。 A. abedfc c. aebcdf i到1 B. acfebd D. aebcfd 14.一组记录的关键字序列为(56,30,89,66,48,50,94,87,100),利用快速排序,以第一 个关键字为分割元素,经过一次划分后结果为()。 A.30,50,48,56,66,89,94,100,87 B. 50,30,48,56,66,89,94,87,100 C.48,30,50,56,66,89,94,87,100 D.50,30,48,66,56,89,94,87,100 15.线性表以()方式存储,能进行折半查找。 A.关键字有序的链接B.顺序 C.关键字有序的顺序D.数组 二、填空题(每小题2分,共24分 16.数据的逻辑结构在计算机中的表示称为结构。 17.求两个n阶矩阵的乘积,算法的基本操作为,时间复杂度为 18.设有一个长度为25的顺序表,第8号元素到第25号元素依次存放的值为8,9,10, 11,25,某人想要在第8个元素前插入1个元素7(也就是插入元素作为新表的第8个元 素),他的做法是从第8号元素开始,直到第25号元素依次向后移动1个位置,然后把7存放 在8号位置,其结果是新表中第25号元素的值为 1030 19.在双向链表中,要在p所指结点后插入q所指的结点(设q所指的结点己赋值),其中 所用的一条语句句一next)一prior=q;功能是使P所指结点的 指向q0 20.设有一个带头结点的,头指针为head的单向链表,p指向表中某一个结点,且有p next=为=NULL,现要删除头结点,并使该单向链表构造成单向循环链表,通过操作head= head一next; 21.从一个战顶指针为top的链找中删除一个结点时,用d保存被删结点的值,可执行 。(结点的指针域为next,数据域为data) 22.循环链队列中,设front和rear分别为队头和队尾指针,(最多元素为MaxSize,采用 少用一个元素的模式),判断循环链队列为满的条件为 23.对稀疏矩阵进行压缩存储,可采用三元组表,一个6行7列的稀疏矩阵A相应的三元 组表共有8个元素,则矩阵A共有个零元素。 24.一棵有8个权垂值构造的哈夫曼树,共有一-一一个结点。 25.一棵有18个结点的二叉树,其2度结点数的个数为8,则该树共有个1度结 占。 26.如图2所示的二叉树,其先序遍历序列为 l剖2 27.在查找表中,通过记录的某关键字能唯一地确定一个记录,该关键宇称为 1031 三、综合题每小题10分,共30分) 28. (1)对给定权值3,1,4,4,5,6,构造深度为5的哈夫曼树。(设根为第1层) (2)求树的带权路径长度。 ( 3)链接存储上述哈夫曼树,结点中共有多少个指针域为空,说明理由。 29. (1)如下的一棵树,给出先序遍历序列 (2)把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树 提示:设图中的树是二叉排序树,找出中序遍历序列与1,2.9的对应关系 (3)请在该树中再插入一个结点3.5作为叶结点,并使它仍然是一棵二叉排序树。 民13 30.设查找表为(5,6,7,8,9,10,11,12,13,14) (1)画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点) (2)给出二叉排序树的定义,针对七述折半查找所对应的判定树的构造过程,说明判定树 是否是二叉排序树(设树中没有相同结点)? (3)为了查找元素5.5,经过多少次元素间的比
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 新工科背景下智能纺织品设计课程建设探索
- 2025至2030年中国球型铰链行业投资前景及策略咨询报告
- 2025至2030年中国淋浴水龙头行业投资前景及策略咨询报告
- 2025至2030年中国洗瓶机旋转喷冲装置行业投资前景及策略咨询报告
- 高中地理学科整合的背景与跨学科教育的必要性
- 冷轧硅钢生产线项目可行性研究报告(范文模板)
- 山东省青岛市黄岛区2020-2021学年高二上学期期末生物试题(解析版)
- 关于成立冷轧硅钢公司可行性研究报告(范文参考)
- 中小学美术教学评价与学科核心素养的关系分析
- 男方父亲婚礼致辞范文15篇
- 思辨与创新智慧树知到期末考试答案章节答案2024年复旦大学
- 手术室-标准侧卧位摆放
- 线性代数智慧树知到期末考试答案章节答案2024年广西师范大学
- 中药药理学(中国药科大学)智慧树知到期末考试答案2024年
- 夫妻卖房一方不能到场委托书
- MOOC 算法设计与分析-武汉理工大学 中国大学慕课答案
- (正式版)JBT 9229-2024 剪叉式升降工作平台
- 江苏大学机械工程学院人才培养调查问卷(校友卷)
- 义务教育均衡发展督导评估汇报
- 全球商用制冷冷冻设备行业调研分析报告2024年
- 肺癌患者的健康宣教课件
评论
0/150
提交评论