宁波大学917数据结构与程序设计2019年考研真题
2024-02-11
999+
329.81KB
11 页
侵权投诉
宁波大学2019年硕士研究生招生考试初试试题(A卷)
(答案必须写在考点提供的答题纸上)
第 0 页 共 11 页
科目代码：
917
总分值：
150
科目名称：
数据结构与程序设计
数据结构部分（75 分）
一、单选题：（每小题2分，10 小题，共20 分）
1、若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（ ）
A．3，2，6，1，4，5 B．3，4，2，1，6，5
C．1，2，5，3，4，6 D．5，6，4，2，3，1
2、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）
A．图中每个顶点的入度 B．图中每个顶点的出度
C．图中弧的条数 D．图中连通分量的数目
3、下列二叉树中，( )可用于实现符号的不等长高效编码。
A. 最优二叉树 B. B-树 C. 平衡二叉树 D. 二叉排序树
4、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则
在进行第i趟排序之前，无序区中关键字元素的个数为（ ）
A．i B．i+1
C．n-i D．n-i+1
5、若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比
较的关键字依次为（ ）
A．f,c,b B．f,d,b
C．g,c,b D．g,d,b
6、设有5000 个待排序的记录关键字，如果需要用最快的方法选出其中最小的10 个记录关键字，
则用下列（ ）方法可以达到此目的。
A． 快速排序 B. 堆排序 C. 归并排序 D. 插入排序
7、排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（ ）
A. 选择排序 B. 快速排序
C. 冒泡排序 D. 插入排序
8、有n个结点的有向完全图的弧数是（ ）
A. n2B. 2n
C. 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;
宁波大学2019年硕士研究生招生考试初试试题(A卷)
(答案必须写在考点提供的答题纸上)
第 1 页 共 11 页
科目代码：
917
总分值：
150
科目名称：
数据结构与程序设计
二、简答题（每题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; }
}
}
}
宁波大学2019年硕士研究生招生考试初试试题(A卷)
(答案必须写在考点提供的答题纸上)
第 2 页 共 11 页
科目代码：
917
总分值：
150
科目名称：
数据结构与程序设计
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;
标签： #宁波大学
摘要：
展开>>
收起<<
宁波大学2019年硕士研究生招生考试初试试题(A卷)(答案必须写在考点提供的答题纸上)第0页共11页科目代码：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、若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（ ）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目3、下列二叉树中，()可...
声明：研友网所有资料均为用户上传分享，仅供参考学习使用，版权归原作者所有。若侵犯到您的权益，请告知我们处理！任何个人或组织，在未征得本平台同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。
