宁波大学917数据结构与程序设计2019年考研真题
2023-12-26
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、下列二叉树中,()可...
声明:研友网所有资料均为用户上传分享,仅供参考学习使用,版权归原作者所有。若侵犯到您的权益,请告知我们处理!任何个人或组织,在未征得本平台同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。