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

1、、单项选择题（本大题共15小题，每小题2分，共30分）1.结点按逻辑关系依次排列形成一条锁链”的数据结构是）A.集合B.线性结构C.树形结构D.图状结2下面算法程序段的时间复杂度为for ( int i=0; im; i+)for ( int j=0; jn 时。线性表A，B和C均以带头结点的单链表作为存储结构，且C表利用A表和B表中的结点空间构成。（注意：单链表的长度值 m和n均未显式存储。）35. 二叉树的二叉链表类型定义如下:typedef struct btnode datatype data;struct btnode *lchild,*rchild; bitreptr;写出后根遍历

2、根指针为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的容量至少为（）A.2B.3C.4D.62设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为（）A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈3下列程序段的时间复杂度为（）i=0 ； s=0;

3、while （ sn）i+ ； s=s+i; A.O（ n ）B.O（log2n）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.j（j-l）/2+i-1D.i（i-l）/2+j-15在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）A.G中有弧B.G中有一条从Vi到Vj的路径C.G中没有弧D.G中有一条从Vj到Vi的路径6下列序

4、列中，由第一趟快速排序可得到的序列（排序的关键字类型是字符串）是（）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.不稳定的排序方法是(）A.直接插入排序B.冒泡排序C.堆排序D.二路归并排序8设散列表表长 m=14，散列函数为h （ k） =k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是（）0 12345678910 11 12 115386184A.3B.5C.8D.

5、99若元素1, 2, 3依次进栈，则退栈不可能出现的次序是（）A.3 , 2, 1B.2 , 1, 3C.3, 1 , 2D.1 , 3, 2C.O (n) D.O (log2n)10直接插入排序的时间复杂度是（ ）A.O （n2）B.O （nIog2n）11. 稀疏矩阵是指（）A元素少的矩阵B有少量零元素的矩阵C有少量非零元素的矩阵D行数、列数很少的矩阵12深度为k （ k 1 ）的二叉树，结点数最多有（）A2kB2k-1C2k-1D2k-1-1()A23 B37C4413. 由带权为9, 2, 5, 7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为D46.214. 有n个顶点的有向完

6、全图的弧数为（ ）An B2 n Cn（n-1）D2 n （n +1）15. 图的深度优先搜索类似于二叉树的（）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所指结点为尾结点的条件是 20. 队列又称为的线性表。21. 顺序栈被定义为结构类型，含有两个域：data和to

7、p，则对栈*sq进行初始化的操作是 22. 对于任何一棵二叉树 T,如果其终端结点数为n0,度为2的结点数为氐，则=。23. 棵具有n个结点的二叉树，采用二叉链表存储，则二叉链表中指向孩子结点的指针有个。24. 若连通图G的顶点个数为n,则图G的生成树的边数为 。25. 个具有n个顶点的无向图的边数最多为 。26. 中根遍历二叉排序树所得到的结点访问序列是键值的 序列。27. 冒泡排序的平均时间复杂度为 。20与互相交换。C，D，进栈过程中可以退栈,写出在栈的输出端28. 将序列60，20，23，68，94，70，73建成堆，则只需把三、使用题（本大题共5小题，每小题6分，共30分）29. 如

8、题29图所示，在栈的输入端元素的输入顺序为 以A开头和以B开头的所有输出序列。A BCDY .题29图题31图题30图题32图中根遍历序列和后根遍历序列。30. 棵二叉树如题30图所示，写出该二叉树的先根遍历序列、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

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

10、中 V=V1,V2,V3,V4,V5,V6,V7， E=， ， ， ，, , , , , ，则图 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.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5. 串的长度是指 ()A.串中所含不同字母的个数B.串中所含字符的个数C串中所含不同字符的个数D.串中所含非空格字符的

11、个数6.组成数据的基本单位是() A. 数据项B.数据类型C.数据兀素D.数据变量7.程序段 i=n；x=0；dox=x+5*i ；i-；while (i0)；的时间复杂度为 ()A.O(1)B.O(n)2C.O( n2)D.O(n3)8.与串的逻辑结构不同的数据结构是 ()A. 线性表B.栈 C.队列D.树9二叉树的第i (i 1 )层上所拥有的结点个数最多为()A.2 B.2iC.2i-1D.2i-110. 设单链表中指针 p 指向结点 A ，若要删除 A 的直接后继，则所需修改指针的操作为 ()A.p-n ext=p-n ext- n extB.p=p-nextC.p=p-n ext-

12、n extD.p-n ext=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.” BCDEF C. BCDEFG ” D. ” BCDEFEF13. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A,并且A的左孩子的平衡因子为-1 ,右孩子的平衡因子为 0，则使其平衡

13、的调整方法为 ()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=1 ；while( i1)的满二叉树中共有个结点。25. 在无向图中，如果从顶点v到顶点v有路径，则称 v和v是。26. 无向完全图G采用存储结构较省空间。27. 在顺序查找、二分查找

14、、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是。28. 快速排序最好情况下的时间复杂度为 。三、使用题(本大题共5小题，每小题6分，共30分)29. 稀疏矩阵A如下，写出矩阵 A的三元组表及矩阵 A的转置矩阵的三元组表。0 3 0 0 0 1 0 0 0 0 0 05-1 0 0 0 00 0 0 0 4 0-30 000030. 棵二叉树的前根遍历序列为ABCDEFG，中根遍历序列为 CBDAEGF ,试构造出该二叉树。31. 下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。冋1125101珀8 9珀12 8凶凶259 史1 41o

15、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丄年月高等教佇自学考试全国统-命题考试数据结构导论试题答案及评分参考（课

16、程代码 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（nlfgv n三、应用題|卒丈惡共5小題，每小題6分二t创分）29*释硫矩阵久的三元爼褰如下M3分）iV1231&13153452&1-14-3稀疏毎阵A的转Smfr的二

17、元組农如下2心分!iiV13jjnr15”321323-15446 111数据结构导论试翳答案及博分鑫龙第页（共3灵）30解:31解，连通网为:就小生成桃为:（左子树3分，右子树3分）答30图数拯结构挣论试题答案及评分参考第2页（共3贡）(注,左子树3分，右子树豈分)33,解:初始序列；朗趴15沁疋2L_J- J.- 分分分分分 分第-MiB8,4&t90,18J0,62(1第二趙:11,46,5345.90,18.30,6290,18,10 f 62 d 第四 j；ri5t45,46758TS0j ,18,10,62(1第五趙江JR,45*4氣北，旳JO,能 jpmnrd电Mr Lchild

18、)；preorlet(T一； 笛分)中根遍历递归算法Void Ordt：r(bitTptrr) if (r!-NUIX) inorderlchiidhvisit(T)finorder(rchi Id);)next -nexhp=pncxt) (1 分 qpAiiexti忑壬耳一-datai(1 分)for(r=qtsnext jrrq 后面寻找兀素值用小的结点if(rnext - daca next data j sr j /1 分if(s* q)/找時了值比qda“萸小的结点snsxtp next= s-ncxt； sntxt=q；(1 t)qncxti qnext=pnextnexh(I

19、分)pnextnexttf/交换 q 和 Apriest 两个姑点(I分/f/Li nkedLi st_Sel ect-Sor t数据结构导沦试题答案憂诧分參禺第3页英3贞)2010年10月数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)1.下列描述中正确的是()A.数据元素是数据的最小单位B.数据结构是具有结构的数据对象C. 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D. 算法和程序原则上没有区别，在讨论数据结构时两者是通用的2归并排序的时间复杂度是( )A . O (n) B.O (nIog2n)C.O ( n) D.O (log

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

21、.数组&二维数组A :n m以列优先顺序存储，数组 A中每个元素占用1个字节，A : 1 1: 址为 0，则元素 A的地址为（）A. （i-1 ） Xm+（j-1） B.（j-1） rH（i-1） C.（j-1） ft+I为首元素，其地D.jn+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数据在计算机存储器内表

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

23、大排序，第一阶段的归并结果为A.31 ，51，11，42，26，77，59，19B.26，59， 31，77，11，51，19，42C.11， 19，二、填空题31，42，1626，（本大题共 13 小题，每小题59，51，772 分，D.26， 共 26 分 )11，19，31，51，59，77，42列程序段的时间复杂度为i=0； s=0；while ( snext=top和操作。23有m个叶结点的哈夫曼树所具有的结点数为24在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号。设根结点编号为1。若编号为i的结点有右孩子，那么其右孩子的编号为25在一棵树中， 结点没

24、有前驱结点。26一个具有n个顶点的有向完全图的弧数是27. n个顶点的无向图G用邻接矩阵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，后根遍历序列为 CEFDBH

25、GA，画出该二叉树。31. 给定表(15, 11, 8, 20, 14, 13)，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。2)写出三种以顶点A为起点的深度优先搜索顶点序列。33.用冒泡排序法对数据序列(49, 38, 65, 97, 76, 134, 27, 49)进行排序，写出排序过程。并说明冒泡 排序是否为稳定排序。四、算法设计题(本大题共2小题，每小题7分，共14分)34编写计算二叉树中叶子结点数目的算法。35开散列表的类型定义如下：typedef s

26、truct tag nodekeytype key;struct tag no de* next;*po in ter, no de;typedef pointer openhash n:试写出开散列表上的查找算法。2040年40月自考数据结构导论参考答案2010年10月高等教育自学考试全国统一命题考试数据结构导论试题答案及评分参考1.C2*B3.D4*C5.D6.B7. A8.B9. A10. A11.D12. BIX CU.D15. B一、单项选择題(本大题共15小題，每小题2分，共30分)(课程代码02142)二、填空題申大題共13小躍，每小题2分，共26分)16.0(巫玖链式存储结掏18. n-i 19.220.队尾2】.三元组表22, top=p23. 2m124. 2i+lE5+根26* nCn)幻.度28. OCn1)三、应用题本大题共5小题每小题6分，女30分)29申解能菲咸序列3,氛5,6,4,1过程：push( 1)( push(2) $ push(