数据结构高课件

第一、二、三章复习1第一章概述2数据的逻辑结构：描述数据间的逻辑关系。典型的逻辑结构：集合、线性、树、图数据的存储结构：逻辑结构在存储器中的映象。典型的存储结构：顺序和链式ADT：是对数据结构的一种更准确的抽象描述，它忽略了数据结构的具体实现步骤，将更多的注意力放在数据的基本操作上，通过基本操作描述数据的逻辑关系。它包括三个部分：数据对象、数据关系和基本操作。什么是算法的时间复杂度？如何计算？什么是算法的空间复杂度？如何计算？第一章作业31、在数据结构中，与所使用的计算机无关的是数据的（）A.存储结构B.

逻辑结构C.逻辑和物理结构D.物理结构2、数据结构在计算机内存中的表示是指（）A.数据元素的结构B.

数据的逻辑结构C.数据的存储结构D.数据元素之间的关系3、算法时间复杂度的含义是指算法的（）A.执行时间的长短B.执行时间的增长率C.执行语句的多少D.需要的存储空间4、如果某算法对于规模为n

的问题的时间耗费为T（n）=

n3

，在一台计算机上运行时间为t秒，则在另一台运行速度是其64倍的机器上，用同样的时间能解决的问题规模是原问题规模的（）A.4倍B.8倍C.

64倍D.

16倍45、下面程序段的时间复杂度为（）for

(

i=0;

i<m;

i++

)for

(

j=0;

j<n;

j++

)A[i][j]

=

i*j;A.

O

(m

*

m)B.

O

(m

*

n)C.

O

(m

+

n)D.

O

(n

*

n)5第二章线性表线性表是n个具有相同类型的数据元素构成的有限序列线性表的存储链序存储(链表)顺序存储(顺序表)双向循环链表单向循环链表单链表链表的静态存储6线性表的操作结构性操作ListEmpty(

L)

//判断线性表是否为空ListLength(

L)

//求线性表的长度GetElem(

L,i,

&e)//读取第i个元素的值LocateElem(L,e,

compare())//定位eListTraverse(L,visit())

//遍历线性表属性类操作ListInsert(&L,i,e)

//插入数据元素ListDelete(&L,

i,

&e)

//删除数据元素……引用性操作加工性操作InitList(&L)

//初始化一个线性表DestroyList(&L)

//删除线性表71、顺序表0

1….i-2

i-1….

n-1a1a2…ai-1ai…antypedef struct

{ElemType

*elem;

//存储空间基址int

length;

//当前长度int

listsize;

//当前分配的存储容量//(以sizeof(ElemType)为单位)}SqList;

//俗称顺序表elemlengthlistsizeLSqList

L;L.elem+L.

length－1L.elem+L.

listsize－18顺序表的插入删除操作34161182531341612531341613018253134161182531ListInsert(&L,

5,

30)123456789ListDelete

(&L,

5,

&e)123456789操作步骤判断位置合法性依次后length-i+1个元素后移一位将新元素e写入到第i个位置将表的长度加1操作步骤判断位置合法性将第i个位置的值赋给变量e依次后length-i+1个元素前移一位将表的长度减19顺序表的插入删除操作2Eis(n

-

i

+1)

=

nn

+1=

1

n+1i=1若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：2=

1(n

-

i)

=

n

-1nEni=1dl102、链表用一组地址任意的存储单元存放线性表中的数据元素a1…...an^a2L:头指针表尾:空指针头结点11typedef

struct LNode

{ElemType

data;

//数据域struct

LNode

*next;

//指针域}

LNode,

*LinkList;LinkList L；//L

为单链表的头指针链表的定义L:头指针

头结点

表尾:空指针a1a2…...an^12链表的基本操作（1）GetElem(L,i,&e)

//取第i个数据元素基本操作：移动指针i次。结束条件：1、找到第i个结点2、i大于链表的长度,即p＝null基本方法: 1、设置一个计数器j；

2、设置一个依次向后移动的指针p

。a1a2…...an^13主循环：while

(p

&&

j<i) {

p

=

pnext;

++j;

}链表的基本操作（2）ai-1eaipss

next

=pnext;pnext

=s;14ListInsert(&L,

i,e)¤

基本操作：¶找到线性表中第i-1个结点¶修改其后继指针链表的基本操作（3）ListDelete(&L,

i,

e)¤

基本操作：¶找到线性表中第i-1个结点¶修改其后继指针ai-1aiai+1ai-1pq

=

pnext;pnext

=

qnext

;

free(q);q正确连接指针15找到正确位置不要丢失结点其它链表a1a2an……单向循环链表双向链表双向循环链表……a1

a2

…

...

an16静态链表静态链表：用数组实现的链式结构82ZHAO3QIAN4SUN5LI9ZHOU0010WAN67备用空间链表头结点space(0)数据链表头结点space(1)数据链表尾结点备用空间链表尾结点space012345678910同时维护两个链表：备用空间链表17完成对一个链表的插入操作同时完成对另一个链表的删除操作第二章作业181、在下列各项叙述中，正确的说法是（）A.在线性表中，每个元素有且仅有一个直接前趋，有且仅有一个直接后继B.

线性表中至少有一个元素

C.在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继D.线性表中元素必须从大到小或从小到大排列2、用线性链表存储线性表时，要求存储空间（）A.连续不连续都可以B.

部分元素的存储空间必须是连续的C.必须是连续的D.必须是不连续的3、对于经常要存取线性表任意指定位置元素的应用，线性表应采用的存储结构是（）a.

链式b.

线性链表c.

栈d.

顺序194、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）a.

访问第i个元素的前驱（1<i≤n

）b.对顺序表中元素进行排序c.

删除第i个元素(1≤i≤n)d.在第i个元素之后插入一个新元素(1≤i≤n)5、线性表的顺序存储结构是通过何种方式表示元素之间的关系（）A.保存左、右孩子地址B.后继元素的数组下标C.元素的存储顺序–

D.保存后继元素地址206、若长度为n

的线性表采用顺序存储结构，在其第i

(1≤i≤n+1)

个位置之前插入一个新元素的算法时间复杂度为(

)–

a.

O(n^2)–

b.

O(n/2)c.

O(n

)d.

O(log2

n)7、在一个单链表中，已知指针p指向其中的某个结点，若在该结点前插入一个由指针s指向的结点，则需执行(

)a.

r

=

p->next;

p->next

=

s;

s->next

=

r;b.

p->next

=

s;

s->next

=

p;c.

s->next

=

p->next;

p->next

=

s;d.以上都不对218、在链式存储结构中，体现数据之间关系的是（）a.

数据在内存的相对位置b.

指示数据元素的指针c.

指针d.

数据的存储地址9、静态链表与动态链表相比，其缺点是（）a.

插入、删除时需移动较多数据b.

不能随机存取c.

有可能浪费较多存储空间d.

以上都不是2210、若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储结构算法的时间效率最高的是（）a.

单链表b.

给出表尾指针的单循环链表c.

双向链表d.

给出表尾指针双向循环链表2311、算法指的是

。24–(A)计算方法(B)排序方法–(C)查找方法(D)解决问题的有限运算序列12、算法设计需要达到的目标是

。–（A）正确性–（C）低存储（B）高效率（D）全是13、以下

操作不是栈的基本运算。–（A）删除栈顶元素（B）删除栈底元素–（C）判断栈是否为空（D）将栈置为空栈14、在顺序存储结构中，只要知道

，就可在相同时间内求出任一结点的存储地址。25–（A）基地址–（C）向量大小（B）结点大小（D）基地址和结点大小

15、对于给定的n个元素，可以构造出的逻辑结构有

、

、

、

四种。16、单链表中指针P所指结点不为尾结点的条件是

。17、在有头结点的单链表中，第1个结点的地址存放在（

）中，其他结点的存储地址存放在前驱结点的

域中。第三章栈和队列栈和队列都是操作受限的线性表栈：限定仅能在表尾一端进行插入、删除操作的线性表；栈的特点：后进先出的线性表LIFO-Last

In

First

Outana2a1栈顶栈底出栈进栈26第三章栈和队列队列：一端插入，另一端删除从尾进，从头出队列的特点：先进先出的线性表FIFO-First

in

First

outa1an-1an出队列进队列队首队尾27堆栈的基本操作Pop(&S,

&e)

,Push(&S,

e)顺序栈：Push(&S,

e)：

*S.top++

=

ePop(&S,

&e)：

e

=

*--S.top;an-1a2a1basetop#define

STACK_INIT_SIZE

100#define

STACKINCREMENT

10typedef

struct

{SElemType

*base;

//栈底SElemType

*top;

//栈顶int

stacksize;

//栈的大小}

SqStack;28堆栈的基本操作Pop(&S,

&e)

,

Push(&S,

e)链式栈Push(&S,

e)：在链表开始插入一个新节点Pop(&S,

&e)：删除链表第一个节点topa1…...an^a229队列的基本操作EnQueue(&Q,

e)，DeQueue(&Q,

&e)链式队列EnQueue(&Q,

e)：在链表最后插入一个新节点DeQueue(&Q,&e)：删除链表第一个节点…a1a2an^frontrear3031队列的基本操作顺序队列EnQueue(&Q,

e)：队列尾指针加1DeQueue(&Q,&e)：队列头指针加1Q.baseQ.rearQ.front143

2

1J6J5

4

5

0

J7Q.rearQ.frontJ3J2J1Q.base循环顺序队列：注意判断队列空和满的条件第三章作业321、队列和栈的共同点是

【

】A.

LIFOB.都是线性表C.无共同点D.

FIFO2、若用一个大小为

6

的数组来实现循环队列，且当前

rear

和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，

rear

和

front

的值分别为

【

】–

A.5和1–

C.4和2B.

1和5D.2和43、向一个栈顶指针为h

的带头结点链栈中插入指针s

所指的结点时，应执行的语句序列是【

】A.

s→next

=

h；h

=

h→next；B.

s→next

=

h→next；h→next

=

s；C.

h→next

=

s；D.

s→next

=

h；4、对于循环队列，正确的是

【

】–A.无法判断队列是否为满B.

循环队列不会满C.无法判断队列是否为空D.以上说法都是错误的335、设栈S

和队列Q

的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,

f,e,

a,g

，则栈S

的容量至少是【】–

A.

2 B.

1 C.

3 D.

4346、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是，【

】A.

栈

B.

图C.

树

D.

队列7、若一个栈的输入序列为1

，2

，3

，…，n

，输出序列的第1个元素为n

，则第i

个输出的元素是()35A.

iC.

n−i+1B.

n−iD.可是其他任意元素8、用不带头结点的单链表存储队列，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时，(

)A.队头，队尾指针都要修改B.队头，队尾指针都可能要修改C.仅修改队头指针D.仅修改队尾指针9、一个栈的输入序列为：12345，则下列序列中不可能的输出序列是，

【

】36–

A.

1

5

4

3

2–

C.

2

3

4

1

5B.

5

4

2

3

1D.

2

3

1

4

510、在算符优先算法中，算符‘＋’和‘（’的优先关系应是，

【

】–

A.

‘＋’<‘（’–

B.

‘＋’=‘（’C.取决于它们出现的位置D.

‘＋’>‘（’综合练习题37判断正误在单链表中,指向第一个结点的指针定义了该链表能够通过在链表的表头不断插入新结点来创建一个单向链表堆栈和队列不属于线性表循环队列是一种物理结构删除单链表的最后一个结点需要遍历整个链表YYNNY练习题--选择题381、向具有n个不同元素的链表中插入一个数据元素,最坏情况下需要访问

个元素?–

[A]

n [B]

n/2

[C]1

[D]n/32、若链表中的元素有序,下列叙述哪一个正确?[A]找第k个元素的时间复杂度是O(1)[B]插入一个给定元素的时间复杂度是O(n2)[C]删除一个给定元素的时间复杂度是O(1)[D]查找一个元素a是否属于链表的时间复杂度是O(n)AD练习题--选择题DC393、设栈的输入序列是1、2、3、4，则

不可能是其出栈序列：–

[A]

1234 [B]

2134

[C]1432

[D]43124、若频繁地对线性表进行插入和删除操作，该线性表应该采用

存储结构。–

[A]散列

[B]顺序

[C]链表

[D]任意练习题--选择题405、线性表中各个结点之间的地址

。[A]必须连续

[B]不一定连续

[C]任意6、在非空链表中，在由p指向的结点后面插入一个由q指向的结点过程是：[A]

p

=

q->next;

p->next

=

q;[B]

q->next

=

p->next;

p->next

=

q;[C]

q->next

=

p->next;

p

=

q;[D]

p->next

=

q;

q->next

=

p;BB7、若删除非空链表中由p所指向的结点的直接后继结点的过程是：[A]

r

=

p->next;

p->next

=

r;

free(r);[B]

r

=

p->next;

p->next

=

r->next;

free(r);[C]

r

=

p->next;

p

=

r->next;

free(r);[D]

p->next

=

p->next

->next

->next;8、在非空双向循环链表中，在由q指向结点前插入一个由p指向的结点的过程是：p->right

=

q;

p->left

=

q->left;q->left=p,

(

)

.41[A]

q->left

=

p;[C]

p->right->right[B]

q->left->right

=

p;[D]

p->left->right

=

p;BD练习题－应用题1用静态链表实现的队列如右图所示:front=9,rear=

7.队列有头结点当执行下列操作时,队列有什么变化?1)元素S入队2)队首元素出队A1B3C4D6E10F7G8H0I0J2K5space

0123456rear

78front

91042A3S0C4D6E10F7G8H1I0J2K543space

0rear

12345678front

9102345678A2S0C3D6E10F7G8H1I0J4K5front

910space

0rear

11)元素S入队2)队首元素出队c练习题－应用题2p

=

head;for(

int

i=1;

i<5;

i++){printf(“%c”,p->data);p

=

p->next;p

=

p->next;}p

=

head;for(

int

i=1;

i<5;

i++){printf(“%c”,p->data);p

=

p->next;p

=

p->next;p

=

p->next;}AECBD44headCEDABCBADE应用题345已知长度为n的线性表A=(a1,a2,…,an)。请将线性表转换为A=(an,an-1,…,a1)。1）请写出顺序表求逆的算法2）请写出单链表求逆的算法//顺序表求逆void

SqReverse(L){46}//

SqReversea1a2a3a4a5a6a7a8a9m=n/2;ElemType

tpElem;for(

i=0;

i<

m;

i++)tpElem

=

L.

elem[i];L.

elem[i]

=

L.

elem[n-i+1]

;L.

elem[n-i+1]

=

tpElem;void

LinkListReverse(L){//单链表求逆}//

LinkListReverseElemType

*

p,

*q,

*r;p=

L->next;r=NULL;while(p){q

=

p->next;p->next

=

r;r

=

p;

p

=

q;}L->next

=

r;^a1

a2

…...

an47应用题41）已知线性表中的元素以值递增有序排列，并以单链表为存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素.…aiai+1ax482）已知线性表中的元素以值递增有序排列，并以顺序表为存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素。49aiaxax+13）若线性