数据结构练习试题附含的答案

数据构造练习题

习题1绪论

1.1单项选择题

1.数据构造是•门研究非数值计算的程序设计问题中，数据元素的①、数据信息在计算机中的②以及一组相关的运算等的

课程。

①A.操作对象B.计算方法C.逻辑构造D.数据映象

②A.存储构造B.关系C.运算D.算法

2.数据构造DS(DataStruct)可以被形式地定义为DS=(D,R),其中D是①的有限集合，R是D上的②有限集合。

①A.算法B.数据元素C.数据操作D.数据对象

②A.操作B.映象C.存储D.关系

3.在数据构造中，从逻辑上可以把数据构造分成。

A.动态构造和静态构造B.紧凑构造和非紧凑构造

C.线性构造和非线性构造D.内部构造和外部构造

4.算法分析的目的是①，算法分析的两个主要方面是②。

①A.找出数据构造的合理性B.研究算法中的输入和输出的关系

C.分析算法的效率以求改良D.分析算法的易懂性和文档性

②A.空间复杂性和时间复杂性B.正确性和简明性

C.可读性和文档性D.数据复杂性和程序复杂性

5.计算机算法指的是①，它必具备输入、输出和②等五个特性。

①A.计算方法B.排序方法

C.解决问题的有限运算序列D.调度方法

②A.可行性、可移植性和可扩大性B.可行性、确定性和有穷性

C.确定性、有穷性和稳定性D.易读性、稳定性和安全性

1.2填空题(将正确的答案填在相应的空中)

1.数据逻辑构造包括、和三种类型，树形构造和图形构造合称为。

2.在线性构造中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点

有且只有个后续结点。

3.在树形构造中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的

直接后续结点可以。

4.在图形构造中，每个结点的前驱结点数和后续结点数可以。

5.线性构造中元素之间存在关系，树形构造中元素之间存在关系，图形构造中元素之间存在关系。

6.算法的五个重要特性是—，—，—，—，—。

7.分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是一。

for(i=0;i<n;i++)

for(j=0;j<n;j++)

A[i][j]=O;

8.分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是一o

for(i=0;i<n;i++)

for(j=0;j<i;j++)

A[i][j]=0;

9.分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是—o

s=0;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

for(k=0;k<n;k++)

s=s+B[i][j][k];

sum=s;

10.分析下面算法(程序段)给出最大语句频度,该算法的时间复杂度是

i=s=O;

while(s<n)

{i++；

s+=i;〃s=s+i

)

11.分析下面算法(程序段)给出最大语句频度，该算法的时间复杂度是

i=l；

while(i<=n)

i=i*2;

1.3算法设计题

1.试写一算法，自大到小依次输出顺序读入的三个数X,Y和Z的值.

2.试写一算法，求出n个数据中的最大值。写出最大语句频度，该算法的时间复杂度。

习题答案

1.11.C,A2.B,D3.C4.C,A5.C,B

1.21.线性构造、树形构造、图形构造，非线性构造

2.没有、1、没有、1

3.前驱、1、后续、任意多个

4.任意多个

5.一对一、一对多、多对多

6.有穷性、确定性、可行性、输入、输出

7.最大语句频度：r?,时间复杂度：.0(n2)

8.最大语句频度:n(n+l)/2,时间复杂度：.0(n2)

9.最大语句频度：r?「时间复杂度：.0(n3)।

10.最大语句频度：n2,时间复杂度：.0(n?)

11.最大语句频度：logzn,时间复杂度：.0(log2n)

习题2线性表

2.1单项选择题

1_.一个向量(即一批地址连续的存储单元)第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址

是o

A.110B.108C.100D.120

2.线性表的顺序存储构造是一种—的存储构造，而链式存储构造是一种—的存储构造。

A.随机存取B.索引存取C.顺序存取D.散列存取

3.线性表的逻辑顺序与存储顺序总是一致的，这种说法—»

A.正确B.不正确

4.线性表假设采用链式存储构造时，要求内存中可用存储单元的地址一。

A.必须是连续的B.局部地址必须是连续的

C.一定是不连续的D.连续或不连续都可以

5.在以下的表达中，正确的选项是」

A.线性表的顺序存储构造优于链表存储构造

B.线性表的顺序存储构造适用于频繁插入/删除数据元素的情况

C.线性表的链表存储构造适用于频繁插入/删除数据元素的情况

D.线性表的链表存储构造优于顺序存储构造

6.每种数据构造都具备三个基本运算：插入、删除和查找，这种说法—。

A.正确B.不正确

7.不带头结点的单链表head为空的判定条件是——»

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

8.带头结点的单链表head为空的判定条件是一。

A.head==NULLB.head->next==NULL

C.head->next==headD.head!=NULL

9.非空的循环单链表head的尾结点(由p所指向)满足—o

A.p->next==NULLB.p==NULL

C.p->next==headD.p==head

10.在双向循环链表的p所指结点之后插入s所指结点的操作是—o

A.p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B.p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C.s->left=p;s->right=p->right;p->right=s;p->right->left=s;

D.s->left=p;s->right=p->right;p->right->left:=s;p->right=s;

11.在一个单链表中，q所指结点是P所指结点的前驱结点，假设在q和P之间插入s结点，则执行—o

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;

B.q->next=s;s->next=p;C.p->next=s;s->next=q;

12.在一个单链表中，假设p所指结点不是最后结点，在p之后插入s所指结点，则执行—。

A.s->next=p;p->next=s;B.s->next=p->next;p->next=s;

C.s->next=p->next;p=s;C.p->next=s;s->next=p;

13.在一个单链表中，假设删除p所指结点的后续结点，则执行――»

A.p->next=p->next->next；B.p=p->next;p->next=p->next->next；

C.p->next=p->next;D.p=p->next->next；

14.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均对比一个结点。

A.nB.n/2C.(n-l)/2D.(n+l)/2

15.在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是。

2

A.0(l)B.0(n)C.0(n)D,0(nlog2n)

16.给定有n个元素的向量，建设一个有序单链表的时间复杂度是。

A.0(1)]B.0(n)C.0(n2)D.0(n*log2n)

2.2填空题（将正确的答案填在相应的空中）

1.单链表可以做一的链接存储表示。

2.在双链表中，每个结点有两个指针域，一个指向,另一个指向___。

3.在一个单链表中p所指结点之前插入一个s（值为e）所指结点时，可执行如下操作：

q=head;

while（q->next!=p）q=q->next;

s=newNode;s->data=e;

q->next=;〃填空

s->next=;〃填空

4.在一个单链表中删除p所指结点的后继结点时，应执行以下操作：

q=p->next;

p->next=;〃填空

delete;〃填空

5.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=和p->next=__的操作。

6.对于一个具有n个结点的单链表，在p所指结点后插入一个新结点的时间复杂度是:在给定值为x的结点后插

入一个新结点的时间复杂度是o

2.3算法设计题:

1.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。

StatusInsert_SqList(SqList&va,intx)

{

if(va.length+l>maxsize)returnERROR;

va.length++;

for(i=va.length-1;va.elem[i]>x&&i>=0;i­)

va.elem[i+l]=va.elem[i];

va.elem[i+l]=x;

returnOK;

2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a，a-逆置为(a“，a-,a)。

voidreverse(inta[],intsize)

(

inti,j,tmp;

for(i=0,j=size-l;i<j;i++,j—)

(

tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

)

3.线性表中的元素以值递增有序排列，并以单链表作存储构造。试写一算法，删除表中所有大于x且小于y的元素(假

设表中存在这样的元素)同时释放被删除结点空间。

voiddel(LinkListL,elemtypea,elemtypeb)

(

p=L;q=p->next;

while(q!=L&&q->data<a)

(

P=q；

q=q->next;

)

while(q!=L&&q->data<b)

(

r=q;

q=q->next;

free(r);

)

if(p!=q)

p->next=q;

)

4.试写一算法，实现单链表的就地逆置(要求在原链表上进展)。

voidconverse(NODEPTRL)

NODEPTRp,q;

p=L->next;q=p->next;

L->next=NULL;

while(p)/*对于当前结点p,用头插法将结点p插入到头结点之后*/

p->next=L->next;

L->next=p;

P二q；

q=q->next;

)

习题答案

2.11.B2.A,C3.B4.D5.C6.A7.A8.B

9.C10.D11.B12.B13.A14.D15.B16.C

2.21.线性结表2.前驱结点、后继结点

3.s,p4.q->next,q

5.p->next,s6.0（1）,0（n）

习题3栈和队列

3.1单项选择题

1.一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是

A.edcbaB.decbaC.dceabD.abcde

2.假设一个栈的入栈序列是1,2,3,n,其输出序列为pl,p2,p3,…，pn,假设pl=n,则pi为一。

A.iB.n=iC.n-i+1D.不确定

3.栈构造通常采用的两种存储构造是——。

A.顺序存储构造和链式存储构造

B.散列方式和索引方式

C.链表存储构造和数组

D.线性存储构造和非线性存储构造

4.判定一个顺序栈ST（最多元素为m0）为空的条件是一。

A.top!=0B.top==0C.top!=m0D.top==mOT

5.判定一个顺序栈ST（最多元素为mO）为栈满的条件是一。

A.top!=0B.top==0C.top!=m0D.top==mOT

6.栈的特点是队列的特点是

A.先进先出B.先进后出

7.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行_»

（不带空的头结点）

A.HS一>next=s;

B.s—>next=HS—>next;11S—>next=s;

C.s->next=HS;HS=s;

D.s—>next=HS;HS=HS—>next;

8.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行—•（不带空的头结点）

A.x=HS;HS=HS一>next;B.x=HS一>data;

C.HS=HS—>next;x=HS—>data;D.x=HS—>data;HS=HS—>next;

9.一个队列的数据入列序列是1,2,3,4,则队列的出队时输出序列是o

A.4,3,2,1B.1,2,3,4

C.1,4,3,2D.3,2,4,1

10.判定一个循环队列QU（最多元素为m0）为空的条件是—o

A.rear-front==m0B.rear-front-l==m0

C.front==rearD.front==rear+1

11.判定一个循环队列QU（最多元素为mO,m0==Maxsize-l）为满队列的条件是__。

A.（（rear-front）+Maxsize）%Maxsize==m0

B.rear-front-l==m0

C.front==rear

D.front==rear+1

12.循环队列用数组A[0,m-1]存放其元素值，其头尾指针分别是front和rear,则当前队列中的元素个数是.

A.（rear-front+m）%m

B.rear-front+1

C.rear-front-1

D.rear-front

13.栈和队列的共同点是一o

A.都是先进后出B.都是先进先出

C.只允许在端点处插入和删除元素D.没有共同点

3.2填空题（将正确的答案填在相应的空中）

1.向量、栈和队列都是—构造，可以在向量的—位置插入和删除元素；对于栈只能在—插入和删除元素；对于

队列只能在插入元素和删除元素。

2.向一个长度为n的向量的第i个元素（IWiWn+l）之前插入一个元素时，需向后移动一个元素。

3.向一个长度为n的向量中删除第i个元素（IWiWn）时，需向前移动一个元素。

4.在具有n个单元的循环队列中，队满时共有个元素。

习题答案

3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C

11.A12.A13.C

3.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i

4.n-1

习题6树和二叉树

6.1单项选择题

1.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法—o

A.正确B.错误

2.假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结点数为个。A.15B.16

C.17D.47

3.按照二叉树的定义，具有3个结点的不同形状的二叉树有种。

A.3B.4C.5D.6

4.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有一种。

A.5B.6C.30D.32

5.深度为5的二叉树至多有一个结点。

A.16B.32C.31D.10

6.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为。

A.2hB.2h-lC.2h+lD.h+1

7.对一个满二叉树，m个树叶，n个结点，深度为h,则__。

A.n=h+mB.h+m=2nC.m=h-lD.n=2h-l

8.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序—。

A.不发生改变B.发生改变C.不能确定D.以上都不对

9.如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉树的后序为。A.uwvts

B.vwutsC.wuvtsD.wutsv

10.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法。A.正确B.错

误

11.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问

顺序是—o

A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca

12.在一非空二叉树的中序遍历序列中，根结点的右边—o

A.只有右子树上的所有结点B.只有右子树上的局部结点

C.只有左子树上的局部结点D.只有左子树上的所有结点

13.如图6.1所示二叉树的中序遍历序列是一。

A.abcdgefB.dfebagcC.dbaefcgD.defbagc

二叉树如图6.2所示，其中序遍历峭列为—。

abdgcefhB.dgbaechf（S-^gdbehfcaD.

为一棵二叉树上的两个结点，在中序遍历时，a在b前的

b的右方B.a在b的左方

D.a是b的子孙

16.某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是__«A.acbedB.decabC.

deabcD.cedba

17.实现任意二叉树的后序遍历的非递归算法而不使用栈构造，最正确方案是二叉树采用—存储构造。

A.二叉链表B.广义表存储构造C.三叉链表D.顺序存储构造

18.如图6.3所示的4棵二叉树，—不是完全二叉树。

left=NULLD.以上都不对

21.二叉树按某(B)(C)种顺序线索化后，任一

结点均有指向其前驱图6.3和后续的线索，这种说

法___。A.正确B.错误

22.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法

A.正确B.错误

23.具有五层结点的二叉平衡树至少有一个结点。

A.10B.12C.15D.17

24.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论—是正确的。

A.树的先根遍历序列与其对应的二叉树的先序遍历序列一样

B.树的后根遍历序列与其对应的二叉树的后序遍历序列一样

C.树的先根遍历序列与其对应的二叉树的中序遍历序列一样

D.以上都不对

25.树最适合用来表示___。

A.有序数据元素B.无序数据元素

C.元素之间具有分支层次关系的数据D.元素之间无联系的数据

6.2填空题(将正确的答案填在相应的空中)

1.有一棵树如图6.5所示，答复下面的问题:

⑴这棵树的根结点是「；

⑵这棵树的叶子结点是—;

⑶结点k3的度是____；

(4)这棵树的度是___；

⑸这棵树的深度是——；

(6)结点k3的子女是——；

(7)结点k3的父结点是—

2.指出树和二叉树的三个主要差异、

3.从概念上讲，树与二叉树是两种不同的数据构造，将树转化为二叉树的基本目

的是一。

4.一棵二叉树的结点数据采用顺序存储构造，存储于数组t中，如图6.6所示，则该二叉树的链接表示形式为。

5.深度为k的完全二叉树至少有一个结点。至多有一个结点，假设按自上而下，从左到右次序给结点编号(从1

开场)，则编号最小的叶子结点的编号是一。

123456789101112131415161718192021

图6.6一棵二叉树的顺序存储数组t

6.在一棵二叉树中，度为零的结点的个数为n。，度为2的结点的个数为nz,则有n产—。

7.一棵二叉树的第i(i》l)层最多有一个结点；一棵有n(n>0)个结点的满二叉树共有.个叶子和个非终

端结点。

8.结点最少的树为—_,结点最少的二叉树为_—。

9.现有按中序遍历二叉树的结果为abc,问有种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是一。

10.由如图6.7所示的二叉树，答复以下问题：

⑴其中序遍历序列为—；…

de

h

⑵其前序遍历序列为

⑶其后序遍历序列为

6.3简答题

1.根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。

2.假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJKo

请画出该树。

3.由如图6.7所示的二叉树，答复以下问题：

(1)画出该二叉树的中序线索二叉树；

(2)画出该二叉树的后序线索二叉树；

(3)画出该二叉树对应的森林。

4.一棵树如图6.8所示，转化为一棵二叉树，表示为.

5.以数据集｛4,5,6,7,10,12,18｝为结点权值，画出构造Huffman树的每一步图示,计算

其带权路径长度为。

6.一棵含有N个结点的k义树,可能到达的最大深度和最小深度各为多少？

7.证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n,图6.8一棵树之间满足以下关系:

n(,=(kT)n]+l

6.4算法设计题

1.编写按层次顺序(同一层自左至右)遍历二叉树的算法。

2.试编写算法，对一棵二叉树，统计叶子的个数。

3.试编写算法，对一棵二叉树根结点不变，将左、右子树进展交换，树中每个结点的左、右子树进展交换。

7.假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,

0.32,0.03,0.21,0.10o试为这八个字母设计哈夫曼编码。

使用0-7的二进制表示形式是另一种编码方案。对于上述实例，对比两种方案的优缺点。

8.试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵二叉树的先序序列为EBADCFHGIKJ和中

序序列为ABCDEFGI1IJK。请画出该树。

习题答案

6.11.B2.B3.C4.C5.C6.A7.D8.A9.C10.A

11.D2.A13.B14.B15.B16.D17.C18.C

19.B20.B21.B22.B23.B24.A25.C

6.2

1.(1)kl⑵k2,k5,k7,k4⑶2(4)3(5)4(6)k5,k6⑺kl

2.树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0;

树中结点的最大度数没有限制，而二叉树结点的最大度数为2；

树的结点无左、右之分，而二叉树的结点有左、右之分；

目的‘并利用二叉树的已有算法解

3.树可采用孩子-兄弟链表(二叉链表)做存储构造，

决树的有关问题。

4.如图6.9所示

5.2J2k-l、2k2+l

6.n2+l

[logn+l]-lr)[logn+1]1

7.2'T22/2-1

8.只有一个结点的树;空的二叉树图6.9

9.5；如图610所示

10.dgbaechif、abdgcefhi、gdbeihfca、

6.31.5种,图6.11

2.二叉树如图6.12所示。

中序线索二叉树如图

J

图6.11树形5种

图6.12

6.13（左）所示；后序线索二叉树如图6.13（右）所示;

该二叉树转换后的的森林如图6.14所示。

树转化为一下，图6.15：（a

5.〉㈣出构读&affif也1种示、，计算其超区路径长度为

叉树,H能到达的最）大深度h=N-k-Klh,

应的森林

7.1单项选择麋］6.13孩子兄弟表

1.在一个图中，所有顶点的度数之和等于所有边数的一倍。

A.1/2B.1C.2D.4

2.任何一个无向连通图的最小生成树。

A.只有一棵B.有一棵或多棵C.一定有多棵D,可能不

存在

3.在一个有向图中，所有顶点的入度图6.16Huffman树之和等于所有顶点的出度之和的一倍。

A.1/2B.1C.2D.4

4.一个有n个顶点的无向图最多有一条边。

A.nB.n(n-l)C.n(n-l)/2D.2n

5.具有4个顶点的无向完全图有条边。

A.6B.12C.16D.20

6.具有6个顶点的无向图至少应有一条边才能确保是一个连通图。

A.5B.6C.7D.8

7.在一个具有n个顶点的无向图中，要连通全部顶点至少需要一条边。

A.nB.n+1C.n-1D.n/2

8.对于一个具有n个顶点的无向图，假设采用邻接矩阵表示，则该矩阵的大小是

A.nB.（n-1）2C.nTD.n

9.对于一个具有n个顶点和3条边的无向图，假设采用邻接表表示，则表头向量的大小为一①_；所有邻接表中的接

点总数是一②

①A.nB.n+1C.n-1D.n+e

②A.e/2B.eC.2eD.n+e

10.一个图如图7.1所示，假设从顶点a出发按深度搜索法进展遍历，则可能得到

的一种顶点序列为一①一;按宽度搜索法进展遍历,则可能得到的一种顶点序列

为—②

①A,a,b,e,c,d,fB.e,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b

②A.a,b,c,B.a,b,c,e,f,dC.a,e,b,c,f,dD.a,c,f,d,e,b

11.一有周J邻接造如图7.2所示。

c

⑴根据有向£1输加算重接资想A

E出发,所得到的顶点序列是

A.vl,v22A'R,v4B.vl,v2,v3,v4,v5

C.vl,v31,v2D.vl,v4,v3,v5,v2

⑵根据有向R377^04修，从|5|八飞发,所得到的顶点序列是

A.vl,v24,v5B.vl,v3,v2,v4,v5

C.vl,v24A5v4D.vl,v4,v3,v5,v2

12.采用邻接----1者的图的深度优先遍历算法类似于二叉树的

A.先序贡5百2…』历一»4、.八店序遍历D.按层遍历

13.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的—o

A.先序遍历B.中序遍历C.后序遍历D.按层遍历

14.判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用

A.求关键路径的方法B.求最短路径的Dijkstra方法

C.宽度优先遍历算法D.深度优先遍历算法

15.关键路径是事件结点网络中。

A.从源点到汇点的最长路径B.从源点到汇点的最短路径

C.最长的回路D.最短的回路

16.下面不正确的说法是。

(1)在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小;

(2)AOE网工程工期为关键活动上的权之和；

(3)在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。

A.(1)B.(2)C.(3)D.⑴、(2)

17.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是。

A.逆拓朴有序的B.拓朴有序的C.无序的

18.在图7.3所示的拓朴排列的结果序列为。

A.125634C.123456D.521634

19.一个有n个顶点的不国持庙囱田所包含的连通分量个数为。

A.0B.1图7.3有向图D.n+1

20.对于一个有向图,假我一个J贝点的人度为kl,、出度为k2,则对应邻接表中该顶点单链表中的结点数为。

A.klB.k2C.kl-k2D.kl+k2

21.对于一个有向图,假设一个顶点的入度为kl,、出度为k2,则对应逆邻接表中该顶点单链表中的结点数为。

A.klB.k2C.kl-k2D.kl+k2

7.2填空题(将正确的答案填在相应饿空中)

1.n个顶点的连通图至少一条边。

2.在无权图G的邻接矩阵A中，假设(vi,vj)或＜vi,vj＞属于图G的边集合，则对应元素等于—，否则等于

3.在无向图G的邻接矩阵A中，假设等于1,则］等于一。

4.图G的邻接表如图7.4所示，其从顶点vl出发的深度有限搜索序列为—，其从顶点vl出发的宽度优先搜索序列

为…。

―图£v2-v5v4

5.一彳一向邻安MUX*示■i忘制入度的方法是

6.一彳v2一豹&v34叫v5、第i个结点出发的边的方法是—。

7.如界—页点卜B%它有棵生成树。

8.VJ一mV6上28条边，则该图至少有个顶点。

9.遍〃v4A里实加工君'BFS遍历图的时间复杂度为，DFS遍历图的时间复杂度为，两者不同之处在于，反映在数

据构造上的

10.v5-v4一除v6v3J。

11.一I结,左刖驱制继史东EJ鬲正是一

A

12.假v6IG的顶点度数最小值大于等于时，G至少有一条回路。

13.根据图的存储构造进展某种次序的遍历，得到的顶点序列是的。

7.3综合题

1.如图7.5所示的有向图，请给出该图的:

(1)每个顶点的入/出度；1r(5

(2)邻接距阵；

(3)邻接表；

(4)逆邻接表;

(5)强连通分量。

24

3

习题答案

7.11.C2.B3.B4.C5.A6.A7.C

8.D9.AC10.DB11.CB12.A13.D14.D15.A

16.A17.A18.B19.B20.B21.A

7.2l.n-12.l;03.1

4.vl,v2,v3,v6,v5,v4；vl,v2,v5,v4,v3,v6

5.求矩阵第i列非零元素之和

6.将矩阵第i行全部置为零

7.n

8.9

9.对每个顶点查找其邻接点的过程；0S)(e为图中的边数)；0(e)；

遍历图的顺序不同：DFS采用栈存储访问过的结点，BFS采用队列存储访问过

的结点。

10.邻接矩阵邻接表

11.一个结点可能有假设干个前驱，也可能有假设干个后继

12.2

13.唯一

7.3

2.

3.

e

512634

512364

4.

W=6

)W=5

5.⑴该AOE图为:h

3

(2)完成整个方窠网r1«大。

(3万侬路径为：I'，V2,V

习题8

W=9

8.1单项2.,4

4W=7

W=3

1.顺序查找法适，J造为一的线性

A.散列存储B.顺序存储或链接存储

C.压缩存储D.索引存储

2.对线性表进展二分查找时;要求线性表必须—o

A.以顺序方式存储B.以链接方式存储

C.以顺序方式存储，且结点按关键字有序排序

D.以链接方式存储，且结点按关键字有序排序

3.采