2015年4月全国自考数据结构导论考前密卷02142(含答案)

目录第一章概论 (1)第二章线性表 (7)第三章栈、队列和数组 (13)第四章树和二叉树 (17)第五章图 (22)第六章查找 (28)第七章排序 (33)第一章概论一、单选题1.数据的最小标识单位是（）A.数据项B.数据类型C.数据元素D.数据变量2.任意两个结点之间都没有邻接关系，组织形式松散，这种组织形式称为（）A.集合B.线性结构C.树形结构D.图结构3.与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）A.存储结构B.逻辑结构C.类型D.运算实现4.具有分支、层次特性，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接，这种组织形式称为（）A.集合B.线性结构C.树形结构D.图结构5.数据的逻辑结构分为四种，其中结构最复杂的是（）A.集合B.线性结构C.树形结构D.图结构6.“能正确地实现预定的功能，满足具体问题的需要”。

这种评价算法好坏的因素称为（）A.正确性B.易读性C.健壮性D.时空性7.计算n!（整数n≥0）的递归算法是:int Factorial（int n）{if（n==0）return1；else return n*Factorial（n-1）；}其时间复杂度为（）n）A.O（n）B.O（log2C.O（n c）D.O（n²）8.下面程序段的时间复杂度为（）for（int i=0；i＜n；i++）for（int j=0；j＜n；j++）A[i][j]=i×j；A.O（1）B.O（n）n） D.O（n²）C.O（log29.将长度为n的单链表链接在长度为m的单链表之后的算法时间复杂度为（）A.O（n）B.O（m）C.O（n+m）D.O（n×m）二、填空题10.数据结构是指一组相互之间存在一种或多种特定关系的数据的组织方式和它们在计算机内的________方式，以及定义在该组数据上的一组操作。

11.1976年瑞士计算机科学家Niklaus Wirth曾提出一个著名公式：程序=数据结构+________。

全国2011年1月自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.在顺序表中查找第i个元素，时间效率最高的算法的时间复杂度为( )A.O(1)B.O(n)C.O(log2n)D.O(n)2.树形结构中，度为0的结点称为( )A.树根B.叶子C.路径D.二叉树3.已知有向图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,V7 B.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.串中所含非空格字符的个数6.组成数据的基本单位是( )A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n；x=0；do{x=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.2iB.2iC.2i-1D.2i-110.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( ) A.p->next=p->next->next B.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的结果为( )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分)请在每小题的空格中填上正确答案。

第一张概论1.1 引言两项基本任务：数据表示，数据处理软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。

机外表示------逻辑结构------存储结构处理要求-----基本运算和运算-------算法1.2.1 数据，逻辑结构和运算数据：凡是能够被计算机存储，加工的对象通称为数据数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。

又称元素、顶点、结点、记录。

数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当作一个整体对待。

又称字段或域，是数据不可分割的最小标示单位。

1.2.2 数据的逻辑结构逻辑关系：是指数据元素之间的关联方式，又称“邻接关系”逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。

即数据的组织形式。

四种基本逻辑结构：1 集合：任何两个结点间没有逻辑关系，组织形式松散2 线性结构：结点按逻辑关系依次排列成一条“锁链”3 树形结构：具有分支，层次特性，形态像自然界中的树4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。

注意点:1.逻辑结构与数据元素本身的形式，内容无关。

2.逻辑结构与数据元素的相对位置无关3.逻辑结构与所含结点个数无关。

运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。

加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。

引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。

引用：查找，读取加工：插入，删除，更新同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。

假如X是S上的一些运算的集合，Y是X的一个子集，使得X中每一运算都可以规约为Y中的一个或多个运算，而Y中任何运算不可规约为别的运算，则称Y中运算（相对于X）为基本运算。

2015年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码02142)本试卷共4页，满分l00分，考试时间l50分钟。

考生答题注意事项：1．本卷所有试题必须在答题卡上作答。

答在试卷上无效，试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3．第二部分为非选择题。

必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

4．合理安排答题空间。

超出答题区域无效。

第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。

未涂、错涂或多涂均无分。

1．“能正确地实现预定的功能，满足具体问题的需要”。

这种评价算法好坏的因素称为A．正确性 B．易读性 C．健壮性 D．时空性2．有一程序片段：{i=0；s=0；while(s<=n){i++；s=s+i；}}，其时间复杂度是C3．在如题3图所示的数组A中链接存储了一个线性表，表头指针为A[0]．next，则该线性表中第一个数据元素的值是A. 60 B．50 C．78 D．404．在一个长度为n(n>1)的单链表上，设有头和尾两个指针，下列操作与链表长度有关的是A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表中第一个元素前插入一个新元素D．在单链表中最后一个元素后插入一个新元素5．某双向链表中的结点如题5图所示。

删除t所指结点的操作为D6．下列关于栈和队列的叙述中：Ⅰ栈和队列都是线性表；Ⅱ栈和队列都是顺序表；Ⅲ栈和队列都不能为空；Ⅳ栈和队列都能用于递归过程实现；Ⅴ栈的特点是先进后出、队列的特点是先进先出，其中正确的是A．Ⅰ和V B．Ⅰ、Ⅱ、V C．Ⅲ和V D．Ⅱ、Ⅳ、V7．二维数组A按行序优先顺序存储，每个数据元素占1个存储单元。

若数据元素A[1][1]的存储地址是420，A[3][3]的存储地址是446，则A[5][5]的存储地址是A．470 B. 471 C．472 D．4738．若对一棵含有199个结点的完全二叉树按自上而下、从左到右依次对结点编号，根结点的编号为l，则树中最后一个结点(即编号为l99)的双亲结点的编号为A．99 B．100 C．101 D．1989．对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时平均查找长度(ASL)为B10．在如题l0图所示的有向图中，从顶点l出发进行深度优先搜索可得到的结果序列是A．1423 B．1432 C．1342 D．124311．设森林F中有三棵树，其结点的个数分别为m1、m2、m3，则与F对应的二叉树根结点的右子树上的结点数是A．m l+m2 B．m2+m3 C．m l+m3 D．m l+m2+m312．假设通信电文使用的字符集为{a，b，e，d，e，f}，各字符在电文中出现的频率分别为{34，5，12，23，8，18}，利用构造Huffman树对每个字符进行编码，则其中编码长度最长的字符是A．a．b B．a，d C．b，e D．e，f13．元素的进栈次序为A，B，c，D，E，出栈的第一个元素为E，则第四个出栈的元素为 A．D B．C C．B D．A14．平均时间复杂度和在最坏情况下的时间复杂度均是0(Nlog2n)的排序算法是A．插入排序 B．快速排序C．选择排序D．堆排序15．在待排记录中其关键字序列基本有序的前提下，时间效率最高的排序方法是A．直接插入排序 B．快速排序C．选择排序 D．堆排序第二部分非选择题二、填空题(本大题共l3小题，每小题2分，共26分)请在答题卡上作答。

2015年4月18日全国自学考试试题及答案（7时4分）一、选择题1.设 i z +=21，i z +-=22，则=+2155z z 【D 】 A.-5 B.5 C.-10 D.102.函数)(z f 在点0z 处连续的充要条件是)(z f 在点0z 处 【C 】 A.可导 B. )(lim 0z f z z →存在 C. )()(lim 00z f z f z z =→ D.解析3.函数)(z f 在点0z 处解析的条件是)(z f 在点0z 的某个邻域内 【A 】 A.处处可导 B.连续 C. 只有点0z 处可导 D.不是处处可导4.幂级数()∑∞=03n nz 的收敛半径是 【 D 】A.1B.3C.∞D.315.函数z e z f =)(在点0=z 处的泰勒级数是 【 A 】A.∑∞=0!n nn z B.∑∞=++-012)!12()1(n n n n z C. ∑∞=++-011)1(n n n n z D. ∑∞=-02)!2()1(n nnn z 6.0=z 是函数zzz f sin )(=的 【 C 】 A.本性奇点 B.一级极点 C.可去奇点 D.以上都不正确7.若0z 是函数)(z f 的孤立奇点，则使10]),([Re -=c z z f s 的充分条件是：0z 是)(z f 的 （B ）A 可去奇点 B.本性奇点 C.解析点 D 一级极点8.t 0cos ω的傅氏变换为 【 C 】 A ．[])()(00ωωδωωδπ--+ B. [])()(00ωωδωωδπ-++j C.[])()(00ωωδωωδπ-++ D. [])()(00ωωδωωδπ--+j9.常数2的傅氏变换为 【 C 】10.函数z z f cos )(=在z 平面上 【D 】 A.连续未必可导 B.可导但不解析 C. 有奇点 D.处处解析11.已知函数z e z f =)(，z z g cos )(=在单连通区域G 内解析，C 为G 内的任意闭曲线，则⎰=+Czdz z e)cos ( 【D 】A.1B.2C. i π2D.012.设函数)(z f 在单连通区域G 内解析，C 为G 内的任意闭曲线，则()⎰=-=-1600)(z z dz z z z f【A 】A.!5)(205z if π B. )0(2)5(if π C.0 D. )(20z if π13.设i z 431+=，i z 432+-=，则=+2122z z 【 B 】 A.12 B.16 C.-16 D.-1214. .函数)(z f 在点0z 处连续，则 【 C 】 A. )(z f 在点0z 处可导 B. )(z f 在点0z 处可微 C. )()(lim 00z f z f z z =→ D. )(z f 在点0z 处解析15.函数),(),()(y x iv y x u z f +=在点000iy x z +=处解析的充要条件是 【 C 】A. ),(y x u ,),(y x v 在),(00y x 处可微B.在点0z 处，xvy u y v x u ∂∂-=∂∂∂∂=∂∂, C . ),(y x u ,),(y x v 在),(00y x 处可微，且xvy u y v x u ∂∂-=∂∂∂∂=∂∂, D. )(z f 在点0z 处解析16.函数z z f sin )(=在z 平面上 【 D 】A.连续未必可导B.可导但不解析C. 有奇点D.处处解析17.已知函数z z f sin )(=，z z g cos )(=在单连通区域G 内解析，C 为G 内的任意闭曲线，则⎰=+Cdz z z )cos (sin【B 】A. π2B.0C. i π2D.118.已知函数z e z f =)(，z z g sin )(=在单连通区域G 内解析，C 为G 内的任意闭曲线，则⎰=+Cz dz z e )sin ( 【A 】A.0B.1C. i π2D. π219.设)(z f 在区域G 内解析，C 为G 内任意一条正向简单闭曲线, 0z 是C 内的一点，则积分()=-⎰Cdz z z z f 3)( 【B 】A.3)(0z f i ''π B. 0 C.3)(20z f i ''π D. )(20z f i ''π 20.设函数)(z f 在z 平面上解析，则⎰=-=-100)(z z dz z z z f 【 B 】A.0B.)(20z if πC.)(0z fD.以上都不正确 A.2 B. )(2ωπδ C. )(4ωπδ D.)(221ωπδω+ 21. ate 的拉氏变换为 【A 】 A.a s -1 B. s 1 C. 22a s s + D. 22as a + 22.)(t δ 的拉氏变换为 【 B 】 A. s 1 B.1 C. t 1 D 22t s t + 23.⎰=1dz e z 【C 】A.1B.0C.1-eD.e -1 A.21-s B. s 1 C. 422+s D. 42+s s24.常数9的拉氏变换为 【A 】 A.s 9 B. js 9 C.)(9s πδ D.)(91s jsπδ+ 25.⎰=20cos πdz 【A 】A.1B.-1C.0D.2 26.幂级数∑∞=⎪⎭⎫ ⎝⎛03n nz 的收敛半径是【B 】A.1 B.3 C.∞ D.31 27.函数z z f sin )(=在点0=z 处的泰勒级数是 【B 】A.∑∞=0!n n n z B. ∑∞=++-012)!12()1(n n n n z C. ∑∞=++-011)1(n n n n z D. ∑∞=-02)!2()1(n nnn z28. i z =函数322)1(1)(+=z z z f 的 【D 】A.本性奇点B.一级极点C.二级极点 D 三级极点29.若0z 是函数)(z f 的孤立奇点，则使0]),([Re 0=z z f s 的充分条件是：0z 是)(z f 的【A 】 A 可去奇点 B.本性奇点 C.解析点 D 一级极点30.t 3sin 的傅氏变换为 【C 】 A ．[])3()3(--+ωδωδπ B. [])3()3(-++ωδωδπj C.[])3()3(-++ωδωδπ D. [])3()3(--+ωδωδπj31.常数3的傅氏变换为 【C 】 A.3 B. )(2ωπδ C. )(6ωπδ D.)(231ωπδω+ 32.t 2sin 的拉氏变换为 【C 】 33. 设i z 231+=，i z 232+-=，则=+2144z z 【B 】 A.12 B.16 C.-16 D.-1234.若函数)(z f 在0z 不连续，则 【C 】A. )()(lim 00z f z f z z =→ B. []0)()(lim 00=-→z f z f z zC. )()(lim 000z f z z f z =∆+→∆ D. []0)()(lim 00≠-→z f z f z z35. 函数)(z f 在点0z 处解析，则)(z f 在点0z 处 【C 】 A.连续未必可导 B.可导未必连续 C. 可导并且连续 D.仅连续36.函数z z f 2sin )(=在z 平面上 【D 】 A.连续未必可导 B.可导但不解析 C. 有奇点 D.处处解析 37. 幂级数∑∞=+0)12(n nzn 的收敛半径是 【A 】A.1B.2C.∞D.2138.函数)1ln()(z z f +=在点0=z 处的泰勒级数是 【C 】A.∑∞=0!n nn z B.∑∞=++-012)!12()1(n n n n z C. ∑∞=++-011)1(n n n n z D. ∑∞=-02)!2()1(n nnn z 39. 0=z 函数322)1(1)(+=z z z f 的 【C 】A.本性奇点B.一级极点C.二级极点 D 三级极点40.若0z 是函数)(z f 的孤立奇点，则使)()(lim ]),([Re 000z f z z z z f s z z -=→的充分条件是：0z 是)(z f 的 【D 】 A 可去奇点 B.本性奇点 C.解析点 D 一级极点 41.jate的傅氏变换为 【C 】A.1B.)(2a πδC.)(2a -ππδD. )(2a +ωπδ42.常数4的傅氏变换为 【C 】 A.4 B. )(2ωπδ C. )(8ωπδ D.)(241ωπδω+ 43.t 2cos 的拉氏变换为 【D 】 A.21-s B. s 1 C. 422+s D. 42+s s44. te 5的拉氏变换为 【A 】 A.51-s B. s 1 C. 252+s s D. 2552+s二、填空题 11. ,)1(1)(22-=z z z f 则1=z 是)(z f 的 二级 极点.2.设1)(2-=z z z f ，则=]1),([Re z f s 21.3. 级数nn z ∑∞=0)3(的收敛半径是314.函数)(z f 点0z 处的导数为1，则=--→)()(2)(2lim 000z z z f z f z z 2 .5设11)(-=z z f ，则=]1),([Re z f s 1 . 6. t 2sin 的傅氏变换为 [])2()2(--+ωδωδπj . 7.常数C 的拉氏变换为sC. 8.)(t u 是单位阶跃函数，则)(t u 的傅氏变换为)(1ωπδω+j . 9.3t 的拉氏变换为43s.10.=-⎰=dz i z z 1310 .11.在复数域内，断言1sin ≤z 是 错误 12.函数)(z f 点0z 处的导数为2，则=--→)(2)()(lim000z z z f z f z z 1 .13.=-⎰=dz z z 2310 .14 连续函数的和、差、积仍然是 连续 函数 15.zz z f 1cos)(5=,则0=z 是)(z f 的 本性奇点 . 16. 级数∑∞=0)4(n n z 的收敛半径为 4 。

2012年10月高等教育自学考试全国统一命题考试数据结构导论试题课程代码：02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。

错选、多选或未选均无分。

1.下面几种算法时间复杂度阶数中，值最大的是A.O(nlog2n)B.O(n2)C.O(n)D.O(2n)2.即使输入非法数据，算法也能适当地做出反应或进行处理，不会产生预料不到的运行结果，这种算法好坏的评价因素称为A.正确性B.易读性C.健壮性D.时空性3.设顺序表的长度为100，则在第40个元素之后插入一个元素所需移动元素的个数为A.40B.60C.61D.1004.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是A. head->next==headB. head->next==NULLC. head!=NULLD. head==NULL5.在链栈的运算中，不需要．．．判断栈是否为空的是A.出栈B.进栈C.取栈顶元素D.求链栈的元素个数6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是A.100B.108C.114D.1168.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为A.4B.5C.6D.无法确定9.m个叶结点的哈夫曼树中，其结点总数为A.mB.2m+1C.2mD.2m-110.二叉树的中序遍历序列中，结点P排在结点Q之前的条件是A.在二叉树中P在Q的左边B.在二叉树中P在Q的右边C.在二叉树中P是Q的祖先D.在二叉树中P是Q的子孙11.有10个顶点的无向完全图的边数是A.11B.45C.55D.9012.在带权有向图中求两个结点之间的最短路径可以采用的算法是A.迪杰斯特拉（Dijkstra）算法B.克鲁斯卡尔（Kruskal）算法C.普里姆（Prim）算法D.深度优先搜索（DFS）算法13.二分查找（Binary Search）算法的时间复杂度是A.O（n2）B.O（nlog2n）C.O（n）D.O（log2n）14.在一棵初始时为空的二叉树中，依次插入键值序列50，72，43，85，75，20，38，45，65，60，构造对应的二叉排序树以后，查找元素60要进行的比较次数是A.2B.3C.4D.515.快速排序属于A.插入排序B.交换排序C.选择排序D.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

数据结构导论模拟试题一、考试题型及分值分布：1、单项选择题(本大题共15小题，每小题2分，共30分)2、填空题(本大题共13小题，每小题2分，共26分)3、应用题(本大题共5小题，每小题6分，共30分)4、算法设计题(本大题共2小题，每小题7分，共14分)二、单项选择题和填空题样题参考（一）单项选择题1. 在二维数组中，每个数组元素同时处于（）个向量中。

A. 0B. 1C. 2D. n2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B 整体连接到A的末尾，其时间复杂度应为（）。

A. O(1)B. O(m)C. O(n)D. O(m+n)3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。

A. front == rearB. front != NULLC. rear != NULLD. front == NULL4. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。

A. 3,2,1B. 2,1,3C. 3,1,2D. 1,3,25. 图的广度优先搜索类似于树的（）遍历。

A. 先根B. 中根C. 后根D. 层次6. 下面程序段的时间复杂度为( )。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A. O(m2)B. O(n2)C. O(m*n)D. O(m+n)7. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。

A. 求子串B. 模式匹配C. 串替换D. 串连接8 利用双向链表作线性表的存储结构的优点是（）。

A. 便于单向进行插入和删除的操作B. 便于双向进行插入和删除的操作C. 节省空间D. 便于销毁结构释放空间9. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。

若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行( )操作。

2015年4月全国自考数据库及其应用考前密卷02120(含答案)一、单项选择题（本大题共20小题，每小题2分，共40分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

第1题在报表中添加日期和时间，可以通过设置其“控件源”属性为日期或时间的计算表达式来显示日期与时间，该控件位置应该安排在报表的（）节区里。

A. 主体B. 页面页眉C. 报表页脚D. 以上均可【正确答案】 D【你的答案】本题分数2分第2题 DBAS指的是（）A. 数据库系统B. 数据库应用系统C. 数据库管理系统D. 数据库服务系统【正确答案】 B【你的答案】本题分数2分第3题 Access数据库的设计一般由5个步骤组成，对以下步骤的排序正确的是（）a.确定数据库中的表b.确定表中的字段c.确定主关键字d.分析建立数据库的目的e.确定表之间的关系（）A. dabecB. dabceC. cdabeD. cdaeb【正确答案】 B【你的答案】本题分数2分第4题数据库系统的核心是（）A. 数据库B. 操作系统C. 数据库管理系统D. 文件【正确答案】 C【你的答案】本题分数2分第5题下列关于复制表论述中错误的是（）A. 可以复制表结构和数据B. 只能复制表结构C. 复制后的副本不能与已有的表重名D. 可以把表中数据以追加方式复制到已有的表中【正确答案】 B【你的答案】本题分数2分第6题下面关于自动编号数据类型叙述错误的是（）A. 每次向表中添加新记录时，Access会自动插入唯一顺序号B. 自动编号数据类型一旦被指定，就会永远地与记录连接在一起C. 如果删除了表中含有自动编号字段的一个记录后，Access并不会对自动编号型字段进行重新编号D. 被删除的自动编号型字段的值会被重新使用【正确答案】 D【你的答案】本题分数2分第7题用于查看报表的页面数据输出形态的视图方式是（）A. “设计”视图B. “版面预览”视图C. “打印预览”视图D. 以上都不对【正确答案】 C【你的答案】本题分数2分第8题A. 纵栏式报表B. 表格式报表C. 图表报表D. 标签报表【正确答案】 B【你的答案】本题分数2分第9题要等价的实现宏中的操作，可以在模块对象中编写（）代码。

自考02142《数据结构导论》历年真题集电子书目录1. 目录 (2)2. 历年真题 (3)2.1 02142数据结构导论200410 (3)2.2 02142数据结构导论200510 (7)2.3 02142数据结构导论200610 (10)2.4 02142数据结构导论200701 (14)2.5 02142数据结构导论200710 (17)2.6 02142数据结构导论200801 (19)2.7 02142数据结构导论200810 (22)2.8 02142数据结构导论200901 (25)2.9 02142数据结构导论200910 (28)2.10 02142数据结构导论201001 (30)2.11 02142数据结构导论201010 (34)2.12 02142数据结构导论201101 (37)2.13 02142数据结构导论201110 (40)3. 相关课程 (42)1. 目录历年真题()02142数据结构导论200410()02142数据结构导论200510()02142数据结构导论200610()02142数据结构导论200701()02142数据结构导论200710()02142数据结构导论200801()02142数据结构导论200810()02142数据结构导论200901()02142数据结构导论200910()02142数据结构导论201001()02142数据结构导论201010()02142数据结构导论201101()02142数据结构导论201110()相关课程()2. 历年真题2.1 02142数据结构导论2004102004年下半年高等教育自学考试全国统一命题考试数据结构导论试题课程代码2142一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1.要将现实生活中的数据转化为计算机所能表示的形式，其转化过程依次为（）A.逻辑结构、存储结构、机外表示B.存储结构、逻辑结构、机外表示C.机外表示、逻辑结构、存储结构D.机外表示、存储结构、逻辑结构2.若评价算法的时间复杂性，比较对数阶量级与线性阶量级，通常（）A.对数阶量级复杂性大于线性阶量级B.对数阶量级复杂性小于线性阶量级C.对数阶量级复杂性等于线性阶量级D.两者之间无法比较3.下列关于线性表的基本操作中，属于加工型的操作是（）A.初始化、求表长度、插入操作B.初始化、插入、删除操作C.求表长度、读元素、定位操作D.定位、插入、删除操作4.在一个单链表中，若p所指结点不是最后结点，s指向已生成的新结点，则在p 之后插入s所指结点的正确操作是（）A.s–>next=p–>next; p–>next=B.p–>next=s–>next; s–>next=C.s–>next=p; p–>next=D.s–>next=p–>next; p=5.若有三个字符的字符串序列执行入栈操作，则其所有可能的输出排列共有（）A.3种B.4种C.5种D.6种6.C语言对数组元素的存放方式通常采用（）A.按行为主的存储结构B.按列为主的存储结构C.按行或列为主的存储结构D.具体存储结构无法确定7.根据定义，树的叶子结点其度数（）A.必大于0B.必等于0C.必等于1D.必等于28.二叉树若采用二叉链表结构表示，则对于n个结点的二叉树一定有（）A.2n个指针域其中n个指针为NULLB.2n个指针域其中n+1个指针为NULLC.2n-1个指针域其中n个指针为NULLD.2n-1个指针域其中n+1个指针为NULL9.在一个无向图中，所有顶点的度数之和等于边数的（）A.1倍B.2倍C.3倍D.4倍10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（）A.先根遍历B.中根遍历C.后根遍历D.层次遍历11.采用顺序查找法，若在表头设置岗哨，则正确的查找方式通常为（）A.从第0个元素开始往后查找该数据元素B.从第1个元素开始往后查找该数据元素C.从第n个元素开始往前查找该数据元素D.从第n+1个元素开始往前查找该数据元素12.下列查找中，效率最高的查找方法是（）A.顺序查找B.折半查找C.索引顺序查找D.分块查找13.索引文件通常由索引表和主文件两部分构成，其中（）A.索引表和主文件均必须是有序文件B.索引表和主文件均可以是无序文件C.索引表必须是有序文件D.主文件必须是有序文件14.直接插入排序算法，其时间复杂性为（）A.O(1)B.O(n)C.O(nlog2n)D.O(n2)15.下列排序方法中，属于稳定的排序方法是（）A.直接插入排序法B.快速排序法C.冒泡排序法D.堆排序法二、填空题（本大题共13小题，每小题2分，共26分）请在每小题的空格中填上正确答案。

自考02142《数据结构导论》真题及（2022.4）自考02142《数据结构导论》真题及答案解析（2022.4）1.[单选题] 下列几种时间复杂度中，阶数最小的是（）A.O(log2n)B.O(n)C.O(n2)D.O(1)2.[单选题] 栈和队列的共同特点是（）A.都是线性表B.先进先出C.后进先出D.只能插入操作3.[单选题] 假设一个10x 10的上三角矩阵A按照列优先顺序压缩在一维数组B中，则B数组的大小应为（）A.50B.55C.100D.1014.[单选题] 一个栈的入栈序列是a，b，c，d，e，则栈可能的输出序列是（）A.edcabC.abcdeD.dceab5.[单选题] 假定一个顺序存储的循环队列的队头和队尾指针分别为f 和r，则判断队空的条件为（）A.f==NULLB.f==rC.r+1==fD.f+1== r6.[单选题] 如果结点A有2个兄弟结点，结点B为A的双亲，则结点B的度为（）A.2B.3C.4D.57.[单选题] 二叉树的中序遍历中，结点P排在结点Q之前的条件是在二叉树中（）A.P在Q的左边B.P在Q的右边C.P是Q的祖先D.P是Q的子孙8.[单选题] 二又树的第k层的结点数最多为（）B.2k+1C.2k-1D.2k+19.[单选题] A是7X4的二维数组，按行优先方式顺序存储元素A[0][0]的存储地址为1000，若每个元素占2个字节，则元素A[3][3]的存储地址为（）A.1026B.1028C.1030D.103210.[单选题] 在表长为n的顺序表上做删除运算，其平均时间复杂度为（）A.O(1)B.O(n)C.O(nlog2n)D.O(n/2)11.[单选题] 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为（）A.eB.2eC.n2-e12.[单选题] 设顺序表的长度为n，则插入算法的平均移动次数约为（）A.nB.n/2C.n-1D.(n-1)/213.[单选题] 设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134)，则用二分查找算法查找关键字90需要比较的关键字个数为（）A.1B.2C.3D.414.[单选题] 以下排序方法中，稳定的是（）A.直接插入排序和快速排序B.快速排序和冒泡排序C.直接选择排序和冒泡排序D.冒泡排序和直接插入排序15.[单选题] 对n个记录的文件进行快速排序，所需要的辅助存储空间的空间复杂度为（）A.O(1)B.O(n)C.O(1og2n)D.O(n2)16.[填空题] 1976年瑞士计算机科学家Niklaus Wirth 曾提出一个著名公式：程序=数据结构+____。

高等教育自学考试数据结构导论真题2014年4月(总分100, 做题时间150分钟)课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1.下列几种算法时间复杂度中，最小的是SSS_SINGLE_SELA O(log2n)B O(n)C O(n2)D O(1)该题您未回答:х该问题分值: 2答案:A2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有SSS_SINGLE_SELA 索引存储方式和树形存储方式B 线性存储方式和散列存储方式C 线性存储方式和索引存储方式D 索引存储方式和散列存储方式该题您未回答:х该问题分值: 2答案:D3.表长为n的顺序表中做删除运算的平均时间复杂度为SSS_SINGLE_SELA O(1)B O(log2n)C O(n)D O(n2)该题您未回答:х该问题分值: 2答案:C4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为SSS_SINGLE_SELA O(1)B O(log2n)C O(n)D O(n2)该题您未回答:х该问题分值: 2答案:C5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为SSS_SINGLE_SELA DB CC BD A该题您未回答:х该问题分值: 2答案:C6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为SSS_SINGLE_SELA front==rearB front!=NULLC rear!==NULLD front==NULL该题您未回答:х该问题分值: 2答案:A7.深度为5的二叉树，结点个数最多为SSS_SINGLE_SELA 31个B 32个C 63个D 64个该题您未回答:х该问题分值: 2答案:A8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为SSS_SINGLE_SELA 1B 3C 4D 5该题您未回答:х该问题分值: 2答案:B9.将题9图所示的一棵树转换为二叉树，结点C是SSS_SINGLE_SELA A的左孩子B A的右孩子C B的右孩子D E的右孩子该题您未回答:х该问题分值: 2答案:D10.n为图的顶点个数，e为图中弧的数目，则图的拓扑排序算法的时间复杂度为SSS_SINGLE_SELA O(n)B O(e)C O(n-e)D O(n+e)该题您未回答:х该问题分值: 2答案:D11.无向图的邻接矩阵是SSS_SINGLE_SELA 对角矩阵B 稀疏矩阵C 上三角矩阵D 对称矩阵该题您未回答:х该问题分值: 2答案:D12.在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为SSS_SINGLE_SELA 50B 51C 100D 101该题您未回答:х该问题分值: 2答案:A13.构造散列函数的方法很多，常用的构造方法有SSS_SINGLE_SELA 数字分析法、除留余数法、平方取中法B 线性探测法、二次探测法、除留余数法C 线性探测法、除留余数法、链地址法D 线性探测法、二次探测法、链地址法该题您未回答:х该问题分值: 2答案:D14.就平均时间性能而言，快速排序方法最佳，其时间复杂度为SSS_SINGLE_SELA O(n)B O(nlog2n)C O(n2)D O(1og2n)该题您未回答:х该问题分值: 2答案:B15.下述算法中，不稳定的排序算法是SSS_SINGLE_SELA 直接插入排序B 冒泡排序C 堆排序D 归并排序该题您未回答:х该问题分值: 2答案:C二、填空题(本大题共13小题，每小题2分，共26分)16.数据的基本单位是_______。

绝密★考试结束前全国2017年4月高等教育自学考试数据结构导论试题课程代码:02142 请考生按规定用笔将所有试题的答案涂㊁写在答题纸上㊂选择题部分注意事项: 1.答题前,考生务必将自己的考试课程名称㊁姓名㊁准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上㊂ 2.每小题选出答案后,用2B 铅笔把答题纸上对应题目的答案标号涂黑㊂如需改动,用橡皮擦干净后,再选涂其他答案标号㊂不能答在试题卷上㊂一㊁单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将 答题纸”的相应代码涂黑㊂错涂㊁多涂或未涂均无分㊂1.任意两个结点之间都没有邻接关系,组织形式松散,这种组织形式称为A.集合B.线性结构C.树形结构D.图结构2.表示数据元素之间的关联方式通常采用的存储方式是A.顺序存储方式和索引存储方式 B.链式存储方式和散列存储方式C.顺序存储方式和链式存储方式D.链式存储方式和索引存储方式3.下面几种算法时间复杂度阶数中,最小的是A.O(log 2n)B.O(n)C.O(n 2)D.O(2n )4.双向循环链表中,在指针p 所指结点的后面插入一个新结点*t,正确的语句为A.t->prior =p;t->next =p->next;p->next->prior =t;p->next =t;B.t->prior =p;t->next =p->next;p->next =t;C.t->prior =p;p->next->prior =t;t->next =p->next;p->next =t;D.p->next->prior =t;p->next =t;5.栈的修改原则是A.先进先出B.后进先出C.栈空则进D.栈满则出6.设有一顺序队列SQ,已知尾指针rear<队列的最大长度-1,则数据x进行入队列操作的语句为A.SQ.front=SQ.front+1;B.SQ.front=SQ.rear+1;C.SQ.front=SQ.front+1;SQ.data[SQ.front]=x;D.SQ.rear=SQ.rear+1;SQ.data[SQ.rear]=x;7.一个数组的第一个元素的存储地址是100,每个元素占2存储单元,则第5个元素的存储地址是A.105B.108C.115D.1188.树中叶子的度是A.0B.1C.2D.39.将一棵有n个结点的完全二叉树按层编号,若编号i所对应的结点为A,且i>1,则A的双亲的编号为A.iB.i/2C.D.10.含有100个结点的二叉树采用二叉链表存储时,空指针域NULL的个数是A.99个B.100个C.101个D.200个11.一个具有n个顶点的有向完全图的弧数为A.n(n-1)/2B.n(n-1)C.n2/2D.n212.图的深度优先搜索遍历类似于树的A.先序遍历B.中序遍历C.后序遍历D.层次遍历13.静态查找表指对查找表只进行两项操作,即A.插入和删除一个数据元素B.查找表中某一元素和插入一个数据元素C.读取表中 特定”数据元素和删除一个数据元素D.查找表中某一元素和读取表中 特定”数据元素14.若在线性表中采用二分查找法查找元素,该线性表应该A.元素按值有序,且采用链式存储结构B.元素按值无序,且采用链式存储结构C.元素按值有序,且采用顺序存储结构D.元素按值无序,且采用顺序存储结构15.下列排序方法中不稳定∙∙∙的是A.冒泡排序B.二路归并C.堆排序D.直接插入排序非选择题部分注意事项: 用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上㊂二㊁填空题(本大题共13小题,每小题2分,共26分)16.从宏观上看,数据㊁数据元素和　▲　反映了数据组织的三个层次㊂17.线性表㊁栈和队列中的元素具有相同的逻辑结构,即　▲　㊂18.一个算法的时空性是指该算法的时间性能和　▲　㊂19.为了便于运算的实现,在单链表的第一个结点之前增设一个类型相同的结点,称之为　▲　㊂20.假设一个8阶的上三角矩阵A按照列优先顺序压缩存储在一维数组B中,则B数组的大小应为　▲　㊂21.在栈中,允许进行插入和删除操作的一端称为　▲　㊂22.即使输入非法数据,算法也能适当地做出反应或进行处理,不会产生预料不到的运行结果,这种评价算法好坏的因素称为　▲　㊂23.设栈S的初始状态为空,若元素a,b,c,d依次进栈,得到的出栈序列是c,d,b,a,则栈S的容量至少是　▲　㊂24.若一棵完全二叉树有14个结点,则它的深度为　▲　㊂25.树的双亲表示法由一个一维数组构成,数组的每个分量包含　▲　和双亲域两个域㊂26.如果包含n个顶点的连通图G的一个子图G′的边数大于n-1,则G′中一定有　▲　㊂27.在含有9个元素的有序表(2,4,12,18,23,37,49,51,68)中二分查找关键字(关键字即为数据元素的值)为37的元素时,所需进行的比较次数为　▲　次㊂28.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为　▲　排序法㊂三㊁应用题(本大题共5小题,每小题6分,共30分)29.设A㊁B㊁C㊁D㊁E五个元素依次进栈(进栈后可立即出栈),问能否得到下列序列: (1)A,B,C,D,E; (2)A,C,E,B,D若能得到,则给出该序列的操作过程(用push(A)表示A进栈,pop(A)表示A出栈);若不能,则说明理由㊂30.已知一棵二叉树的先序遍历结果为ABDCEF,中序遍历结果为DBAECF,试画出这棵二叉树,并写出这棵二叉树的后序遍历序列㊂31.画出题31图所示森林经转换后所对应的二叉树㊂题31图32.已知如题32图所示的无向带权图,请从结点A出发,用普里姆(Prim)算法求其最小生成树,并画出过程示意图㊂题32图33.将一组键值{83,69,41,22,15,33,8,76}应用二路归并排序算法从小到大排序,试写出各趟排序的结果㊂四㊁算法设计题(本大题共2小题,每小题7分,共14分)34.设计一个算法实现以下功能:在整型数组A[n]中查找值为k的元素,若找到,则输出其位置i(0≤i≤n-1),否则输出-1作为标志㊂35.已知二叉链表的类型定义如下:typedef struct btnode{ DataType data;struct btnode*lchild,*rchild;}*BinTree;利用二叉树遍历的递归算法,设计求二叉树的高度的算法Height(BinTree bt)㊂。

全国自学考试数据结构导论试题及答案4套第一套试题一、选择题（每题4分，共40分）1. 下列哪个数据结构是一种非线性结构？A. 数组B. 栈C. 队列D. 树2. 下列哪种算法不适用于解决排序问题？A. 冒泡排序B. 快速排序C. 深度优先搜索D. 归并排序3. 在数据结构中，堆的底层实现通常采用哪种数据结构？A. 数组B. 栈C. 链表D. 队列4. 下列哪个选项是描述图结构的准确说法？A. 图结构是一种线性结构B. 图结构由节点和指向节点的边构成C. 图结构不能存储数据D. 图结构不支持插入和删除操作5. 下列哪个排序算法具有最坏时间复杂度为O(nlogn)？A. 冒泡排序B. 插入排序C. 选择排序D. 希尔排序二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

2. 图的两个顶点之间的路径长度是指连接这两个顶点所需的____数。

3. 链表是一种____结构。

4. 快速排序算法的核心思想是____。

5. 栈和队列都属于线性结构，其主要区别在于____操作的限制。

三、简答题（每题10分，共30分）1. 请简要描述栈的特点以及栈的应用场景。

2. 请简要介绍图的基本概念，并说明图的应用领域。

3. 请解释递归算法的原理，并给出一个使用递归算法解决问题的例子。

四、编程题（共30分）请使用任意编程语言实现一个简单的栈数据结构，并编写测试代码进行验证。

第二套试题一、选择题（每题4分，共40分）1. 在二叉搜索树中，中序遍历的结果是____。

A. 升序排列B. 降序排列C. 随机排序D. 不确定的排序2. 在哈希表结构中，解决冲突问题的常用方法是____。

A. 线性探测B. 链地址法C. 开放地址法D. 扩容法3. AVL树是一种____。

A. 二叉搜索树B. 哈希表C. B树D. 红黑树4. 以下哪个算法不是用于解决查找问题？A. 二分查找B. 深度优先搜索C. 广度优先搜索D. 哈希查找5. 以下哪个数据结构不支持随机访问元素？A. 数组B. 栈C. 链表D. 哈希表二、填空题（每题4分，共40分）1. 在二叉树中，每个节点最多有____个子节点。

绝密 考试结束前全国2015年10月高等教育自学考试数据结构导论试题课程代码:02142请考生按规定用笔将所有试题的答案涂㊁写在答题纸上㊂选择题部分注意事项:1.答题前,考生务必将自己的考试课程名称㊁姓名㊁准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上㊂2.每小题选出答案后,用2B 铅笔把答题纸上对应题目的答案标号涂黑㊂如需改动,用橡皮擦干净后,再选涂其他答案标号㊂不能答在试题卷上㊂一㊁单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将 答题纸 的相应代码涂黑㊂错涂㊁多涂或未涂均无分㊂1.能正确地实现预定的功能,满足具体问题的需要 ㊂这种评价算法好坏的因素称为A.正确性B .易读性C .健壮性 D.时空性2.有一程序片段:{i =0;s =0;w h i l e (s <=n ){i ++;s =s +i ;}},其时间复杂度是A.O (n)B .O (2n)C .O (n1/2) D.O (1)题3图3.在如题3图所示的数组A 中链接存储了一个线性表,表头指针为A [0].n e x t ,则该线性表中第一个数据元素的值是A.60B .50C .78D.404.在一个长度为n (n >1)的单链表上,设有头和尾两个指针,以下操作与链表长度有关的是A.删除单链表中的第一个元素题5图B .删除单链表中的最后一个元素C .在单链表中第一个元素前插入一个新元素D.在单链表中最后一个元素后插入一个新元素5.某双向链表中的结点如题5图所示,删除t 所指结点的操作为A.t ->p r i o r ->p r i o r =t ->n e x t ;t ->n e x t ->p r i o r =t ->p r i o r;B .t ->p r i o r ->p r i o r =t ->p r i o r ;t ->n e x t ->n e x t =t ->n e x t;C .t ->p r i o r ->n e x t =t ->p r i o r ;t ->n e x t ->p r i o r =t ->n e x t;D.t ->p r i o r ->n e x t =t ->n e x t ;t ->n e x t ->p r i o r =t ->p r i o r;6.下列关于栈和队列的叙述中:Ⅰ栈和队列都是线性表;Ⅱ栈和队列都是顺序表;Ⅲ栈和队列都不能为空;Ⅳ栈和队列都能用于递归过程实现;Ⅴ栈的特点是先进后出㊁队列的特点是先进先出,其中正确的是A.Ⅰ和ⅤB.Ⅰ㊁Ⅱ㊁ⅤC.Ⅲ和ⅤD.Ⅱ㊁Ⅳ㊁Ⅴ7.二维数组A按行序优先顺序存储,每个数据元素占1个存储单元㊂若数据元素A[1][1]的存储地址是420,A[3][3]的存储地址是446,则A[5][5]的存储地址是A.470B.471C.472D.4738.若对一棵含有199个结点的完全二叉树按自上而下㊁从左到右依次对结点编号,根结点的编号为1,则树中最后一个结点(即编号为199)的双亲结点的编号为A.99B.100C.101D.1989.对长度为15的有序顺序表进行二分查找,在各记录的查找概率均相等的情况下,查找成功时平均查找长度(A S L)为A.3915B.4915C.5115D.551510.在如题10图所示的有向图中,从顶点1出发进行深度优先搜索可得到的结果序列是题10图A.1423B.1432C.1342D.124311.设森林F中有三棵树,其结点的个数分别为m1㊁m2㊁m3,则与F对应的二叉树根结点的右子树上的结点数是A.m1+m2B.m2+m3C.m1+m3D.m1+m2+m312.假设通信电文使用的字符集为{a,b,c,d,e,f},各字符在电文中出现的频率分别为{34,5, 12,23,8,18},利用构造H u f f m a n树对每个字符进行编码,则其中编码长度最长的字符是A.a,bB.a,dC.b,eD.e,f13.元素的进栈次序为A,B,C,D,E,出栈的第一个元素为E,则第四个出栈的元素为A.DB.CC.BD.A14.平均时间复杂度和在最坏情况下的时间复杂度均是O(n l o g2n)的排序算法是A.插入排序B.快速排序C.选择排序D.堆排序15.在待排记录中其关键字序列基本有序的前提下,时间效率最高的排序方法是A.直接插入排序B.快速排序C.选择排序D.堆排序非选择题部分注意事项:用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上㊂二㊁填空题(本大题共13小题,每小题2分,共26分)16.数据的存储结构又称为物理结构,可分为顺序存储㊁链式存储㊁以及散列存储等几种方式㊂17.一般说来,在每个逻辑结构上都定义了一组基本运算,通常这些运算包括:建立㊁㊁读取㊁插入和删除等㊂18.某带有头结点的单链表的头指针为h e a d,则判断该单链表为非空的条件是㊂19.数组Q[n]表示一个循环队列,设f的值为队列中第一个元素的位置,r的值为队列中实际队尾的位置加1,并假定队列中最多只有n-1个元素,则计算队列中元素个数的公式是㊂20.稀疏矩阵可以采用方法进行压缩存储㊂21.含有n个结点的完全二叉树中度为1的结点的个数最多为㊂22.高度(深度)为k的二叉树中结点个数最多是2k-1㊁最少是㊂23.对于有n个顶点的无向图,所有生成树中都有且仅有条边㊂24.设散列表的地址空间为0到12,散列函数为h(k)=km o d13,用线性探测法解决冲突㊂现要将关键字序列{10,100,32,45,58,128,3,29,200,400,0}映射到该散列表中,则其中关键字值58的地址为㊂25.假设有K个关键字互为同义词,若用线性探测法把这K个关键字用散列函数H将它们存入长度为m的散列表中(Kɤm),则至少共需进行次探测㊂26.在关键字序列{07,12,15,18,27,32,41,92}中用二分法查找和给定值92相等的关键字,在查找过程中依次和给定值92比较的关键字是㊂27.影响排序算法时间复杂度的两个因素是关键字的次数和记录的移动次数㊂28.在直接插入㊁直接选择和冒泡这三种排序方法中,不稳定的排序方法是㊂三㊁应用题(本大题共5小题,每小题6分,共30分)29.设栈S和队列Q的初始状态均为空,7个元素a b c d e f g依次进入栈S㊂若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是b d c f e a g㊂现要求:(1)栈S的容量至少是多少?(2)在(1)的情况下,画出该栈中元素最多时的一个状态示意图㊂30.某二叉树结点的中序遍历序列为A B C D E F G ㊁后序遍历序列为B D C A F G E ,现要求:(1)画出该二叉树;(2)写出该二叉树的先序遍历序列;(3)该二叉树所对应的森林包括几棵树?题32图31.假设有一棵完全二叉树按自上而下㊁从左到右的层序组织包含A ㊁B ㊁C ㊁D ㊁E ㊁F ㊁G 这7个结点,分别给出其邻接矩阵和邻接表㊂32.要求给出至少2个不同的关键字序列,均能构造出如题32图所示的二叉排序树;对此你会得出什么结论?33.采用快速排序方法对关键字序列{265,301,751,129,937,863,742,694,076,438}进行升序排序,写出其每趟排序结束后的关键字序列㊂四㊁算法设计题(本大题共2小题,每小题7分,共14分)34.写出复制一棵二叉树的算法㊂设原二叉树根结点由指针r o o t 指向,复制得到的二叉树根结点由指针n e w r o o t 指向,函数头为:v o i dC o p y T r e e (B T N o d e*r o o t ,B T N o d e*n e w r o o t ),二叉树的存储结构为:t y pe d ef s t r u c t b t n o d e {D a t a T y pe d a t a ;s t r u c t b t n o d e*l c h i l d ,*r c h i l d ;}B T N o d e ,*B T r e e;35.已知带头结点的单链表L 是按数据域值非递减有序链接的,试写一算法将值为x 的结点插入表L 中,使得L 仍然是有序链接的㊂。

自考02142《数据结构导论》真题及（2022.10）自考02142《数据结构导论》真题及答案解析（2022.10）1.[单选题] 设输入序列为ABC，输出为ABC,则经过的栈操作为（）。

A.push，pop，push，push，pop，popB.push，push，pop，pop，push，popC.push，push，push，pop，pop，popD.push，pop，push，pop，push，pop2.[单选题] 设有一循环队列CQ，队列的长度为maxsize，则该循环队列满的条件为（）。

A.（CQ.rear+1)%maxsize==CQ.frontB.CQ.rear==CQ.frontC.（CQ.rear+1)%maxsize==CQ.rearD.CQ.rear==NULL3.[单选题] 树的相关术语中，兄弟指（）。

A.祖先相同的结点B.根相同的结点C.度数相同的结点D.父结点相同的结点4.[单选题] 执行进栈操作，在元素X进栈前需要进行的操作是（）。

A.判断栈是否满，若栈未满，top值加1B.判断栈是否空，若栈未空，top值加1C.判断栈是否满，若栈未满，top值减1D.判断栈是否空，若栈未空，top值减15.[单选题] 森林有两种遍历方法，分别是（）。

A.先序遍历森林和中序遍历森林B.先序遍历森林和后序遍历森林C.中序遍历森林和层次遍历森林D.后序遍历森林和层次遍历森林6.[单选题] 有向图中某顶点v的入度为2，出度为3，则该顶点的度为（）。

A.3B.4C.5D.67.[单选题] 无向图的邻接矩阵为（）。

A.对角矩阵B.对称矩阵C.稀疏矩阵D.一般矩阵8.[单选题] 对升序表进行二分查找，用给定值key与处在中间位置的数据元素T.elem[mid]的键值T.elem[mid].key进行比较，当key 32.[问答题] 给定数据序列{46，25，78，62，12，80}，试按元素在序列中的次序将它们依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。