02142数据结构导论201710月份真题答案与解析

2016年10月高等教育自学考试全国统一命题考试

数据结构导论试卷

(课程代码02142)

本试卷共4页，满分l00分，考试时间l50分钟。

考生答题注意事项：

1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。

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

第一部分选择题(共30分)

一、单项选择题(本大题共10小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。

1．已知问题规模为n，则下列程序片段的时间复杂度是C

2．若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是

A．栈B．队列C．树D．图

3．若线性表采用链式存储结构，则适用的查找方法为

A．随机查找B．散列查找C．二分查找D．顺序查找

4．已知指针P和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，则在S所指结点之后插入上述单链表应执行的语句为

A．q→next；s→next；s→next2P；B．s→next=P；q→next=s→next；

C．p→next=s→next；s→next=q；D．s→next2q；p→next2s→next；

5．栈的运算特点是先进后出，元素a、b、c、d依次入栈，则不能得到的出栈序列是

A．abed B．dcba C．cabd D．bcda

6．在实现队列的链表结构中，其时间复杂度最优的是

A．仅设置头指针的单循环链表B．仅设置尾指针的单循环链表

C．仅设置头指针的双向链表D．仅设置尾指针的双向链表

7．任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是

A．不一定相同 B. 都相同C．都不相同D．互为逆序

8．若某棵树的存储结构采用双亲表示法，如题8图所示，则该树的高度是

A．2 B．3 C．4 D．5

9．无向图的邻接矩阵一定是

A．对称矩阵B．对角矩阵C．稀疏矩阵D．三角矩阵

10．根据连通图的深度优先搜索的基本思想，如题10图所示的连通图的一个深度优先搜索的结果序列是

A．123456 B．123465 C. 126345 D．162543

11．用顺序查找方法对含有n个数据元素的顺序表按从后向前查找次序进行查找，现假设查找

其中每个数据元素的概率不相等，那么

A．该顺序表按查找概率由低到高的顺序来存储数据元素，其ASL最小

B．该顺序表按查找概率由高到低的顺序来存储数据元素，其ASL最小

C．ASL的大小与数据元素在该顺序表中的位置次序无关

D．ASL的大小与查找每个数据元素的概率无关

12．已知散列表的存储空间为T[0，…，l6]，散列函数为H(k)----k mod l7，用二次探测法解决冲突。散列表中已插入下列关键字：TE53--39、T[6]一57和T[73—7，则下一个关键字值23在该散列表中插入的位置是

A．T[23 B．T[4] C．T[8] D．T[10]

13．对关键字序列{eSC，tab，ah，con，brk，del}进行排序时，若关键字序列的变化情况如下；

①esc，tab，ah，con，brk，del

②ah，tab，eSC，con，brk，del

③alt，brk，esc，con，tab，del

④alt，brk，con，esc，tab，del

ah，brk，con，del，tab，esc

⑥ah，brk，con，del，esc，tab。则所用的排序方法是

A．直接插入排序B．直接选择排序C．堆排序D．冒泡排序

14．满足最小堆定义的是

A. {21，25，55，23，51，63} B．{21，51，55，63，25，23}

C．{21，63，55，25，51，23} D．{21，51，23，63，55,25}

15．设有两个长度分别为m、n的降序有序序列{a1，a2，…，a m)、{b1，b2，…，b n)，采用二路归并方法将它们合并成长度为m+12的降序有序序列，则归并过程中元素比较次数最少的条件一定是BCCCCCCCCCCCC

第二部分非选

择题(共70分)

二、填空题(本大题共l3小题，每小题2分，共26分)

16．从宏观上看，数据、数据元素和__数据项___ 反映了数据组织的三个层次。

17．在表长为n的顺序表中插入或删除一个元素，则需移动元素的具体个数与表长和_元素位置_有关。

18．非空的单循环链表的头指针为head，尾指针为rear，则rear一>next=___head____。

19．设以数组Q[m]存放循环队列的元素，变量rear和queuelen分别表示循环队列中队尾元素的下标位置和元素的个数。则计算该队列中队头元素下标位置的公式是__ (rear – queuelen + m )%m___。

20．二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为l087，A[4][7]

的存储地址为ll53，则每个数组元素占用的存储单元的个数是___3_____。

21．设一个完全二叉树共含有196个结点，则该完全二叉树中含有叶结点的个数是___98_____。

22．假设高度为h二叉树中只有度为2和度为0这两种类型的结点，则该类二叉树中结点个数至多为2h-1、至少为__3______。

23．若以数据集{34，5，12，23，8，18}为叶结点的权值构造一棵哈夫曼(HUffman)树，那么该Huffman树的带权路径长度WPL_238_____。

24．设有散列函数H(k)和键值，则这种现象称为“冲突”，且称键值k1和k2互为__同义词____。

25．一个图的最小生成树是满足一定条件的生成树，即一个图的最小生成树是指该图的所有生成树中__权值之和最小____的生成树。

26．对长度为n的有序顺序表进行二分查找，则查找表中的任意一个元素时，无论查找成功与失败，最多与表中__longN_+1___个元素进行比较。

27．排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素按序进行比较，将其插入已排序序列的正确位置上的方法称为__直接插入排序____。

28．一般情况下，时闯复杂度是O(nl0g2n)且其空间复杂度最优的排序方法是___堆排序___。

三、应用题(本大题共5小题，每小题6分，共30分)

29．借助于队列能够将含有n个数据元素的栈逆置，比如栈S中的元素为{a，b，C}逆置后变成{C，b，a}。试简述你的解决方案。

30．为便于表示二叉树的某些基本运算，则深度为k．的二叉树的顺序存储结构中的数组的大小为多少?画出如题30图所示的二叉树的顺序存储结构示意图，并说明对一般形态的二叉树不太适合使用顺序存储结构来表示的原因。

31．先序遍历、中序遍历一个森林分别等同于先序、中序遍历该森林所对应的二叉树。现已知一个森林的先序序列和中序序列分别为ABCDEFIGJH和BDCAIFJGHE，试画出该森林。

32．设有一组关键字值序列{e，b，d，f，a，g，C}现要求：(1)根据二叉排序树的创建方法构造出相应的二叉排序树(关键字值的大小按字母表顺序计)；(2)计算等概率情况下在该二叉排序树上查找成功的平均查找长度ASL。33．若采用二路归并排序方法对关键字序列{25，9，78，6，65，15，58，18，45，20}进行升序排序，写出其每趟排序结束后的关键字序列。

四、算法设计题(本大题共2小题，每小题7分，共l4分)

34．某电商有关手机的库存信息，按其价格从低到高存储在一个带有头结点的单循环链表中，链表中的结点由品牌型号(nametype)、价格(price)、数量(quantity)和指针(next)四个域组成。现新到in台、价格为c、品牌型号为x 的新款手机需入库，写出相应的存储结构和实现该要求的算法。

35．写出向存储结构为邻接矩阵的无向图G中插入一条边(x，y)的算法。算法的头函数为：void AddEdgetoGraph(Graph*G，VertexType X，VertexType y>，无向图G的存储结构为：

全国自学考试数据结构导论试题及答案(4套)

全国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={，，，，,，，,，}，则图G的拓扑序列是 ( ) A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7 C.V1,V3,V4,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7 4.有关图中路径的定义，表述正确的是( ) 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.树

02142数据结构导论201604

2016年4月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码 02142) 本试卷共6页。满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题。每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个公司的组织机构是1名公司经理领导若于名部门负责人、每个部门负责人领导若干名部门员工，则适合于描述该公司组织机构的逻辑结构是 A．线性表 B．队列 C．树 D．图 2．计算n!(整数n≥0)的递归算法是：int Factorial(int n){if(n= =o)return l；else return n*Factorial(n--1)；}其时闯复杂度为 A．0(n) B．0(log2n) C．O(n0) D．O(n2) 3．将一个由指针q指向的结点插在单链表中由指针P所指向的结点之后的操作是 A．p=q； B．p--：>next=q； C．q一>next=p--：>next；p-->next=q； D．p一>next—q；q-->next—p--：>next； 4. 设初始栈为空，s表示人栈操作，x表示出栈操作，则合法的操作序列是 A．sxxssxxs B．ssxsxxxs C．ssxxxssx D．sssxxxsx 5．将递归形式描述的算法改写为功能等价的非递归形式描述的算法，通常应设置的辅助结构是 A．顺序表 B．单链表C．栈 D．队列 6．设长度为n的队列用单循环链表表示(假设表尾结点为当前队列的队尾元素)，若只设头指针，则入队操作、出队操作的时间复杂度分别为 A．O(n)、O(1) B．O(1)、O(1) C．O(1)、O(n) D．0(n)、0(n) 7．若采用顺序存储(一维数组)结构存储一棵如题7图所示的二叉树，根结点1的下标为l，剥结点4的下标为 A．4 B．5 C．6 D．7 8．按层序(自顶向下、从左到右)遍历二叉树时需借助队列作辅助结构。对高度为3的满二叉树进行层序遍历时，队列中所出现的元素个数最多是

数据结构导论年月试题

二00一年下半年全国高等教育自学考试 数据结构导论试卷 一、单项选择题 1.若给定有n个元素的向量,则建立一个有序单向链表的时间复杂性的量级是( ) A.O(1) B.O(n) C.O(n2) D.O(nlog2n) 2.在一个具有n个结点的单链表达中查找值为m的某结点,若查找成功，则平均比较（） A．n B.n/2 C.(n-1)/2 D.(n+1)/2 3．研究数据结构就是研究（） A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构,存储结构及其数据在运算上的实现 4.为了方便地对图状结构的数据进行存取操作，则其数据存储结构宜采用（）方式。 A、顺序存储 B、链式存储 C、索引存储 D、散列存储 5．二维数组A[10……20，5……10]采用行序为主序方式存储，每个数据元素占4个存储单元，且A[10，5]的存储地址是1000，则A[18，9]的地址是（） A、1208 B、1212 C、1368 D、1364 6．设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树中共有（）个结点。 A、13 B、12 C、26 D、25 7．下列几种结构中属于树型结构的是（） 8．设无向图G=（V、E）和G’=（V’，E’），如G’为G的生成树，则下面不正确的说法是（） A、G’为G的连通分量 B、G’为G的无环子图 C、G’为G的子图 D、G’为G的极小连通子图且V’=V 9．下列说法中不正确的是（） A、无向图的极大连通子图称为连通分量 B、连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C、图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D、有向图的遍历不可采用广度优先搜索方法 10．对有序表（18，20，25，34，48，62，74，85）用二分查找法查找85，所需的比较次数为（） A、1次 B、2次 C、3次 D、4次 11．散列表的平均查找长度（） A、与处理冲突方法有关而与表的长度无关 B、与处理冲突方法无关而与表的长度有关 C、与处理冲突方法有关且与表的长度有关 D、与处理冲突方法无关且与表的长度无关 12．对ISAM文件的删除记录时，一般（） A、只需做删除标志 B、需移动记录 C、需改变指针 D、一旦删除就需做整理 13．顺序文件适宜于（） A、直接存取 B、成批处理 C、按关键字存取 D、随机存取 14．一个序列中有10000个元素，若只想得到其中前10个最小元素，最好采用（）方法。 A、快速排序 B、堆排序 C、插入排序 D、二路归并排序

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

全国2012年1月数据结构导论试题课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结 构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i

自考数据结构导论复习资料

数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象

8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被

自考数据结构导论

全国2014年4月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.下列几种算法时间复杂度中，最小的是( A ) A.O(log2n) B.O(n) C.O(n2) D.O(1) 2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有( D ) A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式 C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式 3.表长为n的顺序表中做删除运算的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为( C ) A.O(1) B.O(log2n) C.O(n) D.O(n2) 5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为( C ) A.D B.C C.B D.A 6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为( A ) A.front==rear B.front!=NULL C.rear!==NULL D.front==NULL 7.深度为5的二叉树，结点个数最多为( A )

【自考真题】2018年4月数据结构导论02142试题

绝密★考试结束前 全国2018年4月高等教育自学考试 数据结构导论试题 课程代码:02142 请考生按规定用笔将所有试题的答案涂二写在答题纸上三 选择题部分 注意事项: 1.答题前,考生务必将自己的考试课程名称二姓名二准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上三 2.每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑三如需改动,用橡皮擦干净后,再选涂其他答案标号三不能答在试题卷上三 一二单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将 答题纸”的相应代码涂黑三错涂二多涂或未涂均无分三 1.数据的逻辑结构分为四种,其中结构最复杂的是 A.集合 B.线性结构 C.树形结构 D.图结构 2.下面程序是矩阵转置算法MM的实现过程,其时间复杂度为 const int n=3; void MM(int A[n][n]) { int i,j,temp; for(i=0;i

3.设顺序表的表长为n,则删除一个元素在最坏情况下元素移动次数为 A.n-2 B.n-1 C.n D.n+1 4.带头结点的双向循环链表L为空的条件是 A.L->next==L->prior B.L->prior==NULL C.(L->next==L)&&(L->prior==L) D.(L->next==L)&&(L->prior=NULL) 5.执行进栈操作,在元素x进栈前需要进行的操作是 A.判断栈是否满,若栈未满,top值加1 B.判断栈是否空,若栈未空,top值加1 C.判断栈是否满,若栈未满,top值减1 D.判断栈是否空,若栈未空,top值减1 6.关于队列,下列叙述正确的是 A.队列的元素个数可以无穷大 B.队列中元素的类型可以不同 C.队列是一个非线性的序列 D.队列的特点是先进先出 7.设循环队列的元素存放在一维数组Q[30]中,队列非空时,front指示队列首结点的前一个位置,rear指示队列尾结点三如果队列中元素的个数为10,front的值为25,则rear应指向的元素是 A.Q[4] B.Q[5] C.Q[14] D.Q[15] 8.二叉树第i(i≥1)层上的结点数最多为 A.2i-1 B.i-1 C.2*i D.2*(i-1) 9.关于二叉链表,下列叙述正确的是 A.二叉链表是二叉树唯一的链式存储结构 B.对二叉链表的访问可以从任意结点开始 C.每个二叉链表不需要有一个指向根节点的指针 D.二叉链表的结点结构包含一个数据域和两个指针域 10.假设初始森林中共有n棵二叉树,每棵树中都仅有一个孤立的结点三将该森林构造成哈夫 曼树,则最终求得的哈夫曼树的结点数为 A.n-1 B.n C.2n-1 D.2n 11.无向图中的极大连通子图是 A.连通分量 B.生成树 C.强连通分量 D.强连通图 12.在用邻接表表示图时,对图进行深度优先搜索遍历的算法的时间复杂度为 A.O(n) B.O(n+e) C.O(n2) D.O(n3)

02142数据结构导论2010年1 月份真题及答案

2010年1月高等教育自学考试全国统一命题考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列

9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n) C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++)

全国数据结构导论10月高等教育自学考试试题与答案

全国20XX 年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ C ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ B ）b+(i-1)l A.212 B.213 C.214 D.215 3.由顶点V 1，V 2，V 3构成的图的邻接矩阵为???? ??????010100110，则该图中顶点V 1的出度为（ C ） A.0 B.1 C.2 D.3 4.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．． 的序列是（ C ） A.A ，B ，C ，D ，E B.B ，C ，D ，E ，A C.E ，A ，B ，C ，D D.E ，D ，C ，B ，A 5.由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（C ） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ 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.1 B.2 C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为 （ B ） A.O (1) B.O (n) C.O (n ) D.O (log 2n)

《数据结构导论》考纲、试题、答案

《数据结构导论》考纲、试题、答案 一、考试说明 本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）： 1、判断题（正确打√，错误打×，每题3分，共15分） 2、填空（每空2分，共20分） 3、选择题（每题3分，共15分） 4、名词解释（每小题4分，共20分） 5、简答题（每题6分，共30分） 备注：以上题型供参考 二、课程知识要点 第一章 ◆数据结构 ◆实例 第二章 ◆银行排队顺序存储 ◆学生健康登记表 第三章 ◆栈和队列 ◆回文 ◆杨辉三角 第四章 ◆串 ◆文本加密 第五章 ◆内部排序 ◆查找

◆二叉树 第六章 ◆树 ◆图 ◆数组 第七章 ◆文件 ◆外部排序 备注：根据教材实际章节汇总要点，突出需要掌握的重点内容 三、重点习题 1、判断题 ◆具有n 个结点的线索二叉树上，含有n+1个线索。 ◆三叉链表属于二叉树存储结构。 ◆哈夫曼树不存在度为1的结点。 ◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 ◆栈和队列的存储方式既可是顺序方式，也可是链接方式。 ◆二叉树中每个结点的两棵子树是有序的。 2、填空 ◆数据的逻辑结构指 ◆一个算法的时间复杂度 ◆单链表中，增加头结点的目的 ◆表长为0的线性表 ◆串的长度 ◆若两个串的长度相等且对应位置上的字符也相等 ◆常用的插入排序 ◆常用的处理冲突的方法 ◆常用的选择排序方法 ◆衡量一个算法的优劣主要考虑 ◆在有n个结点的二叉链表中，空链域的个数 ◆常用的选择排序方法

2010年1月自考数据结构导论真题

全国2010年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（） A.顺序文件 B.索引文件 C.散列文件 D.多关键字文件 2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（） A.acbed B.becab C.deabc D.cedba 3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 B.n C.n+1 D.n+2 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 B.1∶1 C.2∶1 D.4∶1 5.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( ) A.O(1) B.O(1og2n) C.O(n) D.O(n2) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 B.快速排序 C.归并排序 D.选择排序 7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 B.n C.n+1 D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为n的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) B.O(n)

C.O(nlog2n) D.O(n2) 10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为( ) A.n-2 B.n-1 C.n D.n+1 11.有关插入排序的叙述，错误的 ．．．是( ) A.插入排序在最坏情况下需要O(n2)时间 B.插入排序在最佳情况可在O(n)时间内完成 C.插入排序平均需要O(nlog2n)时间 D.插入排序的空间复杂度为O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为( ) A.rear=rear+1 B.rear=(rear+1)％(m-1) C.rear=(rear+1)％m D.rear=(rear+1)％(m+1) 14.关于串的的叙述，不正确 ．．．的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为( ) A.i(i-1)／2+j B.j(j-1)／2+i C.i(j-i)／2+1 D.j(i-1)／2+l 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.下列程序段的时间复杂度为____________。 for(i=1；i<=n；i++) for(j=1；j<=n；j++) for(k=1；k<=n；k++) s=i+j+k； 17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。

2020年10月全国数据结构导论自考试题及答案解析.doc

??????????????????????精品自学考料推荐?????????????????? 全国 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. 必大于 0 B. 必等于 0 C.必等于 1 D. 必等于 2 8.二叉树若采用二叉链表结构表示，则对于n 个结点的二叉树一定有（） A.2n 个指针域其中n 个指针为 NULL B.2n 个指针域其中n+1 个指针为 NULL C.2n-1 个指针域其中n 个指针为 NULL D.2n-1 个指针域其中n+1 个指针为 NULL 9.在一个无向图中，所有顶点的度数之和等于边数的（） A.1 倍 B.2 倍 C.3 倍 D.4 倍 10.若采用邻接表存储结构，则图的广度优先搜索类似于二叉树的（） 1

自考数据结构导论试题真题

全国 2004年 1 月高等教育自学考试 数据 结构导论试题 课程代码： 02142 、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分） 在每小题列出的四个备选项中只有一个是符合题目要求的， 请将其代码填写在题后的 括号内。错选、多选或未选均无分。 1．下列数据组织形式中， （ ）的各个结点可以任意邻接。 A ．集合 B ．树形结构 C ．线性结构 D ．图状结构 2．设某二维数组 A[ 1..n ，1..n]，则在该数组中用顺序查找法查找一个元素的时间复杂 性的量级为（ ） A ．O （log 2n ） B ． O （n ） 2 C ．O （nlog 2n ） D ．O （n 2） 3．在线性表的下列存储结构中，读取元素花费时间最少的是（ A ．单链表 B ．双链表 C ．循环链表 D ．顺序表 4．将一个头指针为 p 的单链表中的元素按与原单链表相反的次序存放，则下列算法段 中的空白处应为 q=NULL; while (p!=NULL) { ( D ． 5．数组通常具有两种基本运算， 即（ A ．创建和删除 C ．读和写 6．除根结点外，树上每个结点（ A ．可有任意多个孩子、任意多个双亲 B ．可有任意多个孩子、一个双亲 C ．可有一个孩子、任意多个双亲 D ．只有一个孩子、一个双亲 p=q; r=q; q=p; p=p -> next; q -> next=r; q=p; r=q; p=p -> next; q -> next=r; r=q; p=p -> next; q=p; q A ． B ． C ． ） B ．索引和修改

7．具有 100 个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、 右孩子，其余（）个指针域为空。 9．如果无向图 G 必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是（） A．G 肯定不是完全图B．G 一定不是连通图 C．G 中一定有回路D． G 有 2 个连通分量 10．若构造一棵具有 n 个结点的二叉排序树，最坏的情况下其深度不会超过（ ）A ． n/2 C．（n+1）/2 D． n+1 11．若用二分查找法取得的中间位置元素键值大于被查找值，说明被查找值位于中间值 的前面，下次的查找区间为从原开始位置至（） B．该中间位置－ 1 D ．该中间位置／ 2 ） B．索引存取 D．直接存取 13．若检索顺序文件各个记录的概率相同，设文件占用的页块数为n，则按关键字存取 时的平均访问外存次数为 （ ） A ．n/2 B ．n C ．n/4 D ． log n 1 4 ．下列关键码序列 中， 属于堆的是 （ ） A ．（15，30，22，93，52 ， 71) B ． （15 ， 71 ， 30 ， 22 ， 93 ， 52) C（15，52，22，3071) D（933052221571) 15．已知 10 个数据元素为（ 54，28， 16，34，73， 62，95，60，26，43），对该数列按从小到大排序，经过一趟冒泡排序后的序列为（） A16283454736260264395 B ．28 ， 16 ， 34 ， 54 ， 62 ， 73 ， 60 ， 26 ， 43 ， 95 C ．28 ， 16 ， 34 ， 54 ， 62 ， 60 ， 73 ， 26 ， 43 ， 95 D ．16 ， 28 ， 34 ， 54 ， 62 ， 60 ， 73 ， 26 ， 43 ， 95 A ． 50 C．100 8．邻接表是图的一种（ A ．顺序存储结构C．索引存储结构 B． 99 D．101 ） B．链式存储结构 B．n A ．该中间位置 C ．该中间位置＋ 1 12．散列文件不能（ A ．随机存取 C．按关键字存取

自考02142《数据结构导论》串讲笔记

第一张概论 1.1 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 处理要求-----基本运算和运算-------算法 1.2 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 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）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。

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

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.40 B.60 C.61 D.100 4.设带头结点的单循环链表的头指针为head，则判断该链表是否为空的条件是 A. head->next==head B. head->next==NULL C. head!=NULL D. head==NULL 5.在链栈的运算中，不需要 ．．．判断栈是否为空的是 A.出栈 B.进栈 C.取栈顶元素 D.求链栈的元素个数 6.一个队列的输入序列是A，B，C，D，则该队列的输出序列是 A.A，B，C，D B.B，C，D，A C.D，C，B，A D.C，D，B，A 7.以行序为主序的二维数组a［3］［5］中，第一个元素a［0］［0］的存储地址是100，每个元素占2个存储单元，则a［1］［2］的存储地址是 A.100 B.108 C.114 D.116 8.对任何一棵二叉树T，若叶结点数为5个，则度为2的结点个数为 A.4 B.5 C.6 D.无法确定 9.m个叶结点的哈夫曼树中，其结点总数为 A.m B.2m+1

自考02142《数据结构导论》串讲笔记

： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。

浙江省1月自学考试数据结构导论试题及答案解析

浙江省2018年1月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号 内。每小题1分，共14分) 1.计算机算法指的是( )。 A.计算方法 B.排序方法 C.解决某一问题的有限运算序列 D.调度方法 2.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s↑.next:=p；p↑.next=s; B. s↑.next:=p↑.next;p↑.next:=s； C. s↑.next:=p↑.next;p:=s; D. p↑.next:=s;s↑.next=p; 3.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地址是( )。 A.110 B.108 C.100 D.120 4.循环队列用数组A［0..m-1］存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素 个数是( )。 A.(rear-front+m) MOD m B.rear-front+1 C.rear-front-1 D.rear-front 5.栈和队列的共同特点是( )。 A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点 6.深度为n的二叉树中所含叶子结点的个数最多为( )个。 A.2n B.n C.2n-1 D.2n-1 7.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 8.下面的二叉树中，( )不是完全二叉树。 9.下列说法错误的是( )。

数据结构导论

数据结构导论const maxsize=顺序表的容量； typedf struct {datatype data[maxsize]; int last; {sqlist; sqlist L; 顺序表的插入算法： void insert_sqlist(sqlist L,datetype x,int i) { if(https://www.sodocs.net/doc/b411942927.html,st==maxsize)error(…表潢?)； if((i<1)||(i>https://www.sodocs.net/doc/b411942927.html,st+1))error(…非法位置?)； for(j=https://www.sodocs.net/doc/b411942927.html,st;j=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=X; https://www.sodocs.net/doc/b411942927.html,st=https://www.sodocs.net/doc/b411942927.html,st+1 } 顺序表的删除算法： void delete_sqlist(sqlist L,int i); { if((i<1)||(i>https://www.sodocs.net/doc/b411942927.html,st)) error(非法位置)； for(j=i+1;j=https://www.sodocs.net/doc/b411942927.html,st;j++) L.data[j-2]=L.data[j-1]; https://www.sodocs.net/doc/b411942927.html,st=https://www.sodocs.net/doc/b411942927.html,st-1 } 顺序表的查找算法： int locate_sqlist(sqlist L,datatype X) { i=1; while((i<=https://www.sodocs.net/doc/b411942927.html,st)&&(L.data[i-1]!=x)) i++; if(i<=https://www.sodocs.net/doc/b411942927.html,st) return(i) else return(0) } 单链表类型定义 typedef struct node *pointer; struct node {datatype data; pointer next; }; typedef pointer lklist;