最新自考数据结构重点(珍藏版)
自考数据结构重点（周尧整理）
第一章概论
1.数据是信息的载体。
2.数据元素是数据的基本单位。
3.一个数据元素可以由若干个数据项组成。
4.数据结构指的是数据之间的相互关系，即数据的组织形式。
5.数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算
①数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。
②数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。
数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。
③数据的运算，即对数据施加的操作。最常用的检索、插入、删除、更新、排序等。
6.数据的逻辑结构分类:线性结构和非线性结构
①线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。
②非线性结构：一个结点可能有多个直接前趋和直接后继。
数组、广义表、树和图等数据结构都是非线性结构。
7.数据的四种基本存储方法:顺序存储方法、链接存储方法、索引存储方法、散列存储方法
（1）顺序存储方法：
该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常借助程序语言的数组描述。
（2）链接存储方法：
该方法不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于程序语言的指针类型描述。
（3）索引存储方法：
该方法通常在储存结点信息的同时，还建立附加的索引表。
索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。索引项的一般形式是：(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。
（4）散列存储方法：
该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。
8.抽象数据类型(ADT):是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。
抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。
9. 算法+数据结构=程序
数据结构：是指数据的逻辑结构和存储结构
算法：是对数据运算的描述
10. 数据的运算通过算法描述的。算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。
11. 选用的算法首先应该是"正确"的。此外，主要考虑如下三点：
①执行算法所耗费的时间；
②执行算法所耗费的存储空间，其中主要考虑辅助存储空间；
③算法应易于理解，易于编码，易于调试等等。
12. 一个算法所耗费的时间=算法中每条语句的执行时间之和，每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间。
13.算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。
14. 一个算法的时间复杂度T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。
15. 常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、…、k次方阶0(n k)、指数阶0(2n)。
16. 一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。
第二章线性表
1. 线性表（Linear List）是由n（n≥0）个数据元素（结点）a1,a2,…,a n组成的有限序列。
2. 线性表的逻辑结构特征，对于非空的线性表:
①有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2；
②有且仅有一个终结结点a n，没有直接后继，有且仅有一个直接前趋a n-1；
③其余的内部结点a i（2≤i≤n-1）都有且仅有一个直接前趋a i-1和一个a i+1。
3.常见的线性表的基本运算:
(1)InitList（L）构造一个空的线性表L，即表的初始化。
(2)ListLength（L）求线性表L中的结点个数，即求表长。
(3)GetNode（L，i）取线性表L中的第i个结点，这里要求1≤i≤ListLength（L）
(4)LocateNode（L，x）在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。
(5)InsertList（L，x，i）在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，…，n的结点变为编号为i+1，i+2，…，n+1的结点。这里1≤i≤n+1，而n是原表L的长度。插入后，表L的长度加1。(6)DeleteList（L，i）删除线性表L的第i个结点，使得原编号为i+1，i+2，…，n的结点变成编号为i，i+1，…，n-1的结点。这里1≤i≤n，而n是原表L的长度。删除后表L的长度减1。
4.顺序存储方法：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
顺序表（Sequential List）：用顺序存储方法存储的线性表简称为顺序表。顺序表是一种随机存取结构,顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。
5.顺序表中结点a i的存储地址: LOC（a i）= LOC（a1）+（i-1）*c 1≤i≤n，
6.顺序表上实现的基本运算：
（1）插入：在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。
具体算法：void InsertList(SeqList *L，DataType x，int i) //将新结点x插入L所指的顺序表的第i个结点a i的位置上
算法的时间主要花费在for循环中的结点后移语句上。该语句的执行次数是n-i+1，在表中第i个位置插入一个结点的移动次数为n-i+1，当i=n+1：移动结点次数为0，即算法在最好时间复杂度是O(1)，当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是O(n)
即在顺序表上进行插入运算，平均要移动一半结点（n/2）。
（2）删除：在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1≤i≤n-1，则必须将表中位置i+1，i+2，…，n的结点，依次前移到位置i，i+1，…，n-1上，以填补删除操作造成的空缺。
具体算法：void DeleteList(SeqList *L,int i) //从L所指的顺序表中删除第i个结点a i
结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0，即为0(1)，i=1时，结点的移动次数为n-1，
算法时间复杂度分别是O(n)
顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O(n)。
7. 链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为：用一组任意的存储单元来存放线性表的结点，链表中结点的逻辑次序和物理次序不一定相同（这组存储单元既可以是连续的，也可以是不连续的）。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）。
8. 链表的结点结构：data域--存放结点值的数据域，next域--存放结点的直接后继的地址（位置）的指针域（链域）
单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。终端结点无后继，故终端结点的指针域为空，即NULL。
9.①生成结点变量的标准函数p=( ListNode *)malloc(sizeof(ListNode))； //函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中②释放结点变量空间的标准函数free(p)；//释放p所指的结点变量空间③结点分量的访问方法二：p-﹥data和p-﹥next
④指针变量p和结点变量*p的关系:指针变量p的值——结点地址, 结点变量*p的值——结点内容
10.建立单链表:
（1）头插法建表：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。
算法： s=(ListNode *)malloc(sizeof(ListNode));①//生成新结点
s->data=ch; ② //将读入的数据放入新结点的数据域中
s->next=head;③
head=s;④
（2）尾插法建表：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表尾上,直到读入结束标志为止。
算法： s=(ListNode *)malloc(sizeof(ListNode)); ①//生成新结点
s->data=ch; ② //将读入的数据放入新结点的数据域中
if (head!=NULL)
head=s;//新结点插入空表
else
r->next=s;③//将新结点插到*r之后
r=s;④//尾指针指向新表尾
（3）尾插法建带头结点的单链表：
头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:
⒈由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;
⒉无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。
头结点数据域的阴影表示该部分不存储信息。在有的应用
中可用于存放表长等附加信息。
具体算法：r=head; // 尾指针初值也指向头结点
while((ch=getchar())!='\n'){
s=(ListNode *)malloc(sizeof(ListNode));//生成新结点
s->data=ch; //将读入的数据放入新结点的数据域中
r->next=s;
r=s;
}
r->next=NULL;//终端结点的指针域置空，或空表的头结点指针域置空
以上三个算法的时间复杂度均为O(n)。
11.单链表上的查找：
（1）链表不是随机存取结构
在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。（2）查找的思想方法
计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j 相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且j≠i时，则表示找不到第i个结点。头结点可看做是第0个结点。
算法：p=head;j=0;//从头结点开始扫描
while(p->next&&j
p=p->next;
j++;
}
if(i==j)
return p;//找到了第i个结点
else return NULL;//当i<0或i>0时，找不到第i个结点
时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n)
（2）按值查找：
具体算法：ListNode *p=head->next;//从开始结点比较。表非空，p初始值指向开始结点
while(p&&p->data!=key)//直到p为NULL或p->data为key为止
p=p->next;//扫描下一结点
return p;//若p=NULL，则查找失败，否则p指向值为key的结点
时间复杂度为：O(n)
12.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到a i-1与a i之间。
具体步骤：
（1）找到a i-1存储位置p
（2）生成一个数据域为x的新结点*s
（3）令结点*p的指针域指向新结点
（4）新结点的指针域指向结点a i。
具体算法：p=GetNode(head,i-1)①;//寻找第i-1个结点
if (p==NULL)//i<1或i>n+1时插入位置i有错
Error("position error")；
s=(ListNode *)malloc(sizeof(ListNode)); ②
s->data=x;③s->next=p->next④;p->next=s;⑤
算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。
13.删除运算
删除运算是将表的第i个结点删去。
具体步骤：
（1）找到a i-1的存储位置p（因为在单链表中结点a i的存储地址是在其直接前趋结点a i-1的指针域next中）（2）令p-＞next指向a i的直接后继结点（即把a i从链上摘下）
（3）释放结点a i的空间，将其归还给"存储池"。
\
具体算法：
p=GetNode(head,i-1);①//找到第i-1个结点
if (p==NULL||p->next==NULL)//i<1或i>n时，删除位置错
Error("position error");//退出程序运行
r=p->next;②//使r指向被删除的结点a i
p->next=r->next③;//将a i从链上摘下
free(r);④//释放结点a i的空间给存储池
算法的时间复杂度也是O（n）。
链表上实现的插入和删除运算，无须移动结点，仅需修改指针。
14.单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。判断空链表的条件是head==head->next;
15. 仅设尾指针的单循环链表:用尾指针rear表示的单循环链表对开始结点a1和终端结点a n查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear==rear->next;
16.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行时间是O(1)。
具体算法：
LinkList Connect(LinkList A,LinkList B) {//假设A，B为非空循环链表的尾指针
LinkList p=A->next;//①保存A表的头结点位置
A->next=B->next->next;//②B表的开始结点链接到A表尾
free(B->next);//③释放B表的头结点
B->next=p;//④
return B;//返回新循环链表的尾指针
循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-＞next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。
在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。
17.双向链表:双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指
向其直接前趋的指针域prior。
①双链表由头指针head惟一确定的。
②带头结点的双链表的某些运算变得方便。
③将头结点和尾结点链接起来，为双（向）循环链表。
18.双向链表的前插和删除本结点操作
①双链表的前插操作
void DInsertBefore(DListNode *p,DataType x){//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
DListNode *s=malloc(sizeof(DListNode));//①
s->data=x;//②
s->prior=p->prior;//③
s->next=p;//④
p->prior->next=s;//⑤
p->prior=s;//⑥
}
②双链表上删除结点*p自身的操作
void DDeleteNode(DListNode *p)
{//在带头结点的双链表中，删除结点*p，设*p为非终端结点
p->prior->next=p->next;//①
p->next->prior=p->prior;//②
free(p);//③
}
与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。
19.存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即,存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。
20.顺序表和链表比较
顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：
顺序表链表
分配方式静态分配。程序执行之前必须明确规定存储规模。若线性表长度n变化较大，则存
储规模难于预先确定估计过大将造成空
间浪费，估计太小又将使空间溢出机会增
多。动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。
存储密度为1。当线性表的长度变化不大，易于事
先确定其大小时，为了节约存储空间，宜
采用顺序表作为存储结构。
<1
存取方式随机存取结构，对表中任一结点都可在O （1）时间内直接取得线性表的操作主要
是进行查找，很少做插入和删除操作时，
采用顺序表做存储结构为宜。顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取得。
插入删除操作在顺序表中进行插入和删除，平均要移动
表中近一半的结点，尤其是当每个结点的
信息量较大时，移动结点的时间开销就相
当可观。
在链表中的任何位置上进行插入和删除，都
只需要修改指针。对于频繁进行插入和删除
的线性表，宜采用链表做存储结构。若表的
插入和删除主要发生在表的首尾两端，则采
用尾指针表示的单循环链表为宜
第三章栈
1. 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。
(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。
(2)当表中没有元素时称为空栈。
(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。
栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。
2.顺序栈：栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
①顺序栈中元素用向量存放
②栈底位置是固定不变的，可设置在向量两端的任意一个端点
③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
3.进栈操作：进栈时，需要将S-＞top加1，
①S-＞top==StackSize-1表示栈满
②"上溢"现象--当栈满时，再做进栈运算产生空间溢出的现象。
退栈操作：退栈时，需将S-＞top减1
①S-＞top<0表示空栈
②"下溢"现象--当栈空时，做退栈运算产生的溢出现象。
下溢是正常现象，常用作程序控制转移的条件。
4.两个栈共享同一存储空间:
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
当Top1=Top2-1时，栈满
5. 链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算
6. 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
允许删除的一端称为队头（Front），允许插入的一端称为队尾（Rear），当队列中没有元素时称为空队列，队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
7. 队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受
限的顺序表。
顺序队列的基本操作
①入队时：将新元素插入rear所指的位置，然后将rear加1。
②出队时：删去front所指的元素，然后将front加1并返回被删元素。
当头尾指针相等时，队列为空。
在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
8.顺序队列中的溢出现象：
①当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
②当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
③"假上溢"现象：由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
9.循环队列：为充分利用向量空间，克服"假上溢"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这
种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。
循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为：
①方法一：
if(i+1==QueueSize) //i表示front或rear
i=0;
else
i++;
②方法二--利用"模运算"
i=(i+1)%QueueSize；
循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种：
①另设一布尔变量以区别队列的空和满；
②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（即队列长度）。
10.循环队列的基本运算:
①置队空:
Q->front=Q->rear=0;
Q->count=0;
②判队空:
return Q->count==0;
③判队满:
return Q->count==QueueSize;
④入队
Q->count ++; //队列元素个数加1
Q->data[Q->rear]=x; //新元素插入队尾
Q->rear=(Q->rear+1)%QueueSize;
⑤出队
temp=Q->data[Q->front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1
return temp;
⑥取队头元素
return Q->data[Q->front];
11. 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。
链队列的基本运算:
（1）置空队：Q->front=Q->rear=NULL;
（2）判队空：return Q->front==NULL&&Q->rear==Null;
（3）入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点
p->data=x; p->next=NULL;
if(QueueEmpty(Q))
Q->front=Q->rear=p; //将x插入空队列
else { //x插入非空队列的尾
Q->rear->next=p; //*p链到原队尾结点后
Q->rear=p; //队尾指针指向新的尾
（4）出队：p=Q->front; //指向对头结点
x=p->data; //保存对头结点的数据
Q->front=p->next; //将对头结点从链上摘下
if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空
Q->rear=NULL;
free(p); //释放被删队头结点
return x; //返回原队头数据
（5）取队头元素：if(QueueEmpty(Q))
Error("Queue if empty.");
return Q->front->data;
①和链栈类似，无须考虑判队满的运算及上溢。
②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
③以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算。
12.递归是指：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。
调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。
第四章串
1. 串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。串（String）是零个或多个字符组成的有限序列。一般记为S="a1a2……a n"
将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。
2. 长度为零的串称为空串（Empty String），它不包含任何字符。仅由一个或多个空格组成的串称为空白串（Blank String）。
″ ″和″″分别表示长度为1的空白串和长度为0的空串。
3. 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。
①空串是任意串的子串②任意串是其自身的子串。
4. 通常在程序中使用的串可分为：串变量和串常量。串变量和其它类型的变量一样，其取值是可以改变的。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。
5.串的基本运算：
①求串长：int strlen(char *s);//求串s的长度
②串复制：char *strcpy(char *to,*from)；//将from串复制到to串中，并返回to开始处指针
③联接：char *strcat(char *to,char *from);//将from串复制到to串的末尾，
//并返回to串开始处的指针④串比较：int strcmp(char *s1,char *s2);//比较s1和s2的大小，
//当s1
【例】result=strcmp("baker","Baker"); //result>0
result=strcmp("12","12"); //result=0
result=strcmp("Joe","joseph") //result<0
⑤字符定位：char *strchr(char *s,char c);//找c在字符串s中第一次出现的位置，
//若找到，则返回该位置，否则返回NULL 6. 串的顺序存储结构简称为顺序串。
与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。按其存储分配的不同可将顺序串分为如下两类：
（1）静态存储分配的顺序串
①串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作
②直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值为MaxStrSize时，最多只能放MaxStrSize-1个字符。C语言中以字符'\0'表示串值的终结。
（2）动态存储分配的顺序串:顺序串的字符数组空间可使用C语言的malloc和free等动态存储管理函数，来根据实际需要动态地分配和释放。
7. 用单链表方式存储串值，串的这种链式存储结构简称为链串。
①链串和单链表的差异仅在于其结点数据域为单个字符：
②一个链串由头指针唯一确定。
链串的结点大小:
①为了提高存储密度，可使每个结点存放多个字符。
②当结点大小大于1时，串的长度不一定正好是结点大小的整数
倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。
③虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。
8. 子串定位运算又称串的模式匹配或串匹配。子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。在串匹配中，一般将主串称为目标（串），子串称为模式（串）。
串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中的子串"t i t i+1…t i+m-1"和模式串"p0p1p2…p m-1"进行比较：
①若"t i t i+1…t i+m-1"＝"p0p1p2…p m-1"，则称从位置i开始的匹配成功，或称i为有效位移。
②若"t i t i+1…t i+m-1"≠"p0p1p2…p m-1"，则称从位置i开始的匹配失败，或称i为无效位移。
因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。
有些应用中要求求出P在T中所有出现的有效位移。
9.朴素的串匹配算法的基本思想：即用一个循环来依次检查n-m+1个合法的位移i（0≤i≤n-m）是否为有效位移。
顺序串上的串匹配算法：
①最坏时间复杂度：为O((n-m+1)m)。
②模式匹配算法的改进：朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移i是否为有效位移时，没有利用检查位移i-1，i,…,0时的部分匹配结果。
若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏时间控制在O（m+n）数量级上。
链串上的子串定位运算：用结点大小为1的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移shift是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。
第五章多维数组和广义表
1. 多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。
2. 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。
同一数组的不同元素通过不同的下标标识。（a1,a2,…,a n)
3. 二维数组A mn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素a ij既属于第i行的行向量，又属于第j列的列向量。
4.多维数组:三维数组A mnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量……
三维数组中的每个元素a ijk都属于三个向量。四维数组中的每个元素都属于四个向量……
5.数组的顺序存储方式:由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。
（1）行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。
【例】二维数组A mn的按行优先存储的线性序列为：
a11,a12,…,a1n,a21,a22,…,a2n,……，a m1,a m2,…，a mn
（2）列优先顺序
将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。
【例】二维数组A mn的按列优先存储的线性序列为：
a11,a21,…,a m1,a12,a22,…,a m2,……，a1n,a2n,…，a mn
6.数组元素的地址计算公式:
（1）按行优先顺序存储的二维数组A mn地址计算公式
LOC(a ij)=LOC(a11)+[(i-1)×n+j-1]×d (注：此公式下界为1，如下界为0，则公式变为[i×n+j])
①LOC(a11)是开始结点的存放地址（即基地址）
②d为每个元素所占的存储单元数
③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。
即顺序存储的数组是随机存取结构。
（2）按列优先顺序存储的二维数组A mn地址计算公式
LOC(a ij)=LOC(a11)+[(j-1)×m+i-1]×d(注：此公式下界为1，如下界为0，则公式变为[j×m+i]) （3）按行优先顺序存储的三维数组A mnp地址计算公式
LOC(a ijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d
(注：此公式下界为1，如下界为0，则公式变为[i×n×p+j×p+k])
（4）下界不为1的二维数组的地址计算公式
①二维数组A[c1..d1,c2..d2]的地址计算公式：
LOC(a ij)=LOC(a c1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d
②下界为0的二维数组的地址计算公式（C语言中使用）
LOC(a ij)=LOC(a00)+[i×(d2+1)+j]×d
7. 矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。
矩阵的压缩：矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
8. 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。
（1）对称矩阵
在一个n阶方阵A中，若元素满足下述性质： a ij=a ji0≤i，j≤n-1
（2）对称矩阵的压缩存储
对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。
①按"行优先顺序"存储主对角线(包括对角线)以下的元素
（下三角矩阵中，元素总数为n(n+1)/2）。
即按a00,a10,a11,……，a n-1,0,a n-1,1…，a n-1,n-1次序存放在一个向量sa[0．．n(n+1)/2-1]中
sa[0]=a00 ,sa[1]=a10,……,sa[n(n+1)/2-1]= a n-1,n-1
②元素a ij的存放位置:
sa[i×(i+1)/2+j]=a ij
③a ij和sa[k]之间的对应关系：
令I=max(i,j)，J=min(i,j)，则k和i，j的对应关系可统一为：
k=I×(I+1)/2+J 0≤k （3）对称矩阵的地址计算公式： LOC(a ij)=LOC(sa[0])+[I×(I+1)/2+J]×d，其中I=max(i,j)，J=min(i,j) 9.三角矩阵的划分： 以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 ①上三角矩阵：如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。 ②下三角矩阵：与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。 10.三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)/2]中，其中c存放在向量的最后一个分量中。 ①上三角矩阵中a ij和sa[k]之间的对应关系 k=i×(2n-i+1)/2+j-i 当i≤j k=n×(n+1)/2 当i＞j ②下三角矩阵中a ij和sa[k]之间的对应关系 k=i×(i+1)/2+j 当i≥j k=n×(n+1)/2 当i＜j 三角矩阵的压缩存储结构是随机存取结构。 11.对角矩阵:所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若 干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。 若|i-j|>(k-1)／2，则元素a ij=0。对角矩阵可按行优先顺序或对角线的顺序， 将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关 系。 12. 稀疏矩阵:设矩阵A mn中有s个非零元素，若s远远小于矩阵元素的总数(即s< 其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，a ij)，并由此三元组惟一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。 13. 三元组表：将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。 14.压缩存储结构上矩阵的转置运算 一个m×n的矩阵A，它的转置矩阵B是一个n×m的矩阵，且：A[i][j]=B[j][i]，0≤i 三元组表表示的矩阵转置的思想方法 第一步：根据A矩阵的行数、列数和非零元总数确定B矩阵的列数、行数和非零元总数。 第二步：当三元组表非空（A矩阵的非零元不为0）时，根据A矩阵三元组表的结点空间data（以下简称为三元组表），将A的三元组表a->data置换为B的三元组表b->data 15.三元组表的转置:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data 必定是按行优先存放的。 按这种方法设计的算法，其基本思想是：对A中的每一 列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data， 找出所有列号等于col的那些三元组，将它们的行号和列号互换后 依次放人b->data中，即可得到B的按行优先的压缩存贮表示。该 算法的时间主要耗费在col和p的二重循环上：若A的列数为n， 非零元素个数t，则执行时间为O(n×t)，即与A的列数和非零元 素个数的乘积成正比。通常用二维数组表示矩阵时，其转置算法的 执行时间是O(m×n)，它正比于行数和列数的乘积。 16.带行表的三元组表:为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。 17. 广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。广义表是n(n≥0)个元素a1，a2，…，a i，…，a n的有限序列。 其中： ①a i--或者是原子或者是一个广义表。 ②广义表通常记作：Ls=( a1，a2，…，a i，…，a n)。 ③Ls是广义表的名字，n为它的长度。 ④若a i是广义表，则称它为Ls的子表。 注意： ①广义表通常用圆括号括起来，用逗号分隔其中的元素。 ②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 ③若广义表Ls非空(n≥1)，则a l是LS的表头，其余元素组成的表(a1，a2，…，a n)称为Ls的表尾。 ④广义表是递归定义的 广义表的深度：一个表的"深度"是指表展开后所含括号的层数。 18.广义表的图形形状划分： ①与树对应的广义表称为纯表，它限制了表中成分的共享和 递归 ②允许结点共享的表称再入表，上图(d),子表A是共享结点， 它既是C的一个元素，又是子表B的元素； ③允许递归的表称为递归表 上图(e)，表D是其自身的子表。 19. 广义表的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。 根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。 head=(a，b)=a，tail(a，b)=(b) head(A，y)=A， tail(A，y)=(y) 由于tail(L)是非空表，可继续分解得到： head(tail(L))=b， tail(tail(L))=() 对非空表A和(y)，也可继续分解。 注意: 广义表()和(())不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，得到的表头和表尾均是空表()。 第六章树 1. 树的递归定义： 树(Tree)是n(n≥0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件： (1)有且仅有一个特定的称为根(Root)的结点； (2)其余的结点可分为m(m≥0)个互不相交的子集T l，T2，…，T m，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。 树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。2.广义表表示法:用广义表的形式表示的。上图(a)树的广义表表示法如图(d) （A（B（E，F（I，J）），C，D（G，H））） 3.树结构的基本术语 （1）结点的度(Degree) 树中的一个结点拥有的子树数称为该结点的度(Degree)。 一棵树的度是指该树中结点的最大度数。 度为零的结点称为叶子(Leaf)或终端结点。 度不为零的结点称分支结点或非终端结点。 除根结点之外的分支结点统称为内部结点。 根结点又称为开始结点。 （2）孩子(Child)和双亲(Parents) 树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。 （3）祖先(Ancestor)和子孙(Descendant) ①路径（path）若树中存在一个结点序列k1，k2，…，k i，使得k i是k i+1的双亲(1≤i 路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。 ②祖先(Ancestor)和子孙(Descendant) 若树中结点k到k s存在一条路径，则称k是k s的祖先(Ancestor)，k s是k的子孙(Descendant)。 一个结点的祖先是从根结点到该结点路径上所经过的所有结点，而一个结点的子孙则是以该结点为根的子树中的所有结点。 （4）结点的层数(Level)和树的高度（Height） 结点的层数(Level)从根起算： 根的层数为1，其余结点的层数等于其双亲结点的层数加1。 双亲在同一层的结点互为堂兄弟。 树中结点的最大层数称为树的高度(Height)或深度(Depth)。 （5）有序树(OrderedTree)和无序树(UnoderedTree) 若将树中每个结点的各子树看成是从左到右有次序的(即不能互换)，则称该树为有序树(OrderedTree)；否则称为无序树(UnoderedTree)。若不特别指明，一般讨论的树都是有序树。 （6）森林(Forest) 森林(Forest)是m(m≥0)棵互不相交的树的集合。树和森林的概念相近。删去一棵树的根，就得到一个森林；反之，加上一个结点作树根，森林就变为一棵树。 4.树形结构的逻辑特征 树形结构的逻辑特征可用树中结点之间的父子关系来描述： （1）树中任一结点都可以有零个或多个直接后继(即孩子)结点，但至多只能有一个直接前趋(即双亲)结点。（2）树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。 （3）祖先与子孙的关系是对父子关系的延拓，它定义了树中结点之间的纵向次序。 （4）有序树中，同一组兄弟结点从左到右有长幼之分。 5. 二叉树(BinaryTree)是n(n≥0)个结点的有限集，它或者是空集(n=0)，或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。 二叉树与度数为2的有序树不同：在有序树中，虽然一个结点的孩子之间是有左右次序的，但是若该结点只有一个孩子，就无须区分其左右次序。而在二叉树中，即使是一个孩子也有左右之分。 6.二叉树的性质： 性质1二叉树第i层上的结点数目最多为2i-1(i≥1)。例如5层的二叉树，第5层上的结点数目最多为24=16 性质2深度为k的二叉树至多有2k-1个结点(k≥1)。例如深度为5的二叉树，至多有25-1=31个结点 性质3在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n o=n2+1。例如一棵深度为4的二叉树（a），其终端结点数n0为8,度为2的结点树为7，则8=7+1，n o=n2+1成立 （b）其终端结点数n0为6,度为2的结点树为5， 则6=5+1，n o=n2+1成立 满二叉树：一棵深度为k且有2k-1个结点的二又树称为满二叉树。满二叉树的特点： （1）每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。 （2）满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。特点： （1）满二叉树是完全二叉树，完全二叉树不一定是满二叉树。 （2）在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 （3）在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。 性质4 具有n个结点的完全二叉树的深度为。?lgn?+1 或?lg(n+1)? 例，具有100个结点的完全二叉树的深度为:?lg100?+1=7,26=64 27=128所以?lg100?=6,?lg(100+1)?=7 7．完全二叉树的编号特点：完全二叉树中除最下面一层外，各层都充满了结点。每一层的结点个数恰好是上一层结点个数的2倍。从一个结点的编号就可推得其双亲，左、右孩子，兄弟等结点的编号。 ①若i>1，则k i的双亲编号为?i/2?；若i=1，则K i是根结点，无双亲。 ②若2i≤n，则K i的左孩子的编号是2i；否则，K i无左孩子，即K i必定是叶子。因此完全二叉树中编号i>?n/2? 的结点必定是叶结点。 ③若2i+1≤n，则K i的右孩子的编号是2i+1；否则，K i无右孩子。 ④若i为奇数且不为1，则K i的左兄弟的编号是i-1；否则，K i无左兄弟。 ⑤若i为偶数且小于n，则K i的右兄弟的编号是i+1；否则，K i无右兄弟。 8.完全二叉树的顺序存储：将完全二叉树中所有结点按编号顺序依次存储在一个向量bt[0..n]中。其中：bt[1．．n]用来存储结点，bt[0]不用或用来存储结点数目。 9.一般二叉树的顺序存储: ①将一般二叉树添上一些 "虚结点"，成为"完全二叉树" ②为了用结点在向量中的相对位置来表示结点之间的逻辑关系，按完全二叉树形式给结点编号 ③将结点按编号存入向量对应分量，其中"虚结点"用"∮"表示 10.链式存储结构:二叉树的每个结点最多有两个孩子。用链接方式存储二叉树时，每个结点除了存储结点本身的数据外，还应设置两个指针域lchild和rchild，分别指向该结点的左孩子和右孩子。结点的结构为： typedef char DataType； //用户可根据具体应用定义DataType的实际类型 typedef struct node{ DataType data； Struct node *lchild，*rchild； //左右孩子指针 }BinTNode； //结点类型 typedef BinTNode *BinTree；//BinTree为指向BinTNode类型结点的指针类型 11. 在一棵二叉树中，所有类型为BinTNode的结点，再加上一个指向开始结点(即根结点)的BinTree型头指针(即 根指针)root，就构成了二叉树的链 式存储结构，并将其称为二叉链表。 全国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 页） 全国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={ 数据结构导论复习 第一章概论 1．数据：凡能被计算机存储、加工处理的对象。 2．数据元素：是数据的基本单位，在程序中作为一个整体而加以考虑和处理 3．数据项：又叫字段或域，它是数据的不可分割的最小标识单位。 4．逻辑结构需要注意的几点： ①逻辑结构与数据元素本身的内容无关 ②逻辑结构与数据元素相对位置无关 ③逻辑结构与所有结点的个数无关 5．数据元素间逻辑关系是指数据元素之间的关联方式或称“领接关系”。 6．四类基本逻辑结构（集合、线性结构、树形结构和图形结构）的不同特点？ 答：集合中任何两个结点之间都没有逻辑关系，组织形式松散； 线性结构中结点按逻辑关系依次排列形成一条“锁链”； 树形结构具有分支、层次特性，其形态有点像自然界中的树； 图状结构最复杂，其中的各个结点按逻辑关系互相缠绕，任何两个结点都可以领接。 7．运算是在逻辑结构层次上对处理功能的抽象 8．基本运算的含义？ 答：假如是S上的一些运算的集合，是的一个子集，使得中每一运算都可以“归约”为中的一个或多个运算，而中任一运算不可归约为别的运算，则称中运算为基本运算 9．数据结构是指由一个逻辑结构S和S上的一个基本运算集构成的整体（S ，）。 10．数据结构涉及数据表示和数据处理两个方面 11．存储结构的含义和四种基本存储方式的基本思想？ 答：存储结构是指按照逻辑结构的要求建立的数据的机内表示称为存储结构。 一个存储结构应包含三个主要的部分：存储结点、机内表示和附加设施。 存储结构包括四种存储方式，顺序存储方式、链式存储方式、索引存储方式和散列存储方式。 12．运算实现与运算的联系与区别？ 答：运算指的是数据在逻辑结构S上的某种操作，运算只描述处理功能，不包括处理步骤和方法；而运算实现是指一个完成该运算功能的程序，运算实现的核心是处理步骤的规定，即算法设计。 13．算法的概念和分类？ 答：算法是指规定了求解给定类型问题所需的所有“处理步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被 全国2011年1月高等教育自学考试 数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C.链队列 D.栈 2.将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3.已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4.递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C.队列 D.线性表 5.设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（） A.求子串 B.串联接 C.串匹配 D.求串长 6.对于广义表A，若head(A)等于tail(A)，则表A为（） A.( ) B.(( )) C.(( ),( )) D.(( ),( ),( )) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是 （）A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9.下列叙述中错误的是（） A.图的遍历是从给定的源点出发对每一个顶点访问且仅访问一次 B.图的遍历可以采用深度优先遍历和广度优先遍历 C.图的广度优先遍历只适用于无向图 D.图的深度优先遍历是一个递归过程 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={ 第 1 章计算机系统结构的基本概念 1.1 解释下列术语 层次结构：按照计算机语言从低级到高级的次序，把计算机系统按功能划分成多级层次结构，每 一层以一种不同的语言为特征。这些层次依次为：微程序机器级，传统机器语言机器级， 汇编语言机器级，高级语言机器级，应用语言机器级等。 虚拟机：用软件实现的机器。 然后再在这低翻译：先用转换程序把高一级机器上的程序转换为低一级机器上等效的程序， 一级机器上运行，实现程序的功能。 解释：对于高一级机器上的程序中的每一条语句或指令，都是转去执行低一级机器上的一段等效 程序。执行完后，再去高一级机器取下一条语句或指令，再进行解释执行，如此反复， 直到解释执行完整个程序。 计算机系统结构：传统机器程序员所看到的计算机属性，即概念性结构与功能特性。 在计算机技术中，把这种本来存在的事物或属性，但从某种角度看又好像不存在的概念称为透 明性。 计算机组成：计算机系统结构的逻辑实现，包含物理机器级中的数据流和控制流的组成以及逻 辑设计等。 计算机实现：计算机组成的物理实现，包括处理机、主存等部件的物理结构，器件的集成度和速度，模块、插件、底板的划分与连接，信号传输，电源、冷却及整机装配技术等。 系统加速比：对系统中某部分进行改进时，改进后系统性能提高的倍数。 Amdahl 定律：当对一个系统中的某个部件进行改进后，所能获得的整个系统性能的提高， 受限于该部件的执行时间占总执行时间的百分比。 而是相对地簇聚。包程序的局部性原理：程序执行时所访问的存储器地址不是随机分布的， 括时间局部性和空间局部性。 CPI：每条指令执行的平均时钟周期数。 测试程序套件：由各种不同的真实应用程序构成的一组测试程序，用来测试计算机在各个方面的 处理性能。 全国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 ) 自考数据构造重点（整顿） 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 以上几点最重要是时间复杂性，时间复杂度惯用渐进时间复杂度表达。 自考02331数据结构重点总结(最终修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据结构=程序。算法是对数据运算的描述，而数据结构包括逻辑结构和存储结构。由此可见，程序设计的实质是针对实际问题选择一种好的数据结构和设计一个好的算法，而好的算法在很大程度上取决于描述实际问题的数据结构。 2.数据是信息的载体。数据元素是数据的基本单位。一个数据元素可以由若干个数据项组成，数据项是具有独立含义的最小标识单位。数据对象是具有相同性质的数据元素的集合。 3.数据结构指的是数据元素之间的相互关系，即数据的组织形式。 数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算 ①数据的逻辑结构是从逻辑关系上描述数据，与数据元素的存储结构无关，是独立于计算机的。 数据的逻辑结构分类:线性结构和非线性结构。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。数组、广义表、树和图等数据结构都是非线性结构。 ②数据元素及其关系在计算机内的存储方式，称为数据的存储结构（物理结构）。 数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。 ③数据的运算。最常用的检索、插入、删除、更新、排序等。 4.数据的四种基本存储方法:顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：通常借助程序设计语言的数组描述。 （2）链接存储：通常借助于程序语言的指针来描述。 （3）索引存储：索引表由若干索引项组成。关键字是能唯一标识一个元素的一个或多个数据项的组合。 （4）散列存储：该方法的基本思想是：根据元素的关键字直接计算出该元素的存储地址。 5.算法必须满足5个准则：输入，0个或多个数据作为输入；输出，产生一个或多个输出；有穷性，算法执行有限步后结束；确定性，每一条指令的含义都明确；可行性，算法是可行的。 算法与程序的区别：程序必须依赖于计算机程序语言，而一个算法可用自然语言、计算机程序语言、数学语言或约定的符号语言来描述。目前常用的描述算法语言有两类：类Pascal和类C。 6.评价算法的优劣：算法的"正确性"是首先要考虑的。此外，主要考虑如下三点： ①执行算法所耗费的时间，即时间复杂性； ②执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 全国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) 自考数据结构公式汇总 1.O(1)、O(log2n)、O(n)、O(nlog2n)、O(n2)、 O(n3)、O(n k)、O(2n)。 2.在顺序表中第i个位置插入一个结点的移动次数为n-i+1，插入平均移动n/2次，删 除顺序表第i个结点移动次数为n-i，平均移动(n-1)/2次。 3.定义变量p=(LinkList)malloc(sizeof(ListNode))或 p=(LinkNode*)malloc(sizeof(ListNode)) 4.单循环链表判断空：head= =head->next 5.共享向量空间判断满top1=top2-1 6.入队EnQueue，出队DeQueue，front=rear空队列，循环队列克服假上溢 7.循环队列判断队满(rear+1)%m=front，循环队列指针移动方向顺时针。判队列长度 (rear-front+m)%m 8.链队列判空：Q->front=Q->rear=NULL 9.求串长strlen，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1 大就大于s1小就小于，小写字母>大写字母)，字符定位strchr 10.串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数 O((n-m+1)m) 11.二维数组下标为0公式：行优先LOC(a00)+[i*n+j]*d，列优先LOC(a00)+[j*m+i]*d 12.三维数组下标为0公式：三维数组A mnp按行优先LOC(a ijk)=LOC(a000)+[i*n*p+j*p+k]*d 13.对称矩阵一共有n(n+1)/2个元素，存储位置 k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始 14.上三角矩阵：k=i*(2n-i+1)+j-i，下三角矩阵：k=i*(i+1)/2+j。上三角i>j下三角 i ??????????????????????精品自学考料推荐?????????????????? 全国 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 2015年lO月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共8页。满分l00分。考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸. 2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。 3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间．超出答题区域无效。 第一部分选择题 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡” 的相应代码涂黑。未涂、错涂或多涂均无分。 1．下列选项中，不属于线性结构的是 A．网 B．栈 C．队列 D．线性表 2．长度为n的顺序表，删除位置i上的元素(0≤i≤n一1)，需要移动的元素个数为 A．n—i B．n—i—l C．i D．i+1 3．栈采用不同的存储方式时，下列关于出栈过程的叙述中，正确的是 A．顺序栈需要判定栈空，链栈也需要判定 B．顺序栈需要判定栈空，而链栈不需要判定 C．顺序栈不需要判定栈空，而链栈需要判定 D．顺序栈不需要判定栈空，链栈也不需要判定 4．若一个栈以数组V[0．．n-1]存储，初始栈顶指针top为n，则x入栈的正确操作是 A．top=top+1；V[top]=x B．V[top]=x；top=top+1 C．top=top一1；V[mp]=x D．V[top]=x；top=top—l 5．在二维数组a[9][10]中：每个数组元素占用3个存储空间，从首地址SA开始按行优先 全国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．在数据库方式下的信息处理中，(数据)占据了中心位置。 3．DBMS是位于(用户)和(OS)之间的一层数据管理软件。 4．数据模型不仅描述数据本身的特点，还要描述(数据之间的联系)。 5．DBS中，用户的数据和磁盘中的数据之间转换由(DBMS)实现。 6．在层次、网状模型中，用（指针）导航数据；而在关系模型中，用（关键码）导航数据。7．数据库的三级模式结构是对(数据)的三个抽象级别。 8．DBS中存放三级结构定义的DB称为(数据字典)。 9．DBS的全局结构体现了其(模块功能)结构。 10．DBMS为应用程序运行时开辟的DB系统缓冲区，主要用于(数据传输)和(模式转换)。11．层次模型用(树)型结构来表示实体间的联系。 12．在数据的人工管理阶段，程序与数据是(一一对应)的关系。 13．定义数据库的安全性和完整性的工作由(DBA)完成。 14．数据独立性的好处是(数据存储方式的变化不会影响到应用程序的使用)。 15．数据库的三级体系结构使用户能抽象地使用数据，不必关心(数据在计算机中的表示和存储) 。 16．概念设计阶段用到实体、实体集、属性和实体标识符等4个术语；逻辑设计阶段用到字段、记录、文件和关键码等4个术语； 第二章节数据库设计和ER模型 1．ER数据模型一般在数据（概念设计)阶段使用。 2．“为哪些表，在哪些字段上，建立什么样的索引”这一设计内容应该属于数据库设计中的(物理设计)阶段。 3．数据模型是用来描述数据库的结构和语义的，数据模型有（概念数据模型）和（结构数据模型）两类，ER模型是(概念数据模型)。 4．数据实施阶段包括两项重要的工作，一项是数据(载入)，另一项是应用程序的编码和调试。5．ER图向关系模型转化要解决的问题是如何将实体和实体之间的联系转换成关系模式，如何确定这些关系模式的(属性和键)。 6．数据库的物理设计是对一个给定的（基本数据）模型选取一个最合适应用环境的物理结构的过程。 7．数据库设计中，将(各局部ER之间的联系)分ER图集成时，主要任务是增补。 8．数据库应用系统设计中逻辑设计的主要内容是把ER模型的(实体和联系)转换为关系模式。 9．ER方法是(概念数据模型)设计的方法。 10．现实世界到机器世界过渡的中间层次是(概念模型)。 11．概念设计的目标是(企业组织信息需求)产生反映的数据库概念结构，即概念模式。12．在DBD中，子类具有一个重要的性质：(继承性)。 13．DBD的逻辑设计分成两大部分：（DB逻辑结构设计和应用程序设计）。 14．关系模型用(关键码)表示实体之间的联系。 15．DBS的维护工作由(DBA) 承担。 16．概念设计是设计能够反映用户需求的数据库概念结构，即概念模型。 17．ER模型是人们认识客观世界的一种方法、工具。 18．ER模型具有客观性和主观性两重含义。 第三章节关系模式设计理论 绝密★考试结束前 全国2014年4月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1.答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2.每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题（本大题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸” 的相应代码涂黑。错涂、多涂或未涂均无分。 1.与数据存储结构无关 ．．的概念是 A.栈 B.链表 C.顺序表 D.二叉链表 2.顺序表中有10个数据元素，若第一个元素的存储地址是1000，则最后一个元素地址是1036，第5个元素的地址是 A．1010 B.1016 C.1018 D.1019 3.设栈的初始状态为空，元素1、2、3、4、5、6依次入栈，得到的出栈序列是（2,4,3,6,5,1）,则栈的容量至少是 A.2 B.3 C.4 D..6 4.下列关于队列的叙述中,错误 ．．的是 A.队列是一种先进先出的线性表 B.队列是一种后进后出的线性表 C.循环队列中进行出队操作时要判断队列是否为空 1 D.在链队列中进行入队操作时要判断队列是否为满 5.对稀疏矩阵进行压缩存储的目的是 A.便于运算 B.节省存储空间 C.便于输入输出 D.降低时间复杂度 6.一棵二叉树的第7层上最多含有的结点数为 A.14 B.64 C.127 D.128 7.下列选项为完全二叉树的是 8.用邻接表表示n个顶点e条边的无向图,其边表结点的总数是 A. n×e B. e C. 2e D. n+e 9.无向图中所有顶点的度数之和与所有边数之比是 A.1/2 B.1 C.2 D.4 10.采用邻接矩阵存储图时,广度优先搜索遍历算法的时间复杂度为 A. O（n） B. O（n+e） C. O（n2） D. O（n3） 11.对序列（15,9,7,8,20,-1,4）进行排序,若一趟排序后的结果为（-1,15,9,7,8,20,4）,则采用的排序方法是 A.归并排序 B.快速排序 C.直接选择排序 D.冒泡排序 12.比较次数与待排序列初始状态无关的排序方法是 A.快速排序 B.冒泡排序 C.直接插入排序 D.直接选择排序 13.查找较快,且插入和删除操作也比较方便的查找方法是 A.分块查找 B.二分查找 C.顺序查找 D.折半查找 14.下列关于m阶B树的叙述中,错误 ．．的是 2 自考02331数据构造重点总结(最后修订) 第一章概论 1.瑞士计算机科学家沃思提出：算法+数据构造=程序。算法是对数据运算描述，而数据构造涉及逻辑构造和存储构造。由此可见，程序设计实质是针对实际问题选取一种好数据构造和设计一种好算法，而好算法在很大限度上取决于描述实际问题数据构造。 2.数据是信息载体。数据元素是数据基本单位。一种数据元素可以由若干个数据项构成，数据项是具备独立含义最小标记单位。数据对象是具备相似性质数据元素集合。 3.数据构造指是数据元素之间互有关系，即数据组织形式。 数据构造普通涉及如下三方面内容：数据逻辑构造、数据存储构造、数据运算 ①数据逻辑构造是从逻辑关系上描述数据，与数据元素存储构造无关，是独立于计算机。 数据逻辑构造分类：线性构造和非线性构造。 线性表是一种典型线性构造。栈、队列、串等都是线性构造。数组、广义表、树和图等数据构造都是非线性构造。 ②数据元素及其关系在计算机内存储方式，称为数据存储构造（物理构造）。 数据存储构造是逻辑构造用计算机语言实现，它依赖于计算机语言。 ③数据运算。最惯用检索、插入、删除、更新、排序等。 4.数据四种基本存储办法：顺序存储、链接存储、索引存储、散列存储 （1）顺序存储：普通借助程序设计语言数组描述。 （2）链接存储：普通借助于程序语言指针来描述。 （3）索引存储：索引表由若干索引项构成。核心字是能唯一标记一种元素一种或各种数据项组合。 （4）散列存储：该办法基本思想是：依照元素核心字直接计算出该元素存储地址。 5.算法必要满足5个准则：输入，0个或各种数据作为输入；输出，产生一种或各种输出；有穷性，算法执行有限步后结束；拟定性，每一条指令含义都明确；可行性，算法是可行。 算法与程序区别：程序必要依赖于计算机程序语言，而一种算法可用自然语言、计算机程序语言、数学语言或商定符号语言来描述。当前惯用描述算法语言有两类：类Pascal和类C。 6.评价算法优劣：算法"对的性"是一方面要考虑。此外，重要考虑如下三点： ①执行算法所耗费时间，即时间复杂性； ②执行算法所耗费存储空间，重要是辅助空间，即空间复杂性； ③算法应易于理解、易于编程，易于调试等，即可读性和可操作性。 第一概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。 第一张概论 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）称为一个数据结构。数据结构包括逻辑结构和处理方式。 自考《数据库系统原理》串讲笔记 第一章数据库基础知识 学习目的与要求： 本章属于基础知识，主要是对一些概念的理解和记忆。没有难点，相对的重点是数据模型的四个层次，数据库管理系统的功能，数据库系统的全局结构。 考核知识点与考核要求 1.1数据管理技术的发展阶段（识记） 1.2数据描述的术语（领会） 1.3数据抽象的级别（领会） 1.4数据库管理系统(DBMS) (领会) 1.5数据库系统（DBS）（领会） 1.1 数据管理技术的发展 几个数据库的基本术语： 数据：描述事物的符号记录 数据处理:是指从某些已知的数据出发，推导加工出一些新的数据，这些新的数据又表示了新的信息。 数据管理:是指数据的收集、整理、组织、存储、维护、检索、传送等操作，这部分操作是数据处理业务的基本环节，而且是任何数据处理业务中必不可少的共有部分。 数据管理技术：对数据的收集、整理、组织、存储、维护、检索、传送等操作，基本目的就是从大量的，杂乱无章的，难以理解的数据中筛选出有意义的数据。 数据处理是与数据管理相联系的，数据管理技术的优劣，将直接影响数据处理的效率。 1.人工管理阶段（20世纪50年代中期以前） １）数据不保存在机器中； ２）没有专用软件对数据进行管理； ３）只有程序的概念，没有文件的概念； ４）数据面向程序。 2. 文件系统阶段特点与缺陷（20世纪50年代后期至60年代中期） １）数据可长期保存在磁盘上； ２）数据的逻辑结构与物理结构有了区别； ３）文件组织呈现多样化； ４）数据不再属于某个特定程序，可以重复使用； ５）对数据的操作以记录为单位。 文件系统三个缺陷： １）数据冗余性 ２）数据不一致性自考数据结构导论20051年10月试卷
全国自学考试数据结构导论试题及答案(4套)
自考数据结构导论复习资料
自考数据结构试题真题
计算机系统结构重点题解自考复习资料
自考数据结构导论
2021年自学考试数据结构重点总结02331整理
自考02331数据结构重点总结(最终修订)
全国数据结构导论10月高等教育自学考试试题与答案
自考数据结构公式汇总
2020年10月全国数据结构导论自考试题及答案解析.doc
自考数据结构 试题及答案解析
自考数据结构导论20120年01月试卷
2018自考《数据库系统原理》填空题总结
全国2014年4月自考数据结构真题
2021年自考02331数据结构重点总结最终修订
自考02142《大数据结构导论》串讲笔记
自考02142《数据结构导论》串讲笔记
自考数据库系统原理完整版
- 全国自学考试数据结构导论试题及答案(4套)
- 全国自学考试数据结构导论试题及答案(4套)
- 【历年自考真题6套】数据结构导论02142试题(2015年10月-2020年8月)
- 全国自学考试数据结构导论试题及答案(4套)
- 数据结构导论自考实践题
- 全国2019年4月自考02142数据结构导论试题及答案
- 自考数据结构导论20030年01月试卷
- 全国2017年4月自考《数据结构导论》试题02142
- 2014年4月自考数据结构导论试题及答案
- 全国数据结构导论10月高等教育自学考试试题与答案
- 自考02142《数据结构导论》串讲笔记
- 2020年1月全国自学考试试题及答案解析数据结构导论试卷及答案解析
- 2006年10月全国自考数据结构导论试题及答案
- 自考数据结构导论20051年10月试卷
- 全国1月高等教育自学考试数据结构导论试题及答案解析
- 全国自学考试数据结构导论试卷与答案(4套)
- 自考02142数据结构导论串讲笔记
- 全国2014年10月自考全国数据结构导论试题及答案
- 2015年4月全国自考《数据结构导论》试题
- 自考数据结构导论