《宁波大学2022年[数据结构与程序设计]考研真题》由会员分享，可在线阅读，更多相关《宁波大学2022年[数据结构与程序设计]考研真题（18页珍藏版）》请在金锄头文库上搜索。
1、宁波大学 2022 年数据结构与程序设计考研真题宁波大学 2022 年数据结构与程序设计考研真题数据结构部分数据结构部分一、单选题一、单选题1、若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）A3，2，6，1，4，5B3，4，2，1，6，5C1，2，5，3，4，6D5，6，4，2，3，12、若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为（）A图中每个顶点的入度B图中每个顶点的出度C图中弧的条数D图中连通分量的数目3、下列二叉树中，（）可用于实现符号的不等长高效编码。A.最优二叉树B.B-树C.平衡二叉树D.二叉排序树4、在对 n 个关键字进行
2、直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第 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
3、.冒泡排序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;二、简答题二、简答题1.一颗二叉树的前序遍历的结果
4、是 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 765.假设用于通信的电文仅由 6 个字符组成，其频率分别为：11，9，13，15，29，23。试为这 6 个字符设计哈夫曼编码，要求画出相应的哈夫曼树。三、算法填空三、算法填空1.以下
5、程序实现按递减序对 R0Rn-1 进行直接选择排序。请在空白处填写代码。void selectsort(int R )int i,j,k,temp;for(i=0;i 【1】;i+)k=i;for(j=i+1;jnext;head-next=NULL;while(【2】);p=p-next;head-next=q;3以下是拓扑排序算法的部分代码，请在空白处填写代码。typedef struct ArcNode int adjvex;/*该弧指向顶点的位置*/struct ArcNode *nextarc;/*指向下一条弧的指针*/OtherInfo info;/*与该弧相关的信息*/ArcNo
6、de;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 函数求各顶点入度*/InitSt
7、ack(&S);/*初始化辅助栈*/for(i=0;iG.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=y=z)B)(x=y)AND(y=z)C)(x=y)&(y=z)D)(x=y)&(y=z)3、假设 var1,var2,var3,var4,var5
8、是 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、能正确表
9、示逻辑关系“”的 C 语言表达式是 。A)a=10 or a=0|a=10&a=10|a=08、若 int x=1，y=6，z=2 则表达式 xb)c=a;a=b;0a10a或 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)和之前与
10、其最近的 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)死循环
11、D)014、以下程序段的输出结果是 。int i,s=0;for(i=1;i10;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 语句只能
12、用在循环体和 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 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#def
13、ine ABC(x)x*x int 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)以上都不行二、程序阅读题二、程序阅读题1、写出程序运行结
14、果。#include 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 int main()int na,nb;for(na=1,nb=1;na=20)break;if(nb%3=1)nb+=3;break;nb-=5;printf(%dn,na);return 0;3、写出程序运行结果。#incl
15、ude int a=2,b=3;int max(int a,int b)int c;c=ab?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;三、程序填空题三、程序填空题1、已知两个整型数组 f和 g，它们的元素都已经从小到大排列，并且每个数组中的元素都是各不相同的。例如，f中可能是 1，3，4，7，9；而 g中可能是 3，5，7，8，10。请填空完成以下程序
16、算出这两个数组中有多少组元素是相等的。例如 f2=g1=3,f4=g3=8。#include 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(取 n256)数中，其平方具有对称性质的数(回文数)。请填空完成以下程序。#include int main()int m1
