【考研类试卷】计算机学科专业基础综合数据结构-2及答案解析.doc

1、计算机学科专业基础综合数据结构-2 及答案解析(总分：96.00，做题时间：90 分钟)一、综合应用题(总题数：9，分数：96.00)利用顺序表的操作，实现以下的函数：（分数：32.00）(1).从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。（分数：4.00）_(2).从顺序表中删除第 i个元素并由函数返回被删元素的值。如果 i不合理或顺序表为空则显示出错信息并退出运行。（分数：4.00）_(3).向顺序表中第 i个位置插入一个新的元素 x。如果 i不合理则显示出错信息并退出运行。（分数：4.00）_(4).从顺序表

2、中删除具有给定值 x的所有元素。（分数：4.00）_(5).从顺序表中删除其值在给定值 s与 t之间(要求 s小于 t)的所有元素，如果 s或 t不合理或顺序表为空则显示出错信息并退出运行。（分数：4.00）_(6).从有序顺序表中删除其值在给定值 s与 t之间(要求 s小于 t)的所有元素，如果 s或 t不合理或顺序表为空则显示出错信息并退出运行。（分数：4.00）_(7).将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。（分数：4.00）_(8).从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不相同。（分数：4.00）_1.线性表的每一个表元素是否必须类型相同?为

3、什么? （分数：4.00）_2.设有一个带表头结点的链表，结点的结构为(data，link，sort)，其中 data为整型值域，link 和 sort都是指针域。已知链表所有结点都已通过 link域指针链接起来，构成单链表，且所有结点数据的值互不相同。试编写一个算法，利用 sort域把所有结点按照数据的值从小到大的顺序链接起来。 （分数：4.00）_针对带表头结点的单链表，试编写下列函数：（分数：20.00）(1).定位函数 Locate：在单链表中寻找第 i个结点。若找到，则函数返回第 i个结点的地址；若找不到，则函数返回 NULL。（分数：4.00）_(2).求最大值函数：Max：通过一

4、趟遍历在单链表中确定值最大的结点。（分数：4.00）_(3).统计函数 Count：统计单链表中具有给定值 x的所有元素。（分数：4.00）_(4).建立函数 Create：根据一维数组 an建立一个单链表，使单链表中各元素的次序与 an中各元素的次序相同，要求该程序的时间复杂度为 O(n)。（分数：4.00）_(5).整理函数 Tidyup：在非递减有序的单链表中删除值相同的多余结点。（分数：4.00）_已知 first为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法：（分数：12.00）(1).求链表中的最大整数。（分数：4.00）_(2).求链表的结点个数。（分

5、数：4.00）_(3).求所有整数的平均值。（分数：4.00）_3.用单链表存储多项式的结构定义如下： Typedef struct Term /多项式的项 float coef; /系数 int exp; /指数 struct Term * link;/链指针 * Polynomial; 试编写一个算法，输入一组多项式的系数和指数，按指数降幂的方式建立多项式链表，要求该链表具有表头结点。如果输入的指数与链表中已有的某一个项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为 0标志结束。算法的首部为 Polynomial createPoly()； （分数：4.00）_假设对

6、于一个多项式(Polynomial) P(x)=a m-1 +a m-2 +a 0 用长度为 m的单链表表示为(t m-1 ，t m-2 ，t m-3 ，t 1 ，t 0 )。其中，m 是多项式 P(x)中非零项(term)的个数，每一个 t i (0im-1)是 P(x)的一个非零项，它由三个数据成员 coef、exp 和 link组成，coef 是系数(浮点型)，exp 是指数(整型)，link 是链接指针。各个项的指数 e i 按递减顺序排列：e m-1 e m-2 e 0 0。（分数：12.00）(1).试描述多项式的数据结构(m 可以不出现在定义中)。（分数：4.00）_(2).给出

7、在多项式中插入新项的算法 Insert。该算法的功能是：如果多项式中没有与新项的指数相等的项，则将此新项插入到多项式链表的适当位置；如果多项式中已有与新项的指数相等的项，则将它们合并。（分数：4.00）_(3).利用这个插入算法给出多项式乘法的实现算法。（分数：4.00）_4.没有一个不带表头结点的单链表，表头指针为 head。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针 head指向原链表的最后一个结点。 （分数：4.00）_5.试设计一个实现下述要求的 Locate运算的函数。设有一个带表头结点的双向链表 L，每个结点有 4个数据成员：指向前

8、驱结点的指针 lLink、指向后继结点的指针 rLink、存放数据的成员 data和访问频度freq。所有结点的 freq初始时都为 0。每当在链表上进行一次 Loeate(L，x)操作时，令元素值为 x的结点的访问频度 freq加 1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保存按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 （分数：4.00）_计算机学科专业基础综合数据结构-2 答案解析(总分：96.00，做题时间：90 分钟)一、综合应用题(总题数：9，分数：96.00)利用顺序表的操作，实现以下的函数：（分数：32.00）(1).从顺序表中删除

9、具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。（分数：4.00）_正确答案：()解析：实现删除具有最小值元素的函数 bool deleteMin(SeqList /表空,中止操作返回 value=L.data0;int i,pos=0;/假定 1号元素的值最小 for(i=2;i=L.n;i+) /循环,寻找具有最小值的元素 if(L.datai-1value) /让 value记忆当前具有最小值的元素 value=L.datai-1;pos=i-1; for(int j=pos+1;jL.n;j+)L.dataj-1=L.dat

10、aj; L.n-; return true; (2).从顺序表中删除第 i个元素并由函数返回被删元素的值。如果 i不合理或顺序表为空则显示出错信息并退出运行。（分数：4.00）_正确答案：()解析：实现删除第 i个元素的函数(设第 i个元素在 datai-1,i=1,2,3,n) bool deleteNo_i(SeqList /表空或 i不合理,终止操作 value=L.datai-1; for(int j=i;jL.n;j+)L.dataj-1=L.dataj; L.n-; return true; (3).向顺序表中第 i个位置插入一个新的元素 x。如果 i不合理则显示出错信息并退出运行

11、。（分数：4.00）_正确答案：()解析：实现向第 i个位置插入一个新的元素 x的函数(设第 i个元素在 datai-1，i=1，2，3，n) bool InsNo_i(SeqList/表满或参数 i不合理,中止操作 return false; for(i=L.n;j=i;j-)L.dataj=L.dataj-1; L.datai-1=value;L.n+: return true; (4).从顺序表中删除具有给定值 x的所有元素。（分数：4.00）_正确答案：()解析：从顺序表中删除具有给定值 x的所有元素 void deleteValue(SeqList for(i=L.n;i=1;i-)

12、 /循环,寻找具有值 x的元素并删除它 if(L.datai-1=value)/删除具有值 x的元素 for(j=i;jL.n;j+)L.dataj-1=L.dataj; L.n-; (5).从顺序表中删除其值在给定值 s与 t之间(要求 s小于 t)的所有元素，如果 s或 t不合理或顺序表为空则显示出错信息并退出运行。（分数：4.00）_正确答案：()解析：实现删除其值在给定值 s与 t之间(要求 s小于 t)的所有元素的函数 bool deleteNo_sto_t(SeqList if(st)DataType temp=s;s=t;t=temp; /保持 st int i,j; for(i

13、=L.n-1;i=1;i-) /循环,寻找在给定范围内的元素并删除它 if(L.datai-1=sjL.n;j+) L.dataj-1=L.dataj; L.n-; return true; (6).从有序顺序表中删除其值在给定值 s与 t之间(要求 s小于 t)的所有元素，如果 s或 t不合理或顺序表为空则显示出错信息并退出运行。（分数：4.00）_正确答案：()解析：实现从有序顺序表中删除其值在给定值 s与 t之间的所有元素的函数 bool deleteNo_sto_t1(SeqList if(st)DataType temp=s;s=t;t=temp; /保持 st int i,j,k,

14、u; for(i=1;i=L.ni+); /寻找值s 的第一个元素 if(iL.n)return false; /没有值s 的元素 for(j=i;j=L.nj+); /寻找值t 的第一个元素 for(k=j,u=i;k=L.n;k+,u+) /前移,填补被删元素位置 L.datau-1=L.dataK-1; L.n=L.n-j+i: return true; (7).将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。（分数：4.00）_正确答案：()解析：实现将两个有序顺序表合并成一个新的有序顺序表的函数 bool Merge(SeqList int i=1,j=1,k=1;

15、while(i=A.ni+; else C.datak-1=B.dataj-1;j+;k+ while(i=A.n)C.datak-1=A.dataI-1;i+;k+ while(j=B.n)C.datak-1=B.dataj-1;j+;k+ C.n=k; return true; (8).从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不相同。（分数：4.00）_正确答案：()解析：实现从有序顺序表中删除所有值重复的元素的函数 bool deleteSame(SeqList int i=1,j; while(i=L.n) /循环检测 while(L.datai-1!=L.datai)

16、i+; /寻找重复的元素 i与元素 i+1 j=i+2; /发现重复 while(L.datai-1=L.dataj-1)j+; for(k=i+1,u=j;u=L.n;k+,u+) L.datak-1=L.datau-1; i+: return true; 解析 通过顺序表的定义及基本特性来完成。1.线性表的每一个表元素是否必须类型相同?为什么? （分数：4.00）_正确答案：()解析：线性表每一个表元素的数据空间要求相同，但如果对每一个元素的数据类型要求不同时可以用等价类型(union)变量来定义可能的数据元素的类型。如 Typedef union /联合 int integerInfo;

17、 /整型 char charInfo; /字符型 float floatInfo; /浮点型 info; 利用等价类型，可以在同一空间(空间大小相同)indo 中存放不同数据类型的元素。但要求用什么数据类型的变量存，就必须以同样的数据类型来取。2.设有一个带表头结点的链表，结点的结构为(data，link，sort)，其中 data为整型值域，link 和 sort都是指针域。已知链表所有结点都已通过 link域指针链接起来，构成单链表，且所有结点数据的值互不相同。试编写一个算法，利用 sort域把所有结点按照数据的值从小到大的顺序链接起来。 （分数：4.00）_正确答案：()解析：算法设计的

18、基本思路是：按照链表插入排序的思想，将 sort链初始化为只有一个结点(首元结点)的有序单链表，然后扫描 link链的每个结点，一边扫描一边将结点按其值插入到 sort链中。算法实现如下： Typedef struct node /链表结点类型定义 int data; /数据域 struct node*link; /原有单链表的链接指针 struct node*sort; /将生产的有序单链表的链接指针 DLNode; Typedef DLNode*DList; /链表类型定义 Void sortList(DList list) /利用链表 list的 sort域建立按照结点数据值升序链接的单

19、链表 List-sort=list-link:list-sort-NULL; DLNode*p,*prep,*s=list-link-link; while(s!=NULL) p=list-sort;prep=list; while(p!=NULLp=p-soft; prep-sort=s;s-sort=p; /链入 sort链 s=s-link; /处理 link链的下一结点 此算法有一个嵌套的循环。其中，外层循环执行 n-1次，而内层循环的执行次数取决于数据值。最好情况是原链表中所有结点的数据值都按降序排列，每次插入时仅比较 1次；最坏情况是原链表中所有结点的数据值都按升序排列，这样在插入

20、第 i(2in)个结点时需要比较 i-1次。所以，最好情况下算法的数据比较次数为 O(n)，最坏情况下算法的数据比较次数为 O(n 2 )。 算法的数据移动次数为 0，因为链表插入只需修改结点指针，不需移动元素。针对带表头结点的单链表，试编写下列函数：（分数：20.00）(1).定位函数 Locate：在单链表中寻找第 i个结点。若找到，则函数返回第 i个结点的地址；若找不到，则函数返回 NULL。（分数：4.00）_正确答案：()解析：实现定位函数的算法 LinkedNode*Locate(LinkList L,int i) /取得单链表中第 i个结点地址,i 从 0开始计数,i=0 定位于

21、表头结点 if(i0)return NULL; /位置 i在表中不存在 LinkedNode *p=L;Int k=0; /从表头结点开始检测 while(p!=NULLk+; return p; /否则 k=i,返回第 i个结点地址 (2).求最大值函数：Max：通过一趟遍历在单链表中确定值最大的结点。（分数：4.00）_正确答案：()解析：实现求最大值的函数 LinkedNode * Max(LinkList L) /在单链表中进行一趟检测,找出具有最大值的结点地址,如果表空,返回指针 NULL if(L-link=NULL)return NULL; /空表,返回指针 NULL Linke

22、dNode * pmax=L-link,p=L-link-link; /假定头结点中数据值最大 while(p!=NULL) /循环,下一个结点存在 if(p-datapmax-data)pmax=p; /pmax记忆找到的具有最大值结点 p=p-link; /检测下一个结点 return pmax; (3).统计函数 Count：统计单链表中具有给定值 x的所有元素。（分数：4.00）_正确答案：()解析：实现统计单链表中具有给定值 x的所有元素的函数 int Count(LinkList L,DataType x) /在单链表中进行一趟检测,统计具有给定值 x的结点,如果表空,返回 0 i

23、nt n=0; LinkedNode * p=L-link; /从第一个结点开始检测 while(p!=NULL) /循环,想结点存在 if(p-data=x)n+; /找到一个,计数器加 1 p=p-link; /检测下一个结点 return n; (4).建立函数 Create：根据一维数组 an建立一个单链表，使单链表中各元素的次序与 an中各元素的次序相同，要求该程序的时间复杂度为 O(n)。（分数：4.00）_正确答案：()解析：实现从一维数组 an建立单链表的函数 void Create(LinkList L=rear=new LinkedNode; /创建表头结点 for(int

24、 i=0;in;i+) rear-link=new LinkedNode; /链入一个新结点,值为 ai rear=rear-link; /rear 指向链中尾结点 rear-data=Ai; rear-link=NULL; 采用递归方法实现时，需要通过引用参数将已建立的单链表各个结点链接起来。为此，在递归地扫描数组an的过程中，先建立单链表的各个结点，在推出递归时将结点的 p(被调用层的形参)带回上一层(调用层)的实参 p-link。 void Create(DataType a ,int n,int i,LinkedNode * else p=new LinkedNode; p-data=

25、Ai;p-link=NULL; /建立链表的新结点 createList(A,n,i+1,p-link); /递归返回时通过 p-link 链接 外部调用递归过程的语句为: L=new LinkedNode; /建立表头结点 Create(a,n,0,L-link); /递归建立单链表(5).整理函数 Tidyup：在非递减有序的单链表中删除值相同的多余结点。（分数：4.00）_正确答案：()解析：实现在非递减有序的单链表中删除值相同的多余结点的函数 void Tidyup(LinkList L) LinkedNode * p=L-link,temp; /检测指针 p指向首元结点 while(

26、p!=NULL delete temp; else p=p-link; /指针 p进到链表下一个结点 解析 针对带表头结点的单链表，试编写下列函数：已知 first为单链表的表头指针，链表中存储的都是整型数据，试写出实现下列运算的递归算法：（分数：12.00）(1).求链表中的最大整数。（分数：4.00）_正确答案：()解析：求链表中的最大整数 int Max(LinkedNode * first) /递归算法:求链表中的最大值 if(first-link=NULL)return first-data; /链表仅一个结点,其值即所求 int temp=Max(first-link); /否则递

27、归求后继链表中最大值 if(first-datatemp)return first-data; /再与首元之值比较取大者 else return temp; (2).求链表的结点个数。（分数：4.00）_正确答案：()解析：求链表的结点个数 int Num(LinkedNode * first) /递归算法:求链表中结点个数 if(first=NULL)return 0; /空链表结点个数为 0 return 1+Num(first-link);/否则求后继链表结点数再加 1(3).求所有整数的平均值。（分数：4.00）_正确答案：()解析：求所有整数的平均值 float Avg(Linked

28、Node * first,intreturn(float)(first-data); /其值即所求 else /否则 float Sum=Avg(first-link,n)*n; /先递归求后继链表的平均值 n+; /再计算总和 return(first-data+Sum)/n; 3.用单链表存储多项式的结构定义如下： Typedef struct Term /多项式的项 float coef; /系数 int exp; /指数 struct Term * link;/链指针 * Polynomial; 试编写一个算法，输入一组多项式的系数和指数，按指数降幂的方式建立多项式链表，要求该链表具有

29、表头结点。如果输入的指数与链表中已有的某一个项的指数相等，则新的项不加入，并报告作废信息。整个输入序列以输入系数为 0标志结束。算法的首部为 Polynomial createPoly()； （分数：4.00）_正确答案：()解析：本题程序使用了一些 C+的常用语句，如：“”输出符，“”输入符，“cout”输出到屏幕，“cin”从键盘输入，“endl”换行格式符，“new”动态存储分配。 Polynomial createPoly() struct pnode * head, * p, * pre, * s; float c;int e,i=0; cout ”建立一个多项式的单链表”endl;

30、 /提示 head=new Term; /创建表头结点和表头指针 head-exp=-1;head-link=NULL; /表头结点的 exp标志为-1 while(1) /创建结点 cout”输入第”+i”个项:”; /提示:输入第 i个项 cince; /输入:c 系数,e 指数 coutendl; if(c=0)break; /输入系数为 0,退出 S=new Term;s-coef:c;s-exp=e; /创建结点 p=head;pre=NULL; /寻找按升幂插入的位置 while(p!=NULLp=p-link; if(p!=NULL elses-link=p;pre-link=s

31、; /按升幂插入 return head; 假设对于一个多项式(Polynomial) P(x)=a m-1 +a m-2 +a 0 用长度为 m的单链表表示为(t m-1 ，t m-2 ，t m-3 ，t 1 ，t 0 )。其中，m 是多项式 P(x)中非零项(term)的个数，每一个 t i (0im-1)是 P(x)的一个非零项，它由三个数据成员 coef、exp 和 link组成，coef 是系数(浮点型)，exp 是指数(整型)，link 是链接指针。各个项的指数 e i 按递减顺序排列：e m-1 e m-2 e 0 0。（分数：12.00）(1).试描述多项式的数据结构(m 可以

32、不出现在定义中)。（分数：4.00）_正确答案：()解析：一元多项式的结构定义： Typedef struct Term float coef;int exp; struct Term * link: * Polynomial;(2).给出在多项式中插入新项的算法 Insert。该算法的功能是：如果多项式中没有与新项的指数相等的项，则将此新项插入到多项式链表的适当位置；如果多项式中已有与新项的指数相等的项，则将它们合并。（分数：4.00）_正确答案：()解析：多项式的插入算法： void Insert(Polynomial first,float c,int e) /在多项式链表 first中

33、插入系数为 c，指数为 e的新项 Term * pa=first, * pb=NULL; while(pa!=NULLpa=pa-link; if(pa-exp=e) /多项式中有与新项指数相等的项 if(pa-coef+c!=0)pa-coef=pa-coef+c; /合并 elsepb-link=pa-link;delete pa; /或删除 else /多项式中无与新项指数相等的项 Term * pc=new Term; /创建 pc-exp=e,pc-coef=c; if(pb=NULL)pc-link=first;first=pc; /链接：在首部 elsepb-link=pc;pc

34、-link=pa; /链接:在链中 (3).利用这个插入算法给出多项式乘法的实现算法。（分数：4.00）_正确答案：()解析：多项式乘法的实现算法： void MUL(Polynomial pb=B;c=NULL; while(pb!=NULL) pa=A; while(pa!=NULL) Insert(c,pa-coef*pb-coef,pa-exp+pb-exp); pa=pa-link; pb=pb-link; 4.没有一个不带表头结点的单链表，表头指针为 head。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转。要求逆转结果链表的表头指针 head指向原链表的最后一个结点。 （分数：4.00）_正确答案：()解析：void Inverse (LinkList /空表无需逆转 LinkedNode * p=head-link, * pr=NULL; while(p!=NULL) head-link=pr; /逆转 he