数据结构复习题1--和答案

1、说明：此复习题为复习专用，其给定了期末考试的主要范围，并非给定考试原题，考试时相关的题目基本都要进行改动。因此同学们请注意，不要去背答案，要将题理解并做会。（请注意这决不是原题，只有弄会才可能通过）第1章 绪 论1、数据结构主要研究的三个内容为 、 以及定义在该结构上的 。2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于 。3、数据结构被形式地定义为（D，R），其中D是 的有限集，R是D上的 有限集。4、数据的结构在计算机内存中的表示是指（ ）A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系5、给出以下给定的两个程序段中划波浪线的语句的执行频度（次

2、数）。（1） sum=0;for(i=0;i<n;i+)for(j=0; j<n; j+) sum+=aij;（2） sum=0;for(i=0;i<n;i+)for(j=0; j<=i; j+) sum+=aij; (3) sum=0; for(i=0;i<n;i+) for(j=0; j<m; j+) sum+=aij;6、分析以下各程序段的时间复杂度为（用大O记号表示）（1） i=s=0; while(s<n) i+; s+=i; （2） i=1; while(i<=n) i=i*3;第2章 线性表1、n(n>=0)个元素的线性结构表

3、示成(a1，a2,an)，a1称为_元素，an称为_元素，i称为ai在线性表中的_。对任意一对相邻结点ai、ai+1(1<=i<n),ai称为ai+1的_，ai+1称为ai的_。2、在表长为n的顺序表的第i个位置插入一元素（1<=i<=n+1，插入的新元素作为第i个元素），则涉及到的元素的移动次数为 ；若删除第i（1<=i<=n）个元素，则涉及到的元素的移动次数为 。3、线性表的顺序存储结构（顺序表）其存储空间 。A) 必须是连续的 B) 部分是连续的C) 一定是不连续的 D) 连续不连续都可以4、一个顺序表的第一个元素的存储地址是100，每个元素的长度为2

4、，则第5个元素的地址是 。A）110 B）108 C）100 D）1205、顺序表的存取特点为 ，单链表的存取特点为 。6、对于顺序表的优缺点，以下说法错误的是（ ） 无需为表示结点间的逻辑关系而增加额外的存储空间 可以方便地随机存取表中的任一结点 插人和删除运算较方便 容易造成一部分空间长期闲置而得不到充分利用7、以下说法正确的是线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低在顺序存储线性表中，插入和删除元素时，移动元素的个数与插入或删除位置有关顺序存储的线性表的插人和删除操作不需要付出很大的代价，

5、因为平均每次操只有近一半的元素需要移动8、以下说法正确的是（ ）顺序存储方式的优点是存储密度大、且插入、删除运算效率高链表的每个结点中都恰好包含一个指针线性表的顺序存储结构优于链式存储结构顺序存储结构属于静态结构，链式结构属于动态结构9、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。顺序表 单链表 双链表 单循环链表10、单链表中，增加头结点的目的是为了 ( )使单链表至少有一个结点 标示表结点中首结点的位置使每个元素都能有前驱结点，从而方便运算的实现说明单链表是线性表的链式存储实现11、对于一单链表L(L为头指针，且结点的后继指针分量为nex

6、t),其p结点（p为链表中某结点的指针）既不是第一个结点，也不是最后一个结点。（1）在p结点后插入s结点(s为某结点的指针)的语句序列是： 【1】 （2）删除p结点的直接后继结点的语句序列是：q=p->next; 【2】 ; free(q);（3）若L为带头结点的单链表，则：a) 在表首插入s结点的语句序列是： 【3】 b) 单链表为空的判定条件为： 【4】 （4）若L为不带头结点的单链表，则：a) 在表首插入s结点的语句序列是： 【5】 b) 单链表为空的判定条件为： 【6】 12、已知L是带表头结点的双向链表(L为头指针，且结点的后继指针分量为next，前驱指针为pre ),其p结点

7、（p为链表中某结点的指针）既不是首元结点，也不是尾元结点。a）在p结点后插入s结点(s为某结点的指针)的语句序列是：s->next=p->next；s->pre= 【1】 ; 【2】 =s; p->next=s;b）在p结点前插入s结点(s为某结点的指针)的语句序列是：s->pre=p->pre;s->next= 【3】 ; 【4】 =s; p->pre=s;c）删除p结点的直接后继结点的语句序列是：q=p->next; p->next= 【5】 ; 【6】 =p; free(q);d) 删除p结点的直接前驱结点的语句序列是：q=p&

8、gt;pre; 【7】 ; 【8】 =p; free(q);e) 删除该p结点语句序列是： 【9】 =p->next; p->next->pre= 【10】 ; free(p);f) 在表首插入s结点的语句序列是：s->next=L->next; 【11】 =L; 【12】 ; L->next=s; 13、设带头结点的单链表类型定义如下： typedef struct LNode Elemtype data; /Elemtype 为数据元素类型 struct Lnode *next; /后继结点的指针 *LinkedList;（1）函数InverseList

9、(L)的作用是将一带头结点的单链表实现就地逆置的算法（即利用原来链表的空间，将单链表中的结点按原来相反的顺序存储）。填写空缺位置，使此该算法完整。InverseList(LinkedList &L) p=L->next; L->next= NULL; while ( p ) q=p->next; 【1】 ; 【2】 ; p=q; （2） MergeList(La, Lb)函数的作用是将两个递增有序的带头结点的单链表La, Lb，利用原来的结点空间，合并成一个递增有序的链表La。填写空缺位置，使此该算法完整。void MergeList (LinkedList &

10、;La, LinkedList &Lb) pa=La->next; pb=Lb->next; s=La; while( 【3】 ) if(pa->data<=pb->data) s->next=pa; s=pa; pa=pa->next; else s->next=pb; s=pb; 【4】 ; if (pa) s->next=pa;else s->next= 【5】 ;free(Lb); （3）函数Search(L,i)用来返回带头结点的单链表L的第i个元素的位置指针。填写空缺位置，使此该算法完整。 LinkedList S

11、earch(LinkedList L, int i) p=L; j= 【6】 ; while( 【7】 ) p=p->next; j+; if( 【8】 ) return p; else return NULL; （4）函数ListLength(L)用来求一带头结点的单链表L的长度。请写出此函数的算法代码。14、函数DeleteElem(int a, int n, int i)的作用为：在一个长度为n的数组中，删除其第i个元素。其中第数组的第一个元素为a0，第二个元素为a1，依次类推。请写出此函数的算法代码。第3章 栈与队列1、栈与队列是二种特殊的线性表，栈其亦称为 ；队列亦称为 。2、

12、现有一个空栈，现有4个元素其入栈顺序为a、b、c、d，则不可能得到了出栈顺序为 。A）a,b,c,d B) d,c,b,a C) c,a,b,d D) a,c,b,d3、现有一个空栈，已知其入栈序列为1, 2, 3, , n，其输出序列为p1, p2, p3, , pn。若p1=n，则pi（1in）为 A）i B) n-i C) n-i+1 D) 不确定4、栈与队列的共同点是 。 A）都是先进后出 B）都是先进先出 C）只允许在端点处插入和删除元素 D) 没有共同点5、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s

13、1,则栈的容量至少应该是（ ） 2 3 5 66、设有一顺序栈已含3个元素（当前栈顶元素为a3），如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（ ） 0 1 2 3 maxsize-1a1a2a3sq a3,a1,a4,a2 a3,a2,a4,a1 a3,a4,a2,a1 a4,a3,a2,a17、一个队列的入列序是1，2，3，4，则队列的输出系列是（ ） 4，3，2，1 1，2，3，4， 1，4，3，2 3，2，4，18、向一个栈顶指针为Top（Top指向栈顶元素）的链中插入一个s所指结点时，其操作步骤为（ ）Top->next=s s->next=T

14、op->next;Top->next=ss->next=Top;Top=s s->next=Top;Top=Top->next9、在一个栈顶指针为Top（Top指向栈顶元素）的链栈中，进行出栈操作，并将被出栈元素的值保存到x中，其操作步骤为（ ）p=Top;x=Top->data;Top=Top->next; free(p); p=Top;Top=Top->next;x=Top->data;free(p);x=Top;Top=Top->next;free(Top); x=Top->data; free(Top);10、对于顺序存

15、储的栈，其类型描述如下：typedef struct ElemType ElemMAX; /*ElemType为栈内元素类型，MAX为一预定义常量，数组Elem的首端为栈底，另一端为栈顶*/ int Top; /*Top指示栈顶位置，其值为下标值*/ SqStack;若Top指示的位置为当前栈顶元素的位置，则栈空的判定条件为： ；若Top指示的位置为当前栈顶元素的下一位置（即入栈位置），则栈空的判定条件为： ；11、阅读下列算法，写出其完整的功能。 #define MAX 100typedef struct LNode DataType data; /DataType 为数据元素类型 stru

16、ct Lnode *next; /后继结点的指针 *LinkedList;void RVList( LinkedList head) DataType SMAX;int top=0; LinkedList p; p=head->next; while(p) Stop+=p->data; p=p->next; p=head->next; while(top) p->data=S-top; p=p-next; 12、以下算法是以顺序存储结构实现一个双向栈（即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点）。以下给出了此双向栈类的定义及此双向栈的初

17、始化操作和入栈操作与出栈的算法。填写空白位置，使此算法完整。（注：双向栈结构如下图所示）高下标处的栈低下标处的栈012iMax-j-1Max-2Max-1a0a1a2aiTop1bjb1b0Top0#define Max 可用最大空间长度；typedef structElemType ElemMax；/*ElemType 为栈内数据元素的类型*/ int Top0,Top1; /*定义两个栈顶位置指针，分别存储两个栈的当前栈顶元素的下标*/ DStack;void inistack(DStack &S )/*双向栈S的初始化操作*/ S.Top0= -1; S.Top1= 【1】 ;

18、Status push(DStack &S, int i ,ElemType e)/*将e入栈；其中i为0或1，i为0表示对设在低下标处的栈进行操作，i为1，表示对设在高下标处的栈进行操作*/ if ( 【2】 ) /*若栈满*/printf("Stack is overflow"); return(ERROR); else if (i=0) S.Elem+S.Top0=e; else 【3】 ; retrun OK;Status pop(DStack &S, int i ,ElemType &e)/*出栈操作，其中i为0或1，i为0表示对设在低下标

19、处的栈进行操作，i为1，表示对设在高下标处的栈进行操作，并通过参数e返回出栈元素的值*/ if (i=0) if( S.Top0=-1 ) return 0; else e=S.ElemS.Top0-; return 1; else if( 【4】 ) return 0; else e= 【5】 ; return 1;13、以下是有关循环队列的类型定义及其有关操作，填写上相应的空白位置。 /*类型描述*/#define MAX 100typedef struct ElemType baseMAX; /*ElemType为元素的数据类型*/ int front; /*头指针，若队列不空，指向队列

20、头元素*/ int rear;/*尾指针，若队列不空，指向队列尾元素的下一个位置*/ SqQueue;/*说明：少用一个元素空间，以区别队列判空和判满条件*/Status InitQueue(SqQueue &Q) /*初始化操作*/ Q.front=Q.rear=0;return OK; Status EnQueue(SqQueue &Q,ElemType e) /* 入队操作*/ if( 【1】 ) return ERROR;/*若队列满，返回出错*/ Q.baseQ.rear=e; Q.rear=(Q.rear+1)% MAX; retrun OK;Status DeQu

21、eue(SqQueue &Q,ElemType &e) /*出队操作*/ if( 【2】 ) return ERROR;/*若队列空，则返回出错*/ e=Q.baseQ.front; Q.front= 【3】 ; 14、若用如下图所示一带头结点的单循环链表来表示队列，并且只设一个指针Q指向队尾结点（注意不设头指针）。以下给出了此队列的类型描述、初始化操作、入队操作和出队操作，在空白处填写上正确答案。a1a2anQ（1）一般的队列形式Q（2）空队列形式typedef struct Lnode /*类型描述*/ ElemType data; /*ElemType为元素的数据类型*/

22、 struct Lnode *next; *CLinkQueue;Status InitQueue(CLinkQueue &Q) /*初始化建立空队列Q,执行成功函数返回OK，否则返回FALSE*/ Q=(CLinkQueue) malloc(sizeof(struct Lnode); if(!Q) return FALSE; Q->next= 【1】 ; return OK;Status EnQueue(CLinkQueue &Q, ElemType e) q=(CLinkQueue)malloc(sizeof(struct Lnode*); if(!q) return

23、 FALSE; q->data=e; q->next=Q->next; Q->next=q; 【2】 ; return OK; Status DeQueue(CLinkQueue &Q, ElemType &e) /*出队操作, 操作成功返回OK，否则返回FALSE*/ if( 【3】 ) return FALSE; /*空队时*/ p=Q->next->next; Q->next->next=p->next;if(p=Q) 【4】 ; e=p->data; free(p); return OK; 15、若用如下图所示

24、一带头结点的单链表来表示队列。以下给出了此队列的类型描述、初始化操作、入队操作和出队操作，在空白处填写上正确答案。a1a2an Qfrontrear（1）一般的队列形式 frontrearQ（2）空队列形式struct qnode /结点类型描述 ElemType data; /ElemType为元素的数据类型 struct qnode *next; ;typedef struct /链队类型描述 struct qnode *front; struct qnode *rear; LinkQueue;Status InitQueue(LinkQueue &Q) /*初始化建立空队列Q,执

25、行成功函数返回OK，否则返回FALSE*/ Q.front=Q.rear=(LinkQueue) malloc(sizeof(struct Lnode); if(!Q.front) return FALSE; 【1】 ; return OK;Status EnQueue(LinkQueue &Q, ElemType e) p=(LinkQueue)malloc(sizeof(struct Lnode*); if(!p) return FALSE; p->data=e; p->next=NULL; 【2】 ; 【3】 ; return OK; Status DeQueue(L

26、inkQueue &Q, ElemType &e) /*出队操作, 操作成功返回OK，否则返回FALSE*/ if( 【4】 ) return FALSE; /*空队时*/ p=Q.front->next; Q.front->next=p->next;if(p=Q.rear) 【5】 ; e=p->data; free(p); return OK; 第6章 树与二叉树1、在一棵含有n个结点的二叉树中，其分支数（边数）为： ；若此二叉树只有度为2的分支结点，和度为0的叶子结点，则该树中叶子结点的数目为 ；若此二叉树的深度（根所在数为1，深度为树的最大层数）

27、为d，且此树为满二叉树，则此树的结点数n为 。2、对于一棵有n个结点的完全二叉树，其深度为（根所在数为1，深度为树的最大层数） ；若对其结点按层进行编号（根结点为1，每层从左到右），则对于一编号为i(1<i且2i<n)的结点，其双亲结点编号为： ，其左孩子结点编号为： ，右孩子结点的编号为 。 3、在一棵二叉树中，叶子结点数为22,度为1的结点数为13，则该二叉树的结点总数为 。4、具有n个结点的二叉树，其深度最大为 ，最小为 。5、深度为k的二叉树至少有 个结点，至多有 个结点；深度k的完全二叉树，最少有 个结点，最多有 个结点。 6、一棵完全二叉树按层遍历得到结点序列为ABCD

28、EFGH，则结点H的双亲为 ，结点C的左孩子为 。7、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是 的二叉树。A）空或只有一个结点 B）高度等于其结点数 C）任一结点无左孩子 D）任一结点无右孩子8、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历序列中结点E的直接前驱为 ，后序遍历中节点B的直接后继为 。9、某二叉树的中序序列为ABCDEFG，后序序列为BDCAFGE，则该二叉树的先序序列为 ，该二叉树对应的森林中包括 棵树。10、一棵二叉树的节点数据采用顺序存储结构，存储于数组a中，如下图所示，则该二叉树的后序序列为 。1234567891011121314151

29、61718192021EAFDGCJIHB11、由n个权值构成的哈夫曼树共有 个节点。12、若一棵二叉树的先序（根）遍历序列和中序（根）遍历序列分别是ABDEGCF和DBGEACF，请画出此二叉树，并给出其后序（根）遍历序列和层次遍历序列。13、已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA，请画出此二叉树，并将此二叉树转换为对应的森林14、下列叙述正确的是（）A二叉树是度为2的有序树B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2的节点D二叉树中每一个结点最多只有两棵子树，并且有左右之分15、深度为k的完全二叉树所含叶结点的个数最多为（）

30、A2kB2k-1CkD2k16、根据二叉树的定义，具有3个结点的二叉树共有（）种A3 B4C5D617、深度为5的二叉树至多有（）结点A16B32 C31 D1018、一棵二叉树的先序、中序和后序序列如下，其中一部分未标出，请将补充空缺位置给出完整遍历序列。 先序序列： C D E G H I K 中序序列：C B F A J K I G 后序序列： E F D B J I H A19、给定权值集合15，3，14，2，6，9，16，17，请解答下列问题：（1）构造相应的哈夫曼树（2）计算它的带权路经长度20、对图4-1给定的森林和图4-2所示的树，将其转化成相应的二叉树。ABCDGH图4-2E

31、ABCDFGHI图4-1E21、 二叉树的二叉链表存储结构描述如下typedef struct bnode ElemType data; struct bnode *lchild,*rchild; /* lchild、rchild分别为左、右孩子的指针 */*BiTree;（1）递归函数BiTreeDepth(T)的作用是求二叉树的深度，请填写空缺位置。int BiTreeDepth (BiTree T ) /* T为根指针*/ int dl,dr;if ( T=NULL ) return 0; else dl= 【1】 ; dr= 【2】 ; if(dl>=dr) return dl+

32、1; else return 【3】 ; （2）递归函数PreOrder(T)、InOrder(T)、PostOrder(T)的作用对以T为根指针的二叉树进行先根（序）遍历、中根（序）遍历、后根（序）遍历。 void PreOrder (BiTree T ) /*先序遍历以T为根指针的二叉树*/ if ( T ) visit (T->data); /*其中visit()为结点数据的访问函数*/ 【1】 ; 【2】 ; void InOrder (BiTree T ) /*中序遍历以T为根指针的二叉树*/ if ( T ) 【3】 ; visit (T->data); /*其中vis

33、it()为结点数据的访问函数*/ 【4】 ; void PostOrder (BiTree T ) /*后序遍历以T为根指针的二叉树*/ if ( T ) 【5】 ; 【6】 ;visit (T->data); /*其中visit()为结点数据的访问函数*/ 22、假设用于通讯的电文仅由5个字母（A、B、C、D、E）组成，字母在电文中出现的频率分别为0.25, 0.05,0.40, 0.20,0.10。试为这5个字母设计出哈夫曼编码。（要求：画出相应的哈夫曼树，并根据哈夫曼树给出每个字符的哈夫曼编码）第7章 图1、选择题（1）在一个图中，所有顶点的度数之和等于图的边数的 倍。 A1/2

34、B. 1 C. 2 D. 4 （2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A1/2 B. 1 C. 2 D. 4 （3）有8个结点的无向图最多有 条边。 A14 B. 28 C. 56 D. 112 （4）有8个结点的无向连通图最少有 条边。 A5 B. 6 C. 7 D. 8 （5）有8个结点的有向完全图有 条边。 A14 B. 28 C. 56 D. 112 （6）用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。A栈 B. 队列 C. 二叉树 D. 树 （7）已知图的邻接矩阵，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是：A 0 2 4

35、3 1 5 6 B. 0 1 3 5 6 4 2 C. 0 4 2 3 1 6 5 D. 0 1 3 4 2 5 6（8）已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是：A 0 2 4 3 1 6 5 B. 0 1 3 5 6 4 2 C. 0 1 2 3 4 6 5 D. 0 1 2 3 4 5 6（9）已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是：A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 3（10）已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是：A0 3 2 1

36、B. 0 1 2 3 C. 0 1 3 2 D. 0 3 1 2（11） 图的简单路径是指（ ）不重复的路径。A. 权值B. 顶点C. 边D. 边与顶点均（12） 设无向图的顶点个数为n，则该图最多有（ ）条边。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)（13） n个顶点的连通图至少有（ ）条边。A. n-1 B. nC. n+1D. 0（14）若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。A. 上三角矩阵B. 稀疏矩阵C. 对角矩阵D. 对称矩阵（15）设G1 = (V1, E1) 和G2 = (V2, E2) 为两个图，如果V1

37、Í V2，E1 Í E2，则称（ ）。 A. G1是G2的子图 B. G2是G1的子图 C. G1是G2的连通分量 D. G2是G1的连通分量（16）一个连通图的生成树是包含图中所有顶点的一个（ ）子图。 A. 极小B. 连通C. 极小连通D. 无环（17）对于具有e条边的无向图，它的邻接表中有（ ）个边结点。 A. e-1B. e C. 2(e-1) D. 2e（18）与邻接矩阵相比，邻接表更适合于存储（ ）图。 A. 无向B.连通C.稀疏 D. 稠密图（19）在有向图G的拓扑序列中，若顶点vi在顶点vj之前，则下列情形不可能出现的是 。 A. G中有弧vi，vj B.

38、G中有一条从vi到vj的路径C. G中没有弧vi，vj D. G中有一条从vj到vi的路径 （20）有向图G用邻接矩阵A存储，则顶点i的出度等于 。A. 第i行非0元素个数 B. 第i列非0元素个数C. 第i行和第i列所有非0的元素个数 D. 矩阵A中所有非0元数个数2、填空题（1）具有n个顶点的无向连通图最多具有边数为： ，其生成树具有边数为： 。（2）具有n个顶点的有向图最多具有弧数为： 。（3）遍历图有 、 等方法。（4）图的逆邻接表存储结构只适用于 图。（5）用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度 的次序来得到最短路径的。（6）拓扑排序算法是通过重复选择具

39、有 个前驱顶点的过程来完成的。3、求出图1所示无向图中每个的度，及图2所示有向图每个顶点的出度与入度。4、给出图1所示的无向图的邻接矩阵（邻接数组）。V0V2V1V3图1V45、给出图1所示的无向图的邻接表v1v2v4v3v5v6655563624图316、对于图2所示的有向无环图给出其三种拓扑排序序列。7、给出图3所示连通网的邻接矩阵。8、对如图3所示连通网（边上的数值为此边的权值）：（1）从结点v1出发，利用普里姆算法构造其最小生成树。 （2）利用克鲁斯卡尔算法构造其最小生成树。 （只需画出最终的最小生成树，并在每条边的两侧分别注明边的权值和选边的顺序，并将选边的顺序用括号括起来以区别权值

40、）9、用C语言分别定义图的邻点矩阵表示法和邻接表表示法的数据类型。10、图的邻接矩阵表示如下： #define MaxVexNum 20 typedef struct VexType VexsMaxVexNum; /定义顶点数组，VexType为顶点类型 int ArcsMaxVexNum MaxVexNum; /定义邻接矩阵，有弧或边则值为1，否则为0 int vexnum,arcnum; /顶点数或边数 MGraph; 函数FirstAdjVex(G,v)的作用为：在图G中，求顶点v(v为顶点在顶点数组中的下标，下同)的第一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标

41、），否则返回-1。 函数NextAdjVex(G,v,w)的作用为：在图G中，已知顶点w是顶点v当前的一个邻接顶点，函数用来求相对于顶点w顶点v的下一个邻接顶点；若存在函数返回所求得的邻接顶点（即其在顶点数组中的下标），否则返回-1。如下给出了这两个函数头的定义，请给出这两个函数的完整定义。int FirstAdjVex(MGraph &G,int v).int NextAdjVex(MGraph &G, int v, int w).第9章 查 找1以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为_，时间复杂度为_。2以折半查找方法查找一个线性表时，此线性表必须

42、是_存储的_表。3、在有序表A1.18中，采用二分查找算法查找元素值等于A7的元素，所比较过的元素的下标依次为 。4、已知数组a中元素从a1至an递增有序，Search_Bin函数采用折半查找(即二分法查找)的思想在a1an中查找值为m的元素。若找到，则函数返回相应元素的位置(下标)，否则返回0。填写空缺置，使算法完整。int Search_Bin(int a , int n, int m) low=1;high=n; while ( 【1】 ) mid=(low+high)/ 2; if (m=amid ) return 【2】 ; else if (m<amid ) high=mid

43、-1; else 【3】 ; return 0; 5、函数Search_sq的作用是在a1an中采用顺序查找方法，查找值为m的元素。若找到，则函数返回相应元素的位置(下标)，否则返回0。其中利用0下标元素作为监哨岗。填写空缺置，使算法完整。int Search_sq(int a , int n, int m) int i; a0= 【1】 ; for(i=n;m!=ai;i-); return 【2】 ;6、给定序列为45，53，97，24，37，12，从空树开始依次将其插入建立一二叉排序树。n1n3n2n4n5n6n7n8图6-17、若如图6-1所示的二叉树为一二叉排序树（即二叉查找树），现

44、有一菲波那契数列1,2,3,5,8,13,21,34填入该二叉树，则根结点（结点n1）的值为 ，结点n6的值为： 。若欲插入值为10的结点，插入结点应做为： 。8、以下为二叉链表存储的二叉排序树typedef struct bnode int data; /*设树中元素类型为int类型*/ struct bnode *lchild,*rchild; /* lchild、rchild分别为左、右孩子的指针 */*BiTree; Bitree Search (Bitree T, int m) /*在以T为根指针的二叉排序树中进行查找值为m的结点，找到则返回该结点的地址，否则返回NULL*/ p=T

45、; while(p) if(p->data=m) return 【1】 ; else if(m<p->data) p=p->lchild; else 【2】 ; return NULL;9、对于给定的关键字序列（15，19，8，43，10），选取哈希函数为：H（key）=key%7，分别利用以下给出的解决冲突的方法，在06的地址空间上构造出哈希表（画出所构造的哈希表即可）,并求出在等概率查找的情况下查找成功时的平均查找长度。（1）开放定址法的线性探测再散列；（2）开放定址法的二次探测再散列；10、设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MO

46、D 11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散列，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。第10章 排 序1、外排序是指 。 A）用机器指令直接对硬盘中需排序数据排序。 B）把需排序数据，用其他大容量机器排序。 C）把外存中需排序数据一次性调入内存，排好序后，再输回外存。 D）对外存中大于内存允许空间需排序的数据，通过多次内外存间的交换实现的排序。 2、以下给定的序列，哪些是堆（是大顶堆还是小顶堆），哪些不是堆，若不是利用建立初始堆的方法将其建成一大顶堆。 A）19，75，34，26，97，56 B）97，26，34，75，19，56C）19，56，26，97，34，75 D）19，34，26，97，56，753、以下给出的排序方法哪些是稳定的，哪些是非稳定的