2018考研847c语言复习题及答案

2018考研847c语言复习题及答案一.选择题.以下运算符中优先级最高的是(B)。A.&&B.+C.!=D.?：.C语言中运算对象必需是整型的运算符是(C)〇(A)+ (B)/ (C)% (D)*.已知x=4.5,y=2.5»求表达式(x+y)/2+(int)y%(int)x的值(D)。A)3 B)5C)3.5D)5.54、给出以下定义:characX[]="abcdefg";characY[]=则正确的叙述为(c)A)数组acX和数组acY等价B)数组acX和数组acY的长度相同C)数组acX的长度大于数组acY的长度D)数组acX的长度小ア数组Y的长度5、voidexample(characHello[]){printf("%d",sizeof(acHello));return;}voidmain(){ characHello[]="hello"; example(acHello);return; }的输出是(a)A4 B5 C6D不确定6、若有以下类型说明语句:charw；intx；floaty,z；则表达式w*x+z-y的结果为_D类型。A)floatB)charC)intD)doublemain(){floatx=123.456：printf(“%・5.2f\n”,x)；}以上程序输出的结果是ーB。A)123.4 B)123.5 C)123.45 D)123.468、下面语句的输出结果是_C。Printf("%d\n",strlen("\t\"\065\xff\n"))；A)14 B)8 C)5 D)输出项不合法,无正常输出9、18.请读程序段:charstr[]="ABCD",*p=str；printf("%d\n",*(p+4))；程序段的输出结果是Bー〇

A)68B)0 C)字符，A)68B)0 C)字符，D・的地址D)不确定的值10.若有定义:inta[4][10]；,则以下选项中对数组元素引用错误的是_B0(0<=i<4,0<=j<10)A)*(&a[0][0]+10*i+j) B)*(a+i)+j C)*(*(a+i)+j) D)*(a[i]+j)二.填空题:1.若有定义intm=5,y=2,则执行表达式y+=y-=m*=y后,y的值为 -16..若有定义:inta[卜｛2,4,6,8,10,12｝,*p=a;则・(p+l)的值是ー4—..文件函数eof读到末尾,标志是(-1).运算符的优先顺序,最高的算术运算符,最低的是(赋值运算符)5.假设所有变量均为整型,则表达式(x=2,y=5,y++,x+y)的值是(8)。6.若有定义:charc= 则变量c中包含的字符个数为ー1ー。.设有定义语句:inti=3;floatf=456.789;则表达式1.2+i+“A”+f值的数据类型是 double 〇8设有:inta=l,b=2,c=3,d=4,m=2,n=2;执行(m=a>b)&&(n=c>d)后n的值为(2)〇.已知intx=10,y=20,z=30;以下语句执行if(x>y)z=x;x=y;y=z:后x,y,z的值是(x=20,y=30,z=30)10.定义：chararray[]=｛で,'才｝;数组array占用的内存空间是(6)个字节。三.阅读程序题.下列程序运行的结果〇voidmain()｛intx=5;(intx=3;printf("％d”,x);)printf("％d”，x);.下列程序运行的结果〇voidmain(){intx=1,y=2,z=3;x=y+z;y=x+z;printf("％d”，x<y?x:z);).下列程序运行的结果〇需要冷静的想想voidmain(){inti,j,n=5;inta[][3]={l,2,3,4,5,6,7,8);=a[l][2]/5;j=n-i*3;printf(ua[%d][%d]=%d”,i,j,a[i][j]);3.下列程序运行的结果〇voidmain(){inta[9]=)l,6,-3,2,5,8,7,10,4);intx=a[0];for(inti=0;i<9;i++){if(a[i]>x){x=a[i];}printf("％d”,x);}5.下列程序运行的结果〇intf(char*s){char*p=s;While(*p!=,\0,)p++;return(p-s);)voidmain(){printf("％d“，f("ABCDEF'))答案:1.35 2.5 3.a[l][2]=6 4.10 5.6四.编程题部分1在歌星大奖赛中,有10个评委为参赛的选手打分,分数为l~100分。选手最后得分为:去掉ー个最高分和一个最低分后其余8个分数的平均值。请编写ー个程序实现选手最后得分。程序说明与注释#include<stdio.h>voidmain(){intinteger/,max,min,sum;max=-32768; /・先假设当前的最大值max为C语言整型数的最小值7min=32767; /*先假设当前的最小值min为C语言整型数的最大值sum=0;/・将求累加和变量的初值置为0・/for(i=l;i<=10;i++)sum=0;printf("lnputnumber%d=",i);scanf("%d",&integer); /*输入评委的评分ッsum+=integer;/・计算总分・/if(integer>max)max=integer;/・通过比较筛选出其中的最高分*/if(integer<min)min=integer;/・通过比较筛选出其中的最低分・/}printf("Canceledmaxscore:%d\\nCanceledminscore:%d\\n",max,min);printf("Averagescore:%d\\n",(sum-max-min)/8);/・输出结果・/2.有1、2、3、4个数字,能组成多少个互不相同且无重复数字的三位数?都是多少?main(){intij,k；printf("\n”)；for(i=l;i<5;i++){/・以下为三重循环ッfor(j=l；j<5;j++){for(k=l;k〈5;k++){if(i!=k&&i!=j&&j!=k)/・确保i、j、k三位互不相同・/printf("%d,%d,%d\n”,i,j,k);)数据结构部分ー选择题.ニ叉树的第k层的结点数最多为(D).A.2k-lB.2K+1C.2K-1D.2卜,.若有18个元素的有序表存放在ー维数组A[19]中,第一个元素放A⑴中,现进行二分查找,则查找A[3]的比较序列的下标依次为( D)A.1,2,3 B,9,5,2,3C.9,5,3 D.9,4,2,3.设有6个结点的无向图,该图至少应有(A )条边才能确保是ー个连通图。A.5 B.6 C.7 D.8.设某完全无向图中有n个顶点,则该完全无向图中有(A)条边。(A)n(n-l)/2 (B)n(n-1) (C)n2 (D)n2-l.设某有向图中有n个顶点，则该有向图对应的邻接表中有(B)个表头结点。(A)n-1 (B)n (C)n+1 (D)2n-l.设ー组初始关键字记录关键字为(20,15,14,18,21,36,40,10),则以20为基准记录的ー趟快速排序结束后的结果为(A)。TOC\o"1-5"\h\z10, 15, 14, 18, 20, 36, 40, 2110, 15, 14, 18, 20, 40, 36, 21(〇 !0, 15, 14, 20, 18, 40, 36, 21(D) 15, 10, 14, 18, 20, 36, 40, 217.下列四种排序中(D)的空间复杂度最大。(A)插入排序 (B)冒泡排序 (C)堆排序 (D)归并排序8设某哈夫曼树中有199个结点,则该哈夫曼树中有(B)个叶子结点。(A)99 (B) 100 (〇 !01 (D)102.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为(B).(A)5,3,4,6,1,2 (B) 3,2,5,6,4, 1(〇3,1,2,5,4,6 (D) 1,5,4,6,2, 3.设无向图G中的边的集合E={(a, b), (a, e),(a,c),(b, e), (e,d),(d,f),(f,c)},则从顶点a出发进行深度优先遍历可以得到的ー种顶点序列为(c)。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc二、计算题.某序列{a.h,b,d,e,f,k,c,i,s},请用ニ叉排序树的方法,画出按顺序构造ニ叉树图。字母大小按ASCII码值比较。.无向图G中有abcdef几个顶点:a—b(2),b—c(l),a—c(8),c—d(5),c—e(2),c—f(4),f—e(8),括号内为毎条边的权值。1)画出邻接表。2)根据画出的邻接表,写出进行深度优先遍历序列。3)用普里母算法,构造最优解。.某系统中使用最频繁的字符序列有。,1,2,3,4,5,6,7,8,9个字符构成,且每个出现的频率为2%,7%,15%,20%,30%,14%,5%,13%,10%,8%。请用哈夫曼构造字符编码。答案:11.温馨提示根据ニ叉排序树的性质:(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;(3)左、右子树也分别为ニ叉排序树:注意:了解字母的ASCI!码值大小以及按顺序构造二叉树图解：(做完检查一下对不对)12.1)2)过程如下:

湾晨优九通れ方オ:缸ー・b湾晨优九通れ方オ:缸ー・b—»C—5>¢1->j—ラ已句①网“我上aソリ~4-cd.«J.,№<30回ノユル及2ル七恥U-fn.ljV-M-/c,A.e,-jjクなJtLe工"匐ワ“7々,/,匕/レーリリe,d大ゆ々诙殳乙R園Mレ“/。,ふ。已<Vー入f九J/国枷XXプ多恥4つa,んc,eゴ/ノーひ:")/KJメ,と切在リワ，ん乙eゼスノ"U7)k九加入。国出<〇心ヽ@ド<〇心ヽ@ド13,根的左边是0,右边是1,得到的哈夫曼字编码是如表所示(图有可能不一样,但最终的编码都是ー样的)0(2%),1(7%),2(12%),3(20%),4(15%),5(13%),6(4%),7(9%),8(10%),9(8%)字符哈夫曼编码0011100101111201103004105010601110171111811091110三、编程题1设计ー个算法,写ー个函数让链表逆序方法一:voidinverse(LinkList&L){ /Z逆置带头结点的单链表Lp=L->next;L->next=NULL;while(p){q=p->next; //q指向・p的后继pー)next二L一〉next;L->next=p; //*p插入在头结点之后P=q；方法二:实现带头结点的单链表数据结点逆序连接的函数(pointer是指针)voidreverse(pointerh){pointerp,q;p=h->next; h->next=NULL;while(p!=null)〃链表未到尾就一直作{q二P；p=p->next;q->next=h->next;h->next=q!〃将当前结点作为头结点后的第一元素结点插入说明:红色部分一定要掌握。真题也一定要掌握,一定有原题或多或少。资料只在本群使用。2018学年第二学期期末考试试卷（A卷）あ料题型单选题概念填空题程序阅读题あ料题型单选题概念填空题程序阅读题程序填空题程序编写题总分分值3010202020100得分课程名称C语言程序设计课程编号88710102任课教师ー得分评阅人ー、单选题:（共30题,每题1分,共30分）1.已知intj,i=l;,执行语句j=-i++;后,j的值是()〇A.1B.2C.-1D.-22.在计算机内一切信息的存取、传输和处理都是以（A.ASCII码B.二进制C.十进制）形式进行的。D.十六进制3,将二进制数10110010的最高位求反的操作是（ ）〇A,与（7F）体按位与 B,与（7F）体按位异或C,与（80V。按位或 D.都不正确ー个C语言程序是由（ ）。A,ー个主程序和若干子程序组成C,若干过程组成B.函数组成D.若干子程序组成“京“(际)is.下列说法中正确的是（ ）«C程序书写时,不区分大小写字母C程序书写时，一行只能写ー个语句C程序书写时，ー个语句可分成几行书写C程序书写时每行必须有行号.C语言程序经过链接以后生成的文件名的后缀为（ ）。A..c B..obj C..exe D..cpp.下面四个选项中，均是不合法的用户标识符的选项是（ ）。A.AP_0do B.floatlaO_AC.b-asizeofint D.123tempint8.下面程序段输出结果是()〇inti=5,k;k=(++i)+(++i)+(i++);printf("%d,%dM,k,i);A.24,8 B.21,8C.21,7D.24,79.设变量n为float类型,m为int类型,则以下能实现将n中的数值保留小数点后两位,第三位委行四舍五入运算的表达式是( )〇A.n=(n*100+0.5)/100.0 B.m=n*100+0.5,n=m/100.0C.n=n*100+0.5/100.0 D.n=(n/100+0.5)*100.010.若有定义:intk=7,x=12;,则能使值为3的表达式是( )。A.x%=(k%=5) B.x%=(k-k%5)C.x%=k-k%5 D.(x%=k)-(k%=5)11.假设所有变量均为整型,则表达式(a=2,b=5,b++,a+b)的值是( )。A.7B.8 C.6 D.212.下面程序段执行后的输出结果是(inta=3366;printf("|%・08d|”,a);A.|-0003366|B.|00003366|)<,("□”表示一个空格)C.13366□ロロロ| D.输出格式非法13.有如下程序,该程序的输出结果是( )。voidmain()(intx=1,a=0,b=0;switch(x){case0:b++;a++;a++;b++;}printf("a=%d,b=%d\n",a,b);}A.a=2,b=1B.a=1,b=1C.a=1,b=0D.a=2,b=214.对于条件表达式(k)?(i++):(i--)来说,其中的表达式k等价于( )。A.k==0B.k==1C.k!=0D,k!=115.下面程序段的运行结果是( )°x=y=0;while(x<15)y++,x+=++y;nrintfC，0AHvyV.设有数组定义:chararray[]="China";则数组array所占的空间为( ).A.4个字节B.5个字节C.6个字节D.7个字节.以下程序的输出结果是( )voidmain()(charst[20]="hello\0\t\\\w;printf(%d%d\nH,strlen(st),sizeof(st));}A.99 B.520 C.1320 D.2020.有以下程序,程序运行后的输出结果是()〇intf(intn)(if(n==1)return1;elsereturnf(n-1)+1;}voidmain()(inti,j=0;for(i=1;i<3;i++)j+=f(i);printf("％d\n"，j);}A.4B.3C.2D.1.以下程序的输出结果是( )。voidmain()(char*p="abcdefgh"，*r;long*q;q=(long*)p;q++；r=(char*)q;printf("%s\nH,r);}A.bcdefghB.cdefghC.defghD.efgh.从下列选项中选择不会引起二义性的宏定义是( )。A.#definePOWER(x)x*x B.#definePOWER(x)(x)*(x)C.#definePOWER(x)(x*x) D.#definePOWER(x)((x)*(x)).以下能对二维数组a进行正确初始化的语句是( )。AintAF21F1=H101W52ふシ RintH1⑶ニ，牛14AAB-22.以下程序的输出结果是( )。voidmain()(chararr[2][4];strcpy(arr[O],"you");strcpy(arr[1],"me");arr[O][3]=printf("%s\n",arr);}A.you&me B.youC.meD.err23,以下正确的函数定义形式是（)oA.doublefun(intx,inty)B.doublefun(intx;inty)C.doublefun(intx,inty);D.doublefun(intx,y);.若用数组名作为函数的实参,传递给形参的是（ ）«A,数组的首地址 B.数组第一个元素的值C,数组中全部元素的值 D.数组元素的个数.若有说明:int*p,m=5,n;以下正确的程序段是( )。A.p=&n;scanf("%d",&p); B.p=&n;scanf("%d",*p)C.scanf("%d",&n);*p=n; D.p=&n;*p=m;.若有说明:inti,j=2,*p=&i;则能完成i=j赋值功能的语句是()〇A.i=*p; B.*p=*&j;C.i=&j; D.i=**p;.下面程序段的运行结果是()〇chars[]="abcdefgh",*p=s;p+=3;printf("%d\n",strlen(strcpy(p,"ABCD")));A.8 B.12C.4D,7.以下程序的运行结果是( )。#defineMIN(x,y)(x)<(y)?(x):(y)voidmain()(inti=10,j=15,k;k=10*MIN(i,j);printf("%d\n",k);

.根据下面的定义,能打印出字母M的语句是()〇structperson(charname[9];intage;}；structpersonclass[10]={“John”，17,“Paul”，19,“Mary”，18,”adam“，16};A.printf(”％c\n”，class[3].name); B.printf(”％c\n”，class[3].name[1]);C.printf(M%c\nM,class[2].name[1]); D.printf(*'%c\n",class[2].name[0]);.若要打开A盘上user子目录下名为abc.txt的文本文件进行读、写操作,下面符合此调用是()〇A.fopen("A:\user\abc.txt"，"r”) B.fopen("A:\\user\\abc.txt"，“r+”)得分评阅人C.fopen(”A:\user\abc.txt”，”rb”) D.fopen(”A:\\user\\abc.txt”，”w”)二、填空题:（共20个空,每个空格0.5分,共10理解下列概念,填写其中的空格。.每个C语言程序中有且只有一个函数,它是程序的入口和出口。.引用C语言标准库函数,一般要用预处理命令将其头文件包含进来.语句:x++;++x;x=x+1;x=I+x;,执行后都使变量x中的值增1,请写出一条同值语句（不得与列举的相同）。.C语言用表示假，表示真。.C语言中实现循环结构的控制语句有语句、语句和语向.在C语言程序中,功能模块是由函数来实现的。函数是序段。.对带有参数的函数进行调用时，参数的传递方式主要有调用和式。得分评阅人三、程序阅读题:（共5题,每题4分,共20分）阅读下列各小题的程序,试写出各小题的输出结果。1、下面程序的输出结果是。voidmain()(inta,b;for(a=1,b=1;a<=100;a++)(if(b>=10)break;if(b%3==1){b+=3;continue;}}printf("a=%d\n'\a);2、以下程序的输出结果是main()(inta=0,b=1Ic=0,d=20；if(a)d=d-10；elseif(!b)if(!c)d=15；elsed=25：printf(Hd=%d\nH,d)；3.下面程序的输出结果是0voidsub(intx,inty,int*z){*z=y-x;}voidmain()(inta,b,c;sub(10,5,&a);sub(7,a,&b);sub(a,b,&c);printf(H%d,%d,%d\nH,a,b,c);).下面程序的输出结果是〇' #include<stdio.h>郑 intf(char*s)! {chat*p=s;while(*p!=へ0')p++;return(p-s);}voidmain(void)需 {printf("%d\n”,f("ABCDEド))；).下面程序的输出结果是。structst{intx;int*y;}*p;intdt[4]={10,20,30,40);structstaa[4]={50,&dt[O],60,&dt[O],60,&dt[O],60,&dt[O]};得分评阅人 四、程序填空题:（共10个空,每个空格2分,共 20分）阅读下列程序,填写程序中的空格。.下面程序的功能是把316表示为两个加数的和,使两个加数分别能被13和11整除。#include<stdio.h>voidmain()(inti=0,j,k;do{ ；k=316-13*i;}while(②);j=k/11;printf¢316=13*%d+11*%dM,i,j);}.下面程序段是从键盘输入的字符中统计数字字符的个数,用换行符结束循环。#include<stdio.h>voidmain()(intn=0,c;c=getchar();while(① )

3.4.下面程序的功能是统计文件中字符的个数。3.4./include<stdio.h>voidmain(void)longnum=0;①*fp；if(fp=fopen("fname.dat","r"))=NULL)printf("Cann'topenthefile!”);exit(0);while(②.fgetc(fp);num++;)printf(/znum=%d\n"num);fclose(fp);以下程序是实现在M行N列的二维数组中,找出每一行上的最大值。#defineM3#defineN4voidmain()得分评阅人 五、程序编写题:（共2题,每题10分,共20分）根据下列要求编写C语言程序完成其功能。.从键盘上输入任意正整数,编程判断该数是否为回文数。所谓回文数就是从左到右读这个数上右到左读这个数是ー样的。例如,12321、4004都是回文数。.下面的程序是计算ー组学生的平均成绩和不及格人数，请编写ave函数。structstu（intnum;〃学号char*name;〃姓名charsex; 〃性别floatscore;〃成绩}boy[5]={ {101,-Liping**；M',45},{102,"Zhangpingn,'M',62.5},{103,nHefang",F,92.5},{104,"Chengling"；F',87},{105,“Wangming",'M',58} };voidmain()答案一、单选题。（共30小题,每小题1分,共30分）1-5.CBABC6-10CCBBD11-15BCACD16-20CBBDD21-25BAAAD26-30BCBDB二、概念题。理解下列概念,填写其中的空格。（共20个空,每个空格0.5分,共分）main#includex+=1;0非〇forwhiledo-while，皿ー、单选题.深度为5的ニ叉树至多有(c)个结点A)16 B)32 C)31 D)10.ー个栈的入栈序列a,b,c,d,e,则不可能的出栈输出序列是(D)。A)edcba B)decba C)abcde D)dceab.在ー个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行(A).A)s->next=q->next;q->next=s;B)pつnext=sつnext;s->next=p;C)q->next=s;s->next=p;D)pウnext=s;sつnext=q;.由一个具有n个顶点的连通图生成的最小生成树中,具有(B)条边。A)nB)n-1C)n+1 D)2xn.若一个图的边集为{依ぶ),(れ。,笛ぶ),ヒ,ウ0疋),〇下)},则从顶点A开始对该图进行深度优先搜索,得到的顶点序列可能为(ABDEFC)。A)A,B,C,F,D,E B)A,C,F,D,E,BC)A,B,D,C,F,E D)A,B,D,F,E,C.假定对元素序列(7,3,5,9,1,12)进行堆排序,并且采用小根堆,则由初始数据构成的初始堆为(D)0A)1,3,5,7,9,12 B)1,5,3,9,12,7C)1,5,3,7,9,12 D)1,3,5,9,7,121,3,5,9,7,121.初始序列构造的堆为:7359112此时依据该序列进行自下而上的建堆过程:7]593121359712.若对n个元素进行归并排序,则进行每ー趟归并的时间复杂性为(C)。A)0(1)B)O(log2n)C)O(n) D)O(n2).从具有n个结点的ニ叉搜索树中查找一个元素时,在最坏情况下的时间复杂性为(C)oA)O(n)B)0(1)C)O(log2n)D)O(n2).深度为4的ニ叉树至多有(B)个结点A)8 B)15 C)16 D)31.ー个栈的入栈序列a,b,c,则不可能的出栈输出序列是(C)0A)abe B)cba C)cab D)bca.在ー个单链表中,p指向某ー结点,若要删除p所指向的结点的后继结点,则执行(D).A)pつnext=p->next;B)p=p->next;C)p->next=p;D)p->next=p->nextウnext;.具有n个结点的连通无向图的生成树具有(A)条边。A)n-1B)n C)n+1 D)2xn.若一个图的边集为给产),(へ0,紡ぶ),(5),(。日,。»},则从顶点A开始对该图进行广度优先搜索,得到的顶点序列可能为()。A)A,B,C,D,E,F B)A,C,F,D,E,BC)A,B,D,C,F,E D)A,B,D,E,F,C.假定对元素序列(9,157,3,6)进行堆排序,并且采用小根堆,则由初始数据构成的初始堆为()1,A)9,1,5,7,3,6 B)1,5,3,9,6,7C)1,3,5,6,7,9 D)1,3,5,7,9,6.若对n个元素逬行快速排序,则逬行每ー趟的时间复杂度为()。A)0(1)B)O(log2n)C)O(n) D)O(n2).请指出下面二元组表示的数据结构属于何种结构。(B)D=(K,R)K=(1,2,3,4,5)R={(1,2),(1,5),(2,3),(2,4)}A)线性表B)树C)集合D)图).在ー个长度为n的顺序存储的线性表中,向第i个元素(l<i<n+l)之前插入ー个新元素时,需要从后向前依次后移(B)个元素。A)n-iB)n-i+1C)n-i-1 D)i.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为(D工A)r-f B)(n+f-r)%nC)n+r-f D)(n+r-f)%n.若一棵ニ叉树共有1001各结点,且无度为1的结点,则叶结点的个数为(DIA)498 B)499 C)500 D)501.含n个顶点的连通图中的任意一条简单路径,其长度不可能超过(C1A)1 B)n/2 C)n-1 D)n.对以下数据序列利用快速排序进行排序,速度最快的是(CIA){21,25,5,17,9,23,30} B){25,23,30,17,21,5,9}C){21,9,17,30,25,23,5} D){5,9,17,21,23,25,30)二、计算题。.假定一个线性表为（20,12,14,18,32,24,30,10,38,26）,画出按线性表中元素的次序生成的一棵ニ叉排序树,求出其平均查找长度。.下图所示为一个无向连通网络,试回答下列问题:1）画出该图的邻接表;）写出根据该邻接表从结点A出发,按深度优先的方式进行遍历的结点顺序;）根据prim算法构造出它的最小生成树。.假定用于通信的电文由6个字母A,B,C,D,E,F组成,各字母在电文中出现的概率为15%,35%,13%,7%,20%,10%,试为这6个字母设计哈夫曼编码。.空堆开始依次向堆中插入线性表（64,52,12,48,45,26）中的每个元素,请以线性表的形式给出每插入ー个元素后堆的状态。（为小根堆）.请对下图的无向带权图，写出它的邻接矩阵,并按普里姆算法求其最小生成树。

1.邻接矩阵ABCDEFGHA043・・ー・・B40559--C3505---5D-5507654TOC\o"1-5"\h\zE- 9 - 7 0 3 --F--- 6 3 0 2 -G- - - 5 - 2 0 6H- - 5 4 - - 6 02.邻接表A|BCB|ACDEC|ABDHD|BCEFGHE|BDFF|EDGG|DFHH|CDG

选择原点为AA-CA-BICA-BIC-DA-BIC-D-HA-BIC-D-HIGA-BIC-D-HIGIF-E总距离:26E-FE-FA-CE-FA-CD-HE-FD-HB-A-CB-A-CG-D-HE-FB-A-C-H-D-GE-FB-A-C-H-D-G-F-E总距离:266,已知一棵ニ叉树的静态数组表示(即顺序存储)如下,其中一1表示空,请分别写出该ニ叉树的先序、中序、后序遍历序列。0 12 34 5 67 8 9 101112|20|8|46|5|15|30|-1|-1|-1|10|18|-1|35|.已知一组记录为(256,301,751,129,937,863,742,694,076,438),给出采用快速排序法进行排序时每ー趟的排序结果。快排后的各次排序如下:256,301,751,129,937,863,742,694,76,438256,301,751,129,438,863,742,694,76,937256,301,76,129,438,863,742,694,751,937

256,129,76,301,438,863,742,694,751,93776,129,256,301,438,863,742,694,751,93776,129,256,301,438,863,742,694,751,93776,129,256,301,438,863,742,694,751,93776,129,256,301,438,863,742,694,751,93776,129,256,301,438,694,742,863,751,93776,129,256,301,438,694,742,863,751,93776,129,256,301,438,694,742,751,863,93776,129,256,301,438,694,742,751,863,93776,129,256,301,438,694,742,751,863,937.假定一个线性表为(38,52,25,74,68,16,30,54,90,72),画出按线性表中元素的次序生成的一棵ニ叉排序树,求出其平均查找长度。.下图所示为ー个无向连通网络,试回答下列问题:1）画出该图的邻接表;2）写出根据该邻接表从结点1出发,按深度优先的方式逬行遍历的结点顺序;3）根据prim算法构造出它的最小生成树。10.假定用于通信的电文由8个字母A,B,C,D,E,F,G,H组成,各字母在电文中出现的概率为5%,25%,4%,7%,9%,12%,30%,8%,试为这8个字母设计哈夫曼编码。三、填空题。理解下列概念,填写其中的空格。.在ー个链式队列中,若队头指针与队尾指针的值相同,则表示该队列至多有__1ー个结点。.ー棵树按照左孩子ー右兄弟表示法转换成对应的ニ叉树,则该ニ叉树中树根结点肯定没有一右一孩子。.n个顶点e条边的图采用邻接表存储,深度优先遍历算法的时间复杂度为O(n+e)0.设一棵完全ニ叉树有700个结点,则共有 350 个叶子结点。.折半查找有序表(4,6,10,12,20,30,50,70,88,100X若查找表中元素58,则它将依次与表中30,88,70,50/匕较大小,查找结果是失败。四、编程题。.对于结点类型为LinkNode的单链表,编写算法,统计出单链表中结点的值等于给定值x的结点数。structLinkNode{intdata;structLinkNode*next;}；intCount(LinkNode*HL,intx);intCountX(LNode*HL,日emTypex)inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;

}//CountX.编写算法统计ニ叉树T中有右孩子的内部结点的个数。structTreeNode{intdata;structTreeNode*LChild,*RChild;)；intCountRightNode(TreeNode*T);.对于结点类型为LinkNode的单链表,编写算法,统计出单链表中结点值为偶数的结点数目。structLinkNode{intdata;structLinkNode*next;)；intCount(LinkNode*HL);4,设两个单链表LI和L2分别表示两个集合,设计算法判断L1是否是L2的子集。函^^型:boolIsSubSet(Node*L1,Node*L2)5.编写在以BST为树根指针的ニ叉查找树上进行查找值为item的结点的非递归算法,若查找成功则由item带回整个结点的值并返回true,否则返回false。函数原型:boolFind(BTreeNode*BST,ElemType&item)typedefintElem-Iype;typedefstructbn{ElemTypeitem;structbn*left,*right;}BTreeNode;boolFind(BTreeNode*BST,ElemType&item)BTreeNode*now=BST;while(now)

if(item>now->item)now=now->right;elseif(item<now->item)now=now->left;elsereturntrue;)returnfalse;)给大家五套数据结构的习题,后面都附有答案,有些题目我已删去,但仍个别题目较难,请同学们在复习过程中根据自身情况选做,试题（一）ー、单选题.栈和队列的共同特点是（ ）〇A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点.用链接方式存储的队列,在进行插入运算时（）.A,仅修改头指针 B,头、尾指针都要修改 C.仅修改尾指针 D.头、尾指针可能都要修改.以下数据结构中哪ー个是非线性结构?（）A.队列 B.栈C.线性表D.ニ叉树.设有一个二维数组イ间［川,假设ハ⑼⑼存放位置在644（io）,厶⑵⑵存放位置在676（io）,/r/