02331 数据结构

02331数据结构

第一章概论

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&&jnext为NULL或i=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）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即,存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。

第三章栈

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->rea r=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.递归是指：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。

调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。

13.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。队列又称为先进先出线性表，FIFO表。

14.队列的基本运算：

1）initqueue(q),置空队；2）queueempty(q),判队空；3）queuefull(q),判队满；4）enqueue(q,x),入队；5）dequeue(q),出队；

6）queuefront(q),返回队头元素。

15.顺序队列：队列的顺序存储结构称顺序队列。设置front和rear指针表示队头和队尾元素在向量空间的位置。

16.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。

17.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。

i=(i+1)%queuesize

18.循环队列的边界条件处理：由于无法用front==rear 来判断队列的“空”和“满”。解决的方法有：

1）另设一个布尔变量以区别队列的空和满；

2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front；3）使用一个记数器记录元素

总数。

19.循环队列的基本运算：

1) 置队空。

Void initqueue(cirqueue *q) {

q->front=q->rear=0; q->count=0; }

2) 判队空。

Int queueempty(cirqueue *q) {

return q->count==0; }

3) 判队满。

Int queuefull(cirqueue *q) {

return q->count==queuesize; }

4) 入队。

Void enqueue(cirqueue *q ,datatype x) { if(queuefull(q))

error(“queue overfolw”);q->count++;

q->data[q->rear]=x;

q->rear=(q->rear+1)%queuesize; }

5) 出队。

Datatype dequeue(cirqueue *q) {

datatype temp; if(queueempty(q))

error(“queue underflow”);temp=q->data [q->front]; q->count--;

q->front=(q->front+1)%queuesize;

return temp; }

6) 取队头元素。

Datatype queuefront(cirqueue *q) {

if(queueempty(q))

error(“queue is empty”);return q->d ata[q->front]; }

20.链队列：队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。16.链队列的基本运算：1) 建空队。

Void initqueue(linkqueue *q) {

q->front=q->rear=NULL; }

2) 判队空。

Int queueempty(linkqueue *q) {

return q->front==NULL&&q->rear==NULL; }

3) 入队。

Void enqueue(linkqueue *q,datatype x) { queuenode *p=(queuenode *)malloc(sizeof(queu enode)); p->data=x;

p->next=NULL; if(queueempty(q)) q-fron t=q->rear=p; else{

q->rear->next=p; q->rear=p; } } 4) 出队。

Datatype dequeue(linkqueue *q) {

datatype x; queuenode *p; if(queueempt y(q))

error(“queue is underflow”);p=q->fro nt; x=p->data;

q->front=p->next;

if(q->rear==p) q->rear=NULL; free(p); r eturn x; }

5) 取队头元素。

Datatype queuefront(linkqueue *q) {

if(queueempty(q))

error(“queue is empty”);return q->f ront->data; }

第四章多维数组和广义表

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 ，就构成了二叉树的链式存储结构，并将其称为二叉链表。

1、一个二叉链表由根指针root 惟一确定。若二叉树为

空，则root=NULL ；若结点的某个孩子不存在，则相应的指针为空。

2、具有n 个结点的二叉链表中，共有2n 个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。

带双亲指针的二叉链表: 经常要在二叉树中寻找某结点的双亲时，可在每个结点上再加一个指向其双亲的指针parent ，形成一个带双亲指针的二叉链表。

二叉树存储方法的选择，主要依赖于所要实施的各种运算的频度。

12. 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且

仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：

（1）访问结点本身(N)，（2）遍历该结点的左子树(L)，（3）遍历该结点的右子树(R)。

以上三种操作有三种执行次序：NLR 、LNR 、LRN 三种遍历的命名，根据访问结点操作发生位置命名：

① NLR ：前序遍历(亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。

② LNR ：中序遍历——访问结点的操作发生在遍历其左右子树之中(间)。

③ LRN ：后序遍历——访问结点的操作发生在遍历其左右子树之后。 由于被访问的结点必是某子树的根，所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR 、LNR 和LRN 分别又称为先根遍历、中根遍历和后根遍历。

13. 遍历算法:

1．中序遍历的递归算法定义：(1)遍历左子树； (2)访问根结点； (3)遍历右子树。

2．先序遍历的递归算法定义：(1)访问根结点； (2)遍历左子树； (3)遍历右子树。

3．后序遍历得递归算法定义：(1)遍历左子树； (2)遍历右子树； (3)访问根结点。 14.遍历序列：

遍历二叉树的执行踪迹：三种递归遍历算法的搜索路线相同（如下图虚

线所示）。

具体线路为：从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。 遍历序列

（1） 中序序列：中序遍历二叉树时，对结点的访问次序为中序序列

【例】中序遍历上图所示的二叉树时，得到的中序序列为：D B A E C F

（2） 先序序列：先序遍历二叉树时，对结点的访问次序为先序序列

【例】先序遍历上图所示的二叉树时，得到的先序序列为：A B D C E F

（3） 后序序列：后序遍历二叉树时，对结点的访问次序为后序序列

【例】后序遍历上图所示的二叉树时，得到的后序序列为：D B E F C A

在搜索路线中，若访

问结点均是第一次经过结点（图中标为1）时进行的，则是前序遍历；若访问结点均是在第二次（图中标为2）(或第三次（图中标为3）)经过结点时进行的，则是中序遍历(或后序遍历)。只要将搜索路线上所有在第一次、第二次和第三次经过的结点分别列表，即可分别得到该二叉树的前序序列、中序序列和后序序列。

15.二叉树的建立：建立上图所示二叉树，其输入的先序序列是：ABD ∮∮CE ∮∮F ∮∮。

算法：void CreateBinTree (BinTree *T)

{ //构造二叉链表。T是指向根指针的指针，故修改*T就修改了实参(根指针)本身

char ch；

if((ch=getchar())=='') *T=NULL； //读人空格，将相应指针置空

else{ //读人非空格

*T=(BinTNode *)malloc(sizeof(BinTNode))； //生成结点

(*T)->data=ch；

CreateBinTree(&(*T)-> lchild)； //构造左子树

CreateBinTree(&(*T)-> rchild)； //构造右子树

}

}

16.线索二叉树：n个结点的二叉链表中含有n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为"线索"）。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树

(Thre

aded

Binar

yTree

)。根

据线

索性

质的

不同，

线索

二叉

树可

分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。线索链表解决了二叉链表找左、右孩子困难的问题，出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。利用的是n个结点的二叉链表中含有n+1个空指针域，因此可以利用这些空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针。

线索链表的结点结构：

其中:ltag

和rtag是

增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前趋或后继的线索。

图中的实线表示指针，虚线表示线索。

结点C的左线索为空，表示C是中序序列的开始结点，无前趋；

结点E的右线索为空，表示E是中序序列的终端结点，无后继。

线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。

17.二叉树的线索化:将二叉树变为线索二叉树的过程称为线索化。按某种次序将二叉树线索化的实质是：按该次序遍历二叉树，在遍历过程中用线索取代空指针。下图中序序列为：C B D A F H G I E

和中序遍历算法一样，递归过程中对每结点仅做一次访问。因此对于n个结点的二叉树，算法的时间复杂度亦为O(n)。

18.线索二叉树的运算:查找某结点*p在指定次序下的前趋和后继结点

在中序线索二叉树中，查找结点*p的中序后继结点：

①若*p的右子树空(即p->rtag为Thread)，

则

p->rchild为右线索，直接指向*p的中序后继。

②若*p的右子树非空(即p->rtag为Link)，则*p的中序后继必是其右子树中第一个中序遍历到的结点。也就是从*p的右孩子开始，沿该孩子的左链往下查找，直至找到一个没有左孩子的结点为止，该结点是*p的右子树中"最左下"的结点，即*P的中序后继结点。

在中序线索二叉树中，查找结点*p的中序前趋结点:

①若*p的左子树为空，则p->1child为左线索，直接指向*p的中序前趋结点；

②若*p的左子树非空，则从*p的左孩子出发，沿右指针链往下查找，直到找到一个没有右孩子的结点为止。该结点是*p的左子树中"最右下"的结点，它是*p的左子树中最后一个中序遍历到的结点，即*p的中序前趋结点。

19.在后序线索二叉树中，查找指定结点*p的后序前趋结点

在后序线索二叉树中，查找指定结点*p的后序前趋结点的具体规律是：

① 若*p的左子树为空，则p->lchild是前趋线索，指示其后序前趋结点。

【例】在下图所示的后序线索二叉树中，H的后序前趋是B，F的后序前趋是C。

②若*p的

左子树非

空，则

p->lchild

不是前趋线

索。由于后

序遍历时，

根是在遍历

其左右子树之后被访问的，故*p的后序前趋必是两子树中最后一个遍历结点。

当*p的右子树非空时，*p的右孩子必是其后序前趋

【例】在上图所示的后序线索二叉树中，A的后序前趋是E；

当*p无右子树时，*p的后序前趋必是其左孩子

【例】在上图所示的后序线索二叉树中，E的后序前趋是F （4）在后序线索二叉树中，查找指定结点*p的后序后继结点

具体的规律：

①若*p是根，则*p是该二叉树后序遍历过程中最后一个访问到的结点。*p的后序后继为空

②若*p是其双亲的右孩子，则*p的后序后继结点就是其双亲结点

【例】上图所示的后序线索二叉树中，E的后序后继是A。

③若*p是其双亲的左孩子，但*P无右兄弟，*p的后序后继结点是其双亲结点

【例】上图所示的后序线索二叉树中，F的后序后继是E。

④若*p是其双亲的左孩子，但*p有右兄弟，则*p 的后序后继是其双亲的右子树中第一个后序遍历到的结点，它是该子树中"最左下的叶结点"

【例】上图所示的后序线索二叉树中，B的后序后继是双亲A的右子树中最左下的叶结点H

注意：F是孩子树中"最左下"结点，但它不是叶子。

由上述讨论中可知：在后序线索树中，仅从*p出发就能找到其后序前趋结点；要找*p的后序后继结点，仅当*p的右子树为空时，才能直接由*p的右线索p->rchild得到。否则必须知道*p的双亲结点才能找到其后序后继。因此，如果线索二叉树中的结点没有指向其双亲结点的指针，就可能要从根开始进行后序遍历才能找到结点*P的后序后继。由此，线索对查找指定结点的后序后继并无多大帮助。

20.遍历线索二叉树:

遍历某种次序的线索二叉树，只要从该次序下的开始结点开发，反复找到结点在该次序下的后继，直至终端结点。

遍历中序线索二叉树算法：

void TraverseInorderThrTree(BinThrTree p)

{ //遍历中序线索二叉树

if(p){//树非空

while(p->ltag==Link)

p=p->lchild； //从根往下找最左下结点，即中序序列的开始结点

do{

printf("％c"，p->data)； //访问结点

p=InorderSuccessor(p)； //找*p的中序后继

}while(p)

}//endif

}//TraverselnorderThrTree

分析：

①中序序列的终端结点的右线索为空，所以do语句的终止条件是p==NULL。

②该算法的时间复杂性为O(n)。因为是非递归算法，常数因子上小于递归的遍历算法。因此，若对一棵二叉树要经常遍历，或查找结点在指定次序下的前趋和后继，则应采用线索链表作为存储结构为宜。

③以上介绍的线索二叉树是一种全线索树（即左右线索均要建立）。许多应用中只要建立左右线索中的一种。

④若在线索链表中增加一个头结点，令头结点的左指针指向根，右指针指向其遍历序列的开始或终端结点会更方便。

21.将树转换为二叉树：树中每个结点最多只有一个最左边的孩子(长子)

和一个右邻的兄弟。按照这种关系很自

然地就能将树转换成相应的二叉树：①在所有兄弟结点之间加一连线；②对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。

由于树根没有兄弟，故树转化为二叉树后，二叉树的根结点的右子树必为空

22.将一个森林转换为二叉树:

①将森林中的每棵树变为二叉树

②因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。

23.二叉树到树、森林的转换:把二叉树转换到树和森林自然的方式是：若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，…，都与y用连线连起来，最后去掉所有双亲到右孩子的连线。

24.树的存储结构：

1.双亲链表表

示法：双亲链

表表示法利用

树中每个结点

的双亲唯一

性，在存储结

点信息的同

时，为每个结

点附设一个指

向其双亲的指

针parent，惟

一地表示任何

-棵树。

（1）双亲链表表示法的实现

方法①用动态链表实现

方法②用向量表示——更为方便

分析：E和F所在结点的双亲域是1，它们的双亲结点在向量中的位置是1，即B是它们的双亲。

注意：

①根无双亲，其parent域为-1。

②双亲链表表示法中指针parent向上链接，适合求指定结点的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能要遍历整个数组。

2.孩子链表表示法：孩子链表表示法是为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。

注意：

①孩子结点的数据域仅存放了它们在向量空间的序号。

②与双亲链表表示法相反，孩子链表表示便于实现涉及孩子及其子孙的运算，但不便于实现与双亲有关的运算。

③将双亲链表表示法和孩子链表表示法结合起来，可形成双亲孩子链表表示法。

3.孩子兄弟链表表示法：在存储结点信息的同时，附加两个分别指向该结点最左孩子和右邻兄弟的指针域leftmostchild和rightsibling，即可得树的孩子兄弟链表表示。

注意：

这种存储结构的最大优点是：它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作。

25.树的遍历：1．树T的前序遍历定义：①访问根结点R；②依次前序遍历根R的各子树T1，T2，…，T k。

2．树的后序遍历定义：①依次后序遍历根T的各子树T l，T2，…，T k；②访问根结点R。

对下面的(a)图中的树进行前序遍历和后序遍历，得到的前序序列和后序序列分别是ABCDE和BDCEA。

①前序遍历一棵树恰好等价于前序遍历该树对应的二叉树

②后序遍历树恰好等价于中序遍历该树对应的二叉树。

26.森林的两种遍历方法

1．前序遍历森林：①访问森林中第一棵树的根结点；②前序遍历第一棵树中根结点的各子树所构成的森林③前序遍历除第一棵树外其它树构成的森林。

2．后序遍历森林：①后序遍历森林中第一棵树的根结点的各子树所构成的森林；②访问第一棵树的根结点；③后序遍历除第一棵树外其它树构成的森林。

对下面(a)图中所示的森林进行前序遍历和后序遍历，则得到该森林的前序序列和后序序列分别为ABCDEFIGJH和BDCAIFJGHE。而(b)图所示二叉树的前序序列和中序序列也分别为ABCDEFIGJH和BDCAIFJGHE。

①前序遍历森林等同于前序遍历该森林对应的二叉树

②后序遍历森林等同于中序遍历该森林对应的二叉树

27.树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。

结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。

结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度

：定义为树中所有叶结点的带权路径

长度之和，通常记为：

其中：n表示叶子结点的数目，w i和l i分别表示叶结点k i的权值和根到结点k i之间的路径长度。树的带权路径长度亦称为树的代价。

28．最优二叉树或哈夫曼树：在权为w l，w2，…，w n的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为

最优二叉树或哈夫曼树。

给定4个叶子结点a,b,c,d,分别带权7,5,2,4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：

(a)WPL=7*2+5*2+2*2+4*2=36

(b)WPL=7*3+5*3+2*1+4*2=46

(c)WPL=7*1+5*2+2*3+4*3=35

其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

①叶子上的权值均相同时，完全二叉树一定是最优二叉树，否则完全二叉树不一定是最优二叉树。

②最优二叉树中，权越大的叶子离根越近。

③最优二叉树的形态不唯一，WPL最小

29.哈夫曼算法:哈夫曼首先给出了对于给定的叶子数目及其权值构造最优二叉树的方法，故称其为哈夫曼算法。其基本思想是：

(1)根据给定的n个权值w l，w2，…，w n构成n棵二叉树的森林F={T1，T2，…，T n}，其中每棵二叉树T i中都只有一个权值为w i的根结点，其左右子树均空。

(2)在森林F中选出两棵根结点权值最小的树(当这样的树不止两棵树时，可以从中任选两棵)，将这两棵树合并成一棵新树，为了保证新树仍是二叉树，需要增加一个新结点作为新树的根，并将所选的两棵树的根分别作为新根的左右孩子(谁左，谁右无关紧要)，将这两个孩子的权值之和作为新树根的权值。

(3)对新的森林F重复(2)，直到森林F中只剩下一棵树为止。这棵树便是哈夫曼树。

注意：

①初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子

② n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点。

③哈夫曼树是严格的二叉树，没有度数为1的分支结点。

第一次：0，1->6；第二次：2,6->7；第三次：3,4->8；第四次：5,7->9；第五次：8,9->10。

（1）哈夫曼树的存储结构

用一个大小为2n-1的向量来存储哈夫曼树中的结点，其存储结构为：

#define n 100 //叶子数目

#define m 2*n-1//树中结点总数

typedef struct { //结点类型

float weight； //权值，不妨设权值均大于零

int lchild，rchild，parent； //左右孩子及双亲指针

}HTNode；

注意：

因为C语言数组的下界为0，故用-1表示空指针。树中某结点的lchild、rchild和parent不等于-1时，它们分别是该结点的左、右孩子和双亲结点在向量中的下标。

这里设置parent域有两个作用：其一是使查找某结点的双亲变得简单；其二是可通过判定parent的值是否为-1来区分根与非根结点。

哈夫曼算法的简要描述

在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：

(1)初始化

将T[0．．m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。

(2)输人

读人n个叶子的权值存于向量的前n个分量(即T[0．．n-1])中。它们是初始森林中n个孤立的根结点上的权值。

(3)合并

对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n≤i≤m-1)。每次合并分两步：

①在当前森林T[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。

②将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。具体操作：

将T[p1]和T[p2]的parent置为i，

将T[i]的lchild和rchild分别置为p1和p2

新结点T[i]的权值置为T[p1]和T[p2]的权值之和。

注意：

合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。

30.哈夫曼编码：

数据压缩过程称为编码。即将文件中的每个字符均转换为一个惟一的二进制位串。数据解压过程称为解码。即将二进制位串转换为对应的字符。

对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码，等长编码是前缀码。

平均码长或文件总长最小的前缀编码称为最优的前缀码。最优的前缀码对文件的压缩效果亦最佳。

利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。1．具体做法

（1）用字符c i作为叶子，p i或f i做为叶子c i的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；

（2）将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码（也称哈夫曼编码）。

2．由哈夫曼树求得编码为最优前缀码的原因：

①每个叶子字符c i的码长恰为从根到该叶子的

路径长度l i，平均码长(或文件总长)又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树，

3．因此编码的平均码长(或文件总长)亦最小。

②树中没有一片叶子是另一叶子的祖先，每片

叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。

3．求哈夫曼编码的算法（1）思想方法

给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是：依次以叶子T[i](0≤i≤n-1)为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。

第六章图

1.图：图G是由顶点集V和边集E组成，顶点集是有穷非空集，边集是有穷集；

2.G中每条边都有方向称有向图；有向边称弧；边的始点称弧尾；边的终点称弧头；G中每条边都没有方向的称无向图。

3.顶点n与边数e的关系：无向图的边数e介于0~n(n-1)/2之间，有n(n-1)/2条边的称无向完全图；有向图的边数e介于0~n(n-1)之间，有n(n-1)条边的称有向完全图；

4.无向图中顶点的度是关联与顶点的边数；有向图中顶点的度是入度与出度的和。所有图均满足：所有顶点的度数和的一半为边数。

5.图G（V，E），如V’是V 的子集，E’是E的子集，且E’中关联的顶点均在V’中，则G’(V’,E’)是G的子图。

6.在有向图中，从顶点出发都有路径到达其它顶点的图称有根图；

7.在无向图中，任意两个顶点都有路径连通称连通图；极大连通子图称连通分量；

8.在有向图中，任意顺序两个顶点都有路径连通称强连通图；极大连通子图称强连通分量；9.将图中每条边赋上权，则称带权图为网络。10.图的存储结构：（1）邻接矩阵表示法：邻接矩阵是表示顶点间相邻关系的矩阵。n个顶点就是n阶方阵。无向图是对称矩阵；有向图行是出度，列是入度。

（2）邻接表表示法：对图中所有顶点，把与该顶点相邻接的顶点组成一个单链表，称为邻接表，adjvex|next,如要保存顶点信息加入data；对所有顶点设立头结点，vertex|firstedge,并顺序存储在一个向量中；vertex 保存顶点信息，firstedge保存邻接表头指针。11.邻接矩阵表示法与邻接表表示法的比较：1）邻接矩阵是唯一的，邻接表不唯一；

2）存储稀疏图用邻接表，存储稠密图用邻接矩阵；3）求无向图顶点的度都容易，求有向图顶点的度邻接矩阵较方便；4）判断是否是图中的边，邻接矩阵容

数据结构期末考试复习笔记

判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点

2021北京科技大学计算机科学与技术考研真题经验参考书

我本科在燕山大学，作为河北省的一个旅游城市，旅游季节超级多以外，真的没有开拓我太多眼界，但是鉴于老师负责而且很专业，教会了我很多知识。但是我们专业，在一二线城市，机会多，企业多，就业及科研合作机会也多，所以，选择学校，一定要先看城市，再选学校。对我而言，研究生考进北科大，也是一项很大的挑战和提升。下面是我整理的一些考研经验与心得，希望能助你一臂之力，早日考进自己理想的学校。 数学： 对于计算机科技而言，数学很重要。我们专业是以数学逻辑为基础的，数据结构是建立在数学基础之上的一门学科。可以说，数学是我们的工具书。数学真的很重要。要从3月份就开始复习，这样后面会比较轻松。建议先从基础教材着手，看完教材，要做课后练习题，测试自己是否掌握了本章节的知识。这样，高数和线性代数的课本过一遍，需要2-3个月的时间。第二阶段就要做大量的练习了，研数盒子，这个公众号的特点是习题为主，数学一定要多加练习，这个公众号就是以练习各种习题为主，每周都会发各种作业和讲解，研数盒子有一套教材叫做研数800题非常好。做的过程中，对错题要着重注意并记录一下，建立一个错题本，然后针对没做对的题，分析归纳，然后回归到课本上，查到对应章节，重新温习。这套练习要刷个3遍左右，每一遍你都会有新的认识和体会，个人觉得效果会比做3套不同的题更有效。3遍下来，精读的效果就很明显了，这就是“温故知新”的道理。10月开始，真题要开始做起来了，向上面一样，建立错题本，这个本会是你考研备考后期独一无二的宝典。总之，数学真的很重要，要自始至终坚持到底，除了反复多加练习，还要多思考。 英语： 阅读理解很重要，备考需要坚持每天2篇阅读，开始的时候要精度，好好分析一下句式，掌握好主谓宾从，整段意思也就很容易理解了。学会分析句式以后，后续就会容易很多。再就是单词部分，买一本基础的单词书<<一本单词>>，早晨背完，晚上回忆，过电影一样的，重要的单词，要熟悉到知道在哪个位置，上面的解释是什么。没事看看，不想看书的时候看看，随手看看，遍数多了，自然会记住了，或者每个考生都有自己独特的单词记忆方法，请大家用尽十八般武艺，只有一个目的——背好单词，大家也可以关注蛋核英语公众号。再说说作文，作文呢，一定要积累名言警句，有华丽的辞藻才能表达出自己的观点对不对？作文

自考《数据结构》真题和答案

2016年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。毖须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。 第一部分选择题(共30分) 一、单项选择题(本大题共l5小题，每小题2分，共30分> 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 卡”的相应代码涂黑。错涂、多涂或未涂均无分。 1．下列选项中，不属于线性结构特征的是 A．数据元素之间存在线性关系 B．结构中只有一个开始结点 C．结构中只有一个终端结点 D．每个结点都仅有一个直接前趋 2．设l7个元素的顺序表中，若将第个元素e移动到第个位置，

不改变除e外其他元素之间的相对次序，则需移动的表中元素个数是 3．若用一个大小为7的数组作为循环队列的存储结构，且当前rew和盘0nt的值分别 为2和4，在此之前的操作是从队列中删除了一个元素及加入两个元素，请问这3 个操作之前rear和矗0nt的值分别是 A．0和l B．0和3 C．3和6 D．4和5 4．已知广义表LS=(((a))，((b，(c))，(d，(e，f)))，0)，LS的长度是 A．2 B．3 C．4 D. 5 5．一棵完全二叉树T的全部k个叶结点都在同一层中且每个分支结点都有两个孩子结点。于中包含的结点数是 A．k B. 2k-1 C．k2 D．2k-1 6．如果某二叉树的前序遍历序列为abced，中序遍历序列为cebda，则该二叉树的后序 遍历序列是 A．cedba B．decba C．ecdba D．ecbad 7．一个森林有m棵树，顶点总数为n，则森林中含有的总边数是 A．m B. n-l C．n-m D．n+m 8．设图的邻接矩阵A如下所示。各顶点的度依次是

数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年 《数据结构》试卷（A卷）（考试时间：100分钟） 一. 填空（每空2分，共40分） 1. 数据结构式具有相同性质的数据元素的（1）。 2. 通常程序在调用另一个程序时，都需要使用一个（2）来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A，每个元素用相邻的6个字节存储，存储器按字节编址，已知A的起始存储地址（基址）为1000，在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__（3）_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点，左孩子是第 (6) 个节点。如果该二叉树有10层，则共有 (7) 个节点。 5. 请描述在循环队列Q中，队头和队尾指针分别由front和rear表示，该队列有10个存储空间，判断队空和队满的条件分别分：_____(8)________,_______(9)_________。 6. 字符串t=”child”，s=”cake”，请写出下列函数的结果：StrLength(t) =（10）__;Concat(SubString(s,3,1)，SubString(t,2,2))=____（11）___。 7. 一棵二叉树为 则后序序列为（12），中序序列为（13），先序序列为__（14）____。 8. 请用数据序列{53，17，12，66，58，70，87，25，56，60 }构造一棵二叉排序树_(15）_。 9.。一个栈输入的序列式1,2,3，则可能的且以2为开头的输出序列是 (16) ，不可能的序列是____（17）____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据：2，3，4，8，9，11，13查找11，若采用折半查找法，则在（19）次比较后，才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中，平均情况下（20）_____最快。 二简答题： 1给定{15,3,14,2,6,9,16,17}，试为这8个数设计哈夫曼编码，并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。（要求使用图画出每一步过程）。 C G E D F B H A

02331数据结构200710

2007年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码2331) 本试卷共12页，满分100分；考试时间150分钟。 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下面程序段的时间复杂度为 A．O(1) B．O(log n) C．O(n) D．O(n2) 2．已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在8所指结点之后插入上述链表应执行的语句为【】 3．在计算机内实现递归算法时所需的辅助数据结构是【】 A．栈B．队列 C．树D．图 4．假设以数组A[m]存放循环A[m]的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置。则队头元素所在的存储位置为【】 5．通常将链串的结点大小设置为大于l是为了【】 A．提高串匹配效率B．提高存储密度 C．便于插入操作D．便于删除操作 6．带行表的三元组表是稀疏矩阵的一种【】 A．顺序存储结构B．链式存储结构 C．索引存储结构D．散列存储结构 7．表头和表尾均为空表的广义表是【】 A．( ) B．( ( ) ) C．( ( ( ) ) ) D．( ( )，( ) ) 8．用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为【】A．n-1 B．n C．n+l D．2n 9．为便于判别有向图中是否存在回路，可借助于【】

A．广度优先搜索算法B．最小生成树算法 C．最短路径算法D．拓扑排序算法 10．连通网的最小生成树是其所有生成树中【】 A．顶点集最小的生成树B．边集最小的生成树 C．顶点权值之和最小的生成树D．边的权值之和最小的生成树 11．按排序过程中依据的原则分类，快速排序属于【】 A．插入类的排序方法B．选择类的排序方法 C．交换类的排序方法D．归并类的排序方法 12．下列关键字序列中。构成小根堆的是【】 A．{84，46，62，41，28，58，15，37} B．{84，62，58，46，4l，37，28，15} C．{15，28，46，37，84，41，58，62} D．{15，28，46，37，84，58，62，41} 13．在长度为32的有序表中进行二分查找时，所需进行的关键字比较次数最多为【】A．4 B．5 C．6 D．7 14．假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为【】 A．n-1 B．n C．n+l D．n+2 15．散列文件也称为【】 A．顺序文件B．索引文件 C．直接存取文件D．间接存取文件 二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16．数据的逻辑结构描述数据元素之间的________________________，与存储方式无关。17．在一个长度为100的顺序表中删除第10个元素时，需移动________________________个元素。 18．队列的队尾位置通常是随着________________________操作而变化的。 19．两个空串联接得到的串的长度为________________________。 20．设对称矩阵A压缩存储在一维数组B中，其中矩阵的第一个元素a11存储在B[0]，元素a52存储在B[11]，则矩阵元素a36存储在B[________________________]中。 21．已知一棵哈夫曼树含有60个叶子结点，则该树中共有________________________个非叶子结点。 22．如图所示的有向图中含有________________________个强连通分量。 23．已知一组关键字为{15，36，28，97，24，78，47，52，13，86}，其中每相邻两个关键字构成一个有序子序列。对这些子序列进行一趟两两归并的结果是

郝斌数据结构自学笔记--知识点+程序源代码

郝斌数据结构自学笔记 --知识点+程序源代码 By-HZM 1_什么叫做数据结构 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。 ~ 数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作 2_衡量算法的标准 算法 解题的方法和步骤 ~ 衡量算法的标准 1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性 3_数据结构的特点 【 数据结构的地位 数据结构是软件中最核心的课程 程序=数据的存储+数据的操作+可以被计算机执行的语言 4_预备知识_指针_1 5_预备知识_指针_2 * 指针的重要性： 指针是C语言的灵魂 定义：

地址： 地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】 CPU=====地址线，控制线，数据线=====内存 指针： … 指针就是地址，地址就是指针。 指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。 分类： 1.基本类型的指针 2.指针和数组的关系 ? 变量并不一定连续分配，随机分配内存。 内存： 内存是多字节组成的线性一维存储空间。 内存的基本划分单位是字节。 每个字节含有8位，每一位存放1个0或1个1. 内存和编号是一一对应的。 （ 软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。 NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。 2）局部变量只在本函数内部使用。 如何通过被调函数修改主调函数中普通变量的值。 1）实参为相关变量的地址； < 2）形参为以该变量的类型为类型的指针变量； 3）在被调函数中通过 *形参变量名的形式的形式就可以修改主函数。 CASE 1 #include<> int main(void) { |

计算机专业基础综合数据结构(栈和队列)历年真题试卷汇编6

计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编6 (总分：60.00，做题时间：90分钟) 一、单项选择题(总题数：14，分数：28.00) 1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是( )。【2009年 全国试题1(2)分】 A.栈 B.队列√ C.树 D.图 2.设栈S和队列Q的初始状态均为空，元素a，b，c，d,e,j,g=g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b，d，c，f，e，a，g，则栈S的容量至少是( )。【2009年全国试题2(2)分】 A.1 B.2 C.3 √ D.4 按元素出队顺序计算栈的容量。b进栈时栈中有a，b出栈，cd进栈，栈中有acd，dc出栈，ef进栈，栈 中有aef,fea出栈，栈空，g进栈后出栈。所以栈S的容量至少是3。 3.若元素a，b，c，d,e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是( )。【2010年全国试题1(2)分】 A.d,c，e，b，f,a B.c，b，d,a，e，f C.b，c，a，e，f，d D.a,f，e,d,c，b √ 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a，b，c，d，e依次入此队列后再进行出队操作，则不可能得到的出队序列是( )。【2010年全国试题2(2)分】 A.b，a，c，d, e B.d,b，a，c，e C.d，b,c，a，e √ D.e，c，b，a，d a先入队，b和c可在a的任一端入队，选项A、B、D都符合要求，只有选项C不可能出现。双端队列出队结果的分析可参见四、36。 5.元素a，b，c，d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是( )。【2011年全国试题2(2)分】 A.3 B.4 √ C.5 D.6 元素d进栈时，元素a，b，c已在栈中，d出栈后，P可以在a，b，c任一元素的前面进栈并出栈，也可以在元素a后出栈，c，b，a必须依次出栈，所以元素d开头的序列个数是4。 6.已知循环队列存储在一维数组A[0．n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。[2011年全国试题3(2)分】 A.0，0 B.0，n—1 √ C.n一1，0

02331数据结构课后练习题

第1章概论 练习题 一、单项选择题 1．在数据结构中，从逻辑上可以把数据结构分为（B）A．紧凑结构和非紧凑结构B．线性结构和非线性结构 C．内部结构和外部结构D．动态结构和静态结构2．若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D）A．顺序存储结构B．链式存储结构 C．索引存储结构D．散列存储结构 3．算法分析的两个主要方面是（B）A．正确性和简明性B．时间复杂性和空间复杂性 C．可读性和可维护性D．数据复杂性和程序复杂性4．线性表采用链式存储结构时，要求内存中可用存储单元地址（A）A．不一定连续的B．部分地址必须是连续的 C．必须是连续的D．一定是不连续的 5．算法指的是（C）A．计算机程序B．解决问题的计算方法 C．解决问题的有限运算序列D．排序算法 二、填空题 6．数据结构一般包括逻辑结构、存储结构和数据运算三个方面的内容． 7．数据的逻辑结构可分为线性结构、非线性结构两大类． 8．数据的存储结构（物理结构）一般可以用顺序存储结构、链式存储结构、索引存储结构及散列存储结构等四种存储方法表示． 9．在选用求解一个问题的算法时，除了首先考虑算法是“正确的”之外，还主要考虑执行算法所需要的时间、执行算法所需要的存储空间及算法应易于理解、易于编程、易于调试等三点。 10．设有一批数据元素，为了最快地存取某元素，宜用顺序结构存储，为了方便的插入一个元素，宜用链式结构存储． 三、应用题 设n为正整数，利用大“O”记号，写出下列各程序段的时间复杂度． 11．for (i = 1; i <= n; i++){ y = y + 1; for (j = 1; j <= 2 * n; j++) x = x + 1; } 分析：语句“y = y + 1;”执行n次，语句“x = x + 1;”各执行2 2n次，故该程序段的时间复杂度为O(2n)．12．s = 0; while (n >= (s + 1) * (s + 1)) s = s + 1; 分析：语句“s = s + 1;．

数据结构复习笔记

数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------

2012版《数据结构高分笔记》更新补丁之外部排序

※特别章外部排序（2012版《数据结构高分笔记》更新补丁） ·外部排序简介 所谓外部排序，即对外存中的数据进行排序（相对于内部排序而言），也可以说是对文件中的数据进行排序。有了内部排序算法，为什么还要外部排序？因为文件太大，内存放不下。外排做法可以概括为一句话：将内存作为工作空间来调整外存中数据的位置。 具体可以分成以下三个要点： ①文件在外存中的组织； ②文件在内存中的排序； ③文件在内外存之间的交换。 说明：本补丁是2012年数据结构考研大纲新增内容，虽然知识点不多，但由于第一年被列入考试范围，所以大家要重视。 ·归并排序法 归并排序法是外排序中最常用的方法，分为两个执行阶段。第一阶段：将文件中的数据分段输入到内存中，在内存中用内排序方法对其分类，这样排序完的文件段称作归并段，然后将其写回外存中而在外存中形成了许多初始归并段。第二阶段：对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。 说明：外排序中的归并排序法和内排序中的归并法是类似的，都是由小单元逐渐归并成单元的过程，注意对比，加深理解。 归并排序算法分两个阶段： 1.初始归并段的形成 其过程是根据缓冲区大小，由文件输入（由外存读入内存）记录，当记录充满缓冲区后，选择最小的（以递增排序为例）记录输出（由内存写出到外存），其空缺位置由下一个输入记录来取代，输出的记录成为当前初始归并段的一部分。如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前部分归并段最大的记录要小（如例1中的关键字11，比15要小，不可能出现在当前归并段中），它将等待生成下一个归并段时提供选择。反复进行上述操作，直到所有新输入的记录关键字都小于最后输出记录的关键字时（如步骤9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。接着继续生成下一个归并段，直到全部记录都处理完毕为止。 下面通过例题来具体说明一下。 例1.设输入文件的各个记录的关键字为： 15,19,04,83,12,27,11,25,16,34,26,07,10,90,06, ... ... 假设内存缓冲区可容纳4个记录，成初始归并段。如下表所示，给出了生成初始归并段过程中各步的缓冲区内容和输出结果。

计算机专业基础综合数据结构(树和二叉树)历年真题试卷汇编6

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编 6 (总分：88.00，做题时间：90分钟) 一、单项选择题(总题数：33，分数：66.00) 1.一棵完全二叉树又是一棵( )。【华中科技大学2006一、7(2分)】 A.平衡二叉树 B.堆√ C.二叉排序树 D.哈夫曼(Huffman)树 完全二叉树的叶子至多在下面两层上，且一个结点若无左子树，绝不能有右子树。平衡二叉树任何结点的左右子树的高度差的绝对值不超过1，但其结点的值符合二叉排序树的定义。平衡二叉树(包括二叉排序树)的树形不一定是完全二叉树。堆是一个序列，有大堆和小堆，编号为i的结点，其父结点、左右子女结点之间位置的关系，符合完全二叉树父结点、左右子女结点之间的关系，从这点上说，可以把堆看成完全二叉树。哈夫曼树是二叉树，但树形不一定满足完全二叉树的定义。 2.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学1999一、5(2分)】 A.不确定 B.0 C.1 D.2 √ 左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共2个空链域。 3.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。【合肥工业大学2000一、5(2分)】 A.0 B.1 √ C.2 D.不确定 4.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则X的前驱为( )。【南京理工大学1996 一、6(2分)】 A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点√ D.X的左子树中最右叶结点 5.引入二叉线索树的目的是( )。【南京理工大学1998一、5(2分)】 A.加快查找结点的前驱或后继的速度√ B.为了能在二叉树中方便地进行插入与删除 C.为了能方便地找到双亲 D.使二叉树的遍历结果唯一 6.线素二叉树是一种( )结构。【西安电子科技大学1996一、9(2分)】 A.逻辑 B.逻辑和存储 C.物理√ D.线性 7.甩个结点的线索二叉树上含有的线索数为( )。【中山大学1998二、8(2分)】

数据结构学习总结

数据结构学习总结 经过一学期的学习，我对数据结构有了我自己的认识。一开始，我以为它和C语言和C++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生

全国2012年10月自考数据结构(02331)试题及答案

全国2012年10月高等教育自学考试 数据结构试题 课程代码：02331 请考生按规定用笔将所有试题的答案涂、写在答题纸上。 选择题部分 注意事项： 1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。 2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动，用橡皮擦干净后，再选涂其他答案标号。不能答在试题卷上。 一、单项选择题(本大题共l5小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1．一个算法的时间耗费的数量级称为该算法的 A．效率B．难度 C．可实现性D．时间复杂度 2．顺序表便于 A．插入结点B．删除结点 C．按值查找结点D．按序号查找结点 3．设带头结点的单循环链表的头指针为head，指针变量P指向尾结点的条件是 A．p->next->next==head B．p->next==head C．p->next->next==NULL D．p->next==NULL 4．设以数组A[0..m-1]存放循环队列，front指向队头元素，rear指向队尾元素的下一个位置，则当前队列中的元素个数为 A．(rear-front+m)％m B．rear-front+1 C．(front-rear+m)％m D．(rear-front)％m 5．下列关于顺序栈的叙述中，正确的是 A．入栈操作需要判断栈满，出栈操作需要判断栈空 B．入栈操作不需要判断栈满，出栈操作需要判断栈空 C．入栈操作需要判断栈满，出栈操作不需要判断栈空

数据结构历年真题收集第1章 绪论(含答案)

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。【北京邮电大学2000 二、3 （20/8分）】 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（）【中科院计算所 1998 二、1 （2分）】 A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 【南京理工大学 1999 一、1（2分）【武汉交通科技大学 1996 一、1（ 4分）】4．一个算法应该是（）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（）【南京理工大学 2000 一、1（1.5分）】 A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1]

操作系统可用来进行考研复习资料(1)

第八章死锁习题及答案 一、填空题 1．进程的“同步”和“互斥”反映了进程间① 和② 的关系。 【答案】①直接制约、②间接制约 【解析】进程的同步是指在异步环境下的并发进程因直接制约而互相发送消息，进行相互合作、相互等待，使得各进程按一定的速度执行的过程；而进程的互斥是由并发进程同时共享公有资源而造成的对并发进程执行速度的间接制约。 2．死锁产生的原因是① 和② 。 【答案】①系统资源不足、②进程推进路径非法 【解析】死锁产生的根本原因是系统的资源不足而引发了并发进程之间的资源竞争。由于资源总是有限的，我们不可能为所有要求资源的进程无限地提供资源。而另一个原因是操作系统应用的动态分配系统各种资源的策略不当，造成并发进程联合推进的路径进入进程相互封锁的危险区。所以，采用适当的资源分配算法，来达到消除死锁的目的是操作系统主要研究的课题之一。 3．产生死锁的四个必要条件是① 、② 、③ 、 ④ 。 【答案】①互斥条件、②非抢占条件、③占有且等待资源条件、④循环等待条件 【解析】 互斥条件：进程对它所需的资源进行排它性控制，即在一段时间内，某资源为一进程所独占。 非抢占条件：进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走，即只能由获得资源的进程自己释放。 占有且等待资源条件：进程每次申请它所需的一部分资源，在等待新资源的同时，继续占有已分配到的资源， 循环等待条件：存在一进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 4．在操作系统中，信号量是表示① 的物理实体，它是一个与② 有关的整型变量，其值仅能由③ 原语来改变。 【答案】①资源，②队列，③P-V 【解析】信号量的概念和 P-V原语是荷兰科学家 E．W．Dijkstra提出来的。信号量是一个特殊的整型量，它与一个初始状态为空的队列相联系。信号量代表了资源的实体，操作系统利用它的状态对并发进程共享资源进行管理。信号量的值只能由P-V原语来改变。 5．每执行一次P原语，信号量的数值S减1。如果S>=0，该进程① ；若S<0，则② 该进程，并把它插入该③ 对应的④ 队列中。 【答案】①继续执行，②阻塞（等待），③信号量，④阻塞（等待） 【解析】从物理概念上讲，S＞0时的数值表示某类资源可用的数量。执行 一次P原语，意味着请求分配一个单位的资源，因此描述为S=S－1。当S<0时，表示已无资源，这时请求资源的进程将被阻塞，把它排在信号量S的等待队列中。此时，S的绝对值等于信号量队列上的阻塞的进程数目。

最新自考02331数据结构试题及答案含评分标准资料

2018年10月高等教育自学考试全国统一命题考试 数据结构试卷 (课程代码02331) 本试卷共7页，满分l00分，考试时间l50分钟。 考生答题注意事项： 1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。 4．合理安排答题空间，超出答题区域无效。 第一部分选择题 一、单项选择题：本大题共l5小题，每小题2分，共30分。在每小题列出的备选项中 只有一项是最符合题目要求的。请将其选出。 1．下列数据结构中，逻辑结构不同的是 A．线性表 B．栈 C．队列 D．二叉树 2．将l6个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地址是l000，第6个元素的存储地址是1040，则最后一个元素的存储地址是 A．1112 B．1120 C．1124 D．1128 3．设栈的初始状态为空，元素1，2，3，4，5依次入栈，不能得到的出栈序列是 A．1，2，3，4，5 B．4，5，3，2，1 C．1，2，5，4，3 D．1，2，5，3，4 4．设指针变量P指向非空单链表中的结点，next是结点的指针域，则判断P所指结点为尾结点前一个结点的逻辑表达式中，正确的是 A. p->next!=NULL&&p->next一>next->next == NULL B．p->next!=NULL&&p->next->next—NULL C．p->next->next==NULL D．p->next—NULL 5．已知广义表LS=(((a，b，c)，d)，(e，(fg，(h i)))，LS的深度是 A．2 B．3 C．4 D．5 6．已知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是 A．5 8．8 C．10 D．27 7．已知二叉树T的前序遍历序列为a，b，c，e，d，中序遍历序列为C，e，b，d，a，则T 的后序遍历序列为 A．c，e，d,b，a B．d，e，c，b，a C．e，c，d，b，a D．e，c，b，a，d 8．有向图G有玎个顶点和e条边，G保存在邻接矩阵M中，M中0与1的个数差是 A．n(n+1)／2-e B．n(n+1)／2-2e C．n×n-e D．n×n-2e 9．有向图G中所有顶点的度数之和是24，则G中弧的数量是 A．10 B．12 C．14 D．16 10．设有向图G含有n个顶点、e条边，使用邻接表存储。对G进行深度优先搜索遍历算法的时间复杂度是 A．O(n) B．O(口) C．O(n+e) D．O(n×e) 11．对数据序列(26，14，17，12，7，4，3)采用二路归并排序进行升序排序，两趟排序后，得到的排序结果为 A．14，26，17，l2，4，7，3 B．12，l4，l7，26，3，4，7 C．14，26，12，l7，3，4，7 D．14，26，l2，l7，3，7，4

2018北大计算机考研经验分享

2018北大计算机考研经验分享 我本科毕业于北京科技大学计算机科学与技术专业，研究生将就读于北京大学计算机技术专业。初试考研总分接近370+分，计算机基础综合135分，在专业课上算是有些心得吧。 写这篇经验贴的初衷一是看过很多经验贴，都是比较散乱的回顾+感受，没有系统的复习方法；二是我在新祥旭考研一对一做专业课辅导老师，算是给自己打个广告吧，多说一句，我主要是针对考北大计算机专业的学生。当然，虽然打了一下广告，但是这篇帖子的经验还是希望大家认真看，我觉得还是能够对学弟学妹们有所裨益的。 ，下面主要和大家聊一聊北大计算机考研的情况，政治、英语、数学这些课我就不多说了，这几门课程的资料、老师都是比较成熟且成功的，大家在网上多看看就知道怎么回事了。今天，主要是说专业课以及北大计算机的招录情况。 【北大招录情况】 2018年北大软微计算机技术复试线：复试线为300分，单科线也是50+80。具体的招录比现在基本是没有相关数据的，但是招生人数还是可查的，根据软微学院官网数据：整个软件与微电子学院招收全日制654人，非全日制156人。其中计算机技术专业全日制招生310人，

包含推免生接近70人，留给其他考生的名额为240左右。 总之，现在是大数据时代，北大计算机技术的关注度也越来越高，所以以后考研竞争难度也会越来越大。 【参考书目】 822计算机基础综合 专业课教材 《数据结构》（C语言版）严蔚敏清华大学出版社 《计算机操作系统》汤子瀛西安电子科技大学出版社 《计算机网络》谢希仁电子工业出版社 《计算机组成原理》唐朔飞高等教育出版社 专业辅导书： 王道系列 《数据结构考研复习指导》 《计算机组成原理考研复习指导》 《操作系统考研复习指导》 《计算机网络考研复习指导》 《计算机专业基础综合考试指导全书》 《计算机专业基础综合考试名校真题精析》 《计算机专业基础综合考试最后8套模拟题》

计算机专业基础综合数据结构(概论)历年真题试卷汇编3

计算机专业基础综合数据结构（概论）历年真题试卷汇编3 (总分：70.00，做题时间：90分钟) 一、单项选择题(总题数：15，分数：30.00) 1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。【2011年全国硕士研究生入学计算机学科专业基础综合试题】简称【201 1年全国试题1(2分)】 x=2； while(x *x； （分数：2.00） A.O(log 2 n) √ B.O(n) C.O(nlog 2 n) D.O(n 2 ) 解析： 2.求整数n(n≥0)阶乘的算法如下，其时间复杂度是( )。【2012年全国试题1(2分)】int fact(int n){if(n<=i) return i；return n*fact(n一1)； （分数：2.00） A.O(log 2 n) B.O(n) √ C.O(nlog 2 n) D.O(n 2 ) 解析： 3.已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是( )。【2013年全国试题1(2)分】 （分数：2.00） A.O(n) B.O(m×n) C.O(min(m，n)) D.O(max(m，n)) √ 解析： 4.下列程序段的时间复杂度是( )。【2014年全国试题1(2分)】count=0;for(k=1；k<=n；k*=2)for(j=1；j<=n；j++)count++； （分数：2.00） A.O(log 2 n) B.O(n) C.O(nlog 2 n) √ D.O(n 2 ) 解析： 5.在数据结构中，数据的最小单位是( )。【北京理工大学2006九、1(1分)】 （分数：2.00） A.数据元素 B.字节 C.数据项√ D.结点 解析： 6.在数据结构中，数据的基本单位是( )。【北京理工大学2004五、1(1分)】 （分数：2.00） A.数据项 B.数据类型 C.数据元素√