第一篇：严蔚敏 数据结构课后习题及答案解析
第一章 绪论
一、选择题
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.数据的机内表示称为数据的存储结构。（）
2.算法就是程序。（）
3.数据元素是数据的最小单位。（）
4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（）
5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（）
三、填空题
1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。
2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。
3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。
4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________。
5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系。
6.算法的五个重要特性是_______、_______、______、_______、_______。
7.数据结构的三要素是指______、_______和________。
8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。
9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。
四、算法分析题
1.求下列算法段的语句频度及时间复杂度
参考答案：
一、选择题
1.C 2.C 3.C 4.A、B 5.C 6.C、B
二、判断题:
1、√
2、×
3、×
4、×
5、√
三、填空题
1、线性、树形、图形、集合? ；非线性（网状）
2、没有；1；没有；1
3、前驱；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）/ n3 ≤1，故时间复杂度为Ｏ(n3)
第二章 线性表
一、选择题
1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是()（A）110（B）108（C）100（D）120 2.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。
（A）64（B）63（C）63.5（D）7 3.线性表采用链式存储结构时，其地址（）。
(A)必须是连续的(B)部分地址必须是连续的(C)一定是不连续的(D)连续与否均可以
4.在一个单链表中，若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;5.在一个单链表中，若删除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个（）的有限序列（n≠0)
（A）表元素（B）字符（C）数据元素
（D）数据项
二、判断题
1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。（）
2.如果没有提供指针类型的语言，就无法构造链式结构。（）
3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。（）
4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值。（）
5.要想删除p指针的后继结点，我们应该执行q=p->next ； p->next=q->next； free(q)。（）
三、填空题
1.已知P为单链表中的非首尾结点，在P结点后插入S结点的语句为：_______________________。
2.顺序表中逻辑上相邻的元素物理位置()相邻，单链表中逻辑上相邻的元素物理位置_________相邻。
3.线性表L＝（a1，a2，...，an）采用顺序存储，假定在不同的n＋1个位置上插入的概率相同，则插入一个新元素平均需要移动的元素个数是________________________ 4.在非空双向循环链表中，在结点q的前面插入结点p的过程如下：
p->prior=q->prior;q->prior->next=p;p->next=q;______________________;
5.已知L是无表头结点的单链表，是从下列提供的答案中选择合适的语句序列，分别实现：
（1）表尾插入s结点的语句序列是_______________________________(2)表尾插入 s结点的语句序列是_______________________________
1.p->next=s;2.p=L;3.L=s;
4.p->next=s->next;
5.s->next=p->next;6.s->next=L;7.s->next=null;
8.while(p->next!= Q)? p=p-next;9.while(p->next!=null)p=p->next;
四、算法设计题
1.试编写一个求已知单链表的数据域的平均值的函数（数据域数据类型为整型）。
2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数。
3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现出库（销售）m台价格为h的电视机，试编写算法修改原链表。
4.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个循环链表，每个结点有价格、数量和链指针三个域。现新到m台价格为h的电视机，试编写算法修改原链表。
5.线性表中的元素值按递增有序排列，针对顺序表和循环链表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b（a≤b）之间的元素。
6.设A=(a0,a1,a2,...,an-1),B=(b0,b1,b2,...,bm-1)是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数。
若n=m，且 ai= bi（0≤i 若n 若存在一个j，j 试编写一个比较A和B的C函数，该函数返回-1或 0或 1，分别表示 A 7.试编写算法,删除双向循环链表中第k个结点。 8.线性表由前后两部分性质不同的元素组成(a0,a1,...,an-1,b0,b1,...,bm-1),m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成(b0,b1,...,bm-1,a0,a1,...,an-1),分析两种存储方式下算法的时间和空间复杂度。 9.用循环链表作线性表(a0,a1,...,an-1)和（b0,b1,...,bm-1）的存储结构,头指针分别为ah和bh，设计C函数，把两个线性表合并成形如（a0,b0,a1,b1,…）的线性表，要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度。 10.试写出将一个线性表分解为两个带有头结点的循环链表，并将两个循环链表的长度放在各自的头结点的数据域中的C函数。其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。 11.试写出把线性链表改为循环链表的C函数。 12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。 参考答案： 一、选择题 1.B 2.C 3.D 4.B 5.A 6.A 7、C 二、判断题: 参考答案： 1、× 2、√ 3、× 4、× 5、√ 三、填空题 1、s->next=p->next;p->next=s; 2、一定；不一定 3、n/2 4、q->prior=p; 5、(1)6)3)(2)2)9）1)7) 四、算法设计题 1、#include “stdio.h” #include “malloc.h” typedef struct node {int data;struct node *link;}NODE;int aver(NODE *head){int i=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” typedef struct node { int data;/* 假设数据域为整型 */ struct node *link;}NODE;void del_link(NODE *head,int x)/* 删除数据域为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、void del(NODE *head,float price,int num){ NODE *p,*q,*s;p=head;q=head->next;while(q->price next;} if(q->price==price)q->num=q->num-num;else printf(“无此产品”);if(q->num==0){ p->next=q->next;free(q);} } 4、#include “stdio.h” #include “malloc.h” typedef struct node { float price;int num;struct node *next;}NODE;void ins(NODE *head,float price,int num) { NODE *p,*q,*s;p=head;q=head->next;while(q->price 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个位置，最后修改线性表的长度。 void del（elemtype list[]，int *n，elemtype a，elemtype b） { int i=0，k=0； while（i i++;} *n=*n-k;/* 修改线性表的长度*/ } 循环链表: void del(NODE *head,elemtype a,elemtype b){ NODE *p,*q;p= head;q=p->link;/* 假设循环链表带有头结点 */ while(q!=head && q->data 6、#define MAXSIZE 100 int listA[MAXSIZE],listB[MAXSIZE];int n,m;int compare(int a[],int b[]){ int i=0; while(a[i]==b[i]&&i 7、void del(DUNODE **head,int i){ DUNODE *p;if(i==0){ *head=*head->next;*head->prior=NULL;return(0);} Else {for(j=0;j void convert(elemtype list[],int l,int h)/* 将数组中第l个到第h个元素逆置*/ { int i;elemtype temp;for(i=h;i<=(l+h)/2;i++){ temp=list[i];list[i]=list[l+h-i];list[l+h-i]=temp;} } void exchange(elemtype list[],int n,int m);{ convert(list,0,n+m-1);convert(list,0,m-1);convert(list,m,n+m-1);} 该算法的时间复杂度为O(n+m),空间复杂度为O(1)链接存储:(不带头结点的单链表)typedef struct node { elemtype data;struct node *link;}NODE;void convert(NODE **head,int n,int m){ NODE *p,*q,*r;int i;p=*head;q=*head;for(i=0;i q=q->link;/*q指向an-1结点 */ r=q->link;q->link=NULL;while(r->link!=NULL)r=r->link;/*r指向最后一个bm-1结点 */ *head=q;r->link=p;} 该算法的时间复杂度为O(n+m),但比顺序存储节省时间(不需要移动元素,只需改变指针),空间复杂度为O(1)9.typedef struct node { elemtype data;struct node *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的结点个数 */ { a->link=b;while(b->link!=bh)b=b->link;b->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.typedef struct node { elemtype data;struct node *link;}NODE;void analyze(NODE *a） { NODE *rh，*qh，*r,*q,*p； int i=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.typedef struct node { elemtype data;struct node *link;}NODE;void change(NODE *head){ NODE *p;p=head;if(head!=NULL){ while(p->link!=NULL)p=p->link;p->link=head;} } 12.typedef struct node { elemtype data;struct node *link;}NODE;void del(NODE *x,NODE *y){ NODE *p,*q;elemtype d1;p=y;q=x;while(q->next!=NULL)/* 把后一个结点数据域前移到前一个结点*/ { p->data=q->data;q=q->link;p=q;p->link=NULL;/* 删除最后一个结点*/ free(q);} 第三章 栈和队列 一、选择题 1.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。（A）edcba（B）decba（C）dceab（D）abcde 2.栈结构通常采用的两种存储结构是（）。 （A）线性存储结构和链表存储结构（B）散列方式和索引方式（C）链表存储结构和数组（D）线性存储结构和非线性存储结构 3.判定一个栈ST(最多元素为m0)为空的条件是（）。（A）ST-〉top!=0（B）ST-〉top==0（C）ST-〉top!=m0（D）ST-〉top=m0 4.判定一个栈ST(最多元素为m0)为栈满的条件是（）。（A）ST->top!=0（B）ST->top==0（C）ST->top!=m0-1（D）ST->top==m0-1 5.一个队列的入列序列是1,2,3,4,则队列的输出序列是（）。（A）4,3,2,1（B）1,2,3,4（C）1,4,3,2（D）3,2,4,1 6.循环队列用数组A[0,m-1]存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是（） （A）(rear-front+m)%m（B）rear-front+1（C）rear-front-1（D）rear-front 7.栈和队列的共同点是（） （A）都是先进后出（B）都是先进先出 （C）只允许在端点处插入和删除元素（D）没有共同点 8.表达式a*(b+c)-d的后缀表达式是（）。 （A）abcd*+-（B）abc+*d-（C）abc*+d-（D）-+*abcd 9.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，a1 10.以数组Q[0..m－1]存放循环队列中的元素，变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是（）(A)rear－qulen(B)rear－qulen＋m (C)m－qulen (D)1＋（rear＋m－qulen）% m 二、填空题 1.栈的特点是_______________________,队列的特点是__________________________。2.线性表、栈和队列都是_____________________结构,可以在线性表的______________位置插入和删除元素，对于栈只能在________插入和删除元素，对于队列只能在_______插入元素 和_________删除元素。 3.一个栈的输入序列是12345,则栈有输出序列12345是____________。(正确/错误)4.设栈S和队列Q的初始状态皆为空，元素a1，a2，a3，a4，a5和a6依次通过一个栈，一个元素出栈后即进入队列Q，若6个元素出队列的顺序是a3，a5，a4，a6，a2，a1则栈S至少应该容纳_____个元素。 三、算法设计题 1.假设有两个栈s1和s2共享一个数组stack[M],其中一个栈底设在stack[0]处，另一个栈底设在stack[M-1]处。试编写对任一栈作进栈和出栈运算的C函数push（x,i)和pop(i),i=l,2。其中i=1表示左边的栈，,i=2表示右边的栈。要求在整个数组元素都被占用时才产生溢出。 2.利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算?写出模拟队列的插入和删除的C函数。 一个栈s1用于插入元素,另一个栈s2用于删除元素.参考答案： 一、选择题 1.C 2.A 3.B 4.B 5.B 6.B 7、C 8、C 9、C 10、D 二、填空题 1、先进先出；先进后出 2、线性 ； 任何 ；栈顶；队尾；对头 3、正确的 4、3 三、算法设计题 1.#define M 100 elemtype stack[M];int top1=0,top2=m-1;int push(elemtype x,int i){ if(top1-top2==1)return(1);/*上溢处理*/ else if(i==1)stack[top1++]=x;if(i==2)stack[top2--]=x;return(0);} int pop(elemtype *px,int i){ if(i==1)if(top1==0)return(1);else { top1--;*px=stack[top1];return(0);} else if(i==2)if(top2==M-1)return(1);else { top2++;*px=stack[top2];return(0);} } 2.elemtype s1[MAXSIZE],s2[MAZSIZE];int top1,top2;void enqueue(elemtype x){ if(top1==MAXSIZE)return(1);else { push(s1,x);return(0);}} void dequeue(elemtype *px){ elemtype x;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) 3.字符串满足下式,其中head和tail的定义同广义表类似,如head(‘xyz’)= ‘x’,tail(‘xyz’)= ‘yz’,则s=()。concat(head(tail(s)),head(tail(tail(s))))= ‘dc’。 (A)abcd(B)acbd(C)acdb(D)adcb 4.串是一种特殊的线性表,其特殊性表现在（）(A)可以顺序存储(B)数据元素是一个字符(C)可以链式存储(D)数据元素可以是多个字符 5．设串S1=‘ABCDEFG’,s2=‘PQRST’,函数CONCAT（X，Y）返回X和Y串的连接串，SUBSTR（S，I，J）返回串S从序号I开始的J个字符组成的字串，LENGTH（S）返回串S的长度，则CONCAT（SUBSTR（S1，2，LENGTH（S2）），SUBSTR（S1，LENGTH（S2），2））的结果串是（） （A）BCDEF(B)BCDEFG(C)BCPQRST(D)BCDEFEF 二、算法设计 1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。 2.在一般链接存储(一个结点存放一个字符)方式下,写出采用简单算法实现串的模式匹配的C语言函数int L_index(t,p)。 参考答案： 一、选择题 1.A 2.B 3.D 4.D 5.D 二、算法设计 1.顺序存储： #include “string.h” #define MAXN 100 char s[MAXN];int S_strlen(char s[]){ int i;for(i=0;s[i]!=' ';i++);return(i);} void S_strcpy(char s1[],char s2[])//4.3题 { int i;for(i=0;s1[i]!=' ';i++)s2[i]=s1[i];s2[i]=' ';} 一般链接存储： #include “stdio.h” typedef struct node { char data;struct node *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” typedef struct node { char data;struct node *link;}NODE;int L_index(NODE *t,NODE *p){ NODE *t1,*p1,*t2;?int i;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);} 第五章 数组和广义表 一、选择题 1.常对数组进行的两种基本操作是（） （A）建立与删除（B）索引和修改（C）查找和修改（D）查找与索引 2.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素()的起始地址相同。 （A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4] 3.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。（A）80（B）100（C）240（D）270 4.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A[7][4]的起始地址为（）。（A）SA+141（B）SA+144（C）SA+222（D）SA+225 5.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。（A）SA+141（B）SA+180（C）SA+222（D）SA+225 6.稀疏矩阵一般的压缩存储方法有两种,即（）。（A）二维数组和三维数组（B）三元组和散列（C）三元组和十字链表（D）散列和十字链表 7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点（）。（A）正确（B）错误 8.设矩阵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 二、填空题 1.己知二维数组A[m][n]采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOC(A[0][0]),则A[0][0]的地址是_____________________。 2.二维数组A[10][20]采用列序为主方式存储,每个元素占一个存储单元,并且A[0][0]的存储地址是200,则A[6][12]的地址是________________。 3.有一个10阶对称矩阵A,采用压缩存储方式(以行序为主,且A[0][0]=1),则A[8][5]的地址是__________________。 4.设n行n列的下三角矩阵A已压缩到一维数组S[1..n*(n+1)/2]中,若按行序为主存储,则A[i][j]对应的S中的存储位置是________________。 5.若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.C 2.B 3.C 4.C 5.B 6.C 7、B 8、B 二、填空题 1、loc(A[0][0])+(n*i+j)*k 2、332 3、42 4、i*(i+1)/2+j+1 5、1039；72 三、算法设计题 1.算法思想：依题意,先求出每行的最小值元素,放入min[m]之中,再求出每列的最大值元素,放入max[n]之中,若某元素既在min[i]中,又在max[j]中,则该元素A[i][j]便是马鞍点,找出所有这样的元素,即找到了所有马鞍点。因此,实现本题功能的程序如下: #include for(j=0;j a[j]=0;count=0;d++;} } } 3.#include “stdio.h” #include “malloc.h” typedef struct node { int tag;union {struct node *sublist;char data;}dd;struct node *link;}NODE;NODE *creat_GL(char **s){ NODE *h;char ch;ch=*(*s);(*s)++;if(ch!=' '){ h=(NODE*)malloc(sizeof(NODE));if(ch=='('){ h->tag=1;h->dd.sublist=creat_GL(s);} Else { h->tag=0;h->dd.data=ch;} } else h=NULL;ch=*(*s);(*s)++;if(h!=NULL)if(ch==',')h->link =creat_GL(s);else h->link=NULL;return(h);} void prn_GL(NODE *p){ if(p!=NULL){ if(p->tag==1){ printf(“(”);if(p->dd.sublist ==NULL)printf(“ ”);else prn_GL(p->dd.sublist);} else printf(“%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);else q->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);} int sum(NODE *p)/*求原子结点的数据域之和函数 */ { int m,n;if(p==NULL)return(0);else { if(p->tag==0)n=p->dd.data;else n=sum(p->dd.sublist);if(p->link!=NULL)m=sum(p->link);else m=0;return(n+m);} } int depth(NODE *p)/*求表的深度函数 */ { int h,maxdh;NODE *q;if(p->tag==0)return(0);else if(p->tag==1&&p->dd.sublist==NULL)return 1;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;char s[100],*p;p=gets(s);hd=creat_GL(&p);prn_GL(head(hd));prn_GL(tail(hd));hc=copy_GL(hd);printf(“copy after:”);prn_GL(hc); printf(“sum:%dn”,sum(hd));printf(“depth:%dn”,depth(hd));} 第六章 树和二叉树 一、选择题 1.在线索化二叉树中,t所指结点没有左子树的充要条件是（）（A）t-〉left==NULL（B）t-〉ltag==1（C）t-〉ltag=1且t-〉left=NULL（D）以上都不对 2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法（A）正确（B）错误（C）不同情况下答案不确定 3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法（）(A)正确(B)错误（C）不同情况下答案不确定 4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法（）（A）正确（B）错误（C）不同情况下答案不确定 5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为 （）。 （A）2h（B）2h-1（C）2h+1（D）h+1 6.已知某二叉树的后序遍历序列是dabec。中序遍历序列是debac,它的前序遍历序列是（）。（A）acbed（B）decab（C）deabc（D）cedba 7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的（）（A）前序（B）中序（C）后序（D）层次序 8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是（）。 （A）bdgcefha（B）gdbecfha（C）bdgaechf（D）gdbehfca 9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（） （A）正确（B）错误（C）不同情况下答案不确定 10.按照二叉树的定义,具有3个结点的二叉树有（）种。（A）3（B）4（C）5（D）6 11.在一非空二叉树的中序遍历序列中,根结点的右边（）（A）只有右子树上的所有结点（B）只有右子树上的部分结点（C）只有左子树上的部分结点（D）只有左子树上的所有结点 12.树最适合用来表示（）。 （A）有序数据元素（B）无序数据元素 （C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据 13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）（A）不发生改变（B）发生改变（C）不能确定D.以上都不对 14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用（）存储结构。 （A）二叉链表（B）广义表存储结构（C）三叉链表（D）顺序存储结构 15.对一个满二叉树,m个树叶,n个结点,深度为h,则（）（A）n=h+m（B）h+m=2n（C）m=h-1（D）n=2h-1 16.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为（）（A）uwvts（B）vwuts（C）wuvts（D）wutsv 17.具有五层结点的二叉平衡树至少有（）个结点。（A）10（B）12（C）15（D）17 二、判断题 1.二叉树中任何一个结点的度都是2。（） 2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。（）3.一棵哈夫曼树中不存在度为1的结点。（） 4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2（） 三、填空题 1.指出树和二叉树的三个主要差别___________,___________,_______________。2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是____________ 3.若结点A有三个兄弟(包括A本身),并且B是A的双亲结点,B的度是_______________ 4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域。 5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________。 6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列_________________。7.找出满足下列条件的二叉树 1）先序和中序遍历，得到的结点访问顺序一样。_________________________ 2）后序和中序遍历，得到的结点访问顺序一样。_________________________ 3）先序和后序遍历，得到的结点访问顺序一样。__________________________ 8.一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各是多少？____________________ 9.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有______________________个。 10.含有100个结点的树有_______________________________________条边。 四、问答题 1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:(1)第k层结点数(1≤k≤h)。(2)整棵树结点数。 (3)编号为i的结点的双亲结点的编号。 (4)编号为i的结点的第j个孩子结点(若有)的编号。 2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系： n0=（k-1）n1+1 3.已知一组元素为(50,28,78,65,23,36,13,42,71）,请完成以下操作:(1)画出按元素排列顺序逐点插入所生成的二叉排序树BT。 (2)分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数。(3)画出在BT中删除(23〉后的二叉树。 4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树(请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数。 5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9。 (1)试画出对应的编码哈夫曼树(要求左子树根结点的权小于等于右子树根结点的权)。(2)求出每个字符的晗夫曼编码。(3)求出传送电文的总长度。 (4)并译出编码系列***1的相应电文。 五、算法设计 已知一棵具有n个结点的完全二叉树被顺序存储在一维数组A[n]中,试编写一个算法输出A[i]结点的双亲和所有孩子。 参考答案： 一、选择题 1.B 2.B 3.A 4.B 5.B 6.D 7、A 8、D 9、B 10、C 11、A 12、C 13、A 14、C 15、D 16、C 17 C 二、判断题 1× 2× 3√ 4√ 三、填空题 1、①树的结点个数至少为1，而二叉树的结点个数可以为0； ②树种结点的最大读书没有限制，而二叉树结点的最大度数不能超过2； ③树的结点无左右之分，而二叉树的结点有左右之分。 2、树可采用二叉树的存储结构并利用二叉树的已有算法解决树的有关问题。3、4 4、n+1 5、DGEBHJIFCA 6、ABDEGCEH 7、①无左子树②无右子树③仅一个结点的二叉树 8、最大n,最小┕log2n┙+1 9、22 10、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+1 n0=(k-1)*n1+1 五、算法设计 void parent(int a[],int n,int i){ if(i==1){ printf(“无双亲 n”);return;} Else printf(“双亲:%dn”,a[(i-1)/2]);} void child(int a[],int n,int i)/*i为序号 */ { int queue[MAX],front=0,tail=0,p;/* 队列作为辅助，存储孩子的序号*/ queue[0]=i;tail++;while(front #include “stdio.h” #include “malloc.h” typedef struct node { char data;struct node *lchild,*rchild;}NODE; NODE *T;void create(NODE **T)//创建二叉树 { char ch;ch=getchar();if(ch==' ')*T=NULL;else { *T=(NODE *)malloc(sizeof(NODE));(*T)->data=ch;create(&((*T)->lchild));create(&((*T)->rchild));? } } void inorder(NODE *p)//中序编历二叉树 { if(p!=NULL){ inorder(p->lchild);?? printf(“%c ”,p->data);? inorder(p->rchild);??? }? } int num=0;void count(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);} } void count1(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);} } int onechild(NODE *t)//统计出二叉树中单孩子的结点数方法2 { int num1,num2;if(t==NULL)return(0);else if(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);} } int sum(NODE *t)//统计出二叉树中所有结点数 {if(t==NULL)return(0);else return(sum(t->lchild)+sum(t->rchild)+1);} int leaf(NODE *t)//统计出二叉树中叶子结点数 { if(t==NULL)return(0);else if(t->lchild==NULL&&t->rchild==NULL)return(leaf(t->lchild)+leaf(t->rchild)+1);else return(leaf(t->lchild)+leaf(t->rchild)); } void preorder1(NODE *root)//非递归二叉树前序编历 { NODE *p,*s[100],*q;//q为p的双亲结点 int top=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;}} void delk(NODE **root,char k)//删去并释放数据值为k的叶结点 { NODE *p,*s[100],*q;//q为p的双亲结点 int top=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;else q->rchild=NULL;free(p);return;} s[++top]=p;q=p;p=p->lchild;} p=s[top--];q=p;p=p->rchild;}} void lev_traverse(NODE *T)//按层次从上到下,每层从右到左的顺序列出二叉树所有结点的数据信息 {NODE *q[100],*p;int head,tail;q[0]=T;head=0;tail=1;while(head { 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;} return num;} int like(NODE *t1,NODE *t2)//判定两颗二叉树是否相似 { int like1,like2;if(t1==t2&&t2==NULL)return(1);else if(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);} } char a[100];//数组顺序存储二叉树 void change(NODE *t,int i)//将二叉树的链接存储转换为顺序存储 { if(t!=NULL){a[i]=t->data;change(t->lchild,2*i);change(t->rchild,2*i+1);} } int complete(NODE *t)//判断二叉树是否为完全二叉树 { int i,flag=0;change(t,1);for(i=1;i<100;i++){if(!flag&&a[i]==' ')flag=1;if(flag&&a[i]!=' ')break;} if(i==100)return(1);else return(0);} 第七章 图 一、判断题 1.一个无向图的邻接矩阵中各非零元素之和与图中边的条数相等。（） 2.一个有向图的邻接矩阵中各非零元素之和与图中边的条数相等。（） 3.一个对称矩阵一定对应着一个无向图。（） 4.一个有向图的邻接矩阵一定是一个非对称矩阵。（） 二、选择题 1.在一个图中,所有顶点的度数之和等于所有边数的（）倍。 （A）1/2（B）1（C）2（D）4 2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的（）倍。 （A）1/2（B）1（C）2（D）4 3.一个有n个顶点的无向图最多有（）条边。 （A）n（B）n(n-1)（C）n(n-1）/2（D）2n 4.具有4个顶点的无向完全图有（）条边。 （A）6（B）12（C）16（D）20 5.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。 （A）5（B）6（C）7（D）8 6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要（）条边。 （A）n（B）n+1（C）n-1（D）n/2 7.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小（） （A）n（B）(n-1)2（C）n-1（D）n2 8.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为（），所有邻接表中的结点总数是（）。 ①（A）n（B）n+1（C）n-1（D）n+e ②（A）e/2（B）e（C）2e（D）n+e 9.采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。 （A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历 10.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（）。 （A）先序遍历（B）中序遍历（C）后序遍历（D）按层遍历 11.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用（）.（A）求关键路径的方法（B）求最短路径的Dijkstm方法 （C）宽度优先遍历算法（D）深度优先遍历算法 12.用Prim算法求下列连通的带权图的最小代价生成树，在算法执行的某刻，已选取的顶点集合U＝{1，2，5}，边的集合TE＝{（1，2），（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个顶点的连通图至少_____________条边。 2.在一个无环有向图G中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是_________________。 3.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是________________条。 4.如果从一个顶点出发又回到该顶点，则此路径叫做_______。 5.如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是____________。 6.若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的________遍历。 7.一个连通图的生成树是该图的________连通子图。若这个连通图有n个顶点, 则它的生成树有________条边。 四、算法设计： 1.试在无向图的邻接矩阵和邻接链表上实现如下算法： (1)往图中插入一个顶点 (2)往图中插入一条边 (3)删去图中某顶点 (4)删去图中某条边 2.下面的伪代码是一个广度优先搜索算法，试以下图中的v0为源点执行该算法，请回答下述问题： (1)对图中顶点vn+1，它需入队多少次？它被重复访问多少次?(2)若要避免重复访问同一个顶点的错误，应如何修改此算法? void BFS(ALGraph *G,int k){//以下省略局部变量的说明，visited各分量初值为假 InitQueue(&Q);//置空队列 EnQueue(&Q,k);//k入队 while(!QueueEmpty(&Q)){ i=DeQueue(&Q);//vi出队 visited[i]=TRUE;//置访问标记 printf(“%c”,G->adjlist[i].vertex;//访问vi for(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 3.试以邻接表和邻接矩阵为存储结构，分别写出基于DFS和BFS遍历的算法来判别顶点vi和 vj(i<>j)之间是否有路径。 4.试分别写出求DFS和BFS生成树(或生成森林)的算法，要求打印出所有的树边。 5.写一算法求连通分量的个数并输出各连通分量的顶点集。 6.设图中各边的权值都相等，试以邻接矩阵和邻接表为存储结构，分别写出算法： (1)求顶点vi到顶点vj(i<>j)的最短路径 (2)求源点vi到其余各顶点的最短路径 要求输出路径上的所有顶点(提示：利用BFS遍历的思想)7.以邻接表为存储结构，写一个基于DFS遍历策略的算法，求图中通过某顶点vk的简单回路(若存在)。 8.写一算法求有向图的所有根(若存在)，分析算法的时间复杂度。 参考答案： 一、判断题 1、× 2、√ 3、× 4、× 二、选择题 1.C 2.B 3.C 4.A 5.A 6.C 7、B 8、A、C 9、A 10、D 11、D 12、B 三、填空题 1、n-1 2、i在前，j在后 3、m/2 4、回路 5、强连通图 6、按层 7、极大；n-1 第八章 查找 一、判断题 1.用二分查找法对一个顺序表进行查找，这个顺序表可以是按各键值排好序的，也可以是没有按键值排好序的。（） 2.哈希表的查找不用进行关键字的比较。（） 3.哈希表的定义函数H（key）=key%p(p<=m)这种方法是直接定址法。（） 4.装填因子α的值越大，就越不容易发生冲突。()5.选择hash函数的标准为：随机性好、均匀性好和尽量避免冲突。() 二、填空题 1.顺序查找法的平均查找长度为__________，二分查找法的平均查找长度为________，分块 查找法(以顺序查找确定块)的平均查找长度为__________，分块查找法(以二分查找确定块〉的平均查找长度为_________，哈希表查找法采用链接法处理冲突时的平均查找长度为_________。 2.在各种查找方法中,平均查找长度与结点个数n无关的查法方法是_________ 3.二分查找的存储结构仅限于_________,且是__________。 4.在分块查找方法中,首先查找__________,然后再查找相应的___________。 5.长度为255的表,采用分块查找法,每块的最佳长度是____________。 6.在散列函数H(key)=key%p中,p应取_______________。 7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为_________,则比较二次查找成功的结点数为__________,则比较三次查找成功的结点数为_________,则比较四次查找成功的结点数为________,则比较五次查找成功的结点数为_________,平均查找长度为_________。 8.对于长度为n的线性表,若进行顺序查找,则时间复杂度为__________，若采用二分法查找,则时间复杂度为_________。 9.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和90的元素时,分别需要________次和____________次比较才能查找成功；若采用顺序查找时,分别需要___________次和_________次比较才能查找成功。 三、选择题 1.顺序查找法适合于存储结构为（）的线性表。 （A）散列存储（B）顺序存储或链接存储（C）压缩存储（D）索引存储 2.对线性表进行二分查找时,要求线性表必须（）。 （A）以顺序方式存储（B）以链接方式存储 （C）以顺序方式存储,且结点按关键字有序排序 （D）以链接方式存储,且结点按关键字有序排序 3.采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为（） （A）n（B）n/2（C）(n+1)/2（D）(n-1)/2 4.采用二分查找方法查找长度为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（D）8 7.设哈希表长m=14,哈希函数H(key)=key%11。表中已有4个结点: addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址为空，如用二次探测再散列处理冲突,关键字为49的结点的地址是（）。 （A）8（B）3（C）5（D）9 8.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为（?） （A）35/12（B）37/12（C）39/12（D）43/12 9.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分（）个结点最佳。 （A）10（B）25（C）6（D）625 10.如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用（）查找方法。 （A）分块（B）顺序（C）二分（D）散列 四、问答题 1.已知一个线性表为(38,25,74,63,52,48),假定采用H(k)=k%7计算散列地址进行散列存储,试分别求出利用线性探测的开放定址法处理冲突和利用链接法处理冲突,在该散列表上进行查找的平均查找长度。 2.己知线性表的元素为(87,25,310,8,27,132,68,95,187,123,70,63,47),散列函数为h(k)=k%13,采用链接法处理冲突。设计出这种链表结构,并求该表平均查找长度。 3.假定一个待散列存储的线性表为(32,75,63,48，94,25,36,18,70),散列地址空间为[0...10],若采用除留余数法构造散列函数和线性探查法处理冲突,试给出它们对应的散列表,并求出在等概率情况下的平均查找长度。 4.试用连线把右边是四种线性表的存储结构与左边对应的操作的特点连接起来。 (A）散列表（1）查找和存取速度快,但插入和删除速度慢。 (B)顺序有序表(2）查找、插入和删除速度快,但不能进行顺序存取。 (C)顺序表(3）插入、删除和顺序存取速度快,但查找速度慢。 (D)链接表(4)查找、插入和删除速度慢,但顺序存取和随机存取第i个元素速度快。 五、应用题 设闭散列表容量为7，给定表（30，36，47，52，34），散列函数H（K）＝k mod 6，采用线性探测解决冲突，要求： （1）构造此散列表(散列地址为0~6)： （2）求查找34需要进行比较的次数。 六、算法设计 哈希表的删除 参考答案： 一、判断题 1、× 2、× 3、× 4、× 5、√ 二、填空题 1、(n+1)/2；((n+1)*log2(n+1))/n-1；(s2+2s+n)/2s；log2(n/s+1)+s/2；1+α 2、哈希表查找 3、顺序；有序的 4、索引；块 5、15 6、小于表长的最大素数 7、①1 ②2 ③4 ④8 ⑤5 ⑥3.7 8、①O(n)② O(log2n)9、4、4、5、10 三、选择题 1.B 2.C 3.C 4.D 5.B 6.C 7.D 8.B 9.B 10.A 六、算法设计 哈希表的删除 hashtable del_hashtable(hashtable &hash, keytype K){t=h(k);if(hash[t]= = null)return(“infeasible”);else if(hash[t]= =K)hash[t]=hash[t]->next;else { found=0;q=hash[t];p=hash[t]->next;while((!found)&&(p<> null))if(p->key= =K) {found=1;q->next=p->next;} else{q=p;p=p->next;} if(!found)return(“infeasible”);} return(hash);} 第九章 排序 一、选择题 1.在所有排序方法中，关键字比较的次数与记录得初始排列次序无关的是（） （A）希尔排序（B）起泡排序（C）插入排序（D）选择排序 2.设有1000个无序的元素,希望用最快的速度挑选出其中前10个最大的元素,最好（）排序法。 （A）起泡排序（B）快速排序（C）堆排序（D）基数排序 3.在待排序的元素序列基本有序的前提下,效率最高的排序方法是（） （A）插入排序（B）选择排序（C）快速排序（D）归并排序 4.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始推为（）。 （A）79,46,56,38,40,80（B）84,79,56,38,40,46（C）84,79,56,46,40,38（D）84,56,79,40,46,38 5.一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（）。 （A）38,40,46,56,79,84（B）40,38,46,79,56,84（C）40,38,46,56,79,84（D）40,38,46,84,56,79 6.一组记录的排序码为(25,48,16,35,79,82,23,40,36,72),其中含有5个长度为2的有序表,按归并排序的方法对该序列进行一趟归并后的结果为（）。 （A）16,25,35,48,23,40,79,82,36,72（B）16,25,35,48,79,82,23,36,40,72（C）16,25,48,35,79,82,23,36,40,72（D）16,25,35,48,79,23,36,40,72,82 7.排序方法中,从未排序序列中依次取出元素与己排序序列(初始时为空)中的元素进行比较,将其放入己排序序列的正确位置上的方法,称为（） 第一章 第1章作业：1.1,1.2,1.6(1)(3)1.8 1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。● 数据：指能够被计算机识别、存储和加工处理的信息载体。 ● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。 ● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。 ● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 ● 逻辑结构：指数据元素之间的逻辑关系。 ● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。 这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。 在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。 1.6 设n为正整数，利用大“O”记号，将下列程序段的执行时间表示为n的函数。 (1)i=1;k=0;while(i 通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： T(n)=O(n) 1.8 按增长率由小至大的顺序排列下列各函数：2100,(3/2)n，(2/3)n，nn ,n0.5 , n!，2n，lgn ,nlgn, n(3/2) 答：常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。先将题中的函数分成如下几类： 常数阶：2 对数阶：lgn K次方阶：n、n0.5(3/2)100 指数阶(按指数由小到大排)：nlgn、(3/2)n、2n、n!、nn 注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：(2/3)n < 2100 < lgn < n0.5 < n(3/2)< nlgn <(3/2)n < 2n < n!< nn 第二章 第二章作业：2.2，2.6,2.9,2.13 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑： 1.基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。 2.基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。2.6 下述算法的功能是什么? LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P;if(L&&L->next){ Q=L;L=L->next;P=L;while(P->next)P=P->next;P->next=Q;Q->next=NULL;} return L;}// Demo 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。 2.7 设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.解：算法如下: #define ListSize 100 // 假定表空间大小为100 typedef int DataType;//假定DataType的类型为int型 typedef struct{ DataType data[ListSize];// 向量data用于存放表结点 int length;// 当前的表长度 } Seqlist;//以上为定义表结构 void InsertList(Seqlist *L, Datatype x, int i){ //将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length int j;if(i < 0 || i > L-> length)Error(“position error”);// 非法位置，退出，if(L->length>=ListSize)Error(“overflow“); for(j=L->length-1;j >= i;j--)L->data[ j+1]=L->data [ j ];L->data[ i ]=x;L->length++;} 2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。 答：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。 算法如下： //顺序表存储结构如题2.7 void InsertIncreaseList(Seqlist *L , Datatype x){ int i;if(L->length>=ListSize)Error(“overflow”); for(i=L-> length;i>0 && L->data[ i-1 ] > x;i--)L->data[ i ]=L->data[ i ];// 比较并移动元素 L->data[ i ] =x;L-> length++;} 2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。 解：根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。 算法如下： LinkList MergeSort(LinkList A , LinkList B){// 归并两个带头结点的递增有序表为一个带头结点递减有序表 ListNode *pa , *pb , *q , *C;pa=A->next;//pa指向A表开始结点 C=A;C->next=NULL;//取A表的表头建立空的C表 pb=B->next;//pb指向B表开始结点 free(B);//回收B表的头结点空间 while(pa && pb){ if(pb->data <= pa->data){ // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下 q=pa;pa=pa->next;} else {// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下 q=pb;pb=pb->next;} q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表 } //若pa表非空，则处理pa表 while(pa){ q=pa;pa=pa->next;q->next=C->next;C->next=q;} //若pb表非空，则处理pb表 while(pb){ q=pb;pa=pb->next;q->next=C->next;C->next=q;} return(C);} 该算法的时间复杂度分析如下： 算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n) ●练习2.1：写出在线性表中的查找运算算法。 即查找数据元素x在表中的位置，也就是数据元素下标值加1。 例如：若L.data[i]=x,则返回i+1;若不存在，则返回n+1 练习2.2：编写尾插法建立链表的算法。 练习2.3：若是带头指针的单链表，算法又是怎样？ 若是两个链表，既知道头结点，又知道尾结点，算法又是怎样？ ●练习2：按升序打印带头结点h的单链表中各节点的数据域值，并将打印完的节点从表中删除。 第三章 第三章作业：3.2, 3.3，3.4（2），3.6，3.11 3.2 循环队列的优点是什么? 如何判别它的空和满? 答：循环队列的优点是：它可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的“空”或“满”不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 3.3设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。3.4 指出下述程序段的功能是什么?(2)SeqStack S1, S2, tmp; DataType x; ...//假设栈tmp和S2已做过初始化 while(!StackEmpty(&S1)) { x=Pop(&S1); Push(&tmp,x); } while(!StackEmpty(&tmp)) { x=Pop(&tmp); Push(&S1,x); Push(&S2, x); }(2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。 3.6 利用栈的基本操作，写一个将栈S中所有结点均删去的算法void ClearStack(SeqStack *S)，并说明S为何要作为指针参数 解：算法如下 void ClearStack(SeqStack *S) { // 删除栈中所有结点 S->Top =-1;//其实只是将栈置空 } 因为要置空的是栈S，如果不用指针来做参数传递，那么函数进行的操作不能对原来的栈产生影响，系统将会在内存中开辟另外的单元来对形参进行函数操作。结果等于什么也没有做。所以想要把函数操作的结果返回给实参的话，就只能用指针来做参数传递了。 3.8 设计算法判断一个算术表达式的圆括号是否正确配对。(提示： 对表达式进行扫描，凡遇到‘(’就进栈，遇‘)’就退掉栈顶的‘(’，表达式被扫描完毕，栈应为空。解： 根据提示，可以设计算法如下： int PairBracket(char *SR) {//检查表达式SR中括号是否配对 int i; SeqStack S;//定义一个栈 InitStack(&s); for(i=0;i { if(SR[i]==‘(’)Push(&S, SR[i]);//遇‘(’时进栈 if(SR[i]==‘)’)//遇‘)’ if(!StackEmpty(S))//栈不为空时，将栈顶元素出栈 Pop(&s); else return 0;//不匹配，返回0 } if（EmptyStack(&s)）return 1;// 匹配，返回1 else return 0;//不匹配，返回0 } 6.12 若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。(2)已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。(3)已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。解： (1)已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点： ○A / ○B ○C / / ○D ○E○F / / ○G ○H ○I (2)以同样的方法可画出该二叉树： ○A / ○B ○F ○C ○G / ○D ○E ○H (3)这两棵不同的二叉树为： ○A ○A / ○B ○B 6.21 以二叉链表为存储结构，写一算法交换各结点的左右子树。 答：要交换各结点的左右子树，最方便的办法是用后序遍历算法，每访问一个结点时把两棵子树的指针进行交换，最后一次访问是交换根结点的子树。 void ChangeBinTree(BinTree *T) { //交换子树 if(*T) { //这里以指针为参数使得交换在实参的结点上进行后序遍历 BinTree temp; ChangeBinTree(&(*T)->lchild); ChangeBinTree(&(*T)->rchild); temp=(*T)->lchild; (*T)->lchild=(*T)->rchild; (*T)->rchild=temp; } } 9.11试写出二分查找的递归算法。解： int BinSearch(SeqList R，KeyType K，int low，int high) { //在有序表R[low..high]中进行二分查找，成功时返回结点的位置，失败时返回零 int mid； //置当前查找区间上、下界的初值 if(low<=high){ //当前查找区间R[low..high]非空 mid=(low+high)/2； if(R[mid].key==K)return mid； //查找成功返回 if(R[mid].key>K) return BinSearch(R，K,low，mid-1)//在R[low..mid-1]中查找 else return BinSearch(R，K,mid+1，high)； //在R[mid+1..high]中查找 } return 0； //当low>high时表示查找区间为空，查找失败 } //BinSeareh 10.7.将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重写直接插入排序算法。解： 重写的算法如下： void InsertSort(SeqList R) {//对顺序表中记录R[0..n-1]按递增序进行插入排序 int i,j; for(i=n-2;i>=0;i--)//在有序区中依次插入R[n-2]..R[0] if(R[i].key>R[i+1].key)//若不是这样则R[i]原位不动 { R[n]=R[i];j=i+1;//R[n]是哨兵 do{ //从左向右在有序区中查找插入位置 R[j-1]=R[j];//将关键字小于R[i].key的记录向右移 j++; }while(R[j].key R[j-1]=R[n];//将R[i]插入到正确位置上 }//endif }//InsertSort.12.1 常见的文件组织方式有哪几种?各有何特点? 文件上的操作有哪几种? 如何评价文件组织的效率? 答： 常用的文件组织方式有：顺序文件、索引文件、散列文件和多关键字文件。 ●顺序文件的特点是，它是按记录进入文件的先后顺序存放，其逻辑结构和物理顺序是一致的。 ●索引文件的特点是，在主文件之外还另外建立了一张表，由这张表来指明逻辑记录和物理记录之间的一一对应关系。索引文件在存储器上分为两个区：索引区和数据区，前者存放索引表，后者存放主文件。●散列文件是利用散列存储方式组织的，它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上，对于散列文件，磁盘上的文件记录通常是成组存放的。 ●多关键字文件则包含有多个次关键索引的，不同于前述几种文件，只含有一个主关键字。 文件的操作有两种：检索和维护。 评价一个文件组织的效率，是执行文件操作(如查找、删除等)所花费的时间和文件组织所需的存储空间。 《张衡传》课后习题及答案解析 一、这篇文章是从哪几个方面来写张衡的？文章记叙的重点是什么？ 设题意图： 整体把握课文的内容，并能分析课文结构，在此基础上抓住课文重点，进而了解张衡在科学上的成就和贡献。 答：⑴文章从三个方面写张衡：①第一部分（第1段）写张衡的为人以及在文学方面的才能和成就；②第二部分（第2-4段）写张衡在科学技术方面卓越的才能和贡献；③第三部分（第5段）写张衡在政治上的突出作为。⑵第二部分是文章的重点，可分为两层：一是仕途情况，以及制作浑天仪和著《灵宪》、《算图论》的情况；一是专门介绍候风地支仪。显然，后者又是第二部分的重点。 二、翻译下列各句。 设题意图： 积累常见重点实词，区别他们在文中的意思与现代常用义的不同。 ⒈虽才高于世，而无骄尚之情。常从容淡静，不好交接俗人。 译：虽然才能比一般人高出许多，但并不因此而骄傲自大。（他）平时举止从容、态度平静，不喜欢与一般的世俗之人结交。 ⒉衡善机巧，尤致思于天文阴阳历算。 译：张衡善于器械制造方面的巧思，尤其在天文、阴阳历算方面最用心。 ⒊衡不慕当世，所居之官辄积年不徙。 译：张衡不趋附当时的权臣大官，所任的官职就多年得不到提升。 ⒋尝一龙机发而地不觉动，京师学者咸怪其无征。 译：曾有一条龙的机关发动但感觉不到地面动，京师的学者都认为它没有应验这很奇怪。⒌时政事渐损，权移于下，衡因上疏陈事。 译：当时政治局面每况愈下，权利向下转移，张衡于是给皇帝上书陈述这些事。 三、郭沫若曾评价张衡是一个“全面发展”的人。课外搜集资料，以“我看张衡”为题，在班里做一次三分钟演讲。 设题意图： 旨在加深对课文的理解，学习课文所记载的张衡的种种优良品质，同时训练口头表达能力。（参考答案略） 第 1 章 绪 论 课后习题讲解 1.填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2.选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。⑷ 下面（）不是算法所必须具备的特性。A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（），算法分析的两个主要方面是（）。A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 【解答】C，E 3.判断题 ⑴ 算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定。⑵ 每种数据结构都具备三个基本操作：插入、删除和查找。 【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。 ⑶ 所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。 ⑷ 逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。⑸ 基于某种逻辑结构之上的基本操作，其实现是唯一的。 【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4.分析以下各程序段，并用大O记号表示其执行时间。 【解答】⑴ 基本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n)。 ⑵ 基本语句是k=k+10*i，共执行了n次，所以T(n)=O(n)。 ⑶ 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n)。 ⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即： (T(n)+1)2≤n，所以T(n)=O(n1/2)。 ⑸ x++是基本语句，所以 5．设有数据结构（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示，它是一种图结构。 6.为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。【解答】整数的抽象数据类型定义如下： ADT integer Data 整数a：可以是正整数(1, 2, 3, …)、负整数(-1,-2,-3, …)和零 Operation Constructor 前置条件：整数a不存在输入：一个整数b 功能：构造一个与输入值相同的整数 输出：无 后置条件：整数a具有输入的值 Set 前置条件：存在一个整数a 输入：一个整数b 功能：修改整数a的值，使之与输入的整数值相同 输出：无 后置条件：整数a的值发生改变 Add 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相加 输出：相加后的结果 后置条件：整数a的值发生改变 Sub 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相减 输出：相减的结果 后置条件：整数a的值发生改变 Multi 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相乘 输出：相乘的结果 后置条件：整数a的值发生改变 Div 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相除 输出：若整数b为零，则抛出除零异常，否则输出相除的结果 后置条件：整数a的值发生改变 Mod 前置条件：存在一个整数a 输入：一个整数b 功能：求当前整数与输入整数的模，即正的余数 输出：若整数b为零，则抛出除零异常，否则输出取模的结果 后置条件：整数a的值发生改变 Equal 前置条件：存在一个整数a 输入：一个整数b 功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否则返回0 后置条件：整数a的值不发生改变 endADT 7.求多项式A(x)的算法可根据下列两个公式之一来设计： ⑴ A(x)=anxn+an-1xn-1+…+a1x+a0 ⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0 根据算法的时间复杂度分析比较这两种算法的优劣。 【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。 8.算法设计（要求：算法用伪代码和C++描述，并分析最坏情况下的时间复杂度）⑴ 对一个整型数组A[n]设计一个排序算法。【解答】下面是简单选择排序算法的伪代码描述。 下面是简单选择排序算法的C++描述。 分析算法，有两层嵌套的for循环，所以。 ⑵ 找出整型数组A[n]中元素的最大值和次最大值。【解答】算法的伪代码描述如下： 算法的C++描述如下： 分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。 学习自测及答案 1．顺序存储结构的特点是（），链接存储结构的特点是（）。 【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。 2.算法在发生非法操作时可以作出处理的特性称为（）。【解答】健壮性 3.常见的算法时间复杂度用大Ｏ记号表示为：常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n)4．将下列函数按它们在n 时的无穷大阶数，从小到大排列。 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n,(3/2)n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2,(3/2)n, n!5．试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。 6.对下列用二元组表示的数据结构,试分别画出对应的逻辑结构图，并指出属于何种结构。 ⑴ A=(D，R)，其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)，其中D={a, b, c, d, e, f}，R={，，} ⑶ C=(D，R)，其中D={a，b，c，d，e，f}，R={，，,} ⑷ D=(D，R)，其中D={1, 2, 3, 4, 5, 6}，R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)} 【解答】⑴ 属于集合，其逻辑结构图如图1-4(a)所示；⑵ 属于线性结构，其逻辑结构图如图1-4(b)所示；⑶ 属于树结构，其逻辑结构图如图1-4(c)所示；⑷ 属于图结构，其逻辑结构图如图1-4(d)所示。 7.求下列算法的时间复杂度。count=0;x=1;while(x { x*=2;count++;} return count;【解答】Ｏ(log2n) 第 2 章 线性表 课后习题讲解 1.填空 ⑴ 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。 【解答】表长的一半，表长，该元素在表中的位置 ⑵ 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。【解答】108 【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108 ⑶ 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。 【解答】p->next=(p->next)->next ⑷ 单链表中设置头结点的作用是（）。【解答】为了运算方便 【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。 ⑸ 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。【解答】p->next=head 【分析】如图2-8所示。 ⑹ 在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。 【解答】s->next =rear->next;rear->next =s;rear =s;q=rear->next->next;rear->next->next=q->next;delete q;【分析】操作示意图如图2-9所示： ⑺ 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。【解答】Ο(1)，Ο(n) 【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。⑻ 可由一个尾指针唯一确定的链表有（）、（）、（）。【解答】循环链表，循环双链表，双链表 2.选择题 ⑴ 线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。 A 随机存取 B 顺序存取 C 索引存取 D 散列存取 【解答】A，B 【分析】参见2.2.1。 ⑵ 线性表采用链接存储时，其地址（）。 A 必须是连续的B 部分地址必须是连续的 C 一定是不连续的 D 连续与否均可以 【解答】D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。⑶ 单循环链表的主要优点是（）。A 不再需要头指针了 B 从表中任一结点出发都能扫描到整个链表； C 已知某个结点的位置后，能够容易找到它的直接前趋； D 在进行插入、删除操作时，能更好地保证链表不断开。【解答】B ⑷ 链表不具有的特点是（）。 A 可随机访问任一元素 B 插入、删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 【解答】A ⑸ 若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋，则采用（）存储方法最节省时间。A 顺序表 B 单链表 C 双链表 D 单循环链表 【解答】A 【分析】线性表中最常用的操作是取第i 个元素，所以，应选择随机存取结构即顺序表，同时在顺序表中查找第i个元素的前趋也很方便。单链表和单循环链表既不能实现随机存取，查找第i个元素的前趋也不方便，双链表虽然能快速查找第i个元素的前趋，但不能实现随机存取。 ⑹ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则采用（）存储方法最节省时间。 A 单链表 B 带头指针的单循环链表 C 双链表 D 带尾指针的单循环链表 【解答】D 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、带头指针的单循环链表、双链表都不合适，考虑在带尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以，答案是D。⑺ 若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方法最节省运算时间。 A 单链表 B 循环双链表 C单循环链表 D 带尾指针的单循环链表 【解答】B 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址，所以，单链表、单循环链表都不合适，删除最后一个结点需要知道终端结点的前驱结点的地址，所以，带尾指针的单循环链表不合适，而循环双链表满足条件。 ⑻ 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A O(1)B O(n)C O(n2)D O(nlog2n)【解答】B 【分析】首先应顺序查找新结点在单链表中的位置。 ⑼ 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（）。A O(1)B O(n)C O(n2)D O(nlog2n)【解答】C 【分析】该算法需要将n个元素依次插入到有序单链表中，而插入每个元素需O(n)。⑽ 使用双链表存储线性表，其优点是可以（）。A 提高查找速度 B 更方便数据的插入和删除 C 节约存储空间 D 很快回收存储空间 【解答】B 【分析】在链表中一般只能进行顺序查找，所以，双链表并不能提高查找速度，因为双链表中有两个指针域，显然不能节约存储空间，对于动态存储分配，回收存储空间的速度是一样的。由于双链表具有对称性，所以，其插入和删除操作更加方便。 ⑾ 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（）操作。 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;【解答】B 【分析】注意此题是在q和p之间插入新结点，所以，不用考虑修改指针的顺序。⑿ 在循环双链表的p所指结点后插入s所指结点的操作是（）。A p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;C s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;D s->prior=p;s->next=p->next;p->next->prior=s;p->next=s 【解答】D 【分析】在链表中，对指针的修改必须保持线性表的逻辑关系，否则，将违背线性表的逻辑特征，图2-10给出备选答案C和D的图解。 3.判断题 ⑴ 线性表的逻辑顺序和存储顺序总是一致的。 【解答】错。顺序表的逻辑顺序和存储顺序一致，链表的逻辑顺序和存储顺序不一定一致。⑵ 线性表的顺序存储结构优于链接存储结构。【解答】错。两种存储结构各有优缺点。⑶ 设p，q是指针，若p=q，则*p=*q。 【解答】错。p=q只能表示p和q指向同一起始地址，而所指类型则不一定相同。⑷ 线性结构的基本特征是：每个元素有且仅有一个直接前驱和一个直接后继。 【解答】错。每个元素最多只有一个直接前驱和一个直接后继，第一个元素没有前驱，最后一个元素没有后继。 ⑸ 在单链表中，要取得某个元素，只要知道该元素所在结点的地址即可，因此单链表是随机存取结构。【解答】错。要找到该结点的地址，必须从头指针开始查找，所以单链表是顺序存取结构。4．请说明顺序表和单链表各有何优缺点，并分析下列情况下，采用何种存储结构更好些。 ⑴ 若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。⑵ 如果n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。⑶ 描述一个城市的设计和规划。 【解答】顺序表的优点：① 无需为表示表中元素之间的逻辑关系而增加额外的存储空间；② 可以快速地存取表中任一位置的元素（即随机存取）。顺序表的缺点：① 插入和删除操作需移动大量元素；② 表的容量难以确定；③ 造成存储空间的―碎片‖。 单链表的优点：① 不必事先知道线性表的长度；② 插入和删除元素时只需修改指针，不用移动元素。单链表的缺点：① 指针的结构性开销；② 存取表中任意元素不方便，只能进行顺序存取。 ⑴ 应选用顺序存储结构。因为顺序表是随机存取结构，单链表是顺序存取结构。本题很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 ⑵ 应选用链接存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 ⑶ 应选用链接存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。5．算法设计 ⑴ 设计一个时间复杂度为Ｏ(n)的算法，实现将数组A[n]中所有元素循环右移k个位置。【解答】算法思想请参见主教材第一章思想火花。下面给出具体算法。 分析算法，第一次调用Reverse函数的时间复杂度为O(k)，第二次调用Reverse函数的时间复杂度为O(n-k)，第三次调用Reverse函数的时间复杂度为O(n)，所以，总的时间复杂度为O(n)。 ⑵ 已知数组A[n]中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为Ｏ(n)。 【解答】从数组的两端向中间比较，设置两个变量i和j，初始时i=0，j=n-1，若A[i]为偶数并且A[j]为奇数，则将A[i]与A[j]交换。具体算法如下： 分析算法，两层循环将数组扫描一遍，所以，时间复杂度为Ｏ(n)。 ⑶ 试编写在无头结点的单链表上实现线性表的插入操作的算法，并和带头结点的单链表上的插入操作的实现进行比较。【解答】参见2.2.3。 ⑷ 试分别以顺序表和单链表作存储结构，各写一实现线性表就地逆置的算法。 【解答】顺序表的逆置，即是将对称元素交换，设顺序表的长度为length，则将表中第i个元素与第length-i-1个元素相交换。具体算法如下： 单链表的逆置请参见2.2.4算法2-4和算法2-6。 ⑸ 假设在长度大于1的循环链表中，即无头结点也无头指针，s为指向链表中某个结点的指针，试编写算法删除结点s的前趋结点。 【解答】利用单循环链表的特点，通过指针s可找到其前驱结点r以及r的前驱结点p，然后将结点r删除，如图2-11所示，具体算法如下： ⑹ 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。试编写算法，构造三个循环链表，使每个循环链表中只含同一类字符。 【解答】在单链表A中依次取元素，若取出的元素是字母，把它插入到字母链表B 中，若取出的元素是数字，则把它插入到数字链表D中，直到链表的尾部，这样表B，D，A中分别存放字母、数字和其他字符。具体算法如下： ⑺ 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。 【解答】从头到尾扫描单链表，若当前结点的元素值与后继结点的元素值不相等，则指针后移；否则删除该后继结点。具体算法如下： ⑻ 判断带头结点的双循环链表是否对称。 【解答】设工作指针p和q分别指向循环双链表的开始结点和终端结点，若结点p和结点q的数据域相等，则工作指针p后移，工作指针q前移，直到指针p和指针q指向同一结点（循环双链表中结点个数为奇数），或结点q成为结点p的前驱（循环双链表中结点个数为偶数）。如图2-12所示。 学习自测及答案 1.已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。A 108 B 180 C 176 D 112 【解答】D 2．在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。 A O(0)B O(1)C O(n)D O(n2)【解答】C 3．在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。【解答】n-i+1，n-i 4．在单链表中，除了头结点以外，任一结点的存储位置由（）指示。【解答】其前趋结点的指针域 5．当线性表采用顺序存储结构时，其主要特点是（）。【解答】逻辑结构中相邻的结点在存储结构中仍相邻 6．在双链表中，每个结点设置了两个指针域，其中一个指向（）结点，另一个指向（）结点。【解答】前驱，后继 7．设A是一个线性表（a1, a2, …, an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（1≤i≤n）的概率为插入一个元素所要移动的元素个数又是多少？ 【解答】 ，则平均每。 8．线性表存放在整型数组A[arrsize]的前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。 【解答】本题是在一个递增有序表中插入元素x，基本思路是从有序表的尾部开始依次取元素与x比较，若大于x，此元素后移一位，再取它前面一个元素重复上述步骤；否则，找到插入位置，将x插入。具体算法如下： 9.已知单链表中各结点的元素值为整型且递增有序，设计算法删除链表中所有大于mink且小于maxk的所有元素，并释放被删结点的存储空间。 【解答】因为是在有序单链表上的操作，所以，要充分利用其有序性。在单链表中查找第一个大于mink的结点和第一个小于maxk的结点，再将二者间的所有结点删除。 10．设单循环链表L1，对其遍历的结果是：x1, x2, x3,…, xn-1, xn。请将该循环链表拆成两个单循环链表L1和L2，使得L1中含有原L1表中序号为奇数的结点且遍历结果为：x1, x3,… ；L2中含有原L1表中序号为偶数的结点且遍历结果为：… , x4, x2。【解答】算法如下： 第 3 章 特殊线性表——栈、队列和串 课后习题讲解 1.填空 ⑴ 设有一个空栈，栈顶指针为1000H，现有输入序列为1、2、3、4、5，经过push，push，pop，push，pop，push，push后，输出序列是（），栈顶指针为（）。【解答】23，1003H ⑵ 栈通常采用的两种存储结构是（）；其判定栈空的条件分别是（），判定栈满的条件分别是（）。【解答】顺序存储结构和链接存储结构（或顺序栈和链栈），栈顶指针top=-1和top=NULL，栈顶指针top等于数组的长度和内存无可用空间 ⑶（）可作为实现递归函数调用的一种数据结构。【解答】栈 【分析】递归函数的调用和返回正好符合后进先出性。⑷ 表达式a*(b+c)-d的后缀表达式是（）。【解答】abc+*d-【分析】将中缀表达式变为后缀表达式有一个技巧：将操作数依次写下来，再将算符插在它的两个操作数的后面。 ⑸ 栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。 【解答】后进先出，先进先出，对插入和删除操作限定的位置不同 ⑹ 循环队列的引入是为了克服（）。【解答】假溢出 ⑺ 数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为（）。【解答】（rear-front+n）% n 【分析】也可以是（rear-front）% n，但rear-front的结果可能是负整数，而对一个负整数求模，其结果在不同的编译器环境下可能会有所不同。 ⑻ 用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别是（）和（）。【解答】Ｏ(1)，Ｏ(n)【分析】在带头指针的循环链表中，出队即是删除开始结点，这只需修改相应指针；入队即是在终端结点的后面插入一个结点，这需要从头指针开始查找终端结点的地址。⑼ 串是一种特殊的线性表，其特殊性体现在（）。【解答】数据元素的类型是一个字符 ⑽ 两个串相等的充分必要条件是（）。【解答】长度相同且对应位置的字符相等 【分析】例如“abc”≠“abc ”，“abc”≠“bca”。2.选择题 ⑴ 若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素是（）。A 不确定 B n-i C n-i-1 D n-i+1 【解答】D 【分析】此时，输出序列一定是输入序列的逆序。 ⑵ 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（）。A 6 B C D 2 【解答】C 【分析】由于队列具有先进先出性，所以，此题中队列形同虚设，即出栈的顺序也是e2、e4、e3、e6、e5、e1。 ⑶ 一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）。A 54321 B 45321 C 43512 D 12345 【解答】C 【分析】此题有一个技巧：在输出序列中任意元素后面不能出现比该元素小并且是升序（指的是元素的序号）的两个元素。 ⑷ 设计一个判别表达式中左右括号是否配对的算法，采用（）数据结构最佳 A 顺序表 B 栈 C 队列 D 链表 【解答】B 【分析】每个右括号与它前面的最后一个没有匹配的左括号配对，因此具有后进先出性。 ⑸ 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个（）结构。 A 栈 B队列 C 数组 D线性表 【解答】B 【分析】先进入打印缓冲区的文件先被打印，因此具有先进先出性。⑹ 一个队列的入队顺序是1，2，3，4，则队列的输出顺序是（）。A 4321 B 1234 C 1432 D 3241 【解答】B 【分析】队列的入队顺序和出队顺序总是一致的。⑺ 栈和队列的主要区别在于（）。 A 它们的逻辑结构不一样 B 它们的存储结构不一样 C 所包含的运算不一样 D 插入、删除运算的限定不一样 【解答】D 【分析】栈和队列的逻辑结构都是线性的，都有顺序存储和链接存储，有可能包含的运算不一样，但不是主要区别，任何数据结构在针对具体问题时包含的运算都可能不同。 ⑻ 设数组S[n]作为两个栈S1和S2的存储空间，对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。A S1的栈底位置为0，S2的栈底位置为n-1 B S1的栈底位置为0，S2的栈底位置为n/2 C S1的栈底位置为0，S2的栈底位置为n D S1的栈底位置为0，S2的栈底位置为1 【解答】A 【分析】两栈共享空间首先两个栈是相向增长的，栈底应该分别指向两个栈中的第一个元素的位置，并注意C++中的数组下标是从0开始的。 ⑼ 设有两个串p和q，求q在p中首次出现的位置的运算称作（）。A 连接 B 模式匹配 C 求子串 D 求串长 【解答】B 3.判断题 ⑴ 有n个元素依次进栈，则出栈序列有(n-1)/2种。 【解答】错。应该有 种。 ⑵ 栈可以作为实现过程调用的一种数据结构。 【解答】对。只要操作满足后进先出性，都可以采用栈作为辅助数据结构。⑶ 在栈满的情况下不能做进栈操作，否则将产生―上溢‖。【解答】对。 ⑷ 在循环队列中，front指向队头元素的前一个位置，rear指向队尾元素的位置，则队满的条件是front=rear。 【解答】错。这是队空的判定条件，在循环队列中要将队空和队满的判定条件区别开。⑸ 空串与空格串是相同的。 【解答】错。空串的长度为零，而空格串的长度不为0，其长度是串中空格的个数。 4.设有一个栈，元素进栈的次序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。⑴ C，E，A，B，D ⑵ C，B，A，D，E 【解答】⑴不能，因为在C、E出栈的情况下，A一定在栈中，而且在B的下面，不可能先于B出栈。⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。5.举例说明顺序队列的―假溢出‖现象。 【解答】假设有一个顺序队列，如图3-6所示，队尾指针rear=4，队头指针front=1，如果再有元素入队，就会产生―上溢‖，此时的―上溢‖又称为―假溢出‖，因为队列并不是真的溢出了，存储队列的数组中还有2个存储单元空闲，其下标分别为0和1。 6.在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）【解答】栈顶元素为6，栈底元素为1。其执行过程如图3-7所示。 7． 在操作序列EnQueue(1)、EnQueue(3)、DeQueue、EnQueue(5)、EnQueue(7)、DeQueue、EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数k入队，DeQueue表示队头元素出队）。【解答】队头元素为5，队尾元素为9。其执行过程如图3-8所示。 8．空串和空格串有何区别？串中的空格符有何意义？空串在串处理中有何作用？ 【解答】不含任何字符的串称为空串，其长度为零。仅含空格的串称为空格串，它的长度为串中空格符的个数。串中的空格符可用来分隔一般的字符，便于人们识别和阅读，但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。9.算法设计 ⑴ 假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队的算法。 【解答】出队操作是在循环链表的头部进行，相当于删除开始结点，而入队操作是在循环链表的尾部进行，相当于在终端结点之后插入一个结点。由于循环链表不带头结点，需要处理空表的特殊情况。入队算法如下： 出队算法如下： ⑵ 设顺序栈S中有2n个元素，从栈顶到栈底的元素依次为a2n，a2n-1，…，a1，要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a2n，a2n-2，…，a2，a2n-1，a2n-3，…，a1，请设计算法实现该操作，要求空间复杂度和时间复杂度均为O(n)。【解答】操作步骤为： ① 将所有元素出栈并入队； ② 依次将队列元素出队，如果是偶数结点，则再入队，如果是奇数结点，则入栈； ③ 将奇数结点出栈并入队； ④ 将偶数结点出队并入栈； ⑤ 将所有元素出栈并入队； ⑥ 将所有元素出队并入栈即为所求。 ⑶ 用顺序存储结构存储串S，编写算法删除S中第 i个字符开始的连续j个字符。 【解答】先判断串S中要删除的内容是否存在，若存在，则将第i+j-1之后的字符前移j个位置。算法如下： ⑷ 对于采用顺序存储结构的串S，编写一个函数删除其值等于ch的所有字符。 【解答】从后向前删除值为ch的所有元素，这样所有移动的元素中没有值为ch的元素，能减少移动元素的次数，提高算法的效率。算法如下： ⑸ 对串的模式匹配KMP算法设计求模式滑动位置的next函数。【解答】参见3.2.5 学习自测及答案 1．在一个具有n个单元的顺序栈中，假定以地址低端（即下标为0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。A 不变 B top=0;C top=top-1;D top=top+1;【解答】C 2．一个栈的入栈序列是a, b, c, d, e，则栈的不可能的出栈序列是（）。A edcba B cdeba C debca D abcde 【解答】C 3．从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（）。A x=top;top=top->next;B x=top->data;C top=top->next;x=top->data;D x=top->data;top=top->next;【解答】D 4．设元素1, 2, 3, P, A依次经过一个栈，进栈次序为123PA，在栈的输出序列中，有哪些序列可作为C++程序设计语言的变量名。 【解答】PA321, P3A21, P32A1, P321A, AP321 5.设S=“I_ am_ a_ teacther”，其长度为（）。【解答】15 第 4 章 广义线性表——多维数组和广义表 课后习题讲解 1.填空 ⑴ 数组通常只有两种运算：（）和（），这决定了数组通常采用（）结构来实现存储。【解答】存取，修改，顺序存储 【分析】数组是一个具有固定格式和数量的数据集合，在数组上一般不能做插入、删除元素的操作。除了初始化和销毁之外，在数组中通常只有存取和修改两种操作。 ⑵ 二维数组A中行下标从10到20，列下标从5到10，按行优先存储，每个元素占4个存储单元，A[10][5]的存储地址是1000，则元素A[15][10]的存储地址是（）。【解答】1140 【分析】数组A中每行共有6个元素，元素A[15][10]的前面共存储了(15-10)×6+5个元素，每个元素占4个存储单元，所以，其存储地址是1000+140=1140。 ⑶ 设有一个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址为d，每个元素占1个存储单元，则元素A[8][5]的存储地址为（）。【解答】d+41 【分析】元素A[8][5]的前面共存储了(1+2+…+8)+5=41个元素。⑷ 稀疏矩阵一般压缩存储方法有两种，分别是（）和（）。【解答】三元组顺序表，十字链表 ⑸ 广义表((a),(((b),c)),(d))的长度是（），深度是（），表头是（），表尾是（）。【解答】3，4，(a)，((((b),c)),(d))⑹ 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是（）。【解答】Head(Head(Tail(LS)))2.选择题 ⑴ 二维数组A的每个元素是由6个字符组成的串，行下标的范围从0~8，列下标的范围是从0~9，则存放A至少需要（）个字节，A的第8列和第5行共占（）个字节，若A按行优先方式存储，元素A[8][5]的起始地址与当A按列优先方式存储时的（）元素的起始地址一致。A 90 B 180 C 240 D 540 E 108 F 114 G 54 H A[8][5] I A[3][10] J A[5][8] K A[4][9] 【解答】D，E，K 【分析】数组A为9行10列，共有90个元素，所以，存放A至少需要90×6=540个存储单元，第8列和第5行共有18个元素（注意行列有一个交叉元素），所以，共占108个字节，元素A[8][5]按行优先存储的起始地址为d+8×10+5=d+85，设元素A[i][j]按列优先存储的起始地址与之相同，则d+j×9+i=d+85，解此方程，得i=4，j=9。 ⑵ 将数组称为随机存取结构是因为（） A 数组元素是随机的 B 对数组任一元素的存取时间是相等的 C 随时可以对数组进行访问 D 数组的存储结构是不定 【解答】B ⑶ 下面的说法中，不正确的是（） A 数组是一种线性结构 B 数组是一种定长的线性结构 C 除了插入与删除操作外，数组的基本操作还有存取、修改、检索和排序等 D 数组的基本操作有存取、修改、检索和排序等，没有插入与删除操 【解答】C 【分析】数组属于广义线性表，数组被创建以后，其维数和每维中的元素个数是确定的，所以，数组通常没有插入和删除操作。 ⑷ 对特殊矩阵采用压缩存储的目的主要是为了（）A 表达变得简单 B 对矩阵元素的存取变得简单 C 去掉矩阵中的多余元素 D 减少不必要的存储空间 【解答】D 【分析】在特殊矩阵中，有很多值相同的元素并且他们的分布有规律，没有必要为值相同的元素重复存储。⑸ 下面（）不属于特殊矩阵。 A 对角矩阵 B 三角矩阵 C 稀疏矩阵 D 对称矩阵 【解答】C ⑹ 若广义表A满足Head(A)=Tail(A)，则A为（）A()B(())C((),())D((),(),())【解答】B ⑺ 下面的说法中，不正确的是（） A 广义表是一种多层次的结构 B 广义表是一种非线性结构 C 广义表是一种共享结构 D 广义表是一种递归 【解答】B 【分析】从各层元素各自具有的线性关系讲，广义表属于线性结构。⑻ 下面的说法中，不正确的是（） A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B 对角矩阵只须存放非零元素即可。 C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。 D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储 【解答】D 【分析】稀疏矩阵中大量值为零的元素分布没有规律，因此采用三元组表存储。如果零元素的分布有规律，就没有必要存储非零元素的行号和列号，而需要按其压缩规律找出相应的映象函数。3.判断题 ⑴ 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的，也不是树形的。【解答】错。例如二维数组可以看成是数据元素为线性表的线性表。⑵ 使用三元组表存储稀疏矩阵的元素，有时并不能节省存储空间。 【解答】对。因为三元组表除了存储非零元素值外，还需要存储其行号和列号。⑶ 稀疏矩阵压缩存储后，必会失去随机存取功能。 【解答】对。因为压缩存储后，非零元素的存储位置和行号、列号之间失去了确定的关系。 ⑷ 线性表可以看成是广义表的特例，如果广义表中的每个元素都是单元素，则广义表便成为线性表。【解答】对。 ⑸ 若一个广义表的表头为空表，则此广义表亦为空表。 【解答】错。如广义表L=(()，(a，b))的表头为空表，但L不是空表。 4．一个稀疏矩阵如图4-4所示，写出对应的三元组顺序表和十字链表存储表示。 【解答】对应的三元组顺序表如图4-5所示，十字链表如图4-6所示。 5．已知A为稀疏矩阵，试从空间和时间角度比较采用二维数组和三元组顺序表两种不同的存储结构完成求 运算的优缺点。 【解答】设稀疏矩阵为m行n列，如果采用二维数组存储，其空间复杂度为Ｏ(m×n)；因为要将所有的矩阵元素累加起来，所以，需要用一个两层的嵌套循环，其时间复杂度亦为Ｏ(m×n)。如果采用三元组顺序表进行压缩存储，假设矩阵中有t个非零元素，其空间复杂度为Ｏ(t)，将所有的矩阵元素累加起来只需将三元组顺序表扫描一遍，其时间复杂度亦为Ｏ(t)。当t << m×n时，采用三元组顺序表存储可获得较好的时、空性能。 6．设某单位职工工资表ST由―工资‖、―扣除‖和―实发金额‖三项组成，其中工资项包括―基本工资‖、―津贴‖和―奖金‖，扣除项包括―水‖、―电‖和―煤气‖。 ⑴ 请用广义表形式表示所描述的工资表ST，并用表头和表尾求表中的―奖金‖项； ⑵ 画出该工资表ST的存储结构。 【解答】⑴ ST=((基本工资，津贴，奖金)，(水，电，煤气)，实发金额)Head(Tail(Tail(Head(ST))))=奖金 ⑵ 工资表ST的头尾表示法如图4-7所示。 7．若在矩阵A中存在一个元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A，试设计一个求该矩阵所有马鞍点的算法，并分析最坏情况下的时间复杂度。 【解答】在矩阵中逐行寻找该行中的最小值，然后对其所在的列寻找最大值，如果该列上的最大值与该行上的最小值相等，则说明该元素是鞍点，将它所在行号和列号输出。 具体算法如下： 分析算法，外层for循环共执行n次，内层第一个for循环执行m次，第二个for循环最坏情况下执行n次，所以，最坏情况下的时间复杂度为Ｏ(mn+n2)。 学习自测及答案 1．二维数组M中每个元素的长度是3个字节，行下标从0到7，列下标从0到9，从首地址d开始存储。若按行优先方式存储，元素M[7][5]的起始地址为（），若按列优先方式存储，元素M[7][5]的起始地址为（）。【解答】d+22，d+141 2．一个n×n的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（）。【解答】n(n+1)/2 3．设n行n列的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]~S[n(n+1)/2]中，若按行优先存储，则A[i][j]在数组S中的存储位置是（）。【解答】i×(i-1)/2+j 4．已知广义表LS=(a,(b, c),(d, e, a))，运用Head函数和Tail函数取出LS中原子d的运算是（）。【解答】Head(Head(Tail(Tail(LS))))5．广义表(a, b,(c,(d)))的表尾是（）。A(d)B(c,(d))C b,(c,(d))D(b,(c,(d)))【解答】D 6．设有三对角矩阵An×n（行、列下标均从0开始），将其三条对角线上的元素逐行存于数组B[3n-2]中，使得B[k]=aij求： ⑴ 用i, j表示k的下标变换公式； ⑵ 用k表示i, j的下标变换公式。 【解答】⑴ 要求i, j表示k的下标变换公式，就是要求在k之前已经存储了多少个非零元素，这些非零元素的个数就是k的值。元素aij求所在的行为i，列为j，则在其前面的非零元素的个数是；k=2 + 3(i－1)+(j－i + 1)= 2i+ j。 ⑵ 因为k和i, j之间是一一对应的关系，k+1是当前非零元素的个数，整除即为其所在行号，取余表示当前行中第几个非零元素，加上前面零元素所在列数就是当前列号，即： 7．已知两个n×n的对称矩阵按压缩存储方法存储在已维数组A和B中，编写算法计算对称矩阵的乘积。【解答】对称矩阵采用压缩存储，乘积矩阵也采用压缩存储。注意矩阵元素的表示方法。 第 5 章 树和二叉树 课后习题讲解 1.填空题 ⑴ 树是n（n≥0）结点的有限集合，在一棵非空树中，有（）个根结点，其余的结点分成m（m＞0）个（）的集合，每个集合都是根结点的子树。【解答】有且仅有一个，互不相交 ⑵ 树中某结点的子树的个数称为该结点的（），子树的根结点称为该结点的（），该结点称为其子树根结点的（）。 【解答】度，孩子，双亲 ⑶ 一棵二叉树的第i（i≥1）层最多有（）个结点；一棵有n（n>0）个结点的满二叉树共有（）个叶子结点和（）个非终端结点。【解答】2i-1，(n+1)/2，(n-1)/2 【分析】设满二叉树中叶子结点的个数为n0，度为2的结点个数为n2，由于满二叉树中不存在度为1的结点，所以n=n0+n2；由二叉树的性质n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。 ⑷ 设高度为h的二叉树上只有度为0和度为2的结点，该二叉树的结点数可能达到的最大值是（），最小值是（）。【解答】2h-1，2h-1 【分析】最小结点个数的情况是第1层有1个结点，其他层上都只有2个结点。 ⑸ 深度为k的二叉树中，所含叶子的个数最多为（）。【解答】2k-1 【分析】在满二叉树中叶子结点的个数达到最多。 ⑹ 具有100个结点的完全二叉树的叶子结点数为（）。【解答】50 【分析】100个结点的完全二叉树中最后一个结点的编号为100，其双亲即最后一个分支结点的编号为50，也就是说，从编号51开始均为叶子。 ⑺ 已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点。则该树中有（）个叶子结点。【解答】12 【分析】根据二叉树性质3的证明过程，有n0=n2+2n3+1（n0、n2、n3分别为叶子结点、度为2的结点和度为3的结点的个数）。 ⑻ 某二叉树的前序遍历序列是ABCDEFG，中序遍历序列是CBDAFGE，则其后序遍历序列是（）。【解答】CDBGFEA 【分析】根据前序遍历序列和后序遍历序列将该二叉树构造出来。 ⑼ 在具有n个结点的二叉链表中，共有（）个指针域，其中（）个指针域用于指向其左右孩子，剩下的（）个指针域则是空的。【解答】2n，n-1，n+1 ⑽ 在有n个叶子的哈夫曼树中，叶子结点总数为（），分支结点总数为（）。【解答】n，n-1 【分析】n-1个分支结点是经过n-1次合并后得到的。 2.选择题 ⑴ 如果结点A有3个兄弟，B是A的双亲，则结点B的度是（）。A 1 B 2 C 3 D 4 【解答】D ⑵ 设二叉树有n个结点，则其深度为（）。A n-1 B n C +1 D 不能确定 【解答】D 【分析】此题并没有指明是完全二叉树，则其深度最多是n，最少是 +1。 ⑶ 二叉树的前序序列和后序序列正好相反，则该二叉树一定是（）的二叉树。A 空或只有一个结点 B 高度等于其结点数 C 任一结点无左孩子 D 任一结点无右孩子 【解答】B 【分析】此题注意是序列正好相反，则左斜树和右斜树均满足条件。 ⑷ 线索二叉树中某结点R没有左孩子的充要条件是（）。A R.lchild=NULL B R.ltag=0 C R.ltag=1 D R.rchild=NULL 【解答】C 【分析】线索二叉树中某结点是否有左孩子，不能通过左指针域是否为空来判断，而要判断左标志是否为1。 ⑸ 深度为k的完全二叉树至少有（）个结点，至多有（）个结点，具有n个结点的完全二叉树按层序从1开始编号，则编号最小的叶子的序号是（）。A 2k-2+1 B 2k-1 C 2k-1 D 2k–1-1 E 2k+1 F 2k+1-1 G 2k-1+1 H 2k 【解答】B，C，A 【分析】深度为k的完全二叉树最少结点数的情况应是第k层上只有1个结点，最多的情况是满二叉树，编号最小的叶子应该是在结点数最少的情况下，叶子结点的编号。 ⑹ 一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-1 【解答】D 【分析】满二叉树中没有度为1的结点，所以有m个叶子结点，则度为2的结点个数为m-1。 ⑺ 任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（）。A 肯定不发生改变 B 肯定发生改变 C 不能确定 D 有时发生变化 【解答】A 【分析】三种遍历次序均是先左子树后右子树。 ⑻ 如果T' 是由有序树T转换而来的二叉树，那么T中结点的前序序列就是T' 中结点的（）序列，T中结点的后序序列就是 T' 中结点的（）序列。A 前序 B 中序 C 后序 D 层序 【解答】A，B ⑼ 设森林中有4棵树，树中结点的个数依次为n1、n2、n3、n4，则把森林转换成二叉树后，其根结点的右子树上有（）个结点，根结点的左子树上有（）个结点。A n1-1 B n1 C n1+n2+n3 D n2+n3+n4 【解答】D，A 【分析】由森林转换的二叉树中，根结点即为第一棵树的根结点，根结点的左子树是由第一棵树中除了根结点以外其余结点组成的，根结点的右子树是由森林中除第一棵树外其他树转换来的。 ⑽ 讨论树、森林和二叉树的关系，目的是为了（）。A 借助二叉树上的运算方法去实现对树的一些运算 B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树 D 体现一种技巧，没有什么实际意义 【解答】B 3.判断题 ⑴ 在线索二叉树中，任一结点均有指向其前趋和后继的线索。 【解答】错。某结点是否有前驱或后继的线索，取决于该结点的标志域是否为1。 ⑵ 在二叉树的前序遍历序列中，任意一个结点均处在其子女的前面。【解答】对。由前序遍历的操作定义可知。 ⑶ 二叉树是度为2的树。 【解答】错。二叉树和树是两种不同的树结构，例如，左斜树是一棵二叉树，但它的度为1。 ⑷ 由树转换成二叉树，其根结点的右子树总是空的。【解答】对。因为根结点无兄弟结点。 ⑸ 用一维数组存储二叉树时，总是以前序遍历存储结点。 【解答】错。二叉树的顺序存储结构是按层序存储的，一般适合存储完全二叉树。 4．证明：对任一满二叉树，其分枝数B＝2(n0-1)。（其中，n0为终端结点数）【解答】因为在满二叉树中没有度为1的结点，所以有： n=n0+n2 设B为树中分枝数，则 n=B+1 所以 B=n0 +n2-1 再由二叉树性质： n0=n2+1 代入上式有： B=n0+n0-1-1=2(n0-1) 5．证明：已知一棵二叉树的前序序列和中序序列，则可唯一确定该二叉树。【解答】证明采用归纳法。 设二叉树的前序遍历序列为a1a2a3… an，中序遍历序列为b1b2b3… bn。 当n=1时，前序遍历序列为a1，中序遍历序列为b1，二叉树只有一个根结点，所以，a1= b1，可以唯一确定该二叉树； 假设当n<=k时，前序遍历序列a1a2a3… ak和中序遍历序列b1b2b3… bk可唯一确定该二叉树，下面证明当n=k+1时，前序遍历序列a1a2a3… akak+1和中序遍历序列b1b2b3… bk bk+1可唯一确定一棵二叉树。 在前序遍历序列中第一个访问的一定是根结点，即二叉树的根结点是a1，在中序遍历序列中查找值为a1的结点，假设为bi，则a1=bi且b1b2… bi-1是对根结点a1的左子树进行中序遍历的结果，前序遍历序列a2a3… ai是对根结点a1的左子树进行前序遍历的结果，由归纳假设，前序遍历序列a2a3… ai和中序遍历序列b1b2… bi-1唯一确定了根结点的左子树，同样可证前序遍历序列ai+1ai+2… ak+1和中序遍历序列bi+1bi+2… bk+1唯一确定了根结点的右子树。 6．已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，……，nm个度为m的结点，问该树中共有多少个叶子结点？ 【解答】设该树的总结点数为n，则 n=n0+n1+n2+……+nm 又： n=分枝数+1=0×n0+1×n1+2×n2+……+m×nm+1 由上述两式可得： n0= n2+2n3+……+(m-1)nm+1 7．已知二叉树的中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，试构造该二叉树。【解答】二叉树的构造过程如图5-12 所示。 8．对给定的一组权值W＝（5，2，9，11，8，3，7），试构造相应的哈夫曼树，并计算它的带权路径长度。 【解答】构造的哈夫曼树如图5-13所示。 树的带权路径长度为： WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2 =120 9．已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3次、4次和9次，对该字符串用[0，1]进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图5-14所示。其带权路径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，该字符串的编码长度至少为98位。 10．算法设计 ⑴ 设计算法求二叉树的结点个数。 【解答】本算法不是要打印每个结点的值，而是求出结点的个数。所以可将遍历算法中的―访问‖操作改为―计数操作‖，将结点的数目累加到一个全局变量中，每个结点累加一次即完成了结点个数的求解。具体算法如下： ⑵ 设计算法按前序次序打印二叉树中的叶子结点。 【解答】本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历算法中的访问操作改为条件打印即可。算法如下： ⑶ 设计算法求二叉树的深度。 【解答】当二叉树为空时，深度为0；若二叉树不为空，深度应是其左右子树深度的最大值加1，而其左右子树深度的求解又可通过递归调用本算法来完成。具体算法如下： ⑷ 编写算法，要求输出二叉树后序遍历序列的逆序。 【解答】要想得到后序的逆序，只要按照后序遍历相反的顺序即可，即先访问根结点，再遍历根结点的右子树，最后遍历根结点的左子树。注意和前序遍历的区别，具体算法如下： ⑸ 以二叉链表为存储结构，编写算法求二叉树中结点x的双亲。 【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲。具体算法如下： ⑹ 以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树。 【解答】对二叉链表进行遍历，在遍历的过程中查找结点x并记载其双亲，然后将结点x的双亲结点中指向结点x的指针置空。具体算法如下： ⑺ 一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。【解答】按照题目要求，设置一个工作栈以完成对该树的非递归算法，思路如下： ① 每访问一个结点，将此结点压栈，查看此结点是否有左子树，若有，访问左子树，重复执行该过程直到左子树为空。 ② 从栈弹出一个结点，如果此结点有右子树，访问右子树执行步骤①，否则重复执行步骤②。具体算法如下： ⑻ 编写算法交换二叉树中所有结点的左右子树。 【解答】对二叉树进行后序遍历，在遍历过程中访问某结点时交换该结点的左右子树。具体算法如下： ⑼ 以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。 【解答】先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。 树的孩子兄弟表示法中的结点结构定义如下： template struct TNode { T data;TNode *firstchild, *rightsib;};具体算法如下： 学习自测及答案 1．前序遍历和中序遍历结果相同的二叉树是（）。A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树 【解答】D 1．前序遍历和中序遍历结果相同的二叉树是（）。A 根结点无左孩子的二叉树 B 根结点无右孩子的二叉树 C 所有结点只有左子树的二叉树 D 所有结点只有右子树的二叉树【解答】D 2．由权值为{3, 8, 6, 2, 5}的叶子结点生成一棵哈夫曼树，其带权路径长度为（）。A 24 B 48 C 53 D 72 【解答】C 3．用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树的根结点是（）。 A A[2i-1] B A[2i+1] C A[i/2] D A[2i] 【解答】D 4．对任何一棵二叉树T，如果其终端结点的个数为n0，度为2的结点个数为n2，则（）。A n0=n2-1 B n0=n2 C n0=n2+1 D 没有规律 【解答】C 5．一棵满二叉树中共有n个结点，其中有m个叶子结点，深度为h，则（）。A n=h+m B h+m=2n C m=h-1 D n=2h-1 【解答】D 6．对于完全二叉树中的任一结点，若其右分支下的子孙的最大层次为h，则其左分支下的子孙的最大层次为（）。 A h B h+1 C h或h+1 D 任意 【解答】C 7．假定一棵度为3的树中结点数为50，则其最小高度应为。A 3 B 4 C 5 D 6 【解答】C 8．在线索二叉树中，一个结点是叶子结点的充要条件为（）。A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0 C 左、右线索标志均为0 D 左、右线索标志均为1 【解答】C 9．对于一棵具有n个结点的树，其所有结点的度之和为（）。【解答】n-1 10．在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是（）。【解答】 11．现有按前序遍历二叉树的结果ABC，问有哪几种不同的二叉树可以得到这一结果？ 【解答】共有5种二叉树可以得到这一结果，如图5-15所示。 12．试找出分别满足下列条件的所有二叉树： ⑴ 前序序列和中序序列相同。⑵ 中序序列和后序序列相同。⑶ 前序序列和后序序列相同。 【解答】 ⑴ 空二叉树、只有一个根结点的二叉树和右斜树。⑵ 空二叉树、只有一个根结点的二叉树和左斜树。⑶ 空二叉树、只有一个根结点的二叉树 13．将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。 【解答】图5-16所示树转换的二叉树如图5-18所示，图5-17所示二叉树转换的森林如图5-19所示。 14．以孩子兄弟表示法作为存储结构，编写算法求树的深度。 【解答】采用递归算法实现。若树为空树，则其深度为0，否则其深度等于第一棵子树的深度+1和兄弟子树的深度中的较大者。具体算法如下： 15．设计算法，判断一棵二叉树是否为完全二叉树。 【解答】根据完全二叉树的定义可知，对完全二叉树按照从上到下、从左到右的次序（即层序）遍历应该满足： ⑴ 若某结点没有左孩子，则其一定没有右孩子； ⑵ 若某结点无右孩子，则其所有后继结点一定无孩子。 若有一结点不满足其中任意一条，则该二叉树就一定不是完全二叉树。因此可采用按层次遍历二叉树的方法依次对每个结点进行判断是否满足上述两个条件。为此，需设两个标志变量BJ和CM，其中BJ表示已扫描过的结点是否均有左右孩子，CM存放局部判断结果及最后的结果。具体算法如下： 第 6 章 图 课后习题讲解 1.填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。【解答】0，n(n-1)/2，0，n(n-1)【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。【解答】Ｏ(n+e)【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal算法求最小生成树的时间复杂度为（）。【解答】Ｏ(n2)，Ｏ(elog2e)【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。2.选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 ⑵ n个顶点的强连通图至少有（）条边，其形状是（）。A n B n+1 C n-1 D n×(n-1)E 无回路 F 有回路 G 环状 H 树状 【解答】A，G ⑶ 含n 个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。A 1 B n/2 C n-1 D n 【解答】C 【分析】若超过n-1，则路径中必存在重复的顶点。 ⑷ 对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。A n B(n-1)2 C n-1 D n2 【解答】D ⑸ 图的生成树（），n个顶点的生成树有（）条边。A 唯一 B 不唯一 C 唯一性不能确定 D n E n +1 F n-1 【解答】C，F ⑹ 设无向图G=(V, E)和G' =(V', E')，如果G' 是G的生成树，则下面的说法中错误的是（）。A G' 为 G的子图 B G' 为 G的连通分量 C G' 为G的极小连通子图且V = V' D G' 是G的一个无环子图 【解答】B 【分析】连通分量是无向图的极大连通子图，其中极大的含义是将依附于连通分量中顶点的所有边都加上，所以，连通分量中可能存在回路。 ⑺ G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A 6 B 7 C 8 D 9 【解答】D 【分析】n个顶点的无向图中，边数e≤n(n-1)/2，将e=28代入，有n≥8，现已知无向图非连通，则n=9。⑻ 最小生成树指的是（）。A 由连通网所得到的边数最少的生成树 B 由连通网所得到的顶点数相对较少的生成树 C 连通网中所有生成树中权值之和为最小的生成树 D 连通网的极小连通子图 ⑼ 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A 求关键路径的方法 B 求最短路径的方法 C 广度优先遍历算法 D 深度优先遍历算法 【解答】D 【分析】当有向图中无回路时，从某顶点出发进行深度优先遍历时，出栈的顺序（退出DFSTraverse算法）即为逆向的拓扑序列。 ⑽ 下面关于工程计划的AOE网的叙述中，不正确的是（）?br /> A 关键活动不按期完成就会影响整个工程的完成时间 B 任何一个关键活动提前完成，那么整个工程将会提前完成 C 所有的关键活动都提前完成，那么整个工程将会提前完成 D 某些关键活动若提前完成，那么整个工程将会提前完 【解答】B 【分析】AOE网中的关键路径可能不止一条，如果某一个关键活动提前完成，还不能提前整个工程，而必须同时提高在几条关键路径上的关键活动。3.判断题 ⑴ 一个有向图的邻接表和逆邻接表中的结点个数一定相等。 【解答】对。邻接表和逆邻接表的区别仅在于出边和入边，边表中的结点个数都等于有向图中边的个数。⑵ 用邻接矩阵存储图，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。【解答】对。邻接矩阵的空间复杂度为Ｏ(n2)，与边的个数无关。⑶ 图G的生成树是该图的一个极小连通子图 【解答】错。必须包含全部顶点。 ⑷ 无向图的邻接矩阵一定是对称的，有向图的邻接矩阵一定是不对称的 【解答】错。有向图的邻接矩阵不一定对称，例如有向完全图的邻接矩阵就是对称的。⑸ 对任意一个图，从某顶点出发进行一次深度优先或广度优先遍历，可访问图的所有顶点。【解答】错。只有连通图从某顶点出发进行一次遍历，可访问图的所有顶点。⑹ 在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧。【解答】错。只能说明从顶点a到顶点b有一条路径。 ⑺ 若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑序列必定存在。【解答】对。参见第11题的证明。 ⑻ 在AOE网中一定只有一条关键路径?br />【解答】错。AOE网中可能有不止一条关键路径，他们的路径长度相同。 4．n个顶点的无向图，采用邻接表存储，回答下列问题?br />⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少?br />【解答】 ⑴ 边表中的结点个数之和除以2。⑵ 第i个边表中是否含有结点j。⑶ 该顶点所对应的边表中所含结点个数。 5．n个顶点的无向图，采用邻接矩阵存储，回答下列问题： ⑴ 图中有多少条边？ ⑵ 任意两个顶点i和j是否有边相连？ ⑶ 任意一个顶点的度是多少？ 【解答】 ⑴ 邻接矩阵中非零元素个数的总和除以2。 ⑵ 当邻接矩阵A中A[i][j]=1（或A[j][i]=1）时，表示两顶点之间有边相连。⑶ 计算邻接矩阵上该顶点对应的行上非零元素的个数。6．证明：生成树中最长路径的起点和终点的度均为１。【解答】用反证法证明。 设v1, v2, …, vk是生成树的一条最长路径，其中，v1为起点，vk为终点。若vk的度为2，取vk的另一个邻接点v，由于生成树中无回路，所以，v在最长路径上，显然v1, v2, …, vk , v的路径最长，与假设矛盾。所以生成树中最长路径的终点的度为1。同理可证起点v1的度不能大于1，只能为1。 7．已知一个连通图如图6-6所示，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的顶点序列。 【解答】邻接矩阵表示如下： 深度优先遍历序列为：v1 v2 v3 v5 v4 v6 广度优先遍历序列为：v1 v2 v4 v6 v3 v5 邻接表表示如下： 8．图6-7所示是一个无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。 【解答】按Prim算法求最小生成树的过程如下： 按Kruskal算法求最小生成树的过程如下： 9．对于图6-8所示的带权有向图，求从源点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。源点 终点 最短路径 最短路径长度 v1 v7 v1 v7 7 v1 v5 v1 v5 11 v1 v4 v1 v7 v4 13 v1 v6 v1 v7 v4 v6 16 v1 v2 v1 v7 v2 22 v1 v3 v1 v7 v4 v6 v3 25 10．如图6-9所示的有向网图，利用Dijkstra算法求从顶点v1到其他各顶点的最短路径。 【解答】从源点v1到其他各顶点的最短路径如下表所示。源点 终点 最短路径 最短路径长度 v1 v3 v1 v3 15 v1 v5 v1 v5 15 v1 v2 v1 v3 v2 25 v1 v6 v1 v3 v2 v6 40 v1 v4 v1 v3 v2 v4 45 11．证明：只要适当地排列顶点的次序，就能使有向无环图的邻接矩阵中主对角线以下的元素全部为0。【解答】任意n个结点的有向无环图都可以得到一个拓扑序列。设拓扑序列为v0v1v2…vn-1，我们来证明此时的邻接矩阵A为上三角矩阵。证明采用反证法。 假设此时的邻接矩阵不是上三角矩阵，那么，存在下标i和j（i>j），使得A[i][j]不等于零，即图中存在从vi到vj的一条有向边。由拓扑序列的定义可知，在任意拓扑序列中，vi的位置一定在vj之前，而在上述拓扑序列v0v1v2…vn-1中，由于i>j，即vi的位置在vj之后，导致矛盾。因此命题正确。12.算法设计 ⑴ 设计算法，将一个无向图的邻接矩阵转换为邻接表。 【解答】先设置一个空的邻接表，然后在邻接矩阵上查找值不为零的元素，找到后在邻接表的对应单链表中插入相应的边表结点。邻接矩阵存储结构定义如下： const int MaxSize=10;template struct AdjMatrix { T vertex[MaxSize];//存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 int vertexNum, arcNum;//图的顶点数和边数 };邻接表存储结构定义如下： const int MaxSize=10;struct ArcNode //定义边表结点 { int adjvex;//邻接点域 ArcNode *next;};template struct VertexNode //定义顶点表结点 { T vertex;ArcNode *firstedge;};struct AdjList { VertexNode adjlist[MaxSize];int vertexNum, arcNum;//图的顶点数和边数 };具体算法如下： 一、混选题（单选还是多选自己判断）1．海关四项基本任务的基础是（）A A 监管 B 征税 C 查缉走私 D 编制海关统计 2．关于报关员资格的表述正确的有（）ABC A 遵纪守法，品行端正 B 年满18周岁，具有大专及以上学历 C 全国报关员资格统一考试成绩合格，获得报关员资格证书 D 受雇于一个报关单位 3．进出口收发货人不能进行的报关行为是（）B A 办理本单位的报关业务 B 代理其他单位的报关业务 C 通过本单位所属的报关员向海关报关 D 可以委托海关准予注册登记的保关企业为办理报关 4．报关员遗失报关员证件，应当及时向注册地海关书面说明情况，并在报刊声明作废。海关应当自收到情况说明和报关声明证明之日起（）内予以补发。C A 10日 Ｂ 15日 Ｃ 20日 Ｄ 30日 5．以下属于海关行政强制权的有（）BCD A 稽查权 B 强制扣缴和变价抵缴关税权 C 扣留权 Ｄ 滞报，滞纳金征收权 6．申请分支机构登记许可的报关企业应当符合（）的条件 ABD A 自取得报关企业登记证书满２年 B 自申请之日起最近２年内未因走私受过处罚 C 自申请之日起最近３年内未因走私受过处罚 D 每申请一项跨关区分支机构应增加注册资本人民币50万元 7．下列关于报关单位和报关员关系的理解错误的是()C A 取得报关员资格证书的人员必须受聘于某个报关单位，且由其所在报关单位为其向海关办理注册登记后才能成为报关员 B 报关单位的进出口报关事宜应由报关员代表本单位向海关办理 C 报关员基于所在企业授权的报关行为，其法律责任应由报关员承担 D 对脱离报关员工作岗位和被企业解聘的报关员，报关单位应及时收回其报关员证件，交海关办理注销手续，因未办理注销手续而发生的经济法律责任由报关单位负责 8．关于海关对报关员记分考核管理的表述正确的是（）ABC A 《报关员记分考核管理办法》自2005年１月１日起施行 B 管理对象是在职报关员 C 一次记分分值分别为1分、2分、5分、10分、20分、30分 D 记分周期从每年6月１日起至第二年的6月1日止 9．只能接受有权进出口货物单位的委托，办理本企业承揽，承运货物的报关业务，是（）应遵守的报关行为规则。C A 进出口货物收发货人 B 专业报关单位 C 代理报关单位 D 报关公司或报关行 10．进出口货物收发货人应当在收发货人登记证书有效期届满前（）到注册地海关办理换证手续。B A 15日 B 30日 C 40日 D 60日 11．关于报关员的表述错误的是（）AB A 通过报关员资格考试即可申请海关注册登记 B 报关员可以自己的名义接受社会企业的委托代理保关业务 C 报关员明知报关单位的行为违法而故意实施，应承担连带责任 D 报关单位的报关业务由所属报关员向海关办理 12．根据《报关员记分考核管理办法》的规定，记分达到（）的报关员，海关中止其报关员证效力，不再接受其办理报关手续。C A 15分 B 20分 C 30分 D 50分 13．海关权力行使应遵循（）ABCD A 合法原则 B 适当原则 D 依法独立行使原则 D 公正公开原则 14．自进出口货物放行之日起（）内，海关可以对与进出口货物直接有关的企业，单位的会计帐簿，会计凭证，报关单证以及有关资料和有关进出口货物实施稽查。 A １年 B ２年 C 3年 Ｄ 4年 15．报关企业注册登记许可条件中对企业人员的要求包括()。(2005年考试题)ABC A 报关员人数不少于5名 B 投资者、报关业务负责人、报关员无走私记录 C 报关业务负责人具有5年以上从事对外贸易工作经验或者报关工作经验 D 报关业务负责人、报关员要通过海关规定的业务考核 16．海关作为国家进出关境的监督管理机关，对下列事务具有行政许可权（）（2004年考试题）ABD A 企业报关资格的许可 B 报关员的报关从业许可 C 企业从事对外贸易经营业务的许可 D 企业从事海关监管货物仓储业务的许可 17.下述海关权力的行使须直属海关关长或者其授权的隶属海关关长批准的是（）BCD A 检查权 B 查询权 C 强制扣缴和变价递交关税权 D 税收保全 18．海关行政行为一经作出，就应摧定其符合法律规定，对海关本身和海关管理相对人都具有约束力。这是海关权力的（）表现 C A 特定性 B 独立性 C 效力优先性 D 优益性 二、请完成以下工作项目 1.2007年11月28日，97台日本生产的二手挖掘机被国际运输船舶载抵上海外高桥港。到港后，该船就向外高桥海关申报进境，从该船向海关递交的载货清单上看，该批货物的收货人是杭州绮丽进出口公司（以下简称：绮丽公司）。但是该船申报进境后，收货人迟迟不露面。 2008年2月23日，外高桥海关根据载货清单上的地址，向绮丽公司发出了催报通知，请绮丽公司在2009年2月28日前向海关办理货物进口报关手续，并申明如逾期不向海关办理报关手续，海关将按《海关法》二十一条的规定提取变卖该批货物。3月1日，收货人通过地方政府部门，以无法领取机电产品进口证明为由，向外高桥海关提出退运该批货物的申请。由于其提出退货申请的时间超过海关总署有关规定的退运提出期限，不符合退运条件，外高桥海关于4月7日给出答复，不同意退运，并告知收货人，海关决定提取拍卖该批货物。受海关委托，一通公物拍卖行定于2009年4月22日举行该批货物的公开拍卖会。 2009年4月12日，收货人向上海市中级人民法院提起行政诉讼，请求法院撤销外高桥 海关作出的不准原告退运，并决定提取变卖该批货物的行政行为。 2009年4月22日，97台二手挖掘机在外高桥市进行公开拍卖，拍卖所得价款共计4 277．7万元。 在法院做出最终判决之前，杭州绮丽进出口公司找到了汉德报关行，请教胜诉的可能性。 王红的工作任务包括： 任务1：海关是否有权变卖处理超期未报关货物； 任务2：海关如何变卖超期未报关货物； 任务3：具备哪些条件绮丽公司才有权申领余款 任务4：给出杭州绮丽进出口公司建议。 【解答】对应任务1,海关有权变卖处理超期未报关货物。因为，至2009年2月28日，货物就已进境3个月了。 对应任务2，变卖后所得，用以抵缴：①变卖处理实际支出的费用；②运输、装卸、储存等费用；③进口关税；④进口环节海关代征税；⑤滞报金。 对应任务3，当抵缴以上5项费用还有余额时，绮丽公司才有权申领余款。 对应任务4，给杭州绮丽进出口公司的建议：①向法院提出撤诉申请；②向外高桥海关申请领回余款，以减少损失。 2.孔乙己公司是2004年9月在浙江绍兴市高新技术区新建的外商投资企业，主营涤纶丝的生产，尚未办理进出口备案手续，也未注册登记为报关单位，现因业务需要，要拓展国外市场，货物主要从上海、宁波口岸进出。孔乙己公司安排了小丁去办理相关手续。小丁应携带材料到哪里办理何种手续？ 小丁的工作任务包括： 任务1：去获得外贸经营权； 任务2：外贸经营权获得以后，货物进出口会涉及到哪些部门，故还要部门去备案注册？ 任务3：到这些部门备案注册时会提交哪些主要资料？ 【解答】对应任务1,到所在地的绍兴市商务局的对外贸易处办理企业的进出口经营权的备案登记手续,并提交了备案资料：①按要求填写的《对外贸易经营者备案登记表》；②营业执照复印件；③组织机构代码证书复印件等。 绍兴商务局在自收到黑土地公司提交的上述材料之日起5日内办理了备案登记手续，在《登记表》上加盖备案登记印章。 对应任务2,凭加盖备案登记印章的《登记表》在30日内到当地海关、检验检疫、外汇、税务等部门办理开展对外贸易业务所需的所有手续，当然也不能忘记到当地工商办理经营范围的变更。在营业执照经营范围中加入“货物及技术进出口”字样，孔乙己公司这才具备了可以从事进出口相关业务的资格。 对应任务3,孔乙己公司到大连海关办理注册登记,根据企业的不同性质,获得了企业的10位海关编码和《中华人民共和国海关进出口收发货人报关注册登记证书》。 一、不定项选择题 1.《禁止进口货物目录》（第三、四、五批）所涉及的是对环境有污染的固体废物类，包括（）。AB A 城市垃圾、医疗废物 B 含铅汽车淤渣 C 动物尸体 D 土壤 2.下述不符合限制进出口技术管理的是（）。CD A 限制进出口技术实行目录管理 B 进出口属于限制的技术，应当先向外经贸主管部门申领技术进出口许可意向书 C 进出口经营者凭技术进出口合同向海关办理进出口通关手续 D 进出口经营者取得技术进出口许可证后，可以对外签订技术进出口合同 3.我国出入境检验检疫制度内容包括（）。ABC A 进出口商品检验制度 B 进出境动植物检疫制度 C 国境卫生监督制度 D 进出口商品质量公证鉴定制度 4.下述贸易救济措施适用对象正确的是（）。C A 反倾销、反补贴、与保障措施针对的均是不公平贸易或不公平竞争 B 三者均针对公平条件下数量猛增的进口产品 C 前二者针对的是不公平贸易或不公平竞争，后者针对公平条件下数量猛增的进口产品 D 前二者是针对公平条件下数量猛增的进口产品，后者针对不公平贸易或不公平竞争 5.下述许可证件中有效期为1年，特殊情况下需跨使用，有效期最长不超过次年3月31日是指（）。ACD A 进口许可证 B 出口许可证 C 两用物项和技术进口许可证 D 两用物项和技术出口许可证 6.用于列入《进出口野生动植物种商品目录》中属于我国自主规定管理的野生动物及其产品的进出口通关凭证是（）。B A 公约证明 B 非公约证明 C 非物种证明（当年使用）D 非物种证明（一次性使用） 7.下述由国家环保总局签发的进出口许可证件是（）。ACD A 废物进口许可证 B 公约证明 C 黄金及其制品进出口准许证 D 进口音像制品批准单 【应会考核】 二、辨识进出口商品是否属于管制商品 请查询以下商品属于哪一类进、出口管制或管理，能否经营其进出口或需要向海关提供什么许可证件？ 税则号 商品名称 进出口状态 51051000 粗梳羊毛 进口 11031100 小麦的粗粒及粗粉 进口 10064010 籼米碎米 出口 02022000 冻藏的去骨牛肉 出口 26090000 锡矿砂 出口 87112020 排气量120cc的小马力摩托车 出口 27030000 泥炭 出口 25059000 天然砂 出口 61034200 棉制针织男长裤 出口 60052300 色织棉制经编织物 出口美国 29394100 麻黄碱 进口 51000010 牛黄 进口 31021000 尿素 进口 85238011 已录制的唱片 进口 【解答】http://shanghai.customs.gov.cn/default.aspx 上海海关网查询→商品编码查询→输入商品编码，再对应附录的监管证件代码表，就能很快找出需向海关提供哪种监 管证件。 三、请完成以下工作项目 天津远洋进出口公司向美国某商行出口一批厚板材（商品编码4407999099），合同号为 08-H-26-099，规格20up×30up×300mmup，厚度大于6mm，总数量15m，单价是USD300.00/ mFOB天津新港，10月份装运，采用不可撤销即期信用证付款。根据上述条件填写出口许可证。出口许可证见下页。 任务1：根据上述条件填写出口许可证； 任务2：向发证机关申领上述出口许可证时，应提供哪些材料？ 任务3：发证机关在确认材料无误的前提下，办证工作日需多长时间、才可发证？ 【解答】对应任务一，填制出口许可证如下： 一、混选题（单选还是多选自己判断） 1．进口一辆缺少轮子的汽车，在进行该商品的海关税则归类时，应按（D）归类。A 汽车的零部件 B 汽车底盘 C 汽车车身 D 汽车整车 2．按照商品归类总规则，下列叙述中正确的是(C)。A 在进行商品归类时，商品的包装容器应单独进行税则归类 B 在进行商品归类时，混合物可以按照其中一种成分进行税则归类 C 在进行商品归类时，列明比较具体的税目优先于一般的税目 D 从后归类的原则是商品税则归类的普遍使用原则 3．HS中的税（品）目中所列货品，除完整品和制成品外，还应包括（ABCD）。A 在进出口时具有完整品基本特征的不完整品 B 在进出口中具有制成品基本特征的未制成品 C 完整品或制成品在进出口时的未组装件或拆散件 D 具有完整品或制成品基本特征的不完整品或未制成品在进出口时的未组装件或拆散件 4．下列货品属于HS归类总规则所规定的“零售的成套货品”的是（A C）。A 一个礼盒、内有咖啡一瓶、咖啡伴侣一瓶、杯子两只 B 一个礼盒、内有白兰地酒一瓶、打火机一只 C 一个方便面、调料包两包、叉子一把 D 一个礼盒、一块巧克力、—个塑料玩具 二、请查找下列商品的HS编码 1． 干海马 03055910 2． 冻对虾虾仁 03061321 3．计算机网络通讯用的路由器 85176236 4．蓝色机织物，按重量计含40%合成纤维，35%精梳羊毛，25%的精梳动物细毛（每平方米210克、幅宽180厘米）5112.9000 5．冬虫夏草 12119016 6．家用电动蔬菜榨汁器（3公斤重）85094010 7．食品罐头成分含量：50％猪肉块，20％虾仁，30％其他配料 16024910 8．湿度记录仪 9025.8000 9.丙稀——异丁烯共聚物，按重量计含丙稀单体单元98％异丁烯单体单元2％（初级形状）39021000 10．碳13（碳的同位素）28459000 11．旅游鞋（外底为橡胶塑料，鞋面为尼龙机织物，在鞋面上缝有起加固增强作用的聚 氨酯合成革条，肉眼所见织物面积小于合成革面积）6404.1900 12．人用流感疫苗 30022000 13．真丝领带 6215.1000 14．块状酒心巧克力 1806.3100 15．萨克斯管 9205.1000 16．按摩座椅 90191010 17．铝制压力锅（直径22厘米）76151900 18．填充的玩具熊猫 95030021 19．纯棉男式牛仔裤 62034290 20．家用等离子空气净化器 84213910 三、请完成以下工作项目 2009年3月，浙江华通机电进出口公司为杭州瑞丰混凝土公司代理进口10辆机动混凝土搅拌车，浙江华通机电进出口公司委托汉德报关行办理商品归类和确定海关监管条件。 任务1：要认知，要“识货”； 任务2：套用六大归类总规则； 任务3：归出税则号； 任务4：利用INTERNET电子途径确定海关监管条件。【解答】 操作1：识货。汽车车辆类货车机动车混凝土车混凝土搅拌车 操作2：可套用规则三 （一）“具体列名” 操作3：归出税则号87054000 操作4：.http://shanghai.customs.gov.cn/default.aspx 上海海关网查询→商品编码查询→输入商品编码，可知该混凝土搅拌车的海关监管条件为：“AB6O”。A（入境货物通关单）、B（出境货物通关单）、6（旧机电产品禁止进口）、O（自动进口许可证）。对于本例来说只需要“AO”。 一、不定项选择题 1.出口货物的申报期限为货物运抵海关监管区后、装货的（B）以前。A 48小时 B 24小时 C 14日 D 15日 2.进口货物的申报期限为自装载货物的运输工具申报进境之日起（C）内。A 48小时 B 24小时 C 14日 D 15日 3.载运某批进口货物的船舶于4月17日（星期五）向海关申报进境，而货物至5月8日（5月1日到5月7日为节假日）报关，收货人滞报几日？（）D A 滞报5天 B 滞报4天 C 滞报3天 D 滞报0天 4.在报关程序中，前期阶段适用的范围是（ACD）A 进出境展览品 B 一般进出口货物 C 保税加工进出口货物 D 特定减免税货物 5.电子报关的申报方式有（ABC） A 终端申报方式 B EDI申报方式 C 网上申报方式 D 提取或装运货物 6.进口货物自装载货物的运输工具申报进境之日起超过（C）仍未向海关申报的，货物由海关依照《海关法》的规定提取变卖处理。 A 14日 B 15日 C 3个月 D 6个月 7.某批易腐进口货物通关时，因涉嫌走私被海关扣留，在此期间货物发生变质，对此损 失应以下列哪种方式处理？（）C A 因货物发生变质与收货人或其代理人涉嫌走私有关，故该损失由其承担50%，海关赔偿50% B 因其变质与海关扣留货物有关，故该损失应由海关承担 C 因其变质是在海关正常工作程序所需时间内发生，海关不予以赔偿 D 构成走私，损失由收货人或其代理人自负；未构成走私，损失由海关负责赔偿 8.关于海关接受申报的时间，下列表述错误的是：（C） A 经海关批准单独以电子数据报关单形式向海关申报的，以“海关接受申报”的信息发送给进出口货物收发货人或其代理人，或者公布于海关业务现场的时间为接受申报的时间 B经海关批准单独以纸质报关单形式向海关申报的，以海关在纸质报关单上进行登记处理的时间为接受申报的时间 C在先以电子数据报关单向海关申报，后以纸质报关单向海关申报的情况下，海关接受申报的时间以海关接受纸质报关申报的时间为准 D在采用电子和纸质报关单申报的一般情况下，海关接受申报的时间以海关接受电子数据报关单申报的时间为准 9.申报单证可以分为两大类，即（BD） A 预备单证 B 主要单证 C 基本单证 D 随附单证 10.在一般情况小，进出口货物或其代理人应当自接到海关“现场交单”或者“放行交单”通知之日起多少日内，持打印的纸质报关单，备齐规定的随附单证并签名盖章，到货物所在地海关提交单证并办理相关海关手续？（B） A 7日 B 10日 C 14日 D 15日 11.进出口货物收发货人或其代理人在办理完毕提取进口货物或装运出口货物的手续后，如有需要，可以向海关申请签发有关货物的进口、出口证明。海关签发的常见证明主要有：（ABD） A 进口货物报关单（付汇证明联）和出口货物报关单（收汇证明联）B 出口货物报关单（出口退税证明联）C 进口货物报关单（进口货物证明联）D 进口货物证明书 12.某批货物由列车载运进境，经海关批准，收货人（内地某外贸公司）在列车上申报进境21天后委托专业报关公司向进境地海关办理转关运输手续，并于货物运抵指运地后第8天向该企业所在地海关正式申报。因下列哪项原因，申报人必须缴付滞报金？（）B A 未在规定期限向货物指运地海关正式报关 B 未在规定期限向进境地海关办理转关运输手续 C 未在规定期限向进境地海关正式报关 D 既未在规定期限办理转关运输手续，又未在规定期间正式报关 13.北京某企业将一批机械设备销往南非，该批货物采用出口直转的方式，已向北京海关办理了相关转关手续，并将货物用汽车运至天津口岸，在天津口岸出境时，报关员应该向天津海关出具下列哪些单证资料？（）ABD A 北京海关签发的出口货物报关单 B 出口转关货物申报单 C 出境汽车载货清单 D 汽车载货登记簿 14.北京A企业从美国进口一批大豆，货物从天津进境。A企业在天津海关办理进口货物转关手续前，向北京海关录入“进口货物报关单”电子数据，北京海关受理后，向天津海 关传输有关数据。A企业在向天津海关办理转关手续时要提供（）。ABCD A “进口转关货物申报单”编号 B 提货单 C 进口转关货物核放单 D 汽车载货登记簿 二、请完成以下工作项目 中国成套设备进出口总公司（北京）（CHINA NATIONAL COMPLETE PLANT IMPORT & EXPORT CORP.）与法国LECLEC公司于2005年7月8日在广州签定了出售户外家具（outdoor furniture）的外贸合同，货名：花园椅（Garden Chair, 铸铁底座的木椅，按规定出口时需要有动植物检验检疫证明），型号：TG0503，价格：USD58.00/PC FOB Guangzhou，数量：950把，毛重：20KGS/PC，净重：18KGS/PC，包装：1PC/CTN，集装箱：1X20’，生产厂家：广东南海飞达家具厂，最迟装船日期：2005年9月8日，起运港：广州港，目的港：马赛，支付方式：不可撤销信用证。 任务1：根据以上资料为出口公司整理一份销售合同/成交确认书。 答：SALES CONFIRMATION，列名合同条款：品名、规格、成交方式、装运港、目的港等，中英文对照。 任务2：如果中国成套设备进出口总公司委托广州穗港报关行报关，是否要办理异地报关备案手续？需要的话，应如何办理？ 答：不用办理异地报关备案手续。因为实现了电子口岸，当一个企业一家进出境海关备案之后，这个资料可通电子口岸资料共享。 任务3：如果订舱的装船时间是2005年9月8日10:00 am，那么，报关员应最迟何时在何地报关完毕？ 答：最迟应于2005年9月7日10:00 Am报关完毕。任务4：如果报关员在8月20日以电子数据报关单向海关申报，8月22日收到海关“放行交单”的通知，那么，报关员应不迟于哪一天持打印的纸质报关单，备齐哪些单证到货物所在地海关提交书面单证并办理相关海关手续？ 答：报关员应不迟于9月1日。备齐的单证有：出口报关单、出口收汇核单、装箱单、发票、装货单等。 任务5：应该缴纳哪些海关规定的税费？ 答：不须缴纳税费，相反还可在办理外汇核销之后，向国税申请办理退税。任务6：为该批出口货物出货的进行流程设计。 设计：①查询是否需要出口批件，若要的话，须办理； ②准备报关资料； ③电子申报； ④纸质申报； ⑤陪同查验（若海关要查货的货） ⑥领取海关退单，办理出口收汇核销、出口退税。 2.武汉泰华公司（420123xxxx）在投资总额内委托武汉机械进出口公司(420191xxxx)于2005年6月与香港某公司签约进口一套自用设备，该设备属于鼓励类进口项目。设备于2006年6月1日从上海吴淞海关进境，该合资企业委托上海华宇货代公司于2006年6月2日向上海海关办理转关申请手续，后由“长江号”轮船于2006年6月5日（周一）运抵武汉，并于2006年6月20日向武汉江岸办理进口报关手续，货物经海关查验后放行。 任务1：在此情境中，属于哪种转关方式？ 答：直转转关 任务2：在向海关递交的进口货物报关单“运输工具名称”一栏应中如何填报？ （提示：水路运输下，直转、提前报关填报“@”＋16位转关申报单预录入号；中转填报进境英文船名） 答：“@”＋16位转关申报单预录入号 任务3：在此情境中，该企业应该缴纳多少天的滞报金？ 答：应向海关缴纳1天的滞报金 任务4：在此情境中，在向上海海关办理转关手续时，应提交哪些单证？ 答：进口转关运输货物申报单、船舶监管簿 一、不定项选择题 1．保税加工货物内销，海关按规定免征缓税利息的是（）。C A 副产品 B 残次品 C 边角料 D 不可抗力受灾保税货物 2．下列哪一选项不属于海关非物理围网监管模式的监管（）。D A 来料加工企业和进料加工企业 B 保税工厂 C 保税集团 D 出口加工区 3．加工贸易保税期限表述正确的是下列哪些选项（）。ABCD A 实行纸质手册管理的料件保税期限，原则上不超过1年，经批准可以申请延长，延长最长期限原则上也是一年 B 实行电子账册管理的料件保税期限，从企业电子账册记录第一批料件进口之日起到该电子账册撤销止 C 实行电子手册管理的料件，原则上不超过1年，经批准可以申请延长，延长最长期限原则上也是一年 D 出口加工区保税加工的保税期限，原则上是从加工贸易料件进区到加工贸易成品出区办结海关手续止 4．银行根据海关签发的哪一选项文件，对加工贸易企业设立“银行保证金台账”（）。B A 银行保证金台账通知书 B 设立银行保证金台账联系单 C 银行保证金台账核销联系单 D 银行保证金台账变更联系单 5．下列哪一选项商品在加工贸易企业向海关备案时应提交进口许可证（）。B A 毛豆油 B 消耗臭氧层物质 C 蒸馏酒 D 钢材 6．加工贸易经营单位委托异地生产企业加工企业加工产品出口，应当向哪一选项海关 办理合同备案手续（）。A A 加工企业所在地主管海关 B 经营单位所在地主管海关 C 海关总署 D 进口料件进境地海关 7．某C类管理的企业，与外商签订进口1000美元的服装拉链（属于列明的78种辅料）加工贸易合同，用以加工产品出口，应（）。A A 设台账、实转、发手册 B 设台账、实转、免手册 C 不设台账、发手册 D 不设台账、免手册 8．下列是关于加工贸易企业设立银行保证金的表述，哪些选项是正确的（）。ABC A 适用B类管理的企业经营允许类的商品，银行保证金台账“空转”，经营限制类的商品按照料件应缴税款50%付银行保证金 B 适用C类管理的企业，经营加工贸易允许类和限制类商品，实行保证金台账“实转” C 适用A、B类管理的企业，在出口合同中，由外商提供的78种列明辅料金额不超过10000美元，不设银行保证金台账 D 适用C类企业在出口合同中，由外商免费提供的78种列明辅料金额不超过5000美元，不设银行保证金台账 9．下列是关于保税贮存期限的表述，哪些选项是正确的（）。ABCD A 保税仓库货物的贮存期限为一年，可以申请延长，延长的期限最长不超过一年 B 出口监管仓库货物贮存期限为6个月，可以申请延长，延长期限不超过6个月 C 保税物流中心A型保税贮存期限为1年，可以申请延长，延长期限不超过1年；保税物流中心B型保税贮存期限为2年，可以申请延长，延长期限不超过1年 D 保税物流园区货物不设贮存期限 10．下列哪些选项由直属海关批准设立（）。AB A 保税仓库 B 出口监管仓库 C 保税物流中心A型 D 保税物流中心B型 11．下述珠海园区可以开展的业务是（）。ABCD A 加工制造 B 储存进出口货物 C 进出口贸易 D 国际中转 12．保税物流中心不能开展的业务是（）。B A 保税存储进出口货物及其他未办结海关手续货物 B 维修、翻新和拆解 C 转口贸易和国际中转业务 D 对所存货物开展流通性的简单加工和增值服务 13．下列选项中，哪些选项表述不正确（）。BD A 进口保税仓库自用货架照章征税 B 保税区仓储企业进口的自用货架照章征税 C 保税物流中心进口的自用货架照章征税 D 保税物流园区进口的自用货架照章征税 14．保税物流园区不可以开展的业务是（）。D A 进出口贸易 B 国际采购、分销和配送 C 对所存货物开展流通性简单加工和增值服务 D 加工制造、翻新和拆解 15．从境外进入物流园区的货物，下列哪些选项表述是正确的（）。ACD A 园区企业为开展业务所需货物及其包装材料进口保税 B 园区加工贸易企业进口的料件保税 C 贮存的进口货物保税 D 贮存的为办结海关手续的进口货物保税 16．下列哪一选项从境外进口的货物照章征税（）。D A 出口加工区从境外进口的区内企业自用的生产管理设备 B 保税区企业从境外进口的仓储设备 C 保税物流园区进口的仓储设备、管理设备 D 出口加工区从境外进口的自用交通工具、生活消费品 17．下列哪一选项从境外进口的自用物资(交通工具、消费品除外)可以享受特定减免税的优惠待遇（）。D A 保税仓库 B 出口监管仓库 C 保税物流中心 D 保税物流园区 18．物流中心、物流园区、出口加工区、保税区货物出区到境内区外，表述正确的是 （）。BCD A 出区报进口。海关一律按照一般进口货物照章征税并办理其他相应报关手续 B 出区报进口。如用于境内消费，海关按照一般进口货物报关程序照章征税，并办理相应的海关手续 C 出区报进口。如用于境内消费，海关按照特定减免税报关程序办理海关手续 D 出区报进口。如用于加工贸易，海关按照加工贸易报关程序办理海关手续 19．境内区外货物进入物流中心、物流园区、出口加工区、保税区，下列选项表述正确的是（）。ABCD A 进区报出口。对进入物流中心、物流园区、出口加工区货物在办理进区出口手续时，海关即可签发出口退税报关单证明联（自用交通工具、生活物资等除外） B 进区报出口。对进入保税区的货物，在办理进区出口手续时，海关不立即签发出口退税报关的证明联，待货物实际运输出境，经海关核实再签发出口退税报关单证明联 C 进区报出口，对境内区外的国产设备进入物流中心、物流园区、出口加工区自用，在办理进区出口手续时，海关即可签发出口退税报关单证明联;对进入保税区自用的国产设备，应向海关备案，不填写报关单，不缴纳出口税，海关不签发出口退税报关单证明联 D 对进入物流中心、物流园区、出口加工区、保税区自用的原进口设备，在办理进区手续时，海关不退还原进口时已征得进口税款，也不签发出口退税报关单证明联 【应会考核】 二、综合实务题 题一：注册于上海的某加工贸易经营企业（属海关A类管理企业）与韩国一电子企业签订了一份来料加工合同，委托苏州某加工企业（属海关B类管理企业）进行加工。在料件进口前，该企业已向海关办理了加工贸易合同登记备案手续。2004年3月6日企业购进的料件（限制类）从上海海关申报进境，进境后随之运到加工企业进行加工。一个月以后由于国际市场需求变化，该企业的进口料件生产的部分半成品在经过批准后内销到国内市场。企业持相关批文于2004年4月19日向海关办理了内销申报手续。剩余的加工成品，企业于2004年5月5日返销出口，企业在成品出口后向海关核销结案。 根据上述案例，回答下列问题。1．该加工企业应（）。B A 设保证金台账，实转 B 设保证金台账，付应征税款的50％为保证金 C 不设保证金台账 D 设保证金台账，空转 2．海关在对该项跨关区异地加工贸易合同进行分类管理时，应该按照（）进行管理。B A A类 B B类 C C类 D D类 3．题中申报内销的货物应适用于（）的税率。B A 2004年3月6日 B 2004年4月19日 C 2004年5月5日 D 以上都不对 4．该来料加工合同应该向（）办理加工贸易合同登记备案。B A 上海海关 B 苏州海关 C 海关总署 D 三者都要办理 5．企业在合同报核时应提交的单证为（）。ABCD A 企业合同核销申请表 B “加工贸易保税进口料件内销批准证” C “加工贸易登记手册” D 进出口报关单 题二：江西南昌出口加工区某企业履行进料加工合同，料件从上海口岸进口，同时从境外与境内区外各购进加工设备1台。加工中因工艺原因，需将加工的半成品运往区外进行加工，产品运回加工区后返销境外，余料与边角料内销。 6．对于跨关区进出境的出口加工区货物，符合海关监管要求的操作是（）。B A 按直通式报关 B 按直转转关方式报关 C 按转关运输中提前式报关 D按中转转关方式报关 7．从境外与境内区外进区的加工设备，符合海关税收政策的是（）。A A 前者免税，后者征税 B 前者征税，后者免税 C 两者均免税 D 两者均征税 8．出口加工区内企业企业需要将有关半制成品运往区外外发加工，其正确程序是（）。B A 由区外企业向加工区主管海关申报进口，缴纳进口关税，区内企业在加工区海关备案 B 由区外企业向加工区主管海关缴纳与进口税费等值的保证金或银行保函，办理出区手续 C 由区外企业向加工区主管海关办理加工贸易合同登记备案，按保税货物进口办理相关 手续 D 由出口加工区企业向接受委托的区外主管海关办理转关手续 9．区内企业在加工中产生的边角料的处理，正确的做法是（）。ABC A 应当复运出境 B 经海关核准内销的，按内销时状态确定归类并征税 C 经海关核准内销的，可免予进口许可证件管理 D 经海关核准内销的，可免纳进口关税，但不豁免进口许可证件管理 三、请完成以下工作项目 1．上海某专营进料加工集成电路块出口的外商投资企业A公司是适用海关B类管理的企业。该企业与2007年3月对外签订了主料硅片（非限制类商品）等原材料的进口合同，按合同企业30%加工成品内销，70%加工成品外销，原料4月底交货。6月份与境外商人订立了集成电路块出口合同，交货期为10月底。9月底产品全部储运。 作为A公司的报关员，要完成这个进料加工报关业务，须进行的工作任务： 任务一：外销部分须申领登记手册。如何去领？ 任务二：办理主料进口报关，如何办理？（提示：有个“三七开”的问题）任务三：办理成品出口手续，如何办理？ 任务四：办理合同核销手续，如何办理？ 【解答】 对应任务一：先报商务主管部门批，取得两个批件；办理台账，但实际空转，因为是B 类，允许类商品。 对应任务二：30%内销，报一般贸易；70%加工成品外销，报进料加工。对应任务三：货物备好——领出口收汇核销单——报关单及其他单证资料——到海关申 报（加工贸易登记手册、出口货物报关单及其他单证资料）——查验——放行 对应任务四：出货“后1个月内去办理核销。核销时要有：登记手册、报关单核销联、加盖企业公章的企业合同核销申请表；核销核算表等。经上海海关予以核销的，凭上海海关 签发的“银行保证金台账核销联系单”到指定中国银行办理台账的核销手续。凭银行出具的“银行保证金台账核销通知单”到上海海关领取核销结案通知书。 2．保税区某企业进料加工，生产激光光盘出口，其中部分料件为进区国产料件。因外 商要求变更合同，减少光盘出口数量，部分产品未能如约出口而出区进入国内市场或出区移作他用，在加工过程中产生的残次品、边角料亦运往区外。 须进行的工作任务： 任务一：办理国产料件进区，如何办理？ 任务二：部分产品出境应如何办理？ 任务三：部分产品、残次品、边角料出区内销应如何办理？ 【解答】 对应任务一：国产料件进区，报出口，要有加工贸易纸质手册或者加工贸易电子账册、电子手册；要填写出口货物报关单，提供有关的许可证件；海关不签发出口货物报关单退税证明。 对应任务二：部分产品出境，即实际出口，应签发出口货物报关单退税证明；可豁免许可证件；实行备案制；填写“进出境货物备案清单”。 对应任务三：①部分产品进出境内区外，按实际流向来报，转为“一般进口”、“保税加工”、“特定减免税”。 残次口出区内销，视为一般进口，须补征关税。并还须交缓税利息。边角料出区内销，也视为一般进口，须补征关税。但不需交缓税利息。 一、不定项选择题 1．北京某外资企业从美国购进大型机器成套设备，分三批运输进口，其中两批从天津进口，另一批从青岛进口。该企业在向海关申请办理该套设备的减免税手续时，下列做法正确的是()。B A 向北京海关分别申领两份征免税证明 B 向北京海关分别申领三份征免税证明 C 向天津海关申领一份征免税证明，向青岛海关申领一份征免税证明 D 向天津海关申领两份征免税证明，向青岛海关申领一份征免税证明 2．某纺织品进出口公司在国内收购一批坯布运出境印染，复运进境后委托某服装厂加工成服装，然后回收出口。前后两次出口适用的报关程序分别是()。C A 暂准出境和一般出口 B 一般出口和进料加工 C 出料加工和一般出口 D 出料加工和进料加工 3．与展出活动有关的物品也可以按展览品申报进境的是指（）。AB A 为展出示范过程中被消耗的物料 B 展出中免费散发的宣传印刷品 C 展出期间出售的小卖品 D 展出期间使用的酒精饮料、燃料 4．下列属于暂准进出境货物特征的是()。ABCD A 有条件暂时免予缴纳税费 B 规定期限内按原状复运进出境 C 按货物实际适用情况办结海关手续 D 免予提交进出口许可证 5．上海某航运公司完税进口一批驳船，使用不久后发现大部分驳船油漆剥落，遂向境外供应商提出索赔，供应商同意减价60万美元，并应进口方的要求以等值的驳船用润滑油补偿。该批润滑油进口时应当办理的海关手续是()。A A 按一般贸易进口报关，缴纳进口税 B 按一般贸易进口报关，免纳进口税 C 按无代价抵偿货物报关，缴纳进口税 D 按无代价抵偿货物报关，免纳进口税 6．进口货物的收货人自运输工具申报进境之日起超过3个月未向海关申报的，其进口货物由海关提取依法变卖处理。变卖所得价款在优先拨付变卖处理实际支出的费用后，其他费用和税款的扣除顺序是()。A A 运输、装卸、储存等费用——进口关税——进口环节税——滞报金 B 进口关税——进口环节税——滞报金——运输、装卸、储存等费用 C 滞报金——进口关税——进口环节税——运输、装卸、储存等费用 D 运输、装卸、储存等费用——滞报金——进口关税——进口环节税 7．根据现行海关规定，下列进口货物不属于海关减免税优惠范围的是()。A A 沿海经济开放地区基建项目所需进口机械设备 B 边民互市和边境小额贸易的进口货物 C 残疾人组织和单位进口的货物 D 保税区内适用于自用的生产设备 8．由日本大阪启运，在上海转运至新加坡的货物属于（）。B A 过境货物 B 转运货物 C 通运货物 D 转关货物 9．进出境快件KJ2报关单适用于（）。BC A 文件类进出境快件 B 关税税额在人民币50元以下的货物 C 免税的货样、广告品 D 应予征税的货样、广告品 10．下述不符合海关对租赁货物监管有关规定的是（）。CD A 纳税义务人应在每次支付租金后15日内按支付的租金额向海关申报纳税 B 租赁货物进口时应按租金和货物的实际价格分别填制报关单，并提供租赁合同，进口许可证件及其他报关单证 C 租赁货物按一般进出口货物报关，海关放行后放弃监管 D 租赁货物海关放行后，对货物进行监管，纳税义务人应当在租期届满之日起30日内申请办结海关手续 11．向海关申报无代价抵偿货物进出口时除应当填制报关单和提供其他必须的报关单证外，还应当提供的特殊单证是（）ABCD A 原进出口货物报关单 B 退运进出境的报关单或放弃交由海关处理的证明 C 原进出口货物税款缴纳书 D 索赔协议 12．运输工具负责人或其代理人要求将溢卸货物抵补短卸货物的，应与短卸货物原收货人协商同意，并限于（）。ABC A 同一运输工具、同一品种的进口货物 B 不同运输工具、同一运输公司、同一发货人、同一品种的进口货物 C 同一运输工具非同一航次、同一运输公司、同一发货人、同一品种的进口货物 D 不同运输工具、不同运输公司、同一发货人、同一品种的进口货物 13．下述不属于海关责令直接退运的货物是（）BD A 进口国家禁止进口的货物，经海关依法处理后的 B 有关贸易发生纠纷，能够提供法院判决书、仲裁机构仲裁决定书或者无争议的有效货物所有权凭证的 C 未经许可擅自进口属于限制进口的固体废物用作原料，经海关依法处理后的 D 海关已经确定检验或者认为有走私违规嫌疑的货物 14．下述有关溢卸货物、误卸货物处理符合海关规定的是（）。ABC A.误卸货物如属于运往国内其他口岸的，可由原收货人就地向进境地海关申报进口，也可以经进境地海关同意办理转关手续ABC B.原收货人不接的，可以要求在国内销售，由购货单位办理相应海关手续 C.超过3个月未办理退运或申报进口手续的，由海关提取依法变卖处理 D.海关对误卸、溢卸货物不可以提前提取依法变卖处理 【应会考核】 二、综合实务题 某中港合资企业用自有资金进口企业自用的专用设备1台，CIF10万人民币，属进口许可证件管理，企业向主管海关办理了减免税备案登记，申领了《征免税证明》，并向海关申报进口。设备进口后使用了2年6个月，因产品调整，企业将设备转售给国内另一家企业，价格为3万人民币。 1．外商投资企业向主管海关办理减免税备案登记应提交（）。ABC A 商务主管部门的批准文件 B 营业执照 C 企业合同及章程 D外商投资企业征免税登记手册 2．下述不符合“进出口货物征免税证明”使用有关规定的是（）。BC A 有效期为6个月，特殊情况可申请延长6个月 B 规定口岸海关使用 C 实行一份证明只能验收一批货物的原则 D 年内使用有效 3．设备进口货物报关单的有关栏目的填制错误的是（）。AB A 贸易方式填报：合资合作设备 B 征免性质填报：中外合资 C 用途栏目填报：企业自用 D 征免栏目填报：全免 4．本案例特定减免税货物在海关监管期内销售，符合规定的是（）。AD A 企业应当向海关办理缴纳进口税费的手续 B 海关按照原进口货物成交价格为基础确定完税价格 C 属进口许可证件管理的免交验许可证件 D 海关签发解除监管证明,企业即可将原减免税货物在国内销售 5．本案例特定减免税货物内销，其完税价格应为（）。B A 10万 B 5万 C 4.83万 D 3万 三、请完成以下工作项目 1．长春市B公司与俄罗斯C公司签署协议，进口光学玻璃材料，进口该产品是为了完成国家的863科技项目，所以可以享受减免税的优惠，货物从俄罗斯的莫斯科直接空运至北京。 作为B公司的报关代理，如何对这一票货物进行操作呢？ 任务1：申请办理征免税证明，如何办理？ 任务2：办理转关运输； 任务3：正式报关、提取货物； 任务4：办理后续处置。【解答】 操作分析： 由于货物是航空运输方式进行运输，而且货物属于高技术产品，需要专业的人士进行拆装，所以货物需要申请转关到最终用户的所在地进行申报较为适宜。 第一步，根据工作任务1，申请办理减免税证明 B公司可以享受特定减免税货物特定用途中的科教用品项目，所以携带本企业的相关手册，到所在地海关的关税科申请办理减免税证明手续。 第二步，根据工作任务2，申请办理货物的转关运输 货物属于高精尖的技术产品，需要专业的人士拆装，所以申请办理转关运输；由于货物是航空运输，最好采用提前报关的转关方式进行申报。 第三步，根据工作任务3，正式报关、提取货物 货物由海关的监管车运送到最终用户的所在地之后，进行正式的报关手续，申报→查验→提交减免税证明→海关放行→用户提取货物。 第四步，根据工作任务4，监管期满，办理解除监管的手续 监管期5年结束以后，到海关办理该货物的解除监管手续。 2．上海公安局邀请境外一无线电设备生产厂商到上海展览馆展出其价值100万美元的无线电设备，并委托上海某展览报关公司A办理一切手续。上海展出后又决定把其中价值40万美元的设备运到杭州展出。设备从杭州返回后，上海公安局决定购买其中的20万美元设备。境外厂商为了感谢上海公安局，赠送了5万美元的设备给上海公安部门。其余设备退出境外。 作为A公司的报关员须进行的工作任务？ 任务一：办理上海展出手续，如何办理？ 任务二：办理杭州展出手续，如何办理？ 任务三：办理展品闭馆出境前的仓储手续； 任务四：办理留购与赠送手续； 任务五：办理销案手续。【解答】 操作分析： 第一步，根据工作任务1，办理上海展出手续 1． 进境展览要由境内展出单位的上级主管部门审批。上海公安局展出，由公安部或上 海市人民政府审批。无线电设备要由“无管会”审批。暂时进口的“无管会”批件没有文号。展品属于暂时进口。 2． 凭公安部或上海市政府批件、上海市“无管会”没有文号的批件、展品清单及其他 展出资料到上海海关展览物品主管部门虹桥办事处备案。 3．物品到港后，填写进口货物报关单，预录入，电子通关。4．向虹桥办事处交单：（1）报关单；（2）“无管会”批件；（3）发票、装箱单、提货单。5．提供担保（保证金或保证函）。6．取得海关盖了放行章的提货单。7．提货。 8．在布置展出时，陪同海关查验，负责搬移货物、开拆包装、重封包装。 第二步，根据工作任务2，办理杭州展出手续 1．凭杭州展出单位上级主管部门的批件、展出清单及其他资料到杭州海关备案； 2．向杭州海关提前报关转关，或向上海海关直接转关，办理40万美元展品的转关运输 手续； 3．在杭州海关办理展出手续，闭馆后再以转关运输的方式转运至上海，到虹桥办事处办理有关手续。 第三步，根据工作任务3，展品闭馆出境前的仓储手续 1．60万美元的留在上海的展品应向虹桥办事处办理进入公共型保税仓库的海关手续； 2．从杭州运回的40万美元的展品也应向杭州办事处办理进入公共型保税仓库的海关手续。 第四步，根据工作任务4，办理留购与赠送手续 1．20万美元的留购展品： （1）如C公司有进出口经营权，则可由C公司与参展商签订进口合同；如C公司无进出口经营权，则应委托有关外贸公司签订进口合同。 （2）C公司填写进口报关单，预录入，电子通关，提供无管会有文号的批件和上海机电审查办的机电产品登记证明，以留购价作为完税价格缴纳进口税。 （3）凭已完税税款缴纳证和报关单以及海关签章的出库单从公共型保税仓库提取20万美元的无线电设备。 2．5万美元的赠送展品： (1)属于经贸往来无偿赠送的物品，要有公安局上级主管部门审批，无线电审批批件和机电审查批件，要照章纳税； (2)凭上述3个批件办理报关手续，填写报关单，预录入，电子通关，按进口CIF价格作为完税价格缴纳进口税。 第五步，根据工作任务5，办理销案手续。1.20万美元的留购展品和5万美元的赠送展品，凭已办结海关手续的有关单证来销案； 2.75万美元的展品的出库离境报关后，凭相关证明材料来办理销案，并凭担保收据向主管海关办理撤销担保手续。 一、不定项选择题 1．属于按征收方法不同分类的进出口关税是（）。ABC A 从价税 B 从量税 C 滑准税 D 特惠税 2．由于当前世界上多数国家加入了WTO，成员国(地区)之间在关税方面相互提供最惠国待遇并享受最惠国税税率，因此，人们通常将最惠国税称之为（）。C A 优惠关税 B 特惠关税 C 正常关税 D 普惠关税 3．下列驶入我国港口或者行驶于我国港口之间的船舶中，应征收船舶吨税的是（）。ABD A 已在香港缴纳船舶吨税的俄罗斯籍货船 B 由某中外合资经营国际运输公司租用的中国籍货船 C 中国远洋运输公司自有的班轮 D 中国远洋运输公司租用的在固定国际航线上营运的希腊籍船舶 4．海关在征收船舶吨税时，以船舶的（）计征。B A 注册总吨位 B 注册净吨位 C 实际装货吨位 D 小吨位 5．在下列情形中，海关可以不接受纳税义务人提供的成交价格作为完税价格而另行估定的是（）。ACD A 买卖合同规定买方必须将进口货物转售给卖方指定的第三方 B 买方是卖方的子公司，但成交价格并未受此关系的影响 C 买卖合同是在买方购货不少于1,000公吨的条件下订立的 D 卖方的执行董事在买方的公司中担任副总经理 6．韩国某公司将原产于澳大利亚的羊皮，在印度经鞣制、抛光加工成皮革后在韩国制成皮革箱包，后来港商采购了这批箱包并在香港更换了销售包装转销我国内地。我国海关应当以（）为该进口货物的原产地。A A 韩国 B 澳大利亚 C 印度 D 香港 7．浙江金华某化工进出口公司以“FCA杭州”价格条件出口巴基斯坦尿素一批，出口暂定税率为30%，货物实际从上海装船出境。海关以该货物的成交价格为基础确定完税价格时，应当扣除的项目是（）。D A 金华至杭州的运费和保险费 B 杭州至上海的运费和保险费 C 出口产品的包装费用 D 出口关税 8．海关以“成交价格法”确定一般进口货物的完税价格时，下列各项中的（）不应计入完税价格中。A A 买方支付给采购代理人的购货佣金 B 买方支付给销售代理人的销售佣金 C 买方支付给经纪人的经纪费 D 买方返回给卖方的部分收益 9．浙江天宇鞋业有限公司从意大利进口制鞋生产流水线一套，以CIF上海价格条件成交。出口方出具的商业发票列明：设备价款200000美元，海运运费10000美元，海运保险费1200美元，买方负担的销售佣金6000美元，设备安装调试费用10000美元，技术培训费用1800美元。海关确定该批进口设备的完税价格应当是（）。C A 229000美元 B 227200美元 C 217200美元 D 200000美元 10．以经营租赁方式对外支付租金的租赁进口货物，在租赁期间海关应当（）。AD A 以审定的租金作为完税价格，利息一并计入 B 以审定的租金作为完税价格，利息不予计入 C 采用该租赁进口货物的成交价格作为完税价格 D 予以监管，并在承租人对外支付租金后的15日内征收税款 11．海关在采用“相同货物成交价格估价法”审定某进口货物完税价格时，所参照的“相同货物”必须是（）。ACD A 与被估进口货物申报之日前后45天之内进口的货物 B 与被估进口货物在表面上无任何微细差异 C 与被估进口货物在同一个国家或者地区生产的货物 D 与被估进口货物在物理性质、质量和声誉等方面都相同的货物 12．我国在从价计征进口环节消费税时，采用（），其计算公式为：[(进口关税完税价格＋进口关税)÷(1－消费税从价税率)]×消费税从价税率。A A 价内法 B 价外法 C 倒扣法 D 混合法 13．按《进出口货物原产地条例》解释，“完全在一个国家或者地区获得”的进口货物,必须是完全在该国获得、生产制造、加工的货物。假如我国从A国进口下列货物，符合“完全获得”标准的货物是（）。ACD A 从A国饲养的水牛获取的牛皮 B 由悬挂B国国旗的船舶从公海上捕捞经由A国出口的鮭鱼 C 从A国领海以外享有专有开采权的海床获取的天然气 D 从B国进口在A国使用报废后作为废料回收的汽车轮胎 14．下列关于进口税税率适用表述正确的是（）。AD A 按照普通税率征税的进口货物，不适用暂定税率 B 同时适用协定税率和暂定税率的进口货物，应当从高征税 C 关税配额外的进口货物，通常也适用最惠国税率 D 对于无法确定原产国别的进口货物，应当按普通税率征税 15.《亚太贸易协定》项下的原产地规则要求，除孟加拉外，在生产过程中所使用的非成员国原产的或不名原产地的材料，零件或产物的总价值不超过该货物FOB价的（）。B A 65% B 55% C 40% D 30% 16．下列可以享受特定减免进口关税的货物有（）。ABC A 某省教委所属高校从美国进口的教学用幻灯片 B 农业部某科研机构从日本采购的国内目前无法生产的测试仪器 C 某省民政部门的福利机构从法国进口的残疾人用品 D 韩国政府无偿赠送的抗震救灾物资 17．下列关于补征和追征关税税款的范围、期限和要求的表述，正确的是（）。D A 因纳税义务人违规而少征或漏征关税的，海关可以在进出口货物放行后1年内补征和追征，并征收滞纳金 B 因纳税义务人违规而少征或漏征关税的，海关可以在进出口货物放行后1年内补征和追征，但可以免征滞纳金 C 进出口货物放行后2年内，海关发现少征或漏征关税，可以补征和追征，并征收滞纳金 D 进出口货物放行后1年内，海关发现少征或漏征关税，可以补征和追征，但不应征收滞纳金 二、计算题 1．某单位出口鳗鱼苗一批，离岸价格（FOB）为人民币10万元。2007年暂定出口税率为10％，最惠税率为20％。试计算该批出口货物的关税。 解：出口货物完税价格＝FOB/（1＋出口关税税率） ＝10000/（1+10%） 出口关税＝出口货物完税价格×出口关税税率 ＝10000×10%/（1+10%） ＝909.09元 2．某加工生产企业内销一批配额外未梳棉花1吨，原产地为美国，成交价格为CIF某口岸1053.58美元/吨。企业已向海关提交由国家发展改革委授权机构出具的“关税配额外优惠关税税率进口棉花配额证”，经海关审核确认后，征收滑准关税。已知其适用中国银行的外汇折算价为1美元＝人民币6.8396元，计算应征进口关税税款。 计算方法： ①确定税则归类，未梳棉花归入税号5201000080； ②确定关税税率，审定完税价格：1053.58×6.8396/1000＝7.206元/千克 由于7.206元/千克＜11.397元/千克时，故按暂定关税税率计算： Ri＝8.686/Pi＋2.526%×Pi－1 ＝8.686÷7.206＋2.526%×7.206－1 ＝0.387 ③该滑准关税税率计算后为38.7%，小于40%，按照实际计算的关税税率计征关税。④应征进口关税税额＝完税价格×暂定关税税率 ＝7.206×1000×38.7% ＝2788.75元 3．山东华丰食品进出口贸易有限公司从法国进口冷冻整鸡2000千克，以每千克1.95美元CIF青岛价格条件成交，买方自行向其购货代理人支付佣金200美元。经查，冷冻整鸡税目税号02071200，按从量税征收进口关税，最惠国税税率为1.30元/千克，增值税税率为13%，该商品无进口环节消费税，海关计征汇率为1美元=7.20元人民币。经海关审定以成交价格作为完税价格征收进口关税和进口环节增值税。试计算，该批冷冻整鸡应总计缴纳多少进口税费？ 解： 1）进口关税税额＝进口货物数量×从量税税率 ＝2,000千克×1.30元/千克 ＝2,600元 2）进口环节增值税税额＝进口环节增值税计税组成价格×增值税税率 ＝(进口货物完税价格＋进口关税税额)×增值税税率 ＝(2,000千克×1.95美元/千克×7.20元/美元＋2,600元)×13% ＝(3,900美元×7.20元/美元＋2,600元)×13% ＝(28,080元＋2,600元)×13% ＝30,680元×13% ＝3,988.40元 说明：买方支付的购货佣金按规定无须计入完税价格。 3)总计进口税额＝进口关税税额＋进口环节增值税税额 ＝2,600元＋3,988.40元 ＝6,588.40元 答：该批冷冻整鸡应总计缴纳进口税费6,588.40元。 4．浙江捷达汽车国际贸易有限公司从日本进口排气量为300毫升，装有往复式活塞内燃发动机摩托车10辆，以每辆3500美元CFR上海价格条件成交，由买方自行投保，支付保险费185美元。海关以成交价格并计入保险费估定该进口货物的完税价格。经查阅进口税则获知，该商品税目税号为87113010，进口关税最惠国税税率为45%，进口环节增值税税率17%，进口环节消费税税率10%，当时的计征汇率为1美元=7.50人民币元。试计算该批进口货物应征进口关税、进口环节增值税、进口环节消费税以及总计税额各多少？ 解： 1）进口关税税额＝(3,500美元×10<辆>＋185美元)×7.50元/美元×45% ＝35,185美元×7.50元/美元×45% ＝118,749.38元 进口关税完税价格进口关税税额进口环节消费税税率1进口环节消费税税率(3,50美元01辆0美元185)元7.美元50/1元18,749.3810% 110%263,887.50元118,749.38元0.10.9382,636.88元0.1425,152.09元0.142,515.21元0.92）进口环节消费税税额3）进口环节增值税税额＝(进口关税完税价格＋进口关税税额＋进口环节消费税税额) ×进口环节增值税税率 ＝(263,887.50元＋118,749.38元＋42,515.21元)×17% ＝425,152.09×0.17 ＝72,275.86元 4）总计税额＝进口关税税额＋进口环节消费税税额＋进口环节增值税税额 ＝118,749.38元＋42,515.21元＋72,275.86元 ＝233,540.45元 答：该批进口货物应征进口关税118,749.38元、进口环节增值税72,275.86元、进口环节消费税42,515.21元以及总计税额233,540.45元。 5．某贸易公司于2007年5月11日（周五）申报进口一批货物，海关于当日开出税款缴款书。其中关税税款为人民币24000元，增值税税款为人民币35100元，消费税税款为人民币18900元。该公司实际缴纳税款日期为6月7日（周四）。计算该公司应缴纳的滞纳金。 答：首先确定滞纳天数，然后再计算应缴纳的关税、进口环节消费税和增值税的滞纳金。税款缴款期限为2007年5月26日（周六），但缴纳期限的最后一日是星期 六、星期天或法定节假日，则关税缴纳期限顺延至周末或法定节假日过后的第一个工作日。即为2007年5月28日（周一）。 5月29日－6月7日为滞纳期，共滞纳10天。 按照计算公式分别计算进口关税、进口环节消费税和增值税的滞纳金。关税滞纳金＝滞纳关税税额×0.5‰×滞纳天数 ＝24 000×0.5‰×10 ＝120（元） 进口环节消费税滞纳金＝滞纳进口环节消费税税额×0.5‰×滞纳天数 ＝18900×0.5‰×10 ＝94.5（元） 进口环节增值税滞纳金＝滞纳进口环节增值税税额×0.5‰×滞纳天数 ＝35100×0.5‰×10 ＝175.5（元） 三、综合实务题 1．杭州市某中外合资企业向其合资外方在境外的母公司进口属自动许可管理的纺织机械设备10台，成交总价为每台1200美元CIF Less 3% Quantity Discount上海（即3%数量折扣价）。合同规定，折扣款在买方付款时自行扣除，若买方将该进口设备转售给其他企业，则应从获取的利润中返回10%给卖方。装载该货物的船舶于2007年12月2日申报进境，进口货物收货人于12月8日向海关申报。海关在审核完税价格时认为买卖双方存在特殊关系，不能用成交价格作为完税价格，决定采用上个月进口的与该货物型号完全相同的机械设备的成交价格每台1320美元作为完税价格。该进口货物按从价税征收进口关税，税率为10%，进口环节增值税税率为17%，海关计征汇率为1美元=7.48人民币元。 根据上述情况，请回答下列问题 （1）若进口货物收货人在（）之后向海关申报, 则海关应当加收滞报金。A 12月14日 B 12月15日 C 12月16日 D 12月17日 （2）根据我国《进出口关税条例》的规定，这批货物应按（）征收进口关税。A 一般进口货物 B 特殊进口货物 C 法定免税进口货物 D 外资设备物品（3）海关对纳税义务人所申报的价格表示怀疑，应当首先采用（）要求纳税义务人提供资料以证明其申报价格的真实性。 A 司法程序 B 仲裁程序 C 价格质疑程序 D 价格磋商程序 （4）假如该进口货物确实以“每台1200美元CIF Less 3% Discount上海价”成交，除买方向其代理人支付了360美元的购货佣金外无其他任何瓜葛。海关决定以该成交价格来估定完税价格，估价时不应计入的是（）。 A 保险费 B 购货佣金 C 海运运费 D 折扣款 （5）若海关以“相同货物成交价格法”审定完税价格，纳税义务人对该批进口货物总计应缴纳的进口税额是（）。 A 98736.00元 B 9873.60元 C 18463.63元 D 28337.23元 【解答】 (1)C(2)A(3)C(4)B(5)D 说明： 1）完税价格＝1,320美元×10(台)×7.48元/美元＝98,736.00元 2)进口关税税额＝98,736.00元×10%＝9,873.60元 3)进口环节增值税税额＝(98,736.00元＋9,873.60元)×17% ＝108,609.60元×17%＝18,463.63元 4)总计进口税额＝9,873.60元＋18,463.63元＝28,337.23元 或： 总计进口税额＝完税价格×常数＝98,736.00元×0.2870＝28,337.23元 四、请完成以下工作项目 1．广东天宇贸易有限公司从新加坡进口一批“SONY”牌彩色数字电视机，该产品采用日本牌号和商标，其中显像管为新加坡生产，集成电路板为香港生产，机壳由马来西亚生产，最后在新加坡组装成整机。经查《海关进口税则》获知，该产品最惠国税税率为30%，中国—东盟协定税率为12%，普通税率130%。 假如你是“天宇贸易有限公司”的报关员，工作任务包括： 任务一：向海关申报时，该彩色数字电视机的原产地应填报为哪个国家？ 任务二：该进口货物在申报时，应适用哪个税率？ 任务三：应如何向海关进行申报？ 【解答】 对应任务一：新加坡； 对应任务二：协定税率为12%； 对应任务三：原产地证书（要求提交原产地证书正本和第三联）、报关单、提单、装箱单、发票等。若是经过第三国，还须第三国海关的未再加工证明文件第二篇：数据结构课后习题答案总结
第三篇：《张衡传》课后习题及答案解析
第四篇：数据结构习题与答案
第五篇：报关实务课后习题及答案解析
点击咨询 