第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
2019年浙江宁波大学数据结构与程序设计考研真题.doc
Struct SLNode {
2019 年浙江宁波大学数据结构与程序设计考研真题
数据结构部分（75 分）
一、单选题：（每小题 2 分，10 小题，共 20 分）
1、若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列
为（ ）
A．3，2，6，1，4，5
C．1，2，5，3，4，6
B．3，4，2，1，6，5
D．5，6，4，2，3，1
2、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）
A．图中每个顶点的入度
B．图中每个顶点的出度
C．图中弧的条数
D．图中连通分量的数目
3、下列二叉树中，(
)可用于实现符号的不等长高效编码。
A. 最优二叉树
B. B-树
C. 平衡二叉树
D. 二叉排序树
4、在对 n 个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，
则在进行第 i 趟排序之前，无序区中关键字元素的个数为（ ）
A．i
C．n-i
B．i+1
D．n-i+1
5、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字 b 的过程中，
先后进行比较的关键字依次为（ ）
A．f,c,b
C．g,c,b
B．f,d,b
D．g,d,b
6、设有 5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的 10 个记录关
键字，则用下列（ ）方法可以达到此目的。
A． 快速排序
B. 堆排序
C. 归并排序
D. 插入排序
7、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）
A. 选择排序
C. 冒泡排序
B. 快速排序
D. 插入排序
8、有 n 个结点的有向完全图的弧数是（
）
A. n2
C. n(n-1)
B. 2n
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. 请根据输入序列{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. 以下程序实现按递减序对 R[0]～R[n-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
vertex［MAX-VERTEX-NUM］;
int
vexnum, arcnum;
GraphKind
kind;
}AdjList;
/*图的顶点数和弧数*/
int TopoSort (AdjList G)
{
Stack S;
int
indegree［MAX-VERTEX-NUM］;
int
i,
count,
k;
ArcNode *p;
FindID(G, indegree);
/* FindID 函数求各顶点入度*/
InitStack(&S);
/*初始化辅助栈*/
for(i=0; i
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=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) 3
B) 4
C) 5
D) 6
4、函数 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
D)x%2= =0
。
。
7、能正确表示逻辑关系“
”的 C 语言表达式是
A)a>=10 or a<=0
C)a>=10&&a<=0
D)a>=10||a<=0
C)x%2!=0
0
a
10
或
a
B)a>=0|a<=10
8、若 int x=1，y=6，z=2 则表达式 xb)
c=a;
a=b;
b=a;
printf("a=%d,b=%d\n",a,b);
A）a=30,b=30
B）a=20,b=30
C）a=30,b=20
D）a=20,b=20
10、设有数组定义“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(“%d\n”,sum);
A) 6
B) 3
C) 死循环
D) 0
14、以下程序段的输出结果是
。
int i,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、以下程序段的执行结果是
。
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 a[5]={0,1,2,3,4,5};
B) int a[5]=5;
C) int a[N]={1,2,3} ;
D) int a[5]={3} ;
18、有以下程序：
#include
struct S {
int a,b;
} data[2]={10,100,20,200};
int main()
{
}
struct S
p = data[1];
printf("%d\n", ++(p.a));
return 0;
程序运行后的输出结果是
。
A) 10
B) 11
C) 20
D) 21
19、下面的程序输出的结果是
。
#include
#define ABC(x)
x * x
int main()
{
}
int a = 3;
printf("%d\n", ABC(a + 1));
return 0;
A) 7
B) ABC
C) 4
D) 16
20、要求函数的功能是交换两个整型变量的值，且通过调用正确返回交换的结果。能正确执
行此功能的函数是
。
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
void fun(char s[])
{
}
char *p=s;
while(*p)
if((*p>='0')&&(*p<='9')) p++;
else *s++=*p++;
*s='\0';
int main( )
{
char item[100]="hello123world78";
fun(item);
printf("The string:
%s\n",item);
return 0;
}
2、写出程序运行结果。
#include
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("%d\n",na);
return 0;
}
3、写出程序运行结果。
#include
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;
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
