2019年宁波大学数据结构与程序设计考研真题917

宁波大学2019年硕士研究生招生考试初试试题(A卷)(答案必须写在考点提供的答题纸上) 科目代码： 917 总分值： 150 科目名称： 数据结构与程序设计数据结构部分（75分）一、单选题：（每小题2分，10小题，共20分）1、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（　）A．3，2，6，1，4，5B．3，4，2，1，6，5C．1，2，5，3，4，6D．5，6，4，2，3，12、若用邻接矩阵 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示一个有向图，则其中每一列包含的″1″的个数为（　）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目3、下列二叉树中，()可用于实现符号的不等长高效编码。A.最优二叉树B.B-树C.平衡二叉树D.二叉排序树4、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（　）A．iB．i+1C．n-iD．n-i+15、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（　）A．f,c,bB．f,d,bC．g,c,bD．g,d,b6、设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。A．快速排序B.堆排序C.归并排序D.插入排序7、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（　）A.选择排序B.快速排序C.冒泡排序D.插入排序8、有n个结点的有向完全图的弧数是（　　）A.n2B.2nC.n(n-1)D.2n(n+1)9、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（）A．求关键路径的方法B.求最短路径的Dijkstra方法C.深度优先遍历算法D.广度优先遍历算法10、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）A.s→link=p→link;p→link=s;B.p→link=s;s→link=q;C.p→link=s→link;s→link=p;D.q→link=s;s→link=p;二、简答题（每题5分,5题，共25分）1.一颗二叉树的前序遍历的结果是1，2，3，4，5，6,中序遍历的结果是3，2，4，6，5，1。请画出这颗二叉树。2.请用Prim算法画出右图最小生成树的生成过程。3.请根据输入序列{1002867213054180110138}构造二叉查找树。如果删除元素28，那么二叉树又是如何？4.什么是B-树？有何特点？就下列关键字序列，画出一棵5阶B-树。（20，54，69，84，71，30，78，25，93，41，7，76）5.假设用于通信的电文仅由6个字符组成，其频率分别为：11，9，13，15，29，23。试为这6个字符设计哈夫曼编码，要求画出相应的哈夫曼树。三、算法填空（每空2分，共18分）1.以下程序实现按递减序对R[0]～R[n-1]进行直接选择排序。请在空白处填写代码。voidselectsort(intR[]){inti,j,k,temp;for(i=0;i<【1】;i++){k=i;for(j=i+1;j<=n-1;j++)if(R[j]【2】R[k])k=j;if（k!=i）{temp=R[i];R[i]=R[k];R[k]=temp;}}}}2．已知一个单链表L,函数converse倒置该链表的结点，请在空白处正确填写代码。StructSLNode{DateTypedate;【1】;};voidconverse(SLNode*head){SLNode*q,*p=head->next;head->next=NULL;while(__【2】__){__【3】__;p=p->next;__【4】____;head->next=q;}}3．以下是拓扑排序算法的部分代码，请在空白处填写代码。typedefstructArcNode{intadjvex;/*该弧指向顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/OtherInfoinfo;/*与该弧相关的信息*/}ArcNode;typedefstructVertexNode{VertexDatadata;ArcNode*firstarc;}VertexNode;typedefstruct{VertexNodevertex［MAX-VERTEX-NUM］;intvexnum,arcnum;/*图的顶点数和弧数*/GraphKindkind;}AdjList;intTopoSort(AdjListG){StackS;intindegree［MAX-VERTEX-NUM］;inti,count,k;ArcNode*p;FindID(G,indegree);/*FindID函数求各顶点入度*/InitStack(&S);/*初始化辅助栈*/for(i=0;i<G.vexnum;i++)if(【1】)Push(&S,i);count=0;while(!StackEmpty(S)){Pop(&S,&i);printf(″%c″,G..vertex［i］.data);count++;p=G..vertex［i］.firstarc;while(p!=NULL){【2】indegree［k］--;if(indegree［k］==0)Push(&S,k);【3】}}/*while*/if(count<G..vexnum)return(Error);/*该有向图含有回路*/elsereturn(Ok);}四、应用设计题（共12分）1.设计在链式存储结构上交换二叉树中所有结点左右子树的算法。（4分）2．给定n个城镇之间的交通图，若城镇i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个城镇中选择一个城镇建一所消防站，问这所消防站应建在哪个城镇，才能使离消防站最远的城镇到消防站的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（8分）  程序设计部分（75分）一、选择题（共40分，每题2分）1、在函数调用时，以下说法正确的是。A)函数调用后必须带回返回值B)实际参数和形式参数可以同名C)函数之间的数据传递不可以使用全局变量D)主调函数和被调函数总是在同一个文件里2、为表示关系x≥y≥z，应使用C语言表达式。A)(x>=y>=z)B)(x>=y)AND(y>=z)C)(x>=y)&&(y>=z)D)(x>=y)&(y>=z)3、假设var1,var2,var3,var4,var5是5个整形变量，有如下函数调用语句：func(var1,var2+var3,var4,var5)；该函数调用语句中，含有的实参个数是。A)3B)4C)5D)64、函数fseek(pFile，0L，SEEK_CUR)中的SEEK_CUR代表的起始点是。A)文件开始B)文件末尾C)文件当前位置D)以上都不对5、关于链表，下面说法正确的是。A)链表不能在表头插入元素或者删除元素B)链表支持随机存取C)链表中各元素的物理地址连续D)链表属于动态数据结构6、以下选项中，当x为奇数时，值为0的表达式是。A)x%2==1B)x/2C)x%2!=0D)x%2==07、能正确表示逻辑关系“”的C语言表达式是。A)a>=10ora<=0B)a>=0|a<=10C)a>=10&&a<=0D)a>=10||a<=08、若intx=1，y=6，z=2则表达式x<z?y：z的结果是。A)2B)1C)6D)09、以下程序段的输出结果是。inta=20,b=30,c;if(a>b)c=a;a=b;b=a;printf("a=%d,b=%d\n",a,b);A）a=30,b=30B）a=20,b=30C）a=30,b=20D）a=20,b=2010、设有数组定义“chararray[]="China";”，则数组array所占空间为。A)4个字节B)5个字节C)6个字节D)7个字节11、在嵌套使用if语句时，C语言规定else总是。A)和之前与其具有相同缩进位置的if配对B)和之前与其最近的if配对C)和之前与其最近的且不带else的if配对D)和之前的第1个if配对12、以下叙述正确的是。A)do-while语句构成的循环不能用其它语句构成的循环来代替。B)do-while语句构成的循环只能用break语句退出。C)用do-while语句构成的循环，在while后的表达式为非零时结束循环。D)用do-while语句构成的循环，在while后的表达式为零时结束循环。13、以下程序段的执行结果是。inti,sum;for(i=1;i<=3;sum++)sum+=i;printf(“%d\n”,sum);A)6B)3C)死循环D)014、以下程序段的输出结果是。inti,s=0;for(i=1;i<10;i+=2)s+=i+1;printf("%d\n",s);A)自然数1~9的累加和B)自然数1~10的累加和C)自然数1~9中的奇数之和D)自然数1~10中的偶数之和15、以下程序段的执行结果是。intx=23;do{printf(“%d”,x--);}while(!x);A)2322...1B)23C)不输出任何内容D)陷入死循环16、下列叙述中正确的是。A)break语句只能用于switch语句中B)continue语句的作用是使程序的执行 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 跳出包含它的所有循环C)break语句只能用在循环体和switch语句内D)在循环体内使用break语句和continue语句的作用相同17、下面能正确定义一维数组的选项是。A)inta[5]={0,1,2,3,4,5};B)inta[5]=5;C)inta[N]={1,2,3};D)inta[5]={3};18、有以下程序：#include<stdio.h>structS{inta,b;}data[2]={10,100,20,200};intmain(){structSp=data[1];printf("%d\n",++(p.a));return0;}程序运行后的输出结果是。A)10B)11C)20D)2119、下面的程序输出的结果是。#include<stdio.h>#defineABC(x)x*xintmain(){inta=3;printf("%d\n",ABC(a+1));return0;}A)7B)ABCC)4D)1620、要求函数的功能是交换两个整型变量的值，且通过调用正确返回交换的结果。能正确执行此功能的函数是。A)voidswap(int*x,int*y){int*p;*p=*x;*x=*y;*y=*p;}B)voidswap(intx,inty){intt;t=x;x=y;y=t;}C)voidswap(int*x,int*y){*x=*x-*y;*y=*x+*y;*x=*y-*x;}D)以上都不行二、程序阅读题（共9分，每题3分）1、写出程序运行结果。#include<stdio.h>voidfun(chars[]){char*p=s;while(*p)if((*p>='0')&&(*p<='9'))p++;else*s++=*p++;*s='\0';}intmain(){charitem[100]="hello123world78";fun(item);printf("Thestring:%s\n",item);return0;}2、写出程序运行结果。#include<stdio.h>intmain(){intna,nb;for(na=1,nb=1;na<=100;na++){if(nb>=20)break;if(nb%3==1){nb+=3;break;}nb-=5;}printf("%d\n",na);return0;}3、写出程序运行结果。#include<stdio.h>inta=2,b=3;intmax(inta,intb){intc;c=a>b?a:b;return(c);}voidmax1(int*a,int*b){intc;if(*a>*b){c=*a;*a=*b;*b=c;}}intmain(){inta=4;printf("%d\n",max(a,b));max1(&a,&b);printf("%d%d\n",a,b);return0;}三、程序填空题（共16分，每空2分）1、已知两个整型数组f[]和g[]，它们的元素都已经从小到大排列，并且每个数组中的元素都是各不相同的。例如，f[]中可能是1，3，4，7，9；而g[]中可能是3，5，7，8，10。请填空完成以下程序算出这两个数组中有多少组元素是相等的。例如f[2]=g[1]=3,f[4]=g[3]=8。#include<stdio.h>intcoincidence_count(intf[],intg[],intm,intn){intindex_f,index_g;intcount;count=index_f=【1】;while(【2】&&index_g<n)if(f[index_f]<g[index_g])index_f++;elseif(【3】)index_g++;elsecount++,index_f++,index_g++;【4】;}intmain(){intx[]={1,2,4,7,9,12,13,15,16,20};intnx=sizeof(x)/sizeof(int);inty[]={4,5,7,8,9,10,11,13,16,19};intny=sizeof(y)/sizeof(int);printf("Thereare%dequalnumbers.\n",【5】);return0;}2、求所有不超过n(取n<256)数中，其平方具有对称性质的数(回文数)。请填空完成以下程序。#include<stdio.h>intmain(){intm[16],n,i,t,count=0;inta,k;for(n=1;n<256;n++){k=0;t=1;【1】;for(i=1;a!=0;i++){【2】a/=10;}for(;i>1;i--){【3】;t*=10;}if(k==n*n)printf("%2d%10d%10d\n",++count,n,n*n);}return0;}四、编程题（共10分）根据数论的知识可知，任何一个合数都可以写成几个质数相乘的形式，这几个质数叫做这个合数的质因数。例如：24=2×2×2×3。现在从键盘输入一个正整数n(n<10000)，请编程输出它的所有质因数。第1页共11页_1234567890.unknown