中央电大本科数据结构本2011年1月试题

试卷代号:1252靡位号亡口中央广播电视大学2010…2011学年度第一学骂骂开放本释期末考试数据结构(本}试题2011年l丹四陌丁1曰 il一、单项选择黯{每小题2分，共30分}1.数据元素是数据的3基本单位，它()。A. 只能有一个数据项组成B. 至少有工个数据项主运成c. 可以是一个数据瑕也可以串若干个数据项结成D. 至少有一个数据模为指针类型2. 绒性表的j段序铺构中，()。A逻辑上梧邻的元素在物理位置上不…定相邻B.数据元素是不能随挠谛间的c.逻辑上招邻的元索在物理位置上也指邻a进行数据丑素的插入、删除效率较高3. 以下表中苟且随机宙间的是()。A.就向链表 B.翠i句链表c. 单向循环链表D.顺序表4.设顺序存锚的钱性表长度为h对于删除操作，设翻除位置是等概率的，则跟踪一个元素平均移动元素的次数为( )。A.(口十0/2B.n已2nD.n-…i13615.设top是一个链梢的樵顶指针，战中每个结点由一个数据壤data和指针域next组成，设蹄x接收楼顶元素，蹦出接操作为(。A.x=top一data;top=口top…next;B.top=top-next;x=top-data;C.x=top-next;top=top-data;D.top…next=top;x=top…data;6.以于说法正确的是()。A.~人列是启进先t/jB.拢的特点是后进后出C战的酣睡和捶入操作都只能在接顶进行在5人列的删除和捶入操作都只能在民头进行7.串岳数StrCmp(b，cd勺的值为()。A.1a0C.bcd~、D.-18.设有一个12阶的对辑:矩阵A.采用黑缩存储方式将其下三角部分以行ff为主ff存绪如一维数理b中〈姐阵A的第一个元萦为al，l，数组b的下你从1开始)，则短阵A中第4行的元素在数组b中的于标i→定有(。儿7iζ10B.口ζi15C.9ζi14D.6i99.已知一个阔的边数为m.!l!~该阔的所有票点的庶数之租为()。A.2mB.mC.2m+1。.m/210.以下说法不辑的是()。A.连通图G一定存在生成树日.连通圈G的生成树中一定包含G的所有]Ji点C.连通图G的生成制中不一定包含G的所有边D.i丰满即G的生成树可以烧不连适的136211.散到查我的原理是()。A.在待王安记录的关键字古董与该记录的存储位置之间建立确定的玲应关系B‘按待查记录的关键乎有序的旗序方式存储c.按关键字值的比较进行查找D.基于二分查找的方浩12.排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小敖置到已经排好序的子序列的适当位置，直到全部排好序为止，该排序算法是( )。儿直接插入排序B.快灌排ffc.自泡排序D.选择排序13.采用顺序藉拉法对长度为n的钱性表进行查找〈不采用表尾设监视哨的方法)，最坏的情况下要进行()7X元素间的比较。A.n+2B.nC.n-l。.n/214.如商若Mrw点a出发按广度优先搜索法进行遍弱，周可能得到的顶点序列为()。A.acebdfghB.aebcghdfC.aedfbcghQGG总D.且becdfgh图115.一操暗夫盘树总共有2三个结点，该樨共有()个叶铺点(终端结点〉。A.10B.13已11D. 121363i!得分!评每人l工、填空题{每小黯2分，共24分}1.通常数据的逻辑结椅但括、、、四种类翠。2.设有一个单向链袭，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环能衰，1'吁南语句3.设有一个单向循环链衰，头指针为head，链表牛结点的指针域为next，p摇向尾结点的直接前驱结点，若要蹦除黯结点，得到…个新的单向循环链茬，可执行操作4.在一个链队中，f和r分别为5人头和队昆指针，队结点的擂针域为next，则插入一个s所指结点的操作为口=805.锚环~列的队头指针为f，~人尾指针为r，当时表现5人列为空。6.串函数StrC在t(a，拟的功能走进行串7.一棵工叉树挂有单分支结点，有6个叶结点，剿该树总共有一一一个结点。8.按照二又树的递阻定义，对二叉树遍厉的常用算法有←一一……、…一-一一、王静。9.把数据存储到计算筑中，并具体体现数据之间的逻辑结构称为结构。10.如医2所示的工叉树，其É序遍店序列为→一一…二一一。图211.工叉树为工叉排序的充分必要条件是其任一结点的佳均大于其在孩子的假、小于其右孩子的菌。这种说法是的。〈自答正确或不正确〉12.根据搜索方法的不前，醋的壤菌种方法。1364三、综合噩{每小瓶10分，共30分i1.(1)巳知某工叉树的后序遍历序列娃debca，中序遍历序列是dbeac，试露出该二叉裙。(2)著上述工叉树的各个结点的学符分别代表不同的整数(主革中没有相等的)，并恰好使该树成为一棵工叉排ff树，试绘出a占、c，d，e的大小关系。(3)始出该树的前序遍历序壳。2.(1)设有一个整数序歹d{40，28.6.72.100，3，54}弦次取出路到中的絮，将造一模二叉排序树。(2)对上述工叉排序树，在等概率条件下，求成功查找的平均袭击找长度e3.(1)利用筛选过程担序列{42，凹，67，102，16.32，57，52}建成堆(小根堆)，画出相应的完全二叉捋〈不要求中提过程λ(2)草草市对上述撞琦店的完全工叉辑进行中序遍历得到的序列。四、程序填空黯{每空2卦，共16分}1.以下面数在a[OJ到延到一口中，用折半查找算法查找关键字等于k的记录，王军找成功句口返韶该记录的下挥，失散时运韶1，完成程序中的空格。、•.φkVMPpwJUdnsUCYF?·••+t'kl验,}NODE;intBinary_SearchCNOD在a口，intn.intk)intlow.mid.high;low=O;high=n-1;while((113652avdU-­hrd-mμμ-Kwwlhmkzh毛'4十雹Ga/飞kureturn日lseif((3)low=mid十1;else2.以下最数为链5人列的人队操作，x为要人队的结点的数据域的键，front、rear分割是链队列的5人头、队建指针。structnode、‘，，ElemTypedata;咱一…structnode赞next手structnode祷front，普rear;voidInQueue(ElemTypex)structnode传p;p=(structnode善)(p一data=x;p…next=NULL;rear=(3)1366试卷代号:1252中央广播电视大学2010-2011学年度第一学期开鼓本科期末考试数据结构〈本)试题答案及评分标准(供参考〉2011年1另一、单项选择题{每小题2芳，共30分}1.C2.C6.C7.D11.A12.A二、填空题{每黯2分，共24分}1.集合钱性树形2.p一next=head;3.p…next=head;4.r-一next=s5.r==f6.连接7.118.先序中Ff后9.物理〈存偌〉10.gdbeihfca11.错误12.深度优先广度优先3.D8.A13.B图状4.A9.A14.D5.A10.D15.D三、结合应用题{梅小摆在10分，共30分}1.(1)QvQ1367(2)d~b~e~a~c(3)abdec2.(1)(2)ASL=(1x1十2x2个3x3十4)/7=18/73.(1)初始梅 堆(2)102,52,42,82,16,67,32,57四、税序填空题{每空2分，共16分}1.(1)low~=high(2)mid(3)a[mid].key~七(4)high=mid-1(5)return-1;2. (l)malloc(sizeof(structnode))。)rear-next=p(3)p1368