02142数据结构导论2013年10月份真题及答案
绝密★考试结束前
全国2013年10月高等教育自学考试
数据结构导论试题
课程代码：02142
请考生按规定用笔将所有试题的答案涂、写在答题纸上。
选择题部分
注意事项：
1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。
2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。
1．下列几种算法时间复杂度中，最大的是
A．O（1） B.O（n）
C.O（nlog2n）
D.O（n2）
2．数据结构中结点按逻辑关系依次排列形成一条“链”的结构是
A．集合 B.图结构
C.树形结构
D.线性结构
3．在表长为100的顺序表中做插入运算，平均移动元素的次数为
A．25 B.33
C.50
D.100
4．已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为
A．O（1） B.O（log2n）
C.O（n）
D.O(n2)
5．下列表述正确的是
A．栈空时出栈产生“上溢”，栈满时进栈产生“下溢”
B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢”
C.栈空时出栈和栈满时进栈均产生“上溢”
D.栈空时出栈和栈满时进栈均产生“下溢”
6.队列操作的原则是
A.先进先出
B.后进先出
C.先进后出
D.只进不出
7．一棵深度为6的满二叉树有
A．63个结点 B.64个结点
C.127个结点
D.128个结点
8.在一棵度为3的树中，度为3的结点有4个，度为2的结点有2个，度为1的结点有3个，则度为0的结点有
A.8个
B.10个
C.11个
D.12个
9．一棵二叉树T，度为2的结点数为20个，则叶子结点数为
A．19个 B.20个
C.21个
D.22个
10．有10个叶结点的哈夫曼树中共有
A．10个结点 B.11个结点
C.19个结点
D.21个结点
11．求图中两个结点之间的最短路径采用的算法是
A．广度优先搜索（BFS）算法 B.克鲁斯卡尔（Kruskal）算法
C.普里姆（Prim）算法
D.迪杰斯特拉（Dijkstra）算法
12．顺序查找算法的平均查找长度为
A．log2n B.（n-1）/2
C.n/2
D.（n+1）/2
13．二叉排序树中，根的
A．左子树是二叉排序树、右子树不一定是二叉排序树
B.左子树是二叉排序树、右子树也是二叉排序树
C.左子树不一定是二叉排序树、右子树是二叉排序树
D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树
14．冒泡排序的时间复杂度为
A．O(n) B.O(nlog2n)
C.O(n2)
D.O(log2n)
15．关于稳定性的表述，正确的是
A．稳定性是排序方法本身的特性，与数据无关
B.稳定性不是排序方法本身的特性，与数据有关
C.稳定性是排序方法本身的特性，与数据有关
D.稳定性不是排序方法本身的特性，与数据无关
非选择题部分
注意事项：
用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
二、填空题(本大题共13小题，每小题2分，共26分)
16．数据中不可分割的最小标识单位是___数据项_______。
17．双向循环链表中，在p 所指结点的后面插入一个新结点*t ，需要修改四个指针，分别为：t->prior=p ；__t->next=p->next________；p->next->prior=t ；p->next=t ；。
18.在带有头结点的循环链表中，头指针为head ，判断指针p 所指结点为首结点的条件是_p==head->next;_________。
19．元素的进栈次序为1，2，3，…，n ，出栈的第一个元素是n ，则第k 个出栈的元素是__n-k+1________。
20．在栈结构中，允许插入和删除的一端称为___栈顶_______。
21．100个结点的二叉树采用三叉链表存储时，空指针域NULL 有___102_______个。
22.某二叉树的先序遍历序列为ABKLMNO ，中序遍历序列为BLKANMO ，则该二叉树中结点A 的右孩子为结点__m______。
23．一个二叉树的最少结点个数为_____0_____。
24．图中第一个顶点和最后一个顶点相同的路径称为回路。除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路，称为_____简单回路____。
25．设查找表有n 个数据元素，则二分查找算法的平均查找长度为___(n+1)/2 log2(n+1) -1 _______。
26．用键值通过散列函数获取存储位置的这种存储方式构造的存储结构称为___散列表_______。
27．若在线性表中采用二分查找法查找元素，则该线性表必须按值有序，并且采用___顺序_______存储结构。
28．堆分为最小堆和最大堆，若键值序列{k 1,k 2,…，k n }，满足i
2i i 2i 1k k n (i 1,2,,)k k 2+≥⎧⎢⎥=⎨⎢⎥≥⎣⎦
⎩，则这n 个键值序列{k 1,k 2,…，k n }是___最大堆_______。
三、应用题(本大题共5小题，每小题6分，共30分)
29．设一个链栈的输入序列为X ，Y ，Z ，试写出出栈的所有可能的输出序列及其操作步骤。
30．设二叉树的先序遍历序列为DCBAHEIFG ，中序遍历序列为ABCHDIEFG ，试画出该二叉树并写出后序遍历序列。
31．已知连通带权图如题31图所示，试利用普里姆（Prim ）算法，从顶点A 出发，构造它的最小生成树，画出构造过程。
题31图
32．给定表（28，15，55，3，71，75，10，22，56），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。
33．应用直接选择排序算法，对初始关键字序列为48，35，61，98，82，18，29，48的记录进行从小到大排序，写出排序过程和结果。
四、算法设计题(本大题共2小题，每小题7分，共14分)
34.单链表的结点结构定义如下：
typedef struct node
{ int data;
struct node *next;
}Node, *LinkList;
试编写在带头结点的单链表head中查找第1个元素值小于x的结点的实现算法Node *GetLinklist(LinkList head，int x)，若找到，则返回指向该结点的指针，否则返回NULL。
35．假设树采用孩子兄弟链表表示法，其结构定义如下：
typedef struct tnode
{ DataType data;
struct tnode *son, *brother;
}*Tree;
试编写算法void leveltree(Tree root)实现树的按层次遍历。
浙江省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.下列说法错误的是( )。
02142数据结构导论2013年10月份真题及答案
绝密★考试结束前 全国2013年10月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列几种算法时间复杂度中，最大的是 A．O（1） B.O（n） C.O（nlog2n） D.O（n2） 2．数据结构中结点按逻辑关系依次排列形成一条“链”的结构是 A．集合 B.图结构 C.树形结构 D.线性结构 3．在表长为100的顺序表中做插入运算，平均移动元素的次数为 A．25 B.33 C.50 D.100 4．已知尾指针的单向循环链表中，在第一个结点后面插入一个新结点，该算法的时间复杂度为 A．O（1） B.O（log2n） C.O（n） D.O(n2) 5．下列表述正确的是 A．栈空时出栈产生“上溢”，栈满时进栈产生“下溢” B.栈空时出栈产生“下溢”，栈满时进栈产生“上溢” C.栈空时出栈和栈满时进栈均产生“上溢” D.栈空时出栈和栈满时进栈均产生“下溢” 6.队列操作的原则是
A.先进先出 B.后进先出 C.先进后出 D.只进不出 7．一棵深度为6的满二叉树有 A．63个结点 B.64个结点 C.127个结点 D.128个结点 8.在一棵度为3的树中，度为3的结点有4个，度为2的结点有2个，度为1的结点有3个，则度为0的结点有 A.8个 B.10个 C.11个 D.12个 9．一棵二叉树T，度为2的结点数为20个，则叶子结点数为 A．19个 B.20个 C.21个 D.22个 10．有10个叶结点的哈夫曼树中共有 A．10个结点 B.11个结点 C.19个结点 D.21个结点 11．求图中两个结点之间的最短路径采用的算法是 A．广度优先搜索（BFS）算法 B.克鲁斯卡尔（Kruskal）算法 C.普里姆（Prim）算法 D.迪杰斯特拉（Dijkstra）算法 12．顺序查找算法的平均查找长度为 A．log2n B.（n-1）/2 C.n/2 D.（n+1）/2 13．二叉排序树中，根的 A．左子树是二叉排序树、右子树不一定是二叉排序树 B.左子树是二叉排序树、右子树也是二叉排序树 C.左子树不一定是二叉排序树、右子树是二叉排序树 D.左子树不一定是二叉排序树、右子树也不一定是二叉排序树 14．冒泡排序的时间复杂度为 A．O(n) B.O(nlog2n) C.O(n2) D.O(log2n) 15．关于稳定性的表述，正确的是 A．稳定性是排序方法本身的特性，与数据无关 B.稳定性不是排序方法本身的特性，与数据有关 C.稳定性是排序方法本身的特性，与数据有关 D.稳定性不是排序方法本身的特性，与数据无关
2013年1月数据结构导论试题与答案
绝密★考试结束前 全国2013年1月高等教育自学考试 数据结构导论试题 课程代码：02142 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.数据的基本单位是 A.数据元素 B.数据项 C.字段 D.域 2.算法的空间复杂度是指 A.算法中输入数据所占用的存储空间的大小 B.算法本身所占用的存储空间的大小 C.算法中所占用的所有存储空间的大小 D.算法中需要的辅助变量所占用存储空间的大小 3.从一个长度为100的顺序表中删除第30个元素,需向前移动的元素个数为 A.29 B.30 C.70 D.71 4.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是 A.单链表 B.双链表 C.单循环链表 D.顺序表 5.判断链栈LS是否为空的条件是
C.LS! =NULL D.LS= =NULL 6.关于链队列的运算说法正确的是 A.入队列需要判断队列是否满 B.出队列需要判断队列是否空 C.入队列需要判断队列是否空 D.出队列需要判断队列是否满 7.元素的进栈次序为A,B,C,D,E,则出栈中不可能 ．．．的序列是 A.A,B,C,D,E B.B,C,D,E,A C.E,A,B,C,D D.E,D,C,B,A 8.具有63个结点的完全二叉树是 A.满二叉树 B.二叉排序树 C.哈夫曼树 D.空树 9.将含有80个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是 A.左孩子编号为79，右孩子编号为80 B.左孩子不存在，右孩子编号为80 C.左孩子编号为80，右孩子不存在 D.左孩子不存在，右孩子不存在 10.将题10图所示的一棵树转换为二叉树，结点D是 A.A的右孩子 B.B的右孩子 C.C的右孩子 D.E的右孩子 11.无向图的邻接矩阵是题10图 A.对称矩阵 B.稀疏矩阵 C.对角矩阵 D.上三角矩阵 12.图的广度优先搜索遍历的过程类似于树的 A.前序遍历 B.中序遍历 C.后序遍历 D.按层次遍历 13.要解决散列引起的冲突问题，最常用的方法是 A.数字分析法、除留余数法、平方取中法 B.除留余数法、线性探测法、平方取中法 C.线性探测法、二次探测法、链地址法 D.除留余数法、线性探测法、二次探测法 14.下列表述中，正确的是 A.序列（102，81，55，62，50，40，58，35，20）是堆
全国自学考试数据结构导论试题及答案4套
全国自学考试数据结构导论试题及答案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. 链地址法
2020年10月自考02142数据结构导论试题
全国2020年10月高等教育自学考试数据结构导论试题， 课程代码:02142 1.请考生按规定用笔将所有试题的答案涂、写在答题纸上。 2.答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 选择题部分 注意事项: 每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。 一、单项选择题:本大题共15小题,每小题2分,共30分。在每小题列出的备选项中只有一项是最符合题目要求的,请将其选出。 1.数据的最小标识单位是 A.数据项 B.数据类型 C.数据元素 D.数据变量 7.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉树中共有结点个数是 A.2n B. n+l C.2n一1 D.2n+ l 8.设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号,若结点i有左孩子,则编号为i结点的左孩子结点的编号为 A.2i十1
B.2i C. i/2 D.2i- 1 9.已知一棵二叉树的先序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为 A. CBEFDA B. FEDCBA C. CBEDFA D. CEFBDA 10.一个具有n个顶点的无向完全图的边数为 非选择题部分 注意事项: 用黑色字迹的签字笔或钢笔将答案写在答题纸上.不能答在试题卷上。 二、填空题:本大题共13空,每空2分,共26分。 16.数据的四类基本逻辑结构是:线性结构、树形结构、图结构和__________。 17.数据的存储结构有顺序存储、链式存储、索引存储和_________存储。 18.顺序表插人算法的时间复杂度是___________。 33.对于给定的一- 组键值:83.40.63.13,84.35.96.57.39,79.61.15.请分别写出直接选择排序和冒泡排序的第一-趟排序结果。 四、算法设计题:本大题共2小题,每小题7分,共14分。 34.写出一个将线性表的顺序表存储方式(数组a、表长为n)改成单链表存储方式(其头结点由头指针head指向)的算法。设函数头为:Node * CreateLinkedList(DataType a[ ],int n) 35.以二叉链表作存储结构,请写出二叉链表类型定义;利用二叉树遍历的递归算法,试编写求二叉树高度的算法。 答案暂缺。
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
最新10月全国自学考试数据结构导论试题及答案解析
全国2018年10月自学考试数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.在表长为n 的顺序表上做插入运算，平均要移动的结点数为（ ） A.n/4 B.n/3 C.n/2 D.n 2.顺序表中有19个元素，第一个元素的地址为200，且每个元素占一个字节，则第14个元素的存储地址为（ ） A.212 B.213 C.214 D.215 3.由顶点V 1，V 2，V 3构成的图的邻接矩阵为⎥⎥⎥⎦ ⎤⎢⎢⎢⎣⎡010100110，则该图中顶点V 1的出度为（ ） A.0 B.1 C.2 D.3 4.元素的进栈次序为A ，B ，C ，D ，E ，则退栈中不可能．．． 的序列是（ ） 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的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（ ） A.23 B.37 C.44 D.46 6.在已知尾指针的单循环链表中，插入一个新结点使之成为首结点，其算法的时间复杂度为（ ） 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的元素时，查找成功时需比较的次数为（ ） A.1 B.2 C.3 D.4 8.在查找顺序表各结点概率相等的情况下，顺序按值查找某个元素的算法时间复杂度为 （ ）
10月全国数据结构导论自考试题及答案解析
全国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/2 C．n+1 D．(n+1)/2 5．下列树U′，经剪技运算DELETE（U′，x，2）后为（） 6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（） A．2，14 B．2，15 C．3，14 D．3，15 7．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一 1
堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（） A．116 B．118 C．120 D．122 8．一个带权的无向连通图的最小生成树（） 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分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。 2
全国10月高等教育自学考试数据结构导论试题及答案解析
全国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的存储结构。设有n个结点、e条弧，则拓扑排序的时间复杂度为（） A.O(n) B.O(n+e) C.O(e) D.O(n*e) 9．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）
02142数据结构导论201610
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图所示，则该树的高度是
02142数据结构导论201410试题及答案
2014年10月高等教育自学考试全国统一命题考试 数据结构导论试卷 (课程代码02142) 本试卷共5页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡"的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0.5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的。请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。 1．下列算法的时间复杂度为B 2．根据数据元素之间关系的不同特性，通常将数据结构分为四类基本结构，即 A．集合、顺序结构、树形结构、图结构 B．集合、线性结构、链式结构、图结构 C．集合、线性结构、树形结构、图结构 D．线性结构、顺序结构、链式结构、图结构 3．在表长为101的顺序表中做删除运算，平均移动元素的次数为 A．25 B．50 C．5l D．100 4．在表长为n的顺序表中做插入运算的时间复杂度为A 5．单链表与顺序表相比，其特点是 A．运算算法实现简单 B．便于随机存取数据 C．不需要预先分配存储空间 D．结点个数受到限制 6．关于链栈的说法，正确的是 A．链栈不用预先考虑容量的大小 B．链栈出栈时不需要判断栈空 C．链栈进栈时需要判断栈满 D．链栈出栈时需要判断栈满 7．循环队列存储在数组A[m]中，则入队列操作中队列尾指针rear的变化为 A．rear=rear+1 B．rear=(rear+1)％(m一1)
02142《数据结构导论》复习题.
数据结构导论模拟试题 一、考试题型及分值分布： 1、单项选择题(本大题共15小题，每小题2分，共30分) 2、填空题(本大题共13小题，每小题2分，共26分) 3、应用题(本大题共5小题，每小题6分，共30分) 4、算法设计题(本大题共2小题，每小题7分，共14分) 二、单项选择题和填空题样题参考 （一）单项选择题 1. 在二维数组中，每个数组元素同时处于（）个向量中。 A. 0 B. 1 C. 2 D. n 2. 已知单链表A长度为m，单链表B长度为n，它们分别由表头指针所指向，若将B 整体连接到A的末尾，其时间复杂度应为（）。 A. O(1) B. O(m) C. O(n) D. O(m+n) 3. 假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 4. 若让元素1,2,3依次进栈，则出栈次序不可能出现( )种情况。 A. 3,2,1 B. 2,1,3 C. 3,1,2 D. 1,3,2 5. 图的广度优先搜索类似于树的（）遍历。 A. 先根 B. 中根 C. 后根 D. 层次 6. 下面程序段的时间复杂度为( )。 for(int i=0; i
2023年全国自学考试数据结构导论试题及答案4套
全国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={
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.2i B.2i C.2i-1 D.2i-1 10.设单链表中指针p指向结点A，若要删除A旳直接后继，则所需修改指针旳操作为 ( ) A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p 11.下列排序算法中，某一趟结束后未必能选出一种元素放在其最终位置上旳是( ) 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，则使其平衡旳调整措施为( )
全国自学考试数据结构导论试题及答案（4套）
全国自学考试数据结构导论试题及答案（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.栈 9.二叉树的第i（i≥1）层上所拥有的结点个数最多为( ) A.2i B.2i C.2i-1 D.2i-1 10.设单链表中指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为 ( ) A.p->next=p->next->next B.p=p->next C.p=p->next->next D.p->next=p 11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最
数据结构导论自考题-2_真题(含答案与解析)-交互
数据结构导论自考题-2 (总分100, 做题时间90分钟) 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的。 1. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) A．存储结构B．存储实现 C．逻辑结构D．运算实现 SSS_SIMPLE_SIN A B C D 分值: 2 答案:C 2. 所有的存储结点存放在一个连续的存储空间，该存储方式是( )存储方式。 A．顺序B．链式 C．索引D．散列 SSS_SIMPLE_SIN A B C D 分值: 2 答案:A [解析] 本题主要考查的知识点是顺序存储方式。 [要点透析] 顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。 3. 设线性表有n个元素，以下操作中，( )在顺序表上实现比在链表上实现效率更高。 A．输出第i(1≤i≤n)个元素值B．交换第1个元素与第2个元素的值 C．在第i个元素前插入一个元素D．删除第i个元素 SSS_SIMPLE_SIN A B C D 分值: 2 答案:A [解析] 本题主要考查的知识点为顺序表和链表。 [要点透析] 由于顺序表具有随机存取特性，所以和链表相比输出第i个元素时效率很高。本题答案为A。 4.
与单链表相比，双链表的优点之一是( ) A．插入、删除操作更简单B．可以进行随机访问 C．可以省略表头指针或表尾指针D．前后访问相邻结点更灵活 SSS_SIMPLE_SIN A B C D 分值: 2 答案:D 5. 循环队列的队满条件为( ) A．(CQ.rear+1)%maxsize==(CQ.front+1)%maxsize B．(CQ.rear+1)%maxsize==CQ.front+1 C．(CQ.rear+1)%maxsize==CQ.front D．CQ.rear==CQ.front SSS_SIMPLE_SIN A B C D 分值: 2 答案:C [解析] 本题主要考查的知识点是循环队列的队满条件。 [要点透析] 约定循环队列的队头指针指示队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。当队尾指针“绕一圈”后赶上队头指针时，视为队满。 6. 数组A[0...5][0...5]的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是( ) A．1175 B．1180 C．1205 D．1210 SSS_SIMPLE_SIN A B C D 分值: 2 答案:A 7. 若二叉树(如图所示)采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，最合适的遍历方法是( ) A．先序遍历B．中序遍历 C．后序遍历D．按层次遍历 SSS_SIMPLE_SIN A B C D 分值: 2
自学考试02142《数据结构导论》串讲笔记
第一概论 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）为基本运算。 将逻辑结构S和在S上的基本运算集X的整体（S,X）称为一个数据结构。数据结构包括逻辑结构和处理方式。 1.3 存储实现和运算实现 由于逻辑结构是设计人员根据解题需要选定的数据组织形式，因此存储实现建立的机表示应遵循选定的逻
- 2013年算法与数据结构文档.doc
- E__Temp2_2013数据结构试题
- 02142数据结构导论2013年10月份真题及答案
- 数据结构复习答案2013-1
- 院校资料-北京理工大学2013级数据结构B试题(A卷)-答案
- 数据结构真题2013年10月
- 2013年算法与数据结构文档
- 02331数据结构 全国13年10月自考 试题
- 02331数据结构2012年10月份历年真题02331数据结构2013年1 月份历年真题附答案
- 数据结构课件(2013年)zy (1)
- 2013数据结构 学生信息管理系统-大二
- 2013年数据结构试题集(10套题并附带答案)
- 2013年数据结构试题集10套题并附带答案
- 数据结构(本)期末综合练习(2013年12月)
- 2013年暨南大学830数据结构考研试题
- [考试必备]2013年深圳大学801数据结构考研试题
- 真题_2013年_数据结构
- 数据结构教程图2013
- 2012-2013数据结构
- 2013年10月自学考试数据结构导论试题及答案