数据结构导论考试和部分答案

1、、单项选择题（本大题共15小题，每小题2分，共30分）1.结点按逻辑关系依次排列形成一条锁链”的数据结构是）A.集合B.线性结构C.树形结构D.图状结2下面算法程序段的时间复杂度为for ( int i=0; i<m; i+)for ( int j=0; j< n; j+)a : i: :j: =i*j;A. O(m 2)B. O( n2)C. 0(mn)D. 0(m+n)3线性结构是（)A.具有 n (n>0个表元素的有穷序列B.具有n （n>0个字符的有穷序列C.具有n （n>0个结点的有穷序列D.具有n （n>0个数据项的有穷序列4单链表中删除由某个指

2、针变量指向的结点的直接后继，该算法的时间复杂度是A. 0(1)B. O( . n )C. O(log 2n)D. O(n)5关于串的叙述，正确的是（）A.串是含有一个或多个字符的有穷序列B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有零个或多个字符的有穷序列6. 栈的输入序列依次为1 , 2, 3, 4,则不可能的出栈序列是（）A.1243 B. 1432 C. 2134D.43127. 队列是（）A.先进先出的线性表B.先进后出的线性表C.后进先出的线性表D.随意进出的线性表8.10阶上三角矩阵压缩存储时需存储的元素个数为9. 深度为k （k >1的二叉

3、树，结点数最多有 （10. 具有12个结点的二叉树的二叉链表存储结构中,()A.11B.56C.100D.101kkkk)A.2 个 B.(2 -1)个C.2 -1 个 D.(2 +1)个空链域 NULL的个数为()A. 11B.13 C. 23 D.11.具有n个顶点的无向图的边数最多为（25)A. n+1B. n(n +1)C.n(n-1)/2D.2 n(n +1)A. 0 B. 1 C. 2 D."0 10112.三个顶点V1,V2,V3的图的邻接矩阵为0 0 1 ，该图中顶点V3的入度为（卫1 0一313. 顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个

4、元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为（）A.20000 B.30000 C.40000D.6000014. 外存储器的主要特点是（）A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高15. 在待排数据基本有序的前提下，效率最高的排序算法是（）A.直接插入排序 B.直接选择排序C.快速排序D.归并排序二、填空题（本大题共13小题，每小题2分，共26分）16. 数据的不可分割的最小标识单位是 ，它通常不具有完整确定的实际意义，或不被当作一个整体对待。17. 运算分为加工型运算和引用型运算，读取操作是 运算

5、。18带有头结点的单向循环链表L （L为头指针）中，指针 p所指结点为尾结点的条件是 。19. 在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句 20. 元素S1，&3，s4,s5,s6依次进入顺序栈S,如果6个元素的退栈顺序为S2,s3,S4,s6,S5,则顺序栈的容量至少为 。21. 稀疏矩阵一般采用的压缩存储方法是 。22. 在一棵树中， 结点没有双亲。23. 棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为 。24. 二叉树的二叉链表存储结

6、构中判断指针p所指结点为叶子结点的条件是 。25. 边稀疏的无向图采用 存储较省空间。26. 除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为。27. 二分查找算法的时间复杂度是 。28. 要将序列51，18，23，68，94，70，73建成堆，则只需把 18与 相互交换。三、应用题（本大题共5小题，每小题6分，共30分）29.将题29图所示的一棵二叉树转换成对应的森林。题31图题32图30.给定权值 3，9，13,5，7，构造相应的哈夫曼（Huffman ）树，并计算其带权路径长度。31. 写出题31图的邻接矩阵和每个顶点的入度与出度。32. 二叉排序树的各结点的值依次为2028

7、，请在题32图中标出各结点的值。33. 用冒泡排序法对数据序列（55，38，65，97，76，138，27，49）进行排序，写出排序过程中的各趟结果。四、算法设计题（本大题共2小题，每小题7分，共14分）34. 设线性表A = （a1， a2，,am ），B= （S, b2,b），试写一个按下列规则合并A，B为线性表C的算法， 使得C= （a1, b1,mj,bm ,bm+1,b 当 mn 时；或者C= （a1, b1,na,bn ,an+1,m） 当 m>n 时。线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式

8、存储。）35. 二叉树的二叉链表类型定义如下:typedef struct btnode datatype data;struct btnode *lchild,*rchild; bitreptr;写出后根遍历根指针为t的二叉树的递归算法(void postorder (bitreptr *t)全国2011年10月 数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)1设栈S和队列Q的初始状态为空，元素el,e2,e3,e4,e5和e6依次通过栈S,元素退栈后即进入队列Q,若6个元素的出队序列是e2，e4，e3，e6，e5, e1，则栈S的容量至少为()

9、A.2B.3C.4D.62设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为()A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈3下列程序段的时间复杂度为()i=0 ； s=0;while ( s<n)i+ ； s=s+i; A.O( .n )B.O(log 2n)C.O(n)D.O(n2)4设A是nx n的对称矩阵,将A的对角线及对角线上方的元素Aij(1 < i,j w n,i w j)以列优先顺序存放在一维数组元素B : 1 至B :n(n+1)/2 中，则元素 Aj(iwj)在B中的位置为()A.i(i-l)/2+jB.j(j-l)/2+iC

10、.j(j-l)/2+i-1D.i(i-l)/2+j-15在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()A.G中有弧<Vi, Vj>B.G中有一条从Vi到Vj的路径C.G中没有弧<Vi, Vj> D.G中有一条从Vj到Vi的路径6下列序列中，由第一趟快速排序可得到的序列(排序的关键字类型是字符串)是()A. da, ax, eb, de,bbff ha, gcB.cd, eb, ax, da ff ha,gc,bbC. gc, ax, eb, cd,bbff : da, haD.ax, bb, cd, da ff eb,gc,ha7.不稳定

11、的排序方法是()A.直接插入排序B.冒泡排序C.堆排序D.二路归并排序8设散列表表长 m=14，散列函数为h ( k) =k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是()01234567891011121315386184A.3B.5C.8D.99若元素1, 2, 3依次进栈，则退栈不可能出现的次序是()A.3 , 2, 1B.2 , 1, 3C.3, 1 , 2D.1 , 3, 2C.O (n) D.O (Iog2n)10直接插入排序的时间复杂度是( )A.O (n2)B.O (nIog2n)11.稀疏矩阵是指()A元素少的矩阵B有少量零元素的矩阵C有

12、少量非零元素的矩阵D行数、列数很少的矩阵2)A.n B.2nC.n (n-1)D.2n (n +1)A先根遍历B.中根遍历C.后根遍历 D.层次遍历12深度为k ( k> 1 )的二叉树，结点数最多有()A2kB2k-1C2k-1D2k-1-1()A23 B37C4413. 由带权为9, 2, 5, 7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为D4614. 有n个顶点的有向完全图的弧数为(15图的深度优先搜索类似于二叉树的(二、填空题（本大题共13小题，每小题2分，共26分）16下列程序段的时间复杂度为 for(i=1;i<=n ;i+)for(j=1;j<=n ;

13、j+)x+;17.数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是18. 在表长为n的顺序表上做删除运算，平均要移动的结点个数为19. 在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是20.队列又称为的线性表。21.顺序栈被定义为结构类型，含有两个域:data和top，则对栈*sq进行初始化的操作是22.对于任何一棵二叉树 T，如果其终端结点数为n0,度为2的结点数为n2，则5=_23.棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有个。24.若连通图G的顶点个数为n,则图G的生成树的边数为25.个具有n个顶点的无向图的边数最多为26.中根遍

14、历二叉排序树所得到的结点访问序列是键值的序列。27.冒泡排序的平均时间复杂度为28.将序列60，20，23，68，94，70，73建成堆，则只需把三、应用题（本大题共5小题，每小题6分，共30分）20与互相交换。29.如题29图所示，在栈的输入端元素的输入顺序为C，D，进栈过程中可以退栈,写出在栈的输出端以A开头和以B开头的所有输出序列。A BCDY .题29图题31图题30图题32图30.棵二叉树如题30图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。31.将题31图所示的一棵二叉树转换成森林。32.对于有向无环图:（1）叙述求拓扑排序算法的基本步骤;（2）对于题32图，写出

15、它的4个不同的拓扑排序序列。33.判别以下序列是否为堆。如果不是，则把它调整为堆。（1） （100， 86， 48， 73， 35， 39， 42， 57， 66， 21）； （2）(12， 70， 33， 65， 24， 56， 48， 92， 86， 33)。四、算法设计题（本大题共2小题，每小题7分，共14分）34.n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素A : 1 至A n中，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。35.试写出冒泡排序算法。全国2011年1月数据结构导论试题课程代码：02142、单项选择题(本大题共15小题，每小题

16、2分，共30分)1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为()A.O(1) B.O (.n) C.O(log2 n)D.0( n)2.树形结构中，度为 0的结点称为()A.树根 B.叶子C.路径D.二叉树3. 已知有向图 G=(V,E)，其中 V=V i,V2,V3,V4,V5,V6,V7，E=<V i,V2>，<V3,V5>,<V 3,V6> , <V4,V6>, <V5,V7>, , <V6,V7>，则图 G 的拓扑序列是(A.V 1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V

17、4,V5,V7C.V 1,V3,V4,V5,V2,V 6,V7<V1,V3> , <V1,V4> , <V 2,V5> ,D.Vl,V2,V5,V3,V4,V6,V7A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指(A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个6.组成数据的基本单位是(A.数据项B.数据类型C.数据元素D.数据变量4. 有关图中路径的定义，表述正确的是(7.程序段 i=n ；

18、x=0 ；dox=x+5*i ;的时间复杂度为(8.与串的逻辑结构不同的i-；while(i>0)；)A.O (1)数据结构是(B.O (n)C.O (n2)A.线性表D.O(n3)B.栈 C.队列D.树9.二叉树的第i (i > 1)层上所拥有的结点个数最多为 ()A.2i B.2iC.2i-1D.2i-110.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为A.p-> next=p->n ext-> nextB.p=p->nextC.p=p->n ext- >n extD.p->n ext=p11.下列排序算法中

19、，某一趟结束后未必能选出一个元素放在其最终位置上的是A.堆排序 B.冒泡排序C.直接插入排序D.快速排序12.设字符串 S1 = ABCDEFG ，S2= PQRST"，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2),SUBSTR(S1,LENGTH(S2),2) 后 S 的结果为()A. ” BCQR ” B.” BCDEF" C. BCDEFGD.BCDEFEF 13.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A，并且A的左孩子的平衡因子为-1 ,右孩子的平衡因子为 0,则使其平衡的调整方法为(A.LL 型 B.LR 型 C.R

20、L 型 D.RR 型)A.1B.3C.4D.514.如果结点A有3个兄弟结点，而且 B为A的双亲，则B的度为(15. 数据表A中每个元素距其最终位置较近，则最省时间的排序算法是A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题(本大题共13小题，每小题2分，共26分)16. 下列程序段的时间复杂度为i=1 ；while (i<n) i=i*2 ;个元素。17. 向一个长度为n的顺序表中第i ( K i w n)个元素之前插入一个元素时，需向后移动18. 在循环双链表中，删除最后一个结点，其算法的时间复杂度为19队列的插入操作在队列的 部分进行。20个栈的输入序列是 1, 2,

21、3，n,输出序列的第一个元素是n则第i个输出元素为 。21.一个10阶对称矩阵A，采用行优先顺序压缩存储下三角，aoo为第一个元素，其存储地址为1,每个元素占有1个存储地址空间，则 a85的地址为 。22设字符串S= I AM A STUDENT (其中表示空格字符)，贝U S的长度为 。23.在树形结构中，没有后继的结点是 结点。24棵深度为n(n>1)的满二叉树中共有个结点。25. 在无向图中，如果从顶点v到顶点v'有路径，则称 v和v'是。26. 无向完全图G采用存储结构较省空间。27. 在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数

22、没有关系的查找方法是。28. 快速排序最好情况下的时间复杂度为 。三、应用题(本大题共5小题，每小题6分，共30分)29. 稀疏矩阵A如下，写出矩阵 A的三元组表及矩阵 A的转置矩阵的三元组表。0 3 0 0 0 1 '0 0 0 0 0 05-1 0 0 0 0000040-30 000030.棵二叉树的前根遍历序列为ABCDEFG，中根遍历序列为 CBDAEGF，试构造出该二叉树。31. 下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。po 1 12 5 10_1 珀 8 9 °°12 8 吆0° 25 9 史1 °

23、° 410 co 2 4比32. 给定表(80, 90, 50, 70, 75, 60, 40, 100),试按元素在表中的顺序将它们依次插入一棵初始时为空的二 叉排序树，画出插入完成后的二叉排序树。33. 试写出一组键值(46, 58, 15, 45, 90 , 18, 10, 62)应用直接插入排序算法从小到大排序后各趟的结果。四、算法设计题(本大题共2小题，每小题7分，共14分)34. 试分别写出二叉树的先根遍历和中根遍历的递归算法。35. 试编写以单链表为存储结构实现直接选择排序的算法。20們年4月全国自考数据结构导论参考答案201丄年月高等教佇自学考试全国统-命题考试数据结

24、构导论试题答案及评分参考（课程代码 02142）一、单项选择題f事大題共15小聽.每小题2分，拄30分）1. A2.B3. A4. A5. BG.C7.B& DP C10r AIkC12. D13. B14,015. B二*填空翹（本大题共13小題，每小題2分共26分）1G. O（iog； ii）Hi亠 1IS. 019 駅崖（或尾部）20. n-i4-12k 1222. 1423.叶子（毬端）24. 2" L25.遂通的恋.邻接拒阵釧散列査找28. O（nlf>gv n>三、应用題|卒丈惡共5小題，每小題6分二t创分）29*释硫矩阵久的三元爼褰如下M3分）iV1

25、231&13153452&1-14-3稀疏毎阵A的转Smfr的二元組农如下2心分!iiV13jjnr15”321323-15446 111数据结构导论试翳答案及博分鑫龙第页（共3灵）30解:31解，连通网为:就小生成桃为:（左子树3分，右子树3分）答30图数拯结构挣论试题答案及评分参考第2页（共3贡）（注,左子树3分，右子树豈分）33,解:初始序列；朗£趴15沁疋2LXJ kJ .) 分分分分分第-MiB8,4&t90,18J0,62(1第二趙:11,46,5345.90,18.30,62<1第三 i 15 45.4 F 58 >90,18,10

26、f 62 d 第四 j；ri5t45,46758TS0j ,18,10,62(1第五 Mi 15,18,45*46.58,902,10,62<1Xj®t10TlUB-45t46,53,90j,62第七趣；10 J氛1緘45丄鸽歸,6并9叮(1分)酉、算法设计题(本犬題共2小题.毎小趣丁分，共14分)C J /ra iM MJE »rT FT-.匕卜 j 4Mr -解：托trjhr舱归丹痣：Void p rcordfir(bitreptrr) if(riNULL) visit (r>jpmnrd 电 Mr >Lchild)； preo rdft ( r -

27、- Archil d )； 笛分)中根遍历递归算法Void otdtr(bitrptrr) if(r!-NULL)(inordcrtr> Ichiid) ivisit(r) finorder(Z> rchj Id);(4分昭解：v oid 1 irdtedLi sr_Stltici_Sort ( Li nk*dLi stS>. L)/单链表上胸直接选抒排序貝我 forCp=L»p >next >-next；p= >ncxtj (1 分 qp>HExti忑>-deta(1 分)for(r= qTS = q；rjr T>n&x

28、0/t Q 启面寻找兀素值最小的结点 if(r>next - >daca<x) (1 分x=rT>nex匚>data； srj(1 分)if(s* k吩找時了值出q>血蚀萸小的结点5->nPxtp >next= s>-iicxt； s>nftxt=q； tl t) 工二口 AiicjU*1>口总知.=£5 Ane畫tAhexIi(I 分)p>neit>nejrttp/交换 q 和 fi>next 两个姑点Cl 分)/7fm/Li nkedLi st_Sel ect-Sor t数据结构导沦试聡答案憂评分

29、參考第3页英3贞)2010年10月 数据结构导论试题课程代码：02142、单项选择题（本大题共15小题，每小题2分，共30分）1下列描述中正确的是 ( )A.数据元素是数据的最小单位B.数据结构是具有结构的数据对象C. 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D. 算法和程序原则上没有区别，在讨论数据结构时两者是通用的22归并排序的时间复杂度是()AO(n2)B.O(nlog2n)C.O(n)D.O(log2n)23二分查找的时间复杂度是()AO(n2)B.O(nlog2n)C.O(n)D.O(log2n)4顺序存储的表中有 90000 个元素，已按关键字值升序排列，假设对每

30、个元素进行查找的概率相同，且每个元 素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为 ()A 25000 B.30000 C.45000D.900005散列文件是一种()A 顺序文件B.索引文件C.链接文件 D.计算寻址文件26.两个矩阵 A : m x n, B: nx p 相乘，其时间复杂度为 ( )A 0(n)B.O(mnp)C.O(n ) D.O (mp)7常用于函数调用的数据结构是()A.栈 B.队列 C.链表D.数组&二维数组 A : n: : m以列优先顺序存储，数组A中每个元素占用1个字节，A 1 : 1 为首元素，其地址为 0，则元素 A : i :j的地

31、址为()A. (i-1 )x m+(j-1) B.(j-1) x n+(i-1)C.(j-1) x n+l D.j x n+i9.图的广度优先搜索使用的数据结构是( )A .队列 B.树 C.栈D.集合10序列( 21,19,37,5,2 )经冒泡排序法由小到大排序，在第一次执行交换后所得结果为()A(19， 21， 37， 5， 2) B.(21， 19， 5， 37， 2) C.(21， 19， 37， 2， 5)D.(2， 21， 19， 37， 5)11数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为()A 索引存储方法B.顺序存储方法C.链式存储方

32、法D.散列存储方法12在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的()A 直接前趋B.直接后继C.开始结点D.终端结点13在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为()2AO( 1) B.O( log2n)C.O( n) D.O( n2)14在链队列中执行入队操作，()A 需判别队是否空B.需判别队是否满C.限制在链表头p进行D.限制在链表尾p进行15一整数序列 26， 59， 77， 31， 51， 11， 19， 42，以二路归并排序从小到大排序， 第一阶段的归并结果为 ()A.31 ， 51，11，42，26，77，59

33、， 19B.26， 59， 31， 77， 11，51，19，42C.11， 19，26，31，42，59，51， 77D.26， 11， 19， 31， 51，59，77，42二、填空题 (本大题共 13 小题，每小题 2分，共 26 分) 16下列程序段的时间复杂度为 。i=0； s=0； while( s<n) i+；s=s+i；17数据的存储结构被分为顺序存储结构、 、散列存储结构和索引存储结构 4 种。18从一个长度为n的顺序表中删除第i个元素(K i < n)时，需向前移动 个元素。19在单链表中，插入一个新结点需修改 个指针。20在队列结构中，允许插入的一端称为 。2

34、1稀疏矩阵采用的压缩存储方法是 。22向一个栈顶指针为 top 的链栈中插入一个新结点 *p 时，应执行 p->next=top 和 操作。23有 m 个叶结点的哈夫曼树所具有的结点数为 。24.在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为 。25 .在一棵树中， 结点没有前驱结点。26. 一个具有n个顶点的有向完全图的弧数是 。27. n个顶点的无向图 G用邻接矩阵A : nn存储，其中第i列的所有元素之和等于顶点 V的。28. 选择排序的平均时间复杂度为 。三、应用题(本大题共5小题，

35、每小题6分，共30分)29. 在栈的输入端元素的输入顺序为1, 2, 3, 4, 5, 6,进栈过程中可以退栈，则退栈时能否排成序列3, 2,5, 6, 4, 1和1, 5, 4, 6, 2, 3，若能，写出进栈、退栈过程，若不能，简述理由。(用push (x)表示x进栈，pop(x)表示x退栈)30. 已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为 CEFDBHGA，画出该二叉树。31. 给定表(15, 11, 8, 20, 14, 13),试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非

36、平衡二叉排序树，将它 调整为平衡二叉排序树。(2)写出三种以顶点 A为起点的深度优先搜索顶点序列。33.用冒泡排序法对数据序列(49, 38, 65, 97, 76, 134, 27, 49)进行排序，写出排序过程。并说明冒泡排 序是否为稳定排序。四、算法设计题(本大题共2小题，每小题7分，共14分)34编写计算二叉树中叶子结点数目的算法。35开散列表的类型定义如下：typedef struct tag nodekeytype key;struct tag no de* next;*po in ter, no de;typedef pointer openhash n试写出开散列表上的查找算法。2040年40月自考数据结构导论参考答案2010年10月高等教育自学考试全国统一命题考试数据结构导论试题答案及评分参考