数据结构习题.doc

数据结构习题1.算法的计算量的大小称为计算的B。A效率B.复杂性C.现实性D.难度2.算法的时间复杂度取决于CA问题的规模B.待处理数据的初态C. A和B3.计算机算法指的是C，它必须具备B这三个特性。(1) A计算方法B.排序方法C.解决问题的步骤序列D.调度方法(2)A可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性C.确定性、有穷性、稳定性 D.易读性、稳定性、安全性4一个算法应该是CA程序B问题求解步骤的描述C要满足五个基本特性D.A和C.5.下面关于算法说法错误的是DA算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C.算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是B(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A(1)B.(1),(2)C.(1),(4) D.(3)7从逻辑上可以把数据结构分为c两大类A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构8以下与数据的存储结构无关的术语是C A循环队列B.链表C.哈希表D.栈9以下数据结构中，哪一个是线性结构 ADA广义表B.二叉树C.稀疏矩阵D.串10以下那一个术语与数据的存储结构无关B A栈B.哈希表C.线索树D.双向链表11.数据结构S中：元素的集合为：A，关系的集合为：，则S的逻辑结构为D（A） 集合 （B）线性 (C) 树 (D)图12.数据元素之间存在一对多关系的数据结构是C （A）线性表 （B）队列 (C)二叉树 (D)AOV-网13.以下数据结构中，属于线性结构的有A （A） 线性表 （B） 树 (C) 二叉树 (D) 图1数据的物理结构包括 数据元素的表示和 关系的表示。2.对于给定的n个元素,可以构造出的逻辑结构有集合， 线性结构 树状， 图状四种。3数据的逻辑结构是指数据元素之间的逻辑关系。4.数据结构是指数据元素之间的逻辑关系，具体包含三个方面：数据的逻辑结构，数据的物理存储结构和数据运算的集合。5.根据数据元素之间关系的不同特性，通常有线性、 树形、图状和集合四类基本逻辑结构，它们反映了四类基本的数据组织形式。6数据结构中评价算法的两个重要指标是空间和时间的复杂度7.一个算法具有5个特性:有穷性、 确定性、可行性，有零个或多个输入、有一个或多个输出。 第一章1. 数据结构是指【指相互之间存在一种或多种特定关系的数据元素集合； 】，具体包含三个方面：数据的【逻辑结构 】，数据的【物理结构 】和数据运算的集合。2. 根据数据元素之间关系的不同特性，通常有【集合结构 】、【线性结构 】、【树状结构 】、【图状结构 】四类基本逻辑结构，它们反映了四类基本的数据组织形式。3. 数据结构S中：元素的集合为：A，B，C，D，E，F，G，H，I，关系的集合为：，则S的逻辑结构为（D ）（A） 集合 （B）线性 (C) 树 (D)图4. 数据元素之间存在一对多关系的数据结构是（C ）（A）线性表 （B）队列 (C)二叉树 (D)AOV-网5. 以下数据结构中，属于线性结构的有（A ）（A） 线性表 （B） 树 (C) 二叉树 (D) 图6. 存储结构是逻辑结构在计算机中的实现。(对 )7. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。 (错 )8. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。 (错 )9. 顺序存储结构只能用来存放线性结构；链式存储结构只能存放非线性结构。 (错 )10. 算法就是程序。 (错 )11. 一种逻辑结构可以采用不同的存储方式存放在计算机中。 (对 )第二章1. 线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接【前驱 】外，其他结点有且仅有一个直接【前驱 】;除终端结点没有直接【 后继】外，其它结点有且仅有一个直接【后继 】。2. 线性表的顺序存储结构是指用一组【地址连续 】的存储单元依次存储线性表中的各个元素，逻辑上相邻的元素，其物理位置【连续 】_。链式存储结构中，逻辑上相邻的元素，其物理位置【 不一定连续】 。3. 线性表的顺序存储结构中，逻辑上相邻的元素，其物理位置【连续 】。链式存储结构中，逻辑上相邻的元素，其物理位置【不一定连续 】 。4. 在顺序表中插入或删除一个元素，需要平均移动【表长一半 】元素，具体移动的元素个数与【 插入或删除的位置】有关。5. 单链表是线性表的的【链式 】存储结构。6. 单链表表示法的基本思想是用【指针域 】表示结点间的逻辑关系。7. 循环链表与单链表的区别仅仅在于循环链表尾结点的链域值不是【NULL 】，而是一个指向【表头指针 】的指针。8. 如右图所示，在单键表中，P指针所指结点之后插入一个新结点S，操作的语句是： 【 s-next=p-.next】； 【p-next=s 】。9. 顺序表的类型中，假定每个datatype类型的变量占用k(k=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么，第i个（1in）结点ai的存储地址为【b+(i-1)*k 】。10. 在单链表中，删除P 指针所指向的结点的后继（S指针指向的结点）的操作是【p-next=s-next 】；free(【s 】)。11. 以下为顺序表的插入运算，分析算法，请在空白处填上正确的语句。void insert_seqlist(seqlist *L，datatype x，int i)/*将x插入到顺序表L的位序为i的位置*/ if( L-last = maxsize-1 ) error(“表满”)；if(iL-last+2) error(“非法位置”);for(j=L-last;j=i-1;j-)【L-dataj+1=L-dataj 】;L-datai-1=x; 【L-last+】;12. 以下为顺序表的删除运算，分析算法，请在空白处填上正确的语句。 void delete_sqlist(sqlist *L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ if(iL-last)error(“非法位置”)； for(j=i+1;j=L-last;j+)【L-dataj-1=L-dataj 】; L-last=L-last-1;13. 下列有关线性表的叙述中，正确的是（D ）。(A)一个线性表是n个数据元素的有限序列 (B)线性表中任何一个元素有且仅有一个直接前驱(C)线性表中任何一个元素有且仅有一个直接后继 (D)以上说法都不正确14. 顺序表是线性表的（B ）。(A)链式存储结构 (B)顺序存储结构 (C) 索引存储结构 (D) 散列存储结构15. 从一个长度为n的顺序表中删除第i个元素(1in)时,需向前移动（ A）个元素。(A)n-i (B)n-i+1 (C)n-i-1 (D)i16. 一个长度为n的顺序表中第i个位置上插入新元素(1in+1)时,需向后移动（ B）个元素。(A)n-i (B)n-i+1 (C)n-i-1 (D)i17. 下面的定义是（B ）。 typedef struct node int data ; struct node * next ; linklist;(A)顺序表 (B)单链表 (C)双向链表 (D)二叉链表18. 下面的定义是（A ）。 typedef struct int dataMaxsize ; int last ; seqlist;(A)顺序表 (B)单链表 (C)静态链表 (D)循环队列19. 单链表的一个存储结点包含（A ）。(A)数据域或指针域(B)指针域或链域 (C)指针域和链域 (D)数据域和链域20. 单链表中，增加头结点的目的是为了（C ）。(A)使单链表至少有一个结点 (B) 标示表结点中首结点的位置(C)方便运算的实现 (D)说明单链表是线性表的链式存储实现21. 对于单链表表示法，以下说法错误的是（D ）。(A)指向链表的第一个结点的指针，称为头指针 (B)单链表的每一个结点都被一个指针所指(C)终端结点的指针域就为NULL (D)尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表22. 有一个含头结点的单链表，头指针为head，则判断其是否为空的条件是（B ）。(A) head = = NULL (B) head-next = = NULL (C) head-next = = head (D) head != NULL23. 在带头结点的非空单链表H中，指针p指向某的结点，求p结点的前驱结点指针q的算法是（ B ）。(A)q=H ; while(q!=p) q=q-next; (B) q=H ; while(q-next!=p) q=q-next;(C) q=H-next ; while(q!=p) q=q-next; (D) q=H-next ; while(q-next!=p) q=q-next;24. 在带头结点的单链表H中，求单链表长度len的算法是（ A ）。(A) len=0,p=H ; while(p-next!=NULL) len + ; p=p-next;(B) len=0,p=H-next ; while(p-next!=NULL) len + ; p=p-next; (C) len=1,p=H ; while(p!=NULL) p=p-next; len + ; (D) len=1,p=H-next ; while(p-next!=NULL) p=p-next; len + ;25. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针后面插入结点s的操作是（C ）。(A) p-next=s;s=p-next; (B)p-next=s;s-next=p-next; (C) s-next=p-next;p-next=s; (D)s-next=p;p-next=s;26. 假设指针p指向单链表中的某一结点,s为某结点指针，则在p指针前面插入结点s的操作是（ 无正确答案）。(A) s-next=p-next;p-next=s; (B)p-next=s; s-next=p-next; (C) p-next=s ; s=p-next; (D)s-next=p ; p-next=s;27. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（B ）。(A)p=p-next; (B)p-next =p-next -next ; (C)p-next =p; (D)p=p-next-next;28. 某线性表中最常用的操作是存取序号为i的元素及其前驱的值，可采用的存储的方式是（ A）。(A)顺序表 (B)单向链表 (C)双向循环链表 (D)单向循环链表29. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（C ）。(A)顺序表 (B)用头指针表示的单循环链表 (C)用尾指针表示的单循环链表 (D)单链表30. 在单链表中，头结点是必不可少的。(错 )31. 在单链表中，头结点的作用是简化运算。(对 )32. 在线性表的顺序存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。(对 )33. 在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上也是相邻的。(错 )34. 只要内存足够大，采用链式存储结构的线性表长度不受限制。(对 )第三章1. 仅允许在表的一端进行插入与删除操作的线性表称作【栈 】，允许在表的一端进行插入，另一端进行删除操作的线性表 称作【队列 】。2. 栈称为【后进先出 】线性表。队称为【先进先出 】线性表。3. 队列的操作是按【先进先出 】的原则进行的。4. 栈的运算特点是【后进先出 】。请将用C语言的顺序栈的定义补充完整：typedef struct 【 ElementType dataMaxsize】； 【int top 】；seqstack； 5. 以下运算实现在顺序栈上的进栈，请在空白处用适当的语句予以填充。typedef struct DataType datamaxsize ； int top；SeqStack；int Push(SeqStack *sq ,DataType x) if(sp-top= maxsize-1) error(“栈满”)；return(0)； else【sp-top+ 】； 【sp-datasp-top 】=x；return(1)；6. 队列的操作是按【先进先出 】原则进行的。循环队列Q分配Maxsize个存储单元，队头指针为front，队尾指针为rear，采用少用一个空间的方法处理，判断队列满的条件是【front=(rear +1)%Maxsize 】。7. 循环队列是队列的【顺序 】存储结构。8. 循环队列Q分配Maxsize个存储单元，队头指针为front，队尾指针为rear，采用少用一个空间的方法处理，判断队列满的条件是【front=(rear +1)%Maxsize 】。9. 以下顺序栈定义及出栈运算实现，请在空白处用适当语句填充。typedef struct DataType datamaxsize ； int top；SeqStack；int Pop(SeqStack *sp ，DataType *x) if (sp-top=0) error(“空栈”) ； return(0) ； else *x=_ sp-datasp-top_； _sp-top-_； return(1) ； 10. 栈操作的原则是（B ）。(A)先进先出 (B)后进先出 (C)栈顶插入 (D) 栈顶删除11. 栈的两种常用存储结构分别为A(A)顺序存储结构和链式存储结构 (B)顺序存储结构和散列存储结构 (C)链式存储结构和索引存储结构 (D)链式存储结构和散列存储结构12. 有一栈，元素A，B，C，D依次进栈 ,则以下出栈序列中不可能得到的是（ D）。(A) D、C、B、A (B) C、B、A、D (C) A、B、C、D (D) D、C、A、B13.一个栈的入栈序列是A,B,C,D,E,则不可能的出栈序列是（ C）。(A)EDCBA (B)DECBA (C)DCEAB (D)ABCDE14. 若进栈序列为a，b，c，则通过入出栈操作可能得到的a，b，c的不同排列个数为B(A)4 (B)5 (C)6 (D)715. 循环队列是队列的（A ）。(A)顺序存储结构（B）链式存储结构(C)索引存储结构(D)散列存储结构16. 设循环队列中数组的下标范围是1n，其头尾指针分别是f、r，则队列中元素个数为（D ）。(A)r - f (B)r f + 1 (C)(r f + 1)mod n(D)( r f + n ) mod n17. 在循环队列中(少用一个存储空间)，队满的条件是（ A）。(A)(rear+1)%maxsize=front (B)raer=front (C)(front+1)%maxsize=rear (D)rear=018. 循环队列的队满条件为（ C）。(A) (sq.rear+1) % mazsize =(sq.front+1) % maxsize;(B) (sq.rear+1) % maxsize =sq.front+1(C) sq.(rear+1) % maxsize =sq.front(D) sq.rear =sq.front19. 设数组datam作为循环队列SQ的存储空间，front为头指针，rear为尾指针，执行出队操作,其头指针的值为（D ）。(A) front=front+1 (B) front=(front+1)%(m-1) (C) front=(front-1)%m (D) front=(front+1)%m20. 栈和队列与线性表的逻辑结构相同。(对 )21. 栈只能在栈顶进行插入和删除。(对 )22. 队列只能在队首进行删除，在队尾进行插入。(对 )23. 队列只能在队尾进行删除，在队首进行插入。(错 )第四章1. 通常采用【顺序 】存储结构来存放数组 。对二维数组可有两种存储方法：一种是以【行 】为主序的存储方式，另一种是以【列 】为主序的存储方式。2. 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)= 【loc(a1)+(i+1)*k 】。3. 在C语言中定义的二维数组int M1020，每个元素（整数）占两个存储单元，数组的起始地址为2000， M819的存储值为【2358 】。元素M510的存储位置为【2220 】。4. 假设有6行8列的二维数组A，每个元素占用6个字节，存储器按字节编址。已知A的基地址为1000，那么元素A3，6在按行存储时的地址是【1126 】，按列存储时的地址是【1192 】。5. 对称方阵采用压缩存储， 即为每一对对称位置元素只分配一个存储空间 ，则可将n2个元素压缩存储到【n*(n+1)/2 】个元素的存储空间中。6. 有一个10阶对称矩阵A1010，采用压缩存储方式以行序为主存储，A00的位置是1，则A85的位置是【42 】。7. 三元组表是【稀疏矩阵 】的【顺序 】存储结构。8. 字符串S=“Computer”中，以p为首字符的子串有【5 】个。9. TAILHEAD(a,b),(c,d)运算的结果是【(b) 】。10. 广义表L=（x,a）,(x,a,(b,c),y）的长度是【3 】。11. 设广义表A=(a,b),B=(c,d),求head( (A, B) )的值为【 (a,b)】。12. 有如下稀疏矩阵，请写出它的三元组表：m=6 n=6 t=913. 串是（D ）。(A)一些符号构成的序列(B)有限个字母构成的序列 (C)一个以上的字符构成的序列(D)有限个字符构成的序列14. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=“SCIENCESTUDY”，则调用函数Scopy(P,Sub(S,1,7)后得到（A ）。(A)P=“SCIENCE” (B)P=“STUDY” (C)S=“SCIENCE ” (D)S=“STUDY”15. 设有一个二维数组A68,假设A00存放位置在1000,每个元素占6个空间，按行优先存储，则A36的存储位置是_B_(A)1180 (B)1126 (C)126 (D)18016. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第五个元素的地址是_B_。(A)110 (B)108 (C)100 (D)12017. 为了节省存储空间，将n阶对称矩阵A(下标从1开始)中包括主对角线元素在内的下三角部分的所有元素按照行序为主序方式存放在一维数组B1:n(n+1)/2中，对任意下三角部分的元素aij(ij)在数组B的下标k是_B_。(A)i(i-1)/2+j-1 (B)i(i-1)/2+j (C)i(i+1)/2+j-1 (D)i(i+1)/2+j 18. 基于三元组的稀疏矩阵，对每个非零元素aij,可以用一个（_B_ ）唯一确定。(A)非零元素 (B)三元组(i,j,aij) (C) aij (D) i,j19. 广义表A=(),(a),(b,(c,(D)的长度为_B_。(A)2 (B)3 (C)4 (D)5 20. 空串与由空格组成的串没有区别。(错 )21. 对称矩阵的压缩存储是指对矩阵中的值相同的元素只分配一个存储空间。(对 )22. 对称矩阵的压缩存储是指对矩阵中的规律元素只分配一个存储空间。(对 )23. N阶下三角矩阵压缩存储需要n*(n+1)/2个存储空间。(对 )24. 三元组表是稀疏矩阵的顺序存储结构。(对 )第六章1. 在二叉树中，第i层的结点数最多为【2（i-1）】；2. 深度为k的二叉树的结点总数最多为【2k-1 】。3. 对任何二叉树，若度为2的节点数为n2，则叶子数n0=【n2+1 】。4. 在一棵完全二叉树中，若编号为i的结点有左孩子，则该左孩子结点的编号为【2i 】；若编号为i的结点有右孩子，则该右孩子结点的编号为【2i+1 】。5. 一棵深度为5的二叉树最多有【31 】 个结点。6. 深度为h且有【2h-1 】个结点的二叉树称为满二叉树。(设根结点处在第1层)。7. 具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号是【n/2 】，编号最小的分支结点序号是【1 】，编号最大的叶子结点序号是【 n】，编号最小的叶子结点序号是【n/2+1 】。8. 在有n个结点的二叉树，采用二叉链表存放，空链域的个数为【n+1 】。9. 二叉树通常有【顺序 】存储结构和【二叉链表 】存储结构两类存储结构。10. 给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树。题出错11. 请对给定的二叉树的存储结构，将二叉树的中序遍历输出结点递归算法补充完整：typedef struct node char data； /*元素为字符型*/struct node * Lchild，*Rchild； *BiTree； void Inorder(BiTree root ) if ( root != NULL ) 【 Inorder(root-Lchild) 】；【 Visit（root-data）】； 【inorder（root-Rchild） 】； 12. 请对给定的二叉树的存储结构，将二叉树的先序遍历输出结点递归算法补充完整：typedef struct node char data; /*元素为字符型*/struct node * Lchild,*Rchild; BiTree; void preorder(BiTree root ) if ( root != NULL ) 【Visit（root-data） 】;【preorder（root-Lchild） 】; 【preorder（root-Rchild） 】; 13. 以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。void countleaf(bitree *t,int *count)/*根指针为t，假定叶子数count的初值为0*/ if(t!=NULL) if(t-lchild=NULL)&(t-rchild=NULL) 【count=0 】; countleaf(t-lchild,&count); 【countleaf(t-rchild,&count) 】 14. 哈夫曼树是带权路径长度【最短 】的树，通常权值较大的结点离根【较近 】。15. 有m个叶子结点的哈夫曼树，其结点总数为【2m-1 】。16. 用5个权值3, 2, 4, 5, 1构造的哈夫曼树的带权路径长度是33 。选择题：17. 按照二叉树的定义，具有3个结点的二叉树有_C_种形态。(A)3(B)4 (C)5 (D)618. 二叉树是非线性数据结构，它（C ）。(A)不能用顺序存储结构存储;(B)不能用链式存储结构存储;(C)顺序存储结构和链式存储结构都能存储;(D)顺序存储结构和链式存储结构都不能使用19. 下列陈述中正确的是（D ）。(A)二叉树是度为2的树 (B)二叉树中结点只有一个孩子时无左右之分(C)二叉树中必有度为2的结点 (D)二叉树中最多只有两棵子树，并且有左右之分20. 设有一棵22个结点的完全二叉树，那么整棵二叉树有（D ）个度为0的结点?(A)6(B)7(C)8(D)1121. 某非空二叉树共有叶结点15个，没有度为1的结点，则该树共有（A ）个结点。(A)29 (B)28(C)27(D)不能确定22. 已知完全二叉树有26个结点，则整棵二叉树有（A ）个度为1的结点？(A)1 (B)0 (C)2 (D)不确定23. 将一棵有50个结点的完全二叉树编号，根结点为1，每层从左到右依次编号，则编号为49的结点的双亲结点的编号是（B ）。(A)23(B) 24(C) 25(D)2624. 对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（C ）方法实现编号。(A) 前序遍历 (B) 中序遍历(C) 后序遍历(D) 从根开始进行层次遍历25. 一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，（号码为1-n），编号须具有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加1。而其右子树中结点的最小编号等于V的编号加1。试问应按（B）遍历顺序编号。(A)前根 B中根 C后根 D层次27. 某二叉树的中序遍历为：BDAEC，后序遍历为：DBECA，则前序遍历为（A ）。(A)ABDCE(B)ADBCE(C)ABDEC (D)BDACE 28. 已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为（D ）。(A)DEBAFC (B)DEFBCA (C)DEBCFA (D)DEBFCA29. 在有n个叶子结点的哈夫曼树中，其结点总数为（D ）。(A)不确定(B)2n (C)2n+1 (D) 2n-1 30. 哈夫曼树的带权路径长度是（B ）。(A) 所有结点权值之和 (B) 所有叶结点带权路径长度之和(C) 权结点的值 (D) 除根以外所有结点权值之和31. 下列说法正确的是（A ）。(A) 树的先根遍历序列与其对应的二叉树的先根遍历序列相同(B) 树的先根遍历序列与其对应的二叉树的后根遍历序列相同(C) 树的后根遍历序列与其对应的二叉树的先根遍历序列相同(D) 树的后根遍历序列与其对应的二叉树的后根遍历序列相同判断题：32. 对于一棵任意二叉树，若叶子结点数为n0，度为2的结点个数为n2，则有n2= n0+1。(错 )33. 对于一棵任意二叉树，若叶子结点数为n0，度为2的结点个数为n2，则有n0= n2+1。(对 )34. 深度为n的非空二叉树的第i层最多有2n-1 个结点。(错 )35. 非空二叉树的第i层最多有2i-1 个结点。(对 )36. 二叉树中，任何一个结点的度为2。(错 ) 37. 二叉树中每个结点的两棵子树是有序的。(对 ) 38. 具有12个结点的完全二叉树有4层深。(对 )39. 具有12个结点的完全二叉树有5个度为2的结点。(对 )40. 线索二叉树是在二叉树的所有结点的存储结构中增加先驱和后继指针得到的。(错 ) 41. 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。(对 ) 42. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。(错 ) 43. 哈夫曼树中不存在度为1的分支结点。(对 ) 44. 有n个叶子结点的哈夫曼树共有2n-1个结点。(对 ) 第七章1. 在无向图中，如果从顶点v到顶点v有路径，则称v和v是【 连通 】的。2. 图的存储结构主要有【顺序存储 】和【链式存储 】两种。3. 遍历图的基本方法有【深度 】优先搜索和【广度 】优先搜索两种。4. 有如图所示的图的邻接矩阵，从1顶点出发对该图进行深度优先搜索的结点序列是【1,2,3,4,6,5 】，广度优先搜索的结点序列是【1,2,3,5,6,4 】。5. 若连通图G的顶点个数为n，则G的生成树的边数为【n-1 】。6. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的【出 】 度 。7. 有向图G用邻接矩阵存储，其第i列的所有元素之和等于顶点i的【入 】 度 。8. 无向图的邻接矩阵是一个【对称 】矩阵；在邻接矩阵上，无向图中顶点vi的度为【2 】； 邻接表上，无向图中顶点vi的度为【1 】。9. 一个具有n个顶点的简单无向图最多（C ）条边。(A)n (B)n(n-1) (C)n(n-1)/2 (D)2n10. 有8个结点的无向连通图最少有（C ）条边。(A)5 (B) 6 (C)7 (D)811. 一个具有n个顶点的无向完全图的边数为B(A) n(n+1)/2 (B) n(n-1)/2 (C) n(n-1) (D) n(n+1)12. 任何一个带权的无向连通图的最小生成树B(A)只有一棵 (B)有一棵或多棵 (C)一定有多棵 (D) 可能不存在13. 已知一个有向图，则从顶点a出发进行深度优先遍历，不可能得到的DFS序列为D(A) a d b e f c B .a d c e f bC .a d c b f e (D) a d e f c b14. 对下图1所示的带权有向图，从顶点1到5 的最短路径为（D ）。(A)1,4,5 (B)1,2,3,5(C)1,4,3,5 (D)1,2,4,3,516. 某有向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由m个头结点和n个表结点组成。(错 )17. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(对 )18. 有n个结点的无向完全图有n*(n-1)/2条边。(对 )19. 有n个结点的有向完全图有n*(n-1)/2条边。(错 )20. 某无向图由m个顶点和n条边组成，使用邻接表进行存储，则该邻接表由m个头结点和n个表结点组成。(错 )21. 有向图中所有顶点的入度之和等于所有顶点的出度之和。(错 )22. 普里姆算法是采用“加边法”构造最小生成树的。(错 )23. AOE 网是一种带权的无环连通图。(错 )24. AOE 网是一种带权的有向无环图。(对 )25. AOE网所表示的工程至少所需要的时间等于从源点到汇点的最长路径长度。(对 )26. AOE网来表示工程计划时，从源点到汇点的最短路径表示了关键路径。(错 )27. AOV网的拓扑序列是唯一的。(错 )28. 带权连通图的最小生成树的权值之和是它的生成树的权值之和中最小的。(对 )29. 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( 对)30. 迪杰斯特拉（Dijkstra）算法是按照最短路径长度递增的顺序产生所有的最短路径。(错 ) 第 八、九章1. 折半查找对待查找的列表有两个要求：（1）采用【.顺序 】存储结构（2）关键字【有序 】排列。2. 在线性表中采用折半查找法查找一个数据元素，线性表中元素应该按值有序，并且采用【.顺序 】存储结构。3. 在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值【小 】的结点，只需通过结点X的左指针到它的左子树中去找。4. 中根遍历一棵二叉排序树所得的结点访问序列是键值的【升序 】序列。5. 在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，所得到的二叉排序树是【 】。6. 已知序列(34，76，45，18，26，54，92，65)，按照逐点插入法建立一棵二叉排序列树，该树的深度是【5 】。7. 平衡因子是【结点的左子树深度与右子数深度之差】。平衡的二叉排序树的平衡因子的值只能是【-1 0 1 】。8.哈希法中影响关键字比较次数的三个因素是：（1）【哈希函数、 】（2）【处理冲突的方法、 】（3）【哈希表的装填因子】。哈希表的装填因子是：【哈希表中元素个数 / 哈希表的长度】。的值越小，发生冲突的可能性越小，的值越大，发生冲突的可能性越大。8. 在数值无规律的线性表中进行检索的方法是【顺序查找 】 。9. 按照排序过程涉及的存储设备的不同，排序可分为【内 】排序和【外 】排序。10. 排序过程中一般进行两个基本操作（）【比较】（）【移动 】。其中（）是必要的，（）可以采用适当的存储方式避免。11. 给定关键字（48，62，35，77，55，14，35，98）进行一趟快速排序的结果是【35 14 35 48 55 77 62 98】。12.若对序列(49，38，65，97，76，13，27，50)采用快速排序，则第一趟排序后序列的状态是【273813 49 76 97 65 50】。12. 设有散列函数H(k)=k mod 13散列表为T012，用线性探测再散列。假定在某一时刻T的状态为：T:012345678910111280853415、下一个被插入的关键码是42，其插入的位置是: 【4】。16. 请将直接选择排序算法补充完整：void SelectSort(RecordType R,int length)n = length;for(i=1;i=【n-1 】;i+) k=【i 】; for(j=i+1;j=n;j+) if(Rj.key Rk.key ) k=【j 】; if (【k!=i 】) x=Ri;Ri=Rk;Rk=x; 17. 以下简单选择排序算法，请将算法补充完整:void SelectSort(RecordType R , int length) n=length; for ( i=1 ;i= n-1; i+) k=j;for ( j=i+1; j=n ; j+ )if( Rj.key Rk.key ) k=j; if (k!=i) x=Ri ;Ri=Rk ;Rk=x; 18. 以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。 void select(seqlist r,int n) for(i=1;i=【n-1】;i+)/*每次循环，选择出一个最小键值*/ k=i; for(j=i+1;j=n;j+) if(rj.keyrk.key) 【k=j】; if(【k!=i】)swap(rk,ri）;