严蔚敏_数据结构课后习题及答案解析.pdf

第一章结论一、选择题1.组成数据的根本单位是(A)数据项 B 数据类型2.数据构造是神究数据的 A 理想构造，糊理构造 C 物理构造，谡辑构造 C 数据元素 D 数据变量以及它111之间的相互关系。B 理想构造，抽象构造 D 抽象构造，谡辑构造3.在数据构造中，从谡辑上可以把数据构造分成 A 前态构造和静态构造 B 紧凑构造和非紧凑构造(C)线性构造和非线性构造 D 内部构造和外部构造4.数据构造是一门物究非数值计算的程序设计问题中计算机的 以及它111之间的 和运算等的学科。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.数据谡辑构造包括_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 和_ _ _ _ _ _ _ _ _ _ _ 四种类型，其中机形构造和图形构造合称为_ _ _ _ _O2.在线性构造中，第一个结点_前驱结点，其余每个结点有且只有_ _ _ _ 个前驱结点；最后一个结点_ _ _ _ _ _ 后续结点，其余每个结点有且只有_ _ _ _ _ _ _个后续结点。3.在树形构造中，树根结点没有_ _ _ _ _ _ 结点，其余每个结点有且只有_ _ _ _ _ _ _个前驱结点；叶子结点没有_ _ _ _ _ _ _ _结点，其余每个结点的后续结点可以_ _ _ _ _ _ _ _ _ _O4.在图形构造中，每个结点的前驱结点数和后续结点数可以_ _ _ _ _ _ _ _o5.线性构造中元素之间存在_ _ _ _ _ _ _ 关系，树形构造中元素之间存在_ _ _ _ _ _关系，图形构造中元素之间存在_ _ _ _ _ _ _ 关系。6.算法的五个重要特性是_ _ _ _ _ _、_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _、_ _ _ _ _ _ _o7.数据构造的三要素是指_ _ _ _ _ _ _ _ _ _ _ _和_ _ _ _ _ _ _ _ _o8.链式存储构造与顺序存储构造相比抵，主要优点是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _o9.段有一批数据元素，为了最快的存慌某元素，数据构造宜用 构造，为了方便插入一个元素，数据构造宜用_ _ _ _ _ _ _ _ _ _ _ _ _ 构造。四、算法分析题1.求以下算法段的语句颛度及时间复杂度参考答案：一、选择题1.C 2.C 3.C 4.A、B 5.C 6.C、B二、判断题：1 s V 2 x 3、x 4、x 5、，三、填空题1、线性、树形、图形、集合？;非爱性网状 2、没有；1；没有；13、前驱；1；后继；任 意 多 个 4、任 意 多 个 5、一对一；一对多；多对多6、有穷性；确定性；可行性；输入；输 出7、数据元素；遢辑构造；存储 构 造8、插入、删除、合并等操作较方便9、颗序存第；链式存储四、算法分析题for(i=1;i=n;i+)for(j=1;j=i;j+)x=x+1;分析：该算法为一个二重循环，执行次数为内、外循环次数相乘，但内循环次数不固定，与外储环有关，因些，时间颛度T(n)=1+2+3+n=n*(n+1)/2有1/4&T(n)/n 2 w 1,故它的时间复杂度为0(n 2),即T(n)与n 2数量级一样。2、分析以下算法段的时间频度及时间复杂度for(i=1;i=n;i+for(j=1；j=i；j+)for(k=1;knext=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;Bp=p-next;p-next=p-next-next;Cp-next=p-next;Dp=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)o 三、填空题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的所有结点的ci5数。3.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成一个指环旌表，每个结点有价格、数量和捱指针三个域。现出库销售m台价格为h的电视机，试编写算法修改原捱表。4.某百货公司仓库中有一批电视机，报其价格从低到高的次序构成一个脩环旌表，每个结点有价格、数量和抵指针三个域。现新到m台价格为h的电视机，试编写算法修改原隹表。5.线性表中的元素值按递增有序排列，针对即序表和脩环越表两种不同的存储方式，分别编写C函数删除线性表中值介于a与b a v b之间的元素。6.设A=(a0,a1,a2，,an-1),B=(bO,b1,b2.b m-1)t两个给定的线性表，它们的结点个数分别是n和m,且结点值均是整数。假设 n=m,且 ai=bi 0 in),那么 A=B；假设 nm,且 ai=bi 0 in，那么 AB；假段存在一个j,km,jn,且ai=bi 0 ij，假设a j b j,那么A BO试编写一个比拟A和B的C函数，该函数返回-1或0或1 ,分 别 表 示ABO7.试编写算法，删除双向循环於表中第k个结点。8.线性表由前后两局部性质不同的元素组(aO,a1.an-1,bO,b1，,bm-1),m和n为两局部元素的个数，假设线性表分别采用数组和范表两仲方式存储，编写算法将两局部元素换位成(bO.bl.bm-1,aO,a1.an-1),5i 两种存储方式下算法的时间和空间复杂存。9.用循环用表作线性表(aO,a1，,an-1)和 bO,b1，,bm-1的存储构造，头指针分别为a h和bh,设计C函数，把两个线性表合并成形如aO,bO,a1,b1,的线性表，要求不开辟新的动态空同，利用原来循环能表的结点完成合并操作，构造仍为循环胜表，头指针为head,并分析算法的时间复杂度。10.试写出将一个线性表分解为两个带有头结点的循环捱表，并将两个他环锥表的长度放在各自的头结点的数据域中的C函数。其中，线性表中序号为偶数的元素分解到第一个僻环I起表中,序号为奇数的元素分解到第二个循环隹表中。11.写出把线性曲表改为I I环箝表的c函数。12.己知非空我性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数。参考答案：一、选择题1.B 2.C 3.D 4.B 5.A 6.A 7、C二、判断题：参考答案：1、x 2、，3、x 4、x 5、V三、填空题1、s-next=p-next;p-next=s;2,一定；不一定 3、n/2 4、q-prior=p;5、(1)6)3)2)9)1)7)四、算法设计题1、#include stdio.h#include malloc.htypedef struct nodeint 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.htypedef struct nodeint data;/*假设数据域为整型*/struct node*link;INODE;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);elseP=q；q=q-link;3、void del(NODE*head,float price,int num)!NODE*p,*q,*s；p=head;q=head-next;while(q-pricenext;if(q-price=price)q-num=q-num-num;elseprintf(无此产品)if(q-num=0)!p-next=q-next;free(q);4、#include stdio.h#include malloc.htypedef struct nodefloat price;int num;struct node*next;!N0DE;void ins(NODE*head,float price,int num)!NODE*p,*q,*s;p=head;q=head-next;while(q-pricenext;if(q-price=price)q-num=q-num+num;elses=(NODE*)malloc(sizeof(NODE);s-price=price;s-num=num;s-next=p-next;p-next=s;5、5序表:算法思想：从0开场打描线性表，用k记录下元素值在a与b之间的元素个数，对于不满足该条件的元素，前移k个位置，最后修改线性表的长度。void del elemtype list,int*n,elemtype a,elemtype b)int i=0,k=0；while(i=a&listilink;/*假设循环捱表带有头结点*/while(q!=head&q-datalink;while(q!=head&q-datalink;free(r);if(p!=q)p-link=q;6、#define MAXSIZE 100int listAMAXSIZE,listBMAXSIZE;int n,m;int pare(int a,int b)int i=0;while(ai=bi&in&im)i+；if(n=m&i=n)return(O);if(nm&i=m)return(1);if(in&im)if(aibi)return(1);7、void del(DUNODE*head,int i)DUNODE*p;if(i=O)(*head=*head-next;*head-prior=NULL;return(O);Elsefor(j=0;jnext;if(p=NULL|ji)return；p-prior-next=p-next;p-next-prior=p-proir;free(p);return(O);8.序存储：void convert(elemtype list,int l,int h)/*将数组中第 I 个到第 h 个元素逆置*/int i;elemtype temp;for(i=h;i=(l+h)/2;i+)temp=listi;listi=listl+h-i;listl+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);I该算法的时间复杂度为0(n+m),空间复杂度为0(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;ilink;/*q 指向 an-1 结点*/r=q-link;q-link=NULL;while(r-link!=NULL)r=r-link;/*r指向最后一个bm-1结 点*/*head=q;r-link=p;该算法的时间复杂度为0(n+m),但比顺序存曲节省时间(不需要移动元素，只需改变指针)，空间复杂度为0(1)9.typedef struct nodeelemtype data;struct node*link;INODE;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的 结 点 个 数*1a-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);该算法的时间复杂度为0(n+m),其中n f llm为两个指环旌表的结点个数.10.typedef struct node(elemtype data;struct node*link;NODE;void analyze(NODE*aNODE*rh,*qh,*r,*q,*p；int i=0,j=0；/*i为序号是奇数的结点个数j为序号是偶数的结点个数*/P=a；rh=NODE*malloc sizeof N O D E)；/*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 nodeelemtype 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 nodeelemtype 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,那么枝的不可能的输出序列是。Aedcba Bdecba Cdceab Dabcde2.我构造通常采用的两种存储构造是。A 线性存储构造和造表存俯构造B散列方式和索引方式C附表存假构造和数组D线性存境构造和非线性存储构造3.制定一个枝ST(最多元素为mO)为空的条件是。(A)ST-top!=0 BST-top=0(C)ST-)top!=mO D ST-top=mO4.判定一个枝ST(最多元素为mO)为栈满的条件是。AST-top!=0 BST-top=0CST-top!=mO-1(D)ST-top=mO-15.-个队列的A列f f 则是1 2 3,4,那么队列的输出序列是。A4,3,2,1 B1,2,3,4 C1,4,3,2 D3,2,4,16.循环队列用数组A0,m-1存放其元素值，其头尾指针分别是fron t和rear那么当前队列中的元素个数是(A)(rear-front+m)%m B rear-front+1(C )rear-front-1 D)rear-front7.枝和队列的共同点是(A)都 是 先 进 后 出 B部是先进先出C只允许在端点处插入和删除元素D没有共同点8.表达式a*(b+c)-d的后鬟表达式是。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd9.4个元素a1,a2,a3和a4依次通过一个板，在a4进枝前，枝的状态，那么不可能的出枝序 是 )(A)a4,a3,a2,a1(B)a3,a2,a4,a1(C)a3,a1,a4,a2(D)a3,a4,a2,a110.11数组Q0.m-1存放指环以列中的元素，变量rear和qulen分刖指示循环队列中以尾元素的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是 (A)rear-qulen(B)rear-qulen+m(C)m-qulen(D)1+rear+m-qulen%m二、填空题1枝的特点是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 以列的特点是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _O2.线性表、栈和队列都是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 构造，可以在线性表的_ _ _ _ _ _ _ _ _ _ _ _ _ _ _位置2人和删除元素，对于我只能在_ _ _ _ _ _ _ _插入和删除元素，对于队列只能荏_ _ _ _ _ _ _插入元素和_ _ _ _ _ _ _ _ _删除元素。3.一个枝的输入序列是12345,那么枝有输出序列12345是_ _ _ _ _ _ _ _ _ _ _。(正确/错误)4.设枝S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6依次通过一个栈，一个元素出枝后即进入队列Q,假设6个元素出队列的H序是a3,a5,a4,a6,a2,a1那么枝S至少应该容期_ _ _ _ _ 个元素。三、算法设计题1.假设有两个枝s1 fU s2共享一个数组stackM,其中一个栈底设在stack0处，另一个栈底设在stackM-1j!to试编写对任一栈作进栈和出栈运算的C函数pushx,i)和pop(i),i=l,20其中i=1表示左边的枝，i=2表示右边的枝。要求在整个数组元素都被占用时才产生溢出。2.利用两个技s1,s2模扭一个队列时，如何用我的运算来实现该队列的运算？写出模扭队列的插人和删除的C函数。一个栈s 1用于插入元素，另一个板s 2用于删除元素.参考答案：一、选择题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 100elemtype stackM;int top1=0,top2=m-1;int push(elemtype x,int i)(if(top1-top2=1)return(1);/*上温处理*/elseif(i=1)stacktop1+=x;if(i=2)stacktop2=x;return(O);int pop(elemtype*px,int i)(if(i=1)if(top1=0)return(1);elsetopi;*px=stacktop1;return(O);elseif(i=2)if(top2=M-1)return(1);elsetop2+;*px=stacktop2;return(O);2.elemtype s1 MAXSIZE,s2MAZSIZE;int topi,top2;void enqueue(elemtype x)(if(top1=MAXSIZE)return(1);elsepush(s1,x);return(O);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 值 2(?)(A)(0,1,01,1,0,4,1,0,1)(B)(0,1,0,0,0,0,2,1,0,1)(0(0,1,0,1,0,0,0,1,1)(D)(0,1,0,1,0,1,0,1,1)3.字符串满足下式，其中head和ta il的定义同广义表类似，如head(lx y z)=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.htypedef struct nodechar data;struct node*link;INODE;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(O);第五章数组和广义表一、选择题1.常对数组进展的两利根本操作是(A)建立与删除B索引和修改 C查找和修改(D)查找与索引2.二维数组M的元素是4个字符(每个字符占一个存用单元)组成的串，行下标i的X围从0到4,列下标j 的 X 围从0 到 5,M技行存储时元素M35的起始地址与M 按列存情的元素()的起始地址一样。(A M24 B M34 C M 35 DM443.数组A810中，每个元素A 的长度为3 个字节，从首地址SA开场连续存放在存愤器内，存放该数组至少需要的单元数是。(A)80(B 100(C)240 D)2704.数组A810中，每个元素A 的长度为3 个字节，从首地址SA开场连续存放在存储器内，该数组投行存放时，元素A74的起始地址为。ASA+141 BSA+144 CSA+222 DSA+2255.数组A810中，每个元素A 的长度为3 个字节，从首地址SA开场连续存放在存储器内，该数组按列存放时，元素A的起始地址为。(ASA+141 BSA+180 CSA+222 DSA+2256.稀疏矩阵一般的压缩存储方法有两利，郎 。(A)二维数组和三维数组 B三元组和散列 C三元组 和 十 字 簿 表 D散列和十字簿表7.假设采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点。A正 确 B错误8.设矩薛A 是一个对称花阵，为了节省存储，将其下三角局部按行序存放在一维数组B1,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.已知二维数组Amn采用行序为主方式存储，每个元素占k 个存曲单元，并且第一个元素的存储地址是LOC(A00),a!么A00的地址是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。2.二维数组A1020采用列序为主方式存储，每个元素占一个存储单元，并且A的存储地址是200,那么A12的地址是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ o3.有一个10 3 对称矩阵A,采用压缩存俑方式(以行序3 有，且 A00=1),么 A85的地3 是4.设n 行 n 列的下三角矩阵A 已压缩到一维数组S1.n*(n+1)/2中，假设按行序为主存储，那么Ai用对应的S 中的存储位置是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。5.假设A 是按列序为主序进展存储的4 x 6 的二维数组，其每个元素占用3 个存储单元，并且AOOtf存。地址1 1000,元素A13ff存。地址为_ _ _ _ _ _ _ _ _ _ _ _ 该数组共占用_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 个存曲单元。三、算法设计 如果矩阵A 中存在这样的一个元素Aij满 足 条 件:是 第 i 行中值最小的元素，且又是第j 列中值最大的元素，那么称之为该矩阵的一个马鞍点。编写一个函数计算出1 x n 的矩阵A 的所有马鞍点。2.n 只正子要选大王，选举方法如下：所有猴子按1,2，,n 编号围坐一圈，从 1 号开场按1、2、m 报数，凡报m 号的退出到圈外，如此循环报数，直到圈内刺下只猴子时，这只保子就是大王。n和 m 由维盘输入，打印出最后剩下的猴子号。编写一程序实现上述函数。3.数组和广义表的算法脸证程序编写以下程序：(1)求广义表表头和表尾的函数head()和tail。(2)计算广义表原子结点个数的函数count_GL()0(3)i t 算广义表所有原子结点数据帧(设数据域为整型之和的函数sum_GL()o参考答案：一、拉择题1.C 2.B 3.C 4.C 5.B 6.C 7、B 8、B二、填空题1.loc(A00)+(n*i+j)*k 2.332 3、42 4、i*(i+1)/2+j+1 5、1039；72三、算法设计题1.算法思想：依题意，先求出每行的最小值元素，放人minm之中，再求出每列的最大值元素，放人maxn2中，假设某元素既在mini中，又在maxj中，那 么 该 元 素 便 是 马 鞍 点，找出所有这样的元素，即找到了所有马鞍点。因此，实现此题I力能的程序如下：#include#define m 3#define n 4void minmax(int amn)(int i1,j,have=O;int minm,maxn;for(i1=0;i1m;i1+)/*it算出每行的最小值元素，放入m inm 2中*/mini1=ai10;for(j=1;jn;j+)if(ai1jmini1)mini1=ai1j;)for(j=0;jn;j+)/*计算出每列的最大值元素，放人maxn之中*/(maxj=a0j;for(i1=1;i1max j)maxj=ai1j;for(i1=0;i1m;i1+)for(j=0;j=m*/for(j=0;jn;j+)aj=i+1；count=0;d=0;while(dn)for(j=0;jtag=1;h-dd.sublist=creat_GL(s);日seh-tag=O;h-dd.data=ch;elseh=NULL;ch=*(*s);(*s)+;if(h!=NULL)if(ch=,)h-link=creat_GL(s);elseh-link=NULL;return(h);void prn_GL(NODE*p)if(p!=NULL)!if(p-tag=1)printf()；if(p-dd.sublist=NULL)printf();elseprn_GL(p-dd.sublist);elseprintf(%c,p-dd.data);if(p-tag=1)printf();if(p-link!=NULL)printfC1,);prn_GL(p-link);NODE*copy_GL(NODE*p)NODE*q;if(p=NULL)return(NULL);q=(NODE*)malloc(sizeof(NODE);q-tag=p-tag;if(p-tag)q-dd.sublist=copy_GL(p-dd.sublist);elseq-dd.data=p-dd.data;q-link=copy_GL(p-link);return(q);NODE*head(NODE*p)/*求表头函数*/(return(p-dd.sublist);NODE*tail(NODE*p)/*求表尾函数*/return(p-link);int sum(N0DE*p)/*求原子结点的数据域之和函数*1 int m,n;if(p=NULL)return(O);else if(p-tag=O)n=p-dd.data;elsen=sum(p-dd.sublist);if(p-link!=NULL)m=sum(p-link);else m=0;return(n+m);Iint depth(NODE*p)/*求表的深度函数*/int h.maxdh;NODE*q;if(p-tag=O)return(O);elseif(p-tag=1&p-dd.sublist=NULL)return 1;elsemaxdh=0;while(p!=NULL)(if(p-tag=O)h=O;elseq=p-dd.sublist;h=depth(q);if(hmaxdh)maxdh=h;p=p-link;return(maxdh+1);main()NODE*hd,*hc;char s1OO,*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 Bt-ltag=1(C )t-ltag=1 且 t-lefCNULL D以上都不对2.二叉树按某利顺序线索化后，任一结点均有指向其前赴和后继的线索，这种猊法A正 确 B错 误 C不同情况下答案不确定3.二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这利说法(A)正 确(B)错 误 C不同情况下答案不确定4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 A正 确 B错 误 C不同情况下答案不确定5.设高度为h的二叉树上只有度为0和度为2的结点，那么此类二叉树中所包含的结点数至少为 。A2h B2h-1 C 2h+1 Dh+16.某二叉树的后序遍历序列是dabeco中序遍历序列是debac,它的前序遍历序列是。Aacbed Bdecab Cdeabc Dcedba7.如果T2是由有序的T转换而来的二叉树，那么T中结点的前序就是T 2中结点的 A前 序 B中 序 C后序D层次序8.某二叉树的前序遍历结点访问i序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,那么其后序遍历的结点访问腼序是。A)bdgcefha(B)gdbecfha C bdgaechf(D gdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法 A正 确 B猎 误 C不同情况下答案不确定10.按照二叉树的定义，具有3个结点的二叉树有 种。A 3 B 4 C 5 D 611.在一非空二叉树的中序遍历序列中，根结点的右边 A只有右子机上的所有结点B只有右子树上的局部结点(C)只有左子树上的局部结点D只有左子树上的所有结点12.树最适合用来表示。(A)有序数据元素B无序数据元素(C J元素之间具有分支层次关系的数据(D)元素之间无域系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遢历序列中的相对次序(A 不发生改变B发生改变C不能确定D.以上都不对14.实现任意二叉树的后序遍历的非递归算法而不使用枝构造，最正确方案是二叉树采用 存储构造。(A)二叉捱表B广义表存仲构造C三叉链表D顺序存用构造15.对一个满二叉树,m个树叶,n个结点，深度为h,那 么 An=h+m Bh+m=2n C)m=h-1 Dn=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为 Au w v ts Bvw uts Cw u v ts Dwutsv17.具有五层结点的二叉平衡树至少有 个结点。(A)10 B 12 C 15(D)17二、判断题1.二叉树中任何一个结点的度都是2。2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树。3.一棵哈夫曼树中不存在度为1的结点。4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2 三、填空题1.指出树和二叉树的三个主要差异_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _2.从概念上讲，树与二叉树是两种不同的数据构造，将树转化为二叉树的根本目的是3.假段结点A有三个兄弟（包括A本身），并且B是A的双亲结点,B的度是_ _ _