数据结构(C语言版)(第4版)习题

习题1选择题。(1)计算机识别、存储和加工处理的对象统称为。A．数据B.数据元素C.数据结构D.数据类型(2)数据结构通常是研究数据的及它们之间的联系。A．存储和逻辑结构B.存储和抽象C.理想和抽象D.理想和逻辑(3)下列不是数据的逻辑结构的是。A．散列结构B.线性结构C.树形结构D.图状结构(4)数据结构被形式地定义<D,R>，其中D是的有限集，R是___的有限集。A．算法B.数据元素C.数据操作D.逻辑结构(5)组成数据的基本单位是。A．数据项B.数据类型C.数据元素D.数据变量(6)设数据结构A=(D,R),其中，D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A是。A．线性结构B.树形结构C.图状结构D.集合(7)数据在计算机存储器中表示时，若物理地址与逻辑地址相同并且是连续的，则称为。A．存储结构B.逻辑结构C．顺序存储结构D.链式存储结构(8)在数据结构的讨论中把数据结构从逻辑上分。A．内部结构与外部结构B.静态结构与动态结构B．线性结构与非线性结构D.紧凑结构与非紧凑结构(9)对于一个算法的评价，不包括以下方面的内容。A.健壮性和可读性B.并行性C.正确性D.时间空间复杂度(10)算法分析的两个方面是。A．空间复杂性和时间复杂性B.正确性和简明性C．可读性和文档性D.数据复杂性和程序复杂性1.2填空题(1)数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的和运算等的学科。(2)数据结构包括数据的结构和结构。(3)数据结构从逻辑上划分为3种基本类型，即、和。(4)数据的物理结构被分为、、和种类型。(5)一种抽象数据结构类型包括和两个部分。(6)数据的逻辑结构是指数据的存储结构是指(7)数据结构是指指数数据及其相互之间的当结点之间存在M对N(M:N)的联系时，称这种结构为当结点之间存在1对N(1：N)的联系时，称这种结构为(8)对算法从时间和空间两个方面进行衡量，分别称为分析。(9)算法的效率可以分为效率和效率。(10)for(i=1,t=1,s=0;i<=n;i++){t=t*i;s=s+t;}的时间复杂度为1.3简述下列术语：数据、数据项、数据元素、数据的逻辑结构、数据的物理结构、数据类型和算法。1.4分析下面语句段执行的时间复杂度。(1)for(i=1;i<=n;i++)for(j=1;j<=n;j++)s++;(2)for(i=1;i<=n;i++)for(j=i;j<=n;j++)s++;(3)for(i=1;i<=n;i++)for(j=1;j<=i;j++)s++;(4)i=1;k=0;While(i<=n-1){k+=10*i;i++;}(5)for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;1.5试写一个算法，自大至小依次输出顺序读入的3个整数X、Y和Z。1.6编写算法，求一元多项式Pn(x)=a0+a1x+习题22.1选择题(1)线性表是具有n个的有限序列(n≠0)。A.表元素B.字符C.数据元素D.数据项(2)顺序表的存储结构是一种的存储结构。A.随机存取B.顺序存取C.索取存取D.Hash存取(3)在一个长度为n的顺序表中向第i个元素(1≤i≤n+1)之间插入一个新元素时需要向后移动个元素。A.n-iB.n-i+1C.n-i-1D.i(4)链表是一种采用存储结构存储的线性表。A．顺序B.链式C.星型D.网状(5)下面关于线性表的叙述错误的是A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D．线性表采用顺序存储便于插入和删除操作的实现(6)设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列存储方式最节省运算时间。A.单向链表B.单向循环链表C.双向链表D.双向循环链表(7)设指针q指向单链表中的结点A，指针p指向单链表中的结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为A.s->next=p->next;p->next=-s;B.q->next=s;s->next=p;C.p->next=s->next;s->next=p;D.p->next=s;s->next=q;(8)设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为A.p->next=p->next->nextB.p=p->nextC.p=->next->nextD.p->next=p(9)在一个以h为头的单循环链表中，p指针指向链尾的条件是。A.p->next=hB.p->next=NULLC.p->next->next=hD.p->date=-1(10)对于只有首、尾两端进行操作的线性表，宜采用的存储结构为。A.顺序表B.用头指针表示的单循环链表C.单链表D.用尾指针表示的单循环链表2.2填空题(1)线性表是n个元素的________________。(2)线性表的存储结构有________________。(3)设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为，在链式存储结构上实现顺序查找的平均时间复杂度为。(4)设顺序线性表中有n个数据元素，则在第i个位置上插入一个数据元素需要移动表中的个数据元素，删除第i个位置上数据元素需要移动表中的个元素。(5)若频繁地对线性表进行插入与删除操作，则该线性表应采用存储结构。(6)链式存储结构中的结点包含域和域。(7)在双向链式表中每个结点有两个指针域，一个指向另一个指向(8)对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为在表尾插入元素的时间复杂度为(9)设指针变量p指向单链式表中的结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为________。(10)设指针变量p指向单链式表中的结点A，则删除结点A的后继结点（假设存在）的语句序列为“s=p->next;p->next=;free(s);”2.3将一顺序表A中的元素逆置。例如原来顺序表A中的元素是100,90,80,70,60,50,40，逆置以后为40,50,60,70,80,90,100。要求算法所用的辅助空间尽可能地少，用非形式算法描述，并编写C语言程序。2.4写一算法输出已知顺序表A中元素的最大值和最小值，并编写C语言程序。2.5设一顺序表中的元素值递增有序，写一算法，将元素x插入到表中的适当位置，并保持顺序表的有序性。2.6设有两个按元素递增有序的顺序表A和B（单链式表A和B），编一程序将A表和B表归并成一个新的递增有序的顺序表C（单链式表C），值相同的元素均保留在C表中。2.7设有两个线性表A和B都是单链表存储结构。同一个表中的元素各不相同，且递增有序，写一算法，构成一个新的线性表C，使C为A和B的交集，且C中的元素也递增有序。习题33.1选择题(1)下列说法正确的是_____。A.堆栈是在两端操作、先进后出的线性表B.堆栈是在一端操作、先进先出的线性表C.队列是在一端操作、先进先出的线性表D.队列是在两端操作、先进先出的线性表(2)栈和队列的共同点是_____。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点(3)以下数据结构中是非线性结构的是_____。A.队列B.栈C.线性表D.二叉树(4)已知一个栈的入栈序列是1,2,3，…,n，输出序列是p1，p2，p3⋯A.iB.n-iC.n-i+1D.不确定(5)当利用大小为N的一堆数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时首先应执行_____语句修改top指针。A.top++B.top--C.top=0D.top(6)4个元素进S栈的顺序是A→B→C→D，经POP(S)运算后栈顶元素是_____。A.AB.BC.CD.D(7)一个栈的输入序列是a,b,c,d,e,则栈不可能的输出序列是____。A.e,d,c,b,aB.d,e,c,b,aC.d,c,e,a,bD.a,b,c,d,e(8)设输入序列是1,2,3，…，n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出的元素是_____。A.n-iB.n-i-1C.n+1-iD.不能确定(9)字符A,B,C,D依次进入一个栈，按出栈的先后顺序组成不同的字符串，最多可以组成_____个不同的字符串。A.15B.14C.16D.21(10)递归函数f(n-1)=f(n-1)+n(n≥1)的递归出口是_____。A.f1=0B.f1=1C.(11)设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作为_____。A.top=top+1;B.top=top-1;C.top->next=top;D.top=top->next;(12)中缀表达式A-(B+C/D)*E的后缀形式是_____。A.ABC+D/*E-B.ABCD/+E*-C.AB-C+D/E*D.ABC-+D/E*(13)用front和rear分别表示顺序循环队列的队首和队尾指针，判断队空的条件为_____。A.front+==reearB.(rear+1)%maxSize==frontC.front==0D.front==rear(14)判定一个循环队列QU（最多元素为m0）为满队列的条件为_____。A.QU->front==QU->rearB.QU->front!=QU->rearC.QU->front==(QU->rear+1)%mD.QU->front!=(QU->rear+1)%m(15)设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，A.6B.4C.3D.2(16)用连接方式存储的队列，在进行插入运算时_____。A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改(17)若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素再加入两个元素后，rear和front的值分别为_____。A.1和5B.2和4C.4和2D.5和1(18)设顺序循环队列Q[0：M=1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一个位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为_____。A.R-FB.F-RC.(R-F=M)%MD.(F-R+M)%M(19)设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作为_____。A.front->next=s;front=s;B.s->next=front;rear=s;C.rear->next=s;rear=s;D.s->next=front;front=s;(20)当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为_____。A.n-2B.n-1C.nD.n+13.2填空题（1）栈的插入和删除只能在栈顶进行，后进栈的元素必定先出栈，所以又把栈称为_____表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为下划表。（2）后缀算式923+-102/-的值为_____，中缀算式(3+4X)-2Y/3对应的后缀算式为_____。（3）下面程序段的功能是实现数据x的进栈，要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==n-1)printf(“overfow”);else{__________；__________；}（4）设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_____；_____；（设结点中的两个指针域分别为llink和rlink）。（5）设一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储M-1个队列元素，当前实际存储_____个队列元素（设头指针F指向F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。（6）设有一个顺序共享栈S[0:n-1],其中，第一个栈顶指针top1的处置为-1，第二个栈顶指着top2的初值为n，则判断共享栈满的条件是（7）设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为__________。（8）顺序循环队列判空的条件是（使用front、rear、n表示）__________。（9）顺序循环队列判满的条件是（使用front、rear、n表示）__________。（10）顺序循环队列MAXSIZE=N,最多可以存储_____个元素。3.3简述栈和线性表的区别。3.4简述栈和队列这两种数据结构的相同点和不同点。3.5如果进栈的元素序列为A,B,C,D,可能得到的出栈序列有多少种？写出全部的可能序列。3.6如果进栈的元素序列为1,2,3,4,5,6，能否得到4,3,5,6,1,2和1,3,5,4,2,6的出栈序列？说明为什么不能得到或如何得到。3.7写出下列程序段的运行结果（栈中的元素类型是char）:main(){SeqStacks,*p;charx,y;p=&s;Init_Queue(p);x=’c’;y=’k’;push(p,x);push(p,’a’);push(p,y);x=pop(p);push(p,’t’);push(p,x);x=pop(p);push(p,’s’);while(!Empty_SeqStack(p)){y=pop(p);printf(“%c”,y);}printf(“%c\n”,x);}3.8将一个非负十进制整数转换成二进制数，用非递归算法和递归算法来实现。3.9写一算法将一顺序栈中的元素依次取出，并打印元素值。3.10写出下列程序段的运行结果（队列中的元素类型是char）:main(){SeqStacka,*q;charx,y;q=&a;x=’e’;y=’c’;Init_Queue(q);In_Quene(q,’h’);In_Quene(q,’r’);In_Quene(q,y);x=Out_Quene(q);Init_Queue(q,x);x=Out_Quene(q);Init_Queue(q,’a’);while(!Empty_SeqStack(q)){y=Out_Quene(q);printf(“%c”,y);}printf(“%c\n”,x);}3.11写一算法将一链队列中的元素依次取出，并打印这些元素值。习题44.1选择题(1)下列叙述正确的是_____。A．串是一种特殊的线性表B.串的长度必须大于零C.串中元素只能是字母D.空串就是空白串(2)下列关于串的叙述正确的是_____。A.串长度是指串中不同字符的个数B.串是n个字母的有限序列C.如果两个串含有相同的字符，则它们相等D.只有当两个串的长度相等并且各个对应位置的字符都相符时才相等(3)字符串的长度是指_____。A.串中不同字符的个数B.串中不同字母的个数C.串中所含字符的个数D.串中不同数字的个数(4)两个字符串相等的充要条件是_____。A.两个字符串的长度相等B.两个字符串中对应位置上的字符相等C.同时具备A和B两个条件D.以上答案都不对(5)串是一种特殊的线性表，其特殊性体现在_____。A.可以顺序存储B.数据元素是一个字符C.可以连接存储D.数据元素可以是多个字符(6)设有两个p和q,求q和p中首次出现的位置的位置的运算称为_____。A.连接B.模式匹配C.求子串D.求串长(7)设串s1=“ADCDEFG”,s2==“PQRET”，函数con(x,y)返回x和y串的连接subs(s,i,j)返回串s从序列号为i的字符开始的j个字符组成的子串，len(s)返回串s的度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是_____。A.BCDEFB.BCDEFGC.BCPQRETD.BCDEFEF(8)函数substr(“DATASTRUCTURE”),5,9)的返回值为_____。A.“STRUCTURE”B.“DATA”C.“ASTRUCTUR”D.“DATASTRUCTURE”(9)设有二维数组A[50][60],其元素长度为1B，按列优先顺序存储，首先素A[0][0]的地址为200，则元素A[10][20]的存储地址为_____。A.820B.720C.1210D.1410(10)设串s=“IAMATEACHER!”,其长度是_____。A.16B.11C.14D.154.2填空题（1）两个串相等的充要条件是__________。（2）空串是_____，其长度为_____。（3）空格串是_____，其长度是_____。（4）s=“Iamaman”的长度为_____。（5）s1=“hello”,s2=“boy”,s1,s2连接后为_____。（6）s=“thisisthemainstring”，sub=“string”,strindex(s,sub)是_____。（7）inta[10][10],已知a=1000,sizeof(int)=2,a[3][3]的地址为_____。（8）设有两个串p和q，求q在p中首次出现的位置的运算称为_____。（9）串的长度是指_____。（10）s=“xiaotech”所含子串的个数是_____。4.3设s=“IAMASTUDENT”,t=“GOOD”,q=“WORKER”,求StrLength(s)、StrLength(t)、SubStr(t,2,1)、SteeIndex(s,“A”)、StrIndex(s,t)、StrRep(s,“STUDENT”,q)。4.4已知s=“（XXZ）+*”,t=“（X+Z）*Y”,试利用连接、求字串和置换等基本运算将s转化为t。4.5简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和字串；串变量的名字和串变量的值。4.6编一算法，在顺序串上实现串的判等操作EQUAL(S,T).4.7设有二维数组A(6×8),每个元素占6B顺序存放，A的起地址为1000，做以下计算：（1）数组A的体积（即存储量）；（2）数组的最后一个元素A5,（3）按行优先存放时，元素A1,（4）按列优先存放时，元素A4,74.8已知稀疏矩阵如图4.12所示，画出它的三元组表的示意图。A=图4.12题4.8图习题55.1单选题（1）树最适合用来表示_____。A.有序数据元素B.无序数据元素C.元素间具有层次关系的数据D.元素间无联系的数据（2）在m叉树中，度为0的结点称为_____。A.兄弟B.树叶C.树根D.1（3）如果树的结点A有4个兄弟，而且B为A的双亲，则B的度为_____。（4）根据二叉树的定义可知二叉树共有_____种不同的形态。A.4B.5C.6D.7（5）由3个结点可以构造出_____种不同形态的二叉树。A.3B.4C.5D.6(6)具有20个结点的二叉树，其深度最多为_____。A.4B.5C.6D.20（7）高度为h的满二叉树的结点数是_____个。A.log2hB.2hC.2h-1（8）深度为5的二叉树最多有_____个结点。A.16B.32C.31D.10（9）设一棵二叉树共有50个叶子结点（终端结点），则共有_____个度为2的结点。A.25B.49C.50D.51（10）一颗完全二叉树中根结点的编号为1，并且23号结点有左孩子但没有右孩子，则完全二叉树共有_____个结点。A.24B.45C.46D.47（11）二叉树的第3层最少有_____个结点。A.4B.1C.2D.3（12）设n,m为一棵二叉树上的两个结点，在中序遍历时，n在m之前的条件是_____。A.n在m右方B.n是m的祖先C.n在m左方D.n是m的子孙（13）某二叉树的先序序列和后序序列正好相同，该二叉树可能是_____的二叉树。A.高度大于1的左单支B.高度大于1的右单支C.最多只有一个结点D.既有左孩子又有右孩子（14）某二叉树的先序序列和后序序列正好相反，该二叉树一定是_____的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子（15）有n个结点的二叉树链表共有_____个空指针域。A.n-1B.2n-1C.2n+1D.2(n-1)（16）一个有n个叶结点的哈夫曼树具有的结点数为_____。A.2nB.2n-1C.2n+1D.2(n-1)5.2填空题（1）一颗深度为5的二叉树，最少有_____个叶子结点。（２）一颗完全二叉树采用顺序存储结构，每个结点占４个字节，设编号为５的元素的地址为１０１６，且它有左孩子和右孩子，则该左孩子和右孩子的地址分别为_____和_____。（３）一颗完全二叉树采用顺序存储结构，若编号为ｉ的元素有有左孩子，则该左孩子的编号为_____。（４）一棵含有ｎ（ｎ＞１）个结点的ｋ叉树，当ｋ＝_____时深度最大，此最大深度为_____；当ｋ＝_____时深度最小，此最小深度为_____。（５）深度为为ｋ的玩群二叉树最少有_____个结点，最多有_____个结点。（６）已知一棵二叉树的线序遍历序列为ＥＢＡＤＣＦＨＧＩＫＪ，中序遍历序列为ＡＢＣＤＥＦＧＦＩＪＫ，则该二叉树的后序遍历序列为_____。（７）如果指针ｐ指向一棵二叉树的一个结点，则判断ｐ没有左孩子的逻辑表达式为_____。（８）在由ｎ个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为_____。（９）在树的孩子兄弟表示法中，每个结点有两个指针域，一个指向_____，另一个指向_____。（１０）树的先根遍历结果与其转换的相应二叉树的_____结果相同；树的后跟遍历与其转换的相应二叉树的_____结果相同。５.３写出图５.２４中树的叶子结点、非终端结点、个结点的度和树深。５．４分别画出含３个结点的无序树与二叉树的所有不同形态。５．５分别画出含３个结点的无序树与二叉树的所有不同形态。５.６分别写出图５.２５中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。图５.２４题５.３图图５.２５题５.５图５.７试找出分别满足下列条件的所有二叉树：（１）先徐序列和中序序列相同；（２）后徐序列和中序序列相同；（３）先徐序列和后序序列相同。５.８已知一棵二叉树的中序序列和后序序列分别为ＢＣＤＥＡＦＨＧ和ＤＥＣＢＨＧＦＡ，试画出这棵二叉树。５.９分别写出图５．２４中所示树的先根遍历、后根遍历和层次遍历的结点访问序列。５.１０如果一棵树有n1个度为1的结点，n2个为2的结点。……,nm个度为m的结点，则该树共有多少个叶5.12编一算法求二叉树中的结点的总数。5.13编一算法将二叉树中所有结点的左、右子树相互交换。5.14编一算法判别给定的二叉树是否是完全二叉树。5.15将图5.26中所示的森林转换为二叉树。图5.26题5.15图5.16分别画出图5.27中所示二叉树对应的森林。5.17在以双亲链表表示法存储结构的树中，写出以下算法：（1）求树中结点双亲的算法；（2）求树中结点孩子的算法。5.18在以孩子链表表示法存储结构的树中，写出以下算法：（1）求树中结点双亲的算法；（2）求树中结点孩子的算法。5.19在以孩子兄弟链表结构存储的树中，写出求树中结点孩子的算法。5.20（1）给定权值（4,3,16,9,22,10,5），构造相应的哈夫曼树。（2）设上述权值分别代表7个字母出现的频率，试为这7个字母设计哈夫曼编码。习题66.1选择题（1）一个有8个顶点的有向图，所有顶点的入度之和与所有顶点的出度之和的差是_____。A.16B.4C.0D.2（2）一个有n个顶点的连通无向图最少有_____条边。A.n-1B.nC.n+1D.n+2（3）具有n个顶点的完全有向图的弧数为_____。A.n(n-1)/2B.n(n-1)C.n2D.（4）一个n条边的连通无向图，其顶点的个数最多为_____。A.n-1B.nC.n+1D.nlogn（5）设无向图的顶点个数为n，则该图最多有_____条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.0（6）任何一个无向连通图的最小生成树_____A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在（7）在下列算法中，_____算法用来求图中某顶点到其他所有顶点之间的最短路径。A.DijkstraB.FloyedC.PrimD.Kruskal（8）在一个无向图中，所有顶点的度数之和等于所有边数的_____倍。A.2B.3C.1D.1.5（9）下面关于图的存储的叙述中正确的是_____。A.用邻接表法存储图，占用的存储空间大小只与图中的边数有关，而与顶点个数无关。B.用邻接表法存储图，占用的存储空间大小与图中的边数和顶点个数都有关。C.用邻接矩阵表法存储图，占用的存储空间大小与图中的边数和顶点个数都有关。D.用邻接矩阵表法存储图，占用的存储空间大小只与图中的边数有关，而与顶点个数无关。（10）设有向无环图G中的有向边集合E={<1，2>,<2，3>,<3，4>,<1，4>},则下列属于该有向图G的一种拓扑排序序列的是_____。A.1，2，3，4B.2，3，4，1C.1，4，2，3D.1，2，4，3(11)设无向图G中的边的集合E={(a,b),(a,e),(a,c)(b,e),(e,d),(d,f),(f,c)},则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为_____。A.aedfcbB.acfebdC.aebcfdD.aedfbc（12）连通图G中有n个顶点，G的生成树是_____连通子图。A.包含G的所有顶点B.包含G的所有边C.不必包含G的所有顶点D.包含G的所有顶点和所有边（13）设某有向图中有n个顶点，则该有向图对应的邻接表中有_____中个表头结点。A.n-1B.nC.n+1D.2n-1（14）设无向图G中有n个顶点、e条边，则其对应的邻接表中的表头结点和边表结点的个数分别为_____。A.n,eB.e,nC.2n,eD.n,2e（15）用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为_____。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和（16）用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的出度为_____。A.第i行非0元素的个数之和B.第i列非0元素的个数之和C.第i行0元素的个数之和D.第i列0元素的个数之和（17）可以判断一个有向图中是否含有回路的方法为_____。A.广度优先遍历B.深度优先遍历C.拓扑排序D.求最短路径6.2填空题（1）一个连通无向图有5个顶点、8条条边，则其生成树将要去掉_____条边。（2）在树结构和图结构中，前驱和后继结点之间分别存在着_____和_____的联系。（3）有n个顶点的连通图至少有_____条边，有n个顶点的强连通图至少有_____条边。（4）一个具有n个顶点的有向图至少有_____条弧。（5）如果不知道一个图是有向图还是无向图，但是知道它的邻接矩阵是非对称的，那么这个图必定是_____。（6）在无向图G的邻接矩阵A中，若A[I][J]=1，则A[J][I]为_____。（7）无向图用邻接矩阵存储，其所有元素之和表示无向图的边数的_____。（8）无向图用邻接表存储，其所有边表结点之和表示无向图的边数的_____。（9）无向图用邻接表存储，顶点vi的度为_____（10）有向图用邻接表存储，顶点vi的度为_____（11）图的遍历方式一般有_____和_____两种。（12）Prim算法的时间复杂度为_____，与边数无关，因此适用于求边稠密的网的最小生成树。（13）如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图_____。6.3画出无向图6.23的邻接矩阵和邻接链表示意图，并写出每个顶点的度。6.4画出有向图6.24的邻接矩阵、邻接链表和逆邻接链表示意图，并写出每个顶点的入度、出度。图6.23题6.3图图6.24题6.4图6.5对应图6.25，写出从v1出发的深度优先查找遍历结果和广度优先查找遍历结果各3个。6.6求图6.26的连通分量。6.7分别用Prim算法按列表方式求出图6,27的最小生成树，并画出最小生成树的示意图。图6.25题6.5图图6.26题6.6图图6.27题6.7图6.8写出图6.28的拓扑排序。6.9试写出下列算法：（1）建立无向图邻接矩阵算法；（2）建立无向网邻接矩阵算法；（3）建立有向图邻接矩阵算法。6.10试写出下列算法：（1）建立无向图邻接链表结构算法；（2）建立无向网邻接链表结构算法。6.11编写算法，在无向图的邻接链表结构上生成无向图的邻接矩阵结构。6.12编写算法，在无向图的邻接矩阵结构上生成无向图的邻接链表结构。6.13已知有m个顶点的无向图，采用邻接矩阵结构存储，问：（1）图中有多少条边？（2）任意两个顶点i和j之间是否有边相连？（3）任意一个顶点的度是多少？6.14已知一个无向图，采用邻接链表结构存储，问：（1）图中有多少条边？（2）任意两个顶点i和j之间是否有边相连？（3）任意一个顶点的度是多少？6.15以图6.29所示的无向图连通图为例，按照深度优先查找遍历的算法编写程序上机运行，并获得正确的结果。图6.28题6.8图图6.29题6.15图习题77.1选择题（1）对长度为n的无序线性表进行顺序查找，查找成功、不成功时的平均数据比较次数分别为_____。A.n2、nB.n+12、n-1（2）指出顺序表{2、5、7、10、14、15、18、23、35、41、52}中用二分法查找关键码12需做_____次关键码比较。A.2B.3C.4D.5（3）对线性表进行折半查找时，必须要求线性表_____。A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链式方式存储，且结点按关键字有序排列（4）设二叉树中有n个结点，则在二叉排序树的平均查找长度为_____。A.O(1)B.O(log2n)C.O(n)D.O(（5）在依次插入序列（50,72,43,85,75,20,35,45,65,30）后建立的二叉搜索树中，查找元素35要进行_____元素间的比较。A.4次B.5次C.7次D.10次（6）在一棵高度为5的理想平衡树中，最少含有16个结点，最多含有_____个结点。A.31B.32C.30D.33(7)对包含N个元素的散列表进行查找，平均查找长度_____。A.为O(log2N)C.不直接依赖于ND.上述三者都不是（8）设散列表中有m个存储单元，散列函数H（key）=key%p,则p最好选择_____。A.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数（9）_____是Hash查找的冲突处理方法。A.求余法B.平方取中法C.二分法D.开放地址法（10）当α的值较小时，散列存储通常比其他存储方式具有_____的查找速度。A.较慢B.较快C.相同D.不确定（11）对线性表进行折半查找最方面结构是_____。A.顺序表B.有序的顺序表C.链表D.有序的链表（12）对一个排好序的线性表用二分法检索表中的元素，被检索的表应当采用_____。A.顺序存储B.链接存储C.散列法存储D.存储表示不受限制（13）若在线性表中采用折半查找法查找元素，该线性应该_____。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构（14）用二分法查找一个长度为10的、排好序的线性表，查找不成功是，最多需要比较_____次。A.5B.2C.4D.1（15）采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块，每块分_____个结点最佳。A.10B.25C.6D.625（16）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用_____查找方法。A.分块B.顺序C.二分D.散列（17）散列函数有一个共同性质，即函数值应按_____取其值域的每一个值。A.最大概率B.最小概率C.同等概率D.平均概率（18）某顺序存储的表格中有90000个元素，以按关键字值额定升序排列，假定对每个元素进行查找的概率相同，且每个元素的关键字的值都不相同，在用顺序查找法查找时，平均比较次数约为_____，最大比较次数为_____。A.25000B.30000C.45000D.90000（19）如果m阶B_树中具有n个关键字，则叶子结点（即查找不成功的结点）为_____。A.n-1B.n+1C.nD.n/2（20）m阶B_树中的所有非终端（除根之外）结点中的关键字个数必须大于或等于_____。A.m/2B.m/2-1C.m/2+1D.m7.2填空题（1）对于长度为n的线性表，若进行顺序查找，则时间复杂度为_____；若采用折半法查找，则时间复杂度为_____。（2）假设上在有序线性表A[1..20]进行折半查找，则比较一次查找成功的结点数为_____，比较两次查找成功的结点数为_____，比较三次查找成功的结点数为_____，比较四次查找成功的结点数为_____，比较五次查找成功的结点数为_____，平均查找长度为_____。（3）在一棵二叉树搜索树中，每个分支结点的左子树上所有结点的值一定_____该结点的值，右子树上所有结点的值一定_____该结点的值。（4）在对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个_____。（5）在一棵m阶B_树上，每个非树根结点的关键字数目最少为_____个，最多为_____。（6）对于线性表（70,34,55,23,65,41,20）进行散列存储时，若选用H(K)=K%7作为散列函数，则散列地址为0的元素有_____个，散列地址为6的元素有_____个。（7）在线性表的散列存储中，装填因子α又称为装填系数，若用m表示散列表的长度，用n表示待散列存储的元素的个数，则α等于_____。（8）在散列表中解决冲突的两种方法是_____和_____。（9）在散列存储中，装填因子α的值越大，_____；α的值越小，_____。（10）散列法存储的基本思想是由_____决定数据的存储地址。（11）最优二叉树（哈夫曼树）、最优查树均为查找路径长度i=1nwihi最小的树，其中对于最优二叉树，n表示_____，对于最优查找树，n表示_____（12）在分块检索中，对于256个元素的线性表最好分成_____块，每块的最佳长度是_____；若每块的长度为_____，其平均检索长度为_____。（13）构造哈希函数的方法有_____。（14）哈希表处理冲突的方法有_____。（15）负载因子（装填因子）是散列表的一个重要参数，它反映散列表的_____。（16）在分块查找中首先查找_____，然后查找相应的_____。（17）散列表的查找效率主要取决与散列表造表时选择的_____和_____。（18）当所有结点的权值都相等时，用这些结点构造的二叉排序树，_____遍历它们得到的序列的顺序是一样的。（19）对两棵具有相同关键字集合但形状不同的二叉排序树，_____遍历它们得到的序列的顺序是一样的。（20）m阶B_树每一个结点的子树个数最多_____m。7.3何谓二叉排序树？7.4简述用二次探测法解决冲突的基本思路。7.5顺序查找时间为O(n),二分查找时间为O(log2n)，散列查找时间为7.6简述用多重散列法解决冲突的基本思路。7.7简述用公共溢出区法解决冲突的基本思路。7.8在结点个数n(n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？7.9设单链表的结点是按关键字从小到大排列的，试写出对词链表的查找算法，并说明是否可以采用折半查找（二分查找）。7.10试写一个判别给定二叉树是否为二叉排序数的算法，设此二叉树以二叉链表做存储结构。7.11通过散列函数hashf(x)=xmod11把一个整数数值转换成散列表下标，现要把数据1、13、12、34、38、33、27、22插入到散列表中。（1）使用线性探查再散列法来构造散列表。（2）使用链地址法来构造散列表。（3）针对这种情况，确定其装填因子，查找成功所需的平均查找次数以及查找不成功所需的平均探查次数。7.12试写出二分查找的递归算法。7.13假设线性表中的结点是按键值递增的顺序存放的，试写一顺序查找法，将岗哨设在高下标端，然后分别求出等概率情况下查找成功和不成功时的平均查找长度。7.14已知纪录关键字集合为（53,17,19,61,98,75,79,63,46,49），要求散列到地址区间（100,101,102,103,104,105,106,107,108,109）内，若产生冲突则开型寻址法的线性探测法解决，要求写出选用的散列函数、形成的散列表、计算出查找成功时的平均查找长度和查找不成功时的平均查找长度。习题88.1选择题。（1）下述排序算法中，稳定的是_____。A.直接选择排序B.直接插入排序C.快速排序D.堆排法（2）下列排序算法中，_____需要的辅助存储空间最大。A.快速排序B.插入排序C.希尔排序D.基数排序（3）下列排序算法中，平均时间复杂度为O(n2)是_____A.快速排序B.堆排法C.归并排序D.冒泡排序（4）在基于关键码比较的排序算法中，_____算法在最坏情况下关键的比较次数不高于O(logA.冒泡排序B.直接插入排序C.二路归并排序D.快速排序（5）一组纪录为{46,79,56,38,84,40}，则采用冒泡排序法按升序排列时第一趟的排序结果是_____。A.46，79，56，38，40，84B.46，56，38，79，40，84C.38，40，46，56，84，79D.38，46，79，56，40，84（6）每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法称为_____排序。A.插入B.堆C.快速D.归并（7）每次从无序表中挑选出一个最小或最大的元素，把它交换到有序表的一端，此种排序方法称为_____排序。A.插入B.堆C.快速D.归并（8）设有一组初始纪录关键字序列（5,2,6,3,8），以第一个纪录关键字5为基准进行一趟快速排序的结果为_____。A.2，3，5，8，6B.3，2，5，8，6C.3，2，5，6，8D.2，3，6，5，8（9）设有n个待排序的纪录关键字，则在堆排序中需要_____个辅助纪录单元。A.1B.nC.nlog2n（10）对于关键字序列（12,13,11,18,60,15,7,18,25,100），用筛选法建堆，必须从关键字值为_____的结点开始。A.100B.12C.60D.15（11）在下列排序方法中，比较次数与纪录的初始排列状态无关的方法是_____。A.直接插入排序B.冒泡排序C.快速排序D.直接选择排序（12）设有关键码初始序列{Q,H,C,Y,P,A,M,S,R,D,F,X},新序列{F,H,C,D,P,A,M,Q,R,S,Y,X}是采用_____方法对初始序列进行第一趟扫描的结果。A.直接插入排序B.二路归并排序C.以第一个元素为分界元素的快速排序D.基数排序（13）在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_____。A.直接插入排序B.直接选择排序C.快速排序D.归并排序（14）排序的算法很多，若按排序的稳定性和不稳定性分类，则_____是不稳定排序。A.冒泡排序B.归并排序C.直接插入排序D.希尔（15）若需在On(log2n)的时间内完成对数组的排序，且要求排序A.快速排序B.堆排序C.归并排序D.直接插入排序（16）将两者各有n个元素的有序表归并成一个有序表，其最少的比较次数是_____。A.nB.2n-1C.2nD.n-1（17）下列排序算法中，时间复杂度不受数据初始状态的影响，恒为O(log2n)A.堆排序B.冒泡排序C.直接插入排序D.快速排序（18）下列排序算法中，_____算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。A.堆排序B.冒泡排序C.快速排序D.Shell排序（19）数据表A中有10000个元素，如果仅要求求出其中最大的10个元素，则采用_____算法最节省时间。A.堆排序B.希尔排序C.快速排序D.直接插入排序（20）如果只想得到1024个元素组成的序列中第5个最小袁术之前的部分排列的序，用_____方法最快。A.冒泡排序B.快速排序C.简单选择排序D.堆排序8.2填空题（1）当待排序的纪录数较大，排序码较随机且对稳定性不做要求时，宜采用_____排序；当待排序的纪录数较大，存储空间允许且要求排序稳定时，宜采用____