2020年10月自考02142数据结构导论试题及答案含评分标准

20XX年(下)高等教育自学考试全国统一命题考试数据结构导论试卷及参考答案第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的。

请将其代码填写在题后的括号内。

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

1．数据的基本单位是 ( )A．数据项 B．数据类型C．数据元素 D．数据变量2．下列程序的时间复杂度为 ( )3．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则最节省运算时间的存储方式是 ( )A．单链表 B．仅有头指针的单循环链表C．双链表 D．仅有尾指针的单循环链表4．从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动的元素的个数是( )A．n—i B．n—i+1C．n—i一1 D．i5．顺序栈S中top为栈顶指针，指向栈顶元素所在的位置，elem为存放栈的数组，则元素e进栈操作的主要语句为 ( )6．循环队列sq中，用数组elem[0··25]存放数据元素，sq．front指示队头元素的前一个位置，sq．rear指示队尾元素的当前位置，设当前sq．front为20，sq．rear为12，则当前队列中的元素个数为 ( )A．8 B．16C．17 D．18A．13 B．35C．17 D．368．含有10个结点的二叉树中，度为0的结点数为4，则度为2的结点数为 ( ) A．3 B.4C．5 D．69．对一棵有100个结点的完全二叉树按层编号，则编号为49的结点，它的父结点的编号为( )A．24 B．25C．98 D．9910．可以惟一地转化成一棵一般树的二叉树的特点是 ( )A．根结点无左孩子 B．根结点无右孩子C．根结点有两个孩子 D．根结点没有孩子11．有n个结点的有向完全图的弧数是( )12．设图的邻接链表如题l2图所示，则该图的边的数目是 ( )A．4 B．5C．10 D．201 3．已知一个有序表为(13，18，24，35，47，50，62，83，90，115，134)，当二分检索值为90的元素时，检索成功需比较的次数是 ( )A．1 B．2C．3 D．414．排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是 ( ) A．选择排序 B．快速排序C．冒泡排序 D．插入排序15．排序算法中，不稳定的排序是 ( )A．直接插入排序 B．冒泡排序C．堆排序 D．归并排序第二部分非选择题二、填空题(本大题共l3小题，每小题2分，共26分)请在每小题的空格中填上正确答案。

目录第一章概论 (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）为基本运算。

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.归并排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

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

数据结构自考试题及答案一、单项选择题（每题1分，共10分）1. 在数据结构中，从逻辑上可以把数据结构分为（）。

A. 动态结构和静态结构B. 线性结构和非线性结构C. 顺序结构和链式结构D. 内部结构和外部结构答案：B2. 线性表的顺序存储结构和链式存储结构相比，它的优点是（）。

A. 存储密度大B. 存储密度小C. 插入和删除操作快D. 可以进行随机访问答案：D3. 下列关于栈的描述中，错误的是（）。

A. 栈是先进后出（LIFO）的线性表B. 栈允许在一端进行插入和删除操作C. 栈是具有记忆功能的线性表D. 栈的插入和删除操作必须在栈顶进行答案：C4. 在二叉树的遍历过程中，若某结点的左子树为空，则该结点的左孩子直接与（）相连。

A. 右孩子B. 右兄弟C. 父节点D. 子节点答案：C5. 哈希表的构造方式是（）。

A. 数组B. 树C. 链表D. 图答案：A6. 在图的遍历过程中，深度优先搜索（DFS）和广度优先搜索（BFS）的主要区别在于（）。

A. 遍历顺序B. 是否使用栈C. 是否使用队列D. 是否使用递归答案：C7. 快速排序算法的时间复杂度在最坏情况下是（）。

A. O(n)B. O(nlogn)C. O(n^2)D. O(2^n)答案：C8. 以下排序算法中，时间复杂度为O(nlogn)的是（）。

A. 冒泡排序B. 选择排序C. 快速排序D. 插入排序答案：C9. 在数据库管理系统中，索引的作用是（）。

A. 存储数据B. 提高查询效率C. 维护数据完整性D. 实现数据加密答案：B10. 以下不属于查找算法的是（）。

A. 顺序查找B. 二分查找C. 哈希查找D. 归并排序答案：D二、填空题（每题2分，共20分）11. 在数据结构中，线性表的顺序存储结构通常使用___________来实现。

答案：数组12. 一个长度为n的顺序表，若在第i个位置插入一个元素（1≤i≤n+1），需要向后移动___________个元素。

⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯精品自学考料推荐⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯⋯全国 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 分）请在每小题的空格中填上正确答案。

全国自学考试数据结构导论试题及答案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. 在二叉树中，每个节点最多有____个子节点。

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

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

1．数据结构是（）A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合2．算法分析的目的是（）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性3．在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（）A．插入B．删除C．排序D．定位4．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，15．设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（）A．15 B．16C．17 D．186．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（）A．1207 B．12091C．1211 D．12137．在按层次遍历二叉树的算法中，需要借助的辅助数据结构是（）A．队列B．栈C．线性表D．有序表8．在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）A．不一定相同B．都相同C．都不相同D．互为逆序9．若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法10．若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目11．图的邻接矩阵表示法适用于表示（）A．无向图B．有向图C．稠密图D．稀疏图12．在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（）A．i B．i+1C．n-i D．n-i+113．下列排序算法中，其时间复杂度和记录的初始排列无关的是（）A．插入排序B．堆排序C．快速排序D．冒泡排序14．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）A．f,c,b B．f,d,bC．g,c,b D．g,d,b15．若在文件中查询年龄在60岁以上的男性及年龄在55岁以上的女性的所有记录，则查询条件为（）A．（性别=“男”）OR(年龄> 60)OR（性别=“女”）OR（年龄>55）B．（性别=“男”）OR(年龄> 60)AND（性别=“女”）OR（年龄>55）C．（性别=“男”）AND(年龄> 60)OR（性别=“女”）AND（年龄>55）2D．（性别=“男”）AND(年龄> 60)AND（性别=“女”）AND（年龄>55）二、填空题（本大题共10小题，每小题2分，共20分）请在每小题的空格中填上正确答案。

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

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

1．下列描述中正确的是( )A.数据元素是数据的最小单位B.数据结构是具有结构的数据对象C.数据结构是指彼此之间存在一种或多种特定关系的数据元素的集合D.算法和程序原则上没有区别，在讨论数据结构时两者是通用的2．归并排序的时间复杂度是( )A．O（n2）B.O（nlog2n）C.O（n）D.O（log2n）3．二分查找的时间复杂度是( )A．O（n2）B.O（nlog2n）C.O（n）D.O（log2n）4．挨次存储的表中有90000个元素，已按关键字值升序摆列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用挨次查找法查找时，需平均比力的次数为( )A．25000B.30000C.45000D.900005．散列文件是一种( )A．挨次文件B.索引文件C.链接文件D.计算寻址文件6．两个矩阵A：m×n，B：n×p相乘，其时间复杂度为( )A．O(n)B.O(mnp)C.O(n2)D.O（mp）7.常用于函数调用的数据结构是( )A.栈B.队列C.链表D.数组8．二维数组A［n］［m］以列优先挨次存储，数组A中每个元素占用1个字节，A［1］［1］为首元素，其地址为0，则元素A［i］［j］的地址为( )A.（i-1）×m+(j-1)B.(j-1)×n+(i-1)C.(j-1)×n+iD.j×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，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．一整数序列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分)请在每小题的空格中填上正确答案。

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

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

1．下列各式中，按增长率由小至大的顺序正确排列的是( )A．n，n！，2n ，n3/2B．n3/2，2n，n logn，2100C．2n，log n，n logn，n3/2D．2100，logn, 2n, n n2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( )A．s->next=p->next; p->next=s; B．p->next=s; s->next=p->next;C．p->next=s->next; s->next=p; D．s->next=p; p->next=s->next;3．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向( )A．各自的头结点B．各自的尾结点C．各自的第一个元素结点D．一个表的头结点，另一个表的尾结点4．栈的两种常用存储结构分别为( )A．顺序存储结构和链式存储结构B．顺序存储结构和散列存储结构C．链式存储结构和索引存储结构D．链式存储结构和散列存储结构5．已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为( )A．5 B．6C．16 D．176．已知在如下定义的链串结点中，每个字符占1个字节，指针占4个字节，则该链串的存储密度为typedef struct node {char data[8];struct node *next;} LinkStrNode;A．1/4 B．1/21C．2/3 D．3/47．应用简单的匹配算法对主串s=″BDBABDABDAB″与子串t=″BDA″进行模式匹配，在匹配成功时，进行的字符比较总次数为( )A．7 B．9C．10 D．128．二维数组A[20][10]采用列优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200，则元素A[8][9]的存储地址为( )A．574 B．576C．578 D．5809．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是( )A．（c,d）B．(d)C．b D．(b)10.已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为( )A．ABCDEF B．ABCEFDC．ABFCDE D．ABCDFE11．一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为( )A．O(n) B．O(e)C．O(n+e) D．O(n2)12．在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为( )A．4，4，3 B．4，3，3C．3，4，4 D．3，3，413．下列排序方法中，最好与最坏时间复杂度不相同的排序方法是( )A．冒泡排序B．直接选择排序C．堆排序D．归并排序14．已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于( )A．1.0 B．2.9C．3.4 D．5.515．在下列各种文件中，不能进行顺序查找的文件是( )A．顺序文件B．索引文件C．散列文件D．多重表文件2二、填空题(本大题共10小题，每小题2分，共20分)16．抽象数据类型是指数据逻辑结构及与之相关的___________。

全国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的存储结构。