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

1、全国2012年1月数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)1 .结点按逻辑关系依次排列形成一条锁链”的数据结构是()A.集合 B.线性结构C.树形结构D.图状结构2 .下面算法程序段的时间复杂度为()for ( int i=0; i<m; i+)for ( int j=0; j<n; j+)a ijl =i*j；A. O(m2)B. O(n2)C. O(mn)D. O(m+n)3 .线性结构是()A.具有n (n>0个表元素的有穷序列B.具有n (n>Q个字符的有穷序列C.具有n (n>Q个结点的有穷序列D.具有

2、n (n>0个数据项的有穷序列4 .单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是()A. O(1)B. 0( . 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阶上三角

3、矩阵压缩存储时需存储的元素个数为9 .深度为k (k>l)的二叉树，结点数最多有 (10 .具有12个结点的二叉树的二叉链表存储结构中,()A.11B.56C.100D.101)A.2k 个B.(2k-1)个C.2k-1 个D.(2k+1)个空链域 NULL的个数为()A. 11B.13 C. 23 D.2511.具有n个顶点的无向图的边数最多为()A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)0 1 012.三个顶点V1,V2,V3的图的邻接矩阵为)A. 0 B. 1 C. 2 D.0 0 1 ，该图中顶点V3的入度为(0 1 0313 .顺序存储的表格中有 6000

4、0个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且 每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为()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,S2,S3,S4,S5,S6依次进入顺序栈S,如果6个元素的退栈顺序为S2,S3,S4,S6,S5,S1 ,则顺序栈的容量至少为21 .稀疏矩阵一般采用的压缩存储方法是22.在一棵树中,结点没有双亲。1,23 .一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所有结点编号。设根结点编号为若编号为i的结点有父结点，那么其父结点的

6、编号为24 .二叉树的二叉链表存储结构中判断指针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图的邻接矩阵和每个顶点的入度与出度。

7、32 .二叉排序树的各结点的值依次为2028,请在题32图中标出各结点的值。33 .用冒泡排序法对数据序列（55, 38, 65, 97, 76, 138, 27, 49）进行排序，写出排序过程中的各趟结果。四、算法设计题（本大题共2小题，每小题7分，共14分）34 .设线性表A = （a1， a2,sm）, B= （b1，b2,b）,试写一个按下列规则合并A, B为线性表C的算法,使得C= (a1，b1,，abm ,bm+1, ,b)当 m<n时;或者C= (a1, b1,，na,bn ,an+1,m) 当 m>n 时。线性表A,B和C均以带头结点的单链表作为存储结构，且 C表利

8、用A表和B表中的结点空间构成。（注意：单链表的长度值 m和n均未显式存储。）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的初始状态为空，元素 e1, e2, e3, e4, e5和e6依次通过栈S,元素退栈后即进入队

9、列 Q, 若6个元素的出队序列是 e2, e4, e3, e6, e5, e1,则栈S的容量至少为()A.2B.3C.4D.62 .设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为()A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈3 .下列程序段的时间复杂度为()i=0; s=0;while (s<n)i+ ; s=s+i; A.O (而)B.O(log2n)C.O(n)D.O(n2)4 .设A是nxn的对称矩阵，将A的对角线及对角线上方的元素Aj(1 w i,j w n,i w j)以列优先顺序存放在一维数组元素B 1至B n(n+1)/2中，则元素

10、 Aj(iwj)在B中的位置为()A.i(i-l)/2+jB.j(j-l)/2+i C.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,daffha, gc,bbC. gc,ax,eb,cd,bbff da,haD

11、. ax,bb,cd,daffeb, gc,ha7 .不稳定的排序方法是()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, 210 .直接插入排序的时间复杂度是( )A.O (n2)B.O (nlog2n) C.O (n)D.O (l

12、og2n)11 .稀疏矩B是指()A.元素少的矩阵B.有少量零元素的矩阵C.有少量非零元素的矩阵D.行数、列数很少的矩阵12 .深度为 k (k>1)的二叉树，结点数最多有()A.2k B.2k-1C.2k-1D.2k-1-113 .由带权为9, 2, 5, 7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为()A.23 B.37 C.44D.4614 .有n个顶点的有向完全图的弧数为( )A.n2 B.2n C.n(n-1)D.2n (n+1)15 .图的深度优先搜索类似于二叉树的()A.先根遍历B.中根遍历C.后根遍历 D.层次遍历二、填空题(本大题共13小题，每小题2分，共26

13、分)16 .下列程序段的时间复杂度为 。for(i=1;i<=n;i+)for(j=1;j<=n;j+) x+;17 .数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是 。18 .在表长为n的顺序表上做删除运算，平均要移动的结点个数为 。19 .在带有头结点的单循环链表head中，指针p所指结点为尾结点的条件是 。20 .队列又称为 的线性表。21 .顺序栈被定义为结构类型，含有两个域：data和top,则对栈*sq进行初始化的操作是 。22 .对于任何一棵二叉树 T,如果其终端结点数为n0,度为2的结点数为n2,则n2=。23 .一棵具有n个结点的二叉树，采用二叉链表存储

14、，则二叉链表中指向孩子结点的指针有 个。24 .若连通图G的顶点个数为n,则图G的生成树的边数为 。25 .一个具有n个顶点的无向图的边数最多为 。26 .中根遍历二叉排序树所得到的结点访问序列是键值的 序列。27 .冒泡排序的平均时间复杂度为 。28 .将序列60, 20, 23, 68, 94, 70, 73建成堆，则只需把 20与 互相交换。三、应用题(本大题共5小题，每小题6分，共30分)29 .如题29图所示，在栈的输入端元素的输入顺序为A, B, C, D,进栈过程中可以退栈，写出在栈的输出端以A开头和以B开头的所有输出序列。题29图题30图题31图题32图30 .一棵二叉树如题3

15、0图所示，写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。31 .将题31图所示的一棵二叉树转换成森林。32 .对于有向无环图：(1)叙述求拓扑排序算法的基本步骤；(2)对于题32图，写出它的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中

16、，试编写算法实现将顺序存储结构转换为二叉链表存储结构，其中根结点由tree指向。35 .试写出冒泡排序算法。全国2011年1月数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）1 .在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为（）A.O（1）B.O（而）C.O（log2n）D.O（n）2 .树形结构中，度为 0的结点称为（）A.树根 B.叶子C.路彳至D.二叉树3 .已知有向图 G=（V,E）,其中 V=V 1,V2,V3,V4,V5,V6,V7 , E=<V 1,V2> , <V1,V3> , <V1,V4

17、> , <V 2,V5> , <V3,V5>,<V3,V6>, <V4,V6>, <V5,V7>, 76丫7>,则图 G 的拓扑序列是（）A.V 1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7 C.V 1,V3,V4,V5,V2,V 6,V7D.V 1,V2,V5,V3,V4,V6,V74 .有关图中路径的定义，表述正确的是 （）A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5 .串的长度是

18、指（）A.串中所含不同字母的个数 B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6 .组成数据的基本单位是（）A.数据项B.数据类型C.数据元素D.数据变量7 .程序段 i=n ; x=0 ;dox=x+5*i ; i-; while （i>0）;的时间复杂度为（ ）A.O （1） B.O （n） C.O （n2）D.O（n3）8 .与串的逻辑结构不回啊 数据结构是（） A.线性表 B.栈C.队列D.树9 .二叉树的第i （i>1）层上所拥有的结点个数最多为（）A.2i B.2i C.2i-1D.2i-110 .设单链表中指针p指向结点A,若要删除A的

19、直接后继，则所需修改指针的操作为（）A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p11 .下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（）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. BCD

20、EF" C. BCDEFG " D. BCDEFEF "13 .在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并且A的左孩子的平衡因子为-1 ,右孩子的平衡因子为 0,则使其平衡的调整方法为（）A.LL 型 B.LR 型 C.RL 型 D.RR 型14 .如果结点A有3个兄弟结点，而且 B为A的双亲，则B的度为（）A.1B.3C.4D.515 .数据表A中每个元素距其最终位置较近，则最省时间的排序算法是（）A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题（本大题共13小题，每小题2分，共26分）16 .下列程序段的时间复杂度为 。i

21、=1 ;while (i<n) i=i*2 ;个元素。17 .向一个长度为n的顺序表中第i （1WiWn）个元素之前插入一个元素时，需向后移动18 .在循环双链表中，删除最后一个结点，其算法的时间复杂度为。19 .队列的插入操作在队列的部分进行。20 .一个栈的输入序列是1, 2, 3,，n,输出序列的第一个元素是 n,则第i个输出元素为 。21 .一个10阶对称矩阵A,采用行优先顺序压缩存储下三角，ao0为第一个元素，其存储地址为1,每个元素占有 1 个存储地址空间，则a85 的地址为。22 .设字符串S=" ID AM DAD STUDENT "（其中口表示空格字

22、符），则S的长度为。23 .在树形结构中，没有后继的结点是结点。24 .一棵深度为n（n>1）的满二叉树中共有 个结点。25 .在无向图中，如果从顶点v到顶点v'有路径，则称 v和v'是。26 .无向完全图G 采用 存储结构较省空间。27 .在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是 。28 .快速排序最好情况下的时间复杂度为。三、应用题（本大题共5 小题，每小题6分，共 30 分 ）29 .稀疏矩阵A 如下，写出矩阵A 的三元组表及矩阵A 的转置矩阵的三元组表。030001000000 5-1 0 0 0 0 00

23、0040 -30 0 0 0 030 .一棵二叉树的前根遍历序列为ABCDEFG ，中根遍历序列为CBDAEGF ，试构造出该二叉树。31 .下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。1 12 51018912 82594102 432 .给定表（80， 90， 50， 70， 75， 60， 40， 100） ，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。33 .试写出一组键值（46， 58， 15， 45， 90， 18， 10， 62）应用直接插入排序算法从小到大排序后各趟的结果。四、算法设计题（本大题共2 小

24、题，每小题7 分，共 14 分 ）34 .试分别写出二叉树的先根遍历和中根遍历的递归算法。35 .试编写以单链表为存储结构实现直接选择排序的算法。2011年1月全国自考数据结构导论参考答案2011年1月高等教育自学考试全国统,一命题考试数据结构导论试题答案及评分参考（课程代码 02142）一、单项选择题（本大题共15小跋,每小题Z分.共30分）1. AZ-B3. A4, A5. BG. C7, B8. D生 C1G, A11.C12.1)'13, B14tCIt. B二、填空50；奉大题共13小益，每小建2分.共26分）16. CKh>&n)ni-118.0(1)19.队

25、尾（或尾部）20. n-i4* 121+42ZZ. 1421叶于f卷羯24.25.连逋的28.邻接矩阵2工散列查找2&. （Xnlog! n）二、底对黑；本人黑共5小段,耳小息6分，& 3!分） 29.稀疏用阵A.的三,元蛆我第下：（？分）11334._3. J2612rV31574一 3稀疏短降A的转置矩阵访三元组表却下分）1tjV1515213231544611数据结构导论试鼠举案及评分翡.名第】页（共？页30.解：（左子树3分，石子树3分）答30图31.解，连通网为:献小生成树为;数据结构导论试题答案及评分参考第2页（共3页）32 一答能图(注2左子期3分1右子树三分)M

26、3.解;初始序列146, 5 fhi5*43矢1,10,62第趣上4£户幻5T必需(j,1E,1O,MC1分)一二一山5,4彘5町.45 .蛇社gJ(M2(1分)第二的J15H55&5叼国。,】£门黑62(1分)第四趟：门 5,4516,58*90,却 ,1362(1分)东直.口5,1孔席次;洱铀。,鹿(1分)第六越；10,必,46.5机9口，鹿第七糖工16.1殖1%，品4/箫工2 .就(1步)四，算法谀计遢(本大翅共2小题,每小题¥分.共14分)力中 拓n "三川卢d-.W >*口4斛i无醉HL囚度户丹西:Void preorSE“hit

27、i"邛trr) ifirJNUUJ visit(r>p pruorderCr >lchild)» pteorfler r- >rcliilcl)；)(3 分),根追加递归算法Vcid orcfcrCrjittptrr)< ifCrl-NULL) i.nordcr(i-> I child) visit(r ；inordertr-C>rchjltD j )«仍3友好void U nke dLisi_Se1 Mt_SoTt (Li nkTI_ k t & L) 单链.表上的玄拄逸择排序克旅 (fottp Ljp >nEX

28、t->n总、Hp=p>n”t)tl 分)( q=pAnuxtjKNqAdata*Cl 分)"=乌福二世一 Aucxt打=rAn；Kt)/7在q后面寻找元素值最小的辅点 if(r>nexi - >data<xj (1 £ x= r> nesct-* > data ；r ；(1 分)if(s! =q)找到了值比q>das更小的结点=->n«t (p-AuE3tt=sAiwxt”一>nrtxi=q；Cl 分)t - q- >rKj*t«q->nexi.-"p -> nest

29、 >next； (1 分p>next-Augxil j/交换 q 和 s>riKt 的个结点(1 分)f" /JUnkedList_SelectScrt数娼结构导论试题答案及评分参考第3页(共3页)2010年10月数据结构导论试题课程代码：02142、单项选择题（本大题共15小题，每小题2分，共30分）1 下列描述中正确的是（）A. 数据元素是数据的最小单位B. 数据结构是具有结构的数据对象C. 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D. 算法和程序原则上没有区别，在讨论数据结构时两者是通用的2归并排序的时间复杂度是（）AO（n2）B.O（nlo

30、g2n）C.O（n）D.O（log2n）3二分查找的时间复杂度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）4顺序存储的表中有90000 个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为（ ）A 25000 B.30000 C.45000D.900005 .散列文件是一种（ ）A .顺序文件B.索引文件 C.链接文件D.计算寻址文件6 .两个矩阵 A : mxn, B: nXp 相乘，其时间复杂度为 （ ）A. O（n） B.O（mnp） C.O（n2） D.O （mp）7 .常用于函

31、数调用的数据结构是（ ）A.栈B.队列C.链表 D.数组8 .二维数组 A n m以列优先顺序存储，数组 A中每个元素占用1个字节，A 1 1为首元素，其地 址为 0,则元素 A i j的地址为（）A. （i-1） x m+（j-1）B.（j-1） Xn+（i-1）C.（j-1）Xn+I 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，

32、5）D.（2， 21， 19， 37， 5）11数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（）A.索引存储方法B.顺序存储方法C.链式存储方法D.散列存储方法12在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）A.直接前趋B.直接后继C.开始结点D.终端结点13在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）A O（ 1）B.O（ log2n）C.O（ n）D.O（ n2）14在链队列中执行入队操作，（）A.需判别队是否空B.需判别队是否满C.限制在链表头p进行D.限制在链表尾p进行15

33、 一整数序列26， 59， 77， 31， 51， 11， 19， 42， 以二路归并排序从小到大排序，第一阶段的归并结果为（）A.31 ，51，11，42，26，77，59，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的顺序表中删除

34、第i个元素（iwiwn）时，需向前移动 个元素。19在单链表中，插入一个新结点需修改个指针。20在队列结构中，允许插入的一端称为。21稀疏矩阵采用的压缩存储方法是。22向一个栈顶指针为top 的链栈中插入一个新结点*p 时，应执行p->next=top 和 操作。23有m 个叶结点的哈夫曼树所具有的结点数为。24 .在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号 为1。若编号为i的结点有右孩子，那么其右孩子的编号为 。25 .在一棵树中， 结点没有前驱结点。26 . 一个具有n个顶点的有向完全图的弧数是 。27 . n个顶点的无向图 G用邻接

35、矩阵A n n存储，其中第i列的所有元素之和等于顶点 Vi的。28 .选择排序的平均时间复杂度为 。三、应用题（本大题共5小题，每小题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、元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树， 画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它 调整为平衡二叉排序树。32 .如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点 A为起点的深度优先搜索顶点序列。33 .用冒泡排序法对数据序列（49, 38, 65, 97, 76, 134, 27, 49）进行排序，写出排序过程。并说明冒泡排 序是否为稳定排序。四、算法设计题（本大题共2小题，每小题7分，共14分）34 .编写计算二叉树中叶子结点数目的算法。35 .开散列表的类型定义如下：typedef struct tagnodekeytype key;struct tagnode*next;*pointer,node;typedef pointer openhash n;试写出开散列表上的查找算法。2010年10月自考数据结构导论参考答案201