数据结构基础题及答案da

1、第二章参考一、二、填空题（略）1、结点2、（） 3、前趋4、线性起始终端序号位置前趋 后趋前趋后趋5、线性后趋长度6、空表表长7、初始化 INITLA（L，X）求表长 LENGTH（L） 读表长 GET（L，i）定位 LOCATEINSERT（L，X，i） 删除 DELE，i）8、逻辑结构中相邻的结点在 9、b+（i-1）x k10、Ldataj=Ldataj-1结构中仍相邻11、nO(n)n/2O(n)12、L.dataj-2=l.dataj-113、n-1o(n)(n-1)/2O(n)14、i=115、O(n)16、L.last 17、单链表18、指针20、头结点21、首结点22、头结点i

2、L.last O(1)L.datai-1循环链表双链表19，单链表表结点尾结点头结点任何信息、特殊标志表长23、t=malloc(size)t-next=NULL24、p=haedp=p-next25、(p-next!=NULL)&(jnext!=NULL)&(p-data!=x)27、(p!=NULL)&(p-next!=NULL)p-next28、loc(size)p-next29、insert_lklist(head,x,I)I+n(n-1)/2O(n2)30、p=qp-next=NULLO(n)31、单向循环链表（简称循环链表）32、NULL头结点双向循环链表（简称双链表）33、双链表

3、34、字符数组赋值35、空非空字符36、长度相同子主37、非紧缩紧缩38、结点大小不属于字符集的特殊符号三、单项选择题1、2、3、4、5、6、7、8、9、 、 7、 、37、38、39、40、41、四、简答及应用1、线性表的数据元素的类型为 daype，则在语言上可用下述类型定义来描述顺序表：const maxsize=顺序表的容量；typedef struct daypedatamaxsizelast;sqlist;sqlist L;数据域 data 是一个一维数组，线性表的第 1，2，n 个元素分别存放在此数组的第 0，1，last-1 个分量中，数据域 last 表示线性表当前的长度，而

4、 last-1 是线性表的终端结点在顺序表中的位置。常数 maxsize 称为顺序表的容量，从 last 到 maxsize-1为顺序表当前的空闲区（或称备用区）。Sqlist 类型完整地描述了顺序表的组织。L 被说明为 sqlist 类型的变量，即为一顺序表，其表长应写为 L.last，而它的终端结点则必须写为 L.dataL.last-1。2、假设数据元素的类型为 da ype。单链表的类型定义如下：typedef struct struct nodeda po;node *poerype data;ernext;typedef poerlklist;其中，ponter 是指向 struc

5、t node 类型变量的指针类型;struct node 是结构体类型规定一个结点是由两个域 data 和 next 组成的，其中 data 的结点的数据域,next是结点的链域；lklist 与 poer 相同类型，用来说明头指针变量的类型，因而 lklist也就被用来作为单链表的类型。3、typedef struct dnodestruct dnode*dpoer;da dpoerypedata;rior,next;typedaf dpdlklist;链域 prior 和next 分别指向本结点数据域 data 所含数据元素的直接前趋和直接后继所在的结点。所有结点通过前趋和后继指针双向循环

6、链表。在一起，再加上起标识作用的头指针，就得到4、顺序串的类型定义与顺序表类似，可描述如下： const maxlen=串的最大长度typedef structcharaxlencurlen;string 5、链串的类型定义为：const nodesize=用户定义的结点大小;typedef struct node *poer;struct nodechar chnodesize poinernext;typedef poer strlist;当结点大小为 1 时，可将 ch 域简单地定义为：char ch6、head 称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指针

7、变量是用于存放头指针的变量。为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。头指针变量的作用：对单链表中任一结点的，必须首先根据头指针变量中存放的头指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头指针变量具有标识单链表的作用，故常用头指针变量为命链表。头结点的作用：头结点的数据域可以不任何信息，也可以存放一个特殊标志或表长。其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理7、循环单链表、循环双链表。起来。8、空串和空格串：含 0 个字符

8、的串称为空串，其长度为 0。空格串是含有一个或多处空格字符组成的串，其长度不为 0。串变量和串常量：串常量在程序的执行过程中只能行过程中是可以改变和重新赋值的。不能改变而串变量的值在程序执主串和子串：一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所以子串的主串。串变量的名字与串变量的值：串变量的名字表示串的标识符；串变量的值表示串变量的字符序列。9、(a)A+B(b)B+A (c)D+C+BSUBSTR(B,3,2)SUBSTR(C,1,0)“mule”“mule” “myoldmule” “le”“”2203“myold” “mule”“me”“mule”(f)LENG)LE

9、NGTH(D)INDEX(B,D)INDEX(C,”d”)INSERT(D,2,C)INSERT(B,1,A)DELETE(B,2,2)DELETE(B,2,0)10、REPLA五、算法设计,SUBSTR(T,7,1),SUBSTR(T,3,1);CONCAT(S,”y”);1、 分析：(1)当 A、B 表都不为空时，比较 A，B 表中各元素对应位置的内容的大小，进而判断A，B 的大小。(2)当 A，B 表都不为空时，且 A，B 表中各各元素对应位置的内容相同时，比较 A，B 的长度，进而判断A，B 的大小或是否相等。const maxsize=顺序表的容量;typedefstructdata

10、maxsizelast;sqlist; CMP_sqlist(sqlist A,sqlist B) for (i=0;(iA.last)&(IB.last);i+if(A.dataiB.datai)return(1);if(A.last= =B.last) return(0); else if(A.lastB.last) return(1);else return(-1);2、(1)定位 LOCA，X)在结点类单链表上实现的算法为：locate_lklist(lklist head,daype x)/*求表 head 中第一个值等于 x 的的序号，不存在这种结点时结果为 0*/p=head-n

11、ext;j=1;/*置初值*/while(p!=NULL)&(p-data!=x)p=p-next;j+/*未达表结点又未找到值等于 X 的结点时经，继续扫描*/if (p-data = =x) elsereturn(j);return(0);在无头结点的单链表上实现的算法为：Wlocaklist head,daype X)/*求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0*/p=head; j=1;while(p!=NULL)&(p-data!=x)/*置初值*/p=p-next;j+/*未达表结点又未找到值等于 X 的结点时经，继续扫描*/if( p-data

12、 = =X) elsereturn(j);return(0);(2)按序号查找find(L,i)在结点的单链表上实现的算法为：poerfind_lklist(lklist head , j=1; p=head-next;i);while(jnext; j+if(i= = j) return(p);elsereturn(NULL);在无头结点的单链表上实现的算法为：poerfind_lklist(lklist head ,i); j=1; p=head;while(jnext; j+ if(i= = j) return(p);elsereturn(NULL);(3)、在INSERT(L，X，i)

13、结点单链表上实现的算法为：void insert_lklist(lklist head,daype x,I)/*在表 haed 的第 i 个位置上一人以 x 为值的新结点*/p=find_lklist(head,i-1);/*先找第 i-1 个结点*/if(p= =NULL)reeor(“不存在第 i 个位置”)/*若第 i-1 个结点不存在，退出*/elses=malloc(size);s-data=x/*否则生成新结点*/s-next=p-next/*结点*p 在链域值传给结点*s 的链域*/p-next=s;/*修改*p 的链域*/在无头结点的单链表上实现的算法为：void Winser

14、t(lklist head,dataytpe X,i)/*在表 haed 的第 i 个位置上if(i=0) error(“idata=X;/*否则生成新结点*/ if(i= =1)s-next=head;head=s;else p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“in+1”);elses-next=p-next;p-next=s;(4)删除 DELD,i)在结点的单链表上实现的算法为：void delete_lklist(lklist head,i) /*删除表 head 的第 i 个结点*/p=find_lklist(he

15、ad,i-1)/*先找待删结点的直接前驱*/if(p!=NULL)&(p-next!=NULL)/*若直接前趋存在且待结点存在*/ (q=p-next; /*q 指向待删结点*/p-next=q-next/*摘除待结点*/;free(q);/*已摘除结点 q*/else error(“不存在第 i 个结点”)/*否则给出相关信息*/在无头结点的单链表上实现的算法为：void Wdeleklist head,i)/*删除表 head 的第 i 个结点，若该链表仅有一个结点时，赋该结点指针NULL*/if(inext;free(q); elsep=wfind_lklist(head,i-1);/*

16、找链表 head 中第 i-1 结点指针*/if(p!=NULL)&(p-next!=NULL)q=p-next; p-next=q-next; free(q); else error(“不存在第 I 个结点”)；3、 分析：从第一个结点开始wlength_lklist(lklist head)p=head;j=0;，只要是非空计数一次。/*求表 head 的长度*/while(p!=NULL)p=p-next;j+;return(j);/*回传表长*/4、 设 A,B,C 均为无头结点单链表分析：（1）当有序表 A，B 均非空时，找出两表中元素最小的一个元素，然后将此结点到 C 表中，重复上

17、述步骤。（2）当 A，B 两表有一个为空表时，将另一表中元素顺序地到 C 表中。到 C 表表头。（3）由于 C 按递减排序，因此在 C 表中Lklist Wlink_lklist(lklist A,lklist B) while(A!=NULL)&(B!=NULL)if(A-datadata)p=A;A=A-next; else元素时，应始终p-next=;if(A= =NULL) A=B;while(A!=NULL)p=A;A=A-next;p-next= return(C);5、 分析：（1）当有序表 A、B 均非空时，依次分别从A、B 表头部取下结点，C 表中。（2）当 A、B 两表有一

18、个为空表时，将非空表到 C 表尾部。设 A，B，C 均为结点的单链表lklist HB_lklist(lklist A,lklist B) C=A;A=A-next;B=B-next; /去除头结点 While(A!=NULL)&(B!=NULL)p-next=A;p=p-next;A=A-next; p-next=B;p=p-next;B=B-next;if(B= =NULL)&(A!=NULL) p-next=A;else if(A= =NULL)&(B!=NULL) p-next=B; Return(c);6、 分析：从有序表的尾部开始依次取元素与元素比较，若大于元素，此元素后移一位，再

19、取它前面一个元素重复上述步骤；则将待元素。Void CR(daype A,daype X, i=elenum-1;elenum)while(i=0)&Xnext;while(p!=NULL)&(p-datanext;/*查 X s=malloc(size);s-data=s;8、 (1)顺序表位置 q*/分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。Void NZ_sqlist(sqlist A)fori=0;inext; q-next=p;p=q;/*p 指向当前结点的前趋结点*/*将原单链表的元素依次取出到 q*/*再另一个单链表p 的头部*/s=p;/*s

20、 指向新单链表的第一个结点*/9、 分析：A 与 B 的交是指A 与 B 的相同部分元素，即那些在 A 中出现又在 B 中出现的元素。由于 A、B 是有序表，故从表头开始依次比较当前指针所指元素的值是否相同，若相同，在 C 表中该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复上述步骤，直到A，B 表中有一个表到表尾。(1)顺序表sqlist HDZ_sqlist(sqlist A,sqlist B) t=0;j=0;k=0;while(t=A.last-1)&(j=B.last-1) switchcase A.dataiB.dataj;j+;break;case A.datai

21、= =B.dataj;C.datak=A.datai;k+;i+;j+;break;C.last=k;Return(c );(2)单链表（设结点）lklist HDZ_lklist(lklist A,lklist B)C=initiate_lklist();r=C;p=A-next;q=B-next:; While (p!=null)&(q!=null) Switch case p-data data: p=p-next;break;case p-data data:case p-data=q-data;-next;break;s=malloc(size);s-data=p-data;s-ne

22、xt=r-next; r-next=s;r=s; p=p-next;-next;return(c);10.分析：在有序表B、C 中找出相同元素 X；若 X 在表A 中出现则删除，否则转；重复直到 B、C 表有一个表查找完毕。（1） 顺序表void ASBC_sqlist(sqlist A, sqlist B, sqlistI=0;j=0;k=0;while (jB.last)&(kC.last) switchcase B.datajC.datak:j+;break;case B.datajC.datak:k+;break;C)case B.dataj=C.datak:/*B、C 中找到相同元素

23、*/while(IA.last)&( A.dataI= A.last) return;if (A.dataI=B.dataj)/*在 A 中存在 B、C 表共有元素，删除*/for(t=I+1;tnext;q= A;pb= B -next;pc= C -next; while (pb!=null)&(pc!=null) switchcasepb-datadata: pb=pb-next;break;casepb-datadata: pc=pc-next;break;case pb-data= =pc-data:/* B、C 中找到相同元素*/if(pa= =null)return;if (pa

24、-data= =pb-data)/*在 A 中存在 B、Cq-next=pa-next;free(pa);pa=q-next; pb=pb-next;pc=pc-next;表共有元素，删除*/11分析设置两个指针，分别指向*S 及其后继，然后按循环链表特性，顺序往下查找*s 的直接前趋，找到后删除；void DELETE_Xlklist(lklist S)p=s; q=p-next; while (q-nest!=s) p=q;-next;p-next=s; free(q);12分析：在链表 L 中依次取元素，若取出的元素是字母，把它到字母 B 中，然后在 L中删除该元素；若取出的元素是数字，

25、把它到数字链 D 中，然后在 L 中删除该元素。继续取下一个元素，直到链表的尾部。最后 B、D、L 中分别存放的是字母字符、数字字符和其它字符。设原表有头结点、头指针 L，新建数字字符链D，字母字符链 B，其它字符链 R。 void DISM_lklist(lklist L,lklist D,lklist B,lklist R) D =malloc(size of( ); D -next= D; /*建 D 循环链表头结点*/ B =malloc(sizeof(char); B -next= B; /*建 B 循环链表头结点*/ p= L;q=p-next;while(q!=null)if(q

26、-datadata=0)p-next=q-next; /*在表 L 中摘除 q 结点*/q-next= D -next; D -next=q; /*将 q 结点D 中*/q=p-next;/*移动 q 指针*/else if (q-datadata=a)|(q-datadata=a)p-next=q-next; /*在表 L 中删除 q 结点*/q-next= B -next; B -next=q; /*将 q 结点B 中*/q=p-next;/*移动 q 指针*/else p=p-next;/*移动 q 指针*/p-next=L;R=L;/*使 R 为循环表*/13分析：使用一维数组，数组下

27、标表示元素的序号，数组值为 1 表示元素存在，数组值为 0 表示此元素不存在。若累加数组的下标大于 N，再从 1 开始继续累加数组值，直到所有元素都输出。Void JSP(n, k, an)for(I=0;In;I+) aI =1; j=0;for(I=0;In;I+)s=0;while (snext =null; t-prior=null; return(t);(2)定位（设含头结点） locate_dlklist (dlklist head, daypex)/*求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0 */p=head-next;j=1;/*置初值*/w

28、hile(p!=null)&(p-data!=x)p=p-next;j+;/*未达尾结点又未找到值等于 x 的结点时继续扫描*/if (p-data = = x) return (j);elsereturn (0);（3）（设含头结点）void insert_dlklist (dlklist head,daype x,I)/*在表 head 的第 I 个位置上一个以 x 为值的新结点*/p=head-next; j=1;/*先找第 I-1 个结点*/while (p!=null) &(jdata=x;/*否则生成新结点*/s-prior=p;s-next=p-next; p-next-prio

29、r=s;p-next=s;（4） 删除（设含头结点）void deldtd_dlklist(dlklist head,I) /*删除表 head 的第 i 个结点*/p=head-next;j=1; /*先找第 i 个结点*/ while(p!=null)&(jnext;j+;if(I!=j) error(“不存在第 I 个位置”)/*若第 i 个结点不存在，退出*/ if(p!=null)/*若直接前趋存在且待删结点存在*/p-prior-next=p-next;p-next-prior=p-prior;free(p);/*已摘除结点 p*/else error(“不在存在第 I 结点”)

30、/*否则给出相关信息*/15分析：首先在链表中查找元素值为X 的结点，若找到则让freq 域的值增 1；然后依次和它的前趋的freq 域值比较，若比前 freq 域值大，和前趋结点位置交换，直到比前趋结点的freq 域值小为止。Typedef struct dfnode*dfpoer; Struct dfnodedaype data;freq;dfporior,next;typedef dfpoer dflklist;设该双链表含头结点。LOCATE_dflklist(dflklist L,daype X)/*定位值等于 X 的结点*/ p=L-next; I=1;while (p!=null)&(p-data!=X)o=p-next; I+;if (p-data!=X|(p= = null) error(“不存在值为 X 的结点 ”); else p-freq+;/*令元素值为 X 的结点中freq 域的值增 1*/q=p-prior;while(q!= L)&(q-freqfreq)I=I-1;p-prior-next=p-next; /*摘除 p*/ p-next-prior=p-prior;q-prior-prior=q-prior; p-next=q;prior=p;