全国2019年4月自考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）为基本运算。

数据结构导论自考题-2(总分100, 做题时间90分钟)一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。

1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) A．存储结构B．存储实现C．逻辑结构D．运算实现SSS_SIMPLE_SINA B C D分值: 2答案:C2.所有的存储结点存放在一个连续的存储空间，该存储方式是( )存储方式。

A．顺序B．链式C．索引D．散列SSS_SIMPLE_SINA B C D分值: 2答案:A[解析] 本题主要考查的知识点是顺序存储方式。

[要点透析] 顺序存储方式是指所有存储结点存放在一个连续的存储区里。

利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。

3.设线性表有n个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。

A．输出第i(1≤i≤n)个元素值B．交换第1个元素与第2个元素的值C．在第i个元素前插入一个元素D．删除第i个元素SSS_SIMPLE_SINA B C D分值: 2答案:A[解析] 本题主要考查的知识点为顺序表和链表。

[要点透析] 由于顺序表具有随机存取特性，所以和链表相比输出第i个元素时效率很高。

本题答案为A。

4.与单链表相比，双链表的优点之一是( )A．插入、删除操作更简单B．可以进行随机访问C．可以省略表头指针或表尾指针D．前后访问相邻结点更灵活SSS_SIMPLE_SINA B C D分值: 2答案:D5.循环队列的队满条件为( )A．(CQ.rear+1)%maxsize==(CQ.front+1)%maxsizeB．(CQ.rear+1)%maxsize==CQ.front+1C．(CQ.rear+1)%maxsize==CQ.frontD．CQ.rear==CQ.frontSSS_SIMPLE_SINA B C D分值: 2答案:C[解析] 本题主要考查的知识点是循环队列的队满条件。

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、单项选择题(本大题共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所指的结点，则应执行( )操作。

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

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

2019年4月高等教育自学考试全国统一命题考试数据结构（课程代码 02331）第一部分选择题一、单项选择题:本大题共15小题，每小题2分，共30分。

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

1.线性表是一种由n个数据元素组成的数据结构，n的取值是A.0或者任意一个正整数或者∞B.非负整数C.任意一个正整数或者∞D.某个正整数2.在一个单链表中，已知q所指结点是p所指结点的后继结点，若在p和q之间插入s所指结点，则正确的操作是A.s->next=p->next；p->next=s；B.s->next=q；p->next-s->next；C.q->next=s；s->next-p；D.p->next=s；s->next=p；3.下列选项中，不宜通过栈求解的问题是A.判断字符串是否是回文B.检验圆括号是否匹配C.不同数制之间进行转换D.图的广度优先搜索遍历4.设栈S的输入序列为1，2，3，4，5，则下列选项中不可能是s的输出序列的是A.2，3，4，1，5B.5，4，1，3，2C.2，3，1，4，5D.1，5，4，3，25.使用一个大小为6的数组保存循环队列Q。

若从Q中出队两个元素，并入队个元素，此时队尾rear 和队头front的值分别为2和4.则在执行这三个操作之前rear和font的值分别是A.0和3B.1和2C.2和5D.4和56.设二维数组M有3行4列，按行优先的方式存储，每个元素占6个存储单元。

第1个元素的存储地址为100，则M[2][2]的存储地址为A.135B.153C.160D.1657.设n阶方阵M是对称矩阵，采用压缩存储方式将M中的元素保存在一维数组B中，则下列选项中，正确的是A.保存M中的主对角线中的元素，B的元素个数是nB.保存M中上三角部分的元素，B的元素个数是n(n-1)/2C.保存M中上三角部分的元素，B的元素个数是n(n+1)2D.保存M中的全部元素，B的元素个数是2n8.已知完全二叉树T的第4层有5个叶结点，则T的结点个数最多是A.12B.20C.21D.369.在一棵非空二叉树的后序遍历序列中，所有列在根结点前面的是A.左子树中的部分结点B.右子树中的全部结点C.左右子树中的部分结点D.左右子树中的全部结点10.若对题10图所示的无向图进行深度优先搜索遍历，则下列选项中正确的遍历序列是A.h，c，a，b，d，e，g，fB.e，a，f，g，b，h，c，dC.d，b，c，a，h，e，f，gD.a，b，c，d，h，e，f，g11.对题11图所示的有向图进行拓扑排序。

数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。

全国2019年4月高等教育自学考试离散数学试题课程代码：02324一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有一个选项符合题目要求的。

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

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

1.下列不是平面图的是( )2.无向图G中有16条边，且每个结点的度数均为2，则结点数是( )A.8B.16C.4D.323.如下图所示的有界格中，元素b的补元是( )A.aB.0C.cD.d4.设〈G,*〉是群，且|G|>1，则下列命题不成立的是( )A.G中有幺元B.G中有零元C.G中任一元素有逆元D.G中除了幺元外无其他幂等元5.设Z是整数集合，则下面定义的二元运算不能使Z与 构成代数系统的是( )A.i j=|i-j|,∀i,j∈ZB.i j=i·j-j2，∀i,j∈ZC.i j=i/j,∀i,j∈ZD.i j=i2+j2+1,∀i,j∈Z6.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是( )A.P(A)B.φC.AD.|φ|7.设N为自然数集(含0)，函数F：N→N×N,F(n)=<n,n+1>是( )A.满射，不是入射B.入射，不是满射C.双射D.不是入射，不是满射8.设A={a,b,c}，则下列是集合A 的划分的是( )A.{{b,c},{c}}B.{{a,b},{a,c}}C.{{a,b},c}D.{{a},{b,c}} 9.设集合X={0,1,2,3}，R 是X 上的二元关系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}，则R 的关系矩阵M R 是( )A ．⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1100100000110101 B.⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000001111000101C. ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111101001011000 D. ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0101100011000111 10.下列命题中，不正确的是( ) A.{φ}∈{φ,{φ}} B.{φ}∈{φ,{{φ}}} C.{φ}⊆{φ,{φ}} D.φ⊆{φ,{ φ}}11.设个体域是正整数集，则下列公式中真值为真的公式是( ) A.(∀x)(∃y)(x ·y=0) B.(∀x)(∃y)(x ·y=1) C.(∃ x)(∃y)(x ·y=2)D.(∀x)(∀y)(∃z)(x-y=z)12.令F(x):x 是金属，G(y):y 是液体，H(x,y):x 可以溶解在y 中，则命题“任何金属可以溶解在某种液体中”可符号化为( ) A.(∀x)(F(x)∧(∃y)(G(y)∧H(x,y))) B.(∀x)(∃(x)F(x)→(G(y)→H(x,y))) C.(∀x)(F(x)→(∃y)(G(y)∧H(x,y))) D.(∀x)(F(x)→(∃y)(G(y)→H(x,y))13.在个体域D={a,b}中，与公式(∃x)A(x)等价又不含量词的公式是( ) A.A(a)∧A(b) B.A(a)→A(b) C.A(a)∨A(b) D.A(b)→A(a) 14.下列句子是命题的是( ) A.水开了吗? B.x>1.5C.再过5000年，地球上就没水了。

2019年4月高等教育自学考试计算机系统结构真题(总分100, 做题时间150分钟)单项选择题用微程序直接解释另一种机器指令系统的方法称为（）。

SSS_SINGLE_SELA编译B仿真C翻译D模拟分值: 1答案:B本题考查的是关于仿真的概念。

从计算机信息加工的各个步骤和阶段的角度来看，并行性等级最低的是（）。

SSS_SINGLE_SELA处理器操作步骤并行B存储器操作并行C处理器操作并行D指令、任务、作业并行分值: 1答案:B本题考查的是并行性的相关知识点。

下列选项中属于高级数据表示的是（）。

SSS_SINGLE_SELA向量B定点数C逻辑数D字符串分值: 1答案:A本题考查的是高级数据表示的概念。

浮点数表示中，当阶值位数一定时，不会受到尾数进制影响的是（）。

SSS_SINGLE_SELA精度B数符C范围D离散程度分值: 1答案:B本题考查的是浮点数的内容。

下列属于总线标准的是（）。

SSS_SINGLE_SELA吞吐率B速率C流量D电气分值: 1答案:D本题考查的是总线系统标准的知识点。

浮点数系统使用的阶基rp=2，阶值位数p=2，尾数位数m=4，尾数基值rm=2时，在非负阶正尾数、规格化的情况下可表示的最小尾数是（）。

SSS_SINGLE_SELA1/2B1/4C1/8D1/16分值: 1答案:A本题考查的是浮点数各种特性参数的一般式。

总线按在系统中的位置分的级别数为（）。

SSS_SINGLE_SELA3级B4级C5级D6级分值: 1答案:A本题考查的是总线分类的概念。

总线按在系统中的位置分芯片级(CPU芯片内的总线)、板级 (连接插件板内的各个组件，也称局部总线或内部总线)和系统级(系统间或主机与/O接]或设备之间的总线)等3级。

Cache存储器是为了解决主存满足不了要求的性能指标是（）。

SSS_SINGLE_SELA容量B价格C字长D速度分值: 1答案:D本题考查的是Cache的工作原理。