数据结构与算法,线性表,矩阵,广义表(3学时)

第一部分数据结构与算法什么是数据结构？定义1--是相互之间存在一种或多种特定关系的数据元素的集合。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。例如：数据的物理结构包括

的表示和

的表示。答案：数据元素

，

数据元素间关系

。逻辑结构--数据元素间的相互关系。存储结构（物理结构）---数据元素及其关系（数据的逻辑结构）在计算机存储器中的存储形式。逻辑结构---划分方法一（1）线性结构（如：线性表、栈、队列、串）（2）非线性结构（如：树、图）逻辑结构---划分方法二（1）集合结构中的数据元素除了同属于一种类型外，别无其它关系。（2）线性结构结构中的数据元素之间存在一对一的关系。（3）树型结构结构中的数据元素之间存在一对多的关系。（4）图状结构或网状结构结构中的数据元素之间存在多对多的关系。例如：对于给定的n个元素，可以构造出的逻辑结构有集合________.________以及图状结构或网状结构四种。答案：线性结构，树型结构例如：从逻辑上可以把数据结构分为（）两大类。

A、动态结构、静态结构B、顺序结构、链式结构

C、线性结构、非线性结构

D、初等结构、构造型结构存储结构（1）顺序存储结构（2）链式存储结构（3）散列存储结构（4）索引存储结构例如：下面哪个不是数据结构的基本存储方法（）A顺序方法B链接方法C随机方法D索引方法答案：C5抽象数据类型抽象数据类型(AbstractDataType

，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。

ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。

ADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。例如：数据结构的二元组定义DS={D,S}，D是数据元素的有限集合，而S则是D上的（）的有限集合。A.数组B.数据项C.关系D.操作答案：C

算法是解决某一类问题的步骤的描述。一般而言，算法应该符合以下五项要求：(1)输入：它接受一些输入（有些情况下不需要输入）；(2)输出：至少产生一个输出；(3)确定性：算法的每一步必须有充分明确的含义，不可以有歧义；(4)有穷性：算法是一个有限指令集，并一定在有限步骤之后终止；(5)可行性：算法的每一步必须在计算机能处理的范围之内

算法的描述不依赖于任何一种计算机语言以及具体的实现手段。可以用自然语言、流程图，伪代码等方法来描述。10/25算法

衡量、比较算法优劣的指标主要有两个：

空间复杂度S(n)——根据算法写成的程序在执行时占用的存储空间的大小。该存储空间一般包括三个方面：（1）指令常数变量所占用的存储空间;

（2）输入数据所占用的存储空间;

（3）辅助(存储)空间。一般地，算法的空间复杂度指的是辅助空间。

时间复杂度

T(n)——根据算法写成的程序在执行时耗费时间的长度。常用程序中最深层循环内的语句的原操作的执行频度(重复执行的次数)来表示12/25算法分析例如：一个算法具有以下5个重要特性。()A．有穷性、确定性、可行性、输入、输出

B．可行性、可移植性、可扩充性、输入、输出

C．确定性、有穷性、稳定性、输入、输出

D．易读性、稳定性、安全性、输入、输出答案：A例如：下面叙述正确的是（）

A、算法的执行效率与数据的存储结构无关

B、算法的空间复杂度是指算法程序中指令（或语句）的条数

C、算法的有穷性是指算法必须能在执行有限个步骤之后终止

D、以上三种描述都不对答案：C第二部分线性表、栈、队列

线性表“线性表(LinearList)”是由同一类型的数据元素构成的序列的线性结构。

线性表中元素的个数称为线性表的长度；当一个线性表中没有元素（长度为0）时，称为空表。

线性表的顺序存储实现在内存中用地址连续的一块存储空间顺序存放线性表的各元素。一维数组在内存中占用的存储空间就是一组连续的存储区域。

在长度为n的线性表L中的第i(1≤i≤n+1)个位置插入新结点，平均需要移动元素的次数为n/2最坏：当i=1,需移动全部n个结点（O(n)）最好：当i=n+1（在表尾插入）,无需用移动结点。（O(1)）在长度为n的线性表L中删除第i(1≤i≤n)个元素，其时间同样主要耗费在表中结点的移动操作上，平均需要移动元素的次数为(n-1)/2最坏：当i=1,需移动n-1个结点（O(n)）最好：当i=n（删除表尾元素）,无需用移动结点。（O(1)）

顺序存储的优缺点优点1）无须为表示结点间的逻辑关系而增加额外的存储空间（紧凑结构）。2）可以方便地随机存取表中的任一结点。缺点1）插入和删除平均须移动一半结点。2）存储分配只能预先进行（静态）例如1、若某线性表最常用的操作是存取任一个指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A、顺序表B、单链表C、带头结点的双循环链表D、单循环链表2、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为()(1<=i<=n+1)。

A．0(O)B．0(1)C．0(n)D．0(n2)3、如果最常用的操作是取第i个结点及其前驱，则采用()存储方式最节省时间。

A．单链表B．双链表C．单循环链表D．顺序表答案：A答案：C答案：D

线性表的链式存储实现不要求逻辑上相邻的两个数据元素物理上也相邻，它是通过“链”建立起数据元素之间的逻辑关系。因此对线性表的插入、删除不需要移动数据元素，只需要修改“链”。12/25线性表单链表（带头结点，不带头结点）单向循环链表双向循环链表头结点的作用：头结点指向整个链表，起标识作用，此外，还能简化插入、删除等操作。例如1、从带头结点的双向循环链表中删除p指针所指向的后继结点的操作时如下哪个？（

）2、在单链表中设置头结点的作用是

标识该链表

且

能简化插入、删除等操作

。3、对于双向链表，在两个结点之间插入一个新结点需修改的指针共（

）个。A、1B、2C、3D、44、带头结点的双循环列表L为空表的条件是

L->prior==L==L->next.5、在一个双链表中，在*p结点之前插入*q结点的操作是()。

A.p->prior=q;q->next=p;p->prior->next=q;q->prior=p->prior;

B.q->prior=p->prior;p->prior->next=q;q->next=p;p->prior=q->next;

C.q->next=p;p->next=q;q->prior->next=q;q->next=p;D.p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q;答案：D答案：D答案：D编程题1、有一个带头结点的单链表L={a1，b1，a2，b2，……，an，bn}，请设计一个函数将其拆成两个带头结点的单链表A和B，正序链表A={a1，a2，…，an}逆序链表B={bn，bn-1，……，b2，b1}。注：函数的头部为voidsplit（Linklist*L，LinkList*A，LinkList*B）。2、假设用单链表方式来存储整数序列，如下形式：请编写一个递归算法，对这样的链表进行处理，重复结点（值相同的结点）仅保留排在最前面的一个，最后返回新链表的首地址。3、设有一个表头指针为first的单链表（不带头结点），请设计算法通过一趟遍历将链表就地逆转（例如a->b->c->d变为d->c->b->a),要求逆转后表头指针first指向原链表的最后一个结点，请写出C语言程序。题型小结：链表逆置删除链表中重复元素拆分+逆置

例：有一个带头结点的单链表L={a1，b1，a2，b2，……，an，bn}，请设计一个函数将其拆成两个带头结点的单链表A和B，正序链表A={a1，a2，…，an}逆序链表B={bn，bn-1，……，b2，b1}。

注：函数的头部为voidsplit（Linklist*L，LinkList*A，LinkList*B）。答：算法思想：扫描单链表L，将奇数位置的元素添加到链表A中，将偶数位置的元素逆向添加到链表B中。voidsplit（Linklist*L，LinkList*A，LinkList*B）{

Linklist*pL=L->next,*pA=A,*pB=B,*temp;

while(pL!=NULL){

pA->next=pL;pA=pL;//把奇数位置的结点正向添加到链表A中

pL=pL->next;//pL指向下一个结点

pA->next=NULL;（注意这两句顺序不能颠倒）

temp=pL->next;//把PL的下一个结点的地址先保存下来

pL->next=pB->next;//把偶数位置的结点逆向添加到链表B中

pB->next=pL;

（注意：实际上是链表逆置的主要操作）

pL=temp;}}链表A的建立过程类似于尾插入法，链表B的建立过程类似于头插入法。删除重复元素

例：假设用单链表方式来存储整数序列，如下形式：

请编写一个递归算法，对这样的链表进行处理，重复结点（值相同的结点）仅保留排在最前面的一个，最后返回新链表的首地址。例如，若有上述链表，则处理后的新链表如下：

算法思想：从单链表的第一个结点开始，对每个结点进行检查：检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。递归算法：voidRecDelete_Node(LNode*L){//删除以L为头结点的单链表中所有值相同的结点

if(L==NULL)return;LNode*pre=L,*cur=pre->next;//pre始终指向当前结点cur的前一个位置while(cur!=NULL)//检查链表中所有结点{if(cur->data==L->data){pre->next=cur->next;free(cur);cur=pre->next;}else{pre=cur;cur=cur->next;}}L=L->next;

RecDeleteNote(L);}非递归算法：voidIterDeleteNode(LNode*L){//删除以单链表L中所有值相同的结点

LNode*p=L,*q,*ptr;while(p!=NULL)//检查链表中所有结点{q=p,ptr=p–>next;//检查结点p的所有后继结点ptrwhile(ptr!=NULL){if(ptr–>data==p->data){q->next=ptr->next;free(ptr);ptr=q->next;}else{q=ptr;ptr=ptr–>next;}}p=p->next;}}栈

堆栈的定义“堆栈（Stack）”可以认为是操作受到一定约束的线性表，插入和删除操作都作用在一个称为栈顶(Top)的端点位置。入栈（Push）：把数据插入栈顶位置；出栈（Pop）

：从栈顶中取出数据。栈的特点：先进后出（后进先出）栈的应用：数制转换，表达式求值，括号匹配，函数（递归）调用3、设计一个判别表达式中左、右括号是否配对出现的算法，采用下列哪种数据结构最好？（

）A、栈B、队列C、线性表的顺序存储结构D、线性表的链式存储结构答案：5答案：D答案：A栈例如

1、设栈S和队列Q的初始状态为空，元素a1，a2，a3，a4，a5，a6，a7和a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的顺序是a3，a6，a7，a5，a8，a4，a2，a1，则栈的容量至少应该是_______.2、若5个元素的出栈序列为“e1，e2，e3，e4，e5”，则可能的入栈序列为（

）A、e2，e3,e4,e1,e5B、e3,e1,e4,e5,e2C、e5,e3,e4,e2,e1D、e4,e1,e3,e2,e5答案：B4．一个栈的进栈序列是abcde，则栈的输出序列不可能的是()。

A.edcbaB.decbaC.dceabD.abcde5．表达式a*(b+c)-d的后缀表达式是()。

A．abcd*+-B．abc+*d-C．abc*+d-D．-+*abcd答案：C栈3、表达式“#3*2^(4+2*2-6*3)-5#”求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A、3,2,4,1,1；#*^(+*-B、3,2,8；#*^-C、3,2,4,2,2；#*^(-D、3,2,8；#*^(-答案：D22将过程“中缀->后缀”与“对后缀求解”，合并为一个程序，边扫描边运算！算法的基本思想及处理规则定义两个栈：一个称为OPTR，用于存放运算符；另一个称作OPND，用于寄存操作数或运算结果。初始化：首先置操作数栈为空；运算符栈OPTR栈低元素为“#”。依次读入表达式中的各字符操作数：直接进OPND栈。操作符：如当前运算符<栈顶运算符，栈顶运算符出栈，并从OPND栈中退出两个操作数，执行栈顶元素的操作符的运算，再将计算结果入OPND栈。如当前运算符>栈顶运算符：当前运算符入OPTR栈。如当前运算符=栈顶运算符（1）“（”=“）”，脱去括号并接收下一字符；（2）“#”=“#”，表示整个表达式求值完毕。

利用栈直接计算中缀表达式：＋－×／()#＋>><<<>>－>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=23步骤中缀表达式STACK(底

顶)OPND栈(底

顶)13＋(5－8／4)×2##2＋(5－8／4)×2##33(5－8／4)×2##＋345－8／4)×2##＋(35－8／4)×2##＋(3568／4)×2##+(－357／4)×2##＋(－35884)×2##＋(－/3589)×2##＋(－/358410)×2##＋(－35211)×2##＋(3312×2##＋33132##＋×3314##＋×33215##+3616##9

直接计算中缀表达式示例：（

3＋(5－8／4)×2

）24建立一个栈，用作符号进出建立一个字符数组，用来存放后缀表达式转换规则：从左到右遍历中缀表达式的每个数字和符号。若是数字，则存入字符数组，作为后缀表达式的一部分；若是符号栈为空，则进栈；左括号“（”，进栈；右括号“）”，将栈顶元素依次取出存入字符数组（出栈），直到遇到左括号“（”，脱括号；其他情况，判断其与栈顶符号的优先级优先级>

栈顶符号，进栈优先级<栈顶符号，则将优先级高于该符号的那些栈顶符号依次出栈并存入字符数组，然后该符号进栈。若到中缀表达式最后，则将栈中符号依次取出，存入字符数组。

中缀表达式转换为后缀表达式更好的办法：利用树型结构实现！25队列

入队：在队尾插入数据出队：从队列头部取出数据。队列的特点：

“先进先出”

队列的定义“队列(Queue)”是具有一定操作约束的线性表，插入和删除操作有一定要求：只能在一端（队尾）插入，而在另一端（队首）删除。队列的顺序存储：存在“假溢出”现象，用循环队列可以克服“假溢出”现象。队列的链式存储结构循环队列：队空、队满的条件，入队、出队的操作，循环队列中元素的个数等。◆循环队列为空：Q.front==Q.rear

◆循环队列满：(Q.rear+1)%MaxSize==Q.front

◆入队的操作：Q.rear

=(Q.rear+1)%MaxSize◆出队的操作:Q.front

=(Q.front+1)%MaxSize◆循环队列中元素的个数:(Q.rear-Q.front+MaxSize)%MaxSize

2．循环队列A[0．．m-1]存放其元素值，用front和rear分别表示队共和队尾，当前队列的长度是()。A．rear-front+lB．rear-frontC．(rear-front+m)％mD．(rear-front)％m答案：C例如1、栈和队列都是

操作受限的线性表

，它们的共同点是只允许在它们的

端点

进行插入和删除。

答案：D3．环形队列qu的队空条件是()。

A.(qu.rear+l)%MaxSize==(qu.front+l)%MaxSize:

B.(qu.rear+l)%MaxSize==qu.front+l:

C.(qu.rear+l)%MaxSize==qu.front:

D.qu.rear==qu.front：1、设数组a[1…50,1…80]的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存储，则元素a[45,68]的存储地址为

9174

；若以列序为主序顺序存储，则元素a[45,68]的存储地址为

8788

。2、数组A[0…5，0…6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5]的地址是（）

A、1175B、1180C、1205D、1210二维数组采用顺序存储结构，有行优先和列优先之分。答案：A数组与广义表广义表表长n表深h表头表尾A=()01————B=(e)11e()C