华东交大数据结构自测卷及答案

华东交大数据结构自测卷及答案

一、填空题

1.算法的计算量的大小称之计算的（B）。

A.效率B.复杂性C.现实性D.难度

2.算法的时间复杂度取决于（C）

A.问题的规模B.待处理数据的初态C.A与B

3.计算机算法指的是（C）,它务必具备（B）这三个特性。

（1）A.计算方法B.排序方法C.解决问题的步骤序列D.调度方法

（2）A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性

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

4.从逻辑上能够把数据结构分为（C）两大类。

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

C.线性结构、非线性结构D.初等结构、构造型结构

5.下列与数据的存储结构无关的术语是（D）。

A.循环队列B.链表C.哈希表1）.栈

6.下列数据结构中，哪一个不是线性结构（B）?

A.广义表B.二叉树C.稀疏矩阵D.串

7.下列那一个术语与数据的存储结构无关？（A）

A.栈B.哈希表C.线索树I）.双向链表

8.在下面的程序段中，对x的赋值语句的频度为（C）

FORi:=lTOnDO

FORj:=lTOnDO

x:=x+l;

2

A.0(2n)B.0(n)C.0(n)D.0(log2")

9.程序段FORi:=nTDOWNTO1DO

FORj:=lTOiDO

IFA[j]>A[j+l]

THENA[j]与A[j+1]对换；

其中n为正整数，则最后一行的语句频度在最坏情况下是（D）

A.0（n）B.O（nlogn）C.0（n3）D.0（n2）

10.下列哪个数据结构不是多型数据类型（I））

A.栈B.广义表C.有向图D.字符串

11.下列数据结构中，（A）是非线性数据结构

A.树B.字符串C.队D.栈

12.下列数据中，（C）是非线性数据结构。

A.栈B.队列C.完全二叉树D.堆

13.连续存储设计时，存储单元的地址（A）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

14.下列属于逻辑结构的是（C）。

A.顺序表B.哈希表C.有序表D.单链表

二、推断题

1.数据元素是数据的最小单位。（F）

2.记录是数据处理的最小单位。（T）

3.数据的逻辑结构是指数据的各数据项之间的逻辑关系：（F）

4.算法的优劣与算法描述语言无关，但与所用计算机有关。（F）

5.健壮的算法不可能因非法的输入数据而出现莫名其妙的状态。（T）

6.算法能够用不一致的语言描述，假如用C语言或者PASCAL语言等高级语言来描述，则

算法实际上就是程序了。（T）

7.程序一定是算法。（T）

8.数据的物理结构是指数据在计算机内的实际存储形式。（T）

9.数据结构的抽象操作的定义与具体实现有关。（F）

10.在顺序存储结构中，有的时候也存储数据结构中元素之间的关系。（F）

11.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（F）

12.数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。（T）

13.数据的逻辑结构说明数据元素之间的顺序关系，它依靠于计算机的储存结构.（F）

三、填空

1.数据的物理结构包含数据元素的表示与数据关系的表示。

2.关于给定的n个元素,能够构造出的逻辑结构有集合，线性，树，图（网）

_四种。

3.数据的逻辑结构是指数据元素之间的逻辑关系。

4.一个数据结构在计算机中表示称之存储结构。

5.抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示与

实现无关,即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。

6.数据结构中评价算法的两个重要指标是时间复杂度与空间复杂度

7.数据结构是研讨数据的逻辑结构与物理结构，与它们之间的相互关系，并对与这种

结构定义相应的操作，设计出相应的算法。

8.一个算法具有5个特性：有穷性、确定性、可行性，有零个或者多个输入、有一个

或者多个输出。

9.已知如下程序段

for（i=n;i>=1;i-）{语句1}

（

x=x+1;{语句2}

for（j=n；j>i；j—）{语句3}

y=y+1;{语句4}

）;

语句1执行的频度为n+l；语句2执行的频度为上；语句3执行的频度为n（n+l）/2；

语句4执行的频度为（n-l）n/2。

10.在下面的程序段中，对x的赋值语句的频度为6+3/+211）/6（表示为n的函数）

for（i=1;i<=n；i++）

for（j=1;j<=i;j++）

for（k=1;k<=j;k++）

x:=x+delta;

11.下面程序段中带下划线的语句的执行次数的数量级是：1。刎

i=1；whiIe（i<n）i=i*2；

12.下面程序段中带下划线的语句的执行次数的数量级是（nlog2n）。

1=1；

whiIe（i<n）{for（j=1;j<=n;j++）x=x+1;i=i*2}

13.下面程序段中带有下划线的语句的执行次数的数量级是(logm)

i=n*nwhile(i!=1)i=i/2；

14.计算机执行下面的语句时，语句s的执行次数为_(n+3)(n-2)/2.。

for(i=l;i<n-1；i++)

for(j=n；j>=i;j­)

s；

15.下面程序段的时间复杂度为Ji"____o(n>l)

sum=1；

for(i=0;sum<n;i++)suirr+-=i;

四、应用题

1、有如下几种用二元组表示的数据结构，画出它们分别对应的逻辑图表示形式,

并指出它们分别属于何种结构。(注意：◊表示有方向，()表示无方向)

(1)、A=(K,R),其中：K={a,b,c,d,e,,f,g,h}R={r}

r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g.h>}

(2)、B=(K,R),其中：K={a,b,c,d,e,f,g,h}R={r}

r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e.f>}

(3)、

r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}

线性表、栈与队列测试题

姓名班级学号

选择题(共25分)

(B)1、下面关于线性表的叙述中，错误的是哪一个？

A.线性表使用顺序存储，务必占用一片连续的存储单元。

B.线性表使用顺序存储，便于进行插入与删除操作。

C.线性表使用链接存储，不必占用一片连续的存储单元。

D.线性表使用链接存储，便于插入与删除操作。

(A)2、若某线性表最常用的操作是存取任一指定序号的元素与在最后

进行插入与删除运算，则利用()存储方式最节约时间。

A.顺序表B.双链表

C.带头结点的双循环链表D.单循环链表

(C)3、若长度为n的线性表使用顺序存储结构，在其第i个位置插入一

个新元素的算法的时间复杂度为()(l<=i<=n+l)。

A.0(0)B.0(1)C.0(n)D.0(n2)

(B)4、在单链表指针为p的结点之后插入指针为s的结点，正确的操

作是：

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

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

(B)5、关于一个头指针为head的带头结点的单链表，判定该表为空表

的条件是()

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

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

(B)6.栈中元素的进出原则是

A.先进先出B.后进先出C栈空则进D栈满

则出

(C)7.若已知一个栈的入栈序列是1,2,3,…，n,其输出序列为

pl,p2,p3,...»pn,若pl=n,贝Upi为

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

(B)8.判定一个栈ST(最多元素为mO)为空的条件是

A.ST->top<>0B.ST->top=0C.ST->top<>mO

D.ST->top=mO

(A)9.判定一个队列QU(最多元素为mO)为满队列的条件是

A.QU->rear—QU->front==mOB.QU->rear—QU->front

-1==mO

C.QU->front==QU->rearD.QU->front==QU->rear+l

(D)10.数组Q[n]用来表示一个循环队列，f为当前队列头元素的

前一位置，r为队尾元素的位置，假定队列中元素的个数小于n,

计算队列中元素的公式为

(A)r—f;(B)(n+f—r)%n;(C)n+r—f;(D)(n

+r—f)%n

11.设有4个数据元素al、a2、a3与a4,对他们分别进行栈操作或者队操作。

在进栈或者进队操作时，按al、a2、a3、a4次序每次进入一个元素。假设

栈或者队的初始状态都是空。

现要进行的栈操作是进栈两次，出栈一次，再进栈两次，出栈一次；这时，

第一次出栈得到的元素是②,第二次出栈得到的元素是

④—;类似地，考虑对这四个数据元素进行的队操作是进队两次，出队一

次，再进队两次，出队一次；这时，第一次出队得到的元素是—①—，第

二次出队得到的元素是—②—。经操作后，最后在栈中或者队中的元素还

有一②一个。

供选择的答案:A〜D：①al②a2③a3④a4E：①1②2

③3@0

答：A、B、C、D、E分别为、、、、

12.栈是一种线性表，它的特点是A。设用一维数组来表示一个

栈，A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。往栈

中推入(PUSH)一个新元素时，变量T的值5___；从栈中弹出(POP)

一个元素时，变量T的值_____o设栈空时，有输入序列a,b,c,通过

PUSH,POP,PUSH,PUSH,POP操作后，从栈中弹出的元素的序列是

D，变量T的值是E。

供选择的答案:

A：①先进先出②后进先出③进优于出④出优于进⑤

随机进出

B,C：①加1②减1③不变④清0⑤加2

⑥减2

D：①a,b②b,c③c,a④b,a⑤c,b

⑥a,c

E：①n+1②n+2③n@n-l⑤n-2

答：A、B、C、D、E分别为②_、_②—、①、(6)_®_

13.在做进栈运算时，应先判别栈是否_A_；在做退栈运算时，应先判别栈

是否3o当栈中元素为n个，做进栈运算时发生上溢，则说明该栈的

最大容量为C。

为了增加内存空间的利用率与减少溢出的可能性，由两个栈共享一片连续的

内存空间时，应将两栈的3分别设在这片内存空间的两端，这样，只有

当E时,才产生上溢。

供选择的答案:

A,B：①空②满③上溢④下溢

C：①n-1②n③n+1@n/2

D：①长度②深度③栈顶④栈底

E：①两个栈的栈顶同时到达栈空间的中心点

②其中一个栈的栈顶到达栈空间的中心点

③两个栈的栈顶在栈空间的某一位置相遇

④两个栈均不空，且一个栈的栈顶到达另一个栈的栈底

答：A、B、C、D、E分别为―②—、―①—、_②、_®、_®

二、推断题(共10分)

(F)1.线性表的每个结点只能是一个简单类型，而链表的每个结点能够是一

个复杂类型。

(F)2.在表结构中最常用的是线性表，栈与队列不太常用。

(T)3.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一

种后进先出型结构。

(T)4.关于不一致的使用者，一个表结构既能够是栈，也能够是队列，也能

够是线性表。

(F)5.栈与链表是两种不一致的数据结构。

(F)6.栈与队列是一种非线性数据结构。

(T)7.栈与队列的存储方式既但是顺序方式，也但是链接方式。

(T)8.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会,

应把两个栈的栈底分别设在这片内存空间的两端。

(F)9.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进

后出型结构。

(F)10.一个栈的输入序列是12345,则栈的输出序列不可能是12345o

三、填空题(共20分)

1.线性表、栈与队列都是线性结构,能够在线性表的任意位

置插入与删除元素；关于栈只能在栈顶插入与删除元素:关于队列

只能在队尾插入与队头删除元素。

2.栈是一种特殊的线性表，同意插入与删除运算的一端称之栈顶。

不同意插入与删除运算的一端称之栈底。

3.队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删

除运算的线性表。

4.在一个循环队列中，队首指针指向队首元素的当前位置。

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

6.向栈中压入元素的操作是先插入数据，后移动指

针o

7.从循环队列中删除一个元素时，其操作是先读取元素，后移动指

针O

8.带表头结点的空循环双向链表的长度等于0。

9.表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是

_23123*2-4/345*7/++1089/+

10.已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元

素结点。按要求从下列语句中选择合适的语句序列。

a.在P结点后插入S结点的语句序列是：(4)(1)o

b.在P结点前插入S结点的语句序列是：711841-

c.在表首插入S结点的语句序列是：512o

d.在表尾插入S结点的语句序列是：916。

供选择的语句有：

(1)P->next=S;(2)P->next=P->next->next;(3)P->next=S->next;

(4)S->next=P->next;(5)S->next=L;(6)S->next=NULL;(7)Q=P;

(8)while(P->next!=Q)P=P->next;(9)while(P->next!=NULL)P=P->next;

(10)P=Q;(11)P=L;(12)L=S;(13)L=P;

四、简答题(共15分)

1、说明线性表、栈与队的异同点。

2、顺序队的“假溢出”是如何产生的？如何明白循环队列是空还是满？

3、设循环队列的容量为40(序号从0到39),现通过一系列的入队与出队

运算后，有

①front=ll,rear=19;②front=19,rear=l1；问在这两种情况下，循环队列中

各有元素多少个？

五、算法设计(共30分)

1、写一算法，从顺序表中删除自第i个元素开始的k个元素。

StatusDelete_k(SqlistL,inti,intk)

(

if(i<O||i>L.length||i+k>L.length)returnerror;

for(intj=i+k;j<L.length;j++)

(

L.elem[j-k]=L.elem[j];

L.length-=k;

returnOK;

2、试写一个算法，判别读入的一个以，@，为结束符的字符序列是否是“回文”。

(正读与反读都相同的字符序列为“回文”，比如，匕bba，与匕bcba，是回文，

匕bcde'与'ababab'则不是回文。)

StatusHuiWen(chars[])

(

inti=0;

SqStackS;

InitStack(S);

while(s[i]!=,@,)

{

Push(S,s[i]);

cout«"push,,«s[i];

i++；

)

i=0;

while(s[i]!=,@,)

{

chare;

Pop(S,e);

cout«e«n*n«s[i];

if(e!=s[i])break;

i++；

)

if(s[i]=-@-)retum1;//返回结果1表示是回文，0表示不是回文

elsereturn0;

)

3、假设有一个循环链表的长度大于1,且表中既无头结点也无头指针。已知s

为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前

趋结点。

StatusDelete(LinkLists)

(

p=s；

while(p->next->next!=s)〃查找s的前一个结点的前一个结点；

p=p->next;

q=p->next;

p->next=s;

deleteq;

returnOK;

)

第6章树与图自测卷姓名__班级.一学建

题号—■二三四五总分

题分1017174016100

得分

一、下面是有关二叉树的叙述，请推断正误(每小题1分，共10分)

()1.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n-1个非空

指针域。

()2.二叉树中每个结点的两棵子树的高度差等于lo

()3.二叉树中每个结点的两棵子树是有序的。

()4.二叉树中每个结点有两棵非空子树或者有两棵空子树。

()5.二叉树中所有结点个数是2i-l,其中k是树的深度。

()6.关于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2'—1

个结点。

()7.具有12个结点的完全二叉树有5个度为2的结点。

()8.不一致的求最小生成树的方法最后得到的生成树是相同的.

()9.有n个顶点的无向图，使用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素

之与的一半。

()10.无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

二、填空(每空1分，共17分)

1.由3个结点所构成的二叉树有种形态。

2.一棵深度为6的满二叉树有个分支结点与个叶子。

3.一棵具有257个结点的完全二叉树，它的深度为o

4.设一棵完全二叉树有700个结点，则共有个叶子结点。

5.用5个权值｛3,2,4,5,1｝构造的哈夫曼(Huffman)树的带权路径长度是。

6.推断一个无向图是一棵树的条件是.

7.在有n个顶点的有向图中，若要使任意两点间能够互相到达，则至少需要条弧。

8.G是一个非连通无向图，共有28条边，则该图至少有—_个顶点

9.N个顶点的连通图用邻接矩阵表示时,该矩阵至少有个非零元素。

10.在有n个顶点的有向图中，每个顶点的度最大可达____。

11.设有一稀疏图G,则G使用存储较省空间。

12.设有一稠密图G,则G使用存储较省空间。

13.n个顶点e条边的图使用邻接矩阵存储，深度优先遍历算法的时间复杂度为:

若使用邻接表存储时，该算法的时间复杂度为。

14.已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列

是。则从顶点0出发按广度优先遍历的结点序列是。

0111101

1001001

1000100

1100110

1011010

0001101

1100010

三、选择题(每小题1分，共17分)

()1.不含任何结点的空树

(A)是一棵树；(B)是一棵二叉树；

(C)是一棵树也是一棵二叉树;(D)既不是树也不是二叉树

()2.二叉树是非线性数据结构，因此

(A)它不能用顺序存储结构存储;(B)它不能用链式存储结构存

储;

(C)顺序存储结构与链式存储结构都能存储；(D)顺序存储结构与链式存储

结构都不能使用

()3.具有n(n>0)个结点的完全二叉树的深度为。

(A)Flog2(n)l(B)Lloga(n)J(C)Llog2(n)J+l(D)Flogs(n)+11

()4.把一棵树转换为二叉树后，这棵二叉树的形态是。

(A)唯一的(B)有多种

(C)有多种，但根结点都没有左孩子(D)有多利*但根结点都没有右

孩子

()5.在一个图中，所有顶点的度数之与等于图的边数的倍。

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

()7.在一个有向图中，所有顶点的入度之与等于所有顶点的出度之与的____倍。

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

()8.用邻接表表示图进行广度优先遍历时，通常是使用_______—来实现算法的。

A.栈B.队列C.树D.图

()9.深度优先遍历类似于二叉树的

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

()10.广度优先遍历类似于二叉树的

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

11.树是结点的有限集合，它」根结点，记为T。其余的结点分成为m(m20)个」

的集合Tl,T2,…，Tm,每个集合又都是树，如今结点T称之T,的父结点，T；称之T的子

结点(iWiWm)。一个结点的子结点个数为该结点的」。

供选择的答案

A：①有0个或者1个②有。个或者多个③有且只有1个④有1个或者

1个以上

B:①互不相交②同意相交③同意叶结点相交④同意树枝结点

相交

C：①权②维数③次数④序

答案：A=B=C=

12.二叉树A。在完全的二叉树中，若一个结点没有B,则它必定是叶结点。每棵

树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N

在原树里对应结点的」，而N的右子女是它在原树里对应结点的」。

供选择的答案

A：①是特殊的树②不是树的特殊形式③是两棵树的总称④有是只有二个根结点

的树形结构

B:①左子结点②右子结点③左子结点或者者没有右子结点④兄弟

C~D：①最左子结点②最右子结点③最邻近的右兄弟④最邻近

的左兄弟

⑤最左的兄弟⑥最右的兄弟

答案：A=B=C=D=

四、阅读分析题(每题5分，共40分)

1.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D,A,C,E,B,H,F,G,I；中序遍历序列：D,C,B,E,II,A,G,I,

F,

试画该出二叉树

殳先序、列。

3,

4,

5该图的八

每个顶点的入心曲.

31顶点12346

邻接矩阵；图2

图1(2)1度321图32

q⑶邻接表；

出度022313

(4)逆邻接表。

6.请对下图的无向带权图：

（1）写出它的邻接矩阵，并按普里姆算

法求其最小生成树；

(2)写出它的邻接表,并按克鲁斯卡尔算法求其最小生成树。

7.已知二维数组表示的图的邻接矩阵如下图所示。试分别

画出自顶点1出发进行遍历所得的深度优先生成树与广度优

先生成树。10000001010

8.给定下列网G:（10分）:0010001000

0001000100

40000100010

50000010001

61100000000

70010000001

81001000010

90000101001

101000010000

1试着找出网G的最小生成树，画出其逻辑结构图;

2用两种不一致的表示法画出网G的存储结构图;

3用C语言（或者其他算法语言）定义其中一种表示法（存储结构）的数据类型。

五、算法设计题（前「5题中任选2题，第6~7题中任选1题，共16分）

1.编写递归算法，计算二叉树中叶子结点的数目。

2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。

3.编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。

4.编写按层次顺序（同一层自左至右）遍历二叉树的算法。

5.编写算法判别给定二叉树是否为完全二叉树。

6.编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息与各条弧的信息建立有向

图的邻接表。

解：StatusBuildAdjList（ALGraph&G）〃输入有向图的顶点数，边数，顶点信息与边的信

息，以建立邻接表

returnOK;

}//BuildAdjList

7.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w),即删除一条边的操作。

(假如要删除所有从第i个顶点出发的边呢？提示：将邻接矩阵的第i行全部置0)

解：〃设本题中的图G为有向无权图

StatusDeleteArc(MGraph&G,charv,charw)〃在邻接矩阵表示的图G上删除边

(v,w)

returnOK;}//Delete_Arc

答案：

12345678910

VXXXXXVXVX

—*、

156n个顶点n-1条边的连通图11邻接表

231,327n12邻接矩阵

3989130(n2)

0(n+e)

435092(n-1)140134256

0123465

53312*(n-1)15

0

四、

1、

答：

前序遍历序列：D,A,C,E,B,H,F,G,I；中序遍历序列：D,C,B,E,H,A,

G,I,F,

试画出二叉树B,并简述由任意二叉树B的前序遍历序列与中序遍历序列求二叉树B的思

想方法。

解：方法是：由前序先确定root,由中序可确定root的左、右子树。然后由其左子树的元

素集合与右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将

他们分别作为新的root,不断递归，则所有元素都将被唯一确定，问题得解。

2、答：DLR：ABDFJGKCEH1LM

LDR:BFJDGKACHELIM

LRD：JFKGDBHLMIECA

3、

答：注意全部兄弟之间都要连线（包含度为2的兄弟），并注意原有连线结点一律归入左子

树，新添连线结点一律归入右子树。

4、

答：注意根右边的子树确信是森林，而孩子结点的右子树均为兄弟。

001011

100000

110010

⑶

1

2

3

1

125人

(4)

126人

23

34

42

543

633

6、

解：设起点为a。能够直接由原始图画出最小生成树,

04300000000co而且最小生成树只有一种（类）！

40559000000邻接矩阵为：

3505oooooo5

005507654

009oo703oooo

00oooo6302oo

00oooo5oo206

00oo54oooo60

e

PRIM算沧最小生成树f£b

\2

VbcdefghUv-u

VexaLaaaa{a}{b,c,d,e,f,g,h}

43oooooocooo

lowcost

Vexa0CaaaC{a,c}{b,d,e,f,g,h}

45ooooco5

lowcost

Vex00cbaac{a,c,b}{d,e,f,g,h}

59ooco5

lowcost

Vex000dddd{a,c,b,d){e,f,g,h}

7654

lowcost

Vex000ddd0{a,c,b,d,h{e,f,g}

765

lowcost)

Vex000dg00{a,c,b,d,h,{f,e}

72

lowcostg}

Vex000f000{a,c,b,d,h,{e}

3

lowcostg,f}

Vex0000000{a,c,b,d,h,()

g,f,e}

lowcost

邻接表为:

0a1423

1b042535

2c031535

3d15254765—*74A

4e193753

5f364362

6g355276

7h253466

克鲁斯卡尔算法步骤

tt-iM3+n**、"-cI—3—ea—I—bd—I—h

（按边归并，堆排序）：,,__,g珈一人士、茁八昌七比wr

T—7—T-7二一~?~取b—?—d,g—d就把二个连通分量连接起来了O

7、

8、

1试着找出网G的最小生成树，画出其逻辑结构图；

2用两种不一致的表示法画出网G的存储结构图；

3用C语言（或者其他算法语言）定义其中一种表示法（存储结构）的数据类型。

解：1.最小生成树可直接画出，如右图所示。

2.可用邻接矩阵与邻接表来描述：

——F

0012000040000

1200200089CO

描述存储结构的数据类型可参见教材或者电子教案:

00200015000012注：用两个数组分别存储顶点表与邻接矩阵

#defineINFINITYINT_MAX//最大值8

00001500000010

#defineMAX_VERTEX_NUM20〃假设的最大顶点数（可取为7）

48CO00006COTypedefenum{DG,DN,AG,AN}GraphKind;〃有向/无向图，有向/无向网

T\pcdefstructArcCell{〃弧（边）结点的定义

009000060000

VRTypeadj;//顶点间关系，无权图取1或者0;有权图取权值类型

00001210000000InfoType*info;〃该弧有关信息的指针

JArcCell,AdjMatrix[MAX_VERTEX_NUM]f