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

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

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

3、1019 .深度为k（k>l）的二叉树，结点数最多有（）A.2k个B.（2k-1）个C.2k-1个D.（2k+1）个10 .具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为（）A.11B.13C.23D.2511.具有n个顶点的无向图的边数最多为（)A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1)301012.三个顶点V1,V2,V3的图的邻接矩阵为)A. 0B. 1 C. 2 D. 3001,该图中顶点V3的入度为（01013 .顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不

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

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

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

7、,38,65,97,76,138,27,49）进行排序，写出排序过程中的各趟结果。四、算法设计题（本大题共2小题，每小题7分，共14分）34 .设线性表A=（a1，32,am）,B=（b1，b2,，劫，试写一个按下列规则合并A,B为线性表C的算法，使得C=（a1，b1,，abm,bm+1,b）当m<n时；或者C=（a1,b，na,bn,an+1,，am）当m>n时。线性表A,B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值m和n均未显式存储。）35 .二叉树的二叉链表类型定义如下：typedefStructbtnodedataty

8、pedata;Structbtnode*lchild,*rchild;bitreptr;写出后根遍历根指针为t的二叉树的递归算法（voidpoStorder（bitreptr*t）。全国2011年10月数据结构导论试题课程彳弋码:02142一、单项选择题(本大题共15小题，每小题2分，共30分)1 .设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S,元素退栈后即进入队列Q,若6个元素的出队序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少为()A.2B.3C.4D.62 .设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为()A.线性表

9、的顺序存储结构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(1wi,jwn,iwj)以列优先顺序存放在一维数组元素B1至Bn(n+1)/2中，则元素Aj(iwj)在B中的位置为()A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-15 .在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是()A.G中有弧<V

10、i,Vj>B.G中有一条从Vi到Vj的路径C.G中没有弧<Vi,Vj>D.G中有一条从Vj到Vi的路径6 .下列序列中，由第一趟快速排序可得到的序列(排序的关键字类型是字符串)是()A.da,ax,eb,de,bbffha,gcB.cd,eb,ax,daffha,gc,bbC.gc,ax,eb,cd,bbffda,haD.ax,bb,cd,daffeb,gc,ha7 .不稳定的排序方法是()A.直接插入排序B.冒泡排序C.堆排序D.二路归并排序8 .设散列表表长m=14,散列函数为h(k)=k%11,表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是(

11、)012345678910111211538618439 .若元素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(log2n)11 .稀疏矩B是指()A.元素少的矩阵B.有少量零元素的矩阵C.有少量非零元素的矩阵D.行数、列数很少的矩阵12 .深度为k(k>1)的二叉树，结点数最多有()A.2kB.2k-1C.2k-1D.2k-1-113 .由带权为9,2,5,7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为()14 .有n个顶点的有

12、向完全图的弧数为()A.n2B.2nC.n(n-1)D.2n(n+1)15.图的深度优先搜索类似于二叉树的(20.队列又称为的线性表。21.顺序栈被定义为结构类型，含有两个域:data和top,则对栈*sq进行初始化的操作是22 .对于任何一棵二叉树 T,如果其终端结点数为n0,度为2的结点数为n2,则n2=23 .一棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有个。24 .若连通图G的顶点个数为n,则图G的生成树的边数为25 .一个具有n个顶点的无向图的边数最多为26 .中根遍历二叉排序树所得到的结点访问序列是键值的序列。27 .冒泡排序的平均时间复杂度为28 .

13、将序列60, 20, 23, 68, 94, 70, 73建成堆，则只需把三、应用题(本大题共5小题，每小题6分，共30分)20与互相交换。29 .如题29图所示，在栈的输入端元素的输入顺序为A, B以A开头和以B开头的所有输出序列。C, D,进栈过程中可以退栈，写出在栈的输出端ab( n题30图题31图输入期题29图题32图30.一棵二叉树如题30图所示,写出该二叉树的先根遍历序列、中根遍历序列和后根遍历序列。31 .将题31图所示的一棵二叉树转换成森林。32 .对于有向无环图:(1)叙述求拓扑排序算法的基本步骤;(2)对于题32图，写出它的4个不同的拓扑排序序列。33 .判别以下序列是否为

14、堆。如果不是，则把它调整为堆。(1) (100, 86, 48, 73, 35, 39, 42, 57, 66, 21); (2)(12, 70, 33, 65, 24, 5648, 92, 86, 33)。)A.先根遍历B.中根遍历C.后根遍历D.层次遍历二、填空题(本大题共13小题，每小题2分，共26分)16 .下列程序段的时间复杂度为for(i=1;i<=n;i+)for(j=1;j<=n;j+)x+;17 .数据结构中结点按逻辑关系依次排列形成一条“锁链”的结构是18 .在表长为n的顺序表上做删除运算，平均要移动的结点个数为19 .在带有头结点的单循环链表head中，指针p

15、所指结点为尾结点的条件是7四、算法设计题(本大题共2小题，每小题7分，共14分)A 1至A n中，试编写算法实现将顺34 .n个结点的完全二叉树按结点编号将值顺序存放在一维数组元素页眉内容序存储结构转换为二叉链表存储结构，其中根结点由tree指向。35 .试写出冒泡排序算法。课程代码：02142()A.O(1) B.O(.n)C.O(log2n)全国2011年1月数据结构导论试题一、单项选择题（本大题共15小题，每小题2分，共30分）1 .在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为D.O（n）2 .树形结构中，度为0的结点称为（）A.树根B.叶子C.路彳至D.二叉树3 .已知有

16、向图G=（V,E）,其中V=V1,V2,V3,V4,V5,V6,V7,E=<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,则图G的拓扑序列是（）A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74 .有关图中路径的定义，表述正确的是（）A.路径是顶点和相邻顶点偶对构成的

17、边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5 .串的长度是指（）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.

18、2iB.2iC.2i-1D.2i-110 .设单链表中指针p指向结点A,若要删除A的直接后继，则所需修改指针的操作为（）A.p->next=p->next->nextB.p=p->nextC.p=p->next->nextD.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

19、的结果为（）A."BCQR"B.BCDEF"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 .下列

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

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

22、CDEFG，中根遍历序列为CBDAEGF，试构造出该二叉树。31 .下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。1125101891282594102432 .给定表（80，90，50，70，75，60，40，100），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。33 .试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。四、算法设计题（本大题共2小题，每小题7分，共14分）34 .试分别写出二叉树的先根遍历和中根遍历的递归算法。页眉内容35 .试编写以单链表为

23、存储结构实现直接选择排序的算法。2011年1月全国自考数据结构导论参考答案20H年1月高等教育自学考试全国统一命题考试数据结构导论试题答案及评分参考（课程代码02142）5H 应A 15, B】电0 2L42 2d 密-散列查找一、单项选择题（本大题共】5小跋,每小题2分.共30分）LA2.BRAd.A«.C7.BR.D&.C1LC1111-13,E34,C二、填空驰；本大题共13小题.每小屉2分，共26分）16.J7,ni119.队尾（或尾都）现n-iHl经.1421叶子（签端）E工建通的2乳旬1按期降28,（Xnk岬h）三、我用慰；率文惠共5小题,悠小匙£分，受

24、分）的.Mi轼疏靖年A.的三元组我如下：、分JiJV123113153274匚V451一31一稀荀走降A的痔置矩阵的二元组表加下:4分）tjV131-32132JO1546|1_L.J数据结构导论拭鼠善案及评分妻名第1页（共？页）#页眉内容133Q*解1（左子树3分，6子捌m分）誓如图3L解:连通网为:最小生成树为;数据结构等论试题答篥及评分蠢考第2页（共3页）32（注:左于树3分，右子豺彳分）33,解:初始序列上46列正第一趣46,5出/$"3需。，1810,62（1分）第二趟；L1246,581羽.30,18-0,62（1分）第二趟15,45,46忑8，9心理.10,62（1分）

25、血四趟；RI51451d6,犯9。3和.孙62（1分）第五趟上15,1845,46,5瓦901门。，62（1分）鬼六越：145,46,5£9。二”2索七柳工口。,15.18,45,4668,62,9门门分）四承法设计遁(本大题共2小题，每小题7分洪14分1力4上山EFT*'f.-WT244鼾：兀欣;sa."曲口开胃：Voidprccrdrtbitreptrr)if(r!NUUJvisit(r>)prerirderCr>lchild匕preor«4er(r->rcliild)：；Q分)中根遍历递归算法丁V<?idortr<bit

26、reptrr)if(rlNULL)inordcr(i一二"Ichild)1visit(r);inorderCr>rchild)j)"分)35.群voidLinkedLisi_S«Ject_Sort(Liak*dUst&L)单链表上的直按选择俳序算法fortp=L?p'Auer->nmxtfp=pAnu工。(1分)q=p-Anc如xhq>datw；CJ分)foHj"=q,j?=qir>n0t；r=rAncx»在q后面守找元素值最小的结点if(r2>nex<->data-<x)(1分)

27、(工三r2>next->><lata；s=r；(1分)iKs!-q)找到值比R更小的结点s->n«t(p->next-sjS>n?xt=q?(1分)t=q->ncxt*0-riext=p->nw->nextj(1分)p>nexL>nextL“交换q和L>nKt两个结辰Cl分)/for/I.JnkdList_SelectSort数据结构导论试题答案及评分叁考第m页（共3页）2010年10月数据结构导论试题课程代码：02142一、单项选择题（本大题共15小题，每小题2分，共30分）1 下列描述中正确的是（）A.

28、数据元素是数据的最小单位B.数据结构是具有结构的数据对象C. 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D. 算法和程序原则上没有区别，在讨论数据结构时两者是通用的2归并排序的时间复杂度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）3二分查找的时间复杂度是（）AO（n2）B.O（nlog2n）C.O（n）D.O（log2n）4 顺序存储的表中有90000个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为（）A25000B.30000C.45000D.900005 .散列文

29、件是一种（）A.顺序文件B.索引文件C.链接文件D.计算寻址文件6 .两个矩阵A:mxn,B:nXp相乘，其时间复杂度为（）A.O（n）B.O（mnp）C.O（n2）D.O（mp）7 .常用于函数调用的数据结构是（）A.栈B.队列C.链表D.数组8 .二维数组Anm以列优先顺序存储，数组A中每个元素占用1个字节，A11为首元素，其地址为0,则元素Aij的地址为（）A.（i-1）xm+（j-1）B.（j-1）Xn+（i-1）C.（j-1）Xn+ID.jxn+i9 .图的广度优先搜索使用的数据结构是（）A.队列B.树C.栈D.集合10序列（21,19,37,5,2）经冒泡排序法由小到大排序，在第一

30、次执行交换后所得结果为（）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.链式存储方法D.散列存储方法12在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的（）A.直接前趋B.直接后继C.开始结点D.终端结点13在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（）AO（1）B.O（log2n）C.O（n）D.O（n2）14在链队列中执行

31、入队操作，（）A.需判别队是否空B.需判别队是否满C.限制在链表头p进行D.限制在链表尾p进行15一整数序列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数据的存储结构被分为顺序存储结构、散列存储结构

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

33、完全图的弧数是。27 .n个顶点的无向图G用邻接矩阵Ann存储，其中第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）,试按元素在

34、表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。32 .如题32图所示无向图，（1）写出其邻接矩阵；（2）写出三种以顶点A为起点的深度优先搜索顶点序列。33 .用冒泡排序法对数据序列（49,38,65,97,76,134,27,49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。四、算法设计题（本大题共2小题，每小题7分，共14分）34 .编写计算二叉树中叶子结点数目的算法。35 .开散列表的类型定义如下：typedefstructtagnodekeytypekey;structtagnode*next;*pointer,node;typedefpointeropenhashn;试写出开散列表上的查找算法。15页眉内容2010年10月自考数据结构导论