宁波大学2022年[数据结构与程序设计]考研真题
数据结构部分
一、单选题
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;
二、简答题
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个字符设计哈夫曼编码，要求画出相应的哈夫曼树。
三、算法填空
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;
⏹;continue语句执行过程
⏹};
⏹void converse(SLNode * head)
⏹{
⏹SLNode *q,*p= head->next;
⏹head->next=NULL;
⏹while(    【2】)
⏹{
⏹;
⏹p=p->next;
⏹;
⏹head->next=q;
⏹}
⏹}
3．以下是拓扑排序算法的部分代码，请在空白处填写代码。
⏹typedef  struct  ArcNode{

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。