02142数据结构导论份真题及答案.doc

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

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

1．下列说法正确的是（）A．数据是数据元素的基本单位B．数据元素是数据项中不可分割的最小标识单位C．数据可由若干个数据元素构成D．数据项可由若干个数据元素构成2．数据结构的基本任务是（）A．逻辑结构和存储结构的设计B．数据结构的运算实现C．数据结构的评价与选择D．数据结构的设计与实现3．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（）A．O（1）B．O（n）C．O（nlog2n）D．O(n2)4．顺序存储的线性表（a1,a2,…,a n）,在任一结点前插入一个新结点时所需移动结点的平均次数为（）A．n B．n/2C．n+1 D．(n+1)/25．下列树U′，经剪技运算DELETE（U′，x，2）后为（）6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（）A．2，14 B．2，15C．3，14 D．3，157．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一1堆数组B［1..15］中。

已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（）A．116 B．118C．120 D．1228．一个带权的无向连通图的最小生成树（）A．有一棵或多棵B．只有一棵C．一定有多棵D．可能不存在9．下列有关图遍历的说法中不正确的是（）A．连通图的深度优先搜索是一个递归过程B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征C．非连通图不能用深度优先搜索法D．图的遍历要求每一顶点仅被访问一次10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（）A．小于顺序表的平均查找长度B．大于顺序表的平均查找长度C．与顺序表的平均查找长度相同D．无法与顺序表的平均查找长度比较11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（）A．同义词之间发生冲突引起的B．非同义词之间发生冲突引起的C．同义词之间或非同义词之间发生冲突引起的D．散列表“溢出”引起的12．从外存设备的观点看，存取操作的基本单位是（）A．逻辑记录B．数据元素C．文件D．物理记录13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（）A．顺序文件B．索引文件C．顺序索引文件D．散列文件14．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（）A．（14，18，38，46，65，40，20，53，86，74）B．（14，38，18，46，65，20，40，53，86，74）C．（14，18，20，38，40，46，53，65，74，86）D．（14，86，20，38，40，46，53，65，74，18）15．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（）A．选择排序B．冒泡排序C．快速排序D．插入排序二、填空题（本大题共13小题，每空2分，共26分）请在每小题的空格中填上正确答案。

全国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分)请在每小题的空格中填上正确答案。

绝密★考试结束前
全国 2020 年10月高等教育自学考试
据结构导论试题
课程代码02142
1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。

2.答题前考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

选择题部分
注意事项:
每小题选出答案后用2B铅笔把答题纸上对应题目的答案标号涂黑。

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

不能答在试题卷上。

一、单项选择题本大题共15小题每小题2分共30分。

在每小题列出的备选项中只有一项
是最符合题目要求的请将其选出。

1.数据的最小标识单位是
A.数据项
B.数据类型
C.数据元素
D.数据变量
2.下面程序段的时间复杂度为
o r=0;<n;++)
o r=0;<n;++)
a=*
;
A O(1)
B O(n)
C O2n DO n2)
3.设带头结点的单向循环链表的头指针变量为h e a d,
则空循环链表的判定条件是
A h e a d==NU L L
B h e a d->n e x==NU L L
C h e a d->n e x==h e a d
D h e a d=NU L L
4.设输入序列为1、2、3、4、5、
则通过栈的作用后可以得到的输出序列为。

浙江省2001年10月自学考试数据结构导论试题课程代码：02142一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。

每小题1分，共14分)1.算法分析的目的是( )A.找出数据结构的合理性B.研究算法中的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性2.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。

A.单链表B.双链表C.顺序表D.循环链表3.下面关于线性表的叙述中，错误的为( )A.顺序表使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域4.带头结点的单链表head为空的判断条件是( )A. head=NILB. head↑.next=NILC. head↑.next=headD. head< >NIL5.队列通常采用两种存储结构是( )A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构6.按照二叉树的定义，具有3个结点的二叉树有( )A.3B.4C.5D.67.二叉树的结构如下图所示，其中序遍历的序列为( )A.a,b,d,g,c,e,f,hB.d,g,b,a,e,c,h,fC.g,d,b,e,h,f,c,aD.a,b,c,d,e,f,g,h8.深度为5的二叉树至多有( )个结点。

A.16B.32C.31D.109.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )A.nB.n+1C.n-1D.n+边数10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。

A.nB.n+1C.n-1D.n/211.静态查找表与动态查找表二者的根本差别在于( )A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。

自考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 曾提出一个著名公式：程序=数据结构+____。

全国2年1月数据结构导论试题课程代码：一、单项选择题(本大题共5小题，每小题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(m2)B. O(n2)C. O(mn)D. O(m+n)3.线性结构是()A.具有n（n≥0）个表元素的有穷序列 B.具有n（n≥0）个字符的有穷序列C.具有n（n≥0）个结点的有穷序列D.具有n（n≥0）个数据项的有穷序列4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是()A. O(1)n ) D. O(n)5.关于串的叙述，正确的是( ) A.串是含有一个或多个字符的有穷序列 B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串D.串是含有零个或多个字符的有穷序列6.栈的输入序列依次为，2，3，4，则不可能的出栈序列是()A.1243 B. 1432 C. 2134 D.43127.队列是( )A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.1019.深度为k（k≥ ）的二叉树，结点数最多有( )A.2k个 B.(2k -1)个 C.2k-1个 D.(2k+1)个10.具有12个结点的二叉树的二叉链表存储结构中，空链域L L的个数为( )A. 11 B.13 C. 23 D.2511.具有n个顶点的无向图的边数最多为( )A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1)12.三个顶点1,v2,v3的图的邻接矩阵为010001010⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦，该图中顶点v3的入度为( )A. 0 B. 1 C. 2D. 313.顺序存储的表格中有0000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。

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

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

1.数据的四种基本逻辑结构是指( )A.数组、链表、树、图形结构B.线性表、链表、栈队列、数组广义表C.线性结构、链表、树、图形结构D.集合、线性结构、树、图形结构2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )A.最大时间复杂性和最小时间复杂性B.最好时间复杂性和最坏时间复杂性C.部分时间复杂性和总体时间复杂性D.平均时间复杂性和最坏时间复杂性3.下列关于线性表的叙述中，不正确的是( )A.线性表是n个结点的有穷序列B.线性表可以为空表C.线性表的每一个结点有且仅有一个前趋和一个后继D.线性表结点间的逻辑关系是1:1的联系4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )A.p=p->nextB.p->next=p->nextC.p->next=p->next->nextD.p->next=p5.栈和队列( )A.共同之处在于二者都是先进先出的特殊的线性表B.共同之处在于二者都是先进后出的特殊的线性表C.共同之处在于二者都只允许在顶端执行删除操作D.没有共同之处6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )A.127B.142C.150D.1577.深度为k的二叉树至多有( )A.2k个结点B.2k-1个结点C.2k-1个结点D.2k-1-1个结点8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )A.ABCDEFB.ABECDFC.CDFBEAD.CBDAEF129.下面关于生成树的描述中，不正确的是( )A.生成树是树的一种表现形式B.生成树一定是连通的C.生成树一定不含有环D.若生成树顶点个数为n ，则其边数一定为n-110.图的邻接表如下所示，从顶点V 1出发采用深度优先搜索法遍历该图，则可能的顶点序列 是()A.V 1V 2V 3V 4V 5B.V 1V 2V 3V 5V 4C.V 1V 4V 3V 5V 2D.V 1V 3V 4V 5V 211.下列查找方法中，不属于动态的查找方法是( )A.二叉排序树法B.平衡树法C.散列法D.斐波那契查找法12.要解决散列引起的冲突问题，常采用的方法有( )A.数字分析法、平方取中法B.数字分析法、线性探测法C.二次探测法、平方取中法D.二次探测法、链地址法13.用于外存储器的数据组织结构散列文件，主要适用于( )A.顺序存取B.随机存取C.索引存取D.以上三种都可以14.堆排序属于一种选择排序，其时间复杂性为( )A.O(1)B.O(nlog 2n)C.O(n)D.O(n 2)15.下列排序方法中，属于不稳定的排序方法是( )A.直接插入排序法B.冒泡排序法C.基数排序法D.归并排序法二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

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

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

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

2．第一部分为选择题。

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

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

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

4．合理安排答题空间，超出答题区域无效。

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

请将其选出并将“答题卡”的相应代码涂黑。

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

1．下列算法的时间复杂度为B2．根据数据元素之间关系的不同特性，通常将数据结构分为四类基本结构，即A．集合、顺序结构、树形结构、图结构B．集合、线性结构、链式结构、图结构C．集合、线性结构、树形结构、图结构D．线性结构、顺序结构、链式结构、图结构3．在表长为101的顺序表中做删除运算，平均移动元素的次数为A．25 B．50 C．5l D．1004．在表长为n的顺序表中做插入运算的时间复杂度为A5．单链表与顺序表相比，其特点是A．运算算法实现简单 B．便于随机存取数据C．不需要预先分配存储空间 D．结点个数受到限制6．关于链栈的说法，正确的是A．链栈不用预先考虑容量的大小 B．链栈出栈时不需要判断栈空C．链栈进栈时需要判断栈满 D．链栈出栈时需要判断栈满7．循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为A．rear=rear+1 B．rear=(rear+1)％(m一1)C．rear=(rear+1)％m． D．rear=(rear+1)％(m十1)8．深度为k的二叉树，结点个数最多为B9．已知一棵度为k的树中有个度为l的结点，个度为2的结点，……，个度为k 的结点，则该树中的叶结点个数为B10．具有10个叶结点的哈夫曼树中度为l的结点数为A．0个 B．10个 C．19个 D．20个11．设图的顶点数为n，则采用邻接矩阵作为存储结构的图的深度优先搜索算法的时间复杂度为A．O(1) B．O(11) C．O(n2) D．O(1092n)12．n个顶点的无向图若采用邻接矩阵存储，则该矩阵的大小是A.n×(n—1)B.(n—1)×(n－1)C．(n+1)×(n+1) D．n×n13．已知一个有序表为(15，l9，30，33，49，50，65，88，93，126，164)，当二分查找值为l26的元素时，检索成功需进行的比较次数为A．1次 B．2次C．3次 D．4次14．直接选择排序算法的时间复杂度为D15．下述四种排序算法中，所需辅助存储量最多的是A．堆排序 B．快速排序C．归并排序 D．直接选择排序第二部分非选择题二、填空题(本大题共l3小题，每小题2分。

自考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}，试按元素在序列中的次序将它们依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。

自考02142《数据结构导论》真题及（2022.10）自考02142《数据结构导论》真题解析（2022.10）1.[单选题] 线性表若采用链表存储结构，内存中可用存储单位的地址A.必须是连续的B.有一部分必须是连续的C.一定是不连续的D.连续不连续都可以2.[单选题] 设有一个二维数组a[m][n]，假设a[0][0]存放位置为644，a[2][2]存放位置为676，每个元素占一个存储空间，则a[3][3]存放位置为A.678B.688C.692D.6963.[单选题] 先序遍历与中序遍历结果相同的二叉树A.根结点无左孩子B.根结点无右孩子C.所有结点只有左子树D.所有结点只有右子树4.[单选题] 有n个叶结点的哈夫曼树的结点总数为A.2n－1B.2nC.2n＋1D.2n25.[单选题] 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为A.5B.6C.7D.86.[单选题] 设指针变量front表示链队列的队头指针，指针变量rear 表示链队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为A.front-next= s;front=s;B.s-next= rear;rear=s;C.rear-next=s;rear=s;D.s-next= front;front=s;7.[单选题] 一个栈的输入序列为1 2 3 4,则下列序列中可能是栈的输出序列的是A.2 3 1 4B.4 1 2 3C.3 1 2 4D.3 4 1 28.[单选题] 具有先进先出特征的数据结构是A.堆栈B.队列C.最小堆D.完全二叉树9.[单选题] 不属于数据组织三个层次的是A.数据B.数据元素C.数据类型D.数据项10.[单选题] 程序段s=i=0;do {i=i+1;s=s+i;}while(i= n)的时间复杂度为A.O(n)B.O(nlog2n)C.O(n2)D.O(1)11.[单选题] 对题13图中的树进行遍历后可以得到序列ABCD的遍历方式是A.先序遍历B.中序遍历C.后序遍历D.层次遍历12.[单选题] 对于线性表(7,34,55,25,64,46,20,10)进行散列存储时，若散列函数为H(K)=K%9，则散列地址为1的元素个数是A.1B.2C.3D.413.[单选题] 一个具有n个顶点的无向完全图的边数为A.0B.n(n-1)/2C.n(n-1)D.n(n+1)14.[单选题] 就平均时间性能而言,若需以O(nlog2n)的时间复杂度完成对数组的排序,则可选择的排序方法是A.快速排序B.冒泡排序C.直接选择排序D.直接插入排序15.[单选题] 设有序表中的元素为(13,18,24,35,47,50,62)，则在其中利用二分法查找值为24的元素需要经过比较的次数是A.1B.2C.3D.416.[案例题] 根据图的定义，图中顶点的最少数目是______。

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精品自学考料推荐⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯全国 2019 年 10 月高等教育自学考试数据结构导论试题课程代码： 02142一、单项选择题（本大题共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=s;C.s–>next=p; p –>next=s; B.p –>next=s –>next; s –>next=p;D.s–>next=p –>next; p=s;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.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（）1A. 先根遍历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(nlog 2n)D.O(n 2)15.下列排序方法中，属于稳定的排序方法是（）A. 直接插入排序法B. 快速排序法C.冒泡排序法D. 堆排序法二、填空题（本大题共13 小题，每小题 2 分，共 26 分）请在每小题的空格中填上正确答案。

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

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

1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ C ）A.n/4B.n/3C.n/2D.n2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ B ）b+(i-1)lA.212B.213C.214D.2153.由顶点V 1，V 2，V 3构成的图的邻接矩阵为⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡010100110，则该图中顶点V 1的出度为（ C ）A.0B.1C.2D.34.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．．的序列是（ C ） A.A ，B ，C ，D ，E B.B ，C ，D ，E ，AC.E ，A ，B ，C ，DD.E ，D ，C ，B ，A5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ）A.23B.37C.44D.466.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ A ）A.O （1）B.O （log 2n ）C.O （n ）D.O (n 2)7.已知一个有序表为（13，18，24，35，47，50，62，83，90，115，134），当二分查找值为90的元素时，查找成功时需比较的次数为（ B ）A.1B.2C.3D.48.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为（ B ）A.O (1)B.O (n)C.O (n )D.O (log 2n)9.下列各项键值序列中不是堆的为（ C ）A.{5，23，16，68，94，72，71，73}B.{5，16，23，68，94，72，71，73}C.{5，23，16，73，94，72，71，68}D.{5，23，16，68，73，71，72，94}10.在线性表的下列存储结构中进行插入、删除运算，花费时间最多的是（ C ）A.单链表B.双链表C.顺序表D.单循环链表11.在栈中进行插入和删除操作的一端称为（ A ）A.栈顶B.栈底C.任意位置D.指定位置12.用n个值构造一棵二叉排序树，它的最大高度为（ B ）A.n/2B. nC.nD.log2n13.冒泡排序的时间复杂度是（ A ）A.O(n2)B.O(nlog2n)C.O(n)D.O(log2n)14.设无向图的邻接表如题14图所示，则该图的边数为（ B ）题14图A.4B.5C.10D.2015.带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ A ）A.front==rear B.front!=NULLC.rear!=NULLD.front==NULL二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

全国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的容量至少为(B) A．2B．3C．4D．62．设计一个判别表达式中左右括号是否配对出现的算法，采用的最佳数据结构为(D) A．线性表的顺序存储结构B．队列C．线性表的链式存储结构D．栈3．下列程序段的时间复杂度为(A)i=0；s=0；while（s<n）{i++；s=s+i；}A．O B．O(log2n)C．O(n)D．O(n2)4．设A是n×n的对称矩阵，将A的对角线及对角线上方的元素Aij(1≤i,j≤n,i≤j)以列优先顺序存放在一维数组元素B[1]至B[n(n+1)/2]中，则元素Aij(i≤j)在B中的位置为(B) A．i(i-l)/2+j B．j(j-l)/2+i C．j(j-l)/2+i-1D．i(i-l)/2+j-15．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是(D) A．G中有弧<Vi，Vj>B．G中有一条从Vi到Vj的路径C．G中没有弧<Vi，Vj>D．G中有一条从Vj到Vi的路径6．下列序列中，由第一趟快速排序可得到的序列（排序的关键字类型是字符串）是(A) A．［da，ax，eb，de，bb］ff［ha，gc］B．［cd，eb，ax，da］ff［ha，gc，bb］C．［gc，ax，eb，cd，bb］ff［da，ha］D．［ax，bb，cd，da］ff［eb，gc，ha］7．不稳定的排序方法是(C)A．直接插入排序B．冒泡排序C．堆排序D．二路归并排序8．设散列表表长m=14，散列函数为h（k）=k%11，表中已有4个记录，如果用二次探测法处理冲突，关键字为49的记录的存储位置是(D)01234567891011121315386184A．3B．5C．8D．99．若元素1，2，3依次进栈，则退栈不可能出现的次序是(C)A．3，2，1B．2，1，3C．3，1，2D．1，3，210．直接插入排序的时间复杂度是(A)A．O（n2）B．O（nlog2n）C．O（n）D．O（log2n）11．稀疏矩阵是指(C)A．元素少的矩阵B．有少量零元素的矩阵C．有少量非零元素的矩阵D．行数、列数很少的矩阵12．深度为k（k≥1）的二叉树，结点数最多有(B)A．2k B．2k-1C．2k-1D．2k-1-113．由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为(C) A．23B．37C．44D．4614．有n个顶点的有向完全图的弧数为(C)A．n2B．2n C．n（n-1）D．2n（n+1）15．图的深度优先搜索类似于二叉树的(A)A．先根遍历B．中根遍历C．后根遍历D．层次遍历二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

全国2018年10月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母标号填入题干的括号内。

每小题2分，共30分)1．下列数据组织形式中，（）的结点按逻辑关系依次排列形成一个“锁链”。

A.集合B.树形结构C.线性结构D.图状结构2．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（）A.S上的算法 B.S的存储结构C.在S上的一个基本运算集D.在S上的所有数据元素3．下列说法正确的是（）A.线性表的逻辑顺序与存储顺序总是一致的B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可以不连续C.线性表的线性存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本运算4．设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（）A.s->next=p->next;p->next=s；B.p->next=s;s->next=p->next；C.s->next=p->next;p->next=s;交换p->data和s->data；D.p=s;s->next=p；5．稀疏矩阵一般采用（）方法压缩存储。

A.三维数组B.单链表C.三元组表D.散列表6．树若用双亲链表表示，则（）A.可容易地实现求双亲及子孙的运算B.求双亲及子孙的运算均较困难C.可容易地实现求双亲运算，但求子孙运算较困难D.可容易地实现求子孙运算，但求双亲运算较困难7．将一棵有50个结点的完全二叉树按层编号，则对编号为25的结点x，该结点（）A.无左、右孩子B.有左孩子，无右孩子C.有右孩子，无左孩子D.有左、右孩子8．用邻接表作为有向图G的存储结构。