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

数据结构（C语言版）第1章 绪论,计算机与信息工程学院于江德,2,数据结构研究内容是什么？,1. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和（ ）的学科。,3,数据结构中的基本概念你清楚了吗？,2. 下列关于数据结构的基本概念中，叙述正确的是（ ）。A数据元素是数据的最小单位。B. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。C. 任何一个算法的设计取决于选定逻辑结构，而算法的实现依赖于采用的存储结构。D. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。,4,“数据结构”中的结构指的是？,3. “数据结构”中的“结构”指的是（ ）。A. 数据的值B. 数据元素的各数据项之间的关系C. 数据的构成D.数据元素之间的关系,5,数据的逻辑结构如何描述？,4.数据结构的形式化定义：用一个二元组表示，记为： Data_Structure = （D, S） 其中，D 是数据元素的有限集（即一个数据 对象），S 是该对象中所有数据元素之间的关系的有限集合。,6,数据结构从逻辑上可分为？,5. 从逻辑上可以把数据结构分为（ ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构,7,数据的存储结构,6.以下哪一个术语与数据的存储结构无关？ A双向链表 B栈 C线索二叉树 D哈希表,8,数据结构的基本类型,7.下列数据结构，（ ）是非线性数据结构。 A队列 B栈 C二叉树 D字符串,9,顺序存储结构,8.下述（ ）是顺序存储方式的优点。 a存储密度大 b插入运算方便 c删除运算方便 d数据元素交换方便,10,9. 抽象数据类型如何描述？,抽象数据类型可用三元组（D，S，P）表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。 ADT 抽象数据类型名 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 ADT 抽象数据类型名,11,10. 关于1.3节的问题,typedefStatusOK、ERRORElemType引用参数&,结合例1-7思考：Triplet是？malloc（）注意函数格式,12,一个算法是？,11一个算法应该是（ ）。 A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C.,13,算法的时间复杂度,12某算法的时间复杂度为O(n2)，表明该算法的（）A 问题规模是n2 B 执行时间等于n2C 执行时间与n2成正比D问题规模与n2成正比,14,参考答案,2、C 3、D 5、C6、B7、C 8、D11、B 12、C,你的问题？,Thanks！,数据结构（C语言版）第2章 线性表,计算机与信息工程学院于江德,17,1. 线性结构的基本特征, 集合中必存在唯一的一个“第一元素”；, 集合中必存在唯一的一个 “最后元素”；, 除第一元素之外，均有 唯一的前驱；, 除最后元素之外，均有 唯一的后继。,线性结构是若干数据元素构成的有序（次序）集,18,顺序存储和链式存储,2. 线性表的顺序存储结构和链式存储结构分别是_。( ) A. 顺序存取的存储结构、顺序存取的存储结构 B. 顺序存取的存储结构、随机存取的存储结构 C. 随机存取的存储结构、随机存取的存储结构 D. 随机存取的存储结构、顺序存取的存储结构,19,3. 一批数据用顺序存储结构，第一个元素的存储地址是200，且每个元素长度为2，则第5个元素的存储地址是( ) A、210 B、208 C、200 D、220,20,一、线性表的顺序表示用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址，称作线性表的基地址,21,以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + l 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)l 基地址,22,4.从具有n个结点的单链表中查找值等于x的结点时，在查找成功的情况下，平均需比较( )个结点。A)n B)n/2 C)(n-1)/2 D)(n+1)/2,23,5.单链表中，增加头结点的目的是为了( )。 A)方便运算的实现B)用于标识单链表C)使单链表中至少有一个结点D)用于标识起始结点的位置,24,6、各种存储结构的描述,顺序表单链表双向链表静态链表,25,二、顺序映像的 C 语言描述#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量#define LISTINCREMENT 10 /线性表存储空间的分配增量,typedef struct SqList; / 俗称 顺序表,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),26,用一组地址任意的存储单元存放线性表中的数据元素。,一、线性链表的相关概念,以元素(数据元素的映象) + 指针(指示直接后继的存储位置) = 结点 (这两部分信息组成数据元素ai的映象),以“结点的序列”表示线性表 称作链表,27,以线性链表第一个数据元素 的存储地址作为线性链表的地址，称作线性表的头指针,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针,空指针,线性表为空表时，头结点的指针域为空,28,typedef struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList;,二、结点和单链表的 C 语言描述,LinkList L； / L 为单链表的头指针,29,struct LNode ElemType data; / 数据域 struct Lnode *next; / 指针域 ; typedef struct LNode LNode; typedef LNode *LinkList;,下面的描述和上页的等同吗？,LinkList L； / L 为单链表的头指针,30,结构体成员如何访问？,1、结构体变量中成员的访问例如：LNode a；a.data; a.next;2、结构体指针所指结点中成员的访问例如：LNode *p；或LinkList p；p-data; p-next;,31,2.3.3 双向链表,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,32,四、静态链表,动态链表 链表中的结点空间都是动态申请和释放的。在有些高级语言（如BASIC）中，没有提供指针类型，此时若仍想采用链表作为线性表存储结构，该如何实现?则只能借助一维数组和游标(Cursor)来模拟链表，这种链表称为“静态链表”。,33,#define MAXSIZE1000typedef struct ElemType data; int cur; Component, SLinkListMAXSIZE;,静态链表的描述：,34,7、单链表中,（1）带头结点和不带头结点的单链表L判空条件有何不同？带头结点：L-next = NULL不带头结点：L = NULL（2）p-data = ai，则p-next-data = ? p-next-data = ai+1,35,8、插入和删除操作的实现,顺序表单链表循环链表双向链表双向循环链表静态链表,36,9.在一个有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(n*n) D.O(nlog2n),37,10.若某线性表最常用的操作是存取任一指定序号的元素和在表尾进行插入和删除运算，则利用（ ）存储方式最节省时间。 A顺序表 B双向链表 C带头结点的双向循环链表 D单循环链表,38,11.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表,39,12.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D. 带头结点的双循环链表,40,13若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用（ ）存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表,41,14 链表不具有的特点是（ ） A插入、删除不需要移动元素B可随机访问任一元素 C不必事先估计存储空间D所需空间与线性表长度成正比,42,15静态链表中指针表示的是（ ）。A 内存地址 B数组下标C下一元素地址 D左、右孩子地址,43,算法设计题：,1.设计算法，求带头结点的单循环链表的表长。2.已知单链表L，写一算法，删除其重复结点。3. 写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。 4.已知单链表L,写一算法，返回其倒数第K个结点。 5.写一算法，将一带有头结点的单链表就地逆置，即要求逆置在原链表上进行，不允许重新构造新链表。,44,设L是带头结点的单链表(线性表的长度不包括头结点)。int Length_LinkList1 (LinkList L) LNode * p=L; /*p指向头结点*/int j=0;while (p-next) p=p-next; j+ /*p所指的是第 j 个结点*/return j;,45,已知单链表L，写一算法，删除其重复结点。,void pur_LinkList(LinkList H) 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); else q=q-next; p=p-next; /*p指向下一个，继续*/ ,46,写一算法，将一带有头结点的单链表就地逆置,void LinkList_reverse(LinkList ,47,写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。,void delinsert(LinkList ,48,编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。,LinkedList Exchange（LinkedList HEAD， LinkedList p） HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后继结点交换。q=head-next； q是工作指针，指向链表中当前待处理结点。pre=head； pre是前驱结点指针，指向q的前驱。while（q!=null p是链表中最后一个结点，无后继。Else 处理p和后继结点交换 q=p-next； 暂存p的后继。 pre-next=q； p前驱结点的后继指向p的后继。 p-next=q-next；p的后继指向原p后继的后继。 q-next=p ；原p后继的后继指针指向p。 算法结束。,49,参考答案,25、DBDA9、B 10、A11、 D 12、D 13、D 14、B 15、B,你的问题？,Thanks！,数据结构（C语言版）第3章 栈和队列,计算机与信息工程学院于江德,52,特殊线性表,栈,栈的定义操作特性ADT定义,基本操作实现时间性能,队列,顺序栈,链式栈,比较,存储结构,逻辑结构,队列定义操作特性ADT定义,循环队列,链式队列,存储结构,逻辑结构,基本操作实现时间性能,53,栈的特性：后进先出（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, pop,54,栈的特性：后进先出（LIFO）,2. 有六个元素按6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6,55,栈的特性：后进先出（LIFO）,3. 若已知一个栈的入栈序列是1,2,3,.n，其输出序列为p1,p2,p3,.pn，若p1=n，则pi为（ ） A. i B. n-i C. n-i+1 D.不确定,56,栈的特性：后进先出（LIFO）,4. 若一个栈的输入序列为1，2，3 .n，输出序列的第一个元素是i，则第j个输出元素是（ ）A. i-j-1 B. i-jC. j-i+1 D. 不确定,57,栈的特性：后进先出（LIFO）,5. 设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则下面得不到的序列为（ ）。南京理工大学 1996 一、9（2分）Afedcba B. bcafedC. dcefba D. cabdef,58,栈的特性：后进先出（LIFO）,6. 若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行。但不允许连续三次进行退栈工作，则不可能得到的出栈序列是（ ）A：dcebfa B：cbdaefC：bcaefd D：afedcb,59,7.设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。A线性表的顺序存储结构B. 队列C. 线性表的链式存储结构D. 栈,60,8.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是A)栈 B)队列 C)树 D)图,61,9.若栈采用顺序存储方式存储，现两栈共享空间V1.m，topi代表第i个栈( i =1,2)栈顶，栈1的底在v1，栈2的底在Vm，则栈满的条件是（ ）。A. |top2-top1|=0 B. top1+1=top2C. top1+top2=m D. top1=top2,62,队列的特性：先进先出（FIFO）,10. 某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）A：bacde B：dbaceC：dbcae D：ecbad,63,11已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。A. dacb B. cadb C. dbca D. bdacE. 以上答案都不对,64,12若以1234 作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。A. 1234 B. 4132 C. 4231 D. 4213,65,13. 设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag，则栈S的容量至少是 A)1 B)2 C)3 D)4,66,14.向一个带头结点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-next,67,15.一个循环队列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 +1,68,16.循环队列用数组A0.m-1存放其元素值，已知其头尾指针分别为front和rear，则当前元素个数为（ ）。A(rear front + m) mod mBrear - front+1 C(front rear + m) mod mDrear - front,69,17.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和5 B. 2和4 C. 4和2 D. 5和1,70,18用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。A. 仅修改队头指针B. 仅修改队尾指针C. 队头、队尾指针都要修改D. 队头, 队尾指针都可能要修改,71,参考答案,1、BCCDD6、DDBBC11、ECCBC16、ABD,你的问题？,Thanks！,数据结构（C语言版）第5章 数组和广义表,计算机与信息工程学院于江德,74,二维数组的特点：,2个下标，每个元素ai,j受到两个关系（行关系和列关系）的约束：,一个mn的二维数组可以看成是m行的一维数组，或者n列的一维数组。,N维数组的特点：,n个下标，每个元素受到n个关系约束,一个n维数组可以看成是由若干个n1维数组组成的线性表。,75,数组的顺序存储,二维数组Amn按行优先寻址计算方法，每个数组元素占据d个地址单元。设数组的基址为LOC(a11)：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*d设数组的基址为LOC(a00)：LOC(aij)=LOC(a00)+( i*n+j )*d,76,数组的顺序存储,二维数组Amn按列优先寻址计算方法，每个数组元素占据d个地址单元。设数组的基址为LOC(a11)：LOC(aij)=LOC(a11)+(j-1)*m+i-1)*d设数组的基址为LOC(a00)：LOC(aij)=LOC(a00)+( j*m+i )*d,77,1. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,8,列下标j=1,2,10。若A按行先存储，元素A8,5的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。A. A8,5 B. A3,10C. A5,8 D. A0,9,78,2. 二维数组N的每个元素占4个存储单元，行下标i的范围从0到4，列下标j的范围从0到5，N按行存储时元素N35的起始地址与N按列存储时元素（）的起始地址相同。A. N24 B. N34C. N35 D. N44,79,5.3.1 特殊矩阵的压缩存储,特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。特殊矩阵的压缩存储主要是针对阶数很高的特殊矩阵。为节省存储空间，对可以不存储的元素，如零元素或对称元素，不再存储。对称矩阵（上三角矩阵、下三角矩阵）三对角矩阵,80,对称矩阵的压缩存储,设有一个 nn 的对称矩阵 A。,在矩阵中，aij = aji该矩阵中数组元素的下标有何特征？,81,为节约存储空间，只存对角线及对角线以上的元素，或者只存对角线及对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。把它们按行存放于一个一维数组 B 中，称之为对称矩阵 A 的压缩存储。数组 B 共有 n + ( n - 1 ) + + 1 = n*(n+1)/2 个元素。,82,上三角矩阵,下三角矩阵,83,下三角矩阵,B a00 a10 a11 a20 a21 a22 a30 a31 a32 an-1n-1,0 1 2 3 4 5 6 7 8 n(n+1)/2-1,若 i j, 数组元素Aij在数组B中的存放位置为 1 + 2 + + i + j = (i + 1)* i / 2 + j,前i行元素总数 第i行第j个元素前元素个数,84,若 i j，数组元素Aij在矩阵的下三角部分，在数组 B 中没有存放。因此，找它的对称元素Aji。 Aji在数组 B 的第 (2*n-j-1) * j / 2 + i 的位置中找到。,87,三对角矩阵的压缩存储,B a00 a01 a10 a11 a12 a21 a22 a23 an-1n-2 an-1n-1,0 1 2 3 4 5 6 7 8 9 10,88,三对角矩阵中除主对角线及在主对角线上 下最临近的两条对角线上的元素外，所有其它元素均为0。总共有3n-2个非零元素。将三对角矩阵A中三条对角线上的元素按行存放在一维数组 B 中，且a00存放于B0。在三条对角线上的元素aij 满足 0 i n-1, i-1 j i+1在一维数组 B 中 Aij 在第 i 行，它前面有 3*i-1 个非零元素, 在本行中第 j 列前面有 j-i+1 个，所以元素 Aij 在 B 中位置为 k = 2*i + j。,89,3. 设n阶方阵是一个上三角矩阵，则需存储的元素个数为（ ）An Bn*nCn*n/2 Dn(n+1)/2,90,4. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85（即该元素下标ij=85）的地址为（ ）。A. 13 B. 33 C. 18 D. 40,91,5. 若对n阶对称矩阵A1.n，1.n以行序为主序方式下将其下三角的元素（包括主对角线上的所有元素）依次存放于一维数组B1.n(n+1)/2中，则在B中确定aij (ileft=NULLB. t-ltag=1 C. t-ltag=1且t-left=NULLD. 以上都不对,106,10. 由权值为9、2、5、7的四个叶子构造一棵哈夫曼树，该树的带权路径长度为（ ）A23 B. 37 C. 44 D. 46,107,11将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度（ ）A4 B5 C6 D7,108,12一个具有1025个结点的二叉树的高h为（ ）.A11 B10 C11至1025之间 D10至1024之间,109,13.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。与森林F对应的二叉树根结点的右子树上的结点个数是（ ）。AN1 BN1+N2CN3 DN2+N3,110,14.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）A5 B6 C7 D8,111,15.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定,112,16.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）A9 B11 C15 D不确定,113,17. 一棵完全二叉树上有1000个结点，其中叶子结点的个数是（ ）A 250 B 500 C254 D505 E以上答案都不对,114,问: 设一棵完全二叉树具有1000个结点，则它有 个叶子结点，有 个度为2的结点，有 个结点只有非空左子树，有 个结点只有非空右子树。,489,488,1,0,由于最后一层叶子数为489个，是奇数，说明有1个结点只有非空左子树；而完全二叉树中不可能出现只有非空右子树的结点(0个)。,答：易求出总层数和末层叶子数。总层数k=log2n1 =10;且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的)所以末层叶子数为1000-511=489个。,115,请注意叶子结点总数末层叶子数！还应当加上第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/2244个）。所以，全部2度结点数为255(k-2层)244(k-1层)=499个；总叶子数2度结点数1=500个。,第i层上的满结点数为2i-1,所以，全部叶子数489(末层)11(k-1层)=500个。 度为2的结点叶子总数1=499个。,116,18设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-118有n 个叶子的哈夫曼树的结点总数为( ) A不确定 B2n C2n+1 D2n-1,117,19.有关二叉树下列说法正确的是（ ）A二叉树的度为2B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2D二叉树中任何一个结点的度都为2,118,20.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A2h B2h-1 C2h+1 Dh+1,119,21.一棵树高为K的完全二叉树至少有（ ）个结点A2k 1 B. 2k-1 1C. 2k-1 D. 2k,120,22.对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。A先序 B. 中序C. 后序 D. 从根开始按层次遍历,121,23.树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列C. 后序序列,122,24.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。A前序 B中序 C后序 D按层次,123,25.在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）A都不相同 B完全相同C先序和中序相同，而与后序不同D中序和后序相同，而与先序不同,124,26.若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A.X的双亲 B.X的右子树中最左的结点 C.X的左子树中最右结点 D.X的左子树中最右叶结点,125,27.引入二叉线索树的目的是（ ）A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一,126,28. n个结点的线索二叉树上含有的线索数为（ ）A2n Bnl Cnl Dn,127,29.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ ）个。A n-1 Bn C n+1 D n+2,128,30.一棵有n个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组A1.n中，则二叉树中第i个结点（i从1开始用上述方法编号）的右孩子在数组A中的位置是（ ）AA2i(2i=n) BA2i+1(2i+1=n) CAi-2 D条件不充分，无法确定,129,31.设一棵完全二叉树具有1000个结点，则它有（ ）个度为2的结点。A488 B489C499 D500,130,参考答案,1、ADCCB（5、C）6、CBCBC11、CCDDA16、BBDBB21、CCBCB26、CACCD31、C,你的问题？,Thanks！,数据结构（C语言版）第7章 图,计算机与信息工程学院于江德,133,图结构,图的定义基本术语ADT定义图的遍历：,邻接矩阵,邻接表,存储结构,逻辑结构,完全图度、入度、出度权、网路径、回路连通图、强连通图生成树,最小生成树,最短路径,重要应用,拓扑排序,关键路径,134,1. 有n个结点的无向图的边数最多为（ ）An+1 Bn(n-1)/2 Cn(n+1) D2n(n+1),135,2. 无向图中一个顶点的度是指图中（ ）A通过该顶点的简单路径数B通过该顶点的回路数C与该顶点相关联的边的数目D与该顶点连通的顶点数,136,2. 无向图中一个顶点的度是指图中（ ）A通过该顶点的简单路径数B通过该顶点的回路数C与该顶点相邻接的顶点数D与该顶点连通的顶点数,137,3. 在一个图中，所有顶点的度数之和与图的边数的比是（ ）A1:2 B1:1 C2:1 D4:1,138,4. 在无向图中定义顶点Vi与Vj之间的路径为从Vi到达Vj的一个（ ）。A顶点序列 B边序列C权值总和 D边的条数,139,5. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ ）条边。An B. n+1 C. n-1 D. n/2,140,6. 若G是一个具有36条边的非连通无向图（不含自回路和多重边），则图G至少有（ ）个顶点。A11 B. 10C. 9 D. 8,141,7. 下列哪一种图的邻接矩阵是对称矩阵？（）A. 有向图 B. 无向图C. AOV网 D. AO