最终版：三级数据结构讲义(王娟).doc

江苏省等级考试三级辅导材料-数据结构数据结构一、 算法及其描述1. 一个算法应该具有以下五个重要的特征：1) 有穷性：一个算法必须保证执行有限步之后结束；算法和程序的区别：程序不要求有穷性（操作系统）2) 确定性： 算法的每一步骤必须有确切的定义； 3) 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成； 4) 输入：一个算法有0个或多个输入； 5) 输出：一个算法有一个或多个输出。09春 16下列有关算法的描述中，错误的是_。A. 算法可以没有输入B. 算法至少有一个输出C. 一个算法的优劣由算法的时间复杂度惟一决定D. 一个算法的时间复杂度为O(an)(a1，n是问题规模的量)，则这个算法没有实际使用意义09秋 16算法有穷性的含义是_。A. 算法执行的步数和时间都是有限的B. 算法所处理的数据量是有限的C. 算法程序的长度是有限的D. 算法只能被有限的用户使用2. 算法分析计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。我们重点掌握时间复杂度。时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），T（n）=O（f（n）。具体在以后的程序算法介绍过程中详细分析。时间复杂度通常取n 趋向于无穷大时的主项（即增长速度最快的一项），不包括系数。08 春 12设n为问题规模的量，以下所表示的算法时间复杂度中，当T（n）为_时，随着n增大T（n）增长很快，我们称其对应的算法为无效算法。A. O（log2n）B. O（nlog2n）C. O（2n）D. O（n2）3. 数据、数据元素和数据项数据：是指所有能输入到计算机中并被计算机程序处理的符号的总称。是计算机加工的“原料”。数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据项：有时，一个数据元素可由多个数据项组成。数据项是数据的不可分割的最小单位。举例08秋 20以下有关数据的论述中，正确的是_。A. 数据是能被计算机识别、存储和处理的符号的集合B. 数据元素是数据的不可分割的最小单位C. 数据项是数据的基本单位D. 数据由若干个数据项构成，通常将数据项作为一个整体进行考虑和处理4. 数据结构数据结构的形式定义：数据结构是一个二元组Data_Structure=(D, S)其中，D 是数据元素的有限集， S 是D上关系的有限集。逻辑结构：集合、线性、树形、图或网状09秋 20抽象地反映数据元素之间在结构上的约束关系并不考虑其在计算机中的存储方式，称为数据的_。A.逻辑结构B.层次结构C.物理结构D.存储结构存储结构：顺序、链接、索引、散列08春 16在数据结构中，数据的运算_。A. 效率与采用何种存储结构有关B. 是根据存储结构来定义的C. 分为算术运算和关系运算两大类D. 必须用高级程序设计语言来描述09春 20下列有关数据结构的叙述中，正确的是_。A. 线性表、栈和队列的顺序存储结构及其操作是一致的B. 数组以行序为主序排列时元素下标排列次序的变化为：先变化最右边的下标，从右向左，最后变化最左边的下标C. 非空二叉树中每个结点有且只有一个双亲D. 图的遍历算法中增设一个访问数组用于存放顶点的数据二、 线性表1. 线性表是由n个具有相同特性的数据元素组成的线性序列。09秋 21下列关于线性表的叙述中，正确的是_。A. 同一表中的元素必须相同类型，不同表中的元素必须相同类型B. 同一表中的元素可以不同类型，不同表中的元素必须相同类型C. 同一表中的元素必须相同类型，不同表中的元素可以不同类型D. 同一表中的元素可以不同类型，不同表中的元素可以不同类型2. 逻辑结构：线性结构3. 存储结构：顺序存储结构/链式存储结构顺序存储结构的线性表需要一组连续的存储单元依次存储元素，因此知道存储的起始地址以及每个元素所占空间即可求出第I个元素的存储地址，而链式存储结构的线性表则无需连续空间，因此也无法计算其地址；链式存储结构的线性表进行插入、删除等运算时不需要移动其他结点，而顺序存储结构的线性表则不然；10春 20以下有关存储结构的叙述中，错误的是_。A. 存储结构是数据结构在计算机存储器中的表示B. 顺序存储结构是指数据已按其关键字升序（或降序）排好序的存储结构C. 链式存储结构线性表在插入、删除等操作方面比顺序存储更简单D. 顺序存储结构线性表在存取元素方面比链式存储更快捷4. 顺序存储结构的线性表的运算插入、删除以及其算法分析5. 线性链表的运算插入、删除以及两链表合并07秋 18指针h指向非空带表头结点的循环链表，h指向结点的指针域用h-next（即h.next）表示，p为指向链表中任一结点的指针。若h-next=p（即h.next=p）,则表示p指向_。A.表头结点B.链表第1个结点C.链表第2个结点D.链表尾结点08春 18设单链表中指针P指向结点A，若要删除A后面的一个结点（已存在，）则需要修改指针的操作为_(、功能相同)。 类程序设计语言描述形式p所指结点的指针域用p.next表示，“”为赋值号。A. p.next p.next.nextB. p p.nextC. p p.next.nextD. p.next pC语言描述形式P所指结点的指针域用pnext表示。A. p-next = p-next-nextB. p = p-nextC. p = p-next-nextD. p-next = p08秋 16在长度为n的线性表中，删除数据域值为x的元素，查找该元素采用线性查找法，若表中各个位置上删除元素的概率都相同，则删除算法的时间复杂度为_。A.O（n）B.O（2n ）C.O(n2n)D.O(n2) 09春 22某线性链表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则下列存储结构中，采用_最节省操作时间。A.仅有头指针的循环单链表B.仅有头指针的非循环单链表C.有尾指针的循环单链表D.带表头结点的双向循环链表 08秋 76delmax1和delmax2分别是用类程序设计语言和C+语言描述的，删除带表头结点的单链表lk中数据域值最大的结点的算法。链表中的结点node包括一个整型数据域data和一个指向后继结点的指针域next，如图2所示。lkdatanextnode图2 链表结点请选择一种算法描述形式，在算法中的空格处填入正确内容并回答问题（、任选一题，只能选做一题）。类程序设计语言描述形式（略）C+语言描述形式p指向的结点的数据域用p-data表示、指针域用p-next表示。算法中，NULL为空指针。Algorithm delmax2(lk)/lk为单链表的头指针/m为整型量/p，q，r为辅助指针 r=lk; p=lk-next; if (p!=NULL) m=p-data; (20) ;p=p-next;while (p!=NULl) if ( (21) ) m=p-data; (22) q=p;p=p-next q=r-next; (23) ; delete(q); 回答以下问题：（24）该算法中的r变量最终指向数据域值最大结点的 (24) （前驱结点或后继结点）。（25）若算法中的链表是循环单链表，则程序中的“p!=NULL”这个条件应改为 (25) 。（26）设lk单链表中的结点数据域值依次为3，1，7，5，4，则程序执行结束时，m= (26) 。10秋 22设h指向带表头结点的循环链表，h=（a1，a2，a3），p指向循环链表中的一个结点。若p-next-next= a1(“=”为等于关系运算符)，则p是指向_的指针。其中，p指向结点的指针域用p-next表示。A. 表头结点B. 数据域值为a1的结点C. 数据域值为a2的结点D. 数据域值为a3的结点6. 双向链表结构：插入：删除：09秋 76函数insertdl1和insertdl2分别是用类程序设计语言和C+语言描述的算法。其功能是在dl指向的带表头结点双向循环链表中，将数据域值为x的新结点插在数据域值为ai的结点之前，并返回插入位置i值，如果表中数据域值为ai的结点不存在，则返回值i为0。链表结点如图2所示，结点类型为dnode，数据域data为整型，前、后链域分别为prior和next。 dlpriordataNextdnode图2 双向链表结点请选择一种算法描述形式，在算法中的空格处填入正确内容并回答问题（、任选一题，只能选做一题）。 类程序设计语言描述形式（略） C+语句描述形式符号&开头的参数为引用参数。dl指向链表结点的数据域用dl-data表示，前、后链域分别用dl-prior、dl-next表示。算法中，NULL为空指针。Algorithm insertdl2(&dl,ai,x)/insertdl2函数的类型为整型/dl为指向双向循环链表的头指针/ai，x为双向循环链表结点数据域类型/i为整型/p，s为辅助指针p = dl;i = 0;while ( （20） & p-next-data!=ai)p = p-next; （21） if (p-next-data=ai)s=new dnode; （22） ;s-next=p-next; （23） ;s-prior=p;p-next=s;+i;else i=0;return i;回答以下问题：（24）设dl指向的双向循环链表为非空表，链表第一个结点数据域在算法描述时应表示为 （24） 。（25）设dl=（18，45，36，27），ai=36，x=90，上述算法执行后，dl=（ （25） ）。（26）上述算法中若数据域值为ai的结点存在，则指针s指向的结点位于指针p指向的结点 （26） （之前/之后）。10春22设h是指向链表的头指针，链表中第1个结点数据域值为a1， p是指向链尾结点的指针。h指向结点的数据域用h-data（即h.data）表示，指针域用h-next（即h.next）表示。若h-next-data= a1（即h.next.data= a1），h=p-next（即h=p.next），则该链表是_。A. 带表头结点的单链表B. 带表头结点的循环链表C. 不带表头结点的单链表D. 不带表头结点的循环链表三、 数组1. 由于数组一般不作插入或删除操作因此，一般采用顺序存储结构表示数组。数组可看成是一个定长的线性表，其元素也是一个定长的线性表。2. 逻辑结构：线性结构3. 存储结构：顺序存储结构4. 数组存储位置的计算以行为主序以列为主序07秋 19二维数组A（元素为A00A78）按行优先方式存储，若数组元素A24的存储地址为1090，A46的存储地址为1150，则数组元素A67的存储地址为_。A. 1204B. 1207C. 1209D. 121108春 19设有二维数组Ab1b2，若以行为主序存储时元素Aij的存储地址为D，以列为主序存储时存储地址也等于D的元素为Arowcol，则row、col值的计算公式分别为_。（其中：运算符“/”为整除符，即div；运算符“%”为取余符，即mod）。A. (b1*j+i)/b2,(b1*j+i)%b2B. (b1*j+i)%b2, (b1*j+i)/b2C. (b2*i+j)/b1,(b2*i+j)%b1D. (b2*i+j)%b1, (b2*i+j)/b108秋 23二维数组A的元素存放在A00A810中，每个元素占5个字节，若按列优先次序存储，起始地址为1000，则存储元素A55的起始地址是_。A.1250B.1300C.1255D.130509春 23设二维数组B的元素存放在B00B919中，每个元素占L个存储单元，则B按列优先次序存放时元素B66的地址与B按行优先次序存放时元素_的地址相同。A.B35B. B36C. B53D. B6609秋 23将下三角矩阵的非零元素按行优先顺序依次存储在一维数组B1.m中，其中，m=n(n+1)/2，则非零元素（1jin）在B数组中的元素下标是_。A.i*(i+1)/2+jB.i*(i+1)/2+(j-1)C.i*(i-1)/2+jD.i*(i-1)/2+(j-1)10春 23二维数组A的元素存放在A00A97中，起始地址为LOC，若以行优先次序存储，元素A36的起始地址为LOC+60L，则以列优先次序存储时，地址为LOC+86L的元素是_。A.A24B. A34C. A43D.A5310秋 23二维数组A存储在A00A79中，起始存储地址为LOC，数组元素A25的存储地址为LOC+168，下列关于数组A及元素的叙述中，正确的是_。A. 数组A以行为主序B. 每个元素占2个存储单元的空间C. 数组元素A43的存储地址为LOC+112D. 存储地址为LOC+80的元素为A205. 稀疏矩阵（三元组表）四、 栈1. 栈是一种特殊的表，这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。2. 逻辑结构：线性结构3. 存储结构：顺序存储结构/链式存储结构4. 栈的运算（顺序存储结构/链式存储结构）：栈空的判别条件进栈、出栈共享栈07秋 76 算法convert1和convert2分别是用类程序设计语言和C+语言描述的、将顺序结构栈s转换为链式结构栈（即链栈）sp，并输出栈中元素个数的算法。链栈结点如图1所示，其中，结点类型为node，data为数据域，next为指针域。datanextspnode图1 链栈结点算法中，可直接调用的算法及其功能说明如下：getnum(s)取s栈元素个数函数（整型）empty(s)判s栈空函数pop(s,&x)s栈元素出栈，由x返回请选择一种算法描述形式，在算法中的空格处填入正确内容并回答问题（、任选一题，只能选做一题）。 类程序设计语言描述形式（略） C+语言描述形式符号&开头的参数为引用参数。sp指向结点的数据域用sp-data表示、指针域用sp-next表示。算法中，NULL为空指针。Algorithm convert2(s,&sp)/s为顺序结构栈/sp为链栈栈顶指针/n为整型量/x为s栈的元素类型/p为辅助指针n = (19) ; if (n) sp = new node;pop(s,x);sp-data = x; (20) ;while (!empty(s)p-next = new node;pop(s,x); (21) ;p-data = x; (22) ;else sp = NULL;cout “n = ” n 0时进行入队操作5. 环形队列（front总是指向对头元素的前一个位置，队满时环形队列中仍有一元素空位，由front指示着！）队列空的判别条件：cq.front=cq.rear队列满的判别条件：cq.front=(cq.rear+1) mod (max+1)入队出队08春 17用一个大小为6的一维数组来实现环形队列，设当前队尾rear和对头front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是_。A.1和5B.2和4C.4和2D.5和109春 21环形队列用a0.m-1存放其元素值，设front指向队头元素的前一个位置，rear指向队尾元素，则当前队列中有_个元素。A.(rear-front+m)%mB.(rear-front+1)%mC.rear-front-1D.rear-front09秋 22设有环形队列cq，其队列元素空间表示为cq.e0cq.emax，cq.front指向队头元素的前一个位置，cq.rear指向队尾元素位置，则队列满的判断条件是_，其中m=max+1，“=”为等于关系运算符，%（即mod）为取余运算符。A.cq.front = cq.rearB.cq.rear+1 = mC.(cq.front+1) % m = cq.rearD.(cq.rear+1) % m =cq.front6. 链队列08秋 22qp链队列结构中包括队头指针front和队尾指针rear两个域，分别用qp.front和qp.rear表示，qp为带表头结点的链队列，元素结点指针域为next。如果qp.front-next=qp.rear(或qp.front.next=qp.rear)，则表示_。A.链队列空B.链队列满C.链队列中只有一个结点D.链队列元素首尾相连接六、 树1. 树是具有相同特性的n个结点的有限集，有且仅有1个根结点，其余结点分为m个互不相交的集合，每个集合本身也是树，称为根的子树。2. 基本术语1) 结点的度：结点的子树个数（即分枝数目）2) 树的度：树中结点的最大度3) 叶子和分支结点：度为0的结点称为叶子（或终端结点），度不为0的结点称为分支结点（或非终端结点）4) 双亲与孩子：结点的子树的根称为结点的孩子，该结点称为孩子的双亲5) 兄弟：同一双亲的子女互称兄弟，其父母为兄弟的结点互称堂兄6) 结点的层数：根为第一层，根的孩子为第二层，以此类推7) 树的深度：树中结点的最大层数称为树的深度（或高度）8) 有序树：结点的子树从左到右有顺序，不能互换，否则，称为无序树9) 森林：不相交的树的集合，除去根结点后的子树集合就是森林3. 二叉树1) 二叉树T是有限个结点的集合，它或者是空集，或者由一个根结点u以及分别称为左子树和右子树的两棵互不相交的二叉树u(1)和u(2)组成。2) 满二叉树、完全二叉树3) 几个重要性质 n0=n2+1； 根为第1层，则第i层最多有2i-1个结点； 深度为k的二叉树至多有2k -1个结点07秋 20结点总数为n的完全二叉树中，其叶结点数为_。其中，运算符“/”为整除符。A. n/2B. (n-1)/2C. (n+1)/2D. (n-2)/208春 20有关二叉树的下列说法中，正确的是_。A. 二叉树的度为2B. 二叉树的度可以小于2C. 二叉树中至少有一个结点的度为2D. 二叉树中任何一个结点的度都为208春 21一棵满二叉树，若共有n个结点和m个叶子结点，则_。A. n=2m-2B. n=2m-1C. n=2mD. n=2m+108秋 25具有10个叶结点的二叉树中有_个度为2的结点。A.8B.9C.10D.1109秋 24结点数为n的满二叉树其层数为_（二叉树层数从1开始）。A.log2nB.log2n+1C.log2(n-1)D.log2(n+1)10秋 24设n个结点的二叉树T仅有度为0和度为2的结点，则T有_个叶子结点。A.(n-1)/2B.n/2C.(n+1)/2D.无法确定4) 逻辑结构：树形结构5) 存储结构：通常用链式结构6) 二叉树的遍历： 先序遍历 中序遍历 后序遍历 层序遍历07秋 21在任意一棵二叉树的先序序列和后序序列中，各叶子之间的相对次序关系_。 A. 不一定相同B. 都相同C.都不相同D. 互为逆序lchilddatarchildptr08春 76已知一个具有n个结点的二叉树的先序序列和中序序列分别存放于字符指针（字符串）ppos和ipos所指示的空间中（设该二叉树各结点的数据值均不相同）。下面是分别用类程序设计语言和C+语言描述的算法（函数）ctree1和ctree2，其功能是由一棵二叉树的先序序列和中序序列构造该二叉树。假设二叉树的结点结构如图1所示：图1 二叉树结点其中，ptr为指向二叉树结点的指针，data是字符型数据，存放结点值，lchild和rchild为分别指向左子树和右子树的指针域。函数调用方式为ptrctree1（ppos，ipos，n）或ptr=ctree2（ppos，ipos，n）。请选择一种算法描述形式，在算法中的空格处填入正确内容并回答问题（、任选一题，只能选做一题）。 类程序设计语言描述形式（略） C+语言描述形式算法中，btree为二叉树的结点的类型名。ptr指向结点的数据域用ptr-data表示，两个指针域分别用ptr-lchild、ptr-rchild表示。Algorithm ctree2(ppos,ipos,n)/函数返回值为指向二叉树根结点的指针/ppos为字符指针，指向二叉树的先序序列/ipos为字符指针，指向二叉树的中序序列/n为整型，是二叉树的结点个数/ptr为指向二叉树结点的指针/rpos，pp，ip为字符指针/k为整型/malloc为向系统申请空间的库函数/if ( (19) )return NULL;elseptr = new btree; (20) ;for (rpos = ipos; rposlchild = ctree2(pp,ip,k);pp = ppos+1+k;ip = (22) ;ptr-rchild = ctree2(pp,ip,n-1-k);return ptr;回答以下问题：（23）算法中，for语句的作用是找出 (23) 结点在中序遍历序列中的位置。（24）如果上述算法中ppos中的值为“ABDEHCFGI”，ipos中的值为“DBEHAFCIG”，则执行上述算法所构造出的二叉树（ptr）中叶子结点的个数为 (24) 。（25）后序遍历（24）中的二叉树，其结果序列的第一个和最后一个结点分别是 (25) 。（26）根据一棵二叉树的先序遍历序列和后序遍历序列（能、不能） (26) 惟一地确定这棵二叉树。08秋 24在同一棵二叉树遍历的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序_。A.仅先序和中序相同B.仅中序和后序相同C.都相同D.都不相同09春 25二叉树的先序遍历序列为efhigjk，中序遍历序列为hfiejkg。该二叉树根的右子树的根是： _。A.eB.fC.gD.h09秋 25某完全二叉树采用顺序存储结构，结点数据的存放顺序依次为A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为_。A.HDEBFGCAB.HEDBGFCAC.HDBEAFCGD.HDEFGBCA10春 25二叉树的遍历方法主要有先序遍历、中序遍历、后序遍历和层次遍历。下列有关二叉树遍历的叙述中，对于任意二叉树都正确的是_。A.先序遍历的第一个结点必是后序遍历的第一个结点B.中序遍历的第一个结点必是后序遍历的第一个结点C.先序遍历的第一个结点必是层次遍历的第一个结点D.中序遍历的第一个结点必是层次遍历的第一个结点10春76下面分别是用类程序设计语言和C+语言描述的算法count1和count2，其功能是通过二叉树的先序遍历，求指针bt指向二叉树的总结点数n、度为0的结点数n0、度为1的结点数n1和度为2的结点数n2。llinkdatarlinkbt二叉树结点如图所示，其中，data为数据域，llink、rlink分别为左、右指针域。图 二叉树结点请选择一种算法描述形式，在算法中的空格处填入正确内容并回答问题（、任选一题，只能选做一题）。 类程序设计语言描述形式（略） C+语言描述形式符号&开头的参数为引用参数。bt指向二叉树结点的数据域用bt-data表示，左、右指针域分别用bt-llink、bt-rlink表示。Algorithm pre2(bt,&n,&n2)/bt为指向二叉树根结点的指针/n，n2为整型 if (bt) if (bt-llink & 20 )+n2; 21 ;pre2(bt-llink,n,n2);pre2(bt-rlink,n,n2);Algorithm count2(bt,&n,&n0,&n1,&n2)/bt为指向二叉树根结点的指针/n,n0,n1,n2为整型 n=0; 22 ;pre2(bt,n,n2);if (n0) 23 ;else n0=0;n1=n-n0-n2;回答以下问题：(24)、(25)设先序遍历bt指向二叉树的结点序列为ABE.CD.F.，其中“.”表示空域，执行上述算法程序后，n= 24 ，n0= 25 。(26) 上述算法中，调用的先序遍历过程pre2 26 （可以/不可以）改为后序遍历过程来求二叉树中的n、n2结点数。10秋25设二叉树的先序遍历序列为ABCDEFG，中序遍历序列为BADCFEG，则该二叉树根的左子树有_个结点。A.1B.2C.3D.510秋76下面分别是用类程序设计语言和C+语言描述的算法insert1(由算法pre1调用)和insert2(由算法pre2调用)，其功能是通过二叉树的先序遍历，在数据域值等于d(二叉树中结点数据域值均不等)的叶结点的左子树中插入数据域值等于x的新结点，返回并输出x结点在二叉树中的层数lev。llinkdatarlinkbt二叉树结点如图2所示，bnode为二叉树结点类型，其中data为数据域，llink、rlink分别为指向左、右子树的指针域。图2 二叉树结点bnode请选择一种算法描述形式，在算法中的空格处填入正确内容并回答问题（、任选一题，只能选做一题） 类程序设计语言描述形式（略） C+语言描述形式符号&开头的参数为引用参数。bt指向二叉树结点的数据域用bt-data表示，左、右子树指针域分别用bt-llink、bt-rlink表示。Algorithm insert2(bt,d,x,&lev,&i)/bt为指向二叉树根结点的指针/d,x为结点数据域类型/lev,i为整型/p为辅助指针if(bt)+i;if( 20 & !bt-rlink & bt-data=d)bt-llink=new bnode;p=bt-llink; 21 ;p-llink=NULL;p-rlink=NULL;lev= 22 ;insert2(bt-llink,d,x,lev,i);insert2(bt-rlink,d,x,lev,i);-i;Algorithm pre2(bt,d,x)/bt为指向二叉树根结点的指针/d,x为结点数据域类型/lev,i为整型 lev=0; 23 ;insert2(bt,d,x,lev,i);if(lev)cout”lev=”lev二叉树子女为左，兄弟为右10春24森林F中有T1、T2和T3三棵树，它们的结点数分别为t1、t2和t3，按上述次序将森林F转换成二叉树BT存储，则BT的右子树的结点数为_。A.t2+t3B.t2+t3-1C.t1+t2D.t1+t2-15. 树二叉树09春24指针t指向的树转换为指针bt指向的二叉树，则下列叙述中正确的是_。（1）t树与bt树结点数相等（2）t树与bt树的存储结构相同（3）t树与bt树的层数相等（4）bt树的右子树必定为空A.（1）、（2）B.（1）、（3）C.（1）、（4）D.（2）、（3）、（4）七、 图1. 图的定义：1) 图是网状关系的数据结构，其数据元素之间的关系是可以任意的，任意两个元素之间都可能相关。2) 无向图：图中顶点之间的偶对是无序对; 有向图：图中顶点之间的偶对是有序对2. 图的基本术语：1) 用n表示图中顶点数目，e表示边或弧的数目，一个有n个顶点、n(n-1)/2条边的无向图称为无向完全图，一个有n个顶点、n(n-1)条弧的有向图称为有向完全图。2) 无向图 度：与该顶点相连的边的数目称为顶点的度；有向图 入度：以该顶点为终点的弧的数目称为该顶点的入度 出度：以该顶点为始点的弧的数目称为该顶点的入度3) 连通图：无向图中任意两个顶点都是连通的 强连通图：有向图中任意两个顶点都是连通的09秋 26具有n个顶点的图G，顶点间的连线（边或弧）数为n(n-1)，则图G是_。A. 有向完全图B.有向非完全图C.无向完全图D.无向非完全图10春 26在具有n(n1)个顶点的无向图中，每个顶点度的最大值为_。A. n-1B.2(n-1)C.n(n-1)/2D.n(n-1)3. 图的存储：1) 邻接矩阵：表示图中顶点间相邻关系的矩阵。2) 邻接表：图的一种链式存储结构。无向图只需形成一个邻接表，有向图需要一个邻接表和一个逆邻接表。07秋22设有向图G的二元组定义如下：G=(V,A)其中，V=v1,v2,v3,v4 A=,则以下叙述中，正确的是_。A.顶点v1的入度为2B.顶点v2的出度为1C.顶点v3和顶点v4的弧数为3D.G的强连通分量数为208春 22 对无向图的邻接矩阵来说，_。A.第i行上的非零元素个数和第i列上的非零元素个数一定相等B.非零元素个数等于图中的边数C.第i行上和第i列上的非零元素个数的总数等于顶点vi的度数D.矩阵中非全零行的行数等于图中的顶点数08秋 26n个顶点连通无向图的邻接矩阵中至少有_个非0元素。A.n-1B.2(n-1)C.n(n-1)/2D.n(n-1)10秋 26若有向图G用邻接矩阵来存储（0表示顶点间无弧连接，1表示顶点间有弧连接），则该邻接矩阵的第i行元素的和_。A.仅表示第i个顶点的出度B.仅表示第i个顶点的入度C.表示第i个顶点的度D.既表示第i个顶点的出度，也表示第i个顶点的入度4. 图的遍历：图的遍历就是从图中某一顶点出发，访问图中所有顶点，且使每个顶点只被访问一次的过程。1) 深度优先搜索（类似于树的先根遍历）09春 26无向图g=(v,e)，其中：v=a,b,c,d,e,f，e=(a,b),(a,c),(a,e),(b,e),(c,f),(d,e), (d,f)，采用邻接矩阵存储结构，按顶点字母先后次序存储，从顶点a出发，对该图进行深度优先搜索，得到的顶点序列是_。A.a,b,e,d,f,cB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b2) 广度优先搜索（类似于层次遍历）八、 查找1. 线性查找（顺序查找）1) 方法：查找时，用给定的关键字值从表的一端开始，依次逐个与表中元素的关键字值进行比较，如果找到其关键字与给定值相等的元素，则查找成功；否则表中所有元素的关键字与给定值比较都不等，则查找不成功。2) 性能分析：对含有n个记录的线性表，记录的查找在等概率的前提下，查找成功的平均查找长度ASL成功（n+1）/2；查找不成功的比较次数为n+1。2. 对半查找（二分查找）若查找表中元素按关键字有序，并采用顺序存储结构进行存储，可采用折半查找方法进行查找。1) 方法：首先将要查找的给定值k与中间位置的记录关键字进行比较，这个中间记录将查找表分成两个区间，如果比较结果相等则查找成功；若不相等，再根据k与中间记录关键字的比较结果确定下一步在哪个区间查找，这样逐步缩小区间，直到查找成功或该表中没有这样的元素为止。2) 性能分析：设表长n=2h 1 ,则 h=log2(n+1) ,其中h为最大对半次数。又设表中每个元素的查找概率都相同，则对半查找的平均查找长度为 ，n50时，近似为log2(n+1)-1。08春23对有13个元素的有序表1，3，9，12，32，41，45，62，75，77，82，95，100作折半查找，当查找值为82的元素时，须经过_次比较后查找成功。A4B3C2D110春27用对半查找方法对序列(13，24，33，41，52，63，79，88，90)进行查找，则需比较2次可查找成功的元素有_个。A1B2C4D83. 分块查找（索引线性查找）建立一个分块表，存放被查找的元素，表中分成若干块（也称为子表），块与块之间的元素按关键字有序，块内元素的存放顺序是任意的。1) 方法：首先确定待查关键字所在的块（子表），此时可采用顺序查找/折半查找方法，然后再在已确定的块内进行顺序查找。2) 性能分析：分块查找的平均查找长度=查找索引表的平均查找长度+块内查找的平均查找长度假设长度为n的表均匀地分为b块，每块中的记录个数有s个，又设每个元素的查找概率都相等，块间块内均采用线性查找方法，则分块查找的平均查找长度为，若取s=,则为平均查找长度最小值+107秋23分块查找需要建立一个分块表和一个索引表，分块表分成若干个块，表中元素关键字的排列要求是_。A.块间无序、块内无序B.块间无序、块内有序C.块间有序、块内无序D.块间有序、块内有序08秋 27设分块查找中分块表每个元素的查找概率都相等，块内块间均采用线性查找方法，若分块表中共有1600个元素，则最小的平均查找长度为_。A.41B.40C.39D.2810秋 27分块查找（索引线性查找）存储结构的索引表中，通常包含两个数据域，存放这一块中的_。A. 最大关键字值、块中元素的个数B. 最大关键字值、第一个元素的位置值C. 最小关键字值、块中元素的个数D. 最小关键字值、中间元素的位置值4. 三种查找方法的比较从查找成功时的平均查找长度来看，线性查找速度最慢，对半查找速度最快，分块查找介于两者之间。从查找不成功时和给定值比较的关键字个数的最大值来看，线性查找为n+1，对半查找为，分块查找为b+s+2（块间、块内均采用线性查找）5. 散列查找散列法也称哈希法。这种方法由元素的关键字通过某种函数计算出对应的函数值，作为元素的存储位置，这个函数称为散列函数。查找时，按照上述同样的过程，由给定的关键字计算得到的存储位置，然后到相应单元中查找元素。用这种方法建立的结构称为散列表，也称为哈希表，用散列函数求得元素在表中的存储位置称为散列地址。这是一种重要的存储方式，由此形成的查找方法称为散列查找。一般情况下，关键字集合比散列表中的存储位置的数目要来得大，因此很有可能出现由两个不用的关键字计算得到的散列函数值相等。如不同的关键字KEY1和KEY2，它们的散列函数值相等，