数据结构补弱

数据结构补弱账号平台名CONTENTS目录一

时间复杂度计算二

链表的头结点和头指针以及操作三

队列四

哈夫曼编码五

并查集六

哈希表时间复杂度计算一、简单题型1、以下算法的时间复杂度为（

）voidfun(intn){int

i=1;while(i*i<=n)i++;}A.O(

ꢀ)

B.O(n^2)

C.O(n)

D.O(log2n)时间复杂度计算一、简单题型1、以下算法的时间复杂度为（

）voidfun(intn){int

i=1;while(i*i<=n)i++;}A.O(

ꢀ)

B.O(n^2)

C.O(n)

D.O(log2n)i

=

1

，2

,

3

,

4

,

……ꢁꢂ

<=nꢁ

<=

ꢃ2222时间复杂度计算一、简单题型1、以下算法的时间复杂度为（A

）voidfun(intn){int

i=1;while(i*i<=n)i++;}A.O(

ꢀ)

B.O(n^2)

C.O(n)

D.O(log2n)i

=

1

，2

,

3

,

4

,

……ꢁꢂ

<=nꢁ

<=

ꢃ2222时间复杂度计算一、简单题型2、以下算法的时间复杂度为（

）voidfun(intn){int

i=1;while(i<=n)i*=2;}A.O(n)B.O(n^2)

C.O(nlog

n)

D.O(log

n)22时间复杂度计算一、简单题型指数与对数的关系：ꢄꢅ

<=

ꢀ

<=>

ꢆ

<=

ꢇꢈꢉꢄꢃ例如：ꢂꢅ

<=

ꢀ

<=>

ꢆ

<=

ꢇꢈꢉꢂꢃ时间复杂度计算一、简单题型2、以下算法的时间复杂度为（

）voidfun(intn){int

i=1;while(i<=n)i*=2;}A.O(n)B.O(n^2)

C.O(nlog

n)

D.O(log

n)22i

=

2,

4,

8,

16,……ꢂꢊ

<=nk

=1,

2,

3,

4,

……kꢊ

<=

ꢋꢌꢍꢂꢀ时间复杂度计算一、简单题型2、以下算法的时间复杂度为（D

）voidfun(intn){int

i=1;while(i<=n)i*=2;}A.O(n)B.O(n^2)

C.O(nlog

n)

D.O(log

n)22i

=

2,

4,

8,

16,……ꢂꢊ

<=nk

=1,

2,

3,

4,

……kꢊ

<=

ꢋꢌꢍꢂꢀ时间复杂度计算二、中等题型3、以下程序的时间复杂度为（

）int

k=0;for(inti=1;i<n;i++)for(intj=0;j<i;j++)k++;A.O(n)B.O(nlogn)

C.O(n^2)

D.O(n*i)时间复杂度计算二、中等题型前n项求和公式：ꢃꢀ(ꢎ+

ꢀ)ꢂ

ꢁ

=

ꢎ

+

ꢂ

+

ꢏ

+

……

+

ꢀ

=ꢁ=ꢎ时间复杂度计算二、中等题型3、以下程序的时间复杂度为（

）int

k=0;for(inti=1;i<n;i++)for(intj=0;j<i;j++)k++;A.O(n)B.O(nlogn)

C.O(n^2)

D.O(n*i)k++执行的次数:i

=1,

2,

3,

4,

……

n-1ꢐ(ꢐ+ꢎ)ꢂ(ꢀ−ꢎ)∗ꢀꢀꢂ−ꢀꢂk=1,

3,

6,

10,…==ꢂ时间复杂度计算二、中等题型3、以下程序的时间复杂度为（C

）int

k=0;for(inti=1;i<n;i++)for(intj=0;j<i;j++)k++;A.O(n)B.O(nlogn)

C.O(n^2)

D.O(n*i)k++执行的次数:i

=1,

2,

3,

4,

……

n-1ꢐ(ꢐ+ꢎ)ꢂ(ꢀ−ꢎ)∗ꢀꢀꢂ−ꢀꢂk=1,

3,

6,

10,…==ꢂ时间复杂度计算二、中等题型4、下列函数的时间复杂度是（

）int

func(intn){int

i=0,sum=0;while(sum<n)sum+=++i;returni;}A.O(logn)

B.O(ꢀꢎ/ꢂ)

C.O(n)D.O(nlogn)时间复杂度计算二、中等题型4、下列函数的时间复杂度是（

）int

func(intn){int

i=0,sum=0;while(sum<n)sum+=++i;returni;}A.O(logn)

B.O(ꢀꢎ/ꢂ)

C.O(n)D.O(nlogn)++i

执行的次数:i

=1,

2,

3,

……

k(ꢊ+ꢎ)∗ꢊꢂꢊꢐ=ꢎsum=1,

3,

6,

……

ꢐ

=>=

ꢀ结束ꢂꢎ/ꢂꢑ

+

ꢊ

>=

ꢂꢀ

->

k>=

ꢀ=

ꢀ时间复杂度计算二、中等题型4、下列函数的时间复杂度是（

B

）int

func(intn){int

i=0,sum=0;while(sum<n)sum+=++i;returni;}A.O(logn)

B.O(ꢀꢎ/ꢂ)

C.O(n)D.O(nlogn)++i

执行的次数:i

=1,

2,

3,

……

k(ꢊ+ꢎ)∗ꢊꢂꢊꢐ=ꢎsum=1,

3,

6,

……

ꢐ

=>=

ꢀ结束ꢂꢎ/ꢂꢑ

+

ꢊ

>=

ꢂꢀ

->

k>=

ꢀ=

ꢀ时间复杂度计算三、复杂题型5、循环中语句的执行次数是（

）int

k=0;for(inti=1;i<n;i++)for(intj=0;j<2*i;j++)k++;A.nB.n+1C.n(n-1)D.n(n+1)时间复杂度计算三、复杂题型前n项求和公式：ꢃꢀ(ꢀ

+

ꢎ)ꢂꢁ

=

ꢎ

+

ꢂ

+

ꢏ

+

……

+

ꢀ

=ꢁ=ꢎꢀ(ꢂ+ꢂꢀ)ꢃꢁ=ꢎ

ꢂꢁ

=

ꢂ

+

ꢒ

+

ꢓ

+

……

+

ꢂꢀ

==n(n+1)或ꢂꢀ(ꢀ+ꢎ)ꢂꢃꢁ=ꢎ2

ꢁ

=

ꢂ(ꢎ+

ꢂ

+

ꢏ

+

……

+

ꢀ)

=

ꢂ=n(n+1)时间复杂度计算三、复杂题型5、循环中语句的执行次数是（

）int

k=0;for(inti=1;i<n;i++)for(intj=0;j<2*i;j++)k++;A.nB.n+1C.n(n-1)D.n(n+1)k++执行的次数:i

=1,

2,

3,

……

n-1(ꢀ−ꢎ)∗ꢀꢀ−ꢎꢐ=ꢎꢀ−ꢎꢐ=ꢎk=2,

6,

12,

……

ꢂꢐ

=

ꢂ

ꢐ

=

ꢂ=

(ꢀ

−

ꢎ)

∗ꢀꢂ时间复杂度计算三、复杂题型5、循环中语句的执行次数是（C

）int

k=0;for(inti=1;i<n;i++)for(intj=0;j<2*i;j++)k++;A.nB.n+1C.n(n-1)D.n(n+1)k++执行的次数:i

=1,

2,

3,

……

n-1(ꢀ−ꢎ)∗ꢀꢀ−ꢎꢐ=ꢎꢀ−ꢎꢐ=ꢎk=2,

6,

12,

……

ꢂꢐ

=

ꢂ

ꢐ

=

ꢂ=

(ꢀ

−

ꢎ)

∗ꢀꢂCONTENTS目录一

时间复杂度计算二

链表的头结点和头指针以及操作三

队列四

哈夫曼编码五

并查集六

哈希表链表的头结点和头指针以及操作单链表结点指向关系PP->nextaiai+1P->dataP->next->data链表的头结点和头指针以及操作头结点与头指针head头指针head头指针aiaiai+1head头结点首结点链表的头结点和头指针以及操作一、双链表的插入操作sxpLa1a3

^a2(1)

s->next=p->next;(2)p->next->prior=s;(3)s->prior=p;(4)p->next=s;链表的头结点和头指针以及操作二、双链表的删除操作psLa1a3

^a2(1)

p->next=s->next;(2)s->next->prior=p;(3)free(s);链表的头结点和头指针以及操作1、头指针为

h的单链表上，若该链表带头结点，则判定该表为空表的条件是（

），若该链表不带头结点，则判定该表为空表的条件是（

）A.h

==NULLB.h->next==NULLC.h->next==hD.h!=NULL链表的头结点和头指针以及操作1、头指针为

h的单链表上，若该链表带头结点，则判定该表为空表的条件是（

B

），若该链表不带头结点，则判定该表为空表的条件是（

A

）A.h

==NULLB.h->next==NULLC.h->next==hD.h!=NULL链表的头结点和头指针以及操作链表的头结点和头指针以及操作A链表的头结点和头指针以及操作3、若单链表h带有头结点且长度为n，设有尾指针

r，下列（

）操作与链表的表长有关。A.

删除单链表的第一个结点B.删除单链表的最后一个结点C.在单链表第一个结点前插入一个新结点D.在单链表最后一个结点后插入一个新结点链表的头结点和头指针以及操作3、若单链表h带有头结点且长度为n，设有尾指针

r，下列（

B

）操作与链表的表长有关。A.

删除单链表的第一个结点B.删除单链表的最后一个结点C.在单链表第一个结点前插入一个新结点D.在单链表最后一个结点后插入一个新结点链表的头结点和头指针以及操作4、有一个带头结点的单链表

L，头指针为

head，节点结构为

(data,next)，以下代码片段的功能是（

）p=head;while(p->next!=NULL&&p->next->data<x){p=p->next;}q=(Node*)malloc(sizeof(Node));q->data=x;q->next=p->next;p->next=q;A.

在链表中查找值为

x的节点B.在链表中删除值为

x的节点C.在链表中按升序插入值为

x的节点D.在链表中按降序插入值为

x的节点链表的头结点和头指针以及操作4、有一个带头结点的单链表

L，头指针为

head，节点结构为

(data,next)，以下代码片段的功能是（

C

）p=head;while(p->next!=NULL&&p->next->data<x){p=p->next;}q=(Node*)malloc(sizeof(Node));q->data=x;q->next=p->next;p->next=q;A.

在链表中查找值为

x的节点B.在链表中删除值为

x的节点C.在链表中按升序插入值为

x的节点D.在链表中按降序插入值为

x的节点链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;q=NULLphead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;q=NULL,r=NULLphead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;r=NULLpqhead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;r=NULLpqhead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;r=NULLpqhead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;q

rphead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;rpqhead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;rqphead0123

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;qrp213

^headq=p;0p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;rqp213

^headq=p;0p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;rpq3

^21headq=p;0p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;rqp213

^headq=p;0p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;qrp321

^headq=p;0p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;while(p!=NULL){r=q;qrphead0321

^q=p;p=p->next;q->next=r;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

//添加

r=NULL;while(p!=NULL){r=q;

//此句位置后移q=p;p=p->next;q->next=r;

//将

r=q移至此句后}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;q=NULL,r=NULLphead0123

^p=p->next;q->next=r;r=q;}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;r=NULLphead0123

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;r=NULLheadp0123

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;r=NULLheadp0123

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;headrp0123

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;headrp0123

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0123

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0213

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;prhead0213

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;prhead0213

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;prhead0213

^p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0321p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0321p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0321p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0321p=p->next;q->next=r;r=q;q}head->next=q;}链表的头结点和头指针以及操作5、设有一个带头结点的单链表表示的线性表

L=(a1,a2,…,an)，以下算法实现了将线性表

L逆置的功能，代码中是否存在错误（

）void

reverseList(Node*head){Node*p,*q,*r;p=head->next;q=NULL;

r=NULL;while(p!=NULL){q=p;pheadr0321p=p->next;q->next=r;r=q;q}head->next=q;}代码不唯一，此处两个代码都对CONTENTS目录一

时间复杂度计算二

链表的头结点和头指针以及操作三

队列四

哈夫曼编码五

并查集六

哈希表队列队列是一种操作受限的

线性表

，只允端插入，另一端删除出队入队a1,a2,a3,a4,a5,a6队头队尾队列队列的链式存储结构frontreartypedefstructLinkNode{//队列结点int

data;structLinkNode*next;}LinkNode;a3^typedefstruct{LinkNode*front,*rear;}LinkQueue;//链式队列入队：入队尾，单链表的尾插法出队：出队首，单链表删除首结点队列队列的链式存储结构front=0xab004rear=0xab004LinkQueueQ;//建立头结点Q.front

=Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next

=NULL;^0xab004队列队列的链式存储结构front=0xab004

rear=0xce0a0a1^0xab0040xce0a0//入队：尾插单链表LinkNode*s=(LinkNode*)malloc(sizeof(LinkNode));s->data=x;s->next=NULL;Q.rear->next=s;//Q.rear->next=0xce0a0,插入链尾Q.rear=s;//Q.rear=0xce0a0，修改尾指针指向队列队列的链式存储结构front=0xab004rear=0xeff00a1a2a3^0xab0040xce0a00xef0800xeff00入队：入队尾，单链表的尾插法队列队列的链式存储结构front=0xab004rear=0xeff00a2a3^0xab004//出队：删除首结点0xef0800xeff00LinkNode*p=Q.front->next;//指向删除的首结点Q.front->next

=p->next;//改变指针指向关系if(Q.rear==p)Q.rear=Q.front;

//若删除为最后一个结点free(p);//释放队列队列的顺序存储结构43210#defineMaxSize

50

//队列最大长度typedefstruct{int

data[MaxSize];

//存放队列元素int

front,rear;

//队头队尾指针}S;rear=0front=0队空队列队列的顺序存储结构rear=Maxrear=Maxed43210edc43210front=3bfront=0a队满a,b,c出队假溢出队列队列顺序存储存在问题解决rear=Maxed43210ed43210front=3front=3rear=rear%Max循环利用假溢出队列队列顺序存储存在问题解决rear=Maxed43210ed43210front=3front=3rearf假溢出f入队rear++rear=(rear+1)%Max队列队列顺序存储存在问题解决rear=Maxe43210ed43210frontrearfront=3hgfh入队假溢出入队：rear=(rear+1)%Max判空：front

==rear判满：front

==(rear+1)%Max出队：front

=(front+1)%Max长度：(rear-front+Max)%Max队列队列顺序存储存在问题解决链式队列有循环队列吗？rear=Maxe43210ed43210frontrearfront=3hgfh入队假溢出入队：rear=(rear+1)%Max判空：front

==rear判满：front

==(rear+1)%Max出队：front

=(front+1)%Max长度：(rear-front+Max)%Max队列1、最不适合用作链式队列的链表是（

）A.

只带队首指针的非循环双链表B.只带队尾指针的循环单链表C.只带队首指针的循环双链表D.只带队尾指针的循环双链表队列1、最不适合用作链式队列的链表是（

A

）A.

只带队首指针的非循环双链表B.只带队尾指针的循环单链表C.只带队首指针的循环双链表D.只带队尾指针的循环双链表队列2、最适合用作链式队列的链表是（

）A.

带队首指针和队尾指针的循环单链表B.带队首指针和队尾指针的非循环单链表C.只带队首指针的非循环单链表D.只带队首指针的循环单链表队列2、最适合用作链式队列的链表是（

B

）A.

带队首指针和队尾指针的循环单链表B.带队首指针和队尾指针的非循环单链表C.只带队首指针的非循环单链表D.只带队首指针的循环单链表队列3、假设以数组Q[m]存放循环队列中的元素，front为队头指针，rear为队尾指针，且约定front指向队头元素的前一个位置，rear指向队尾元素。若初始时队列为空，且第一个进入队列的元素存放在Q[0]位置，那么在第k（k<m）个元素入队后，队头指针front和队尾指针rear的值分别为（

）A.

m-1,

k-1B.m,k-1C.m-k,

kD.m-k+1,

k队列3、假设以数组Q[m]存放循环队列中的元素，front为队头指针，rear为队尾指针，且约定front指向队头元素的前一个位置，rear指向队尾元素。若初始时队列为空，且第一个进入队列的元素存放在Q[0]位置，那么在第k（k<m）个元素入队后，队头指针front和队尾指针rear的值分别为（

A）A.

m-1,

k-1B.m,k-1C.m-k,

kD.m-k+1,

kCONTENTS目录一

时间复杂度计算二

链表的头结点和头指针以及操作三

队列四

哈夫曼编码五

并查集六

哈希表哈夫曼编码21213：0002：0017：019：101129129051757012323注意：1）0和1表示左或右子树没有明确规定；

2）左、右孩子结点顺序是任意的3）前缀编码：没有一个编码是另一个编码的前缀哈夫曼编码1、下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（

）。A、30，15，5和

30，15，9B、30，15，5和

30，18，8C、30，15，10

和

30，20，12D、30，18，10

和

30，12，7哈夫曼编码1、下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（

D）。A、30，15，5和

30，15，9B、30，15，5和

30，18，8C、30，15，10

和

30，20，12D、30，18，10

和

30，12，7哈夫曼编码2、已知字符集

{x,y,

z,w,

v,

u}，若各字符出现的次数分别为

7,4,9,2,12,

5，则对应字符集中各字符的哈夫曼编码可能是（

）。A.

01,1010,

00,1011,11,

100B.11,

000,01,0011,10,0010C.00,1011,01,0010,

11,

100D.0010,

10,11,

0011,01,000哈夫曼编码2、已知字符集

{x,y,

z,w,

v,

u}，若各字符出现的次数分别为

7,4,9,2,12,

5，则对应字符集中各字符的哈夫曼编码可能是（

A）。A.

01,1010,

00,1011,11,

100B.11,

000,01,0011,10,0010C.00,1011,01,0010,

11,

100D.0010,

10,11,

0011,01,000CONTENTS目录一

时间复杂度计算二

链表的头结点和头指针以及操作三

队列四

哈夫曼编码五

并查集六

哈希表并查集并查集并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题并查集并查集支持的三种基本操作：•

Initial(S)：将集合S中的每个元素初始化为只有一个单元素的子集合•

Union(S,Root1,Root2)：把集合S中的子集合Root2并入子集合Root1中，要求Root1和Root2互不相交(祖先不同)，否则不可合并•

Find(S,x)：查找集合S中单元素x所在的子集合，返回子集合的根结点并查集Initial(S)：将集合S中的每个元素初始化为只有一个单元素的子集合0123456789192-1

-1

-1

-1

-1

-1

-1

-1

-1

-10834//并查集初始化操作voidInitial(intS[]){for(inti=0;i<size;i++)S[i]=-1;

//每个自成单元素集合}57并查集Find(S,x)：查找集合S中单元素x所在的子集合，返回子集合的根结点0123456789-1

-1

0190107

-102

5

78194intFind(intS[],intx){3

6while(S[x]>=0)

//循环寻找x的根x=S[x];return

x;

//S[]的根小于0}并查集•

Union(S,Root1,Root2)：把集合S中的子集合Root2并入子集合Root1中，要求Root1和Root2互不相交(祖先不同)，否则不可合并0123456789-1

-101901071194voidUnion(intS[],intRoot1,

intRoot2){//将根Root2连接到另一根Root1下面36S[Root2]=Root1;}并查集•

Union(S,Root1,Root2)：把集合S中的子集合Root2并入子集合Root1中，要求Root1和Root2互不相交(祖先不同)，否则不可合并012345678916-1

-101901071voidUnion(intS[],intRoot1,

intRoot2){394//将根Root2连接到另一根Root1下面S[Root2]=Root1;}注意：两个元素所在的集合合并为一个集合的前提是先找到这两个元素的根结点，且根结点不同并查集并查集在图论中的应用判断图的连通性：遍历图中所有的边，将边的两个端点所在的集合进行合并。最后检查所有节点，如果所有节点都属于同一个集合，说明图是连通的；否则，图是不连通的，不同的集合数量就是图的连通分量数量。检测图中是否存在环：遍历图的边，对于每条边的两个端点，检查它们是否已经在同一个并查集集合中。如果两个端点已经在同一个集合中，说明这条边会导致环的形成；如果遍历完所有边都没有出现这种情况，则图中无环。求解最小生成树(Kruskal算法)：首先将图中所有边按照权值从小到大排序。然后依次选取边，判断边的两个端点是否在不同的并查集集合中。如果在不同集合，则将这条边加入到最小生成树中，并合并两个端点所在的集合；如果在同一个集合，则舍弃该边，以避免形成环。并查集a0b1c2d3e4fg6h7ijc15b58967a-1-1-1-1-1-1-1-1-1-16d178ef733109g223h112i5j(j,g):1(c,d):7(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b1c2d3e4fg69h7ijc15b58967a-1-1-1-1-1-1-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b1c2d3e4fg69h7ijc15b584967a-1-1-1-1-1-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b1c2d3e4fg69h70ijc15b584967a-1-1-1-1-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b1c2d36e4fg69h70ijc15b584967a-1-1-1-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b1c2d36e4fg69h70ijc15b5849867a-1-1-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b10c2d36e4fg69h70ijc15b5849867a-1-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b10c2d36e4fg69h70ijc15b52849867a-1-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b10c2d36e45fg69h70ijc15b52849867a-1-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a0b10c2d36e45fg69h70ijc15b52849867a-1-16d178ef733109g223h112i5j(j,g):1(c,d):7(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a04b10c2d36e45fg69h70ijc15b52849867a-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23并查集a04b10c2d36e45fg69h70ijc15b52849867a-16d178ef733109g223h112i5j(j,g):1(e,i):2

(a,h):3

(d,g):3

(j,i):5(a,b):6

(c,f):6(e,f):7(c,d):7(e,a):8

(e,h):9

(f,g):10

(h,i):12

(c,b):15

(b,e):17

(j,f):23CONTENTS目录一

时间复杂度计算二

链表的头结点和头指针以及操作三

队列四

哈夫曼编码五

并查集六

哈希表哈希表关于哈希表，重点讲解以下三个问题：1）冲突的解决2）查找成功的平均查找长度3）查找失败的平均查找长度哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。（2）采用再哈希法寻找下一个空位，使用的哈希函数为：RH(key)=(7*key)%10+1，寻找下一个空位的公式为：Hi=(Hi-1+RH(key))%15，其中H0=H(key)。画出相应的哈希表，并计算等概率下查找成功的平均查找长度。哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。H(12)=12%13=12H(57)=57%13=5H(78)=78%13=0H(23)=23%13=10H(20)=20%13=7H(31)=31%13=5

冲突H(45)=45%13=6H(3)=3%13=3哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。H(12)=12%13=12H(57)=57%13=5H(78)=78%13=0H(23)=23%13=10H(20)=20%13=7H(31)=31%13=5

冲突H(45)=45%13=6H(3)=3%13=3开放定址法：Hi=(H(key)+di)MODmi=1,2,3…k(k<=m-1)m：表长

di为增量序列

H(key)哈希函数(1)di=1,2,3,…,m-1称为线性探测再散列(2)di=1^2,-1^2,2^2,-2^2,…,k^2,-k^2(k<=m/2)称为二次探测再散列(3)di=伪随机数序列，称伪随机探测再散列哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。H(12)=12%13=12H(57)=57%13=5H(78)=78%13=0H(23)=23%13=10H(20)=20%13=7H(31)=31%13=5

冲突H(45)=45%13=6H(3)=3%13=3H1=(H(31)+1)MOD15=6仍冲突

H2=(H(31)+2)MOD15=7仍冲突H3=(H(31)+3)MOD15=8解决哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。H(12)=12%13=12H(57)=57%13=5H(78)=78%13=0H(23)=23%13=10H(20)=20%13=7H(31)=31%13=5

冲突H(45)=45%13=6H(3)=3%13=3H1=(H(31)+1)MOD15=6仍冲突

H2=(H(31)+2)MOD15=7仍冲突H3=(H(31)+3)MOD15=8解决H(15)=15%13=2H(36)=36%13=10冲突H1=(H(36)+1)MOD15=11解决哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。H(12)=12%13=12H(57)=57%13=5H(78)=78%13=0H(23)=23%13=10H(20)=20%13=7H(31)=31%13=5

冲突H(45)=45%13=6H(3)=3%13=3H1=(H(31)+1)MOD15=6仍冲突

H2=(H(31)+2)MOD15=7仍冲突H3=(H(31)+3)MOD15=8解决H(15)=15%13=2H(36)=36%13=10冲突H1=(H(36)+1)MOD15=11解决012345678910

11

12

13

147815357

45

20

3123

36

12哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（1）采用线性探测再散列方法寻找下一个空位，画出相应的哈希表，并计算等概率下查找成功的平均查找长度和查找失败的平均查找长度。012345678910

11

12

13

147815357

45

20

3123

36

12查找成功的平均查找长度

=查找成功的总次数/元素个数=(1*8+2*1+4*1)/10=1.4查找失败的平均查找长度

=失败情况的查找次数求和/失败情况=(2+1+3+2+1+5+4+3+2+1+4+3+2)/13=33/13=2.53哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（2）采用再哈希法寻找下一个空位，使用的哈希函数为：RH(key)=(7*key)%10+1，寻找下一个空位的公式为：Hi=(Hi-1+RH(key))%15，其中H0=H(key)。画出相应的哈希表，并计算等概率下查找成功的平均查找长度。哈希表1、设哈希表长度为15，哈希函数为H(key)

=key

%13。用开放地址法解决冲突，对下列关键字序列12，23，45，57，20，03，78，31，15，36构造哈希表。（2）采用再哈希法寻找下一个空位，使用的哈希函数为：RH(key)=(7*key)%10+1，寻找下一个空位的公式为：Hi=(Hi-1+RH(key))%15，其中H0=H(key)。画出相应的哈希表，并计算等概率下查找成功的平均查找长度。H(12)=12%13=12H(57)=57%13=5H(78)=78%13=0H(23)=23%13=10H(20)=20%13=7H(31)=31%13=5

冲突H(45)=45%13=6H(3)=3%13=3哈希表1、设哈希表长