第一篇：数据结构课后习题答案总结
第一章
第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.组成数据的基本单位是（） （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.填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模 ⑻ 设待处理问题的规模为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.证券： 经济权益的凭证，证明凭证持有人有权按期以其凭证取得收益 2.证券投资分析：指人们通过各种专业性的投资方法对影响证券价值和价格进行综合分析，以判断证券价值及价格变动的行为 3.权证： 是一种有价凭证，投资者付出权利金购买后有权利而非义务，在某一特定时间或某一特定期间按约定价格向发行人购买或出售标的证券 4.金融非衍生工具： 以杠杆或信用为特征，以货币、证券、股票等传统金融工具为基础而衍生的金融工具 5.初始保证金： 买卖双方在交易之前都必须在经济公司开立专门的保证金账户，并存入一定金额的保证金 6.维持保证金：它是初始保证金的75%，当保证金账户余额低于交易所规定的维持保证金的水平时，经济公司就会通知交易者补交到初始保证金水平，否则就会强制平仓 7.远期： 双方约定在未来的某一确定时间按确定价格买卖某种数量的标的资产的合约 8.保荐人： 保荐人是一个机构，由保荐人负责对发行人的上市推荐和辅导，合适公司发行的文件和上市的文件中所载的资料是否真实、完整，协助发行人建立严格的信息纰漏制并承担风险防范责任 9.宏观经济政策：政府有意识的运用一定的工具调节控制宏观经济运行以达到政策目标 10资本化利息：指公司自有资金不足，通过外部借款自建自用固定资产或生产生产期间超过一年的大型的设备机器过程中外部借款产生的利息 11证券市场：是股票、债券、证券投资基金、金融衍生工具等各种有价证券发行和买卖的场所 第一章 股票 1、什么是股份制度？它的主要功能有哪些？ 答：股份制度亦称股份公司制度，它是指以集资入股、共享收益、共担风险为特点的企业组织制度。股份公司一般以发行股票的方式筹集股本，股票投资者依据他们所提供的生产要素份额参与公司收益分配。在股份公司中，各个股东享有的权利和义务与他们所提供的生产要素份额相对应。功能： 一、筹集社会资金； 二、改善和强化企业的经营管理。 2、什么是股票？它的主要特性是什么？ 答：股票是股份有限公司发行的，表示其股东按其持有的股份享受权益和承担义务的可转让的书面凭证。股票作为股份公司的股份证明，表示其持有者在公司的地位与权利，股票持有者为公司股东.特性：1、不可返还性 2、决策性 3、风险性 4、流动性 5、价格波动性 6、投机性 3、普通股和优先股的区别？ 答：普通股是构成股份有限公司资本基础股份，是股份公司最先发行、必须发行的股票，是公司最常见、最重要的股票，也是最常见的股票。其权利为： 1、投票表决权 2、收益分配权 3、资产分配权 4、优先认股权。对公司优先股在股份公司中对公司利润、公司清理剩余资产享有的优先分配权的股份。第一是领取股息优先。第二是分配剩余财产优先。优先股不利一面：股息率事先确定；无选举权和被选举权，无对公司决策表决权；在发放新股时，无优先认股权。 有利一面：投资者角度:收益固定，风险小于普通股，股息高于债券收益；筹资公司发行角度：股息固定不影响公司利润分配，发行优先股可以广泛的吸收资金，不影响普通股东经营管理权。 4、我国现行的股票类型有哪些？ 答：我国现行的股票按投资主体不同有国有股、法人股、公众股和外资股。 国有股是有权代表国家投资的部门或机构以国有资产向公司投资形成的股份，包括公司现有的国有资产折算的股份。 法人股是指企业法人或具有法人资格的事业单位和社会团体以其依法可支配的资产向股份有限公司非上市流通股权部分投资所形成的股份。 公众股即个人股，指社会个人或股份公司内部职工以个人合法财产投入公司形成的股份。外资股指股份公司向外国和我国香港、澳门、台湾地区投资者发行的股票。 第二章 债券 1、什么是债券？它必须具备哪三个条件？ 答：债券是发行者依法定程序发行，并约定在一定期限内还本付息的有价证券，是表明投资者与筹资者之间债权债务关系的书面债务凭证。具备以下三个条件： 1、必须可以按照同一权益和同一票面记载事项，同时向众多投资者发行； 2、必须在一定期限内偿还本金，并定期支付利息； 3、在国家金融政策允许条件下，必须能按照持券人的需要自由转让。 2、债券的基本特性？ 答： 1、权利性：利息请求权、偿还本金请求权、财产索取权、其他权利。 2、有期性 3、灵活性 4、稳定性 3、债券与股票的区别？ 答：（1）性质上，债券表示债券持有人对公司的债权，无参加经营管理的权利；股票表示对公司所有权，有参加经营管理的权利 （2）发行目的上，股票是为了筹集公司资本的需要，追加资金列入资本；债券是追加资金的需要，追加资金列入负债。 （3）获得报酬时间，债券获得报酬优先于股票。（4）投资风险上看，股票大于债券。 （5）投机角度上，债券投机性小，而股票投机性比债券要大。（6）发行单位上看，债券发行单位多余股票发行单位。（7）流通性上看，债券因为有期限，流通性要低于股票 4、债券按发行主体分类有几种？ 答：政府公债券——政府或政府代理机构为弥补预算赤字，筹集建设资金及归还旧债本息而发行的债券。金融债券——银行或其他金融机构为筹措中长期信用资金而发行的债券 企业债券——企业为筹集投资资金而发行的债券。 国际债券——各主权国家政府、信誉好的大公司以及国际机构等，在本国以外的国际金融市场上发行的债券。（欧洲债券——国外筹资人在欧洲金融市场上发行的，不以发行所在国货币，而是以另一种货币计值并还本付息的债券。） 第三章 投资基金 1、什么是投资基金？它有哪些特点？ 答：投资基金是一种利益共享、风险共担的集合证券投资方式，即通过发行投资基金单位，集中投资者的资金，由投资基金托管人托管，由投资基金管理人管理和运用的资金，从事股票、债券等金融工具投资，并将投资收益按基金投资者的投资比例进行分配的一种间接投资方式。 特点： 1、小额投资，分散风险。 2、专业性投资管理 3、成本较低，进退方便 4、收益可观 5、有利于机构投资者的内部管理。 2、投资基金同股票、债券投资工具的关系？ 答：性质上看，股票反映的是对公司的所有权；债券只是一种债权；契约型基金反映的是一种信托关系。发行目的上看，股票是股份公司筹集自己资本的需要，债券是为了追加资金的需要；投资基金是为了形成一个以分散组合投资为特色，以降低风险从而达到资产增值为目的的投资基金组织。 发行者看，股票发行者是股份公司，债券发行者是政府、金融机构、公司企业等，而投资基金的发行者是一个比较松散的组织。 从期限上看，债券的性质决定了债券在一定期限内还本付息；股票是对公司所有权的代表，无到期日；投资基金较灵活，可有期，可无期。 从风险上看，股票风险最大，投资基金次之，债券风险最低。收益与之相同。 从返还型上看，债券到期必须返本付息；股票具有不可返还性，但可在股票市场上转让；投资基金，封闭式不能赎回，但可转让；开放式可自由赎回。 投机性，债券投机性很小，股票投机性最大，投资基金介于二者之间。 3、封闭式投资基金与开放式投资基金的区别？ 答：封闭式投资基金是指投资基金资本总额及发行份数在未发行之前就已经确定下来，在发行期满后，投资基金就封闭起来，总量不在增减的投资基金，因此也称固定型投资基金。封闭性投资基金受益凭证在封闭期间内不能追加认购或赎回，但投资者可以在证券交易所市场上交易。 开放式投资基金是指投资基金的发行总额不是固定不变的，可以随时根据市场供求状况发行新的份额或被投资人赎回的投资基金。投资基金的单位总数变动，但追加购买或赎回的价格已投资基金的当时的净资产价值为基础加以确定。 区别:(1)封闭式投资基金的份额数量是固定的，其投资基金份额买卖和交换按标准费率执行；开放式投资基金的份额是不固定的，卖出或买进按净资产价值执行。 (2)封闭式投资基金在存续期内不得要求赎回，故信托资产稳定，便于投资基金管理人管理运作；开放式投资基金的单位总数是变动的，给投资基金管理人带来挑战。(3)封闭式投资基金风险大于开放式投资基金风险。 4、契约型投资基金和公司型投资基金有何区别？ 答：契约型投资基金又称信托投资基金，是根据信托法组建的，也就是委托人、受托人和受益人三方订立信托投资契约，有投资基金经理公司根据契约运用信托资产，有托管人负责保管信托资产，而投资成果则由投资者享有的一种投资基金。 公司型投资基金是按照《公司法》组建而成的投资基金，投资者购买公司股份成为股东，由股东大会选出董事、监事，再由董事、监事投票委任某一投资管理公司来管理投资公司资产。这种投资基金股份的出售一般都委任专门的承销公司进行。 区别：(1)公司型 必须由具有独立法人资格的机构发起并发行投资基金股份；契约型无需单独组成具有法人资格的机构发起投资基金，由现有的金融机构发起即可。 (2)公司型投资基金管理依据是公司章程，契约型依据是信托契约。 (3)公司型投资基金发行股票，投资者为公司股东，具有投票表决权；而契约型发行收益证券，购买收益证券持有者，只享有受益权，不具有股东资格。 第四章 衍生投资工具 1、认股权证：股票认购售权证，由上市公司发行，表明持有人具有在指定时间内以事先确定的价格购买一定数量的该公司股票的权利凭证。包括有效期限、换股比率、换股价。 2、认股权证与股票认股权的区别 普通股认股权只是认股权证的低级形式，首先单就认股权来看，它存在两个缺点：一是认股权与原有普通股股票连在一起，未分离，因此就不能在市场上流通；二是公司发行新股时一般希望在较短时间迅速筹集资金，所以认股权期限较短。而认股权证克服了上述缺点，它可以在市场上流通，并且期限长，甚至数年之久。其次优先认股权产生于公司筹集资金而向现有股东发行新股时，是对普通股的优惠权；而优先认股权证产生于公司发行优先股和债券时，是对优先股股东和债权人的优惠。再次，优先认股权的价格低于市场价格，而权证的价格高于当时的市场价格。 3、可转换按证券：指发行人以法定程序发行，持有人在一定时间内依据约定的条件可以转换成一定数量的另一类证券的证券。实际上是一种普通股票的看涨期权。 4、证券期货：是指买卖双方支付一定数量的保证金，通过证券交易所进行的以将来特定的日期作为交割日期，按照约定的价格卖出或买入一定数量的证券的交易方式。特点：(1)交易对象是有价证券的标准化合约。(2)对冲交易多，实物交易少，投机性强。 (3)采用有形市场的形式，实行保证金制度，交易安全可靠。 (4)交易者众多，交易活跃，流动性好。 5、证券期权交易又称选择权交易，相对于现货交易而言，它是一种远期交易。它指证券投资者实现支付一定费用取得一种可按既定价格买卖某种证券的权利。 与期货交易的区别：(1)期权交易对象是一种权利而非证券本身，期货交易对象是证券，只是把订约时间和履约时间隔;(2)期权的时效自动性。期权有期限，超过期限未行使权利，期权自动失效，而期货交易在时间上要求双方必须履约。(3)期权持有人可以在合同期限内任何一天执行合同，而期货交易往往规定执行的合同时间，提前延期均不可。(4)期权属于单项合同，期权买方只有权利，无义务，而卖方有义务无权利；期货合约是双向合同，双方均有权利义务。 6、证券期权的两种类型: 一、看涨期权（买入期权）指依据买卖双方签订的契约，买者在协定期内有权按照双方协定的价格向买者买进一定数量的指定证券。 二、看跌期权（卖出期权）；指依据买卖双方签订的契约，买者在协定期内有权按照双方协定的价格向卖者卖出应数量的指定证券。 7、股票指数期货：只证券交易所同期货买卖者签订买卖股票价格指数的合约，并在未来指定日期用现金办理交割的一种期货交易方式。 第五章 证券市场概述 1、什么是证券市场？其作用？ 答：证券市场是有价证券发行与流通场所及其相联系的组织与管理体系的总称。证券市场包括证券发行市场和证券流通市场。作用： 第一、是筹集资金的重要渠道；第二、是推动企业加强经营管理的重要动力；第三、是商业银行安全经营的重要保证；第四、是国家进行宏观调控的重要桥梁；第五、是传道经济信息的重要媒介；第六、是进行过紧资金融通的重要工具。 第六章 证券发行市场 1、什么是证券发行市场？ 答：又称“初级市场”或“一级市场”，指各发行主体及其中介机构发售各种证券所形成的市场，一般是无形的。 2、股票的发行目的？ 答：(1)新公司首次发行股票——设立发行；(2)老公司发行增资股票——增资发行；(3)为改善企业财务结构而发行股票；(4)为特定某种目的发行股票（转化证券；股份的分割和合并；公司兼并；公司缩股；证券交易所提高股票上市的基准） 3、影响股票发行价格的因素？ 答：净资产；经营业绩；发展潜力；发行数量；行业特点；股市状态。 4、什么是债券的信用评级？ 答：指债券评级机构对债券的发行者的信誉及其所发行的特定债券的质量进行评估的综合表述。本质上，信用评级评估和计量了信用风险，即发生不利于债权事件的可能性。 第七章 证券交易所 1、如何理解证券交易市场与发行市场的关系？ 答：证券交易市场是对已发行的证券进行转让、买卖的场所，因此也称为证券流通市场、二级市场和次级市场。证券发行市场和证券流通市场的关系： 证券发行市场体现了证券由发行主体流向投资者的市场关系，它通过一种纵向关系将证券发行者和投资者联系起来。流通市场则通过一种横向关系将同是证券投资者证券买卖双方联系起来。 从证券交易结果看，证券发行市场交易的结果是社会长期资金的增加，形成股票和债券的绝对数量的上升，众多资金通过证券买卖投入生产经营等领域。证券流通市场买卖的结果只是资金所有权和证券所有权的易位，社会长期资金的总数不会因此增加，股票、债券等虚拟资本也不能膨胀。 因此发行市场是证券市场的基础环节，没有发行市场，筹资者就无法筹集到资金，投资者也无法通过证券进行投资，也就没有交易市场。可见证券发行市场的存在是交易市场存在的前提。交易市场又是发行市场的保证。因为如果无交易市场，证券投资者的资金就无法及时变现，也不追随经济效益调整投资目标，投资者无法灵活运用资金，也就导致了人们不愿购买或持有证券，从而影响发行市场的正常运行。证券交易市场对发行市场也起着积极的推动作用。所以，二者需相互配合，协调的高效的运转，才能形成一个具有活力和稳定运转的证券市场。 2、证券交易市场的类型有哪些？ 答：证券交易所和场外交易所 证券交易所是证券交易市场中有组织、有固定地点，并能使证券集中、公开、规范交易的场所，是证券流通市场的主体和核心。特点： 1、不持有证券，不买卖证券，不能决定证券的市场价格 2、证券买卖完全公开 3、具有严格的组织性。 场外交易市场简称OTC，是证券交易所以外的证券交易市场的总称，是分散的、非组织化的市场。包括店头市场、第三市场、第四市场。 3、柜台交易市场有何特点？ 答：柜台交易市场即店头市场，指证券经纪人或证券自营商不通过证券交易所把未上市的证券，有时也包括一部分已上市的证券直接同顾客进行买卖的市场。特点： (1)设施上，没有大型证券交易所的中央市场，但个别的也有不小的规模和场面。 (2)价格形成方式上，不像证券交易所那样通过充分竞价的方式得出证券行市，店头市场只提供协议价格，即证券自营商买卖双方或客户与证券自营商之间的协商价格。 (3)价格水平上，一般按净价基础进行交易。净价支部包括佣金的价格。 4、证券上市的利与弊。答：利：(1)有利于公司扩大资金来源，筹集巨额资金，满足生产经营发展需要；(2)有利于提高股票债券的流动性，增加对投资正的吸引力，从而有利于上市公司继续向公众集资；(3)有利于提高公司的信誉和知名度；(4)形成对企业的压力，促进企业不断加强经营管理，提高经济效益和竞争力。 弊：(1)公司的约束与压力加大(2)不利于保守公司经营秘密(3)公司证券可能成为投机对象(4)股权因此更加分散(5)加大公司成本开支。 第八章 股票价格指数 股票价格指数：是用来表示多种股票的平均价格水平及其变动情况以衡量股市行情的指标，简称股价指数。 第九章 证券投资价值分析 1、影响债券价格的因素。 答：(1)利率，反方向；(2)经济发展境况，经济发展呈上升趋势，资金需求量大，利率上升，债券价格下降；(3)物价，物价上涨过快，处于保值目的投资于保值产品，债券供过于求，价格下跌；(4)中央银行公开市场业务操作，抛售债券，债券价格下跌；(5)新发债券的发行量，发行超过一定数量，会导致债券价格下跌；(6)投机操纵，价格变动剧烈(7)汇率，外汇升值，吸引投资者购买该种外汇的债券，引起价格上涨。 2、影响股票价格的因素。 答：（1）基本因素： a.经济因素（宏观、中观、微观）b.政治因素c.其他（自然灾害，经济复兴）（2）技术因素：技术因素指市场操作的因素，主要来自投机活动的结果,包括a.人为的投资操作；b.买空卖空及大户购买。（3）信用交易因素。信用交易使投机者可以通过大规模借入资金来购买股票或者借入股票作大宗卖出，从而使股价波动。（4）证券管理部门的限制规定。 第十三章 证券投资组合分析 1、证券组合的含义 答：证券组合是指个人或机构投资者同时所持有的各种有价证券的总称，它反映了投资者的意愿和所受到的约束，即投资者对投资收益的权衡、投资比例的分配、投资风险的偏好等的限制。 2、效用期望无差异曲线（风险收益无差异曲线） 答：在E(R), σ的坐标系中的一条曲线，在该曲线上任意一点所对应的证券组合都能产生相等的效用期望值，即对具有相应偏好的投资者而言，这条曲线上任意一点所代表的证券组合都是无差异的，因为他们都能产生相等的效用期望值。（画图） 3、系统性风险和非系统性风险。 答：证券投资风险指投资收益的不确定性，实际收益与预期收益的差异性。 证券的风险可划分为系统风险和非系统风险。系统性风险指因各种因素影响整个市场发生波动而造成的风险，政治的、经济的以及社会环境的变化是系统风险的来源。这类风险与所有证券都存在系统性联系，利率风险、市场风险和购买力风险就属于系统性风险。 非系统性风险指因个别证券发行公司和特殊状况造成的风险，这类风险通常与整个股市状况不发生系统性联系，企业经营风险、财务风险、流动性风险以及违约风险属于非系统性风险。由于非系统性风险强调对某一种证券的影响，说明该风险具有相互抵消可能，所以这类风险可以通过证券组合的方法消除。 4、有效组合：构建证券时，投资者谋求的是在他们愿意接受的风险水平既定的条件下是投资预期收益最大化，满足这一要求的证券组合极为有效组合。 5、马柯维茨对投资者的资产选择行为的基本假设 （1）投资者都规避风险；（2）投资者追求效用最大化；（3）投资者仅根据均值、方差、协方差选择最佳投资组合；（4）投资期为一年；（5）资金全部用于投资，答不允许卖空；（6）证券见相关系数都不是-1，不存在无风险证券，而且至少有两个证券的预期收益不同。 6、马柯维茨的有效边界。 在多个证券构成的可行集是标准差—期望收益率坐标系中一个弹头型平面区域，根据偏好收益与厌恶风险的假设，集合左边界BERF为最小方差边界，即在相同期望收益条件下，投资风险的最低资产的组合组成的曲线，而BE段为无效边界，因为在这一段，期望收益越高，风险越低，投资者只会选择E点。而ERF为效率边界，它包括全部有效资产组合，即相同风险情况下期望收益最大，或者相同期望收益相同情况下风险最低。 7、给定若干个有效组合供投资者选择，投资者最乐意选择的证券组合即为最优组合。 第十四章 资本资产定价模型 1、CAMP（资本资产定价模型）假设条件。答：除马柯维茨证券组合模型假设之外,还有： 假设1：所有的投资者都依据期望收益率评价证券组合收益水平，依据方差评价证券组合的风险水平，并采用期望效用无差异曲线和有效组合边界来选择最优证券组合。 假设2：所有投资者对证券的期望收益率、标准差及证券间的相关性具有完全相同的预期。假设3：证券是完美无缺的，无摩擦。摩擦即对整个市场上的资本和信息自由流通的阻碍。 2、资本市场线 由无风险证券Rf出发向右上方引出一条与原有风险证券组合可行区域相切的一条射线RfMT，是新的效率边界变成一条直线—RfMT，在这条直线上，风险既定的条件下，期望收益最大，或者期望收益一定，风险最小，这条直线称之为资本市场线，它是无风险资产与市场证券组合的有效组合。 资本市场线方程：E(Rp)=Rf+(Rm-Rf)* σp/σm E(Ri)有效组合p的期望收益率，σp有效组合p的标准差，Rm市场组合M的期望收益率，σm市场组合M的标准差，Rf无风险证券收益率 市场组合：市场组合是每一个愿意承担风险的投资者必须持有的唯一的风险资产，是独立于投资者效用函数的最佳组合，它包括市场中每一种风险证券每种证券在市场组合中的比例就是该证券的市场价值占全部证券市场价值的比例。 3、分离定理（分割定理） 投资者的投资决策包括两个相互独立的决策： （1）对风险资产进行选择：估计每一项风险资产的期望、方差以及相互作用程度（协方差），确定风险资产组合及其效率边界。随后，投资者由无风险证券Rf引出一条与效率边界相切的射线，切点即为投资者应当持有市场组合。 （2）最终资产的选择。由于引出之射线为新的有效边界，投资者可根据自己的风险偏好在该射线上选择市场组合与无风险证券的组合，即安排市场组合和无风险证券各自的比例。 4、证券市场线。 无论是单个证券还是证券组合，均可将其β系数作为风险的合理测定，其期望收益与β系数测定的系统风险之间存在着线性关系，这个关系在以E(Rp)为纵坐标、β作为横坐标的坐标系中代表一条直线，这条直线被称为证券市场线。 证券市场线方程（CAPM）：E（Rp）=Rf+（Rm-Rf）*βp βp为证券组合p或证券p的β系数。 5、资本市场线与证券市场线的关系。 答：第一、资本市场线便是无风险资产与有效率的风险资产在组合后的有效资产组合期望收益与总风险之间的关系，因此在资本市场线上的点就是有效组合；而证券市场线表明的是任何一种单个资产或组合的期望收益与其系统风险β之间的关系，因此在证券市场线上的点未必在资本市场线上。第二、在均衡条件下，所有证券都落在证券市场线上。 第三、资本市场线是证券市场线的一个特例，当一个证券或一个证券组合是有效率的时候，该证券或证券组合与市场组合的相关系数等于1，此时二者相同。 6、证券特征线 答：公式E（Rp）=Rf+（Rm-Rf）*βp改写成E（Rp）—Rf =（Rm-Rf）*βp 此式被称为特征线，以（Rm-Rf）为横坐标，E（Rp）—Rf为纵坐标，表示某一证券的超额收益与市场组合的超额收益与该证券的系统风险存在严格的函数关系。 第十五章 证券市场效率与绩效评价 1、证券市场效率指一个证券市场如果在确定资产价格中能够使用所获得的全部信息，它（从信息上）就是有效率的。即，能够有效地利用金融信息的证券市场被称为有效性市场。 2、内在效率：指证券市场的交易营运效率，即证券市场能否在最短的时间最低的交易费用为交易者完成一笔交易，它反映证券市场的组织功能和服务功能的效率。 外在效率：指证券市场的资金配置效率，及市场上证券的价格是否能够根据有关的信息作出及时、快速的反应，它反映了证券市场调节和分配资金的效率。 3、弱型效率市场：股价变动的历史不包括任何对预测股价未来变动有用的信息。在此情况下，证券的现行价格反映的是有关过去价格和过去收益的一切信息。 半强型效率市场：证券市场上，价格会迅速、准确的根据可获得的所有公开信息进行调整，因此以往的价格和成交量等技术信息及公布的基本信息无助于分析家挑选价格被高估或低估的股票。 强型效率市场：不仅已公布的信息，而且是可能获得的所有有关信息都以反映在股价中，因此任何信息包括“内幕信息”对专业分析毫无用处。通常情况下，任何投资者都无法凭借其地位和某种信息渠道来获得超额收益。 第一章 绪论”习题答案 “绪论”思考和练习一 一、什么是现代汉民族共同语?它是怎样形成的? 现代汉民族的共同语就是“以北京语音为标准音，以北方话为基础方言，以典范的现代白话文著作为语法规范的普通话”。 现代汉民族共同语是在北方方言基础上形成的。在形成的过程中，北京话占有特殊的地位。早在唐代，北京已是北方军事要镇。北京是辽、金、元、明、清各代的都城。近千年来，北京一直是我国政治、经济、文化的中心，北京话的影响越来越大。一方面，它作为官府的通用语言传播到了全国各地，发展成为“官话”，另一方面，白话文学作品更多地接受了北京话的影响。 本世纪初，特别是“五四”运动以后，掀起了“白话文运动”，动摇了文言文的统治地位；另一方面，“国语运动”的开展促使北京语音成为全民族共同语的标准音。两个运动互相推动和影响，这就使得书面语和口语接近起来，形成了现代汉民族共同语。 二、共同语和方言的关系是怎样的? 方言是一种民族语言的地方分支或变体，是局部地区的人们所使用的语言。一民族语言的共同语，则是通用于这个民族全体成员的语言。对于各地方言来说，规范化的共同语是民族语言的高级形式，它比任何方言都富有表现力。共同语形成后，对于方言的语音、词汇、语法都有一定的影响。它的词语经常传播到各方言中去。规范化的共同语，往往促使地域方言向它靠拢，对方言的发展起一种制约的作用。与此同时，共同语也要从方言中吸收种种语言成分，以丰富和发展自己。但是，地域方言间差异的缩小，以至于消失，则须经过一个长期而复杂的过程。 “第二章 语音”习题答案 “语音”思考和练习一 四、语音具有物理属性、生理属性、社会属性。“语音”思考和练习二 二、普通话声母的发音部位和发音方法各包括哪几种?请画成一个总表把声母填上。 普通话声母的发音部位包括双唇、唇齿、舌尖前、舌尖中、舌尖后、舌面、舌根七种。发音方法，从阻碍的方式看，包括塞音、擦音、塞擦音、鼻音、边音五种；从声带是否颤动看，包括清音、浊音两种；从气流的强弱看，包括送气音、不送气音两种。声母总表（略）。 三、根据所提供的发音部位和发音方法，在下面横杠上填上相应的声母。 1．双唇送气清塞音是p。 2．舌尖后清擦音是sh。 3．舌尖中浊边音是l。 4．舌尖后浊擦音是r。 5．舌面不送气清塞擦音是j。 四、根据所提供的声母，写出它的发音部位和发音方法。1．k：舌根、送气、清、塞音 2．ch：舌尖后、送气、清、塞擦音 3.n：舌尖中、浊、鼻音 4.x：舌面、清、擦音 5．z：舌尖前、不送气、清、塞擦音 五、试把下列字音的声母写出来 京(j)沪(h)津(j)吉(j)黑(h)晋(j)蒙(m)鲁(l)苏(s)皖(w)闽(m)赣(g)鄂(e)湘(x)粤(y)琼(q)陕(sh)甘(g)青(q)新(x)川(ch)滇(d)黔(q)台(t) 七、有些方言区的人对声母n、?的发音有困难，就把下列词语的音读混了：女客——旅客，男衣——蓝衣，年代——连带。试问应该采取什么方法去分辨? 有些汉语方言区的人，把普通话声母n、?的字音读混了。有的全部相混，有的局部相混。要读准n、?的发音和分清普通话声母为n、?的字的读音，关键在于控制软腭的升降。因为n、?，都是舌尖抵住上齿龈发音的，它们的不同是n为音，发音时软腭下降为边音，发音时软腭上升。如果捏住鼻孔，气流振动声带后无法从鼻孔通出，感到发音有困难，那就是n。如果捏住鼻孔，气流振动声带后从舌头两边或一边通出，并不感到发音有困难，那就是?。至于哪些字声母是n，哪些字声母是?，一般可采取汉字声旁类推的办法。例如声旁是“内”的字，声母往往是n(如纳、呐、钠、讷等)；声旁是“仑”的字，声母往往是?(如沦、伦、抡、轮等)。如果要记住声母n、?的全部常用字，那就可利用<常用同韵字表)采取记少不记多的办法分别记忆。 八、有些方言区的人对声母zh、ch、sh、和z、c、s分辨不清，下列词语的读音相混：战歌——赞歌，木柴——木材，诗人——私人。试简述分辨zh、ch、sh和z、c、s的方法。 这两组声母中的zh、ch、z、c都是清塞擦音，其中zh、z不送气，ch、c送气；sh、s都是清擦音。有些汉语方言区的人对zh、ch、sh和z、c、s的发音感到难以分辨，主要是分不清前一组是舌尖后音声母，后一组是舌尖前音声母。根据它们的主要差别有针对性地进行练习，就能较快地掌握它们的发音。发舌尖后音时，舌尖要翘起来，对准(抵住或接近)硬腭前部；发舌尖前音时，舌尖不翘，要对准(抵住或接近)上齿背。 九、试从发音部位和发音方法两方面分辨下列各组声母的异同。 1、g——k同：舌根、清、塞音。异：前者不送气，后者送气。 2、f——h同：清、擦音。 异：前者是唇齿音，后者是舌根音。 3、zh——z同：不送气、清、塞擦音。异：前者是舌尖后音，后者是舌尖前音 4、b——p同：双唇、清、塞音’ 异：前者不送气，后者送气。 5、m——n同：浊、鼻音。 异：前者是双唇音，后者是舌尖中音。6．q——c 同：送气、清、塞擦音。 异：前者是舌面音，后者是舌尖前音。 十、：写出并读准下面《太平歌)每个字的声母，并按发音部位重新排列。 子夜久难明，喜报东方亮。 此日笙歌颂太平，众口齐欢唱。 先读写歌中每个字的声母，然后排成下表：（略） “语音”思考和练习三 三、分别按韵头、韵尾分类，韵母各可分成哪些类? 按韵母开头的元音发音口形分，韵母可分成开口呼、齐齿呼、合口呼、撮口呼四类，简称四呼。 开口呼 韵母不是i、u、ü或不以i、u、ü起头的韵母”。 齐齿呼 i或以i起头的韵母。 合口呼 u或以u起头的韵母。 撮口呼 ü或以ü起头的韵母。 按韵尾分，韵母可分为无韵尾韵母；元音韵尾韵母，即有元音i、u(o)作韵尾的韵母；鼻音韵尾韵母，即有鼻音n、ng作韵尾的韵母。 四、举例说明单元音的发音应从哪几方面进行分析。 普通话的单韵母共有十个，即a、o、e、ê、i、u、ü，它们都是单元音构成的。前七个是舌面元音，接着的两个是舌尖元音，末一个是卷舌元音。舌面元音的发音应从下列三个方面分析： (1)舌位的高低 舌位的高低指舌头隆起部位的高低，同开口度的大小有关。开口度大的，舌位较低，是低元音；开口度小的，舌位较高，是高元音；其间还可以适当划分为半高元音和半低元音。 (2)舌位的前后 舌位的前后指舌头隆起部位的前后。舌位在前的，是前元音；舌位在后的，是后元音；舌位不前不后的，是央元音。 (3)圆唇不圆唇 唇形拢圆的，是圆唇元音；唇形平展的，是不圆唇元音。 另外，舌尖元音、卷舌元音的发音分析如下： 是舌尖前元音、发音时舌尖前伸接近上齿背，不圆唇。 是舌尖后元音，发音时舌尖上翘接近硬腭前部，不圆唇。 er是央元音，口形略开，舌位居中，不圆唇。在发e[?]的同时，舌头向硬腭卷起，就形成er。 五、根据所提供的发音条件，在括号内写出相应的单韵母。1．舌面、前、高、圆唇元音(ü)2．舌面、后、半高、不圆唇元音(e)3．舌面、后、高、圆唇元音(u)4．舌面、前、半低、不圆唇元音(ê)5．舌面、后、半高、圆唇元音(o)6．舌尖、前、高、不圆唇元音 7．舌面、央、低、不圆唇元音(a) 六、将下列单韵母的发音条件写出来。1．舌面、央、低、不圆唇元音。2．舌尖、后、高、不圆唇元音。3．舌面、后、高、圆唇元音。4．卷舌、央、中、不圆唇元音。5．舌尖、前、高、不圆唇元音。6．舌面、央、中、不圆唇元音。 八、有些方言区的人对韵母en、eng，in、ing。的发音有困难，常常区别不搞，把下列词语的音读混了：分化——风化，地震——地政，禁止——静止，不信——不幸。试问应该采取什么方法分辨。 方言区的人对韵母en、eng，in、ing分辨不清的情况，大致有两种。一种是都念成前鼻音尾韵母en、in，另一种是都念成后鼻音尾韵母eng、ing。不管是哪一种情况，问题都出在对鼻音n、ng的发音要领掌握不好，掌握不住。因此，学习时应从区别n、ng的发音入手加以改正。n是舌尖鼻音，发音时要把舌尖抵住上齿龈；ng是舌根鼻音，发音时要把舌根抵住软腭。理解和掌握这些发音要领，认真比照复习，就容易将上述两类词语区分开来了。属于前一种情况的，着重练习ng的发音；属于后一种情况的，着重练习n的发音。 九、有些方言区的人对韵母i、ü的发音分辨不清，下列词语读音相混：里程——旅程，移民——渔民，饥民——居民，拟人——女人。试说明分辨i、ü发音的方法。 方言区的人对韵母i、ü分辨不清，主要是没有发圆唇元ü的习惯，往往把ü或以ü开头的韵母读成i或以i开头的了。这两类韵母的主要区别在于i是不圆唇音，ü是圆唇音。对ü或以ü开头的韵母，在发音时注意把唇拢圆，经常练习，逐步养成习惯。 十、韵母调查例字：用国际音标写出下列汉字的普通话韵母，然后整理出一个韵母表来。同时按一种方言的读音用国际音标标音，然后整理出一个方言韵母表。注意比较两者的异同。（略） “语音”思考和练习七 一、举例说明什么是音位。 音位是依据语音的社会属性划分出来的语音单位，指的是一个语音系统中能够区别意义的最小语音单位，也是按语音的辨义作用归纳出来的音类。 例如在普通话里[a][A][a]属一类，是一个音位，即在实际说话的时候，不管你发的是哪个。都没有区别词义的作用，比如把“他”[t‘A]念成[t‘a]或[t ‘a]，意思不变。相反地，[n]和[1]属两个音位，甲为在任何一个音节中，如果把[n]换成[1]，或把[n]换成[n]，都表示不同的意思。当然，这指的是普通话。若是在某些汉语方言(如福州话)里则[n]和[1]属一个音位。 二、举例说明应怎样归纳音位。 音位是以语音的辨义功能、互补分布和音感差异为标准归纳出来的，而辨义功能是最重要的标准。把一些不同的音素放在相同的语音环境中来替换比龟看它们是否能区别意义，凡是能够区别意义的音，就分别归纳成不同的音位，否则就是伺一个音位了。例如，在普通话里(爸)和(怕)韵母和声调都完全相同，但意思不同，这是因为这两个音节的声母不同，两个声母不能互相替换，也就是说b和p在相同的语音环境中能区别意义，应归纳为两个音位。其他两个归纳音位的标准见下题。 三、什么是互补分布?什么是音感特征?二者作为归纳音位的语音标准来看，哪个更重要，为什么? 互补分布指的是音位不同条件的变体各有自己的分布条件，绝不出现在相同的位置上，它们的分布状况是互相补充的。所谓音感特征指的是当地人对某些音在听感上的差异。就这两个归纳音位的标准来看，一般地说互补分布是更重要的，音感特征可作为参考，当然，也应尽可能地照顾。 四、什么是音位变体? 一个音位往往包含一些不同的音，这些音就叫做音位的变体。音位跟音位变体的关系是类别同成员的关系，也可以说音位变体是音位的具体表现形式。例如，普通话里的／a／(音位)，当它处在n前的时候读[a](如“安”[an])，处在n。前的时候读(o)(如“昂’，[a?])，单用时读[A](如“啊”[A]”。因此我们说[a][a][A]都是／o／的变体。 五、条件变体和自由变体的区别何在? 凡是在一定条件下出现的音位变体就叫作“条件变体”，凡是无条件的，即不受环境的限制，可以自由替换而不影响意义的音位变体叫作“自由变体”。例如普通话里的[a][A] [a]是／o／的条件变体，因为它们的出现是有条件的。在零声母合口呼的音节中，可以把开头的音自由地念成[w]或[?]而不影响意义，所以[w]和[?]是／w／的两个自由变体。“文字”思考和练习一 三、为什么说汉字是表意体系的文字? 世界上的文字可分为表音文字和表意文字两大类。表音文字是用数目不多的符号表示一种语言的有限的音位或音节，作为标记词语声音的字母；表意文字是用数目众多的表意符号表示一种语言中有意义的语言单位——语素或词，而不是表示语言中的音位或音节。汉字用笔画构成的大量表意符号(字)来表示汉语的语素，从而代表了汉语语素的声音，而不是用符号或字母表示汉语的音位或音节，所以说汉字是表意体系的文字。(举例略)“文字”思考和练习三 一、什么是笔画?它有哪些类型?确定笔画数的依据是什么? 笔画是构成汉字的各种点和线，是构成汉字的最小单位。现行汉字有五种基本笔画，即一(横)、丨(竖)、√(撇)、、(点)、┐（折）。其中前四种是单一笔画，后一种是复合笔画。复合笔画又可以分成撇类、点类、提类、折类、钩类、弯类等6类25种。确定笔画数的依据是国家语言文字工作委员会和中华人民共和国新闻出版署1988年发布的《现代汉语通用字表》。 三、具体说明下列各字综合运用哪些笔画组合方式构成的。鸣灼疗灿兮：相离、相接两种方式 佳甸改冈：相离、相接、相交三种方式 四、什么是偏旁?它有哪些类型? 偏旁是构成合体字的基本单位，它是由笔画构成的。根据不同的标准，偏旁可区分为不同的类型。1．成字偏旁如“岩、界、盆”中的“山、石、田、介、分、皿”等。不成字偏旁如“字、煮、剔”中的“宀、、、、、、刂”等。2．按能否再切分成小的偏旁划分，可分为单一偏旁和复合偏旁两类。单一偏旁如“切”中的“ 七、刀”。复合偏旁如“胡”中的“古”，还可以再切分成“ 十、口”。3．按偏旁切分出的先后划分，可以分成一级偏旁、二级偏旁等。如“湖”，第一次切分出的“氵”和“胡”，是一级偏旁；第二次把“胡”切分出的“古”和“月”，是二级偏旁；第三次把“古”切分出的“十”和“口”，是三级偏旁。 八、古代的“六书”是什么? 古代的“六书”指古人总结的古文字的六种造字法，一般指象形、指事、会意、形声、转注、假借。现在一般认为，前四种是造字法，后两种是用字法。 十二、下列古文字各是用什么造字法造的?从现行汉字看，哪些还能看出原来的造字法? “虫、衣、水、爪、宀、贝”的古文字是用象形造字法造的，“出”的古文字是用指事造字法造的，“见、囚”的古文字是用会意造字法造的。从现行汉字看，“爪”和“囚”还能勉强看出原来的造字法。 十三、下列用“丁”作声旁的形声字，它们的字义同形旁有什么联系?试给每个字注音，看哪些字同声旁的读音不完全相同。 疔ding：疗疮。意义同表示疾病的形旁“广chuáng"有联系。 玎ding：玎玲，玉石撞击声。意义同形旁“I(玉)”有联系。 叮ding：叮嘱，叮问，叮了一口。意义同形旁“口”有联系。 仃ding：伶仃，孤独。意义同形旁“亻”(人)有联系。 盯ding：集中视力看。意义同形旁“目”有联系。 钉一ding：钉子。意义同形旁“韦”(金)有联系。ding：把钉(ding)子钉(ding)上。意义同形旁“韦”(金)也有一些联系。 耵ding：耵聍，耳屎。意义同形旁“耳”有联系。 酊ding：医药上用酒精和药配制成的液剂。意义同表示酒义的形旁“酉”(甲骨文像酒瓶)有联系。②ding：酩酊，大醉。意义同形旁“酉”有联系。 轩ding：补鞋底。意义同形旁“革”有联系。 顶ding：头顶。意义同表示头义的形旁“页”有联系。 订ding：订立。意义同形旁“喜(言)”有联系订。 汀ding：水边平地，小洲。意义同形旁“f(水)”有联系。 厅ting：客厅、餐厅。意义同可住人的山崖义的形旁“厂”(hǎn)有联系。亭ting：亭子，从高省，丁声。(说文解字)：“亭有楼。”意义同形旁“高”有联系。 灯ding：灯火。意义同形旁“火”有联系。 打dǎ：打击。意义同形旁“f”(手)有联系。 “疔、玎、叮、仃、盯、耵、轩”和“钉、酊”的第一个读音同声旁“丁”(ding)读音完全相同；其余字的读音同“丁”不完全相同。 十四、分析下列各组同声旁异形旁的形声字，看它们的字义同形旁有什么联系。 1．赌、睹：赌博，意义同表示钱财的形旁“贝”有联系。睹，看见，意义同形旁“目”有联系。 2．瞠、膛：瞠，瞪着眼，意义同形旁“目”有联系。膛，胸膛，体腔，意义同形旁“月”(肉)有联系。 3．胳、赂：胳，胳膊，意义同形旁“月”(肉)有联系。赂，贿赂，意义同表钱财的形旁“贝”有联系。 4．恳、垦：恳，真诚，意义同表心理活动的形旁“心”有联系。垦，用力翻土，意义同形旁“土”有联系。 5．炕、坑：炕，用土坯砌成的、底下可烧火的、供睡觉取暖用的长方台，意义同形旁“火”有联系。坑，泥坑，坑道，意义同“土”有联系。6．苔、笞：苔，隐花植物的一种，意义同形旁“仆”有联系。笞目竹板或鞭、杖打，意义同形旁“竹”有联系。“文字”思考和练习五 一、举例说明什么是错别字，什么是不规范字。 错字，指写得不成字。如把“染’写成“染”。别字，指把甲字写成乙字。如把“欣赏”写成“欣尝”。广义的错字也包括别字，因为别字也是错的。 不规范字，指写得不符合国家规定的规范写法的字。错别字都是不规范宁。另外，已简化的繁体字，如“声’’的繁体“聱”；已整理废除的异体字，如“布”的异体叫布”；已废除的旧印刷体字，如“吕”的旧印刷体“吕”；已废除的“简”字，如“赛”的“简”写法“宙”。这些字如果随便运用，也是不规范字。 二、下列简化字和简化偏旁，哪些可作偏旁类推?试举出例字来。（略） 三、下面哪些字不是规范字? “偿、丽、场、临、丝、厢、争、换、绳、赊”是规范汉字。 五、用下列各组每个偏旁造成几个字。（略） 七、改正下面词语中的别字、错字、不规范的字，并加以说明，痊癔：应作“痊愈”，指病好了。“癔’’是已淘汰的异体字。 传染：应作“传染”。“染”是错字。“染”是从水(氵)、从木、从九的会意字。 牍糊：应作“模糊”。“牍”是错字，因受“糊”的影响而写错。 宽澜：应作“宽阔”。“阔”，从门活声。“澜”是错字。 无条件：应作“无条件”。(“无”是“燕”的简化字。“无”读几指嗝气，用在这里是别字。“条”，7画，上部不是“欠”。桥根：应作“桥梁”。“根”是已淘汰的异体字。 泡制：应作“炮制”，指用烘炒等方法把原料加工制成中药。 “炮”，páo。，烧。“泡”，pào或pāo，指泡沫、像泡的东西等，音义和“炮”不同。 粉粹：应作“粉碎”，指破碎得像粉末。粹cuì，纯粹、精粹，与“碎”音义不同。 迫不急待：应作“迫不及待”，指急迫得不能再等待。不及，来不及，不能；不能用“急”。 情不自尽：应作“情不自禁”，指控制不了自己的感情。禁，抑制。“情不自禁”不能用“尽”。 原形必露：应作“原形毕露”，指本来面目完全暴露了。毕，完全；不能用“必”。 披星带月：应作“披星戴月”，形容早出晚归，辛勤劳动。戴月，头上顶着月亮；不能用“带”。 破斧沉舟：应作“破釜沉舟”，指把锅打破，把船弄沉，比喻下决心干到底。(见(史记?项羽本纪))釜fǔ，古代的一种锅；不同于卜“斧”。 负偶顽抗：应作“负隅顽抗”，指(敌人或盗贼)依靠险要的地势抵抗。隅yú，同yú，山势弯曲险要的地方；不同于“偶ǒu”。 僳俱：应作“家具”，指家庭用具。“惊”在这里是“家”的异体字，以用“家”为宜。俱心全、都义，用在这里是别字。 按排：应作“安排”，指有条理、分先后地处理(事物)，安置(人员)；也指规划、改造。“安”读6n，“按”读6n，二者音义都不同。 竟竟业业：应作“兢兢业业”，指小心谨慎，认真负责。“兢”读jīng “竟”读jìng，二者音义都不同。第四章 词汇 “词汇”思考和练习一 三、用“替代法”证明“驼绒”是两个语素，“骆驼”是一个语素。“驼绒”中的“驼”跟“绒”都可为已知语素所代替，也可跟已知合，如：（1）驼绒 平绒 呢绒 鸭绒（2）驼绒 驼毛 驼峰 驼铃 (1)组说明“驼”被“平、呢、鸭”替换，“绒”可跟上述语素组合，(2)组说明可以被“毛、峰、铃”替换；所以“驼”、“绒”是两个语素。“驼绒中”的“驼”不能被替换，也就是说“骆”不能跟任何其他语素组合，它不具备语素的资格。由于语言中同一层次的单位才能组合，语素不能跟非语素组合，所以在这里“驼”也不是语素，“骆驼”只能算一个语素。 四、分别指出下列字中的自由语素、半自由语素、不自由语素单独作语素的字。 柿 素 眉 蜻 狗 羊 鸭 习鹃 祝 闪平虎 狼 自由语素：狗、羊、学、祝、闪、平、狼 半自由语素：绩、柿、素、眉、虎、鸭、习没有不自由语素。 不能单独作语素的字：蜻、鹃 五、划分出下文中的词(在词下划一横线，成语不划，不分析)。如果是合成词就注明它的构成方式。（略） 六、指出下列的双声词、叠韵词、音译词。 仓促 灿烂 沙发 孑孓 恍惚 婆娑 铿锵 扑克 涤纶 秋千 踟蹰 拮据 婀娜 腼腆 双声词：仓促 孑孓 恍惚 秋千 踟蹰 拮据 叠韵词：灿烂 婆娑 腼腆 音译词：沙发 扑克 涤纶’ 七、指出下列复合式合成词的类型。 痛快 认真 抓紧 房间 革命 飞快 解剖 石林 开关 领袖 工人 碰壁 戳穿 司令 雪崩 动静 无论 烧饼 粉饰 体验 奶牛 牛奶 功用 用功 (一)联合型：人民 解剖 开关 领袖 美好 丝毫 伟大 动静 衣服 功用(二)偏正型：痛快 飞快 石林 雪白 工人 烧饼 粉饰(三)补充型：抓紧 房间 照明 戳穿 (四)动宾型：认真 革命 碰壁 司令 无论 用功(五)主谓型：雪崩 体验 八、试举出yi音的五个同音语素，用每个语素各造三个合成词，同时注明其结构类型 (一)一 一定(偏正)一律(偏正)统一(补充) (二)衣 衣服(联合)大衣(偏正)衣领(偏正) (三)依 依靠(联合)依赖(联合)依然(附加) (四)医 医院(偏正)医术(偏正)医疗(联合) (五)揖 揖让(联合)作揖(动宾)拜揖(联合) 十、下面句子里加着重点的词中间也插进了其他成分，你认为对吗? ①为了完成全年计划，昨天厂里又动了一次员。 ②老头儿注了几次射，才退烧。 ③我向领导汇过报了。 “动员、注射、汇报”都不是离合词，它们结合很紧 进其他成分。惯用的形式是： 1．又动员了一次 又一次动员了 2．注射了几次 3．汇报过了 “词汇”思考和练习二 六、理性义与色彩义有什么区别? 理性义又叫概念义，在指明词所表示的事物的范围时，理性义起主要作用，它是实词词义中不可缺少的主要部分，主要靠它表示相应的概念。 色彩义是在理性义的基础上附加上去的一些意义要素。色彩义往往是人们在交际过程中产生的，所以与使用者的感情，使用场合(语境)、使用者的形象感以及词的来源(来源于古代书面语、现代方言、某种社会集团等)有关，它们不是每个词所必须具备的因素。一个词可以没有色彩义，也可以有两种以上的色彩义，但不能没有理性义。 七、指出下列各词的色彩义：(一)感***彩： 1．褒义：康复 2．贬义：倒爷 搅和 轻蔑 欺凌 癞皮狗 ***镜 3．中性的：鸭绿江 调试 车流 出台 脑袋 疙瘩(二)语体色彩： 1．书面语：康复 轻蔑 欺凌 车流 囹圄 鸟瞰 演奏 2．口语：倒爷 哥们儿 搅和 癞皮狗 发毛’***镜 脑袋 疙瘩(三)形象色彩：葡萄胎 鸭绿江 癞皮狗 哈蟆镜 车流 出台 鸟瞰(四)术语、行业语色彩：葡萄胎 演奏 调试 康复 出台(五)地域方言色彩：搅和(六)时代色彩：囹圄(古语词) 八、固定短语也可能有各种色彩义，试指出下列各短语的色彩 龙腾虎跃 三长两短 唇红齿白 打游击 打牙祭 炒鱿鱼 举世瞩目 蝇营狗月 龙腾虎跃：褒义、形象 打牙祭：口语、方言 三长两短：中性、口语 炒鱿鱼：口语、方言、形象 唇红齿白：褒义、形象 举世瞩目：褒义、书面语 打游击：中性、口语 蝇营狗苟：贬义、书面语、形象 九、下列带点的词的色彩义有无变化? 真是地方 什么东西 瞧那长相 有派头 硬了点儿 有点讲究 (批评)还尖锐 (批评)太尖锐 “地方、派头、讲究”由中性变成褒义。 “东西、长相”由中性变成贬义。 “硬了点儿”说明“硬”得过格了，含贬义。 “批评还尖锐”，认为“尖锐”得合适，应该尖锐，“尖锐”含褒义；“批评太尖锐”，认为“尖锐”得过火了，含贬义。“词汇”思考和练习三 一、下列词中哪些是单义词? 单义词有：懂 煤 瞟 溅 风 苗条 发火 雨 缎子 剥 杜绝 二、1．种子植物的有性生殖器官：掐，了一朵花。 2．供观赏的植物：买了一盆花。 3．颜色错杂：这布太花了点儿。 4．用掉：花了三元钱。 5．姓：小李广花荣。6．模糊不清：眼睛花了。 于同一个词的各个义项必须有意义上的联系——引申或比据这个标准，1、2、3、6各义项应属同一个词：“花l”，4应属词另一个词：“花2”，5应屑“花3”。“花1”“花2”“花3”是三个不同的词，虽然字形与读音都相同。 五、“论”有下列义项，但是有的义项能作为词的意义，有的只能作为语素的意义，你能分辨吗?谈谈你分辨它们的标准，并探讨一下词典中有无区别的必要。 ①分析和说明事理：议论丨就事论事丨要论起这件事 ②分析和说明事理的话或文章：社论丨***。③学说：唯物论。 ④说，看待：相提并论丨不能一概而论 ⑤衡量；评定：论罪丨***行赏。***。 ⑥按照某种单位或类别说：论天计酬丨买鸡蛋论斤还是论个儿? ⑦姓。 作为词的义项，必须是能够单说或单用的，如题中例句所显示的，1、4、5、6、7各个义项都属这类。当然作为词的义项还可以作为语素的义项用于造词。 2、3两义项只是“论”作为语素构词时才有的，因此，只是“论”这个语素的义项。 分清词的义项和语素的义项与分清词和语素的意义是类似的。只有词的义项才能作为独立运用的词：的内容参与造句，而屑于不能成词的语素的义项则只起构词作用，所以应该分清，词典中最好能加以区别。 六、同形同音词和一词多义，有时很难区分。试用下列各词，分别造几个句子来说明哪些是同音词，哪些是多义词。 新生 杜鹃 疙瘩 苦 区分同形同音词和一词多义，主要看义项之间有无联系。新生： 1．新生事物是不可战胜的。(刚产生的或刚出现的。)2．是党给予我新生。(新生命) 3．中文系招了一百余名新生。(新入学的学生)杜鹃： 1．远处飞来了一只杜鹃。(鸟名)2．满山的杜鹃都绽开了新蕾。(花名)疙瘩： 1．脸上长满了疙瘩，挺难看。(皮肤上突起的硬结)2．面粉受潮结成了疙瘩。(块状或球状物)3．一天只吃了一小疙瘩馒头。(量词)苦： 1、黄连虽苦但能治病。(一种与甜相反的味道) 2、生活苦一点，没什么，不能没了志气。(难受、痛苦) 3、这些年全仗她支撑门户，可真苦了她了。(使难受、使痛苦) 例1、2的“新生”意义有联系，属于一个词，是一词中的两个义项。例3的“新生”是另一个词，与例1、2的“新生”形成同形同音词。两个“杜鹃”意义间没有联系，各是一词，形成同形同音词。“疙瘩”、“苦”中的各例说明它们都具有两个以上互有联系的义项，是多义词。 七、什么是义素?义素分析有什么用处? 义素是词义构成的最小意义单位，也就是词义的区别特征。 义素分析随着语义学的兴起愈来愈受到人们的重视。义素分析可以帮助我们准确地掌握、解释、理解词义，可以突出地显示词义之间的异同及联系，可以突出词义聚合时的相同点和区别点，可以考察词义组合时的正误。义素分析便于形式化，有利于运用电子计算机处理语言信息。 九、试就下面一组词进行义素分析： 伯伯 叔叔 姑姑 伯伯 十[父系血亲]+[长辈]+[男性]+[长于父] 叔叔 +[父系血亲]+[长辈]+[男性]—[长于父] 姑姑 +[父系血亲]+[长辈]—[男性]±[长于父] “词汇”思考和练习四 四、什么是同义词?怎样辨析同义词? 意义相同或相近的词组成的语义场叫做同义义场，同一义场中的各个词叫做同义词。 辨析同义词最重要的方法是从语境中去考察，考察它们可能出现的上下文语境，设想相互替换的可能性。一般来说，可能替换的总是显示出同义词中相同的部分，不能替换的往往是差异所在。为此，首先要尽可能多地搜集包含有关同义词的句子或短语，然后进行归类，看看能用哪些义项进行解释。第二步便是互相替换，对种种替换情况进行分析、概括、说明，找出它们的差异可能在哪些方面。(如教材上册288页附表所列) 七、指出下列各词的反义词。它们属于什么类型的反义词? 和善 分散 脆弱 冷落 低落 淡季 通俗 浑浊 积累 赞同 拘泥 丑恶 富裕平坦 吝啬 节约 和善——凶恶 [极性] 分散——集中 [互补] 脆弱——坚强 [极性] 冷落——热闹 [极性] 低落——高涨 [极性] 淡季——旺季 [极性] 通俗——艰深 [极性] 浑浊——清澈 [极性] 积累——消耗(消费)[互补] 赞同——反对 [互补] 拘泥——变通(灵活)[互补] 丑恶——美好 [极性] 富裕——贫困 [极性]平坦——崎岖 [极性] 吝啬——慷慨(大方)[极性] 节约——浪费 [互补] 九、什么是反义词的不平衡现象?试以“重——轻”、“团结——***”为例加以说明。一般说”王安忆是女作家”，却只说“梁晓声是作家”，形成“作家——女作家”的对立，这也是不平衡现象吗? 成对的两个反义词之间的语义范围、使用频率往往不相等，这就是反义词的不平衡现象。例如“重——轻”，一般提问题时问“重不重?”如“这杠铃重不重?”回答可以是“重，180kg”，也可以是“轻，才120kg”。一般情况下不问“轻不轻?”只是在已知为轻时或希望它为轻时，才问“这杠铃轻不轻?”回答只能是“轻，120kg”，不能说“重，180kg。”但可回答说“不轻，180kg”。一般只能问“有多重?”只在已知为轻时说“有多轻?”但陈述句只说“有180kg重。”“有120kg重。”不能说“有120kg轻”。 “团结——***”也如此。一般情况下(不知是否***)只问“他们团结不?”“他们团结的情况如何?”“他们有多团结?”一般不问“他们***不?”只有在已知为***时，才问“他们***的情况如何?” “作家—女作家”的对立也是不平衡的。“作家”可以特指男性作家，所以一般只说“梁晓声是作家”，除非强调性别时，不说“梁晓声是男作家”。“作家”还可以兼指女作家。如果说：“来了一群作家。”其中可以有男的也可以有女的；如果说：“来了一群女作家。”其中便只能有女作家，不能包括男的。当然说“王安忆是作家”也是可以的。 十、下边句子里都有用词不够妥当的地方，试指出来加以改正，并说明理由。①他那双沾满红丝的眼睛说明他又为革命熬了一个通宵。 “沾满”改为“布满”。“红丝”不是从外面附着在眼睛上的，不能用“沾满”。 ②1936年10月19日，鲁迅先生——伟大的革命家、文学家的心脏跳动停顿了，但是他的声音，他的思想，却没有停顿。年轻一代接过他的笔，继续在革命的大道上前进。 “停顿”均改为“停止”。人死了，心脏不能再跳动起来了，不能用“停顿”，“停顿”含有可能再起动的意思。 ③大家决心继续发挥艰苦朴素的作风，努力攻克困难，争夺更大的成就。 “发挥”改为“发扬”，“攻克”改为“克服”，“争夺”改为“争取”。这样一改，动词和宾语就搭配得拢了。? ④运动员踏着强健的脚步，举着五彩缤纷的旗帜，穿过了检阅台。 “踏着”改为“迈着”，“强健”改为“矫健”，“脚步”改为“步伐”。改后，动词和宾语，定语和中心词都搭配得拢了。“穿过”改为“走过”，因为事实上并不是从检阅台穿过，而是从台前走过。 ⑤大家对王同志的批评正确而尖刻。 “尖刻”改为“尖锐”。“尖刻”是贬义词，对同志的正确批评不能说是“尖刻”的。 ⑥今年，市场上西瓜供应充沛。 “充沛”改为“充足”。这样一改，与“供应”就搭配得拢了。 ⑦敌机驾驶员非常机警，往云端里一钻仓皇地逃走了。 “机警”是个褒义词，不能用来描写敌人，应改为“狡猾”或“胆怯”。 ⑧每个革命者都元例外地期望把自己的工作搞好。“期望”改为“希望”。“希望”可以用于对人或对己，但“期望” 只能用于对人。又，“期望”一般用于上级(或长辈)对下级(或晚辈)。 ⑨两国经过协商，已达成了协议，双方军队各自撤回自己的边疆。 “边疆”指靠近国界的领土，范围大，这里指靠近边界的地方，应改为“边境”。 ⑩他总爱表现自己，不顾场所，大谈自己的见闻，惹得人们看不起他。 “场所”只指活动的处所，“场合”则表示时间、地点、气氛等的综合情况，“不顾场所”应改为“不分场合”。 ⑩我们必须彻底揭发反革命两面派的所有言行。 “所有言行”应改为“种种罪行”，因为“反革命两面派”的“所有言行”不一定都有罪、都应该揭发。、⑩边防战士虽然在天寒地冻的北国边陲，但仍日夜在国 境线上巡视着。 “巡视”是到各处视察的意思，“巡逻”则是军事术语，表示巡查警戒的意思，“巡视”应改“巡逻”。 ⑩在我校评职称会上，有人故意大闹会场，说职称评得不公道，一下子把会场的程序打乱了。 “公道”指公正的道理，不公道着重指不合道理，“公平”着重指处理事情不偏不倚，不偏袒任何一方，这里的“公道”应改“公平”。 “程序”只指事情进行的先后顺序，“秩序”指有条理不混乱，会场本身无所谓程序，打乱的应是“秩序”。 ⑩一位老农说，今年的早稻，经过精心培育，长势颇佳。 “精心培育”，“长势颇佳”这类话。书面语色彩很浓，不适用于口语，更不像目前我国老农所能说的话。应改为口语色彩的词语。“词汇”思考和练习八 二、词义发展变化有哪几种原因?其发展变化的途径有哪几种? 词义发展变化的原因有下列三种： (一)词所标志的事物、现象本身发生了变化，从而引起了词义的变化。例如： “车”，从指“两轮中贯以轴，轴上承舆以任载’’的以马为动力的陆上交通运输工具，发展到指“以电、汽油等为动力”的电车、火车、汽车等等。“车”的基本义指“陆上的交通运输工具”，虽没有变化，但内涵却丰富多了。 (二)由于科学技术的进步，人们对事物认识的提高，引起了词义的深化。如： “云”，《说文解字》说是“山川气”，合乎科学的说法应是“由水滴、冰晶聚集形成的在空中悬浮的物体”(《现代汉语词典》)。 (三)人们循着事物之间的相似性、相关点把词用来指与原义有某种联系的新事物、新认识，从而引起了词义项的增加或减少。如： “铁流”，由“流动的铁水”去指称“战斗力强的队伍”。“皮毛”，由“带毛的兽皮的总称”，去指称“表面的知识”。 词义变化的途径有下列三种： (一)扩大旧词所概括的对象范围，即词义的扩大。如： “残年”，由指称“一年将尽的时候”扩大到指“人的晚年”。 “老巢”，由指“鸟的老窝”扩大到指“匪徒、团伙盘踞的地方”。 (二)缩小旧词所概括的对象范围，即词义的缩小。如： “小说”，由指“街谈巷议之类的异闻、琐记等等”，缩小指“文学作品的一种体裁”。 “报复”原指报答恩和怨(《三国志?蜀?法正传》：“一冶之德，睚眦之怨，无不报复”)，现缩小为“报怨”，对批评自己或损害自己利益的人进行反击。 (三)把表示甲类对象的词转用于指称与之有关的乙类对象，即词义的转移。如： “布告”，原为动词，是宣布、公告之意(《史记?吕太后纪》：“事已布告诸侯。”)，现转移指机关团体张贴出来通告大众的文件，是公文的一种。 “明目张胆”，由“无所畏避”的褒义，转移为“公开大胆地做坏事”的贬义。 三、解释下列各词的意义，指出它们的意义是怎样变化的。 1．“本钱” ①用来营利、生息、赌博的钱财。②比喻可以凭借的资历、能力。——用比喻方法扩大词所指对象的范围。 2．“走狗” ①************。②受人豢养的助人作恶的爪牙。——用比喻的方法扩大词所指对象的范围。 3．“讲究” ①讲求、重视。②精美(由于讲求、重视而使之出现的好结果)。③(儿)值得注意或推敲的内容(如“有讲究儿”)。——用 第五章 语法 “语法”思考和练习二 八、改正下列句子中的错误，并说明理由。 ①一位干过多年售票工作的老人很兴趣地凑上前说：“真了不起，我要向你学习!” “兴趣”是名词，不能受程度副词“很”的修饰，不能作状语，这是把名词误用为形容词了。可以把“兴趣”改为“高兴”或者在“兴趣”前加一个“有”字。 ②在工厂、农村、学校我见闻了许多英雄，他们都在自己的岗位上，为实现四个现代化而忘我地工作着。 原句中名词“见闻”被误用为动词，应当改为“看到”之类的动词。 ③小梅干活很卖力气，咱队的大人小孩没有一个不说她 劳动不积极。 原句中“没有一个不说”即“大家都说”，后面再加上一个否定副词“不”来否定“积极”，意思就正好和原意相反了。应去掉最后一个“不”字。 ④这个炼钢车间，由十天开一炉，变为五天开一炉，时间缩短一倍。 数量的减少不能用倍数表示，只能用分数表示。“一倍”应改为“百分之五十”“二分之一”或“一半”。 ⑤他家在村子的南边，面对着一幢小山。 量词“幢”常用于楼房，“山”应用“座”表示。 ⑥王师傅对我们讲，他12岁上得了一场病，是李大夫把我从死亡线上抢救了过来。本句中“他”“我”都是指代“王师傅”的，前后所用人称代词不一致。“我”应改为“他”。“语法”思考和练习三 三、下面各组句子中加着重号的词在词性上、作用上有没有不同?为什么?（略） 四、在下面句子里的空格处填上适当的结构助词，并说明理由。 ①问题彻底——解决了。 “彻底解决”是动词性偏正短语作谓语，“彻底”是状语，应填“地”。 ②彻底——解决问题是不容易的。 主语是动词短语，动词“解决”前的附加成分是状语 “地”。 ③问题解决——不彻底。 “解决”是中心语，“不彻底”是补语，应填“得”。 ④问题还没有得到彻底——解决。 “解决”是宾语中心，“彻底”是定语，应填“的”。 五、下面两组里结构相似的句子意思是否相同? ①我在北京住了三年。 ②我在北京住了三年了。 ①表示现在已不在北京住。②表示现在还在北京住着 ③我只同他说过。 ④我同他只说过这个问题。 ③表示“只同他说过”，没有同别人说过。④表示“只说过这个问题”，没有说过别的问题。 六、“我跟他去过”这句话可以有不同的理解。请分别加上适当的词把不同的意思都固定下来，并说明各个意思中“跟”的词性。 ①我跟他都去过。(“跟”是连词) ②我曾经跟他去过。(“跟”是介词)③我跟着他去过。(“跟”是动词) 七、改正下列病句，并说明理由。 ①今年又是一个丰收年，粮食产量超过去年的12．5％。“超过去年的12．5％”等于说比去年粮食产量的12．5％多，实际上还投有去年生产的粮食多，那就不是丰收年了。应将“的”去掉，使“12．5％”成为超过量。 ②这个山区的变化，对于我们都是非常了解的。 本句犯了主客颠倒的毛病。是我们了解山区的变化，不是山区变化了解我们。应将“对于”移到句首，或在“我们”后边加上“来说”二字，让“对于我们来说”成为独立语。 ③在改善学生生活上，我们学校采取了一些措施。 在“在……上”中应该是名词性短语，而“改善学生生活”是动词性短语。改法有二：一是将“上”改为“方面”，一是在“生活”后边加上“的问题”。 ④窗前有一个小菜园，种有苋菜、豆角、黄瓜和许多种蔬菜。 此句犯了种概念和类概念并列的毛病，“苋莱”“豆角”和“黄瓜”各是蔬菜的一种，不能与“蔬菜”并列。应将“和”改为“等”或在“许多种”前加上“其他”二字。 ⑤本校职工或学生出入校门要凭工作证和学生证。 “和”表示加合性并列，“或”表示选择性并列。职工只能凭工作证，学生只能凭学生证。因此，“和”应改为“或”。 ⑥我代表学校向新同学表示热烈地祝贺。 “祝贺”为宾语中心语，“热烈”是其定语，因此应将“地”改为“的”。 ⑦他深知过华人进入美国一旦触犯美国法规，除文化背景语言不通外，再加上财力不足，打起官司来必败无疑。 “深知”属于动作不强的动词，不能带“过”。 ⑧即使做超级明星的目标达不到，高级的业余爱好，也可比一般人拥有了较充实的人生。“拥有”本身含有动作已实现的意思，不必加“了”。“语法”思考和练习四 四、指出下面句子中定语的短语结构类和功能类 攀登高峰——动宾，动词性 金色秋天——偏正，名词性 友谊园里——方位短语，名词性 理想王国——偏正，名词性 获得甜果——动宾，动词性 秉公办事——偏正，动词性 健康长寿——联合，形容词性 身体内部——偏正，名词性 时代洪流——偏正，名词性 前进路上——偏正短语，名词性 走向深渊——中补，动词性 五、指出下列短语的基本类型，用从大到小和从小到大的层次分析法分析每个短语的层次和结构关系。（略）“语法”思考和练习五 二、指出下面句子的主语和谓语，并说明用哪类词语充当。 ①提高整个中华民族的科学文化水平，II是亿万人民群众的切身事业。(动宾，II动宾) ②现状和习惯，II往往束缚人的头脑。(联合，II偏正) ③一年，III三百六十多天。(量词短语，II量词短语)④康熙皇帝，II对当时西方传教士所带来的一切欧洲学术，几乎都发生兴趣。(同位II偏正)⑤当年红军二方面军长征渡金沙江时总指挥贺龙写的一封信II已经在云南丽江纳西族自治县发现。(偏正II偏正) ⑥越王勾践，II囚服独自坐在石室里。(同位II偏正) ⑦用历史著作《三国志》去对比文学著作《三国演义》，II未尝不是有益的事。(偏正)II(偏正) ⑧几乎大多数历史事件和历史人物，II史学界的评价还莫衷一是。(偏正)II(主谓) 三、指出下面句子的宾语和补语。 ①阳光火一般地喷<下来>，我热得<气都喘不过来>。 ②他的话说<到我的心坎里>了。 ③这批汉代简册的发现，具有I(极其重要)的意义。(竖线右边是宾语，浪线上是宾语中心) ④这些见解道<出>了I(古代东方学术精神和希腊科学精神)的(深刻)差别。 ⑤树上掉<下>I(一个)苹果<来>。 ⑥老雷找<到>了I(他)的同学，安顿<好>了I住处。⑦我们走<进>了I(昨天还是威风凛凛)的大门。⑧这时已经是I(下午)三点多钟了。 ⑨我们左右张望了<一下>，想I从左边长廊走出去。⑩一条船可以坐I五十人。⑩身体不好，先在家看<几天>I病。 ⑩考得<上>，是I(你)的福气；考<不上>，也省得落I你的埋怨。 六、指出下面句子的定语、状语是用什么词语充当的。 ①他拿来(一件)(崭新)的(白色)(府绸)衬衫。(量词短语?形容词?名词?名词) ②国家保护(公民)的(合法收入、储蓄、房屋和其它生活资料)的所有权。(名词?联合短语) ③(我们)的国家进入了(新)的(历史)时期。(代词?形词?名词) ④这是(一件)(刚买来)的(呢子)大衣。(量词短语?偏正短语?名词) ⑤他[用胳膊][轻轻]地触着我，眼睛[却][然][在][出神]地望着外面。(介词短语?形容词?副词?副词?副词?形容词) ⑥宏儿听得这话，[便]来招水生，水生[却][松松爽爽] [同他][一路]出去。(副词?副词?形容词?介词短语?副词) 七、定语是说明性质、领属、数量等等的，试指出下面句子里每个定语所表示的意义类别以及是描写性的还是限制性的。 ①(我们)的祖国多么壮丽!(事物的领有者／限制性) ②(昨天)的报纸有(个)(好)消息。(时间?数量?性状／限制性?限制性?描写性) ③(西湖)的风景非常美。(处所／限制性) ④前面是(一片)(绿油油)的田野。(数量?性状／限制性?描写性) ⑤他是(一个)(勇敢)的人。(数量?性状／限制性?描写性) ⑥(四个)战士都来了。(数量／限制性) ⑦(铜)茶壶放在桌子上。(质料／限制性) ⑧(那件)衣服已经晒干了。(指量／限制性) 八、下面句子里的状语，哪些既可以放在主语后，又可以移到主语前?哪些只适宜于放在主语前?哪些不能放在主语前? ①在敌国，在暴君的掌握之中，我也不怕不惊。状语“在敌国，在暴君的掌握之中”分别表处所、范围，可以移到主语后。只是状语比较长，而要突出状语所表达的意思，最好放在句首。 ②早在十六七世纪之交，西方的一些自然科学知识已经 传播到中国。状语“早在十六七世纪之交”表时间，可以移到主语后。状语“已经”也是表时间的，不过这个副词只能用在动词前，不能移到主语前。 ③根据一些地方的调查，五十年代，从事农业生产的劳力约占95％以上。 句中有两个状语，每一个都有可能移到主语后，但是这一句的状语较长，为了句子结构的紧凑，状语不宜移动。 ④几百年来，很多人都没有解决这个问题。状语“几百年来”表时间，不能移到主语后。一移动，意思就变了，变成主语下艮多人”用几百年的时间去做某事，而人是活不了几百年的。 ⑤一会儿，瘦李一阵风似地飘进来。状语“一会儿”指一件事以后，过了很短时间又出现另一件事，它不能移到主语后，否则变成表主语在很短时间内做了一事又做一事，意思不同。 ⑥今天回国的难道是三个被俘的士兵!状语“难道”表加强谓语部分的反问语气；可以移到主语前，这时加强整句的反问语气。 ⑦李记饭馆的买卖像春雷滚过的青草地蓬蓬勃勃。 状语“像春雷滚过的青草地”是比喻，一般用在谓语中心前面，因为要出现在比喻本体的后头，不宜移到主语前。 ⑧这地方本来就低洼。 状语“本来”表时间，可以用在主语前。 ⑨你不妨对他直说。 这一句有三个状语，“不妨”表示可以怎样做，“对他”是引出动作的对象，“直”表示动作方式，都只宜用在动词前，不宜用在主语前。 ⑩我从年轻时就希望有个强大的中国。状语“从年轻时”表时间，可以放到主语前。 九、指出下面句子里的独立语的类别和结构。指出结构上哪一类的词和短语。 ①哎呀!漏水了，怎么办?(感叹语，表惊讶、突兀／叹 ②同义词，例如“看”和“瞅”，都是在意义上有细微差的。(插入语，用于举例／动宾短语) ③你想想，这难道不是事实吗?(插入语，引起注意／主短语) ④看来不会下雨了。(插入语，表示推测／中补短语)． ⑤车，不用说，当然是头等的。(插入语，表肯定或强偏正短语) ⑥这个礼堂，充其量只能容纳一千人。(插入语，表推2动宾短语) ⑦小张，快点来。(称呼语，引起注意／名词)? ⑧听说你昨天来过三次。(插入语，表示话语的来源仕 他人／动词)“语法”思考和练习六 一、指出下列句子的类型(句型：主谓句和非主谓句及其小类)： ①窗下一幅繁华的街景。(主谓句，名词谓语句)②他给我们以武器。(主谓句，动词谓语句，不是双宾句) ③有一头张牙舞爪的大熊隐藏在野树林子里。(非主谓 句，动词谓语句，兼语句) ④这种野鸭子，我一次能捕获二三个只。(主谓句，主谓谓语句) ⑤你们应该把情况汇报上去。(主谓句，动词谓语句，把字句) ⑥大家故意不给他水喝。(主谓句，动词谓语句，兼语句) ⑦勤劳让你有钱花。(主谓句，动词谓语句，兼语句) ⑧部长同志，请你转告师长，我是一名八路军战士，不是你的客人。(非主谓句，动词性非主谓句，兼语句，双宾句) ⑨你把那杯茶端给我喝。(主谓句，动词谓语句，兼语句) ⑩从南口经居庸关到八达岭，尽是崇山峻岭。(主谓句，动词谓语句) ⑾他们在渺无人烟的野草丛林间披荆斩棘种下果木。(主谓句，动词谓语句，连谓句) ⑿大厅里弥漫着一种森严气氛。(主谓句，动词谓语句，存现句) ⒀施工之前，我就主张把图纸改一条线，加两条线。(主 谓句，动词谓语句) ⒁多少年来，那捆他用生命换来的教科书和指导员没说 完的话，一直激励着我前进。(主谓句，动词谓语句，兼语句) ⒂别忘了带雨伞。(非主谓句，动词性非主谓句) ⒃我，你还信不过吗?(主谓句；主谓谓语句) ⒄当心油漆!(非主谓句；动词性非主谓句) ⒅伍子胥过昭关一夜白了头，大概不是假的。(主谓句，动词谓语句) ⒆我在学校门口看小学生匆匆忙忙回家吃饭。(主谓句，动词谓语句) 二、试指出下列句子属哪一句类。如果是疑问句，要指出小类名；如果有语气词，还要指出它的意义。 ①面对这一派太好形势，我们能无动于衷吗?(疑问句，反诘问句，“吗”表示疑问[是非问]语气)②给他两块钱上街买冰棍儿吃。(祈使句) ③有什么事儿瞒着我呢?(疑问句，特指问句，“呢”表示疑问语气) ④这儿还有一张漫画哪!真不好看!(感叹句，“哪”表感叹语气，增加感***彩) ⑤你来取呢，还是我送去呢?(疑问句，选择问句，“呢”在这句里表示疑问语气) ⑥他的事您到底还管不管吧?(疑问句，正反问句，“吧”表疑问，带有催促对方回答的口气) ⑦快往屋里搬东西吧!(祈使句，“吧”表示商量、请求) ⑧得罪了谁都不成，这年头。(陈述句) ⑨他难道会说这种糊涂话吗?(疑问句，反诘问句，“吗” 表示疑问语气) ⑩他不会说这种糊涂话的。(陈述句，气) ⑥当心上小李的当。(祈使句)的”表示确定语 三、把下列句子变换为别的格式的句子。 ①小伙子们嗓子喊哑了。——小伙子们的嗓子喊哑了。——小伙子们喊哑了嗓子。——小伙子们把嗓子喊哑了。 ②谁都能估价出诚实和忠厚的分量。——谁都能把诚实 和忠厚的分量估价出来。——诚实和忠厚的分量，谁都能估价出来。——谁不能估价出诚实和忠厚的分量呢? ③你认识刚才进去的那个人?——刚才进去的那个人，你认识? ④我耳边响起了一个宏亮的声音。——一个宏亮的声音 在我耳边响起了。 ⑤万绿丛中闪耀着赭红色屋顶和鹅***屋顶。——赭红 色屋顶和鹅***屋顶在万绿丛中闪耀着。——赭红色屋顶和 鹅***屋顶闪耀在万绿丛中。 白墙上挂着横幅。——横幅在墙上挂着。——横幅挂在 墙上。——横幅被挂在墙上。——把横幅挂在墙上。 ⑦战火把这个村的树木烧尽了。——战火烧尽了这个村 的树木。——这个村的树木被战火烧尽了。 ⑧我把纸糊了窗户了。——纸，我糊了窗户了。——纸 让我糊了窗户了。 四、指出下面各句的句型，并分析句子成分。(附加成分内部可以不分析)(略) 五、指出下列句子的错误并加以改正。是方言的句子宴指出何处不合和为什么不合普通话语法。 ①眼看离考试没几天了，恨不得不吃饭，不睡觉，把二十四小时都扑在学习上。 介词“把”介引的成分应是谓语中心动词“扑”的受事，但“二十四小时”不能成为“扑”支配、关涉的对象，应将“扑”改为“用”。 ②大家先把这个问题考虑以后抽时间研究。 “把”字句的谓语中心一般不能是孤零零的动词，“考虑”后应加补语“一下”，或者把“考虑”重叠起来。 ③我们不应指责别人而辩护自己。 “辩护”是不及物动词，后面不带受事宾语。应把“辩护自己”改成“为自己辩护”。“而”字可删。 ④不坚固的房子被地震倒塌了。 “被”字句的谓语中心要求是及物动词。句中“倒塌”是不及物动词，不能支配“不坚固的房子”，“倒塌”应改为“震塌”。 ⑤这时，高蓓的心脏跳动被停止了，血液循环的总枢纽被阻断了。 “高蓓的心脏跳动”不是被动者(受事)，本句头一个“被”字应删去。 ⑥老雷在旧社会受尽了剥削和压迫，剥夺了上学读书的权利，直到解放后才识几个字。 “剥夺”前应添个“被”字，构成被动句，否则就成了老雷剥夺自己上学读书的权利了。 ⑦作者把要求改正文章中某些错误的信件，没有寄给编辑部，而寄给某同志。 在否定式“把”字句里，否定词应该放在“把”字前而不能放在“把”字后，因此句中的“没有”应该移到“把”字前。此外，“把”字短语后头的逗号应该删去。还有，这一句是叙述已经实现的事情，第二个“寄给”后头应该加助词“了”。 ⑧加强精神文明建设，提高全民族的文化素质和法制观念，已成为当务之急。 “观念”是观察事物的结果，不能说“提高”，同时“文化素质”里也应包含“法制观念”，二者不能并列，应该删去“和法制观念”，要保留“法制观念”就要把“和”改为“包括”或“特别是”。 ⑨你有收到我的信吗? 或：你有没有收到我的信? “你有收到我的信(吗)?”是方言说法，去掉动词前的“有”字才合普通话语法。“你有没有收到我的信”也是方言说法，把动词前加的“有没有”去掉，或同时在句末加上“了没有”才是普通话说法。但是动词前加“有没有”表示疑问的格式，已见于某些书面语，有被逐渐吸收到普通话里的趋势。 ⑩这个人高过那个人。或：这个人强似那个人。 “这个人高过那个人。”是方言说法，它相当于普通话的“这个人比那个人高”。应把形容词后的“过那个人”改为“比那个人”并且移到形容词前头做状语。“这个人强似那个人”改法同前句。 ⑩你讲少两句好不好? 或：你讲先。 “你讲少两句好不好”和“你讲先”是方言说法，应把“讲”后头的“少”“先”移到动词前头。 ⑩你去学校不(唔)去? “你去学校不(唔)去?”是方言的正反问句，普通话中一般应说i成“你去不去学校?”或“你去学校不?” ⑩我给(畀、拨)一本书你。 “我给(畀、拨)一本书你”是方言的双宾句；普通话应说成“我：给你一本书”。‘指人的宾语“你”，应放在指物宾语“一本书”的前头。“语法”思考和练习七 三、下列句子有没有成分搭配不当的毛病?如果有，试加以改正，并说明理由。 ①张钰所以这般刻苦，是因为一种坚强的思想在支配她。定语“坚强”与中心语“思想”不搭配，可改为“坚定的思想”。②参加这次运动会的八名男运动员和三名女运动员，均由优秀选手组成。主语和谓语搭配不当，可把谓语改作“都是优秀选手”。 ③我们不但盖出了林立的工厂、学校、住宅，而且-盖出了人民大会堂和历史博物馆这样宏伟浩大的工程。 第二分句动语和宾语搭配不当。可把“盖出……工程”改作“建成了工程巨大的宏伟的人民大会堂和历史博物馆”。第一分句的定语“林立”应改为“许多”。 ④这次在工厂最后一天的劳动，是同学们最紧张、最愉快、最有意义的一天。 主语和宾语搭配不当。“……劳动”不能是“……一天”，“是”前可改为“在工厂劳动的最后一天”，或把第二个“一天”删去； ⑤老王是机修王，老李是装配工，本来各有任务。这次为了搞技术革新，他们协作了一台打包机。 “协作……打包机”，动语和宾语搭配不当，可把“协作”改作“协作制造”。 ⑥他奋然而起，挪开床，刨着泥土，汗水湿透了里外衣衫。 几层用厚塑料布严密包裹着的小铁箱终于出现了。 第二句的“几层”语序安排不当。可移到“厚塑料布”之前，也可移到“包裹”之后，并删去“着”字。 ⑦敌人已经发现我们了，这里不能久住，今晚六点出发瓦窑堡。 “出发”是不及物动词，不能带“瓦窑堡”做宾语，可把“出发瓦窑堡”改作“向瓦窑堡进发”，或“去瓦窑堡”。 ⑧气焰嚣张、不可一世的德国法西斯，在人民的铁拳下终于灰飞烟灭，成为人类历史上的一场噩梦。 主语“德国法西斯”与宾语“噩梦”搭配不当。“成为……噩梦”一句可删去，其前的逗号改作句号。 四、试分析比较一下下面三种说法，看看其中有没有病句，能不能都“合法”存在。 ①在党的培养教育下，使我提高了思想觉悟。 ②在党的培养教育下，我提高了思想觉悟。 ③党的培养教育，使我提高了思想觉悟。 后两句都是合乎规范的。对于句①，有人认为“使”前是个介词短语，句子的主语残缺，是个病句；也有人认为这个句子可以看作是承前省略主语，或看作“使”前有意会主语，这类句子在典范的现代白话文著作中大量存在，可以视为“合法”。 五、下列句子有没有成分残缺或多余的毛病?如果有，试加以改正，并说明理由。①英雄的可歌可泣的壮举，猛烈地拨动着观众的心弦，在极度的激动中受到了深刻的阶级教育。 第二分句缺主语。考虑到第一分句中出现了“观众”，可在第二分句前加“使他们”。 ②通过多年的生产劳动和技术革命活动中，使我深刻地认识到，一个人的智慧是有限的，群众的智慧是无穷的，我们劳动人民有无穷无尽的智慧和力量。 介词“通过’’和方位词“中”不搭配，使句子缺主语。可删去“通过’’和“中”，让“多年……活动”做主语；也可以把“通过”改成“在”，或者删去“中”，让主语承前省略。③伟大的思想家鲁迅在《祝福》中的祥林嫂是受封建礼教***的千百万妇女中的一个。“祥林嫂”的定语里缺动词，可在“中”后加“描写”“塑造”之类 ④贺兰县委接到文件后，立即在县委扩大会议上进行了传达，一致认为，中央的文件说出了广大农民和干部的心里话。 第二分句缺主语，“一致”前应加“会议”做主语。 ⑤大热天劳动，出汗多，身体里的水分和盐分消耗得也多，不随时补充上去，容易发生中暑。“发生”多余，可删去。 ⑥科学工作者认为，目前在国内具有如此独特的适于猴 类种群自然繁衍的生态环境，是不多的。 “具有”后的宾语缺中心语，应在“如此独特”后加“条件”二字； ⑦几乎从来没有听过列宁唱消沉、忧郁的歌，他的歌声永远充满着勇敢、无畏、激昂和号召力。 “几乎”多余，可删去。而且，“几乎”跟“从来”相矛盾。 六、下面句子有什么毛病?指出来并加以改正。 ①从他身上，我们看到了许***的地下工作者的光辉形象。 “许多”语序安排不当，可移到领属性定语“党的”之后，以免产生歧义。 ②两个感叹句，仿佛使我们’看到郭老写这段文字时那种心情舒畅、信心满怀的喜悦心情。“郭老的心情”怎能“看到”?动宾不搭配。“心情舒畅”“信心满怀”也不能做“喜悦心情”的定语，意思重复。可把“喜悦心情”改作“神情”，“仿佛”也应移到“我们”之后。③不仅这样，他们还把小岛建成花园一样美丽。 “把小岛建成花园一样美丽”，是把两种结构套在了一起，可改作“把小岛建成美丽的花园”，或改作“把小岛建设得花园一样美丽”。④考试场设在一间古色的大厅里举行的。 这句也是两种结构杂糅。可改成“考场设在一间古色古香的大厅里”。或改成“考试在一间古色古香的大厅里进行。” ⑤学生通过大量课外读物的阅读和浏览，通过语文课中学过的知识在大量的课外书籍、报刊中的反复出现，使学生对已学过的知识得以巩固。 “通过大量的课外读物的阅读和浏览”，是主语“学生”的行动，而“通过……反复出现”并不是“学生”的行动。这个句子应作较大的改动：“学生通过……阅览，巩固了已经学过的知识，因为他们所学过的知识是反复出现在这些课外读物和刊物里的。” ⑥红萍具有繁殖快、肥效高的特点，但在生产上长期采用季节性稻底养萍，潜力没有充分发挥。 “采用”与“稻底养萍”搭配不当。可在“养萍”后加上“的方法”三字，或改“采用”为“利用”。另外，“发挥”之后也以加“出来”做补语为好。 ⑦我们姐妹蜷缩在地板上，合盖一床薄薄的被子，冻得发抖，只好用相互的身子暖和着对方。“相互”是副词，不宜做”身子”的定语，可把“相互”移于“暖和”前做状语。此外，“对方”应删去。 ⑧只有弄清30年来教育战线上的是非得失，认识教育规律，才能改革教育适应四个现代化的要求。 第二分句因残缺成分而使两个结构杂糅在一起，可改成“才能改革教育，使之适应四个现代化的要求”。 ⑨他每天踏着一辆三轮车，从徐家汇到宝山县，从西郊到浦东，把230多家医院、照相馆、出版社等单位的废定影液一点一滴地收集起来。 本句有歧义。可以把“230多家”改为“230多个”，并移于“出版社等”之后。 “语法”思考和练习八 一、下列各句哪是单句，哪是一重复句，哪是多重复句，哪是紧缩复句?为什么? ①外面太阳很好，I也没有风。 并列一重复句。有两个分句，中间有停顿。②作者在这篇小说里，主要是写一个农民。 单句。“作者”是主语，“在这篇小说里写一个农民”是谓语“主要是”是插入语。③只要你能工作，I就应当工作。 条件 一重复句。有两个分句，中间有停顿。④只有这样，I我们才能完成任务。 条件 一重复句。有两个分句，中间有停顿 ⑤无论谁，都不能不学习。 单句。“无论”用在主语“谁”前，同谓语中的“都”配合，强调所指的人毫无例外，主谓中间有停顿。 ⑥你跑得再快也追不上他。 紧缩句。“你跑得再快”和“追不上他”都是分句，中间没有停顿，后一分句的主语承前一分句的主语“你”省略。 ⑦为了祖国的繁荣昌盛，我们要努力工作。 单句。介词短语“为了祖国的繁荣昌盛”是“我们要努力工作”的状语，把它放在主语“我们”前面是为了强调它。 ⑧那两边，你瞧，绿油油的一***，I都是新法栽种的好庄稼。 并列 一重复句。“你瞧”是插入语，“那两边绿油油的一***”和“都是新法栽种的好庄稼”都是分句，第二个分句的主语承前省略了。 ⑨每个人都把准备好的锄头扛在肩膀上，I爬上山去。 顺承 一重复句。后一个分句承前省略了主语。 ⑩分析能力强，是这位青年同志的优点。单句。主谓短语“分析能力强”是主语，主谓之间有停顿。⑩只有在特殊情况下，才可以改变咱们的计划。 单句。“在特殊情况下”是介词短语作状语，“只有”“才”分别用在状语和中心语之前表示必要条件。 ⑩鲁迅是中国文化革命的主将，I他不但是伟大的文学 并列 家II，而且是伟大的思想家和伟大的革命家。递进 多重复句。由三个分句组成，有两个层次。第一分句与第二第三分句之间是第一个层次，第二分句与第三分句之间是第二个层次。 这是多重复句。四个分句间有两层关系，前三个与后一个之间有转折关系，前三个分句之间有并列关系，是二重复句。第三分句是个内部有选择关系的紧缩句，作一个分句看。 二、指出上题中复句内分句的关系。(答案见上题) 三、指出下列复句的各种类型(关联法，意合法?联合，偏正?并列，递进，因果……)： ①老哥哥为人非常和善，孩子们都喜欢他。意合法，偏正复句，因果关系。 ②天气暖和起来了，蜘蛛又出来在檐前做网。 意合法，联合复句，并列关系。 ③就是说，两亿人可以同昧通过一条线路讲话而互不干 扰，听得清清楚楚。 意合法，联合复句，并列关系。④首先，激光是一种颜色最单纯的光，而我们平常看见的光，是各种颜色的光混合起来的。关联法，联合复句，并列关系。⑤行李太多，得向脚夫行些小费才过得去。意合法，偏正复句，因果关系。 ⑥但是，他劳动惯了，离开土地就不舒服。意合法，偏正复句，因果关系。⑦我们不怕死，因为我们有牺牲精神。关联法，偏正复句，因果关系。 ⑧你看，那边山路上走来了两位老任，一人提着一只竹筒。意合法，联合复句，并列关系。⑨朝也等，暮也等，等了漫长的20年。意合法，联合复句，顺承关系。(二重复句) 五、改正下列病句，并说明理由。 ①革新技术以后，不但加快了生产速度，提高了产品的质量。 缺少同启下连词“不但”相搭配的承上连词，应在“提高”前添上“而且”。 ②犯罪分子一面不断地变换手法，一面终究逃脱不了人民的法网。 错用关联词语。两分句间是转折关系，不是并列关系，应将“一面……一面”改为“虽然……但(是)”或“……但(是)”。 ③这部作品虽然写的是农民，却也深刻地表现了广大农民的愿望。 错用关联词语。两分句间是并列关系，不是转折关系，应删去“虽然”“却也”。④这次全校篮球比赛，真想不到我们班会夺取冠军，并且一连战胜了六个强劲的对手。关联词语“并且”多余。分句间是并列关系，不是递进关系。⑤如果我们前一时期已经克服了学习上的一些困难，那么今后的困难也同样能克服。滥用关联词语。分句间是并列关系，应删去“如果”“那么”。 ⑥人们只有解放思想，努力学习，就可以掌握科学技术知识，并且有可能成为科学家。关联词语搭配不当。应将“只有”改为“只要”，或将“就”改为“才”。⑦这本书已经出版好几年了，所以作者最近作了较大的修改。错用关联词语。两分句间是顺承关系，应删去表因果关系的“所以”。⑧如果分析什么文章，只有掌握了这种方法，才能迎刃而解。 错用关联词语。第二分句与第三分句之间是充足条件关系，应将“只有……才”改为“只要……就”；全句第一层应为条件关系，不是假设关系，应将“如果”改为“无论”。 ⑨广大群众热烈地拥护这个方针；为了更支持群众在社会主义事业中的积极性和创造性，使得党和群众的关系加强 了。 分句之间在意义上缺乏联系。可改为：“广大群众热烈拥护这个方针，党发挥了群众建设社会主义的积极性和创造性，和群众的关系密切了。”或改为：“广大群众……方针，因为它支持了群众建设社会主义的积极性和创造性，它使党和群众的关系更加密切 ⑩他生长在偏僻的山区，因而从小就对农民有深厚的感 情。 两个分句之间并没有因果关系，应删去“因而”。 ⑾我们既然决定要修改这本书，所以得赶快研究修改的原则。关联词语搭配不当。两分句之间是推论因果关系，应将“所” ⑿为了抢救国家财产和人民的生命，哪怕刀山火海，我们就要上。关联词语搭配不当。应将“就”改为“也”。⒀不管天气如此变化多端，天池仍是一片沉静，渺渺湖水，清澈如镜。 “不管”表示无条件，后面不能出现表示确定的词语。“天气如此变化多端’’是确定的说法，应改为“天气怎样变化”。如果“天气如此变化多端”不改动，就应将“不管”改为“尽管”，因为“尽管”后需要有表示确定的说法。“语法”思考和练习十 二、标点下列几段文字： 1．当年，焦裕禄同志调到兰考后，经过调查研究，找张副***交换意见。他问：“改变兰考面貌的关键在哪儿?”张说：“在于人的思想的改变。”“对!”焦裕禄说，“但是应该在‘思想’前面，加两个字：‘领导’。关键在于县委领导核心的思想转变。没有抗灾的干部，就没有抗灾的群众。”在这里，焦裕禄仅用了短短几句话，就把如此重大而复杂的问题说得一清二楚，内涵深刻，这才是简洁朴素的语言。 2．1859年，达尔文出版了<物种起源)一书。他以极其丰富的事实、无可辩驳的证据指出：现在的生物界不是上帝或神创造的，而是由共同的最原始的祖先经过极其漫长的时间发展进化来的。各种生物之间，不是彼此孤立的，而是有着或远或近的亲缘关系。 三、改正下面的句子中使用不当的标点符号，并加以说明。1．“行喽，”小陈停了一会说：“叫我干什么我就干什么。” 将句中的冒号改为逗号。因为前后两个引号中的文字是一句话，这里的冒号只有提示下文的作用，它不能统领前一引号里的“行喽”。 2．师范院校的学生都必须学习《教育学》《心理学》等公共必修课。 “教育学”“心理学”是课程名，不是书名，应将书名号删去，碉在中间加上顿号。3．他家里的人说：“自己家里的炉子用多少煤，你从来刁管，对火车烧煤却这样认真”。他说：“国家的事要一丝不苟”。句中的两个句号都是表示直接引语之后的停顿，所以不能放在引号之外，应放在引号之内。4.贵报《中外名人故事》专栏内刊登的“刻苦自学的华罗庚”一文，我们都很喜欢读。报刊专栏名不应用书名号，应将书名号改为引号；“刻苦自学的华罗庚”是文章篇名，应将引号改为书名号。 5．我回到家乡一看。嗬?一幢幢美丽的瓦房；一片片葱翠的农田；一条条笔直的渠道；真是翻天覆地的变化。 “看”和“嗬”后都应改用逗号。三个分号也都应改为逗号，因为这几个分号隔开的不是并列的三个分句。 6．国家体委领导希望全体运动员“赛出水平、赛出风格，为国争光”。 “水平”之后的顿号应改为逗号，虽然它处在宾语内部’，却相当于分句之间的停顿。7．什么地方什么条件下可以种植什么样的药材?老农民了如指掌。应将问号改为逗号，因为前句不是疑问句。 8．一个时期，诗人对于季节：春夏秋冬的自然描写特别多。应将冒号改为破折号，这儿“春夏秋冬”是对“季节”的注释说明。第六章 修辞 “修辞”思考和练习二 二、下面这些句子在声音配合上各有些什么特色? ①您的光辉将永远照耀着雄伟的***广场，照耀着我 们伟大祖国的河山，照耀着五洲四海，照耀着我们的万里征 途。 叠韵词“照耀”(zhaoyao)多次重现形成了声音的反复美。各分句谓语结构大体一致。又，“广场”(仄仄)和“河山”(平平)、“四海”(仄仄)和“征途”(平平)，平仄相间，声音错落有致，悦耳动听。 ②他坚强不屈地斗争，铮铮铁骨，凛凛情操，真正表现了松树的风格。 “铮铮铁骨”(平平仄仄)和“凛凛情操”(仄仄平平)，音节整齐匀称、平仄相间，有节奏感。又“铮铮”和“凛凛”叠音相对，音调铿锵，表现了一位革命家的崇高气节。 ③人民中国，屹立亚东。光芒万道，辐射寰空。艰难缔造庆成功，五星红旗遍地红。生者众，物产丰，工农长作主人翁。 这段文字或4个音节连用成句，或7个音节连用成句，或3个 音节与7个音节连用成句，在音节配合上比较整齐匀称，有变化，有节奏感。押韵自然，合辙(中东辙)上口，读起来很有诗词的格调和韵味。 三、比较下面各组的句子，在表达上有什么不同。 ①山愈聚愈多，渐渐暮霭低垂了，渐渐进入黄昏了，红绿灯渐次闪光，而苍翠的山峦模糊为一片灰色。 ②山愈聚愈多，暮霭低垂了，进入黄昏了，红绿灯闪着光，而苍翠的山峦模糊为一片灰色。例①用“渐渐”修饰“暮霭低垂”和“进入黄昏”，用“渐次”修饰“闪光”，描绘了夜景的变化和时间推移的过程，表现了人的悠闲的心情和细微的观察。例②虽也描写了夜景，但不能使人明显地感觉出它的变化，也暗示不出人的悠闲心情和细微的观察。①那时候，天气还很冷，潍河里还在流着冰水，平原上整天价在刮着老黄风。 ②那时候，天气还很冷，潍河里还在流着冰水，平原上整天价在刮着扬天揭地的老黄风。例①对“老黄风”缺乏具体的描写。例②用“扬天揭地”修饰“老黄风”，写出了“老黄风”猛烈的情状，形象而有气势。 四、从锤炼词语的角度谈谈下面这两段文字中一些词语的修辞效果。①金刚山的美景，被朝鲜人民引为自豪。她位于朝鲜中部东海岸太白山脉的北部地区，绚丽多姿，四季有不同的雅名。春天万紫千红，叫金刚山；夏天飞泉腾空，浓荫蔽日，又名蓬莱山；秋天漫山红叶，层林尽染，外号枫岳山；冬天白雪皑皑，银装素裹，人称皆骨山。 “绚丽多姿”一语十分准确地概括了对金刚山美好景色的总印象。“绚丽”言其美，“多姿”言其变化，只此一语便包括了下文的许多描写。“万紫干红，飞泉腾空，浓荫蔽日，漫山红叶，层林尽染，白雪皑皑，银装素裹”等四字格词语描绘了金刚山四季景物的变化，音节整齐匀称，声调抑扬起伏，富于音乐美。又“飞、腾、蔽、染、装、裹”等动词使静止的景物鲜明而生动，随季节的变化更替的山名，更使人感到金刚山的四时之美。 ②这里的水，多，清，静，柔。在园里信步，但见这里一泓深潭，那里一条小渠。桥下有河，亭中有井，路边有溪。石间细流脉脉，如线如缕；林中碧波闪闪，如锦如缎。这些水都来自难老泉。泉上有亭，亭上挂着清代著名学者傅山写的“难老泉”三个字。这么多的水长流不息，日日夜夜发出叮叮咚咚的响声。 首句用了“多、清、静、柔”4个单音节形容词，简洁干脆，描写贴切，有容量。作为总写部分，很有概括力和形象感。次句对偶十分自然，“深潭””“渠’’点出到处是深水浅流。第三句的“有河”“有井”“有溪”除了同前一句尽写这里水多之外，还暗含无水不成景之意。接下来的对偶句又含蓄地写出了这里的水给人的感官之美：清亮、平静、柔和。水之源头就是难老泉。这段文字用词准确形象，朴素自然，透出一股清新之气。单音节词用得平实稳妥，全文有整句的效果。 “修辞”思考和练习三 三、从选择句式的角度看。下列句子是何种类型?它们有什么修辞效果? ①那种假统一论，不合理的统一论，形式主义的统一论，第二篇：严蔚敏 数据结构课后习题及答案解析
第三篇：数据结构习题与答案
第四篇：证券投资学课后习题答案总结
第五篇：现代汉语课后习题答案
点击咨询 