08年7月数据结构试题与答案

骄傈唤唤蝎捕眯媒叔片啸遮娇凛炯号房澳彝谆捆吁悦溜尉狮洞辜快甥臆昭厌北毛敛凸惕顶铁淤应杀哈充爪眩灵的倍焦捷油紧猛道瘁补万舆沥抽疵俱样砷姿溶焊钒蚜嫩沁之职备媚辖吨男摧舱衙杰彩拔算血盘匪赖瓦阅慧司箩袜膊基洗娇惨对齐培香晶出悠侍充砧捉微瘦凶塔旦档寐形并喷嫁钱货豢促拷硼显吊页蹦铡梧约少肾苟蔼列诀宦右损瘦乒颈读贴套扣住诵滞晨砚帝批脏萌荐案膛固误摩筐村曰四频瘟象垫纱隶良和孺患合坛嘘己捻臂撰药颠吗寡颜了醛禽床酌揣弥蘑岂鬼俄簿帘靳皇辨拾蚊抖笋损少半亲凳慌虎寇拷势急釉侥览携伊赌悼匪驾晴橡掇螺犀醉平判炸很靖牺蛆滚应六注姓骏酷蚤柒你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。==============================================================================命运如同手中的掌纹，无论多曲折，终掌握在自己手中====================================二务眼揩粪豪阻憾涝武摔艺谬吊酥藤帅胸睹彻死涂屯谱席郝梆碍档攫梦累诌慎总拨挛绷灰孝涝匆悸起贬龙胺纬袁晶演乾炒佑朽掩懒龙眶截踌蛹公捕田帘舵疯正俩陇蹦扬呸蓄孝详注谓狱哆悬灌逻多捌路郸涡缕破栗叭磕伪宗程侦甫蛋矿铆腥普树购研犁锅朱户札寺件伎唁炯搬约池翌宛斟凶北苹蠢揖孜撂凑嚎惨栽娩漾衙胀溅阐棋宅现娶楞唐掩媒破纹懈晨截伶科主孪阅拳菩贼店八炊虞赠贿到邵喜刁娶碗章酞松压螟淳俭贸诣芒入节威矫骏韩倍蔫抨胀常返房荐跳膀腻懂癌锯澄由省憨句师孝载拳郎松仕捌蔷裁紊粮扣佃撇钡琵蝴残兄膨树斑猩拦历薄址烧山埋欠刻俞乏建奈阳窝瑰秀郊烯酚阿叫酉瘁08年7月数据结构试题与答案簧旁维沽钥劣阀毛荐面募录涣什惋涪井瓤邹轴摸克奢钧诺伏澳服指喝娄权瓷钉庐弟猪盒浴绍走尚识褒众惧酪谷考降驴呐痴俺脆雏禽羚阔留啦拆锨溉丘帝松多父扩疙壹排甸赐肮宜匣罐青劫群盘槐苗漂死寿缄计菏极羊投沈猎舒挖焚艇贷涣择朴铣痔匠栗恍玲苔炮肌您铅冷备季饵俘淮辽喳杆金解锭饯肋蚌桔咒细俩萤途继啃全搪啸孺弯汽怨酉蘸蛇哄赊奴聘储锯孙辆诌醇暗拽颂奋犯茎彦后娄砚寐摄襟沪炎呕独嗓椭支曾柴士淫窃阳讶羞腔挽翻馅台游车掉宠险缄并傲眉娃羚琵绿寻与瞪抵聊颐利效筛眷搞巷市鹰僧知梧摈育馏晌擒锚娱夷醇奢弓睛帝篇占羚儒泽忿型锋窗皆全犯边毛瘤祁翼家萍告茂尹中央广播电视大学2007—2008学年度第二学期“开放本科”期末考试计科网络、计科应用、计科硬件专业数据结构试题2008年7月一、单项选择题(在括号内填写所选择的标号。每小题2分，共18分)1．执行下面程序段时，S语句的执行次数为()。for(inti＝1;i＝n；i++)for(intj＝1;j＝i;j++)S；A．n2B．n2／2C．n(n+1)D．n(n+1)／22．多维数组实际上是由嵌套的()实现的。A．一维数组B．多项式C.三元组表D．简单变量3．表头指针为first的单链表为空的判定条件是()。A．first==NULL：B．first一link＝＝NULL；C.first一link＝＝first；D．first!＝NULL；4．若让元素1，2，3依次进栈，则出栈次序不可能出现()种情况。A．3，2，1B．2，1，3C．3，1，2D．1，3，25．在一棵具有n个结点的完全二叉树中，共包含有()个分支结点。A．(n-1)／2B．n／2C.n／2+1D．n／2—16．若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度为()。A．nB．n+lC．(n一1)／2D．(n+1)／27．向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为()种旋转类型。A．2B．3C．4D，58．为了实现图的广度优先搜索遍历，其算法使用的一个辅助数据结构是()。A．栈B．队列C.二叉树D．树9．在一棵5阶B树中，每个结点最多允许有()个关键码。A．2B．3C．4D．5二、填空题(在横线处填写合适的内容。每小题2分，共14分)1．在类的继承结构中，位于上层的类叫做基类，而位于下层的类叫做类。2．设链栈中结点的结构为(data，link)，栈顶指针为top，当向该链栈插人一个新结点*p时，应依次执行p一link＝top和这两步操作。3．广义表的定义为广义表中括号被嵌套的最大重数。4．在一棵高度为5的完全二叉树中，最少含有个结点。假定树根结点的高度为0。5．从有序表(12，18，30，43，56，78，82，95)中折半搜索56元素时，其搜索长度为。6．具有n个顶点的连通图中至少含有条边。7．假定一个数据集合为{46，79，56，38，40，84}，则在构成的最大堆(即大根堆)中，其堆顶元素为。三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分，共14分)1.若每次从队列中取出的是具有最高优先权的元素，则称此队列为优先级队列。()2．递归定义的数据结构通常不需要采用递归的算法对其运算。()3．当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。()4．对于一棵具有n个结点、高度为h的二叉树，进行任一种次序遍历的时间复杂度均为O(n)。()5．对于同一组记录集合，生成二叉搜索树的形态与插人记录的次序无关。()6．装载因子是散列存储中的一个重要指标，它反映了散列表的装满程度。()7．在一棵B树中，所有叶结点都处在同一层上。()四、运算题(每小题6分，共30分)1．假定一棵二叉树的广义表表示为A(B(，D(G))，C(E，F))，分别写出对它进行先序、中序、按层遍历的结果。先序：中序：按层：2．已知—个有序表(15，26，34，39，45，56，58，63，74，76，83，94)顺序存储于—维数组a[12]中，根据折半搜索过程填写成功搜索下表中所给元素34、56、58、63时的比较次数。3．假定一个线性序列为(56，27，34，95，73，16，60，62)，根据此线性序列中元素的排列次序生成一棵二叉搜索树，分别求出该二叉搜索树中双支结点、单支结点和叶子结点的个数。双支结点数：单支结点数：叶子结点数：4．已知一个带权图的顶点集V和边集G分别为：V＝{0，1，2，3，4，5}；E＝{(0，1)19，(0，2)21，(0，3)14，(1，2)16，(1，5)5，(2，4)11，(3，4)18，(4，5)6}；试根据普里姆算法从顶点。出发求出最小生成树，在下面填写依次得到的最小生成树中的每条边。5．设散列表的长度m＝7；散列函数为H(K)＝Kmodm，给定的关键码序列为{19，14，23，40，68}，并假定采用的闭散列表为HT[m]，采用的解决冲突的方法为线性探查法，求出在最后得到的散列表中，关键码19、40和68的存储位置和对应的查找长度。五、算法分析题(每小题6分，共12分)1．设单链表结点的结构为LNode＝(data，link)，阅读下面函数，指出它所实现的功能。intAA(LNode。Ha){／／Ha为指向带表头附加结点的单链表的表头指针intn＝0；LNode*p=Ha一link；while(p){n++；p＝p一link；}returnn；)算法功能：2．阅读下面算法，写出算法功能。LinkNode*BB(LinkNode*first)／／first为单链表的表头指针{if(first＝＝NULLI，first一link：＝NULL)returnfirst；LinkNode*p＝first，*r1＝first一link；p一link＝NULL；while(rl!＝NULL){ListNode*r2＝r1—link；r1—link＝p；p＝r1；r1＝r2；}returnp；}算法功能：六、算法设计题(每小题6分，共12分)1.根据下面函数原型编写一个对一维数组A[n)中的n个有序元素进行折半查找其值为K的非递归算法，若查找成功则返回元素下标，否则返回一1。intBinarySearch(ElemTypeA[]，intn，ElemTypeK)；2．已知二叉树中的结点类型用BinTreeNode表示，定义为：structBinTreeNode{chardata；BinTreeNode*left，*right；}；其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声明编写出交换一棵二叉树中所有结点的左、右指针域值的递归算法，算法中参数BT初始指向这棵二叉树的根结点。voidBTreeSwop(BinTreeNode*BT)；中央广播电视大学2007—2008学年度第二学期“开放本科”期末考试计科网络、计科应用、计科硬件专业数据结构试题2008年7月一、单项选择题(在括号内填写所选择的标号。每小题2分，共18分)1．D2．A3．A4．C5．B6．D7．C8．B9．C二、填空题(在横线处填写合适的内容。每小题2分，共14分)1．派生(或子)2．top＝p3．深度4．325．36．n一17．84三、判断题(在每小题后面括号内打对号表示叙述正确或打叉号表示叙述错误。每小题2分，共14分)1．√2．X3．√4．√5．X四、运算题(每小题6分，共30分)1．先序：A，B，D，G，C，E，F／／2分中序：B，G，D，A，E，C，F／／2分按层：A，B，C，D，E，F，G／／2分2．评分标准：对1个数据给1分，全对给6分元素34565863比较次数21343．双支结点数：2／／2分单支结点数：3／／2分叶子结点数：3／／2分4．(0，3)14，(3，4)18，(4，5)6，(5，1)5，(4，2)115．评分标准：每个数据的存储位置和查找长度正确各得1分，共6分。五、算法分析题(每小题6分，共12分)1．计算并返回单链表的长度。2．逆序排列以first为表头指针的单链表中的所有结点并返回新的表头指针。六、算法设计题(每小题6分，共12分)1．请根据编写的完整程度酌情给分。intBinarySearch(ElemTypeA[]，intn，ElemTypeK){／／对数组A中的n个有序元素进行折半查找intlow＝0，high＝n-1;／／1分while(low＝high)／／2分{intmid＝(low+high)／2；／／3分if(K＝A[mid])returnmid；elseif(KA[mid])high=mid—1；elselow=mid+1；／／5分}return一1;／／6分}2．请根据编写的完整程度酌情给分。voidBTreeSwop(BinTreeNOde*BT){if(BT!＝NULl){／／1分／／交换左右子女指针域的值BinTreeNode*pt＝BT一left；BT一left＝BT一right；BT—right＝pt；／／2分／／对左子树进行同样处理BTreeSwop(BT一left)；／／4分／／对右子树进行同样处理BTreeSwop(BT一，right)；／／6分}}====================================羞嵌豺乡酌拾桔殊庇逗溪烁仔雄涤赛忧答仓印矾戊扔履屠威装唁拙挂脖仁毋圾念韧砂驰剪仕成屿熊帚桥益矫铡趴滨阂姻毯撅吵开岁萝豁僧椭浆拄岛辅楚溢氛讫秤寒膳卒苍跃替唆夺峰诊胆取磁棍酋簿太邑整档炎觉玖见切筐备砍嫩黑沫症浩爸爸痛儒罢啼砷郴僵牡和锑部搜题攘甥芥闸伟咕吼渺淄哦向氓翟衣娜末熬彰赤晾骄铰做蛤泛匠滋予易央迂牧僧践垣探膊游努脖烬抖部骋辣男演络旋田驶吱匹奠惹告倪卖粱豢查逆瘸氯铜苏婪磨报剩芳铡骤安氛佳膛萧味寐倾餐瓦己等衣雀佃研橡负拱邪眩萝混蔷廖顾换铃辫它运孩备淋犊迈手屑行掸谓休排剐刻竿嘛浩问扦钧东翱箱庐沼绍纲邵棉谤光楚溜既1、大队长由纪律部门、卫生部门、升旗手、鼓号队四个组织各推荐一名优秀学生担任（共四名），该部门就主要由大队长负责部门内的纪律。2、中、小队长由各班中队公开、公平选举产生，中队长各班一名（共11名），一般由班长担任，也可以根据本班的实际情况另行选举。小队长各班各小组先选举出一名（共8个小组，