2018年04月02142数据结构导论试题及答案.docx

《2018年04月02142数据结构导论试题及答案.docx》由会员分享，可在线阅读，更多相关《2018年04月02142数据结构导论试题及答案.docx（9页珍藏版）》请在第壹文秘上搜索。

1、2018年4月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码02142)本试卷共S页分100分,考试时间150分仲。考生答注意事呱：1 .本卷所有试题必须在答题卡上作答。答在试卷上无效,试卷空白处和背面均可作单稿城。2 .第一部分为选择题。必疹对应试卷上的号使用2B归检将“答IS卡”的相应代码涂黑。3 .第二部分为非选择题。必须注明大、小8号,使用0.5充米黑色字迹签字篦作答。4 .合理安簿答题空间,超出答题区“无效。第一部分选择题一、里选择:本大共15小题，每小E2分,共30分.在小列出的普选项中只有一是符合目戛求的,请将其选出1 .数累的逻辑结构分为四科，其中结构复杂的是瓦集a

2、B线性脑构C.树形砧构D.ff1.fW2 .下面程序是矩阵转置算法MM的实现过程.其时间复杂度为constintn=3voidMM(intAnQn)inti,j.tempifor(i三0ini+)forj-0i3 .设原序次的次长为n,JHH除一个元索在最坏情配下元族移动次数为A.n2B.n-!C.nD.n+i4.带头结点的双向神环转表1.为空的条件是A.1.next=1.-priorR1.-prior=NU1.1.C. (1.-nex三三1.)8*.(1.-prior三*三1.)D. (1.next三三1.)8t(1.-prior三NU1.1.)5.执行透枝操作，在元烹X进校前需要进行的操作

3、是A.判断栈是否清，若枝未滴.t。P值加1C.判断栈黑否濡，若栈未满，top值M16.关于队列，下列叙述正确的是A.队列的元索个数可以无穷大B.判断找是否空，若栈未空，topff加】D.判断桃是否空，若枝未空,top侦城1B.队列中元索的类Sf可以不同C队列是一个非线性的序列D.队列的IJ点是先进先出7 .设循环队列的元案存放在一维数组Q30中，队列非空时，front指示队列首结点的帆一个位置，rear指示队列见结点.如果队列中元京的个数为IOJront的值为25,则rear应指向的元素是A.Q4RQ5CQCUD.Q158 .二又树第KiND层上的结点敷最多为A.24-*Ri-IG2iD.2-

4、G-D9 .关于二叉转表,下列叙述正确的是A.二叉转奏是二又树曜一的钻式存储结构B.对二又链表的访问可以从任意结点开始C.好个二叉链表不需要有一个指向根节点的指针D.二叉链裳的结点结构包含一个数据域和两个指针单10 .假设初始森林中共有nt二又树.AJ棵树中都仅有一个孤立的站点.将该森林构造成哈夫受树，则最终求得的哈夫曼树的站点败为A.n1B.nC.Zn-ID.2n11 .无向图中的极大连通子图是A.连通分量R生成树C.强连通分量D.强连通图12 .在用邻接裳我示图时，对图进行深度优先费索遍历的算法的时向或杂度为A.0(n)B.0(n+e)CO(n*)D.O(n)13 .静态去找表与动态森找表

5、二者的根本差别在于A.它们的3?羯结构不同B.施加在其上的掾作不同C.所包才的数榭元案类8不同D.存储实现不同IU在/列曲列H(k)-kMODm中，一般来讲,应取A.奇数B.偶数C.素数D,充分人的数15 .在下述四种棒序算法中,所需在助存储Ift最多的是A.堆排序B.快速排序C.直接选择排序).内并排序第二部分非选择题二、填空融；本大共13空.每空2分.共26分16 .战性表中如果站点数不为零，刚除起始结点没有口接前驱外，其他姆个结点有且仅有个直接的17 .单琏表各个结点在内存中的存储位置并连续”18 .栈初始化运算的目的是.19 .假设以E和O分别表示进栈和出栈操作，则对输入序列a,b,C

6、,d,e进行一系列操作EEOEEOEooo之后,得到的输出序列为。20 .二叉树的任一结点都有两株子树.并且这两棵f俐之间有关系.21 .一棵树中所有结点的域大值称为该树的高度.22 .高度为h(h32)的完全二叉树至少有个叶子结点。23 .图的广度优先搜索遍历类似于树的按遍历的过程。24 .秘疏矩阵可以采用法进行乐闻存谛.25 .完成拓扑排序的前提条件是AOY网中不允许出现.26 .数据元素的键值和之间建立的对应关系称为散列函数。27 .静态查找去是以具有相同特性的数据兀点集合为道辑结构，似不包括插入和28 .设表中元案的初始状态是按设值递增有序的,分别用堆排序、快速排序、目泡排序和归并排序

7、方法对其按递增顺序进行排序，排序方法最省时间.三、JS用量：本大噩共S小题,每小6分，共3Q分29 .将题29图所示的二又树转换为对应的树或温杯.30.18设某个电文由5个字母a,b,c.d.efi!成,每个字母在电文中出现的次数为7,9,5,6,12,试为这5个字母设计哈夫曼树并写出对应的哈夫曼编码.(构建新二又树时，要求新二又树的左子树极的权值小于等于右子树慢的权值.)31.831图所示为一科向03,试燃出该图的邻接表表示及对该图进行拓扑搏序的各科可使的拓扑序列.31B32 .设Itt列表长度为11,故列函数H(key)三keymodIMmod为求余运算3怆定的健值序列,(3.12,13,

8、27,34,22.38.25).试画出采用线性探测法解决冲突时所构造的数列次，并求出在等微率的情瓦下夷找成功时的平均去找长度.33 .设有健值序列如题33宣所示，现采用快速排序算也以位于最左位置的值为基及对它进行排序.请给出57,72.88这三个元*在第一超快速拷序后的位置.033初始位置O1234S678能值序列722657,834280734860，算法ift计题：本大题共2小11.每小题7分，共14分.4 .假设单钻表的类型定义如下Itypcdcfstructnode(DetaTypcdatastructnodenext)Nodet1.ink1.ist设计算法Inimte1.ink1.i

9、St。实现单链表的初始化.5 .巳知静态表找表顺序存储结构的类型定义如下IconstintMaxsize三201typedefstruct(KeyTypekey,关健字-其他域Tab1.cE1cmtypedefstruct(TabIeEIeme1.enMauixe1.intSqTabIe1.设计实现有序我二分行找算法SearChBin(SqTabIeT.KeyTypekey(1.定有序表是按健值从小到大有序).绝密启用前2018年4月高等教育自学考试全国统一命题考试数据结构导论试题答案及评分参考（课程代码02142）一、孽选择:本大共15小,每小2分,共30分1.D2,C3.B4.C5.A6.

10、D11.A12.BOpB14.C15.D二、填空星:本大共13空,每空2分.其26分e9.D10.C17.不一定20.次序:M1.19.Ixkca寻30图1.构造一个空校21.J三fte11（2分）a00b01（注;根结点2分：左于树1分,右子钟1分）（2）各字符的编码为，31.（】）读有向图的邻接表为,（2）各牌可能的拓扑排序序列为,AEDBC1分）AEBDC.（1分）31答32表,0C,00key312V342238.25H(key)31f2I510H-S3比较次数111114*25（注I每个t1分,答对任意4个及以上得4分）（2）等概率情义下香找成功的平均/找长度=（I+I+1+1.+4

11、+1+2+5）/11=16/11（2分）33. 元素57在华*Q：AQ。（蝴元IrT2式位置516萨06萨,I2分Z元素88在位置8.SN2分）四、法i计:本大!共2小,小7分,共M分.34. 1.ink1.is1.Initunc1.ink1.ist()1.ink1.isthead：.能d.nd1.ocnext三NU1.1.returnhead：35. intScarchBin(SqTabIcTKcyTypckey)int1.ow.highIow三三1.ig三T.nwhi1.e(1.ow21if(key=T.e!emmid.key)returnmidie1.9eif(keyT.e1.emmid.key)high三mid-1.1Geecscow三mid+h一