浙江理工大学数据结构习题及答案

第一章绪论、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的（）和运算等的学科。①（A）数据元素（B）计算方法（C）逻辑存储（D）数据映像②（A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（）,它必须具备输入、输出和（）5个特性。①（A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法②（A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题数据的机内表示称为数据的存储结构。（）算法就是程序。（）数据元素是数据的最小单位。（）算法的五个特性为：有穷性、输入、输出、完成性和确定性。（）算法的时间复杂度取决于问题的规模和待处理数据的初态。（）三、填空题1.数据逻辑结构包括________、________、_________和 四种类型,其中树形结构和图形结构合称为 。在线性结构中,第一个结点____前驱结点,其余每个结点有且只有 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 个后续结点。在树形结构中,树根结点没有_______结点,其余每个结点有且只有 个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以 。在图形结构中,每个结点的前驱结点数和后续结点数可以 。线性结构中元素之间存在________关系,树形结构中元素之间存在 关系,图形结构中元素之间存在 关系。6.算法的五个重要特性是_______、_______、______、_______、 。7.数据结构的三要素是指______、_______和 。链式存储结构与顺序存储结构相比较,主要优点是 。设有一批数据元素,为了最快的存储某元素,数据结构宜用 结构,为了方便插入一个元素,数据结构宜用 结构。四、算法分析题1.求下列算法段的语句频度及时间复杂度参考答案：、选择题1.C2.C3.C4.A、B5.C6.C、B二、判断题:1、√2、×3、×4、×5、√三、填空题1、线性、树形、图形、集合?；非线性（）2、没有；1；没有；13、前驱；1；后继；任意多个4、任意多个5、一对一；一对多；多对多6、有穷性；确定性；可行性；输入；输出7、数据元素；逻辑结构；存储结构8、插入、删除、合并等操作较方便9、顺序存储；链式存储四、算法分析题for(i=1;i<=n;i++)for(j=1;j<=i;j++)x=x+1;分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外循环有关，因些，时间频度T(n)=1+2+3+…+n=n*(n+1)/2有1/4≤T(n)/n2≤1，故它的时间复杂度为Ｏ(n2),即Ｔ(n)与n2数量级相同。2、分析下列算法段的时间频度及时间复杂度for（i=1;i<=n;i++）for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=i+j-k;分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3++n)由于有1/6≤T（n）/n31，故时间复杂度为Ｏ(n3)第二章线性表一、选择题一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()（A）110（B）108（C）100（D）120向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。（A）64（B）63（C）63.5 （D）7线性表采用链式存储结构时，其地址（）。(A)必须是连续的(B)部分地址必须是连续的(C)一定是不连续的(D)连续与否均可以在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）（A）s->next=p;p->next=s;（B）s->next=p->next;p->next=s;（C）s->next=p->next;p=s;（D）p->next=s;s->next=p;在一个单链表中，若删除p所指结点的后续结点，则执行（）（A）p->next=p->next->next;（B）p=p->next;p->next=p->next->next;（C）p->next=p->next;（D）p=p->next->next;6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继7.线性表是具有n个（）的有限序列（n0)（A）表元素（B）字符（C）数据元素 （D）数据项二、判断题线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（）如果没有提供指针类型的语言，就无法构造链式结构。（）线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（）语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。（）5.要想删除p指针的后继结点，我们应该执行q=p->next；p->next=q->next；free(q)。（）三、填空题已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_______________________。顺序表中逻辑上相邻的元素物理位置()相邻，单链表中逻辑上相邻的元素物理位置_________相邻。线性表L＝（a1a2an）采用顺序存储，假定在不同的n1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________________________在非空双向循环链表中，在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;______________________;已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，分别实现：（1）表尾插入s结点的语句序列是_______________________________(2)表尾插入s结点的语句序列是_______________________________p->next=s;p=L;L=s;p->next=s->next;s->next=p->next;s->next=L;s->next=null;while(p->next!=Q)?p=p-next;while(p->next!=null)p=p->next;、算法设计题试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点c函数。某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格为h的电视机，试编写算法修改原链表。某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。5.线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编C函数删除线性表中值介于ab（ab）之间的元素。6.设A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。n=m，且ai=bi（0i<n），A=B；n<m，且ai=bi（0i<n），A<B；若存在一个j，j<mj<n，且ai=bi（0i<j），若aj<bj，则A<B，否则A>B。试编写一个比较A和B的C函数，该函数返回-1或0或1，分别表示A<B或A=B或A>B。7.试编写算法,删除双向循环链表中第k个结点。线性表由前后两部分性质不同的元素组成(a0,a1,...,an-1,b0,b1,...,bm-1),mn为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析两种存储方式下算法的时间和空间复杂度。用循环链表作线性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存储结构,头指针分别为ahbh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。试写出把线性链表改为循环链表的C函数。己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。参考答案：、选择题1.B2.C3.D4.B5.A6.A7、C二、判断题:参考答案：1、×2、√3、×4、×5、√三、填空题1、s->next=p->next;p->next=s;2、一定；不一定3、n/24、q->prior=p;5、(1)6)3)(2)2)9）1)7)四、算法设计题1、#include"stdio.h"#include"malloc.h"typedefstructnode{intdata;structnode*link;}NODE;intaver(NODE*head){inti=0,sum=0,ave;NODE*p;p=head;while(p!=NULL){p=p->link;++i;sum=sum+p->data;}ave=sum/i;return(ave);}2、#include"stdio.h"#include"malloc.h"typedefstructnode{intdata;/*假设数据域为整型*/structnode*link;}NODE;voiddel_link(NODE*head,intx)/*删除数据域为x的结点*/{NODE*p,*q,*s;p=head;q=head->link;while(q!=head){if(q->data==x){p->link=q->link;s=q;q=q->link;free(s);}else{p=q;q=q->link;}}}3、voiddel(NODE*head,floatprice,intnum){NODE*p,*q,*s;p=head;q=head->next;while(q->price<price&&q!=head){p=q;q=q->next;}if(q->price==price)q->num=q->num-num;elseprintf("无此产品");if(q->num==0){p->next=q->next;free(q);}}4、#include"stdio.h"#include"malloc.h"typedefstructnode{floatprice;intnum;structnode*next;}NODE;voidins(NODE*head,floatprice,intnum){NODE*p,*q,*s;p=head;q=head->next;while(q->price<price&&q!=head){p=q;q=q->next;}if(q->price==price)q->num=q->num+num;else{s=(NODE*)malloc(sizeof(NODE));s->price=price;s->num=num;s->next=p->next;p->next=s;}}5、顺序表：算法思想：从0开始扫描线性表，用k记录下元素值在a与b之间的元素个数，对于不满足该条件的元素，前移k个位置，最后修改线性表的长度。voiddel（elemtypelist[]，int*n，elemtypea，elemtypeb）{inti=0，k=0；while（i<n){if(list[i]>=a&&list[i]<=b)k++;elselist[i-k]=list[i];i++;}*n=*n-k;/*修改线性表的长度*/}循环链表:voiddel(NODE*head,elemtypea,elemtypeb){NODE*p,*q;p=head;q=p->link;/*假设循环链表带有头结点*/while(q!=head&&q->data<a){p=q;q=q->link;}while(q!=head&&q->data<b){r=q;q=q->link;free(r);}if(p!=q)p->link=q;}6、#defineMAXSIZE100intlistA[MAXSIZE],listB[MAXSIZE];intn,m;intcompare(inta[],intb[]){inti=0;while(a[i]==b[i]&&i<n&&i<m)i++;if(n==m&&i==n)return(0);if(n<m&&i==n)return(-1);if(n>m&&i==m)return(1);if(i<n&&i<m)if(a[i]<b[i])return(-1);elseif(a[i]>b[i])return(1);}7、voiddel(DUNODE **head,inti){DUNODE*p;if(i==0){*head=*head->next;*head->prior=NULL;return(0);}Else{for(j=0;j<i&&p!=NULL;j++)p=p->next;if(p==NULL||j>i)return(1);p->prior->next=p->next;>next->prior=p->proir;free(p);return(0);}8.顺序存储:voidconvert(elemtypelist[],intl,inth)/*将数组中第l个到第h个元素逆置*/{inti;elemtypetemp;for(i=h;i<=(l+h)/2;i++){temp=list[i];list[i]=list[l+h-i];list[l+h-i]=temp;}}voidexchange(elemtypelist[],intn,intm);{convert(list,0,n+m-1);convert(list,0,m-1);convert(list,m,n+m-1);}该算法的时间复杂度为O(n+m),空间复杂度为O(1)链接存储:(不带头结点的单链表)typedefstructnode{elemtypedata;structnode*link;}NODE;voidconvert(NODE**head,intn,intm){NODE*p,*q,*r;inti;p=*head;q=*head;for(i=0;i<n-1;i++)q=q->link;/*q指向an-1结点*/r=q->link;>link=NULL;while(r->link!=NULL)r=r->link;/*r指向最后一个bm-1结点*/*head=q;>link=p;}该算法的时间复杂度为O(n+m),但比顺序存储节省时间(不需要移动元素,只需改变指针),空间复杂度为O(1)9.typedefstructnode{elemtypedata;structnode*link;}NODE;NODE *union(NODE *ah,NODE*bh){NODE *a,*b,*head,*r,*q;head=ah;a=ah;b=bh;while(a->link!=ah&&b->link!=bh){r=a->link;q=b->link;a->link=b;b->link=r;a=r;b=q;}if(a->link==ah)/*a的结点个数小于等于b的结点个数*/{>link=b;while(b->link!=bh)b=b->link;>link=head;}if(b->link==bh)/*b的结点个数小于a的结点个数*/{r=a->link;a->link=b;b->link=r;}return(head);}该算法的时间复杂度为O(n+m),其中n和m为两个循环链表的结点个数.10.typedefstructnode{elemtypedata;structnode*link;}NODE;voidanalyze(NODE*a）{NODE *rh，*qh，*r,*q,*p；inti=0，j=0；/*i为序号是奇数的结点个数j为序号是偶数的结点个数*/p=a；rh=（NODE*）malloc（sizeof（NODE））/*rh为序号是奇数的链表头指针*/qh=(NODE*)malloc(sizeof(NODE));/*qh为序号是偶数的链表头指针*/r=rh;q=qh;while(p!=NULL){r->link=p;r=p;i++;p=p->link;if(p!=NULL){q->link=p;q=p;j++;p=p->link;}}rh->data=i;r->link=rh;qh->data=j;q->link=qh;}11.typedefstructnode{elemtypedata;structnode*link;}NODE;voidchange(NODE *head){NODE *p;p=head;if(head!=NULL){while(p->link!=NULL)p=p->link;p->link=head;}}12.typedefstructnode{elemtypedata;structnode*link;}NODE;voiddel(NODE*x,NODE*y){NODE*p,*q;elemtyped1;p=y;q=x;while(q->next!=NULL)/*把后一个结点数据域前移到前一个结点*/{p->data=q->data;q=q->link;p=q;p->link=NULL;/*删除最后一个结点*/free(q);}第三章栈和队列一、选择题一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。（A）edcba（B）decba（C）dceab（D）abcde栈结构通常采用的两种存储结构是（）。（A）线性存储结构和链表存储结构（B）散列方式和索引方式（C）链表存储结构和数组（D）线性存储结构和非线性存储结构3.判定一个栈ST(最多元素为m0)为空的条件是（）。（A）ST-〉top!=0（B）ST-〉top==0（C）ST-〉top!=m0（D）ST-〉top=m0判定一个栈ST(最多元素为m0)为栈满的条件是（）。（A）ST->top!=0（B）ST->top==0（C）ST->top!=m0-1（D）ST->top==m0-1一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是frontrear则当前队列中的元素个数是（）（A）(rear-front+m)%m（B）rear-front+1（C）rear-front-1（D）rear-front7.栈和队列的共同点是（）（A）都是先进后出（B）都是先进先出（C）只允许在端点处插入和删除元素（D）没有共同点8.表达式a*(b+c)-d的后缀表达式是（）。（A）abcd*+-（B）abc+*d-（C）abc*+d-（D）-+*abcd9.4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（ ）(A)a4，a3，a2，a1 (B)a3，a2，a4，a1(C)a3，a1，a4，a2 (D)a3，a4，a2，a110.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（ ）(A)rear－qulen (B)rear－qulen＋m(C)mqulen (D)1＋（rearmqulen）二、填空题1.栈的特点是_______________________,队列的特点是 。2.线性表、栈和队列都是_____________________结构,可以在线性表的 位置插入和删除元素对于栈只能在________插入和删除元素对于队列只能在 插入元素和 删除元素。一个栈的输入序列是12345,则栈有输出序列12345是 。(正确/错误)设栈S和队列Q的初始状态皆为空，元素a1a2a3a4a5a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3a5a4a6a2a1S少应该容纳个元素。三、算法设计题假设有两个栈s1s2共享一个数组stack[M],其中一个栈底设在stack[0]处，另一个栈底设在stack[M-1]处。试编写对任一栈作进栈和出栈运算的Cpush（x,i)和pop(i),i=l,2。其中i=1表示左边的栈，,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。一个栈s1用于插入元素,另一个栈s2用于删除元素.参考答案：一、选择题1.C2.A3.B4.B5.B6.B7、C8、C9、C10、D二、填空题1、先进先出；先进后出2、线性；任何；栈顶；队尾；对头3、正确的4、3三、算法设计题1.#defineM100elemtypestack[M];inttop1=0,top2=m-1;intpush(elemtypex,inti){if(top1-top2==1)return(1);/*上溢处理*/elseif(i==1)stack[top1++]=x;if(i==2)stack[top2--]=x;return(0);}intpop(elemtype*px,inti){if(i==1)if(top1==0)return(1);else{top1--;*px=stack[top1];return(0);}elseif(i==2)if(top2==M-1)return(1);else{top2++;*px=stack[top2];return(0);}}2.elemtypes1[MAXSIZE],s2[MAZSIZE];inttop1,top2;voidenqueue(elemtypex){if(top1==MAXSIZE)return(1);else{push(s1,x);return(0);}}voiddequeue(elemtype*px){elemtypex;top2=0;while(!empty(s1)){pop(s1,&x);push(s2,x);}pop(s2,&x);while(!empty(s2)){pop(s2,&x);push(s1,x);}}第四章串一、选择题1.下列关于串的叙述中，正确的是（）(A)一个串的字符个数即该串的长度(B)一个串的长度至少是1(C)空串是由一个空格字符组成的串(D)两个串S1和S2若长度相同，则这两个串相等2.字符串"abaaabab"的nextval值为(?)(A)(0,1,01,1,0,4,1,0,1)(B)(0,1,0,0,0,0,2,1,0,1)(C)(0,1,0,1,0,0,0，1,1)(D)(0,1,0,1,0,1,0,1,1)字符串满足下式,其中headtail的定义同广义表类似,如headxyzx,tail(xyzyzs=()。concat(head(tail(s)),head(tail(tail(s))))=dc(A)abcd(B)acbd(C)acdb(D)adcb串是一种特殊的线性表,其特殊性表现在（）(A)可以顺序存储(B)数据元素是一个字符(C)可以链式存储(D)数据元素可以是多个字符设串S1ABCDEFGs2PQRSTCONCAT（X，Y）返回XY串的连接串，SUBSTR（SIJ）返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S12LENGTH（S2））SUBSTR（S1LENGTH（S2）2））的结果串是（）（A）BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF二、算法设计分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。在一般链接存储(一个结点存放一个字符)方式下,写出采用简单算法实现串的模式匹配的C语言函数intL_index(t,p)。参考答案：一、选择题1.A2.B3.D4.D5.D二、算法设计1.顺序存储：#include"string.h"#defineMAXN100chars[MAXN];intS_strlen(chars[]){inti;for(i=0;s[i]!='\0';i++);return(i);}voidS_strcpy(chars1[],chars2[])//4.3题{inti;for(i=0;s1[i]!='\0';i++)s2[i]=s1[i];s2[i]='\0';}一般链接存储：#include"stdio.h"typedefstructnode{chardata;structnode*link;}NODE;NODE*L_strcpy(NODE*s1){NODE*s2,*t1,*t2,*s;if(s1==NULL)return(NULL);else{t1=s1;t2=(NODE*)malloc(sizeof(NODE));s2=t2;while(t1!=NULL){s=(NODE*)malloc(sizeof(NODE));s->data=t1->data;t2->link=s;t2=s;t1=t1->link;}t2->link=NULL;s=s2;s2=s2->link;free(s);return(s2);}}2.#include"stdio.h"typedefstructnode{chardata;structnode*link;}NODE;intL_index(NODE*t,NODE*p){NODE*t1,*p1,*t2;?inti;t1=t;i=1;while(t1!=NULL){p1=p;t2=t1->link;while(p1->data==t1->data&&p1!=NULL){p1=p1->link;t1=t1->link;}if(p1==NULL)return(i);i++;t1=t2;}return(0);}第五章数组和广义表一、选择题常对数组进行的两种基本操作是（）（A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从04,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素()的起始地址相同。（A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4]数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。（A）80（B）100（C）240（D）270数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（）。（A）SA+141（B）SA+144（C）SA+222（D）SA+225数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。（A）SA+141（B）SA+180（C）SA+222（D）SA+225稀疏矩阵一般的压缩存储方法有两种,即（）。（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（）。（A）正确（B）错误设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B[1,n(n-1)/2]中,对下三角部分中任一元素ai,j(i<=j),在一组数组B的下标位置k的值是（）。（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二、填空题己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是 。二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是 。有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且A[0][0]=1),则A[8][5]的地址是 。nn列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是 。若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A[0][0]的存储地址为1000,元素A[1][3]的存储地址为 ,该数组共占用_______________个存储单元。三、算法设计1.如果矩阵A中存在这样的一个元素A[i][j]满足条件:A[i][j]是第i行中值最小的元素,且又是第j列中值最大的元素,则称之为该矩阵的一个马鞍点。编写一个函数计算出1×n的矩A的所有马鞍点。2.n只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王。n和m由键盘输入,打印出最后剩下的猴子号。编写一程序实现上述函数。3.数组和广义表的算法验证程序编写下列程序:(1)求广义表表头和表尾的函数head()和tail()。(2)计算广义表原子结点个数的函数count_GL()。(3)计算广义表所有原子结点数据域(设数据域为整型〉之和的函数sum_GL()。参考答案：一、选择题1.C2.B3.C4.C5.B6.C7、B8、B二、填空题1、loc(A[0][0])+(n*i+j)*k2、3323、424、i*(i+1)/2+j+15、1039；72三、算法设计题1.算法思想：依题意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,则该元素A[i][j]便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。因此,实现本题功能的程序如下:#include<stdio.h>#definem3#definen4voidminmax(inta[m][n]){inti1,j,have=0;intmin[m],max[n];for(i1=0;i1<m;i1++)/*计算出每行的最小值元素,放入min[m]之中*/{min[i1]=a[i1][0];for(j=1;j<n;j++)if(a[i1][j]<min[i1])min[i1]=a[i1][j];}for(j=0;j<n;j++)/*计算出每列的最大值元素,放入max[n]之中*/{max[j]=a[0][j];for(i1=1;i1<m;i1++)if(a[i1][j]>max[j])max[j]=a[i1][j];}for(i1=0;i1<m;i1++)for(j=0;j<n;j++)if(min[i1]==max[j]){printf("(%d,%d):%d\n",i1,j,a[i1][j]);have=1;}if(!have)printf("没有鞍点＼n");}2.算法思想:本题用一个含有n个元素的数组a,初始时a[i]中存放猴子的编号i,计数器似的值为0。从a[i]开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出a[i]值(退出圈外的猴子的编号),同时将a[i]的值改为O(以后它不再参加报数),计数器值重新置为0。该函数一直进行到n只猴子全部退出圈外为止,最后退出的猴子就是大王。因此,现本题功能的程序如下:#include"stdio.h"main(){inta[100];intcount,d,j,m,n;scanf("%d%d",&m,&n);/*n>=m*/for(j=0;j<n;j++)a[j]=j+1;count=0;d=0;while(d<n)for(j=0;j<n;j++)if(a[j]!=0){count++;if(count==m){printf("%d",a[j]);a[j]=0;count=0;d++;}}}3.#include"stdio.h"#include"malloc.h"typedefstructnode{inttag;union{structnode*sublist;chardata;}dd;structnode*link;}NODE;NODE*creat_GL(char**s){NODE*h;charch;ch=*(*s);(*s)++;if(ch!='\0'){h=(NODE*)malloc(sizeof(NODE));if(ch=='('){h->tag=1;h->dd.sublist=creat_GL(s);}Else{h->tag=0;h->dd.data=ch;}}elseh=NULL;ch=*(*s);(*s)++;if(h!=NULL)if(ch==',')h->link=creat_GL(s);elseh->link=NULL;return(h);}voidprn_GL(NODE*p){if(p!=NULL){if(p->tag==1){printf("(");if(p->dd.sublist==NULL)printf("");elseprn_GL(p->dd.sublist);}elseprintf("%c",p->dd.data);if(p->tag==1)printf(")");if(p->link!=NULL){printf(",");prn_GL(p->link);}}}NODE*copy_GL(NODE*p){NODE*q;if(p==NULL)return(NULL);q=(NODE*)malloc(sizeof(NODE));q->tag=p->tag;if(p->tag)q->dd.sublist=copy_GL(p->dd.sublist);elseq->dd.data=p->dd.data;q->link=copy_GL(p->link);return(q);}NODE*head(NODE*p)/*求表头函数*/{return(p->dd.sublist);}NODE*tail(NODE*p)/*求表尾函数*/{return(p->link);}intsum(NODE*p)/*求原子结点的数据域之和函数*/{intm,n;if(p==NULL)return(0);else{if(p->tag==0)n=p->dd.data;elsen=sum(p->dd.sublist);if(p->link!=NULL)m=sum(p->link);elsem=0;return(n+m);}}intdepth(NODE*p)/*求表的深度函数*/{inth,maxdh;NODE*q;if(p->tag==0)return(0);elseif(p->tag==1&&p->dd.sublist==NULL)return1;else{maxdh=0;while(p!=NULL){if(p->tag==0)h=0;else{q=p->dd.sublist;h=depth(q);}if(h>maxdh)maxdh=h;p=p->link;}return(maxdh+1);}}main(){NODE*hd,*hc;chars[100],*p;p=gets(s);hd=creat_GL(&p);prn_GL(head(hd));prn_GL(tail(hd));hc=copy_GL(hd);printf("copyafter:");prn_GL(hc);printf("sum:%d\n",sum(hd));printf("depth:%d\n",depth(hd));}第六章树和二叉树一、选择题在线索化二叉树中,t所指结点没有左子树的充要条件是（）（A）t-〉left==NULL（B）t-〉ltag==1（C）t-〉ltag=1t-〉left=NULL（D）以上都不对二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法（A）正确（B）错误（C）不同情况下答案不确定二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（）(A)正确(B)错误（C）不同情况下答案不确定由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（）（A）正确（B）错误（C）不同情况下答案不确定设高度为h的二叉树上只有度为02的结点,则此类二叉树中所包含的结点数至少为（）。（A）2h（B）2h-1（C）2h+1（D）h+1已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（（A）acbed（B）decab（C）deabc（D）cedba如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（）（A）前序（B）中序（C）后序（D）层次序某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。（A）bdgcefha（B）gdbecfha（C）bdgaechf（D）gdbehfca二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）（A）正确（B）错误（C）不同情况下答案不确定按照二叉树的定义,具有3个结点的二叉树有（）种。（A）3（B）4（C）5（D）6在一非空二叉树的中序遍历序列中,根结点的右边（）（A）只有右子树上的所有结点（B）只有右子树上的部分结点（C）只有左子树上的部分结点（D）只有左子树上的所有结点12.树最适合用来表示（）。（A）有序数据元素（B）无序数据元素（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）（A）不发生改变（B）发生改变（C）不能确定D.以上都不对实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（储结构。（A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构15.对一个满二叉树,m个树叶,n个结点,深度为h,则（）（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（）（A）uwvts（B）vwuts（C）wuvts（D）wutsv17.具有五层结点的二叉平衡树至少有（）个结点。（A）10（B）12（C）15（D）17二、判断题二叉树中任何一个结点的度都是2。（）由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（）一棵哈夫曼树中不存在度为1的结点。（）平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（）三、填空题1.指出树和二叉树的三个主要差别___________,___________, 。从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是____________若结点A有三个兄弟(包括A本身),并且BA的双亲结点,B的度是_______________若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域。已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________。已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC,并写出前序序列_________________。找出满足下列条件的二叉树1）先序和中序遍历，得到的结点访问顺序一样。_________________________2）后序和中序遍历，得到的结点访问顺序一样。_________________________3）先序和后序遍历，得到的结点访问顺序一样。__________________________一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？____________________一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有 个。含有100个结点的树有 条边。四、问答题一棵深度为hm叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:(1)第k层结点数(1≤k≤h)。(2)整棵树结点数。编号为i的结点的双亲结点的编号。编号为i的结点的第j个孩子结点(若有)的编号。证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：k-1）n1+13.已知一组元素为(50,28,78,65,23,36,13,42,71）,请完成以下操作:(1)画出按元素排列顺序逐点插入所生成的二叉排序树BT。分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数。画出在BT中删除(23〉后的二叉树。有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数。有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权)。求出每个字符的晗夫曼编码。求出传送电文的总长度。(4)并译出编码系列1100011100010101的相应电文。五、算法设计已知一棵具有n个结点的完全二叉树被顺序存储在一维数组A[n]中,试编写一个算法输出A[i]结点的双亲和所有孩子。参考答案：一、选择题1.B2.B3.A4.B5.B6.D7A8、D9、B10、C11、A12、C13、A14、C15、D16、C17C二、判断题1×2×3√4√三、填空题1、①树的结点个数至少为1，而二叉树的结点个数可以为0；②树种结点的最大读书没有限制，而二叉树结点的最大度数不能超过2；③树的结点无左右之分，而二叉树的结点有左右之分。2、树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。3、44、n+15、DGEBHJIFCA6、ABDEGCEH7、①无左子树②无右子树③仅一个结点的二叉树8、最大n,最小┕log2n┙+19、2210、99四、问答题1.答：（1）mk-1（2）（mh-1）/（m-1）（3）i=1时，该结点为根，无双亲结点；否则其双亲结点的编号为（i+m-2）/m（4）编号为i的结点的第j个孩子结点(若有)的编号为i*m+（j-（m-1））2.证明：设树结点为n,则n=n0+n1因是满k叉树,每个非叶子结点引出k个分支，故有k*n1个分支。除根外，每个分支引出一个结点，则树共有k*n1+1个结点。所以n0+n1=k*n1+1n0=(k-1)*n1+1五、算法设计voidparent(inta[],intn,inti){if(i==1){printf("无双亲\n");return;}Elseprintf("双亲:%d\n",a[(i-1)/2]);}voidchild(inta[],intn,inti)/*i为序号*/{intqueue[MAX],front=0,tail=0,p;/*队列作为辅助，存储孩子的序号*/queue[0]=i;tail++;while(front<tail){p=queue[front++];if(p!=i)printf("%d",a[p-1]);/*自身不输出*/if(2*p<=n)queue[tail++]=2*p;if(2*p+1<=n)queue[tail++]=2*p+1;}main(){inta[MAX],n,i;printf("请输入二叉树的结点个数:");scanf("%d",&n);input(a,n);printf("请输入i:");scanf("%d",&i);parent(a,n,i);child(a,n,i);}二叉树其他运算的算法（只作参考）#include"stdio.h"#include"malloc.h"typedefstructnode{chardata;structnode*lchild,*rchild;}NODE;NODE*T;voidcreate(NODE**T)//创建二叉树{charch;ch=getchar();if(ch=='')*T=NULL;else{*T=(NODE*)malloc(sizeof(NODE));(*T)->data=ch;create(&((*T)->lchild));create(&((*T)->rchild));?}}voidinorder(NODE*p)//中序编历二叉树{if(p!=NULL){inorder(p->lchild);??printf("%c",p->data);?inorder(p->rchild);???}?}intnum=0;voidcount(NODE*p)//统计出二叉树中单孩子的结点数方法1{if(p!=NULL){count(p->lchild);if(p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL)num++;count(p->rchild);}}voidcount1(NODE*p,int*num1){if(p!=NULL){count1(p->lchild,num1);if(p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL)(*num1)++;count1(p->rchild,num1);}}intonechild(NODE*t)//统计出二叉树中单孩子的结点数方法2{intnum1,num2;if(t==NULL)return(0);elseif(t->lchild==NULL&&t->rchild!=NULL||t->lchild!=NULL&&t->rchild==NULL)return(onechild(t->lchild)+onechild(t->rchild)+1);else{num1=onechild(t->lchild);num2=onechild(t->rchild);return(num1+num2);}}intsum(NODE*t)//统计出二叉树中所有结点数{if(t==NULL)return(0);elsereturn(sum(t->lchild)+sum(t->rchild)+1);}intleaf(NODE*t)//统计出二叉树中叶子结点数{if(t==NULL)return(0);elseif(t->lchild==NULL&&t->rchild==NULL)return(leaf(t->lchild)+leaf(t->rchild)+1);elsereturn(leaf(t->lchild)+leaf(t->rchild));}voidpreorder1(NODE*root)//非递归二叉树前序编历{NODE*p,*s[100],*q;//q为p的双亲结点inttop=0;//top为栈顶指针p=root;q=p;while((p!=NULL)||(top>0)){while(p!=NULL){printf("%d",p->data);s[++top]=p;p=p->lchild;}p=s[top--];p=p->rchild;}}voiddelk(NODE**root,chark)//删去并释放数据值为k的叶结点{NODE*p,*s[100],*q;//q为p的双亲结点inttop=0;//top为栈顶指针if((*root)==NULL)return;if((*root)->lchild==NULL&&(*root)->rchild==NULL&&(*root)->data==k){*root=NULL;return;}p=*root;q=p;while((p!=NULL)||(top>0)){while(p!=NULL){if(p->lchild==NULL&&p->rchild==NULL&&p->data==k){if(q->lchild==p)q->lchild=NULL;elseq->rchild=NULL;free(p);return;}s[++top]=p;q=p;p=p->lchild;}p=s[top--];q=p;p=p->rchild;}}voidlev_traverse(NODE*T)//按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息{NODE*q[100],*p;inthead,tail;q[0]=T;head=0;tail=1;while(head<tail){p=q[head++];printf("%c",p->data);if(p->rchild!=NULL)q[tail++]=p->rchild;if(p->lchild!=NULL)q[tail++]=p->lchild;}}intdepth(NODE*t)//求二叉树的深度{intnum1,num2;if(t==NULL)return(0);if(t->lchild==NULL&&t->rchild==NULL)return(1);else{num1=depth(t->lchild);num2=depth(t->rchild);if(num1>num2)return(num1+1);elsereturn(num2+1);}}intonechild3(NODE*root)//非递归统计出二叉树共有多少个度为1的结点{NODE*p,*s[100];inttop=0,num=0;//top为栈顶指针p=root;while((p!=NULL)||(top>0)){while(p!=NULL){if(p->lchild!=NULL&&p->rchild==NULL||p->lchild==NULL&&p->rchild!=NULL)num++;s[++top]=p;p=p->lchild;}p=s[top--];p=p->rchild;}returnnum;}intlike(NODE*t1,NODE*t2)//判定两颗二叉树是否相似{intlike1,like2;if(t1==t2&&t2==NULL)return(1);elseif(t1==NULL&&t2!=NULL||t1!=NULL&&t2==NULL)return(0);else{like1=like(t1->lchild,t2->lchild);like2=like(t1->rchild,t2->rchild);return(like1&&like2);}}chara[100];//数组顺序存储二叉树voidchange(NODE*t,inti)//将二叉树的链接存储转换为顺序存储{if(t!=NULL){a[i]=t->data;change(t->lchild,2*i);change(t->rchild,2*i+1);}}intcomplete(NODE*t)//判断二叉树是否为完全二叉树{inti,flag=0;change(t,1);for(i=1;i<100;i++){if(!flag&&a[i]=='\0')flag=1;if(flag&&a[i]!='\0')break;}if(i==100)return(1);elsereturn(0);}第七章图一、判断题一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。（）一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。（）一个对称矩阵一定对应着一个无向图。（）一个有向图的邻接矩阵一定是一个非对称矩阵。（）二、选择题在一个图中,所有顶点的度数之和等于所有边数的（）倍。（A）1/2（B）1（C）2（D）4在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。（A）1/2（B）1（C）2（D）4一个有n个顶点的无向图最多有（）条边。（A）n（B）n(n-1)（C）n(n-1）/2（D）2n4.具有4个顶点的无向完全图有（）条边。（A）6（B）12（C）16（D）20具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。（A）5（B）6（C）7（D）8在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。（A）n（B）n+1（C）n-1（D）n/2对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（）（A）n（B）(n-1)2（C）n-1（D）n2对于一个具有ne条边的无向图,若采用邻接表表示,则表头向量的大小为（），所有邻接表中的结点总数是（）。①（A）n（B）n+1（C）n-1（D）n+e②（A）e/2（B）e（C）2e（D）n+e采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。（A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。（A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）（A）求关键路径的方法（B）求最短路径的Dijkstm方法（C）宽度优先遍历算法（D）深度优先遍历算法Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{125}，边的集合TE＝{（12），（2，5）}，要选取下一条权值最小的边，应当从（）组中选取。(A){（1，4），（3，4），（3，5），（2，5）(B){（5，4），（5，3），（5，6）}(C){（1，2），（2，3），（3，5）}(D){（3，4），（3，5），（4，5），（1，4）}三、填空题1.n个顶点的连通图至少 条边。在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是 。在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是 条。如果从一个顶点出发又回到该顶点，则此路径叫做 。如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是____________。若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的 遍历。一个连通图的生成树是该图的________连通子图若这个连通图有n个顶点,则它的生成树有 条边。四、算法设计：试在无向图的邻接矩阵和邻接链表上实现如下算法：往图中插入一个顶点往图中插入一条边删去图中某顶点删去图中某条边下面的伪代码是一个广度优先搜索算法，试以下图中的v0为源点执行该算法，请回答下述问题：对图中顶点vn+1，它需入队多少次？它被重复访问多少次?(2)若要避免重复访问同一个顶点的错误，应如何修改此算法?voidBFS(ALGraph*G,intk){//以下省略局部变量的说明，visited各分量初值为假InitQueue(&Q);//置空队列EnQueue(&Q,k);//k入队while(!QueueEmpty(&Q)){i=DeQueue(&Q);//vi出队visited[i]=TRUE;//置访问标记printf("%c",G->adjlist[i].vertex;//访问vifor(p=G->adjlist[i].firstedge;p;p=p->next)//依次搜索vi的邻接点vj(不妨设p->adjvex=j)if(!visited[p->adjvex])//若vj没有访问过EnQueue(&Q,p->adjvex);//vj入队}//endofwhile}//BFS试以邻接表和邻接矩阵为存储结构，分别写出基于DFSBFS遍历的算法来判别顶点vivj(i<>j)之间是否有路径。试分别写出求DFSBFS生成树(或生成森林)的算法，要求打印出所有的树边。写一算法求连通分量的个数并输出各连通分量的顶点集。设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法：(1)求顶点vi到顶点vj(i<>j)的最短路径求源点vi到其余各顶点的最短路径要求输出路径上的所有顶点(提示：利用BFS遍历的思想)以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。参考答案：一、判断题1、×2、√3、×4、×二、选择题1.C2.B3.C4.A5.A6.C7B8、A、C9、A10、D11、D12、三、填空题1、n-12、i在前，j在后3、m/24、回路5、强连通图6、按层7、极大；n-1第八章查找一、判断题用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。（）哈希表的查找不用进行关键字的比较。（）哈希表的定义函数H（key）=key%p(p<=m)这种方法是直接定址法。（）装填因子α的值越大，就越不容易发生冲突。()选择hash函数的标准为：随机性好、均匀性好和尽量避免冲突。()二、填空题顺序查找法的平均查找长度为__________，二分查找法的平均查找长度为 ，分块查找法(以顺序查找确定块)的平均查找长度为 ，分块查找法(以二分查找确定块〉的平均查找长度为 ，哈希表查找法采用链接法处理冲突时的平均查找长度为_________。在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________二分查找的存储结构仅限于_________,且是 。在分块查找方法中,首先查找__________,然后再查找相应的 。长度为255的表,采用分块查找法,每块的最佳长度是 。在散列函数H(key)=key%p中,p应取 。假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为 ,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为 ,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为 ,平均查找长度为 。对于长度为n的线性表,若进行顺序查找,则时间复杂度为 若采用二分法查找,则时间复杂度为 。9.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为2990元素时,分别需要________次和 次比较才能查找成功；若采用顺序查找时,分别需要___________次和 次比较才能查找成功。三、选择题1.顺序查找法适合于存储结构为（）的线性表。（A）散列存储（B）顺序存储或链接存储（C）压缩存储（D）索引存储2.对线性表进行二分查找时,要求线性表必须（）。（A）以顺序方式存储（B）以链接方式存储（C）以顺序方式存储,且结点按关键字有序排序（D）以链接方式存储,且结点按关键字有序排序采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为（）（A）n（B）n/2（C）(n+1)/2（D）(n-1)/2采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为（）（A）O(n2)（B）O(log2n)（C）O(n)（D）O(log2n)5.二分查找和二叉排序树的时间性能（）。（A）相同?（B）不相同?（C）无法比较6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时,（）次比较后查找成功。（A）1（B）2（C）4