研究生入学考试2010年数据结构考研辅导复习题汇总

?数据结构?〔C语言版〕

第1章绪论

计算机与信息工程学院于江德1?数据结构?研究内容是什么？1.数据结构是一门研究非数值计算的程序设计问题中计算机的〔〕以及它们之间的〔〕和〔〕的学科。2?数据结构?中的根本概念你清楚了吗？2.以下关于数据结构的根本概念中，表达正确的选项是〔〕。A．数据元素是数据的最小单位。B.数据的逻辑结构是指数据的各数据项之间的逻辑关系。C.任何一个算法的设计取决于选定逻辑结构，而算法的实现依赖于采用的存储结构。D.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。3“数据结构〞中的结构指的是？3.“数据结构〞中的“结构〞指的是〔〕。A.数据的值B.数据元素的各数据项之间的关系C.数据的构成D.数据元素之间的关系4数据的逻辑结构如何描述？4.数据结构的形式化定义：用一个二元组表示，记为：Data_Structure=〔D,S〕其中，D是数据元素的有限集〔即一个数据对象〕，S是该对象中所有数据元素之间的关系的有限集合。5数据结构从逻辑上可分为？5.从逻辑上可以把数据结构分为〔〕两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构6数据的存储结构6.以下哪一个术语与数据的存储结构无关？A．双向链表B．栈C．线索二叉树D．哈希表7数据结构的根本类型7.以下数据结构，〔〕是非线性数据结构。A．队列B．栈C．二叉树D．字符串8顺序存储结构8.

下述〔〕是顺序存储方式的优点。

a．存储密度大

b．插入运算方便

c．删除运算方便d．数据元素交换方便99.抽象数据类型如何描述？抽象数据类型可用三元组〔D，S，P〕表示，其中，D是数据对象，S是D上的关系集，P是对D的根本操作集。ADT抽象数据类型名{数据对象：〈数据对象的定义〉数据关系：〈数据关系的定义〉根本操作：〈根本操作的定义〉}ADT抽象数据类型名1010.关于1.3节的问题typedefStatusOK、ERRORElemType引用参数&结合例1-7思考：Triplet是？malloc〔〕注意函数格式11一个算法是？11．一个算法应该是〔〕。A．程序B．问题求解步骤的描述C．要满足五个根本特性D．A和C.12算法的时间复杂度12．某算法的时间复杂度为O(n2)，说明该算法的〔〕A问题规模是n2B执行时间等于n2C执行时间与n2成正比D问题规模与n2成正比13参考答案2、C3、D5、C6、B7、C8、D11、B12、C14你的问题？Thanks！15?数据结构?〔C语言版〕

第2章线性表

计算机与信息工程学院于江德161.线性结构的根本特征①集合中必存在唯一的一个“第一元素〞；②集合中必存在唯一的一个“最后元素〞；③除第一元素之外，均有唯一的前驱；④除最后元素之外，均有唯一的后继。线性结构是假设干数据元素构成的有序〔次序〕集17顺序存储和链式存储2.

线性表的顺序存储结构和链式存储结构分别是______。()A.顺序存取的存储结构、顺序存取的存储结构B.顺序存取的存储结构、随机存取的存储结构C.随机存取的存储结构、随机存取的存储结构D.随机存取的存储结构、顺序存取的存储结构183.

一批数据用顺序存储结构，第一个元素的存储地址是200，且每个元素长度为2，那么第5个元素的存储地址是()A、210

B、208C、200

D、22019

一、线性表的顺序表示用一组地址连续的存储单元

依次存放线性表中的数据元素

a1a2

…ai-1ai

…an线性表的起始地址，称作线性表的基地址20以“存储位置相邻〞表示有序对<ai-1，ai>即：LOC(ai)=LOC(ai-1)+l一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=

LOC(a1)+(i-1)×l

↑基地址214.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较(

)个结点。

A)n

B)n/2

C)(n-1)/2

D)(n+1)/2225.单链表中，增加头结点的目的是为了(

)。A)方便运算的实现

B)用于标识单链表

C)使单链表中至少有一个结点

D)用于标识起始结点的位置236、各种存储结构的描述顺序表单链表双向链表静态链表24二、顺序映像的C语言描述#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{

}SqList;//俗称顺序表ElemType*elem;//存储空间基址int

length;//当前长度int

listsize;//当前分配的存储容量

//(以sizeof(ElemType)为单位)25

用一组地址任意的存储单元存放线性表中的数据元素。一、线性链表的相关概念以元素(数据元素的映象)+指针(指示直接后继的存储位置)=结点(这两局部信息组成数据元素ai的映象)以“结点的序列〞表示线性表称作链表26

以线性链表第一个数据元素的存储地址作为线性链表的地址，称作线性表的头指针头结点

a1a2…...an^头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点〞，以指向头结点的指针为链表的头指针空指针线性表为空表时，头结点的指针域为空27

typedefstructLNode{ElemTypedata;//数据域

structLnode*next;//指针域}LNode,*LinkList;

二、结点和单链表的C语言描述LinkListL；//L为单链表的头指针数据域指针域data*next28structLNode{ElemTypedata;//数据域

structLnode*next;//指针域};

typedef

structLNode

LNode;

typedef

LNode

*LinkList;

下面的描述和上页的等同吗？LinkListL；//L为单链表的头指针29结构体成员如何访问？1、结构体变量中成员的访问

例如：LNodea； a.data;a.next;2、结构体指针所指结点中成员的访问

例如：LNode*p；或LinkListp； p->data;p->next;30

2.3.3双向链表typedefstructDuLNode{ElemTypedata;

//数据域

structDuLNode*prior;

//指向前驱的指针域

structDuLNode*next;

//

指向后继的指针域}

DuLNode,*DuLinkList;31四、静态链表动态链表链表中的结点空间都是动态申请和释放的。在有些高级语言〔如BASIC〕中，没有提供指针类型，此时假设仍想采用链表作为线性表存储结构，该如何实现?那么只能借助一维数组和游标(Cursor)来模拟链表，这种链表称为“静态链表〞。32#defineMAXSIZE 1000 typedefstruct{ElemTypedata;int cur;}Component,SLinkList[MAXSIZE];静态链表的描述：337、单链表中〔1〕带头结点和不带头结点的单链表L判空条件有何不同？ 带头结点：L->next=NULL 不带头结点：L=NULL〔2〕p->data=ai，那么p->next->data=? p->next->data=ai+1348、插入和删除操作的实现顺序表单链表循环链表双向链表双向循环链表静态链表359.在一个有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()

A.O(1)B.O(n)C.O(n*n)

D.O(nlog2n)3610.假设某线性表最常用的操作是存取任一指定序号的元素和在表尾进行插入和删除运算，那么利用〔〕存储方式最节省时间。A．顺序表B．双向链表C．带头结点的双向循环链表D．单循环链表3711.

某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，那么采用〔〕存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表3812.设一个链表最常用的操作是在末尾插入结点和删除尾结点，那么选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表3913．假设某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。那么采用〔〕存储方式最节省运算时间。A．单链表B．双链表C．单循环链表D．带头结点的双循环链表4014．链表不具有的特点是〔〕A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性表长度成正比4115．静态链表中指针表示的是〔〕。A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址42算法设计题：1.设计算法，求带头结点的单循环链表的表长。2.单链表L，写一算法，删除其重复结点。3.写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。4.单链表L,写一算法，返回其倒数第K个结点。5.写一算法，将一带有头结点的单链表就地逆置，即要求逆置在原链表上进行，不允许重新构造新链表。43设L是带头结点的单链表(线性表的长度不包括头结点)。intLength_LinkList1(LinkListL){LNode*p=L;/*p指向头结点*/intj=0;while(p->next){p=p->next;j++}/*p所指的是第j个结点*/returnj;}44单链表L，写一算法，删除其重复结点。voidpur_LinkList(LinkListH){LNode*p,*q,*r;p=H->next;/*p指向第一个结点*/

if(p==NULL)return;while(p->next){q=p;while(q->next)/*从*p的后继开始找重复结点*/{if(q->next->data==p->data){r=q->next;/*找到重复结点，用r指向，删除*r*/q->next=r->next;

free(r);}elseq=q->next;}p=p->next;/*p指向下一个，继续*/}}45写一算法，将一带有头结点的单链表就地逆置voidLinkList_reverse(LinkList&L){

LinkList

p,q,s; p=L->next;q=p->next;s=q->next;p->next=NULL;

while(s->next) { q->next=p;p=q; q=s;s=s->next; } q->next=p;s->next=q;L->next=s;}46写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。voiddelinsert(LinkList&L){ p=L->next; //p是链表的工作指针 pre=L; //pre指向链表中数据域最小值结点的前驱 q=p; //q指向数据域最小值结点，初始假定是第一结点 while(p->next!=NULL) { if(p->next->data<q->data) //找到新的最小值结点 { pre=p; q=p->next;} p=p->next; } if(q!=L->next) //假设最小值是第一元素结点，那么不需再操作 { pre->next=q->next; //将最小值结点从链表上摘下 q->next=L->next; //将q结点插到链表最前面 L->next=q; }}47编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。LinkedListExchange〔LinkedListHEAD，LinkedListp〕∥HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后继结点交换。{q=head->next；∥q是工作指针，指向链表中当前待处理结点。pre=head；∥pre是前驱结点指针，指向q的前驱。while〔q!=null&&q!=p〕{pre=q；q=q->next；}∥未找到p结点，后移指针。if〔p->next==null〕printf〔“p无后继结点\n〞〕;∥p是链表中最后一个结点，无后继。Else∥处理p和后继结点交换{q=p->next；∥暂存p的后继。pre->next=q；∥p前驱结点的后继指向p的后继。p->next=q->next；∥p的后继指向原p后继的后继。q->next=p；∥原p后继的后继指针指向p。}}∥算法结束。48参考答案2~5、DBDA9、B10、A11、D12、D13、D14、B15、B49你的问题？Thanks！50?数据结构?〔C语言版〕

第3章栈和队列

计算机与信息工程学院于江德51特殊线性表栈栈的定义操作特性ADT定义根本操作实现时间性能队列顺序栈链式栈比较存储结构逻辑结构队列定义操作特性ADT定义循环队列链式队列存储结构逻辑结构根本操作实现时间性能52栈的特性：后进先出〔LIFO〕1.

输入序列为ABC，可以变为CBA时，经过的栈操作为〔〕A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop53栈的特性：后进先出〔LIFO〕2.

有六个元素按6，5，4，3，2，1的顺序进栈，问以下哪一个不是合法的出栈序列？〔〕A.543612B.453126C.346521D.23415654栈的特性：后进先出〔LIFO〕3.

假设一个栈的入栈序列是1,2,3,......n，其输出序列为p1,p2,p3,......pn，假设p1=n，那么pi为〔 〕A.i B.n-iC.n-i+1 D.不确定55栈的特性：后进先出〔LIFO〕4.

假设一个栈的输入序列为1，2，3...n，输出序列的第一个元素是i，那么第j个输出元素是〔〕A.i-j-1B.i-j C.j-i+1 D.不确定56栈的特性：后进先出〔LIFO〕5.

设abcdef以所给的次序进栈，假设在进栈操作时，允许退栈操作,那么下面得不到的序列为〔〕。南京理工大学1996一、9〔2分〕A．fedcbaB.bcafedC.dcefbaD.cabdef57栈的特性：后进先出〔LIFO〕6.

假设元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，那么不可能得到的出栈序列是〔

〕A：dcebfa

B：cbdaef

C：bcaefd

D：afedcb587.设计一个判别表达式中左，右括号是否配对出现的算法，采用〔〕数据结构最正确。A．线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈598.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机那么依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是

A)栈

B)队列C)树

D)图609.假设栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i=1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，那么栈满的条件是〔〕。A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]61队列的特性：先进先出〔FIFO〕10.

某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，那么不可能得到的顺序是〔〕A：bacde

B：dbaceC：dbcae

D：ecbad6211．输入序列为abcd经过输出受限的双向队列后能得到的输出序列有〔〕。A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对6312．假设以1234作为双端队列的输入序列，那么既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是()。A.1234B.4132C.4231D.42136413.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。假设每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，那么栈S的容量至少是A)1B)2C)3D)46514.向一个带头结点HS的链栈中插入一个s所指结点时，那么执行〔 〕A.HS->next=s; B.s->next=HS->next;HS->next=s;C.s->next=HS;HS=s;D.s->next=HS;HS=HS->next6615.一个循环队列Q最多可存储m个元素，其头尾指针分别是front和rear，那么判定该循环队列为满的条件是〔〕A.Q.rear-Q.front==mB.Q.rear!=Q.frontC.Q.front==(Q.rear+1)%mD.Q.front==Q.rear%m+16716.

循环队列用数组A[0..m-1]存放其元素值，其头尾指针分别为front和rear，那么当前元素个数为〔〕。A．(rear–front+m)modmB．rear-front+1C．(front–rear+m)modmD．rear-front6817.假设用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再参加两个元素后，rear和front的值分别为多少？()A.1和5B.2和4C.4和2D.5和16918．用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，那么在进行删除操作时()。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改70参考答案1、BCCDD6、DDBBC11、ECCBC16、ABD71你的问题？Thanks！72?数据结构?〔C语言版〕

第5章数组和广义表

计算机与信息工程学院于江德73二维数组的特点：2个下标，每个元素ai,j受到两个关系〔行关系和列关系〕的约束：一个m×n的二维数组可以看成是m行的一维数组，或者n列的一维数组。N维数组的特点：n个下标，每个元素受到n个关系约束一个n维数组可以看成是由假设干个n－1维数组组成的线性表。a11a12…a1n

a21a22…a2n

……

aij…

am1am2…amn

Amn=74数组的顺序存储二维数组A[m][n]按行优先寻址计算方法，每个数组元素占据d个地址单元。设数组的基址为LOC(a11)：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*d设数组的基址为LOC(a00)：LOC(aij)=LOC(a00)+(i*n+j)*d75数组的顺序存储二维数组A[m][n]按列优先寻址计算方法，每个数组元素占据d个地址单元。设数组的基址为LOC(a11)：LOC(aij)=LOC(a11)+((j-1)*m+i-1)*d设数组的基址为LOC(a00)：LOC(aij)=LOC(a00)+(j*m+i)*d761.

二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,…,8,列下标j=1,2,…,10。假设A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素〔〕的起始地址相同。设每个字符占一个字节。A.A[8,5]B.A[3,10]C.A[5,8]D.A[0,9]772.

二维数组N的每个元素占4个存储单元，行下标i的范围从0到4，列下标j的范围从0到5，N按行存储时元素N[3][5]的起始地址与N按列存储时元素〔 〕的起始地址相同。A.N[2][4] B.N[3][4]C.N[3][5] D.N[4][4]785.3.1特殊矩阵的压缩存储特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵〔上三角矩阵、下三角矩阵〕三对角矩阵79对称矩阵的压缩存储设有一个nn的对称矩阵A。在矩阵中，aij=aji该矩阵中数组元素的下标有何特征？80为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储。数组B共有n+(n-1)++1=n*(n+1)/2个元素。81上三角矩阵下三角矩阵82下三角矩阵Ba00a10a11a20a21a22a30a31a32……an-1n-1

012345678n(n+1)/2-1假设ij,数组元素A[i][j]在数组B中的存放位置为1+2++i+j=(i+1)*i/2+j前i行元素总数第i行第j个元素前元素个数83假设i<j，数组元素A[i][j]在矩阵的上三角局部,在数组B中没有存放，可以找它的对称元素A[j][i]：=j*(j+1)/2+i注：书上P95公式〔5-3〕i和j的范围

84上三角矩阵Ba00a01a02a03a11a12a13a22a23

a33

0123456789假设ij，数组元素A[i][j]在数组B中的存放位置为 n+(n-1)+(n-2)++(n-i+1)+j-i前i行元素总数第i行第j个元素前元素个数n=485

假设ij，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+1)+j-i==(2*n-i+1)*i/2+j-i==(2*n-i-1)*i/2+j假设i>j，数组元素A[i][j]在矩阵的下三角局部，在数组B中没有存放。因此，找它的对称元素A[j][i]。A[j][i]在数组B的第(2*n-j-1)*j/2+i的位置中找到。86三对角矩阵的压缩存储Ba00a01a10a11a12a21a22a23…

an-1n-2an-1n-1

01234567891087三对角矩阵中除主对角线及在主对角线上下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组B中，且a00存放于B[0]。在三条对角线上的元素aij

满足

0in-1,i-1ji+1在一维数组B中A[i][j]在第i行，它前面有3*i-1个非零元素,在本行中第j列前面有j-i+1个，所以元素A[i][j]在B中位置为k=

2*i+j。883.

设n阶方阵是一个上三角矩阵，那么需存储的元素个数为〔〕A．nB．n*nC．n*n/2 D．n(n+1)/2894.

设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，那么a85〔即该元素下标ij=85〕的地址为〔〕。A.13B.33C.18D.40905.

假设对n阶对称矩阵A[1..n，1..n]以行序为主序方式下将其下三角的元素〔包括主对角线上的所有元素〕依次存放于一维数组B[1..n(n+1)/2]中，那么在B中确定aij(i<j)的位置k的关系为〔〕。A．i*(i-1)/2+jB．j*(j-1)/2+iC．i*(i+1)/2+jD．j*(j+1)/2+i91参考答案1、BBDBB92你的问题？Thanks！93?数据结构?〔C语言版〕

第6章树和二叉树

计算机与信息工程学院于江德94树形结构树树的定义根本术语ADT定义树的遍历：先序遍历后序遍历层序遍历二叉树双亲表示法孩子表示法相互转换存储结构逻辑结构存储结构逻辑结构孩子兄弟表示法二叉树的定义二叉树的性质特殊二叉树二叉树的性质二叉树的四种遍历方法满二叉树完全二叉树二叉链表顺序存储线索链表三叉链表遍历算法实现基于遍历的其他算法95二叉树的遍历1.

一棵二叉树的先序遍历结果为ABCDEF，中序遍历结果为CBAEDF，那么后序遍历结果为〔 〕A.CBEFDA B.FEDCBAC.CBEDFA D.不确定96二叉树的遍历2.

某二叉树的后序遍历序列为dabec，中序遍历序列为debac，那么先序遍历序列为〔〕。A．acbedB．decabC．deabcD．cedba97二叉树的遍历3.

对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历98二叉树的遍历4.

二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历:HFIEJKG。该二叉树根的右子树的根是()A．EB．FC．GD．H99二叉树的遍历5.

某二叉树的先序和后序序列正好相反，那么该二叉树一定是〔〕的二叉树。A.空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子100二叉树的遍历5’.

某二叉树的先序和后序序列正好相反，那么该二叉树一定是〔〕的二叉树。A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树101二叉树的遍历6.

设n，m为一棵二叉树的两个结点，在中序遍历时，n在m前的条件是〔〕A.n在m的右方 B.n是m的祖先C.n在m的左方 D.n是m的子孙1027.具有10个叶子结点的二叉树中有〔 〕个度为2的结点。A.8 B.9 C.10 D.111038.树中所有结点的度的和等于所有结点数加〔〕。A．0 B．1C．－1 D．21049.在线索化二叉树中，t所指结点没有左子树的充要条件是〔 〕A．t->left=NULLB.t->ltag=1C.t->ltag=1且t->left=NULLD.以上都不对10510.

由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为〔〕A．23B.37C.44D.4610611．将有关二叉树的概念推广到三叉树，那么一棵有244个结点的完全三叉树的高度〔〕A．4B．5C．6D．710712．一个具有1025个结点的二叉树的高h为〔〕.A．11B．10C．11至1025之间D．10至1024之间10813.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是〔〕。A．N1B．N1+N2C．N3D．N2+N310914.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1那么T中的叶子数为〔〕A．5B．6C．7D．811015.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是〔〕A．m-nB．m-n-1C．n+1D．条件缺乏，无法确定11116.

假设一棵二叉树具有10个度为2的结点，5个度为1的结点，那么度为0的结点个数是〔〕A．9B．11C．15D．不确定11217.一棵完全二叉树上有1000个结点，其中叶子结点的个数是〔〕A．250B．500C．254D．505E．以上答案都不对113问:设一棵完全二叉树具有1000个结点，那么它有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。48948810由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现只有非空右子树的结点(0个)。答：易求出总层数和末层叶子数。总层数k=log2n＋1=10;且前9层总结点数为29-1=511

(完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。114请注意叶子结点总数≠末层叶子数！还应当加上第k-1层〔靠右边〕的0度结点个数。分析：k层的489个叶子的父结点占上层的245个结点〔489/2)上层〔k=9)右边的0度结点数还有29-1-245=11个！另一法：可先求2度结点数,再由此得到叶子总数。首先，k-2层的28-1〔255〕个结点肯定都是2度的〔完全二叉〕另外，末层叶子〔刚刚已求出为489〕所对应的双亲也是度＝2，〔共有489/2＝244个〕。所以，全部2度结点数为255(k-2层)＋244(k-1层)=499个；总叶子数＝2度结点数＋1=500个。第i层上的满结点数为2i-1所以，全部叶子数＝489(末层)＋11(k-1层)=500个。度为2的结点＝叶子总数－1=499个。11518．设给定权值总数有n个，其哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-118‘．有n个叶子的哈夫曼树的结点总数为()A．不确定B．2nC．2n+1D．2n-111619.有关二叉树以下说法正确的选项是〔〕A．二叉树的度为2B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2D．二叉树中任何一个结点的度都为211720.一棵二叉树高度为h,所有结点的度或为0，或为2，那么这棵二叉树最少有()结点A．2hB．2h-1C．2h+1D．h+111821.一棵树高为K的完全二叉树至少有〔〕个结点A．2k–1B.2k-1–1C.2k-1D.2k11922.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用()次序的遍历实现编号。A．先序B.中序C.后序D.从根开始按层次遍历12023.树的后根遍历序列等同于该树对应的二叉树的().A.先序序列B.中序序列C.后序序列12124.假设二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用()遍历方法最适宜。A．前序B．中序C．后序D．按层次12225.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序〔〕A．都不相同B．完全相同C．先序和中序相同，而与后序不同D．中序和后序相同，而与先序不同12326.假设X是二叉中序线索树中一个有左孩子的结点，且X不为根，那么x的前驱为()A.X的双亲B.X的右子树中最左的结点C.X的左子树中最右结点D.X的左子树中最右叶结点12427.引入二叉线索树的目的是〔〕A．加快查找结点的前驱或后继的速度B．为了能在二叉树中方便的进行插入与删除C．为了能方便的找到双亲D．使二叉树的遍历结果唯一12528.n个结点的线索二叉树上含有的线索数为〔〕A．2nB．n－lC．n＋lD．n12629.设F是一个森林，B是由F变换得的二叉树。假设F中有n个非终端结点，那么B中右指针域为空的结点有〔〕个。A．n-1B．nC．n+1D．n+212730.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A[1..n]中，那么二叉树中第i个结点〔i从1开始用上述方法编号〕的右孩子在数组A中的位置是〔〕A．A[2i](2i<=n)B．A[2i+1](2i+1<=n)C．A[i-2]D．条件不充分，无法确定12831.设一棵完全二叉树具有1000个结点，那么它有〔〕个度为2的结点。A．488B．489C．499D．500129参考答案1、ADCCB〔5‘、C〕6、CBCBC11、CCDDA16、BBDBB21、CCBCB26、CACCD31、C130你的问题？Thanks！131?数据结构?〔C语言版〕

第7章图

计算机与信息工程学院于江德132图结构图的定义根本术语ADT定义图的遍历：邻接矩阵邻接表存储结构逻辑结构完全图度、入度、出度权、网路径、回路连通图、强连通图生成树最小生成树最短路径重要应用拓扑排序关键路径1331.

有n个结点的无向图的边数最多为〔〕A．n+1B．n(n-1)/2 C．n(n+1) D．2n(n+1)1342.

无向图中一个顶点的度是指图中〔〕A．通过该顶点的简单路径数B．通过该顶点的回路数C．与该顶点相关联的边的数目D．与该顶点连通的顶点数1352’.

无向图中一个顶点的度是指图中〔〕A．通过该顶点的简单路径数B．通过该顶点的回路数C．与该顶点相邻接的顶点数D．与该顶点连通的顶点数1363.

在一个图中，所有顶点的度数之和与图的边数的比是〔〕A．1:2B．1:1 C．2:1 D．4:11374.

在无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个〔〕。A．顶点序列 B．边序列C．权值总和D．边的条数1385.

在一个具有n个顶点的无向图中，要连通全部顶点至少需要〔〕条边。A．n B.n+1 C.n-1 D.n/21396.

假设G是一个具有36条边的非连通无向图〔不含自回路和多重边〕，那么图G至少有〔〕个顶点。A．11B.10C.9D.81407.

以下哪一种图的邻接矩阵是对称矩阵？〔 〕A.有向图 B.无向图 C.AOV网 D.AOE网1418.简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。假设无向图G有n个结点，其邻接矩阵为A[1…n,1…n]，且压缩存储在B[1…k]，那么k的值至少为〔〕。A．n(n+1)/2B.n2/2C.(n-1)(n+1)/2D.n(n-1)/21429.一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有〔〕个零元素。A．eB.2eC.n2-eD.n2-2e14310.假设采用邻接矩阵来存储简单有向图，那么其某一个顶点i的入度等于该矩阵〔〕。A．第i行中值为1的元素个数B.所有值为1的元素个数C．第i行及第i列中值为1的元素总个数D．第i列中值为1的元素个数14411.

下面关于图的存储的表达中，哪一个是正确的。〔〕A．用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用邻接矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关14512．要连通具有n个顶点的有向图，至少需要〔〕条边。A．n-lB．nC．n+lD．2n14613．在一个无向图中，所有顶点的度数之和等于所有边数〔〕倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的〔〕倍。A．1/2B．2C．1D．414714.以下说法不正确的选项是〔〕。A．图的遍历是从给定的源点出发每一个顶点仅被访问一次B．遍历的根本算法有两种：深度遍历和广度遍历C．图的深度遍历不适用于有向图D．图的深度遍历是一个递归过程14815.无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的选项是〔〕。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b149注：南京理工大学以前的题16.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？〔〕aebdfcacfdebaedfcbaefdcbaefdbcA．5个B．4个C．3个D．2个150在生成树的构造过程中，图中n个顶点分属两个集合：已落在生成树上的顶点集U和尚未落在生成树上的顶点集V-U，那么应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。一般情况下所添加的顶点应满足以下条件:UV-U151〔1〕初始状态：U={u0},〔u0∈V〕，TE={},〔2〕从E中选择顶点分别属于U、V-U两个集合、且权值最小的边〔u0,v0)，将顶点v0归并到集合U中，边〔u0,v0)归并到TE中；〔3〕直到U=V为止。此时TE中必有n-1条边，T＝(V,{TE})就是最小生成树。设：N=〔V,E〕是个连通网，另设U为最小生成树的顶点集，TE为最小生成树的边集。构造步骤:普利姆〔Prim〕算法152例：1465231565546362364251[注]：在最小生成树的生成过程中，所选的边都是一端在V-U中，另一端在U中。153设计思路：①增设一辅助数组Closedge[n]，每个数组分量都有两个域：要求：使Closedge[i].lowcost=min((u,vi))uU计算机内怎样实现Prim〔普里姆〕算法？Prime算法特点:

将顶点归并，与边数无关，适于稠密网。故采用邻接矩阵作为图的存储表示。adjvexlowcostvi在U中的邻点uClosedge[i]V-U中顶点viu与vi之间对应的边权从u1~um中挑154vexlowcostvexlowcostvexlowcostvexlowcostvexlowcostvexlowcostV-UU65432vclosedge1423561655536426具体例如：{1}{2,3,4,5,6}1611151∞1∞{1,3}{2,4,5,6}035153634{1,3,6}{2,4,5}35062360{1,3,6,4}{2,5}3503600{1,3,6,4,2}{5}00002300000{1,3,6,4,2,5}{}13起点46245235123456显然，Prim算法的时间效率＝O(n2)155步骤：(1)首先构造一个只有n个顶点但没有边的非连通图T={V,},图中每个顶点自成一个连通分量。(2)当在边集E中选到一条具有最小权值的边时,假设该边的两个顶点落在T中不同的连通分量上，那么将此边参加到生成树的边集合T中；否那么将此边舍去，重新选择一条权值最小的边。(3)如此重复下去，直到所有顶点在同一个连通分量上为止。此时的T即为所求〔最小生成树〕。克鲁斯卡尔(Kruskal)算法:设N={V,E}是有n个顶点的连通网，Kruskal算法采用邻接表作为图的存储表示156Kruskal〔克鲁斯卡尔〕算法例：146523156554636215432135246157普里姆算法克鲁斯卡尔算法时间复杂度O(n2)O(eloge)稠密图稀疏图算法名适应范围比较两种算法158有向无环图的应用①AOV网(ActivityOnVertexNetwork)—用顶点表示活动的网络AOV网定义：假设用有向图表示一个工程，在图中用顶点表示活动，用弧表示活动间的优先关系。Vi必须先于活动Vj进行。那么这样的有向图叫做用顶点表示活动的网络，简称AOV网。②AOE网(ActivityOnEdges)—用边表示活动的网络AOE网定义：如果在无环的带权有向图中，用有向边表示一个工程中的活动，用边上权值表示活动持续时间，用顶点表示事件，那么这样的有向图叫做用边表示活动的网络，简称AOE网。有两种常用的活动网络〔ActivityNetwork〕：159AOV网络的用途：7.5.1拓扑排序例1：教学方案的制定AOV网络假设用于教学方案的制定，可以解决：哪些课程是必须先修的，哪些课程是可以并行学习的。预备知识：拓扑排序什么叫拓扑排序？由某个集合上的一个偏序得到的该集合上的一个全序，这个操作称之为拓扑排序。直观看，偏序指集合中仅有局部成员之间可比较，而全序指集合中全体成员之间均可比较。实质：对一个有向无环图中的顶点排成一个具有前后次序的线性序列。160进行拓扑排序的方法：输入AOV网络。令n为顶点个数。 在AOV网络中选一个没有直接前驱的顶点,并输出之;

从图中删去该顶点,同时删去所有它发出的有向边;

重复以上2、3步,直到：全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或：图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。拓扑排序算法：重复选择没有直接前驱的顶点。

161abcdefghk64521187244用边表示活动的网〔AOE网〕例如:源点汇点6174顶点：事件；有向边：活动有向边对应的权：活动持续的时间162AOE网络的用途：常用于大型工程的方案管理。利用AOE网络可以解决以下两个问题：(1)完成整个工程至少需要多少时间。(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?或者说，哪些活动是影响工程进度的关键？7.5.2关键路径163整个工程完成的时间为：从有向图的源点到汇点的最长路径。abcdefghk64521187244例如:“关键活动〞指的是：该弧上的权值增加将使有向图上的最长路径的长度增加。显然……源点汇点6174164

如何求关键活动？“关键活动〞有何特征？该活动的最早开始时间=该活动的最迟开始时间jkdut165假设第i条弧为<j,k>,那么对第i项活动而言“活动(弧)〞的最早开始时间e(i):e(i)=ve(j);“活动(弧)〞的最迟开始时间l(i):l(i)=vl(k)–dut(<j,k>);事件发生时间的计算公式:ve(源点)=0;ve(k)=Max{ve(j)+dut(<j,k>)}vl(汇点)=ve(汇点);vl(j)=Min{vl(k)–dut(<j,k>)}“事件(顶点)〞的最早发生时间ve(j)ve(j)=从源点到顶点j的最长路径长度;“事件(顶点)〞的最迟发生时间vl(k)vl(k)=关键路径长度-从顶点k到汇点的最长路径长度;166求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动ell-e00002266046258377077071031616014140033167求从源点到其余各点的最短路径的算法的根本思想:依最短路径的长度递增的次序求得各条路径源点v1…其中，从源点到顶点v1的最短路径是所有最短路径中长度最短者。思考：该路径有何特点？v2求最短路径的迪杰斯特拉算法：一般情况下，Dist[k]=<源点到顶点k的弧上的权值>或者=<源点到其它顶点的路径长度>+<其它顶点到顶点k的弧上的权值>设置辅助数组Dist，其中每个分量Dist[k]表示当前所求得的从源点到其余各顶点k的最短路径。168在这条路径上，必定只含一条弧，且这条弧的权值最小。(v1)

下一条路径长度次短的最短路径的特点:路径长度最短的最短路径的特点:它只可能有两种情况:或者是直接从源点到该点(只含一条弧)；

或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。其余最短路径的特点：再下一条路径长度次短的最短路径的特点:它可能有三种情况：或者是，直接从源点到该点(只含一条弧)；或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是,从源点经过顶点v2,再到达该顶点〔由两条弧或三条弧〕。它或者是直接从源点到该点(只含一条弧)；或者是，从源点经过已求得最短路径的顶点，再到达该顶点。169迪杰斯特拉(Dijkstra)算法思想按路径长度递增次序产生最短路径算法：把V分成两组：(1) S：已求出最短路径的顶点的集合(2) V-S=T：尚未确定最短路径的顶点集合求解的过程是将T中顶点按最短路径递增的次序参加到S中，保证(1)从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度(2)每个顶点对应一个距离值S中顶点：从V0到此顶点的最短路径长度T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度依据：可以证明V0到T中顶点Vk的最短路径，或是从V0到Vk的直接路径的权值；或是从V0经S中顶点到Vk的路径权值之和〔反证法可证〕170(v0,v2)+(v2,v3)<(v0,v3)终点

从v0到各终点的dist值和最短路径v1v2v3v4v5vjS之外的当前最短路径之顶点60{v0,v2,v3}50{v0,v4,v3}30{v0,v4}90{v0,v4,v5}60{v0,v4,v3,v5}5540312100603010102050s{v0,v2}{v0,v2,v4}{v0,v2,v4,v3}{v0,v2,v4,v3,v5}10{v0,v2}∞

30{v0,v4}100{v0,v5}∞∞∞∞例3：v2v4v3v5100{v0,v5}012345dist[w]01234510{v0,v2}50{v0,v4,v3}30{v0,v4}17117.

在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为()。A.O(n) B.O(n+e)C.O(n2)D.O(n3)17218.下面是求连通网的最小生成树的prim算法：集合VT，ET分别放顶点和边，初始为〔1〕，下面步骤重复n-1次:a：〔2〕；b：〔3〕；最后：〔4〕。CABA〔1〕．A．VT，ET为空B．VT为所有顶点，ET为空C．VT为网中任意一点，ET为空D．VT为空，ET为网中所有边〔2〕．A.选i属于VT，j不属于VT，且〔i，j〕上的权最小B．选i属于VT，j不属于VT，且〔i，j〕上的权最大C．选i不属于VT，j不属于VT，且〔i，j〕上的权最小D．选i不属于VT，j不属于VT，且〔i，j〕上的权最大〔3〕．A．顶点i参加VT，〔i,j〕参加ETB.顶点j参加VT，〔i,j〕参加ETC.顶点j参加VT，〔i,j〕从ET中删去D．顶点i,j参加VT，〔i,j〕参加ET〔4〕．A．ET中为最小生成树B．不在ET中的边构成最小生成树C．ET中有n-1条边时为生成树，否那么无解D．ET中无回路时，为生成树，否那么无解17319.有向图G=(V,E)，其中V={v1,v2,v3,v4,v5,v6,v7}，E={<v1,v2>，<v1,v3>，<v1,v4>，<v2,v5>，<v3,v5>，<v3,v6>，<v4,v6>，<v3,v7>，<v6,v7>}，G的拓扑序列是〔〕。A．v1,v3,v4,v6,v2,v5,v7B．v1,v3,v2,v6,v4,v5,v7C．v1,v3,v4,v5,v2,v6,v7D．v1,v2,v5,v3,v4,v6,v717420.一个有向无环图的拓扑排序序列〔〕是唯一的。A．一定B．不一定17521.在有向图G的拓扑序列中，假设顶点Vi在顶点Vj之前，那么以下情形不可能出现的是〔〕。A．G中有弧<Vi，Vj>B．G