2019年浙江宁波大学数据结构与程序设计考研真题.doc

2019年浙江宁波大学数据结构与程序设计考研真题
数据结构部分（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.n2 B.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;
二、简答题（每题5分,5题，共25分）
1.一颗二叉树的前序遍历的结果是1，2，3，4，5，6,中序遍历的结果是3，2，4，6，5，1。请画出这颗二叉树。
2.请用Prim算法画出右图最小生成树的生成过程。

3.请根据输入序列{1002867213054180110138}构造二叉查找树。如果删除元素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]进行直接选择排序。请在空白处填写代码。
voidselectsort(intR[])
{inti,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倒置该链表的结点，请在空白处正确填写代码。
StructSLNode{
DateTypedate;
【1】;
};

voidconverse(SLNode*head)
{
SLNode*q,*p=head->next;
head->next=NULL;
while(__【2】__)
{
__【3】__;
p=p->next;
__【4】____;
head->next=q;
}
}
3．以下是拓扑排序算法的部分代码，请在空白处填写代码。
typedefstructArcNode{
intadjvex;/*该弧指向顶点的位置*/
structArcNode*nextarc;/*指向下一条弧的指针*/
OtherInfoinfo;/*与该弧相关的信息*/
}ArcNode;
typedefstructVertexNode{
VertexDatadata;
ArcNode*firstarc;
}VertexNode;
typedefstruct{
VertexNodevertex［MAX-VERTEX-NUM］;
intvexnum,arcnum;/*图的顶点数和弧数*/
GraphKindkind;
}AdjList