数据结构导论2142复习资料
第一章概论
1，数据表示：将数据从机外表示转化为机内表示。变化过程：机外表示->逻辑结构->存储结构。
2，数据处理：计算机执行对机内表示的数据的各种操作从而实现处理要求，得到所需结果。
过程：处理要求->基本运算和运算->算法
3，计算机专业人员的两项基本任务：数据表示和数据处理。
4，从数据结构观点看，通常的数据分为三个层次：数据、数据元素、数据项。
5，凡能被计算机存储、加工的对象通称为数据。
6，数据元素是数据的基本单位，具有完整确定的实际意义，又称为元素，结点，顶点或记录。
7，数据项是数据的不可分割的最小单位，不具备完整确定的实际意义，又称字段、域。数据元素由数据项组成。8，逻辑关系是指数据元素之间的关联方式或称邻接关系
9，数据元素之间逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。
10，数据逻辑结构四种基本形式：集合、线性结构、树形结构、图状结构。
11，集合：任何两个结点之间都没有逻辑关系，组织形式松散。
12，线性结构：结点按逻辑关系依次排列成一条锁链。
13，树形结构：具有分支、层次特点，其形态类似自然界中的树。
14，图状结构：各个结点按逻辑关系相互缠绕，任何两个结点都可以邻接。
15逻辑结构与数据元素本身形式、内容无关。逻辑结构与数据元素相对位置无关。逻辑结构与结点个数无关。
16，在数据的逻辑结构上规定的某种操作称为运算。运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。这种加工以一个或多个逻辑结构及其他有关参数为对象，以经过修改的逻辑结构或从原逻辑结构中提取的有关信息为结果。
17，运算两种基本类型：加工型运算和引用型运算。查找：找出满足某条件的结点在逻辑结构中的位置。
读取：读出某逻辑结构中指定位置的结点的内容。插入：在某逻辑结构中指定位置增加一个新结点。
删除：撤销某逻辑结构中指定位置的结点。更新：修改某逻辑结构中指定位置的结点内容。
18，数据结构中将数据的组织形式（逻辑结构）和对数据的操作方式（基本运算）作为一个整体来看待。
19，存储实现的目的是建立数据的机内表示。建立的数据的机内表示称为数据的存储结构。
20，一个存储结构分为三个部分：存储节点，数据元素之间的关联方式，附加设施。
21，四种基本存储结构：顺序存储结构，链式存储结构，索引存储结构，散列存储结构。（理解四种形式）
22，算法是计算机科学的一个基本概念，也是程序设计的一个核心概念。一个算法规定了求解给定问题所需要的所有处理步骤及其执行顺序，使得给定类型的任何问题都能在有限时间内被机械的求解。
23，任何算法都是用某种语言加以描述的。三类：程序（计算机语言描述算法），伪语言算法，非形式算法。
24，非形式算法：用自然语言同时可能还使用了程序设计语言或伪语言描述的算法。
25，评价算法的4个方面：正确性，易读性，健壮性，高效性。高效性是指算法的时间性能和空间性能。
26，算法在给定输入下的计算量：a，根据问题特点合理选择一种多多种“标准操作”。b，确定算法在给定输入下执行了多少次标准操作，并将此次数规定为该算法在给定输入下的计算量。
27，以算法在所有输入下的计算量的最大值作为算法的计算量，称为算法的最坏情况的时间复杂度
28，以算法在所有输入下的计算量的加权平均值作为算法的计算量，称为算法的平均时间复杂度
29，算法的输入规模或问题的规模是指该算法输入的数据所含数据元素的数目或与此数目相关的其他参数。
30，常见的时间复杂度量级：常数阶O(1)，对数阶O(log2n)，线性阶O(n)，平方阶O(n2)，指数阶O(2n)。
通常认为具有指数阶量级的算法是实际不可计算的，低于平方阶的算法是高效的。
31，空间复杂度是除输入数据所占用存储空间之外所需要的附加的存储空间的大小。
第二章线性表
1，线性结构是n个结点的有穷序列。（a1，a2，a3…..an）。注意：起始结点，终端结点，直接前趋，直接后继
2，线性结构的节本特征：若至少含有一个结点，则除起始结点没有直接前趋外其他结点都有唯一一个直接前驱，除终端结点没有直接后继外其他每个结点都有唯一一个直接后继。
3，线性表的逻辑结构是线性结构。表中所含结点个数为线性表的长度，若表长为0则称空表
4，线性表的基本操作：
Initate（L）初始化线性表L，
Length（L）求线性表L长度，Get（L，i）读取线性表L中的第i个数据元素，
Locate（L，x）在线性表L中查找值为x的数据元素的位置，
Insert（L，x，i）将值为x的数据插入到线性表L的第i位置，
Delete（L，i）从线性表L中删除第i个数据元素
5，顺序表：是线性表的顺序存储结构，即按照顺序存储方式构造的线性表的存储结构，顺序表的一个存储结点存储线性表的一个数据元素，所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列。
6，顺序表的类型定义：
Const maxsize=顺序表容量//maxsize表示线性表中可容纳数据的个数
Typedef struct
{ datatype data[ maxsize ]; //data是数组，线性表的第1,2,3,…n个数据元素存入data[0], data[1],data[2]…. data[n-1]中Int last ; //last表示线性表的长度，maxsize表示
} sqList;
sqList L;
顺序表是用一维数组实现的线性表，数组下标是元素的相对地址，逻辑上相邻的元素存储在物理位置也相邻的单元中7，顺序表的插入算法
Void inset（sqlist L，datatype x，int i ）
{ if （https://www.wendangku.net/doc/5e18226880.html,st = = maxsize ）error (“表满”);
if （i<1 || i>https://www.wendangku.net/doc/5e18226880.html,st +1 ）error (“位置非法”);
for ( j = https://www.wendangku.net/doc/5e18226880.html,st ; j>=i ; j-- )
L.data[j]=L.data[j-1]
L.data[i-1]=x;
https://www.wendangku.net/doc/5e18226880.html,st =https://www.wendangku.net/doc/5e18226880.html,st +1;
}
8，顺序表的删除算法
Void Delete（sqlist L，int i ）
{ if （i<1 || i>https://www.wendangku.net/doc/5e18226880.html,st +1 ）error (“位置非法”);
for ( j = i+1; j<= https://www.wendangku.net/doc/5e18226880.html,st; j-- )
L.data[j-2]=L.data[j-1]
https://www.wendangku.net/doc/5e18226880.html,st =https://www.wendangku.net/doc/5e18226880.html,st -1;
}
9，顺序表的定位算法
Int Locate （qslist L，datatype x）
{ i=1；
While （i<=https://www.wendangku.net/doc/5e18226880.html,st && L.data[i-1] != x）i++;
If ( i<=https://www.wendangku.net/doc/5e18226880.html,st ) return I;
Else return 0;
}
在以上3个算法基础上能设计出简单顺序表相关算法
10，顺序表插入算法平均移动次数：n/2，时间复杂度O（n）
顺序表删除算法平均移动次数：n-1/2，时间复杂度O（n）
顺序表定位，读表元，求表长算法复杂度O（1）
11，顺序表的优点：无需为表结点逻辑关系而增加额外的存储空间；可以方便的随机存取表中任一结点；
顺序表的缺点：插入和删除操作除表尾位置外要做大量移动效率较低，要求占用连续内存空间
12，单链表的基本思想是用指针表示结点之间的逻辑关系。节点分为两部分：data和next
Data部分称为数据域，next部分称为指针域或链域。所有节点通过指针的链接而组织成为单链表。NULL表示空指针，head称为头指针变量指向单链表中的第一个结点。
13，链表结点类型定义：
Typedef struct node * pointer ；
Struct node
{ datatype data；
Point next；
}；
Typedef pointer lklist；
Pointer是指向struct node 类型的指针类型，struct node 是结构体类型，即结点类型
指针的概念是链式存储结构的核心。
14，通常在单链表的第一个数据结点之前增设一个与结点类型相同但不存数据的结点称为头结点，其他为表结点，表中第一个和最后一个称为首节点和尾结点。带头单链表的图示形式：
15，单链表求表长算法
Int length（lklist head）
{ p=head；j=0；
While（p->next!=NULL）{ p=p->next ; j++; }
Return j;
}
16，单链表定位算法
Int Locate （lklist head ，datatype x）
{ p=head；j=0；
While（p->next !=NULL && p->data !=x）
{ p=p->next ; j++; }
If ( p->data = = x) return j; Else return 0;
}
17，单链表的删除算法
void delete (lklist head, int i)
{ p=head; j=0；
While （p->next !=NULL && j
if ( p！=NULL && p->next!=NULL )
{ q=p->next; p->next=q->next; free(q); }
else error(”不存在第i个结点”);
}
18，单链表插入算法
void insert (lklist head, datatype x，int i)
{ p=head; j=0；
While （p->next !=NULL && j
if (p！=NULL ) { s=()malloc(); s->data=x; s->next=p->next; p->next=s; }
else error(“不存在第i个位置”);
}
在以上4个算法基础上能设计出简单单链表相关算法
19，循环链表的主要优点是从链表中任何一结点出发能通过后移操作而扫描整个循环链表。图示：
循环链表判空：若head->next = = head 则循环链表空。
20，双向链表：
双向链表插入（在p所指结点后插入q所指结点）：q->prior=p; q->next= p->next; p->next->prior=q; p->next =q;
双向链表删除（删除p所指结点）：p->prior->next=p->next; p->next->prior=p->prior;
21，存储结点中数据域占用的存储量与整个存储结点中用存储量之比称为存储密度。
顺序表空间利用率高于链表，顺序表实现要求事先估计容量，估计过大浪费空间，估计过小导致溢出。
第三章栈、队列和数组
1，栈是一个特殊的线性表，插入和删除操作限定在表的某一端进行，允许插入和删除的一端为栈顶，另一端为栈底。处于栈顶位置的数据元素为栈顶元素，不含任何数据元素的栈称为空栈。
2，栈的顺序存储结构称为顺序栈。顺序栈是由一个数组和一个记录栈顶位置的变量组成。
#define maxsize 栈容量
Typedef struct sqstack
{ datatype data[maxsize];
Int top;
}sqstack;
3，对于顺序栈，约定top值为0表示栈空，栈非空时top值表示栈顶元素的下标位置，入栈时top先加1 栈空：s.top= =0 栈满：s.top= = maxsize -1
栈空时进行出栈操作则产生“下溢”
栈满时进行入栈操作则产生“上溢”
4，顺序栈S进栈操作：S->top=s->top+1; s->data[s->top]=x;
5，顺序栈S出栈操作：*x= s->data[s->top]；S->top=s->top-1;
6，队列是一种运算受限的线性表，插入限定在表的一端，删除限定在表的另一端，允许插入的一端为队尾，允许删除的一端为队头。队列是先进先出的线性表。
7，队列的顺序实现称为顺序队，它由一个一维数组及两个分别指示队头和队尾的变量组成，这两个变量分别称为队头指针和队尾指针。通常约定队尾指针指示对为元素在一维数组中的当前位置，队头指针指示队头元素在一维数组中的当前位置的前一个位置。
8，顺序队列的类型定义
#define maxsize 队列容量
Typedef struct sqqueue
{ datatype data[maxsize];
Int front , rear;
} sqqueue;
9，入队操作时，队中存储空间未满，而rear已指向数组末尾无法进行入队操作，这是一种“假溢出”
10，将队列设置为循环链表，设置数组首尾相连，当rear=maxsize -1时入队则若数组低端仍有空闲空间则令rear置为0。11，循环队列的入队操作：sq.rear= (sq.rear+1) % maxsize; sq.data[sq.rear] =x;
12，循环队列的出队操作：sq.front=(sq.front +1 ) % maxsize;
13，循环队列判满条件：若(sq.rear+1) % maxsize = = sq.front 则表示循环队列满
14，循环队列判空的条件：若sq.rear = = sq.front 则表示队列空
15，n维数组可视为其数据元素为n-1维数组的线性表。数组通常只有两中基本运算：读，写。
16，二维数组的机器级实现通常采用顺序存储结构来存放数组，一般两种存储方法：以行优先存储，以列优先存储理解如何计算数组中第i元素的地址
17，压缩存储的思想是：值相同的多个元素只分配一个存储空间，零元素不分配空间。
18，要压缩存储的矩阵分为两种：特殊矩阵和稀疏矩阵。
对称矩阵可压缩到n（n+1）/2个空间内。
对称矩阵的下三角部分按行优先存入一维数组M是，矩阵行号列号与M下标对应关系。
下三角矩阵按行优先存入一维数组M是，矩阵行号列号与M下标对应关系。
上三角矩阵按行优先存入一维数组M是，矩阵行号列号与M下标对应关系。
19，稀疏矩阵压缩存储时只存储非零元素，对每个非零元素存放行号，列号，元素值：（i，j，aij）写出矩阵的三元组，根据三元组写出矩阵
第四章树
1，树是n个结点的有穷集合：1）有且仅有一个称为根的结点。2）其余结点分为m个互不相交的集合，每个都是一棵树，称为根的子树。树是一种分支层次结构。所谓分支是指树中任何一结点的子孙可以按他们所在的子树的不同而划分成不同的分支；所谓层次是指树上所有结点可以按他们的层数划分成不同的层次。
2，结点的度，叶子，终端结点，非终端结点，分支点，树的度，双亲，父节点，孩子，子结点，兄弟，子孙，祖先，结点的层数，树的高度或深度。
3，二叉树是结点的有穷集合，它或者是空集或者同时满足下述两个条件：1）有且仅有一个称为根的结点2）其余结点分为两个互不相交的集合T1，T2都是二叉树，且T1，T2有顺序分别称为左子树和右子树。
4，二叉树上的任何一个结点的子树都有左右之分，即使只有一棵子树的仍须区别它是左子树还是右子树。二叉树有5种基本形态：空二叉树，只含有根的二叉树，只含有非空左子树的二叉树，只含有非空右子树的二叉树，同时具有左子树和右子树的二叉树。
5，二叉树第i层上至多有2i-1个结点。深度为k的二叉树至多有2k-1个结点。
对任何二叉树若2度结点数为n2，则叶子结点数n0=n2+1。
深度为k且有2k-1个结点的二叉树称为满二叉树，深度为k的满二叉树上删去第k层上最右边连续j个结点后得到的深度为k的二叉树称为完全二叉树。
6，具有n个结点的完全二叉树的深度为|_log2n +1_|
如果有一棵n个结点的完全二叉树按层编号，则对任一编号为i的结点x有：
1）若i=1，则结点x是根，若i>1则x的双亲编号是i/2
2）若2i>n则x无左孩子，否则x的左孩子编号是2i
3）若2i+1>n则x无右孩子，否则x的右孩子编号是2i+1
7，二叉树通常有两种存储形式：顺序存储结构和链式存储结构。链式存储结构通常使用二叉链表和三叉链表。
二叉链表结点分为三个部分：lchild，data，rchild。Data域称为数据域存储数据元素，lchild存储左孩子指针，rchild 存储右孩子指针。二叉链表中指向根节点的指针称为根指针。二叉链表节点类型定义如下：
Typedef struct btnode *bitreptr；
Struct btnode
{ datatype data；
Bitreptr lchild，rchild；
}；
Bitreptr root；若root==NULL则树为空树，具有n个结点的二叉树一共有2n个指针域，其中n-1个用来指向左右孩子，其余n+1个为NULL。
8，二叉树的顺序存储结构由一个一维数组构成，二叉树上的结点按某种次序分别存入数组中。对完全二叉树上所有结点按层编号，则结点编号可以反映结点之间的逻辑关系。即将编号为i的结点存入数组的i元素中。对于非完全二叉树
则通过增加虚结点从而转换为一棵完全二叉树。
9，二叉树的遍历：按某种次序关系系统的访问二叉树上的所有节点，使得每个结点被访问一次。
二叉树遍历分为：先根遍历，中根遍历，后根遍历
先根遍历：先访问根节点，然后先根访问左子树，然后先根访问右子树
中根遍历：先中根访问左子树，然后访问根节点，然后中根访问右子树
后根遍历：先后根访问左子树，然后后根访问右子树，然后访问根节点
根据树写出对应遍历序列，根据两个遍历序列画出树，能写出三种遍历算法
10，树的存储结构通常有三种形式：孩子链表表示法，孩子兄弟链表表示法，双亲表示法三种结构图示
12，树转换为二叉树，森林转换为二叉树
自考数据结构导论20051年10月试卷
全国2005年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.若要描述数据处理的变化过程，其正确的次序应为( ) A.处理要求、基本运算和运算、算法 B.处理要求、算法、基本运算和运算 C.基本运算和运算、处理要求、算法 D.算法、处理要求、基本运算和运算 2.从运算类型角度考虑，属于引用型的运算是( ) A.插入、删除 B.删除、修改 C.查找、读取 D.查找、删除 3.若在长度为n的顺序表中插入一个结点，则其结点的移动次数( ) A.最少为0，最多为n B.最少为1，最多为n C.最少为0，最多为n+1 D.最少为1，最多为n+1 4.在一个单链表中，若p所指结点是q所指结点的前驱结点，则在结点p、q之间插入结点s的正确操作是( ) A.s->next=q；p->next=s->next B.p->next=q；p->next=s C.s->next=q->next；p->next=s D.s->next=q->next；p->next=s->next 5.若有一串数字5、6、7、8入栈，则其不可能 ．．．的输出序列为( ) A.5、6、7、8 B.8、7、6、5 C.8、7、5、6 D.5、6、8、7 6.FORTRAN语言对数组元素的存放方式通常采用( ) A.按行为主的存储结构 B.按列为主的存储结构 C.按行或列为主的存储结构 D.按行和列为主的存储结构 7.树是n个结点的有穷集合，( ) A.树的结点个数可以为0，此时称该树为空树 B.树至少含有一个根结点，不能为空 C.树至少含有一个根结点和一个叶子结点 D.树至少含有一个根结点和两个叶子结点 8.深度为k的二叉树至多有( ) A.2k个叶子 B.2k-1个叶子 C.2k-1个叶子 D.2k-1-1个叶子 9.具有10个顶点的有向完全图应具有( ) 浙02142# 数据结构导论试题第 1 页（共 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={
数据结构导论试题和部分答案
全国2012年1月数据结构导论试题课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( )A.集合 B.线性结构 C.树形结构 D.图状结 构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i 二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、二路归并排序 数据结构导论复习 第一章概论 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 ) 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++) 《数据结构导论》考纲、试题、答案 一、考试说明 本课程为闭卷考试（开卷考试、上交论文、上交作品等考查类课程无考试指导）（根据课程考核实际方式选择），考试时间90分钟，考试题型包括以下题型中的三种（根据每门课程的实际确定题型及分值所占比例）： 1、判断题（正确打√，错误打×，每题3分，共15分） 2、填空（每空2分，共20分） 3、选择题（每题3分，共15分） 4、名词解释（每小题4分，共20分） 5、简答题（每题6分，共30分） 备注：以上题型供参考 二、课程知识要点 第一章 ◆数据结构 ◆实例 第二章 ◆银行排队顺序存储 ◆学生健康登记表 第三章 ◆栈和队列 ◆回文 ◆杨辉三角 第四章 ◆串 ◆文本加密 第五章 ◆内部排序 ◆查找 ◆二叉树 第六章 ◆树 ◆图 ◆数组 第七章 ◆文件 ◆外部排序 备注：根据教材实际章节汇总要点，突出需要掌握的重点内容 三、重点习题 1、判断题 ◆具有n 个结点的线索二叉树上，含有n+1个线索。 ◆三叉链表属于二叉树存储结构。 ◆哈夫曼树不存在度为1的结点。 ◆栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 ◆栈和队列的存储方式既可是顺序方式，也可是链接方式。 ◆二叉树中每个结点的两棵子树是有序的。 2、填空 ◆数据的逻辑结构指 ◆一个算法的时间复杂度 ◆单链表中，增加头结点的目的 ◆表长为0的线性表 ◆串的长度 ◆若两个串的长度相等且对应位置上的字符也相等 ◆常用的插入排序 ◆常用的处理冲突的方法 ◆常用的选择排序方法 ◆衡量一个算法的优劣主要考虑 ◆在有n个结点的二叉链表中，空链域的个数 ◆常用的选择排序方法 全国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) 全国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.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为____________。 全国 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．按关键字存取 ??????????????????????精品自学考料推荐?????????????????? 全国 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 第一张概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。 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 全国2012年1月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是( ) A.集合 B.线性结构 C.树形结构 D.图状结构 2.下面算法程序段的时间复杂度为( ) for ( int i=0; i A. 先进先出的线性表 B. 先进后出的线性表 C. 后进先出的线性表 D.随意进出的线性表 8.10阶上三角矩阵压缩存储时需存储的元素个数为( ) A.11 B.56 C.100 D.101 9.深度为k（k≥1）的二叉树，结点数最多有( ) A.2k个 B.(2k -1)个 C.2k-1个 D.(2k+1)个 10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为( ) A. 11 B.13 C. 23 D. 25 11.具有n个顶点的无向图的边数最多为( ) A.n+1 B.n(n+1) C.n(n-1)/2 D.2n(n+1) 12.三个顶点v1,v2,v3的图的邻接矩阵为 010 001 010 ?? ?? ?? ?? ?? ，该图中顶点v3的入度为( ) A. 0 B. 1 C. 2 D. 3 13.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找 的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为( ) A.20000 B.30000 C.40000 D.60000 14.外存储器的主要特点是( ) A.容量小和存取速度低 B.容量大和存取速度低 C.容量大和存取速度高 D.容量小和存取速度高 15.在待排数据基本有序的前提下，效率最高的排序算法是( ) A.直接插入排序 B.直接选择排序 C.快速排序 D.归并排序 浙02142# 数据结构导论试题第 2 页共 5 页 ： 第一张概论 引言 两项基本任务：数据表示，数据处理 软件系统生存期：软件计划，需求分析，软件设计，软件编码，软件测试，软件维护 由一种逻辑结构和一组基本运算构成的整体是实际问题的一种数学模型，这种数学模型的建立，选择和实现是数据结构的核心问题。 机外表示------逻辑结构------存储结构 ~ 处理要求-----基本运算和运算-------算法 数据，逻辑结构和运算 数据：凡是能够被计算机存储，加工的对象通称为数据 数据元素：是数据的基本单位，在程序中作为一个整体加以考虑和处理。又称元素，顶点，结点，记录。 数据项：数据项组成数据元素，但通常不具有完整确定的实际意义，或不被当做一个整体对待。又称字段或域，是数据不可分割的最小标示单位。 — 1.2.2 数据的逻辑结构 逻辑关系：是指数据元素之间的关联方式，又称“邻接关系” 逻辑结构:数据元素之间逻辑关系的整体称为逻辑结构。即数据的组织形式。 四种基本逻辑结构： 1 集合：任何两个结点间没有逻辑关系，组织形式松散 2 线性结构：结点按逻辑关系依次排列成一条“锁链” 3 树形结构：具有分支，层次特性，形态像自然界中的树 { 4. 图状结构：各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接。 注意点: 1.逻辑结构与数据元素本身的形式，内容无关。 2.逻辑结构与数据元素的相对位置无关 3.逻辑结构与所含结点个数无关。 运算：运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。 。 加工型运算：改变了原逻辑结构的“值”，如结点个数，结点内容等。 引用型运算:不改变原逻辑结构个数和值，只从中提取某些信息作为运算的结果。 引用：查找，读取 加工：插入，删除，更新 同一逻辑结构S上的两个运算A和B, A的实现需要或可以利用B，而B的实现不需要利用A，则称A可以归约为B。 浙江省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.wendangku.net/doc/5e18226880.html,st==maxsize)error(…表潢?)； if((i<1)||(i>https://www.wendangku.net/doc/5e18226880.html,st+1))error(…非法位置?)； for(j=https://www.wendangku.net/doc/5e18226880.html,st;j=i;j--) L.data[j]=L.data[j-1]; L.data[i-1]=X; https://www.wendangku.net/doc/5e18226880.html,st=https://www.wendangku.net/doc/5e18226880.html,st+1 } 顺序表的删除算法： void delete_sqlist(sqlist L,int i); { if((i<1)||(i>https://www.wendangku.net/doc/5e18226880.html,st)) error(非法位置)； for(j=i+1;j=https://www.wendangku.net/doc/5e18226880.html,st;j++) L.data[j-2]=L.data[j-1]; https://www.wendangku.net/doc/5e18226880.html,st=https://www.wendangku.net/doc/5e18226880.html,st-1 } 顺序表的查找算法： int locate_sqlist(sqlist L,datatype X) { i=1; while((i<=https://www.wendangku.net/doc/5e18226880.html,st)&&(L.data[i-1]!=x)) i++; if(i<=https://www.wendangku.net/doc/5e18226880.html,st) return(i) else return(0) } 单链表类型定义 typedef struct node *pointer; struct node {datatype data; pointer next; }; typedef pointer lklist;数据结构导论年月试题
自考数据结构导论复习资料
自考数据结构导论
02142数据结构导论2010年1 月份真题及答案
《数据结构导论》考纲、试题、答案
全国数据结构导论10月高等教育自学考试试题与答案
2010年1月自考数据结构导论真题
自考数据结构导论试题真题
2020年10月全国数据结构导论自考试题及答案解析.doc
自考02142《数据结构导论》串讲笔记
02142数据结构导论份真题及答案.doc
自考数据结构导论20120年01月试卷
自考02142《数据结构导论》串讲笔记
浙江省1月自学考试数据结构导论试题及答案解析
数据结构导论
- 02142《数据结构导论》复习题.
- 数据结构导论复习题
- 自考数据结构导论复习资料
- “数据结构导论”的学习方法
- 数据结构导论练习题
- 数据结构导论练习题
- 复习总结资料(数据结构导论)
- 2020年10月自考02142数据结构导论试题及答案含评分标准
- 02142数据结构导论201410试题及答案
- 02142数据结构导论201310试题及答案
- 数据结构导论自考全书重点综合复习
- 全国自学考试数据结构导论试题及答案(4套)
- 全国2012年1月自考数据结构导论考试试题,答案,笔记
- 数据结构导论
- 全国2010年1月自考数据结构导论考试试题,答案,笔记
- 自考数据结构导论复习资料
- 自考数据结构导论试题真题
- 全国自学考试数据结构导论试卷与答案(4套)
- 4《数据结构导论》复习题
- 全国自学考试数据结构导论试题及答案(4套)