人武学院《数据结构》课后习题答案及期末综合练习.doc 35页

'第十章内部排序一、基本知识题答案1.排序：将一组杂乱无序的数据按一定的规律顺次排列起来叫做排序。内部排序：数据存储在内存中，并在内存中加以处理的排序方法叫内部排序。堆：堆是一个完全二叉树，它的每个结点对应于原始数据的一个元素，且规定如果一个结点有儿子结点，此结点数据必须大于或等于其儿子结点数据。稳定排序：一种排序方法，若排序后具有相同关键字的记录仍维持原来的相对次序，则称之为稳定的，否则称为不稳定的。2.回答下面问题(1)5000个无序的数据，希望用最快速度挑选出其中前10个最大的元素，在快速排序、堆排序、归并排序和基数排序中采用哪种方法最好？为什么？(2)大多数排序算法都有哪两个基本操作？答：(1)采用堆排序最好。因为以上几种算法中，快速排序、归并排序和基数排序都是在排序结束后才能确定数据元素的全部顺序，而无法知道排序过程中部分元素的有序性。堆排序则每次输出一个最大（或最小）的元素，然后对堆进行调整，保证堆顶的元素总是余下元素中最大（或最小）的。根据题意，只要选取前10个最大的元素，故采用堆排序方法是合适的。(2)两个基本操作：比较两个关键字的大小、改变指向记录的指针或移动记录本身。3.3.已知序列{17，25，55，43，3，32，78，67，91}，请给出采用冒泡排序法对该序列作递增排序时每一趟的结果。答：采用冒泡排序法排序时的各趟结果如下：初始：17，25，55，43，3，32，78，67，91第1趟：17，25，43，3，32，55，67，78，91第2趟：17，25，3，32，43，55，67，78，91第3趟：17，3，25，32，43，55，67，78，91第4趟：3，17，25，32，43，55，67，78，91第5趟：3，17，25，32，43，55，67，78，91第5趟无元素交换，排序结束。4.已知序列{491，77，572，16，996，101，863，258，689，325}，请分别给出采用快速排序、堆排序和基数排序法对该序列作递增排序时每一趟的结果。答：采用快速排序法排序时的各趟结果如下：初始：491，77，572，16，996，101，863，258，689，325第1趟：[325，77，258，16，101]491[863，996，689，572]第2趟：[101，77，258，16]325，491[863，996，689，572]第3趟：[16，77]101[258]325，491[863，996，689，572]第4趟：16[77]101[258]325，491[863，996，689，572]第5趟：16，77，101[258]325，491[863，996，689，572]第6趟：16，77，101，258，325，491[863，996，689，572]第7趟：16，77，101，258，325，491[572，689]863[996]第8趟：16，77，101，258，325，491，572[689]863[996]第9趟：16，77，101，258，325，491，572，689，863[996]第10趟：16，77，101，258，325，491，572，689，863，996采用堆排序法排序时各趟的结果如下图所示：35 (a)初始堆(b)建堆(c)交换996和77，输出996(d)筛选调整采用基数排序法排序时各趟的结果如下：初始：491，77，572，16，996，101，863，258，689，325第1趟（按个位排序）：491，101，572，863，352，16，996，77，258，689第2趟（按十位排序）：101，16，352，258，863，572，77，689，491，996第3趟（按百位排序）：16，77，101，258，352，491，572，689，863，9965.已知序列{86，94，138，62，41，54，18，32}，请给出采用插入排序法对该序列作递增排序时，每一趟的结果。答：采用插入排序法排序时各趟的结果如下：初始：(86)，94，138，62，41，54，18，32第1趟：(86，94)，138，62，41，54，18，32第2趟：(86，94，138)，62，41，54，18，32第3趟：(62，86，94，138)，41，54，18，32第4趟：(41，62，86，94，138)，54，18，32第5趟：(41，54，62，86，94，138)，18，32第6趟：(18，41，54，62，86，94，138)，32第7趟：(18，32，41，54，62，86，94，138)6.已知序列{27，35，11，9，18，30，3，23，35，20}，请给出采用归并排序法对该序列作递增排序时的每一趟的结果。答：采用归并排序法排序时各趟的结果如下：初始：27，35，11，9，18，30，3，23，35，20第1趟：[27，35][9，11][18，30][3，23][20，35]第2趟：[9，11，27，35][3，18，23，30][20，35]第3趟：[9，11，27，35][3，18，20，23，30，35]第4趟：[3，9，11，18，20，23，27，30，35，35]二、算法设计题答案1.二、算法设计题1.一个线性表中的元素为全部为正或者负整数，试设计一算法，在尽可能少的时间内重排该表，将正、负整数分开，使线性表中所有负整数在正整数前面。解：本题的算法思想是：设置两个变量分别指向表的首尾，它们分别向中间移动，指向表首的如果遇到正整数，指向表尾的如果遇到负整数则互相交换，然后继续移动直至两者相遇。实现本题功能的算法如下：voidpart(intarray[],intn){inti,j;35 i=1;j=n;while(i=0)j--;if(inext;/*p指向待插入的元素*/while(p!=NULL){q=head;if(p->keykey)/*插到表首*/{pre->next=p->next;p->next=head;head=p;}else{while(q->next!=p&&q->next->keykey)q=q->next;if(q->next==p){pre=p;p=p->next;}else{pre->next=p->next;p->next=q->next;q->next=p;p=pre->next;}}}35 }3.试设计一个算法实现双向冒泡排序。（双向冒泡排序就是在排序的过程中交替改变扫描方向。）解：实现本题功能的算法如下：voiddbubblesort(sqlistr,intn){inti,j,flag;flag=1;i=1;while(flag!=0){flag=0;for(j=i;jr[j+1]){flag=1;r[0]=r[j];r[j]=r[j+1];r[j+1]=r[0];}}for(j=n-i;j>i;j--){if(r[j]p->key)p=p->link;elseif(x==p->key)returnp;else{p=NULL;returnp;}}虽然链表中的结点是按递增顺序排列的，但是其存储结构为单链表，查找结点时只能从头指针开始逐步进行搜索，所以不能用折半查找。2.如果线性表中各结点查找概率不等，则可以使用下面的策略提高顺序表的查找效率：如果找到指定的结点，则将该结点和其前趋（若存在）结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法（注意查找时必须从表头开始向后扫描）。解：采用顺序存储结构的算法如下，设记录存储在线性表的1~n单元中。如果查找成功，返回关键字为k的记录在线性表中的位置，如果失败则返回0。intseqsearch(sqlistr,intn,intk){inti,j;i=1;while((r[i].key!=k)&&(i<=n))i++;if(i<=n){r[0]=r[i];r[i]=r[i-1];r[i-1]=r[i];i--;return(i);}elsereturn(0);}采用链式存储结构的算法如下。如果查找成功，则返回指向关键字为k的结点的指针，否则返回NULL。node*seqsearch(node*head,intk){if(head->key==k)35 return(head);else{node*p,*q;intx;p=head;q=head->link;while(q!=NULL&&q->key!=k){p=q;q=q->link;}if(q!=NULL){x=p->key;p->key=q->key;q->key=x;q=p;}return(q);}}3.试设计一个在用开放地址法解决冲突的散列表上删除一个指定结点的算法。解：本题的算法思想是：首先计算要删除的关键字为k的记录所在的位置，将其置为空（即删除），然后利用线性探测法查找是否有与k发生冲突而存储到下一地址的记录，如果有则将记录移到原来k所在的位置，直至表中没有与k冲突的记录为止。实现本题功能的算法如下：voiddelete(sqlistr,intn,intk){inth,h0,h1;h=k%n;while(r[h].key!=k)h=(h+1)%n;r[h]=NULL;h0=h;h1=(h+1)%n;while(h1!=h){while(r[h1].key%n!=h)h1=(h1+1)%n;r[h0]=r[h1];r[h1]=NULL;h0=h1;h1=(h1+1)%n;}}4.设给定的散列表存储空间为H[1~m]，每个单元可存放一个记录，H[i](1≤i≤m)的初始值为零，选取散列函数为H(R.key)，其中key为记录R的关键字，解决冲突方法为线性探测法，编写一个函数将某记录R填入到散列表H中。35 解：本题的算法思想：先计算地址H(R.key)，如果没有冲突，则直接填入；否则利用线性探测法求出下一地址，直到找到一个为零的地址，然后填入。实现本题功能的函数如下：voidinsert(recordH,intm,recordR){inti;i=H(R.key);if(H[i]==NULL)H[i]=R;else{while(H[i]!=NULL){i=(i+1)%(m+1);}H[i]=R;}}第七章一、基本知识题1.图的逻辑结构特点是什么？什么是无向图和有向图？什么是子图？什么是网络？答：图是比树更为复杂的一种非线性数据结构，在图结构中，每个结点都可以和其它任何结点相连接。无向图：对于一个图G，若边集合E（G）为无向边的集合，则称该图为无向图。有向图：对于一个图G，若边集合E（G）为有向边的集合，则称该图为有向图。子图：设有两个图G=(V,E)和G’=(V’,E’)，若V(G’)是V(G)的子集，且E(G’)是E(G)的子集，则称G’是G的子图(Subgraph)。网络：有些图，对应每条边有一相应的数值，这个数值叫做该边的权。边上带权的图称为带权图，也称为网络。2.什么是顶点的度？什么是路径？什么是连通图和非连通图？什么是非连通图的连通分量？答：顶点的度：图中与每个顶点相连的边数，叫该顶点的度。在一个图中，若从某顶点Vp出发，沿一些边经过顶点V1,V2,…,Vm到达，Vq，则称顶点序列(Vp,V1,V2,…,Vm,Vq)为从Vp到Vq的路径。在无向图中，如果从顶点Vi到顶点Vj之间有路径，则称这两个顶点是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。非连通图的连通分量：非连通图的每一个连通的部分叫连通分量。3.给出图6.25所示的无向图G的邻接矩阵和邻接表两种存储结构。答：图G所对应的邻接矩阵如下：图G所对应的邻接表如下：图254.假设图的顶点是A、B……请根据下面的邻接矩阵画出相应的无向图或有向图。35 答：(a)所对应的无向图如下图(a)所示，(b)所对应的有向图如下图(b)所示：5.5.分别给出图6.26所示G图的深度优先搜索和广度优先搜索得到的顶点访问序列。图26答：深度优先搜索得到的顶点访问序列：0、1、3、7、8、4、9、5、6、2；广度优先搜索得到的顶点访问序列：0、1、2、3、4、5、6、7、8、9。6.应用prim算法求图6.27所示带权连通图的最小生成树。答：该图的最小生成树如下：图277.写出图6.28所示有向图的拓朴排序序列答：该有向图的拓朴排序序列为：3、1、4、5、2、6。二、算法设计题图28二、算法设计题答案1.如图6.29所示图G，试给出其对应的邻接表，并写出深度优先算法。解：该图对应的邻接表如下：深度优先算法：voiddfsgraph(adjlistadj,intn)/*深度优先遍历整个图*/{inti;for(i=1;i<=n;i++)visited[i]=0;for(i=1;i<=n;i++)if(!visited[i])dfs(adj,i);}voiddfs(adjlistadj,intv)/*以v为出发点，对图进行dfs遍历*/{structedgenode*p;visited[v]=1;printf("%d",v);p=adj[v]→link;while(p!=NULL)35 {if(visited[p→adjvex]==0)dfs(adjlist,p→adjvex);p=p→next;}}2.如图6.29所示图G，试给出其对应的邻接矩阵，并写出广度优先算法。解：该图对应的邻接矩阵如下：广度优先算法：voidbfsgraph(intadjarray[n][n],intn)/*广度优先遍历整个图*/{inti;for(i=0;inext;}returndegree;}voidprintout(adjlistadj,intn){inti,degree;printf("Theoutdegreesare:n");for(i=0;iadjvex==v)degree++;p=p->next;}}returndegree;}voidprintin(adjlistadj,intn){inti,degree;printf("Theindegreesare:n");for(i=0;imaxdegree){maxdegree=degree;maxv=i;}}printf("maxoutdegree=%d,maxvertex=%d",maxdegree,maxv);}(4)求出度数为0的顶点数的算法：intoutzero(adjlistadj,intn){intnum=0,i;for(i=0;ileft,num);num=CountNode(t->right,num);}returnnum;}求二叉树叶子结点总数的算法如下：intCountLeaf(btree*t,intnum)/*num初值为0*/{if(t!=NULL){if(t->left==NULL&&t->right==NULL)num++;num=CountLeaf(t->left,num);num=CountLeaf(t->right,num);}returnnum;}2.2.一个二叉树以链式结构存储，写出在二叉树中查找值为x的结点的算法。解：本题可以用先序、中序和后序遍历中的任意一种遍历，只要将遍历算法中的访问根结点改为判断其值是否等于x。下面是用中序遍历求解的算法，函数返回值为x的结点的地址，若没有找到则返回空。btree*search(btree*t,intx,btreep)/*p的初值为NULL*/{if(t!=NULL){p=search(t->left,x,p);if(t->data==x)p=t;/*找到x的地址放在p中*/p=search(t->right,x,p);}returnp;}3.设计一个算法将一个以链式存储结构的二叉树，按顺序方式存储到一维数组中。解：这是一个递归算法，如下：voidcreate(btree*t,inttree[],inti){if(t!=NULL){tree[i]=t->data;create(t->left,tree,2*i);create(t->right,tree,2*i+1);}}4.假设二叉排序树t的各元素值均不相同，设计一个算法按递增次序打印各元素值。解：按中序序列遍历二叉排序树即按递增次序遍历，所以递增打印二叉排序树各元素值的函数如下：voidinorder(btree*t){if(t!=NULL){inorder(t->left);printf("%d",t->data);35 inorder(t->right);}}5.已知一个中序线索二叉树，试编写中序遍历的非递归算法。解：在中序线索二叉树中进行非递归中序遍历，只要从头结点出发，反复找到结点的后继，直至结束即可。在中序线索二叉树中求结点后继的算法如下：tbtree*succ(tbtree*p){btree*q;if(p->rtag==1)return(p->right);else{q=p->right;while(q->ltag==0)q=q->left;return(q);}}由此得到中序遍历线索二叉树的非递归算法如下：voidthinorder(tbtree*p){if(p!=NULL){while(p->ltag==0)p=p->left;do{printf("%d",p->data);p=succ(p);}while(p!=NULL);}}第五章A[10][20]采用列为主序存储,每个元素占1个单元,A[0][0]的地址为200,则A[6][12]的地址是多少?3262.稀疏矩阵m×n采用三元组顺序表存储结构,非零元个数tu满足什么条件时,该存储结构才有意义?tunext->next（表中带头结点）。这会使操作变的更加容易。4.4.写出在循环双链表中的p所指结点之后插入一个s所指结点答：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;5.5.写出在单链表中的p所指结点之前插入一个s所指结点的操作。答：s->next=p->next;p->next=s;temp=p->data;p->data=s->data;s->data=temp;6.6.请利用链表来表示下面一元多项式A(x)=4*x^11+9*x^8+11*x^3+8*x+7答：多项式A(x)用链表表示如下：head_A-->4,11-->9,8--.11,3-->8,1-->7,0^二、算法设计题答案1.1.有一个有n个结点的单链表，设计一个函数将第i-1个结点与第i个结点互换，但指针不变。解：本题的算法思想是：要使结点互换而指针不变，只要将两个结点的数据进行交换即可。实现本题功能的函数如下：voidexchange(node*head,inti,n){node*p,*q;intdata;if(i>n)printf("error!n");else{p=head;for(intj=1;jnext;q=p->next;data=q->data;q->data=p->data;p->data=data;}}2.2.设计一个函数，查找单链表中数值为x的结点。解：实现本题功能的函数如下：voidsearch(node*head,intx){node*p;p=head;while(p->data!=x&&p!=NULL)p=p->next;if(p!=NULL)printf("结点找到了！n");elseprintf("结点未找到！n");}3..已知一个单链表，编写一个删除其值为x的结点的前趋结点的算法。解：本题的算法思想是：先找到值为x的结点*p和它的前趋结点*q，要删除*q，只需把*p的值x放到*q的值域中，再删除结点*p即可。实现本题功能的函数如下：voiddelete(node*head,intx){node*p,*q;q=head;p=head->next;while((p!=NULL)&&(p->data!=x)){q=p;p=p->next;}if(p==NULL)35 printf("未找到x！n");elseif(q==head)printf("x为第一个结点，无前趋！n");else{q->data=x;q->next=p->next;free(p);}}4.4.已知一个单链表，编写一个函数从此单链表中删除自第i个元素起的length个元素。解：实现本题功能的函数如下：voiddeletelength(node*head,inti,intlength){node*p,*q;intj;if(i==1)for(j=1;j<=length;j++)/*删除前k个元素*/{p=head;/*p指向要删除的结点*/head=head->next;free(p);}else解：实现本题功能的函数如下：voiddeletelength(node*head,inti,intlength){node*p,*q;intj;if(i==1)for(j=1;j<=length;j++)/*删除前k个元素*/{p=head;/*p指向要删除的结点*/head=head->next;free(p);}else{p=head;for(j=1;j<=i-2;j++)p=p->next;/*p指向要删除的结点的前一个结点*/for(j=1;j<=length;j++){q=p->next;/*q指向要删除的结点*/p->next=q->next;free(q);}}}5.已知一个递增有序的单链表，编写一个函数向该单链表中插入一个元素为x的结点，使插入后该链表仍然递增有序。解：本题算法的思想是：先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，然后插入该结点。实现本题功能的函数如下：voidinsert(node*head,intx){node*s,*p,*q;s=(node*)malloc(sizeof(node));/*建立一个待插入的结点*/s->data=x;s->next=NULL;if(head==NULL||xdata)/*若单链表为空或x小于第一个结点data域*/{s->next=head;/*插入到表头后面*/head=s;}else{q=head;p=q->next;while(p!=NULL&&x>p->data){q=p;p=p->next;}s->next=p;/*插入结点*/q->next=s;}}6.已知一个单链表，编写一个函数将此单链表复制一个拷贝。解：本题算法的思想是依次查找原单链表（其头指针为head1）中的每个结点，对每个结点复制一个新结点并链接到新的单链表（其头指针为head2）中。实现本题功能的函数如下：voidcopy(node*head1,node*head2){node*p,*q,*s;head2=(node*)malloc(sizeof(node));q=head2;q->data=head1->data;p=head1->next;while(p!=NULL){35 s=(node*)malloc(sizeof(node));s->data=p->data;q->next=s;q=s;p=p->next;}q->next=NULL;}7.有一个共10个结点的单链表，试设计一个函数将此单链表分为两个结点数相等的单链表。解：本题的算法思想是：在原单链表一半处将其分开，第5个结点的next域置为空，为第一个单链表的表尾。第二个单链表的表头指针指向原单链表的第6个结点。实现本题功能的函数如下，函数返回生成的第二个单链表的表头指针，第一个单链表仍然使用原单链表的表头指针。node*divide(node*head1){node*head2,*prior;head2=head1;for(inti=1;i<=5;i++){prior=head2;head2=head2->next;}prior->next=NULL;returnhead2;}8.与上题相同的单链表，设计一个函数，将此单链表分成两个单链表，要求其中一个仍以原表头指针head1作表头指针，表中顺序包括原线性表的第一、三等奇数号结点；另一个链表以head2为表头指针，表中顺序包括原单链表第二、四等偶数号结点。解：本题算法的思想是将第一个链表中的所有偶数序号的结点删除，同时把这些结点链接起来构成第二个单链表。实现本题功能的函数如下：voidsplit(node*head1,node*head2){node*temp,*odd,*even;odd=head1;head2=head1->next;temp=head2;while(odd!=NULL&&odd->next!=NULL){even=odd->next;/*even指向偶数序号的结点*/odd->next=even->next;temp->next=even;temp=even;odd=odd->next;/*odd指向奇数序号的结点*/}even->next=NULL;}9.已知一个指针p指向单循环链表中的一个结点，编写一个对此单循环链表进行遍历的算法。解：本题的算法思想是：因为是单循环链表，所以只要另设一指针q指向p用来帮助判断是否已经遍历一遍即可。实现本题功能的函数如下：voidtravel(node*p){node*q=p;while(q->next!=p){printf("%4d",q->data);q=q->next;}printf("%4d",q->data);}10.已知一个单循环链表，编写一个函数，将所有箭头方向取反。解：本题算法的思想是：从头到尾扫描该循环链表，将第一个结点的next域置为NULL，将第二个结点的next域指向第一个结点，如此直到最后一个结点，便用head指向它。由于是循环链表，所以判定最后一个结点时不能用p->next=NULL作为条件，而是用q指向第一个结点，以p!=q作为条件。实现本题功能的函数如下：voidinvert(node*head){node*p,*q,*r;p=head;q=p->next;while(p!=q){r=head;while(r->next!=p)r=r->next;p->next=r;p=p->next;}q->next=head;}11.在双链表中，若仅知道指针p指向某个结点，不知头指针，能否根据p遍历整个链表？若能，试设计算法实现。35 解：能。本题的算法思想是：分别从p开始沿着next以及prior向右、向左扫描直至各自的链为空即可遍历整个链表。实现本题功能的函数如下：voidtravellist(node*p){node*q;q=p;while(q!=NULL){printf("%4d",q->data);q=q->next;}q=p->prior;while(q!=NULL){printf("%4d",q->data);q=q->prior;}}12.试编写一个在循环双向链表中进行删除操作的算法，要求删除的结点是指定结点p的前趋结点。解：实现本题功能的算法如下：voiddeleteprior(node*p){node*pri,q;pri=p->prior;q=pri->prior;if(pri==p)printf("p结点无前趋！n");第三章二、算法设计题习题解答(3)一、基本知识题答案1.什么是栈？什么是队列？它们各自的特点是什么？答：栈是限定在表的一端进行插入或删除操作的线性表；队列是元素的添加在表的一端进行，而元素的删除在表的另一端进行的线性表；栈的特点是后进先出，队列的特点是先进先出。2.线性表、栈、队列有什么异同？答：栈和队列都是线性表，但是是受限的线性表，对插入、删除运算加以限制。栈是只允许在一端进行插入、删除运算，因而是后进先出表；而队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表。3.简述栈的入栈、出栈操作的过程。答：栈的入栈、出栈操作均在栈顶进行，栈顶指针指向栈顶元素的下一个位置。入栈操作先将入栈元素放到栈顶指针所指示的位置上，然后将栈顶指针加1。出栈操作先将栈顶指针减1，然后从栈顶指针指向位置取值。4.在循环队列中简述入队、出队操作的过程。答：在循环队列中，设队首指针指向队首元素，队尾指针指向队尾元素后的一个空闲元素。在队列不满时，可执行入队操作，此时先送值到队尾指针指向的空闲元素，队尾指针再加1（要取模）。在队列不空时，可执行出队操作，此时先从队首指针指向处取值，队首指针再加1（要取模）。二、算法设计题答案1.设用一维数组stack[n]表示一个堆栈，若堆栈中一个元素需占用length个数组单元（length>1），试写出其入栈、出栈操作的算法。解：用一整型变量top表示栈顶指针，top为0时表示栈为空。如果栈不空，则从stack[1]开始存放元素。实现本题功能的函数如下：入栈算法：voidPush(EleTypex){if((top+length)>n)printf("上溢出n");else{if(top==0)/*为空栈*/{top++;stack[top]=x;}else{top=top+length;stack[top]=x;}}}出栈算法：voidPop(EleTypex){if(top==0)printf("为空栈n");else{if(top==1){x=stack[top];top--;}else{35 x=stack[top];top=top-length;}}}2.试编写一个遍历及显示队列中元素的算法。解：设表达式在字符数组a[]中，使用一堆栈S来帮助判断。实现本题功能的函数如下：intcorrect(chara[]){StackS;InitStack(S);for(i=0;ilink==NULL;C.first->link==first;D.first!=NULL;29.带头结点的单链表first为空的判定条件是（B）。A.first==NULL;B.first->link==NULL;C.first->link==first;D.first!=NULL;30.设单链表中结点的结构为（data,link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行的操作是（B）。A.s->link=p->link;p->link=s;B.q->link=s;s->link=p;C.p->link=s->link;s->link=p;D.p->link=s;s->link=q;31.设单链表中结点的结构为（data,link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行的操作是（D）。A.s->link=p;p->link=s;B.p->link=s;s->link=p;C.s->link=p->link;p=s;D.s->link=p->link;p->link=s;32.设单链表中结点的结构为（data,link）。若想摘除p->link所指向的结点，则应执行的操作是（A）。A.p->link=p->link->link;B.p=p->link;p->link=p->link->link;C.p->link=p;D.p=p->link->link;33.非空的循环单链表first的尾结点（由p所指向）满足的条件是（C）。A.p->link==NULL;B.p==NULL;C.p->link==first;D.p==first;34.设单循环链表中结点的结构为（data,link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行的操作是（D）。A.s=rear;rear=rear->link;deletes;B.rear=rear->link;deleterear;C.rear=rear->link->link;deleterear;D.s=rear->link->link;rear->link->link=s->link;deletes;35.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较的结点数是（D）。A.nB.n/2C.(n-1)/2D.(n+1)/236.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（B）。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)37.给定有n个元素的向量，建立一个有序单链表的时间复杂度是（C）。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)38.单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（C）。A.O(1)B.O(m)C.O(n)D.O(m+n)39.利用双向链表作线性表的存储结构的优点是（B）。A.便于单向进行插入和删除的操作B.便于双向进行插入和删除的操作C.节省空间D.便于销毁结构释放空间40.带表头的双向循环链表的空表满足（B）。A.first＝NULL;B.first->rLink==firstC.first->lLink==NULLD.first->rLink==NULL41.已知L是一个不带表头的单链表,在表首插入结点*p的操作是（C）。A.p=L;p->link=L;B.p->link=L;p=L;C.p->link=L;L=p;D.L=p;p->link=L;42.已知L是带表头的单链表,删除首元结点的语句是（B）。A.L=L->link;B.L->link=L->link->link;C.L=L;D.L->link=L;43.栈的插入和删除操作在(A)进行。A.栈顶B.栈底C.任意位置D.指定位置44.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时，首先应执行(B)语句修改top指针。A.top++;B.top--;C.top=0;D.top;45.若让元素1,2,3依次进栈，则出栈次序不可能出现(C)种情况。A.3,2,1B.2,1,3C.3,1,2D.1,3,235 46.在一个顺序存储的循环队列中，队头指针指向队头元素的(A)位置。A.前一个B.后一个C.当前D.后面47.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为(B)。A.n-2B.n-1C.nD.n+148.从一个顺序存储的循环队列中删除一个元素时，首先需要(A)。A.队头指针加一B.队头指针减一C.取出队头指针所指的元素D.取出队尾指针所指的元素49.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D)。A.front+1==rearB.rear+1==frontC.front==0D.front==rear50.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为(D)。A.front==rearB.front!=NULLC.rear!=NULLD.front==NULL51.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行(C)操作。A.top->link=s;B.s->link=top->link;top->link=s;C.s->link=top;top=s;D.s->link=top;top=top->link;52.设链式栈中结点的结构为（data,link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行(A)操作。A.x=top->data;top=top->link;B.top=top->link;x=top->data;C.x=top;top=top->link;D.x=top->data;53.设循环队列的结构是typedefstruct{DataTypedata[MaxSize];intfront,rear;}Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应为(D)。A.Q.front==Q.rear;B.Q.front-Q.rear==MaxSize;C.Q.front+Q.rear==MaxSize;D.Q.front==(Q.rear+1)%MaxSize;54.设循环队列的结构是constintMaxSize=100;typedefintDataType;typedefstruct{DataTypedata[MaxSize];intfront,rear;}Queue;若有一个Queue类型的队列Q，则应用(A)表达式计算队列元素的个数。A.(Q.rear-Q.front+MaxSize)%MaxSize;B.Q.rear-Q.front+1;C.Q.rear-Q.front-1;D.Q.rear-Qfront;55.为增加内存空间的利用率和减少溢出的可能性,由两个栈共享一块连续的内存空间时,应将两栈的(D)分别设在这块内存空间的两端。A.长度B.深度C.栈顶D.栈底56.递归是将一个较复杂的（规模较大的）问题转化为一个稍为简单的（规模较小的）与原问题（C）的问题来解决，使之比原问题更靠近可直接求解的条件。A.相关B.子类型相关C.同类型D.不相关57.递归调用时系统需要利用一个（D）来实现数据的传递和控制的转移。A.队列B.优先级队列C.双端队列D.栈58.在系统实现递归调用时需利用递归工作记录保存（C），当递归调用程序执行结束时通过它将控制转到上层调用程序。A.调用地址B.递归入口C.返回地址D.递归出口59.在递归执行过程中，当前执行的递归函数过程的递归工作记录一定是递归工作栈中的栈顶记录，称之为（A）记录。A.活动B.当前C.日志D.标记60.将递归求解过程改变为非递归求解过程的目的是（A）。A.提高速度B.改善可读性C.增强健壮性D.提高可维护性61.35 如果一个递归函数过程中只有一个递归语句，而且它是过程体的最后语句，则这种递归属于（D），它很容易被改写为非递归过程。A.单向递归B.回溯递归C.间接递归D.尾递归62.设有一个递归算法如下intfact(intn){//n大于等于0if(n<=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要函数调用的次数为（B）次。A．nB．n+1C．n+2D．n-163.设有一个递归算法如下intX(intn){if(n<=3)return1;elsereturnX(n-2)+X(n-4)+1;}试问计算X(X(5))时需要调用（C）次X函数。A．2次B．3次C．4次D．5次64.设有一个广义表A(a)，其表尾为（C）。A．aB．(())C．（）D．(a)65.设有一个广义表A((x,(a,b)),(x,(a,b),y))，运算Head(Head(Tail(A)))的执行结果为（A）。A．xB．(a,b)C．(x,(a,b))D．y66.下列广义表中的线性表是（C）。A．E(a,(b,c))B．E(a,E)C．E(a,b)D．E(a,L())67.对于一组广义表A(),B(a,b),C(c,(e,f,g)),D(B,A,C),E(B,D)，其中的E是（D）。A.线性表B.纯表C.递归表D.再入表68.已知广义表A((a,b,c),(d,e,f))，从A中取出原子e的运算是（C）。A．Tail(Head(A))B．Head(Tail(A))C．Head(Tail(Head(Tail(A))))D．Head(Head(Tail(Tail(A))))69.树中所有结点的度之和等于所有结点数加(C)。A.0B.1C.–1D.270.在一棵树中，(C)没有前驱结点。A.树枝结点B.叶子结点C.树根结点D.空结点71.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加(A)。A.2B.1C.0D.–172.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于(C)。A.nB.n-1C.n+1D.2*n73.在一棵具有n个结点的二叉树的第i层上(假定根结点为第0层，i大于等于0而小于等于树的高度)，最多具有(A)个结点。A.2iB.2i+1C.2i-1D.2n74.在一棵高度为h(假定树根结点的层号为0)的完全二叉树中，所含结点个数不小于(D)。A.2h-1B.2h+1C.2h-1D.2h75.一棵具有35个结点的完全二叉树的高度为(A)。假定空树的高度为-1。A.5B.6C.7D.876.在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为(D)。假定树根结点的编号为0。A.ë(n-1)/2ûB.ën/2ûC.én/2ùD.ën/2û-177.在一棵完全二叉树中，若编号为i的结点存在左子女，则左子女结点的编号为(C)。假定树根结点的编号为0。A2iB2i-1C2i+1D2i+278.在一棵完全二叉树中，假定树根结点的编号为0，对于编号为i(i>0)的结点，其双亲结点的编号为(B)。A.ë(i+1)/2ûB.ë(i-1)/2ûC.ëi/2ûD.ëi/2û-179.在一棵树的左子女-右兄弟表示法中，一个结点的右子女是该结点的(A)结点。A.兄弟B.父子C.祖先D.子孙80.在一棵树的静态双亲表示中，每个存储结点包含(B)个域。A1B2C3D481.已知一棵二叉树的广义表表示为a(b(c),d(e(,g(h)),f))，则该二叉树的高度为(B)。假定树根结点的高度为0。A.3B.4C.5D.682.已知一棵树的边集表示为{,,,,,,,}，则该树的深度为(B)。假定树根结点的高度为0。A.2B.3C.4D.583.利用n个值作为叶结点的权生成的霍夫曼树中共包含有(D)个结点。A.nB.n+1C.2*nD.2*n-184.利用3,6,8,12这四个值作为叶子结点的权，生成一棵霍夫曼树，该树的带权路径长度为(A)。35 A55B29C58D3885.一棵树的广义表表示为a(b,c(e,f(g)),d)，当用左子女-右兄弟链表表示时，右指针域非空的结点个数为(C)。A1B2C3D486.向具有n个结点的堆中插入一个新元素的时间复杂度为(C)。A.O(1)B.O(n)C.O(log2n)D.O(nlog2n)87.若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长度为(D)。A.nB.n+1C.(n-1)/2D.(n+1)/288.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索任一元素的平均搜索长度为(C)。A.5.5B.5C.39/8D.19/489.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索第三个元素的概率为1/6，则搜索任一元素的平均搜索长度为(A)。A.5/3B.2C.7/3D.4/390.对长度为n的单链有序表，若搜索每个元素的概率相等，则搜索任一元素的搜索成功的平均搜索长度为(B)。A.n/2B.(n+1)/2C.(n-1)/2D.n/491.对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为(A)的值向上取整。A.log2(n+1)B.log2nC.n/2D.(n+1)/292.对于长度为n的顺序存储的有序表，若采用折半搜索，则对所有元素的搜索长度中最大的为(B)的值的向下取整加1。A.log2(n+1)B.log2nC.n/2D.(n+1)/293.对于长度为9的顺序存储的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为(C)除以9。A.20B.18C.25D.2294.对于长度为18的顺序存储的有序表，若采用折半搜索，则搜索第15个元素的搜索长度为(B)。A.3B.4C.5D.695.对具有n个元素的有序表进行折半搜索，则搜索任一元素的时间复杂度为(D)。A.O(n)B.O(n2)C.O(1)D.O(log2n)96.在一棵高度为h的具有n个元素的二叉搜索树中，搜索一个元素的最大搜索长度为(D)。A.nB.log2nC.(h+1)/2D.h+197.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为(C)。A.O(n)B.O(1)C.O(log2n)D.O(n2)98.向具有n个结点的二叉搜索树中插入一个元素的时间复杂度大致为(B)。A.O(1)B.O(log2n)C.O(n)D.O(nlog2n)99.在一棵AVL树中，每个结点的平衡因子的取值范围是(A)。A.-1~1B.-2~2C.1~2D.0~1100.向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为(C)种旋转类型。A.2B.3C.4D.5101.向一棵AVL树插入元素时，可能引起对最小不平衡子树的左单或右单旋转的调整过程，此时需要修改相关(B)个指针域的值。A.2B.3C.4D.5102.向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此时需要修改相关(D)个指针域的值。A.2B.3C.4D.5103.设G1=（V1，E1）和G2=（V2，E2）为两个图，如果V1ÍV2，E1ÍE2，则称(A)。A．G1是G2的子图B．G2是G1的子图C．G1是G2的连通分量D．G2是G1的连通分量104.有向图的一个顶点的度数等于该顶点的(C)。A．入度B．出度C．入度与出度之和D．（入度+出度）／２105.一个连通图的生成树是包含图中所有顶点的一个(C)。A．极小子图B．连通子图C．极小连通子图D．无环子图106.n个顶点的连通图中至少含有(A)。A．n-1条边B．n条边C．n(n-1)/2条边D．n(n-1)条边107.n个顶点的强连通图中至少含有(B)。A．n-1条有向边B．n条有向边C．n(n-1)/2条有向边D．n(n-1)条有向边108.在一个带权连通图G中，权值最小的边一定包含在G的(A)中。A．最小生成树B．生成树C．广度优先生成树D．深度优先生成树109.对于具有e条边的无向图，它的邻接表中有(D)个边结点。A．e-1B．eC．2(e-1)D．2e110.具有n个顶点的有向无环图最多可包含(C)35 条有向边。A．n-1B．nC．n(n-1)/2D．n(n-1)111.一个有n个顶点和n条边的无向图一定是(D)。A．连通的B．不连通的C．无环的D．有环的112.在n个顶点的有向无环图的邻接矩阵中至少有(C)个零元素。A．nB．n(n-1)/2C．n(n+1)/2D．n(n-1)113.对于有向图，其邻接矩阵表示比邻接表表示更易于(A)。A．查找一条边B．求一个顶点的邻接点C．进行图的深度优先遍历D．进行图的广度优先遍历114.在一个有向图的邻接矩阵表示中，删除一条边需要耗费的时间是(A)。A．O(1)B．O(i)C．O(j)D．O(i+j)115.与邻接矩阵相比，邻接表更适合于存储(C)。A．无向图B．连通图C．稀疏图D．稠密图116.设一个有n个顶点和e条边的有向图采用邻矩阵表示，要计算某个顶点的出度所耗费的时间是(A)。A．O(n)B．O(e)C．O(n+e)D．O(n2)117.为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是(B)。A．栈B．队列C．二叉树D．树118.设无向图的顶点个数为n，则该图最多有（B）条边。A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)119.在一个无向图中，所有顶点的度数之和等于所有边数的(B)倍。A.3B.2C.1D.1/2120.若采用邻接矩阵存储具有n个顶点的无向图，则该邻接矩阵是一个(D)。A.上三角矩阵B.稀疏矩阵C.对角矩阵D.对称矩阵121.图的深度优先搜索类似于树的（A）次序遍历。A.先根B.中根C.后根D.层次122.图的广度优先搜索类似于树的（D）次序遍历。A.先根B.中根C.后根D.层次123.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（C）辅助结构，判断一条边的两个端点是否在同一个连通分量上。A.位向量B.堆C.并查集D.生成树顶点集合124.采用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是（C）数。A.非零B.非整C.非负D.非正125.设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（B）。A.O(nlog2e)B.O(n+e)C.O(ne)D.O(n2)126.若待排序对象序列在排序前已基本按排序码递增顺序排列，则采用(A)方法比较次数最少。A.直接插入排序B.快速排序C.归并排序D.直接选择排序127.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是(C)。A.直接选择排序B.直接插入排序C.快速排序D.起泡排序128.对5个不同的数据元素进行直接插入排序，最多需要进行(B)次比较。A.8B.10C.15D.25129.下列排序算法中，(D)算法是不稳定的。A.起泡排序B.直接插入排序C.基数排序D.快速排序130.假设某文件经过内部排序得到100个初始归并段，那么如果要求利用多路平衡归并在3趟内完成排序，则应取的归并路数至少是(C)。A.3B.4C.5D.6131.在基于排序码比较的排序算法中，(C)算法在最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.堆排序D.快速排序132.在下列排序算法中，(C)算法使用的附加空间与输入序列的长度及初始排列无关。A.锦标赛排序B.快速排序C.基数排序D.归并排序133.一个对象序列的排序码为{46,79,56,38,40,84}，采用快速排序（以位于最左位置的对象为基准）所得到的第一次划分结果为(C)。A.{38,46,79,56,40,84}B.{38,79,56,46,40,84}C.{40,38,46,79,56,84}D.{38,46,56,79,40,84}134.如果将所有中国人按照生日（不考虑年份，只考虑月、日）来排序，那么使用下列排序算法中(C)算法最快。A.归并排序B.希尔排序C.快速排序D.基数排序35 135.设有一个含有200个元素的表待散列存储，用线性探查法解决冲突，按关键码查询时找到一个元素的平均探查次数不能超过1.5，则散列表的长度应至少为（D）。（注：平均探查次数的计算公式为Snl={1+1/(1-α)}/2,其中α为装填因子）A.400B.526C.624D.676136.5阶B树中,每个结点最多允许有（C）个关键码。A.2B.3C.4D.5137.在10阶B树中根结点所包含的关键码个数最少为（B）。A.0B.1C.3D.4138.在一棵高度为h的B树中，叶结点处于第（A）层。（注：树根结点为第0层，B树高度为失败结点所处层数）。A.h-1B.hC.h+1D.h+2139.在一棵高度为h的B树中，插入一个新关键码时，为搜索插入位置需读取（B）个结点。A.h-1B.hC.h+1D.h+2140.当对一个线性表R[60]进行索引顺序搜索（分块搜索）时，若共分成了10个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（C）。A.7B.8C.9D.10141.当对一个线性表R[60]进行索引顺序搜索（分块搜索）时，若共分成了8个子表，每个子表有6个表项。假定对索引表和数据子表都采用顺序搜索，则搜索每一个表项的平均搜索长度为（B）。A.7B.8C.9D.10142.既希望较快的搜索又便于线性表动态变化的搜索方法是（D）。A.顺序搜索B.折半搜索C.散列搜索D.索引顺序搜索148.采用线性探查法解决冲突时所产生的一系列后继散列地址（C）。A.必须大于原散列地址B.必须小于原散列地址C.可以大于或小于原散列地址D.不能超过散列表长度的一半149.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度（C）。A.为O(log2n)B.为O(n)C.与n/m值有关D.与n/m值无关填空题1.数据是__信息______的载体，它能够被计算机程序识别、存储和加工处理。2.数据结构包括逻辑结构、___存储结构_____和数据的运算三个方面。3.数据结构的逻辑结构包括线性结构和__非线性______结构两大类。4.数据结构的存储结构包括顺序、____链接____、索引和散列等四种。5.基本数据类型是计算机已经实现了的_数据结构_______。6.抽象数据类型的特点是_数据封装_______、信息隐蔽、使用与实现分离。7.算法的一个特性是_有穷性_______，即算法必须执行有限步就结束。8.面向对象的特征应包括对象、类、__继承______、消息通信。9.属性与服务相同的对象构成类，类中的每个对象称为该类的_实例_______。10.对象的私有状态只能通过该对象的___操作（或服务）_____才能改变。11.模板类是一种数据抽象，它把__数据类型______当作参数，可以实现类的复用。12.在类的继承结构中，位于上层的类叫做基类，其下层的类则叫做_派生（或子）_______类。13.一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的__下标（或顺序号）_______存取的。14.在程序运行过程中不能扩充的数组是___静态_______分配的数组。这种数组在声明它时必须指定它的大小。15.在程序运行过程中可以扩充的数组是____动态______分配的数组。这种数组在声明它时需要使用数组指针。16.二维数组是一种非线性结构，其中的每一个数组元素最多有__两个_______个直接前驱（或直接后继）。17.若设一个n´n的矩阵A的开始存储地址LOC(0,0)及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为__LOC(0,0)+(i*n+j)*d_______。18.对称矩阵的行数与列数__相等_______且以主对角线为对称轴，aij=aji，因此只存储它的上三角部分或下三角部分即可。19.将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储_n(n+1)/2________个矩阵元素。20.将一个n阶对称矩阵A的上三角部分按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中，则A[I][J]在I≤J时将存放于数组B的_(2n-I-1)*I/2+J________位置。35 21.利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和____值_____。22.线性表是由n（n≥0）个_数据元素________组成的有限序列。23.若设串S=“documentHash.doc”，则该字符串S的长度为___16______。24.链表是一种采用链式（或链接）存储结构存储的线性表。25.链表只适用于顺序查找。26.在链表中进行插入和删除操作的效率比在顺序存储结构中进行相同操作的效率高。27.链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的_指针域_________的值。28.链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配_______和释放。29.单链表中逻辑上相邻的结点而在物理位置上_不一定______相邻。30.在单链表中,除了表头结点外,任意结点的存储位置由其直接_前驱____结点的指针域的值所指示。31.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对_表头指针_______进行特殊处理。32.若设L是指向带表头的单链表,语句L->link=L->link->link的作用是__删除______单链表中的第一个结点。33.在双向链表中,每个结点除了数据域外,还有两个指针域,它们分别指向_前趋结点和后继结点_______。34.线性表的链接存储只能通过__链接指针______顺序访问。35.链表与顺序表、索引表、散列表等都是数据逻辑结构的_存储_________表示。36.设双向循环链表每个结点结构为(data,llink,rlink),则结点*p的前驱结点的地址为__p->llink________。37.栈是一种限定在表的一端进行插入和删除的线性表，又被称为__后出先进_________表。38.队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为_先进先出_______表。39.向一个链式栈插入一个新结点时，首先把栈顶指针的值赋给新结点的指针域，然后把新结点的存储位置赋给__栈顶指针______。40.队列的删除操作在__队头（或队首）______进行。41.向一个顺序栈插入一个元素时，首先使___栈顶指针_____后移一个位置，然后把待插入元素写入到这个位置上。42.若设顺序栈的最大容量为MaxSize，top==-1表示栈空，则判断栈满的条件是___top==MaxSize-1_________。43.当用长度为MaxSize的数组顺序存储一个栈时，若用top==MaxSize表示栈空，则表示栈满的条件为_top==0_______。44.向一个循环队列中插入元素时，需要首先移动__队尾______指针，然后再向所指位置写入新元素。45.向一个栈顶指针为top的链式栈中插入一个新结点*p时，应执行_p->link=top_______和top=p操作。46.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有__1______个结点。47.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有___一_____个结点。48.如果一个对象部分地包含自己，或自己定义自己，则称这个对象是__递归_______的对象。49.如果一个过程直接或间接地调用自己，则称这个过程是一个__递归______的过程。50.递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归；其二是保存本层的形式参数和___局部变量______。51.函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就_释放_______局部变量所占用的存储空间。52.迷宫问题是一个回溯控制的问题，最好使用___递归_______的方法来解决。53.非空广义表的除第一个元素外其他元素组成的表称为广义表的__表尾______。54.广义表A((a,b,c),(d,e,f))的表尾为__((d,e,f))______。55.广义表是一种递归的数据结构，子表结点则指示下一层广义表的__表头结点______。56.广义表的深度定义为广义表括号的___重数_____。57.对于一棵具有n个结点的树，该树中所有结点的度数之和为_n-1_____。58.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为_2_______个。59.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为__3_______。假定树根结点的层数为0。60.假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为__4______。假定树根结点的深度为0。61.在一棵高度为3的四叉树中，最多含有__85______个结点，假定树根结点的高度为0。62.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有____6____个。63.一棵高度为5的完全二叉树中，最多包含有_63_______个结点。假定树根结点的高度为0。64.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则该树的高度为_3_______。假定树根结点的高度为0。65.35 在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为___6_____个。66.假定一棵二叉树的结点数为18，则它的最小高度为_4_______。假定树根结点的高度为0。67.在一棵高度为h的理想平衡二叉树中，最少含有___2h_____个结点。假定树根结点的高度为0。68.在一棵高度为h的理想平衡二叉树中，最多含有__2h+1-1______个结点。假定树根结点的高度为0。69.若将一棵树A(B(C,D,E),F(G(H),I))按照左子女-右兄弟表示法转换为二叉树，该二叉树中度为2的结点的个数为____2____个。70.将一棵树按照左子女-右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有__右______子女。71.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的左子女元素的下标为__2i+1____。72.在一个堆的顺序存储中，若一个元素的下标为i(0≤i≤n-1)，则它的右子女元素的下标为__2i+2______。73.在一个最小堆中，堆顶结点的值是所有结点中的___最小值_____。74.在一个最大堆中，堆顶结点的值是所有结点中的___最大值_____。75.以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素的渐进时间复杂度为_.O(n)_______。76.对长度为n的搜索表进行搜索时，假定搜索第i个元素的概率为pi,搜索长度（即在搜索过程中依次同有关元素比较的总次数）为ci，则在搜索成功情况下的平均搜索长度的计算公式为________。77.假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为__20.5______。78.从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为___3_____。79.假定对长度n=50的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为___19___个。80.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向__右子树______继续搜索。81.向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_左子树_______上。82.根据n个元素建立一棵二叉搜索树的渐进时间复杂度大致为___O(nlog2n)__________。83.在一棵AVL树中，每个结点的左子树高度与右子树高度之差的绝对值不超过__1______。84.根据一组记录(56,42,50,64,48)依次插入结点生成一棵AVL树时，当插入到值为_50______的结点时需要进行旋转调整。85.根据一组记录(56,74,63,64,48)依次插入结点生成一棵AVL树时，当插入到值为63的结点时需要进行_先右后左双旋转____调整。86.根据一组记录(56,42,38,64,48)依次插入结点生成一棵AVL树时，当插入到值为38的结点时需要进行_____右单旋转_______调整。87.根据一组记录(56,42,73,50,64,48,22)依次插入结点生成一棵AVL树时，当插入到值为__64_____的结点时才出现不平衡，需要进行旋转调整。88.在一棵具有n个结点的AVL树上进行插入或删除元素的渐进时间复杂度大致为___O(log2n)______。若3个顶点的图G的邻接矩阵为，则图G一定是________向图。有89.n(n﹥0)个顶点的连通无向图各顶点的度之和最少为_2(n-1)_______。90.用邻接矩阵存储图，占用的存储空间与图中的__顶点______数有关。91.设图G=(V,E)，V={V0,V1,V2,V3},E={(V0,V1),(V0,V2),(V0,V3),(V1,V3)}，则从顶点V0开始的图G的不同深度优先序列有___4_____种。92.设图G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，从顶点1出发，对图G进行广度优先搜索的序列有___2_____种。93.n(n﹥0)个顶点的无向图中顶点的度的最大值为__n-1______。94.在重连通图中每个顶点的度至少为__2______。95.n个顶点的连通无向图的生成树含有__n-1______条边。96.11个顶点的连通网络N有10条边，其中权值为1,2,3,4,5的边各2条，则网络N的最小生成树各边的权值之和为___30______。97.在使用Kruskal算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个__连通分量______上，才会被加入到生成树中。98.一般来说,深度优先生成树的高度比广度优先生成树的高度要__高______。99.求解带权连通图最小生成树的Prim算法使用图的___邻接矩阵_____作为存储结构。100.设图的顶点数为n，则求解最短路径的Dijkstra算法的时间复杂度为_O(n2)_______。101.第i(i=1,2,…,n-1)趟从参加排序的序列中取出第i个元素，把它插入到由第0个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做__直接插入________排序。102.第i(i=0,1,...,n-2)趟从参加排序的序列中第i35 个至第n-1个元素中挑选出一个最小元素，把它交换到第i个位置，此种排序方法叫做__直接选择_______排序。103.每次直接或通过基准元素间接比较两个元素，若出现逆序排列就交换它们的位置，这种排序方法叫做_____交换_____排序。104.每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做___二路归并______排序。105.在直接选择排序中，记录比较次数的时间复杂度为__O(n2)______。106.在直接选择排序中，记录移动次数的时间复杂度为__O(n)________。107.在堆排序中，对n个记录建立初始堆需要调用___n/2_______次调整算法。108.在堆排序中，如果n个对象的初始堆已经建好，那么到排序结束，还需要从堆顶结点出发调用_n-1________次调整算法。109.在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为__O(log2n)__________。110.对n个数据对象进行堆排序，总的时间复杂度为____O(nlog2n)__________。111.给定一组数据对象的关键码为{46,79,56,38,40,84}，则利用堆排序方法建立的初始堆（最大堆）为____84，79，56，38，40，46___________。112.快速排序在平均情况下的时间复杂度为__O(nlog2n)_________。113.快速排序在最坏情况下的时间复杂度为___O(n2)_________。114.快速排序在平均情况下的空间复杂度为___O(log2n)_________。115.快速排序在最坏情况下的空间复杂度为__O(n)__________。116.给定一组数据对象的关键码为{46，79，56，38，40，84}，对其进行一趟快速排序处理，得到的右子表中有__3______个对象。117.在对n个数据对象的二路归并排序中，每趟归并的时间复杂度为___O(n)_________。118.在对n个数据对象进行的二路归并排序中，整个归并过程的时间复杂度为_O(nlog2n)__________。119.在索引表中，每个索引项至少包含有__关键码________域和地址域这两项。120.假定一个线性表为{12,23,74,55,63,40,82,36}，若按key%3条件进行划分，使得同一余数的元素成为一个子表，则包含74的子表长度为_2_______。121.假定一个线性表为(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的以a为第一个字母的子表长度为3________。122.在索引表中，若一个索引项对应数据对象表中的一个表项，则称此索引为稠密索引，若对应数据对象表中的若干表项，则称此索引为___稀疏_____索引。123.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的时间复杂度为_O()_______。124.假定对长度n=100的线性表进行索引顺序搜索，并假定每个子表的长度均为，则进行索引顺序搜索的平均搜索长度为__11______。125.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则一级索引表的长度为___500_____。126.若对长度n=10000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个表项的索引，则二级索引表的长度为___25_____。127.假定要对长度n=100的线性表进行散列存储，并采用开散列法处理冲突，则对于长度m=20的散列表，每个散列地址的同义词子表（单链表）的长度平均为__5______。128.在线性表的散列存储中，装载因子a又称为装载系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，则a等于__n/m______。129.对于包含n个关键码的m阶B树，其最小高度为__élogm(n+1)ù__________。130.已知一棵3阶B树中含有50个关键码，则该树的最小高度为_4_______。131.已知一棵3阶B树中含有50个关键码，则该树的最大高度为__5______。132.在一棵m阶B树上，每个非根结点的关键码数最少为__ém/2ù-1________个。133.在一棵m阶B树上，每个非根结点的子树最少为___ém/2ù_____棵。134.在一棵m阶B树上，每个非根结点的关键码数最多为___m-1_____个。135.在对m阶B树插入元素的过程中，每向一个结点插入一个关键码后，若该结点的关键码个数等于___m_____个，则必须把它分裂为2个结点。136.在从m阶B树删除关键码的过程中，当从一个结点中删除掉一个关键码后，所含关键码个数等于ém/2ù-2个，并且它的左、右兄弟结点中的关键码个数均等于_ém/2ù-1_______，则必须进行结点合并。判断题1.数据元素是数据的最小单位。N35 2.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。Y3.算法和程序原则上没有区别，在讨论数据结构时二者是通用的。N4.数据的逻辑结构与数据元素本身的内容和形式无关。Y5.算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。N6.只有用面向对象的计算机语言才能描述数据结构算法。N7.如果采用如下方式定义一维字符数组：YconstintmaxSize=30;chara[maxSize];则这种数组在程序执行过程中不能扩充。8.如果采用如下方法定义一维字符数组：NintmaxSize=30;char*a=newchar[maxSize];则这种数组在程序执行过程中不能扩充。9.数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。N10.多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。Y11.在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。N12.顺序表和一维数组一样，都可以按下标随机（或直接）访问。Y13.插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。N14.使用三元组表示稀疏矩阵中的非零元素能节省存储空间。Y15.用字符数组存储长度为n的字符串，数组长度至少为n+1。Y16.线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。Y17.线性表若采用链式存储表示,在删除时不需要移动元素。Y18.在线性链表中删除中间的结点时，只需将被删结点释放。N19.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。Y20.每次从队列中取出的是具有最高优先权的元素,这种队列就是优先级队列。Y21.链式栈与顺序栈相比,一个明显的优点是通常不会出现栈满的情况。Y22.在一个顺序存储的循环队列中,队头指针指向队头元素的后一个位置。N23.栈和队列都是顺序存取的线性表,但它们对存取位置的限制不同。Y24.在使用后缀表示实现计算器类时用到一个栈的实例,它的作用是暂存运算器对象。Y25.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。Y26.若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。N27.在用单链表表示的链式队列Q中，队头指针为Q->front，队尾指针为Q->rear，则队空条件为Q->front==Q->rear。N28.递归定义的数据结构通常用递归算法来实现对它的操作。Y29.递归的算法简单、易懂、容易编写，而且执行效率也高。N30.递归调用算法与相同功能的非递归算法相比，主要问题在于重复计算太多，而且调用本身需要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大Y31.递归方法和递推方法本质上是一回事，例如求n!时既可用递推的方法，也可用递归的方法。N32.用非递归方法实现递归算法时一定要使用递归工作栈。N33.将f=1+1/2+1/3+…+1/n转化为递归函数时，递归部分为f(n)=f(n-1)+1/n，递归结束条件为f(1)=1。Y34.一个广义表的表头总是一个广义表。N35.一个广义表的表尾总是一个表。Y36.一个广义表((a),((b),c),(((d))))的长度为3，深度为4。Y37.一个广义表((a),((b),c),(((d))))的表尾是((b),c),(((d)))。N38.当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。Y39.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。Y40.二叉树是一棵无序树。N41.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。Nb42.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。Y43.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。N44.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。Y45.在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方便。Y46.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。Y47.对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。N35 48.对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)N49.在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。N50.线索二叉树中的每个结点通常包含有5个数据成员。Y51.对具有n个结点的堆进行插入一个元素运算的时间复杂度为O(n)。N52.在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排列存放，则可得到最小的平均搜索长度。Y53.进行折半搜索的表必须是顺序存储的有序表。Y54.能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上相同。N55.假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，其长度小于等于参加运算的任意一个集合单链表的长度。Y56.假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，其长度小于参加运算的任意一个集合单链表的长度。N57.折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。Y58.对于同一组关键码互不相同的记录，若生成二叉搜索树时插入记录的次序不同则得到不同形态的二叉搜索树。Y59.对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。N60.对于两棵具有相同记录集合而具有不同形态的二叉搜索树，按中序遍历得到的结点序列是相同的。Y61.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越大的结点离树根越近，则得到的是最优二叉搜索树。Y62.在二叉搜索树中，若各结点的搜索概率不等，使得搜索概率越小的结点离树根越近，则得到的是最优二叉搜索树。N63.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。Y64.邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。N65.邻接矩阵适用于稠密图（边数接近于顶点数的平方），邻接表适用于稀疏图（边数远小于顶点数的平方）。Y66.存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。Y67.强连通分量是有向图中的极大强连通子图。Y68.对任何用顶点表示活动的网络（AOV网）进行拓扑排序的结果都是唯一的。N69.有回路的有向图不能完成拓扑排序。Y75.对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。Y76.图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。Y77.如果无向图中每个顶点的度都大于等于2，则该图中必有回路。Y78.如果有向图中各个顶点的度都大于2，则该图中必有回路。N79.图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。Y80.图的广度优先搜索算法通常采用非递归算法求解。Y81.对一个有向图进行拓扑排序，一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。N82.直接选择排序是一种稳定的排序方法。N83.若将一批杂乱无章的数据按堆结构组织起来,则堆中数据必然按从小到大的顺序线性排列。N84.当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。Y85.在任何情况下，快速排序需要进行关键码比较的次数都是O(nlog2n)。N86.若用m个初始归并段参加k路平衡归并排序，则归并趟数应为élog2mù。N87.堆排序是一种稳定的排序算法。N88.任何基于排序码比较的算法，对n个数据对象进行排序时，最坏情况下的时间复杂度都不会大于O(nlog2n)N93.一棵m阶B树中每个结点最多有m-1个关键码，最少有ém/2ù-1个关键码。N94.在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关，而且与每一个子表中的对象个数有关。Y95.在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。Y96.在散列法中采取开散列（链地址）法来解决冲突时,其装载因子的取值一定在(0,1)之间。N97.AVL树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡m路搜索树的叶结点也不一定在同一层次上。Y98.在一棵B树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加1。Y99.向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。N100.从一棵B树删除关键码的过程中，若最终引起树根结点的合并，则新树比原树的高度增加1。N考试复习1.35 根据给定的含有13个元素的有序表构造二叉排序树，在其中查找元素成功时平均查找长度为多少？1.顺序表和链表中结点的访问特性分别是什么？（A.顺序访问；B.随机访问）2.3叉树中度为2，3的结点个数为2，3，则其中叶子结点的个数为。3.若程序中用以下语句说明循环队列queue：ElemTypequeue[MaxSize]；intfront=rear=-1；/*队首和队尾指针分别为front、rear；*/请问队列为空和队列为满分别满足什么条件？5.一个非连通图有n个顶点和n-1条边，则此图中一定存在有什么特征？6.元素之间的关系在顺序存储结构中通过什么来体现（或映射）？7.下面语句段中有@标记的语句的执行频度是多少？intx=91,y=100;while(y>0)@if(x>100){x-=10;y--;}elsex++;8．按照四则运算加、减、乘、除和幂运算（^）优先关系的惯例，给出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D^F9．已知二叉树的中序和后序遍历序列分别为DGBAECF和GDBEFCA，请给出二叉树示意图并给出先序遍历序列、顺序存储结构示意图。10．已知某有序顺序表含有13个数据元素，根据给定条件在该表中进行二分查找。请给出二分查找判定树并计算查找成功时平均查找长度。11．给出对如图所示网络进行深度优先遍历和宽度优先遍历时输出的结点序列，并给出利用Prim算法构造其最小生成树过程及其用到的两个向量的变化过程。12..有无序数据序列38，49，21，97，38，49，15，48，7，56，请回答以下问题：1．对此序列进行冒泡排序第二趟排序结束的数据序列；2．对此序列进行快速排序第一趟排序结束的数据序列；3．对此序列进行堆排序第一趟排序结束的数据序列；4.对此序列进行按增量5，3希尔排序二趟排序后的数据序列。13、根据给定的序列{25，18，46，2，53，39，32，4，74，67}构造平衡二叉树。14、根据给定的权值集合W={0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}构造哈夫曼树和编码。15、算法设计题：1．将给出非递归的后序遍历算法。2．请设计算法：将给定的带头结点的单链表中的结点就地倒置。14′要求：利用原有的链表结点空间，不额外申请链表的结点空间。35'