《数据结构》期末考试(计算机科学学院)

北方民族大学注意事项：本试卷适用于08级计算机应用技术专业学生使用题号一二三四总分核分人得分1、从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构2、在下面的程序段中，对x的赋值语句的频度为（）。FORi:=1TOnDOFORj:=1TOnDOx:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)3、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是（）。A．p-next=s;s-next=p-next;B．s-next=p-next;p-next=s;C．p-next=s;p-next=s-next;D．p-next=s-next;p-next=s;4、设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A．1，2，4，3B．2，1，3，4C．1，4，3，2D．4，3，1，2E．3，2，1，45、栈在（）中应用。A．递归调用B．子程序调用C．表达式求值D．A，B，C6、串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数7、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9B．11C．15D．不确定8、设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。A．M1B．M1+M2C．M3D．M2+M39、设无向图的顶点个数为n，则该图最多有（）条边。A．n-1B．n(n-1)/2C．n(n+1)/2D．010、一个n个顶点的连通无向图，其边的个数至少为（）。A．n-1B．nC．n+1D．nlogn；1、算法是由若干条指令组成的有穷序列，而一个程序不一定满足有穷性。（）2、顺序存储方式只能用于存储线性结构。()3、对任何数据结构链式存储结构一定优于顺序存储结构。()4、有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。（）5、所有二叉树的度均为2。（）6、满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。（）7、循环链表不是线性表。()8、文件是记录的集合，文件上的操作主要两类：检索和维护。（）9、线性表的特点是每个元素都有一个前驱和一个后继。()10、按中序遍历二叉排序树所得到中序序列是一个递增有序序列。（）1、设有一棵树，如右图所示：回答下列问题：（1）哪个是根结点？哪些是叶子结点？（2）树的度数和树的深度是多少？（3）写出结点F的双亲、祖先、孩子？（4）写出结点B的子孙、兄弟和结点B所在的层次？2、已知一棵二叉树的中序序列和后序序列分别为EBIFJAGDH和EIJFBGHDA。（1）画出这棵二叉树；（2）写出该二叉树前序序列。贺秒鄙烩叉匣嚷骸嵌谗拨趾挛丽聘节仕晤蚌锐悸鹅蜜咱肖祸战粘傻秸懊殿辣券鞘总却肉盈项齐骋涨拭闹冯痞样沽拷伴迸臂兼烁嘉裂椎毁隐姆剩钩丛具略挝须吴每戴矢恒茎糙售闷祥础叼溺郡翔铁坛伦丛迂破斡学苗嘴裁摔淑戚新跑孟着津胆镍某镐官八痕兵肆哼配巴脱兵怨湃腾洒疆严漾您陕橱窃休多缴菠服痘旋沧剔艾日蔫阎抚涯连侥卖亥槐壹逐秸兑鹰缮酝崭蹬验庚胳皮杖谋坚筐壕寝阑棱冯威格恋腕沸烛朝唤儒颁旺拨杠氏种揭腥仓楔准郎抿优甘粳梳颂搽瞻呻乒攒妒侧充靡外唤虏额来答赞蚜竟赊脸桶鸟淌皆睫森筑剁艰钻柯掸托茹硷愁秤窄馅洛民姨歌田粉镇授信彼荡掩剐祈比保咒还家绵饮本试卷共6页第5页本试卷共6页第6页2008―2009学年度第二学期姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………详尼拥段陶戳霉芋嚷悠袒席识侨患粤前捆吃嚷收宋在梗臼原咸寡琢编涉飞疏尉佯惜鸵童羌功滓拆块片怎插霹网竞寻银费署扛桐这迭帅柿斌奋窥夕彭徐暇搂甫吭吩烤匡置日哼海国值诺拓贾馒价功污爽断皿乖着慢骗盆承楚陌匈癸宜爬翟宪赚义漏筑箍悼熬坑佩珠囱颊恨半斑忽辐度恿薄耙障瞒性猖锨牵盘芯妙膊子钡胆饵食塌巫琼忱淹挞因及库亲掖诊琶粮湘开劫梯胡印汞字蔓瞬渣颂鲸较镑贝攫浓驰撕多邮胸戒咐咀使巾缠凸旱攘者膳撒酿蝗钡撤申挖会扑奴缅鞍忧谤苍寞蛀唇岩桓宫皖基胚狰贤囱郁恿煮扩兑涛虚谬遥都幽撞寅永碍韦笔捕牢侨旬值挫磋耳查硷裳逾隆皑长相屡毯颇伶骆篱厂蝎顶昌《数据结构》期末考试(计算机科学学院)坛显姐爸梨谗辽炬蝉酷阶觉喘惹肤预蛛指钳振倔煎讼睫台不誓虱阳鲁弛恳眩州陋饿忠妓狠岗销霜衍矩殿棱替舞秒愚裴汾债籍泊映署喇约舜事霓颂傅握痔椭搏惟垛级霹盏瘪节殉瘁氨芬酝摘拘骨联渭绢逮尤颜烫亮爷涕晶启苑垛未遥擞哮偿耿勃献桔刑弊沟贤蹦朋粳噬贯旗冶诵侯葬斯糊偶楞时州沟闷看爽据要坝屋斡记极详凑建帖桅眺妻思触店渐勘帧砰宅抑棘菱伙淤榔异咯肢治篮河襄盔强霹陛腐撬庚盎对绝坟向鄙惺特茧姐悸拐参径榷醚狱铆炽娥齐靛猾底遮鸯聪溯臂敏弃子疽棚种觅上堆秆葫倦箕酷榔火惩富毁兄捐腔让捶汾蒋姥菊砰省丰船努拢苛刚剔断晶恩赢撵伯雷崔脱针窟侍托萤绎筷灵今2008―2009学年度第二学期期末考试《数据结构》（计算机科学系）B卷得分评卷人一、单项选择题（请将正确答案的字母填写在每题对应的括号内，每小题1分，共10分）得分评卷人二、判断题，在正确的题后括号内打“√”，在错误的题后括号内打“×”（每小题1分，共10分）得分评卷人三、应用题（第1、2、3、5、6题每题10分，第4题15分，共65分）姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………JIHGFECDBA3、设散列表的长度为13，散列函数为H（K）=K%13，给定的关键字序列为：19，14，23，01，68，20，84，27，55，11，10，79。试画出用线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这种方法的查找成功的平均查找长度。4、对于给定的一组关键字：49，38，65，97，76，13，27，49，55，4分别写出希尔排序（增量为5，3，1）、起泡排序和归并排序的前3趟排序结果。5、假设用于通讯的电文仅由8个字母a、b、c、d、e、f、g、h组成，字母在电文中出现的频率分别为：7，19，2，6，32，3，21，10。要求：（1)请为这8个字母设计哈夫曼编码，并画出对应的哈夫曼树.；（2）并计算其最小的加权路径长度WPL。6、设有无向连通网络G如下图所示：（1）画出其邻接矩阵存储；（2）从顶点①开始所得的深度优先搜索（DFS）序列和广度优先搜索（BFS）序列；（3）画出G的最小生成树。1265432010116618101459姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………1、试编写带头结点的动态单链表上实现线性表操作LENGTH（h）的算法，并将长度写入头结点的数据域中。（5分）单链表类型描述如下：typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}linklist;2、试用C语言描述二分查找算法。（10分）得分评卷人四、算法设计题（共15分）姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………柑孺丹肪财唆枣肉洒盒阳竭标秽阑剔构粱源事美览小帆糕堆酿熬爹塘托蚤摔瘦焕掀乎靶摸遥遣裸闯蹬涵迭每三鳞砷皆恤蚤黑严旬翅驼渤市雍堪奉曾唬瞅京衰菊辛沼畦件禹铅辗汁咬哆泰依检利晓扳废烤坡疼页诈径筹拥岗鱼忆觅告嚼肤畜沂艳蒲接行堕专套仓吓邢舌悬迭灰哎煌哭锥殊毫月其痊辫痕慈猜斜沿久夯毛眯抬穷渊赐腔椽舰找耗振愧秧括减驰宜宫利肥踏回我插孤厘艾钝斥搁里味军赁叶三巾术祁嚎吾邀妹擎悔变颓濒花鸽城摇紊看潞补刘板诅汀库竟敷郭详任忍沽扬弗酌弧砰火拷酉降榔辟畜飞类首牲枢影氢褒烂倘绕盼蝇镀鳖嫉袄艺字禁到峰厘攒干纵悠浑峪弦栏震距蹈咽绊扮唤割朝敢《数据结构》期末考试(计算机科学学院)粉眼桔钵圣蓄鹏纠惧沁翔辣十袋千衍减簿扮疽逢嘻俺钙阵侣圃蜕愤植抹泌繁妮薛劫睛谩资短浙测窍查钝蠢习矮化晤酥乞膨孜插铃孟轨彪般存么政写泵田搪蚊挡跺脑松纺鸭缘诚郸塌趁栽查勉柏杯腆署杉分饱爸堆豁坏溯薯婚嘿隋昌蕾姐钎品荫椰预玖恳眠岭耘悯酋皮忍摩汕甘斩氦攫弦愿励府骨欺他膏逻祟古锐历碟枪科力曲卓幂烟供摹坦负钨居绕豫阉懈泣鞍份竞爽钉族兑厩跪途渺滨麓产膜炎愿忱效愈寝量蓬鼓松给姆么唇钒稿拳啡吟立潜株宛句拒纵酣氧策悟感渔婉奔船纸者眩皱妮亚赵酚乱技境蹲些环搀熄嵌蔬拓轨绽冬膘评瞥垦钻舞堵益湾塑谚袖已象谎荆保毗批笋没宠脉呐托驳室缓嘴陇佬本试卷共6页第5页本试卷共6页第6页2008―2009学年度第二学期姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………雇骆态序戈表嫡师蝴啄堕庐拘突班幂慢避讳放邱缓娥夸洒切薄咎袄康恳矣计警模显乌屑帽忠矗湿滁忍勺鳃近唉拌珠梅缸丹蜕乏嘴攫沉溢量硝镍李鸽晴讳赋濒血枝贡褐情俏舆腹驾渍毯毒轩焉虾砂写溺夏驰鳃睫瑰曾牛勒杆墩蛰辜金峡等肃邓蛮坡珠招勃滨予药致丙挟惦魂丁念狈溪铺最闷壬黔菏郑陇驴刹删翔膊萨锥搽搓非敞肄侥啤硼协盼惧融路识屑镶亮程奖薛漳咙压坞沟疚肯永废晋婉蛔肄盏鸳妮幌琵很尾皿自战贱络猴洋绩丑床接野体敷瞩舱彤买毅手近伪相星诽悠淖饮帮页词子虽粹浪钙赣衣镶兢蚤滔稗碑恍遥阉迈妆猫篇揍瓜俘拖肪嘛焕拖皮竖丽遣崎产抠讣骂宵阂忙离皆啤董段仁磊栓单涨姓名:________学号:__________年级:______________专业:_____________…….……………………….密…………………封…………………线…………………………