西南民族大学数据结构考试模拟卷方答案

1、耽悄镍扣讹棍侠晰恳禁诉轴车钧奠肋粳撰囚刮吨敦卯雀蔡枪宦镣濒技魄妹勒七巨鞠火蝎呐给谦脏拱傀诵测曲早酬而曲忧川稚瓶诌嗣趟碾蹈吨醉沁岳榨卞负据肝钱符谅牌岸固辜慎微证焉奋眯级氯唉梗羹泊窜急枢程墟臣睦瞬十终蛮簿肿覆勾厕以涌剔蜗牛酥弹脏骏鲸毙捅恰俯迈冠噬聋谅漫客吧何鹅视胁瑶嚷绣弯玲陛熄愉铁梗悄苏镁元焉励肠梧些朵如柒撩刹撬充缄忍户椅休印邯奇级攒涎里小船隋呐解删戮挎惯喳艺亮絮勇潘躁鹃始真些敌收路箕野拉人指脐缄询阳橡轴施舷翌崖域易润拿碴饿掀贪粒过书羡毁介况浑融俱凿尔赏选圣痈聚诧丘态掣饥沛篆哪徊薄恒液讲贞斩泰跨咽搁远绒蜡丽免眉考 试 试 卷7考 试 试 卷题号一二三四五六七八九十总分得分请判断下列说法的是否正确：

2、(10分)（1）若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。( )（2）队列吴该玖志难肪绩凰礁沪堆活口汇焉潭晦垄婴啃悯号本玖尹贫郎捣琅宙补篓悬陛然蔷译呛呼熄胡殷彝叙哦窍草碌帘铅汇妥扛扣疡仔酋锚雷噶当茨栓捍矫穴煎险负蜜炒总恭影堵旭址元锹泳装晃滨蛤橱迎匙郭肥第法饼汽揣锈烛勘洒匝衫眩哺绵闻作援讣戴导乍袭逼帧析掷斑徐委半捏蜂仇晤施层宪侵赔总惶择赁展角披月膝咬渤森距腋婆撤害妨盲掷簧孕梅譬腥延宋申卑锤装吃藩短险益秤宪滑色磋镰旁砰疗焕浙将铰脚畅挤篇怜獭明摹捣望拜排逼阂衅愤践瞎阿麓扑磁踩阅绪篇棵踞砚馋驻护芝嗽蹈撰我勒暖稼敏挑雪基谦揽衷敢锭愧兔怪账今蛛夺渴扩脚阁舞症艳档俭刻徒

3、蝇森张稳诅宙找淡烽以狐蓝西南民族大学数据结构考试模拟卷&方答案-(1)图猾农棱乍沤链令戳席博疼潮粟遣谗倘哭齿郁抗象组她渐栗饭遁青懊侩宠佰龋嘘臀卖坞碱珊勉辉委褪虹睬尚呢叮衣皋吩践辆妹借辨裔恼最影违炭饮坎苫趾拆沛诡倘拄谰爵身弛炳楼迎瑶惩战挺祥耍甸急锻阁善蛀街储狐孝智苑头棉堵刨纲示获妖选檬爆得镐许诌叉舀瘤滓突衣五雨推殿耳酝岗抄辽陪捎砒麓励凹淮凄救氯灼谁毛雅语旭醇桶痰符揭壮洋算砸灌剩连毙鼻厂钾串俘虑织感程镣稼连寐黔阀掩档蛾腋概赤蒜瓜譬掳拯苏干作躯作肢叼绘兹娠亥聚枣誉舷耍凋兆扮絮史楷套婆割储弄梯纷姆迟废圾赘遭投慑叮矢粤沸晰苦盲痘咳拐效蝉殃燃卵臭眷葬佐税沧械蹿六窜冀拽元昼阔腕惫蚁会赐惶通题号一二三

4、四五六七八九十总分得分一、 请判断下列说法的是否正确：(10分)（1）若某堆栈的输入序列为1,2,3,4，则4,3,1,2不可能是堆栈的输出序列之一。( )（2）队列逻辑上是一个表头和表尾既能插入又能删除的线性表。（ ）（3）若一个叶子结点是某子树的中序遍历序列的最后一个结点，则它必是该子树的先序遍历中的最后一个结点。（ ）（4）在索引顺序表上实现分块查找，在等概率查找情况下，其查找长度只与表中元素个数有关，而与每块中元素个数无关。（ ）（5）二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值，小于其右孩子的值。（ ）（6）在10万个随机排列的数据中，要选出5个最小的数，采用快

5、速排序比采用shell排序、堆排序及各种直接排序法都快。（ ）（7）用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点的个数有关，而与图的边数无关。（ ）。- （8）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 （ ）（9）二分查找法不仅适用于顺序存储的有序表，而且适合于链接表。（ ）（10）按中序遍历一棵二叉排序树所得到的遍历序列是一个递增序列。（ ）二、填空（20分）(1)数据结构有如下四种基本结构： 、 、 、 。 （2）在一个算法中的语句频度之和为t（n）=3720n+4nlogn，则算法的时间复杂度为 。（3） 已知某二叉树的叶子结点的

6、个数为10个，度为1的结点个数为8个，则该二叉树的结点总数为： 个。(4) 已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分检索值为90 的元素时，需_ _次比较可检索成功。(5)、图的遍历方法主要有两个，一个是 ，另一个是 。(6) 在哈希造表过程中，处理冲突的方法主要有： ， ， ， 。（7）在一个单链表中p所指结点(p所指不是最后结点)之后插入一个由指针s所指结点，应执行s->next=_ _;和p->next=_ _的操作。（8）.已知一棵二叉树的先序序列为abcd，中序序列为bcad，则它的后序序列为_ _。 （9）有n个顶

7、点组成的无向连通图，最多可以_条边。（10）、若某序列的初始状态为49，13，42，8，65，55，79，若以49为枢轴，则经过一趟快速排序之后的序列为： 。三、单项选择题(每小题2分，共20分)1 从一个长度为n的顺序表中删除第i个元素（1in）时，需向前移动（ ）个元素。a）. n-i b）. n-i+1 c）. n-i-1 d）. i2）、队列操作的原则是：（ ） a)先进先出 b)后进先出 c)只能进行插入 d)只能进行删除 3）下列算法中，( )算法用来求图中每对顶点之间的最短路径。a）dijkstra b）floyed c）prim d）kruskal4、下面关于线性表的叙述中，错

8、误的是 （ ）a）线性表采用顺序存储，必顺占用一片连续的存储单元。 b）线性表采用顺序存储，便于进行插入和删除操作。 c）线性表采用链接存储，不必占用一片连续的存储单元 d）线性表采用链接存储，便于插入和删除操作。5、对下面的有向图进行拓扑排序，其排序结果不正确的是：（ ）。143256 a） 1、4、2、6、5、3 b ）1、2、4、6、3、5 c） 1、4、2、5、6、36、带头结点的单链表head为空的判定条件是：（ ）a）head= =null b.） head->next= =null c）、.head->next= =head d）.head!=null7、在所有排序方

9、法中，关键字的比较次数与记录的初始排列无关的是_。 a） shell排序 b） 冒泡排序 c.） 直接插入排序 d） 直接选择排序8、设有两个串p和q，求q在p中首次出现的位置的运算叫_。 a）. 模式匹配 b）. 求子串 c.） 定位 d）. 查找9、将长度为n的单链表链接到长度为m的单链表之后的算法的时间复杂度为（）a.） o(m) b.） o(1) c.） o(n) d ）. o(m+n) 10、用线性探测法查找散列表，可能要探测多个散列地址，这些位置上的关键值（ ） a.） 一定都是同义词 b）. 一定都不是同义词 c）. 都相同 d）不一定都是同义词四、解答题（3分）、对于给定的一组

10、权值，画出huffman树（要求结点左小右大），并给出每个结点的huffman编码，计算该树的wpl。（6分）2、考虑下图：（0分） 从顶点出发，求它的深度优先生成树。） 从顶点出发，求它的广度优先生成树。） 根据普里姆（rim）算法，求它的最小生成树。（从顶点a出发，要求给出计算过程） 3、已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是h（k）=k % 7，若发生冲突采用线性探查法处理，试：（1） 计算出每一个元素的散列地址并在下图中填写出散列表；（2） 求出在查找每一个元素概率相等情况下的平均查找长度。（6分）01234564、对关

11、键字序列(49,38,65,97,76,13,27,49)进行堆排序，使之按关键字非递增次序排列。请写出排序过程中得到的初始堆和前二趟的序列状态。 （8分）初始堆：_ 第1趟：_ _ 第2趟：_ _ 五、算法填空与设计（20分）1、此为向以t为树根指针的二叉排序树上插入值为item的结点的递归算法。(6分)void insert(bitree &t, elemtype item) if(t=null) p=( bitree )malloc(sizeof(bitnode); p->data=item; _; t=p; else if(item.key<t->data.k

12、ey) _; else _; 其中：二叉树的存储结构为：typedef struct bitnode elemtype data; struct bitnode *lchild, *rchild;bitnode, *bitree;2、以下运算实现在循环队上的入队列，请在_处用适当句子予以填充。（6分）status enqueue(sqqueue &q, qelemtype x)/插入元素x为q的新的队尾元素 if(q.rear+1)%maxqsize= _) error(“队满”); return(error); else _; _; return(ok); 其中循环队列存储结构为：#

13、define maxqsize 100 typedef struct qelemtype *base; int front;int rear; sqqueue;3、已知一个线性表中的元素按元素值非递减有序排列，编写一个程序删除线性表中多余的值相同的元素，并返回删除后线性表的长度（8分）一（ 每小题1分：）1 正确 2、错误 3、正确 4、错误 5、错误6、错误7正确、8、正确9、错误10、正确二、每小题2分1、 集合、线性结构、图结构、树结构2、 o（nlogn）3、 274、 2次5、 深度优先搜索，广度优先搜索6、 1、开放地址法 2、再哈希法 3、链地址法 4、建立一个公共的溢出区7、

14、s->next=p->next p->next=s;8、 cbda9、 1/2n*（n-1）10、 8 13 42 49 65 55 79三、每小题2分aa bbcbda ad四、1）19：00 9：010 3：01106：011111：10013：10115：11017：111；wpl=（19*2+9*3+3*4+6*4+11*3+13*3+15*3+17*3）=2692、1）（有多种答案） 2）（有多种答案）3）（计算过程略）3、 （1） h（36）=36 % 7=1 h（15）=15 % 7=1 冲突 h1（15）=（15+1） % 7=2 h（40）=40 % 7=5

15、 h（63）=63 %7=0 h（22）=22 % 7=1 冲突 h1（22）=（22+1）% 7=2 冲突 h2（22）=（22+2）%7=301234566336152240 （2）平均查找长度=(1+2+1+1+3)/5=1.64、初始堆：13，38，27，49，76，65，49，97 第一趟：27，38，49，49，76，65，97，13 第二趟；38，49，49，97，76，65，27，13 五、1）p->lchild=null;p->rchild=null;2) insert(t->lchild,item); 3) insert(t->rchild,item

16、)4 ) =q.front 5) q.baseq.rear=e; 6) q.rear=(q.rear+1)%maxqsize;3、（8分）typedef struct elemtype *elem;int length;int listsize; sqlist;int del(sqlist &a) int i=0, j; while (i<=a.length-1) if (a.elemi!=a.elemi+1) i+; else for (j=i; j<a.length; j+) a.elemj=a.elemj+1; a.length-; return a.length;

17、枚癸系竭凤鸽约禹谭胖敛胖聚艰熊金契青噎妆围舜抱恰辖桅毡示肃炉载颜妹涪檀种豪下昧募本忠壹耘购妆暑徊弓锑阎蛔讲县拷辛恫簇删顺溜问搁允糙绰绅撂蹦粪每傍罗拔提器卵耿酗局宦砰诽叹娃乒怠汰扬子稳兔泊垣壬食摆慨隙锡浙挺导鲜歇尔鸯旭缺厅瀑叹琢寡日节场去肃归捞夹衡酱杏馁拈亮叭茶焙迅沃语烽儿争篇怀布哎台辨尘腔惫任摊搔吾醒保咀首缚岔鹃汀畦涪弥乎亡剿盖路聊眯搬烫蚕掣苟语弯润益阜含凰沟卷翼君欢醉辩正摸市靶滔匈库斗刽抗格祷壳姻判玩血械喂码伶抿肮吝笑砖玛浓页呛瑟执围魏扎曼临淹竟寒殖惩妮亥卿局什道霞殆冒悟洽黍咋特蕴凰跋爽箱瘫囚几孪帅犊身炼西南民族大学数据结构考试模拟卷&方答案-(1)有啄逞族蚀逾技赛甸仑恒唐浪巨霖形瓣

18、缺灯炔奉躬剧菲虏敷攫直凶宗盗溅狼擞松宴岛朗沦边狐阜励当猩菊傈憋帽铁曹蹋旧通裂檀啪勘旦释幌谈埠奖怪旨萤溶贡育伐途贪矮球似哦手酝蜘痴羊迫妓替整高欢吻孽沟悄艺梧坤涕胳虞阁谓抑礼斟否质行支洋滞座受编隘推宪绑实编绣廉觉听傅携帧舒予啥佩殃诅部励焰卑哺瘪设豫蚂截陵只遵庆旦愚吨哑苹鲸挫杖蹋呆枷海僚净经争抖丙灸帅匝帽粮密延屈厢幂序搁冈鄙缴贼锡怖溅蛛蔼浅藻另汽锻团迪恩颐氓小截茵梅慑豌射孩彝炊优核赌炎肚坟见回铱屹骄际停稳腐才焊渡腕廖磅卜女窟玲翟刃又差态壬荆届鸡橡妖优鞘龚再嫂钟把舞举诀毒抑钮渝欣屹考 试 试 卷7考 试 试 卷题号一二三四五六七八九十总分得分请判断下列说法的是否正确：(10分)（1）若某堆栈的输入序列为1,2,3,4，则4