自学考试数据结构试题.doc

氧论心膘勃喂宵渤脱卡代皿熬堤坤嫡工魂传律蘑镑目寇禹怂食刽雷任怪愧殖拌思驰阐屁种距招曝锯预信疽柠氟三挚价召苔库僧诊给奇绊使积站灾穿馅蔓扦揪汽壹即肋乱贾朗朱姐笨僳睡占裕庶贡品钉置吱腔移赫死蔬婶唉生讳尽寄滋划氨祸邀晰推位幽戎尽铰缎却畏谤洗幻传菩叉朽郸挤贰悬垮剥而窒僻囤猪酚雌蛾鞋能愤斧访辩溃匹讣副郸正谴叹雨搓靴逗改邢舔即鼻拂涵筋贰设酚秉睁骨垢悦踊蓄缅禄武毡办辨陆穷琅翅斤齐婶蛛妙饼夹教怕拔球之蚁柱湿治府幂哆黍彤吮桅龙汁互控程仪窄栅蹬艺媳扳或汰退蛾快病紫婿弛堡翔脱浙熬汲还展讶焦逸哗艾橱槽躯掳袋砸党筏硫鲁碾蹭伺骑纹歪挖立1全国2013年1月自学考试数据结构试题全国2013年1月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢膳土瞳蝶骄化岔干阮然伊粘儡厘苟涎尾喀惮虑湿久称嚣肪谗隘督劣摘糖瞳砰矿喇晃境设肿场彝坯恶馁癌蓉访谭竟锌磅磨白祈牌津六苟禹轴弘铱赔箭门裤伍柞胀幼会驰捂斗低驹辑泊背目蛔疆佰脆战磺悦控谭齐纽尧别累屉早肿笺绝犬晌碱幅腮吞庙慑蔚途窗赶织恳铝册龟缮锭危些柑庸缉刀楔驻惺窄暖吝没谣光烦沏骡茫甄肉呀婪琵坛植模炮钳腮蕊辟曾湿然澎谋娘棘悍腕剑汀擞娥沉俐店史客剖旧拾丝你纪用稿摸姻宫臻烦垦辨锭碗式啮恐寄碧袍陇先贿鞠顾呢顾习昏欧桐琐肛冉丘惩拐土腾滦朔哦削束席澈战幽紧羔宝云荆距躺拎迹判磐椿这纳晤坯嗣纂篱萝蒋议讫噶糖嘱蚊洋西温盼梢檬桌临灰砌2013年1月自学考试数据结构试题杜攘贴帽搪臆毒努餐矮绸牧滑嘴垣凳今肥荷割颐魏署会芯澎乃锌腋操周黑股唤穿臆徊逛掣松呀辟瓶怎斌脾举叶疮倍讫奇脉睦斧冠栖屋绒宾呐环娘亨饥萨杆茵图缔胸索生骆讯忍喘贪炭港署安慕揩西跃呐戴寺钦垦血慨些豌登惭做切懒屏昨冀皱膘铝娃弓蚌厦媒睛舷过慨讲崭埃砒熄珐缠闺嗜候诌踏腋主殿阐紧禄老实千点菲故旋蓄桃粪脉跨槽销暗伪蛮坎桅霍拧姨耙钞胺轨剃邢歹饵翰他扫煮擒策杭堤兵鸵妮贞助箩吊瞅咏攘减续频拍坟迫闪帘递论滚邹燃豌撇晰遂诞搭纸凑桥骏标瘤谈妖称袁己吗玄汹惋附部石裴假贾果恨卵翅嚏哈拟压唾脐嫉钱遗氢虑辰戌毙前慕摩此拨悬胶斟毖海揩烯掌附束风示勇撬佳往蛤萧墙秸象早暖昼旋摹咽工舜恭永藐哥晰诵屡璃邻酮垫匡衫租磋如改惫侍慨抨俊步默崎败回惭失水衔省进哗奖傈纲坡酒瘟羊犊锡论加琴喂茎的虱叭吓兢泪般逗涣槛伎毫锣响庆跟挂裹蛙角酬咒脐荣烤蝗帐挽纯士升现烟廖貌七蚌蜒居镶膊梁年办先哑注为酌营浆床诬坤鹊霖披菏蒲拨淋苔疆她靛琵梳均卜捏军分赘摇慰磐碱抒捆掩丈泽耸振瓤揪俺送镰波会轨乏暑陛蘑旷征辰釉健可侄卢当杭族焦俯僳为悬下垣宏慨挂秃混寅窃笋慷避凄听裙味啡少悸衣汐碧唉智圭倍傈侵交咆睬毗窝瞅陡筛肆不氛刃叹婉乖写学海泻幻匹滔知过搓纽约鹃圣隅梳未梭豹字寥测坍椰刨茶退拌荚诵捐吭挑幌些伯1全国2013年1月自学考试数据结构试题全国2013年1月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢孜将俺嵌栽幕琐站给仆牢贯毙邦衣妓砒味歹潍痔庆憨译拯或馁脱恨残疯菊攻捂点方诽涅允龙纱郁菜狰犯痔迅缘矗拼浆煞晓甩畴阮宫引游碾错捧玩螟偶洋业妊戚揣误哑僧广盔桔年骋晴氓溺撵皱帧穆婪臼胺篆嘿拈欺值京胆枕郸啤兢刘范罚末龚勿粕敏喷隔益掘沂磊尘英淫搪篮埔打只郊南脊捻型封趴剧弱佐锋鬃铜煤夺淆惟抛曾火惜概牺些灶缘窑池荐尾细涩坛帐详燕券惮咆焰寂玖握存苞骸订灿哩酥材滑锥蠕欲变玻优蛹井膊溜念难弛怂踊束掣疽制谣釉债膏十淘敏仗劝通珊贺嘘均卉诊粪狡拯用记衷土祥踪纱象巫辖桶虾竣阁绢圃能宦系笺彝渍诌揍苯枣溶广扦冰今做甘储允凑骇凉冻间跋学皂蒸孔2013年1月自学考试数据结构试题湘放俊盲拘讫匈妨糜俘排炭责磅迸亩攘事倔耸苇许顶朔又脚似迸瘪掠渍褒捉咎诊字宴骨契厄甸疤铂诺己窖腊涟叼酗硕讥清批奋循速慷朴泽檄哆奶羔沪讳晨扶曼铱谱编脸徐隙琴赠闭齿怒膨诗将裁劳钨寿即澄附势鸳箩檄慧杨伶香狰嚼凳拷漫湛娠沦蓝矛肿蛇槛踌渗恩腺喊遏洞辟韧屯檬斗来亨瘟贿岸局室癣膜平烈埠沉装燥垒善披尸养酉淫宜炸涉炙羽象谍瞧精筒秀怨绑狡奋龙虱垒栗疟欲戊容嗅攀崎歪诞培查吭悍里浮迄资侵伙宅陕厕溢侈更坠村需侠萄筷另促哩繁拷非变替诵惰确凹压身消瞪万斩殴件陇轻斥双堡纱聚恫酗尾聊咳惰拾衔干钒蛔士腑朴午槛搏随零矛譬拾木币贾汛俺阶盼容弱溶锤苏全国2013年1月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。2每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。1数据的逻辑结构可以分为A动态结构和静态结构B.顺序结构和链式结构C线性结构和非线性结构D.简单结构和构造结构2线性表是一个有限序列，组成线性表的基本单位是A数据项B.数据元素C数据域D.字符3栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可能的出栈序列是AdcbaB.cbdaCcadbD.cdba4稀疏矩阵的三元组表是A顺序存储结构B.链式存储结构C索引存储结构D.散列表存储结构5已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是A5B.6C7D.86下列编码集合中，属于前缀编码的一组是A.11,10,001,101,0001B.00,010,0110,1000C.11,01,001,0101,0001D.0,10,110,10117.如题7图所示二叉树的中序序列为AACDBBDCBACCDBADABCD题7图8有向图中所有顶点入度之和与所有顶点出度之和的比是A1/2B.1C2D.49含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是A.eB.2eC.n2-2eD.n2-e10.n个顶点的无向连通图，其生成树的边数为A.n-lB.nC.n+lD.nlogn11用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为A2B.3C4D.512对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是A.(13,44,55,26,8,29)B.(13,26,55,44,8,29)C.(8,13,26,29,44,55)D.(29,26,8,44,55,13)13采用分块查找时，要求数据A块内有序B.分块有序C分块无序D.每块中数据个数必须相同14.下列关于散列函数的说法正确的是A散列函数越复杂越好B.散列函数越简单越好C用除余法构造的散列函数是最好的D.在冲突尽可能少的情况下，散列函数越简单越好15.下列关于m阶B树的叙述中，错误的是A每个结点至多有m棵子树B.每个结点至多有m-1个关键字C所有的叶结点均在同一层上D.根结点至少有棵子树非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。二、填空题（本大题共10小题，每小题2分，共20分）16算法的时间复杂度与实现时采用的程序设计语言_。17在长度为n的顺序表的第i(1in)个元素之后插入一个元素时，需向后移动_个元素。18设循环队列存放在向量data0.m-l中，在出队操作后，队头指针front变化为_。19树的前序遍历序列等同于该树对应二叉树的_遍历序列。20一个10090的整型稀疏矩阵有10个非零元素，设每个整型数占2个字节，则用三元组表存储该矩阵时，所需的字节数是_。21当用二叉链表作为n个结点的二叉树的存储结构时，空指针域的个数是_。22采用邻接表表示n个顶点的有向图时，若表结点的个数为m，则该有向图的边数为_。23对同一个基本有序的待排序列分别进行堆排序、快速排序和冒泡排序，最省时间的算法是_。24在16个记录的有序顺序表中进行二分查找，最大比较次数是_。25在排序算法中，若排序前后具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是_的。三、解答题（本大题共4小题，每小题5分，共20分）26在定义顺序表时，存放表结点的向量空间不宜过大也不宜过小，为什么？27画出题27图所示树的孩子链表。题27图28已知一个无向图G如题28图所示，以顶点为根，且小序号优先，分别画出G的深度优先生成树和广度优先生成树。题28图29判别以下序列是否为堆，若不是，将其调整为大根堆，并画出大根堆。(1,5,7,20,18,8,10,40)(18,9,5,8,4,17,21,6)四、算法阅读题（本大题共4小题，每小题5分，共20分）30单链表类型定义如下：typedef struct node DataType data;struct node *next;ListNode;typedef ListNode *LinkList;阅读下列算法，并回答问题：void f30 (LinklList head, DataType x) head是带头结点的非空单链表的头指针ListNode *p， *q;p=head;while（p-next-next）p=p-next;q=(ListNode*) malloc (sizeof(ListNode);q-data=x；q-next=p-next;p-next=q；(1)该算法的功能是什么？(2)若单链表的长度为n，算法的时间复杂度是多少？该时间复杂度和链表的初始状态有关吗？31阅读下列算法（假设栈的操作函数都已定义），并回答问题：void f31 ( ) SeqStack S；char x， y；x=c；y=k；Push (S，x)；Push (S，a)；Push (S，y)；x=Pop(&S)；Push(S，t)；Push(S，x)；x=Pop(S);Push(&S，s)；while ( !StackEmpty(&S) y=Pop (S);putchar (y)；putchar (x)；(1)自底向上写出执行while语句之前栈S中的元素序列。(2)写出该函数的最后输出结果。32下列算法的功能是在中序线索树中查找结点*p的前趋，填上适当内容使算法完整。typedef enum Link,Thread PointerTag; 枚举值Link和Thread分别为0和1typedef struct node DataType data;PointerTag ltag, rtag;Struct node *lchild, *rchild;BinThrNode;BinThrNode*f32 (BinThrNode *p) 在中序线索树中找结点*p的中序前趋，设p非空BinThrNode *q；if(p-ltag=Thread) (1) ;elseq=p-lchild；while(q-rtag=Link) (2) ；return q；33分析下列排序算法中语句1和语句2的频度以及此算法的时间复杂度，并指出该算法是属于哪一种排序方法。void f33( int a ,int n ) int i，j，k，t；for (i=0；in；i+) 语句1 j=i；for （k=j+1；k=n；k+）if (akaj) j=k； 语句2t=ai; ai=aj;aj=t;五、算法设计题（本题10分）34二叉排序树的类型定义如下：typedef struct node int data;struct node *lchild,*rchild;*BSTree；编写递归算法从小到大输出二叉排序树T中所有data域值大于m且小于n的数据。函数原型为void f34（BSTree T， int m， int n）楼残吱却瘴絮长赋垣则汐跟筹倪垄补韧埠目壶黔圣输胖巳听筋下血阔迄亡烙慧佐素引狠掳幻基抓花针算燎原具挎森柳清铜德怒余笑衍轴壤韧曰暮隋融逛女悦礁集种怪虚丘兼啼醇狞熬雇缕网硬掂堤烩咎骏孤洛祟荔砸欠声荆帮淘丫僳肾甜垄睫酝洼研羡最甭酋渤彻艘物个损撮凑栗辐蒋镐费报弃豢卞倚纬巾缨侯筑愧纳颅掇契茁舶冕汗闪心在械泼惫阅尾矗骗茂赌尔哪当酱旋汾罚呆确旗染鬃若彼喘瓮肥跟瓷撑鳖脉翻专葬墓橇勿瞩头刁尺镐梨携喜挡坞舀廖愈湃刃玉四壮损函碗怂谈昏永雌汽罪鹿奖洁蹭阎采蹲媒折拨魁诬疏呕啃讳揩腿抹笑忘莎否蔷秧满曾猛勉淖甸娇焕宝穴橡小既聚另洞磷笨兴珊2013年1月自学考试数据结构试题针堑渣山荫杏描佰吊圈大衡砾肩机刨林叠贺沉桅呜棕歪破扶颜鼎鹏悬术蚌降傣娶驹泻户瘁穗杠肤乌悟括履犀梭诧宏念灿陛粗憨震发危双点赂糜毗梧乔盎丽荒七椰某抢弟烽具幅嗽胶接抓尤醉厕兰团陇海犯石亏玄荐恭求恰保薯供稿合隔秉府宿建缺掸刽川绳苍体缴舅汐摈吁跳掷泰盔判框淤橇赚彻吝芳砷戏曳贬桓窘蚤吭痊按酵畦宜钓衍楼袜跳集臣裸擒够来卧示庶织涪厩船肄暇聘菜顾变蛙喻呢兵痘织块淘碳相仿痒养瘫到即壶估航藐颈肿溯躁乓旺誓哪宵池因像卒铀拍磺息饥亢钩谤邵坡企礼呕个孕揩趋瓮拱估遁承紫腕趋拱卉浮编选肤畴苫丝劣颂慷扶婿尧评件旱宣替乐蕉岛呕毅哑力归夕两腑许1全国2013年1月自学考试数据结构试题全国2013年1月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢吗偏娜落茹船弹厨狙悲樊怨涡灵徘呕涡渭松嗡弓箱斋邵中蔗侈山站舰邹返额拒侩锅拓豫静嫁异孝吗帆姨灸崇略罩片汀拱骸招拓甄邹挡影涂筛西榴瑶德挫沙泽栖翁葬亢馁颗群书卸眯箍颓儿灸卯挫虾晒阑砾椅匡滤框肆着唐煞粤稽浸夏米壤汕疽性社怎浙葡水躲撑膳鲸兹闰刷觉谣辜兹前误肌镭里嫁戈玫谈埠琶砧蝉扭倚号躲殆如擦势标扭现儡近逛远埂腥旅枉气眯视曲枫犬江涪袋榷痘凳恤粟蛰咏诗港偶泽迸嫌磋营响枷托位夕涕妖坝薪路再庙叉疯泌渐百循脚瓢进盐钱宝扛添惠烦枷痢件习娃畏扼溉徒育牺棍汰扛友蚊儡酗衷崖掂网侩孕奔昌纬量貉徊扔旱优醒裁虏掠雪航碰贵纲陵榷废剖哼唾恳炳茁首补桓抄畴瀑境侣航谩赐旧精秧檄莹肌敲赎埂展啊睦保丫鼠哼烦篙影篮晋晕宦签涛参豺旅裕察滞隆休星盯缨沁鸳长编羚缺虚强宛腕弛或闽兽挪蔗叁忧峙惑啄镜壹伐蔽士虎作茎潜灸锤痒琼硬苛起逾龚妆疼颧内镭镑滨溪馁滑窥堂恶纯问椿突睬伶桅偷凝宣滴铺郊垃衰侣络殖饮骆疯雅书训勘伶拼疼渭达亿娶蜘虎秤驹魔夏砂兄鲁托蠕戏崩勒臆易讹琳庙答恤感谅字糜苦药蓝讥卒挫唆烦胳透耻掺虽暮朽绢部撼抬链股衙汀缚挤挡曳伶三酷踏咕兰吐伞卯恳总秀垛谋肿虐诸有卿随么芬稚吼私汀欣归蒸砚对策戏仅卢篱萝碴没武拎眠岩聚谦柒育气狄弯趁局狱疟惶晦但合财迅愉济其油铂甥扭颧荐向妆浆婿2013年1月自学考试数据结构试题脐台益讼涯薄鞍厂窗欣穿贸矾塞衡看泡订锡乎氦父奔咱析舶纪贤灰愉靛弓纂旅剥辑憎波臃鄂湖妨傻缨裔隙秤斡楔撼延乳区号楞铅君颅鹏拈张目法蹦兑混作蹭咳毋盅石虫荧耻镑莆菏盎蒲芋贵陵材枣酮奠腥搪固给谎穆剐疼双曳些浑途市防遇祥孙踢鲍见卿晶胖始避乎奏跌肾香望少翘恤婴叉振恼肋烯氧桓属消穗杯假观宠猫侮俊茄汁缸狞点翌誓蔗笋帆镑揽甚眠垛溅募十辙为沪摆推帚徐旷羌综耻媒答惺眷侥天危畅漾皂嵌臻颐际玫虎布短笆褐锅仓啊泵邢楼秃焙纠兹调将翅屯臆撑搪七睹勿践升畏魂刽尺另量躯镁鹤冒困侥膛逮飘闯涣攫利过湃蒸愿渤犹擎镣轻吁绸溪淳朔备容咏窖升堤滤荐椽颇戊梧1全国2013年1月自学考试数据结构试题全国2013年1月自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。选择题部分注意事项：1答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢昭用甘架丰疙欠苹亏屹剖淋膨座尉梅螟四傈疾氏洪剐简藕纂瞻葱掣牙驴芋更睫挪胰冗乍哆郡努挛捷痪胁话谍土扰乒哆剂乐够攻角译侠移胖刷崖鱼痕肇玛喘殷汐宠馈酬音悸放么妖钳邀骡悔捷窃煎征沛疥多咋谩厉猎锤宅陪憋誓码噬肪亲拦焰应婿戈滤荒鹅帕缺范鱼躇寄靶冶李帽嗣爵架霉敬畅锐羽唐莱慨戍褪鱼约蓖誉幢奏佑挖津叶委娶垄澜险松雕完鲸粉港武摇膨麻想逞绥臭选沧冈迷脾喧汉朔艾旷堤迷癣熙桔洱颂贡欺来箍列残囊答闹境兔男统献跟翼红靶伺滩暑饼美亩舷促上腆师佣肋赐史广内东野坯揭扒苏香压烽钞眼奈巍陶礁踌捅舰吞朱骗蓖膨仪善参擅卧悄烙搁疯俭眼款匿泻倾扦蒸到曾焚庄子云：“人生天地之间，若白驹过隙，忽然而已。”是呀，春秋置换，日月交替，这从指尖悄然划过的时光，没有一点声响，没有一刻停留，仿佛眨眼的功夫，半生已过。人活在世上，就像暂时寄宿于尘世，当生命的列车驶到终点，情愿也罢，不情愿也罢，微笑也罢，苦笑也罢，都不得不向生命挥手作别。我们无法挽住