宁波大学研究生入学试卷.doc

宁波大学2019年硕士研究生招生考试初试试题(A卷) (答案必须写在考点提供的答题纸上)科目代码： 917总分值： 150科目名称：数据结构与程序设计数据结构部分（75分）一、单选题：（每小题2分，10小题，共20分）1、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6 D5，6，4，2，3，12、若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（）A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数D图中连通分量的数目3、下列二叉树中，( )可用于实现符号的不等长高效编码。A. 最优二叉树 B. B-树 C. 平衡二叉树 D. 二叉排序树4、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为（）AiBi+1Cn-iDn-i+15、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）Af,c,bBf,d,bCg,c,bDg,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. slink = plink; plink = s; B. plink = s; slink = q;C. plink = slink; slink = p; D. qlink = s; slink = p;二、简答题（每题5分, 5题，共25分）1. 一颗二叉树的前序遍历的结果是1，2，3，4，5，6, 中序遍历的结果是3，2，4，6，5，1。 请画出这颗二叉树。 2. 请用Prim算法画出右图最小生成树的生成过程。 3. 请根据输入序列100 28 6 72 130 54 180 110 138构造二叉查找树。如果删除元素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. 以下程序实现按递减序对R0Rn-1 进行直接选择排序。请在空白处填写代码。void selectsort (int R ) int i, 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 倒置该链表的结点，请在空白处正确填写代码。 Struct SLNode DateType date; 【1】 ;void converse(SLNode * head) SLNode *q,*p= head->next; head->next=NULL; while(_【2】 _) _【3】_; p=p->next; _【4】 _; head->next=q;3以下是拓扑排序算法的部分代码，请在空白处填写代码。typedef struct ArcNode int adjvex; /*该弧指向顶点的位置*/ struct ArcNode *nextarc; /*指向下一条弧的指针*/ OtherInfo info; /*与该弧相关的信息*/ ArcNode; typedef struct VertexNode VertexData data; ArcNode *firstarc; VertexNode; typedef struct VertexNode vertexMAX-VERTEX-NUM; int vexnum, arcnum; /*图的顶点数和弧数*/ GraphKind kind; AdjList; int TopoSort (AdjList G) Stack S; int indegreeMAX-VERTEX-NUM; int i, 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.vertexi.data); count+; p=G.vertexi.firstarc; while(p! =NULL) 【2】 indegreek-; if(indegreek=0) Push(&S, k); 【3】 /*while*/ if (count<G.vexnum) return(Error); /*该有向图含有回路*/ else return(Ok); 四、应用设计题（共12分）1. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。（4分）2给定n个城镇之间的交通图，若城镇i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个城镇中选择一个城镇建一所消防站，问这所消防站应建在哪个城镇，才能使离消防站最远的城镇到消防站的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。（8分）程序设计部分（75分）一、选择题（共40分，每题2分）1、在函数调用时，以下说法正确的是 。 A) 函数调用后必须带回返回值 B) 实际参数和形式参数可以同名 C) 函数之间的数据传递不可以使用全局变量 D) 主调函数和被调函数总是在同一个文件里2、为表示关系xyz，应使用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= =1 B)x/2 C)x%2!=0 D)x%2= =07、能正确表示逻辑关系“”的C语言表达式是 。A)a>=10 or a<=0 B)a>=0|a<=10 C)a>=10&&a<=0 D)a>=10|a<=08、若int x=1，y=6，z=2 则表达式x<z?y：z的结果是 。 A)2 B)1 C)6 D)0 9、以下程序段的输出结果是 。int a=20,b=30,c;if(a>b)c=a;a=b;b=a;printf("a=%d,b=%dn",a,b);A）a=30,b=30 B）a=20,b=30 C）a=30,b=20 D）a=20,b=2010、设有数组定义“char array = "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、以下程序段的执行结果是 。int i,sum;for(i=1;i<=3;sum+) sum+=i;printf(“%dn”,sum);A) 6 B) 3 C) 死循环 D) 014、以下程序段的输出结果是 。int i,s=0;for(i=1;i<10;i+=2) s+=i+1;printf("%dn",s); A) 自然数19的累加和 B)自然数110的累加和C) 自然数19中的奇数之和 D) 自然数110中的偶数之和15、以下程序段的执行结果是 。int x=23;do printf(“%d”,x-); while(!x);A) 23 22 . 1 B) 23 C) 不输出任何内容 D) 陷入死循环16、下列叙述中正确的是 。A) break语句只能用于switch语句中 B) continue语句的作用是使程序的执行流程跳出包含它的所有循环C) break语句只能用在循环体和switch语句内D) 在循环体内使用break语句和continue语句的作用相同17、下面能正确定义一维数组的选项是 。A) int a5=0,1,2,3,4,5; B) int a5=5;C) int aN=1,2,3 ; D) int a5=3 ;18、有以下程序： #include <stdio.h> struct S int a,b; data2=10,100,20,200; int main() struct S p = data1; printf("%dn", +(p.a); return 0; 程序运行后的输出结果是 。A) 10 B) 11 C) 20 D) 2119、下面的程序输出的结果是 。#include <stdio.h>#define ABC(x) x * xint main()int a = 3;printf("%dn", ABC(a + 1); return 0;A) 7 B) ABC C) 4D) 1620、要求函数的功能是交换两个整型变量的值，且通过调用正确返回交换的结果。能正确执行此功能的函数是 。A) void swap(int *x, int *y) int *p; *p=*x ; *x=*y; *y=*p;B) void swap(int x , int y) int t; t=x; x=y; y=t; C) void swap(int *x, int *y) *x=*x-*y; *y=*x+*y; *x=*y-*x;D) 以上都不行二、程序阅读题（共9分，每题3分）1、写出程序运行结果。#include <stdio.h>void fun(char s) char *p=s; while(*p) if(*p>=0)&&(*p<=9) p+; else *s+=*p+; *s=0; int main( ) char item100="hello123world78" fun(item); printf("The string: %sn",item); return 0;2、写出程序运行结果。#include<stdio.h>int main() int na,nb; for (na=1,nb=1;na<=100;na+) if (nb>=20) break; if (nb%3=1) nb+=3;break; nb-=5; printf("%dn",na); return 0;3、写出程序运行结果。#include<stdio.h>int a=2,b=3;int max (int a, int b) int c; c=a>b?a:b; return (c);void max1 (int *a, int *b) int c; if (*a>*b) c=*a; *a=*b; *b=c;int main() int a=4; printf("%dn",max(a,b); max1(&a,&b);printf("%d %dn",a,b); return 0;三、程序填空题（共16分，每空2分）1、已知两个整型数组f和g，它们的元素都已经从小到大排列，并且每个数组中的元素都是各不相同的。例如，f中可能是1，3，4，7，9；而g中可能是3，5，7，8，10。请填空完成以下程序算出这两个数组中有多少组元素是相等的。例如f2=g1=3,f4=g3=8。#include<stdio.h>int coincidence_count(int f, int g, int m, int n) int index_f, index_g; int count; count = index_f = 【1】; while (【2】 && index_g < n) if (findex_f < gindex_g) index_f+; else if (【3】) index_g+; else count+, index_f+, index_g+; 【4】;int main( ) int x = 1, 2, 4, 7, 9, 12, 13, 15, 16, 20; int nx = sizeof(x)/sizeof(int); int y = 4, 5, 7, 8, 9, 10, 11, 13, 16, 19; int ny = sizeof(y)/sizeof(int); printf("There are %d equal numbers.n", 【5】);return 0;2、求所有不超过n(取n<256)数中，其平方具有对称性质的数(回文数)。请填空完成以下程序。#include<stdio.h>int main() int m16,n,i,t,count=0; int a,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%10dn",+count,n,n*n); return 0;四、编程题（共10分）根据数论的知识可知，任何一个合数都可以写成几个质数相乘的形式，这几个质数叫做这个合数的质因数。例如：24=2223。现在从键盘输入一个正整数n(n<10000)，请编程输出它的所有质因数。第 10 页 共 11 页