2023年数据结构与算法期末试卷B.doc

—第二学期闽江学院期末试卷

考试课程：《数据构造与算法》
试卷类别：A卷□ B卷þ 考试形式：闭卷þ 开卷□
合用专业年级：13级金融服务、13级软件服务
装 订 线
班级 姓名 学号
题号
一
二
三

总分
得分

一、单项选用题60%（请将答案填入答题卡对应位置，30题，每题2分，共60分）
得分

1、计算机算法必要具有输入、输出和（ ）等5个特性。
A．可行性、可移植性和可扩充性 B．可行性、确定性和有穷性
C．确定性、有穷性和稳定性 D．易读性、稳定性和安全性
2、设语句x++时间是单位时间，则如下语句时间复杂度为（　　）。
for(i=1；i<=n；i++)
x++；
A．O(1) B．O (n2) C．O(n) D．O (n3)
3、如下哪种逻辑构造关系最松散（ ）
A．集合 B．线性 C．树 D．图
4、如下哪种线性表存储地址一定是持续（ ）
A．有序表 B．次序表 C．单链表 D．双链表
5、带头指针循环链表在表尾插入，时间复杂性 ( )
A．O(1) B．O(n） C．O (n2) D．O (n3)
6、设结点构造为(data，next)，L是带头结点和尾指针单循环链表，L->last是表尾结点指针。若想删除链表首元结点，则应执行下列（　　）操作？
A．s = L->last； L->last= L->last->next； free(s)；
B．L->last= L->last->next； free(L->last)；
C．L->last= L->last->next->next； free(L->last)；
D．s = L->last->next->next； L->last->next->next = s->next； free(s);
7、带头结点单链表L为空鉴定条件是（　　）
A．L->next == NULL； B．L!= NULL；
C．L->next== L； D．L== NULL；
8、设结点构造为(prior,data,next)，L是不带头结点循环双链表，L是表头结点指针。若想删除循环双链表中p结点后继结点(假设存在)，则应执行下列（　　）操作？
A．p->next = p->next->next；
B．p->next = p->next->next；p->next->prior = p；
C．p->next = p->next->next；p->next->next->prior = p;
D．p->next->prior = p；p->next = p->next->next;
9、若在线性表中常常波及插入删除操作，则采用如下哪种表进行元素存储比很好（　　）？
A．有序表 B．次序表 C．链表 D．栈
10、在一种长度为n次序表中插入第i个元素(1<=i<=n+1)时，需向前移动（　　）个元素。
A．n-i B．n-i+1 C．n-i-1 D．i
11、假定对元素序列（7，3，5，9，1，12）进行堆排序，并且采用小根堆，则由初始数据构成初始堆为（ ）。
A．1，3，5，7，9，12 　 B．1，3，5，9，7，12
C．1，5，3，7，9，12 D．1，5，3，9，12，7
12、假定一种初始堆为(1，5，3，9，12，7，15，10)，则进行第一趟堆排序后得到成果为（ ）。
A．3，5，7，9，12，10，15，1 B. 3，5，9，7，12，10，15，1
C. 3，7，5，9，12，10，15，1 D. 3，5，7，12，9，10，15，1
13、在平均状况下速度最快排序措施为（ ）
A．直接选用排序 B．归并排序 C．基数排序 D．迅速排序
14、若一种元素序列基本有序，则选用（ ）措施较快。
A．直接插入排序 B．简朴选用排序
C．归并排序 D．迅速排序
15、对1000个元素进行排序，规定既快又省空间，则如下（　　）算法比很好。
A．直接插入排序 B．堆排序
C．归并排序 D．迅速排序
16、设元素进栈次序为1，2，3，那么如下哪种是不也许出栈序列。
　A．123 B．132 C．312 D．312
17、栈插入和删除操作在（ ）进行。
A．栈顶 B．栈底 C．中间 D．任意位置
18、队列中元素进出原则为（　　）。
A．先进先出 B．后进先出 C．大数先出 D．小数先出
19、对二叉排序树进行如下哪种遍历会得到一种有序序列。
A. 先序遍历 B. 中序遍历　　　　C. 后序遍历 D. 层序遍历
20、由权值分别为3,8,6,2,5叶子结点生成一棵哈夫曼树，它带权途径长度为（ ）。
A. 24 B. 48 C. 72 D. 53
21、在一棵度为3树中，度为3结点数为3个，度为2结点数为2个，度为1结点数为3个，则度为0结点数为（ ）个。
A. 8 B. 9 C. 6 D. 7
22、在一棵二叉树上第3层结点数最多为（ ）。
A. 2 B. 4 C. 6 D. 8
23、用次序存储措施将完全二叉树中所有结点逐层存储在数组中R[1..n]，结点R[i]若有右孩子，其右孩子编号为结点（ ）。
A. R[2i+1] 　　B. R[2i] C. R[i/2] D. R[2i-1]
24、已知图中某条途径上有k个顶点，则该途径长度为（　　）。
A．k-1 B．k C．k+1 D．2k
25、如下( )算法用于在有向网中求单源最短途径。
A．普里姆算法 　　B．克鲁斯卡尔算法
C．迪杰斯特拉算法 D．弗洛伊德算法
26、在一张有向图中，若一种顶点入度为k1，出度为k2，则对应邻接表中该标点单链表中结点数为( )。
A．k1 B．k2 C．k1+k2 D．2(k1+k2)
27、设有7个结点无向图，该图至少应用( )条边能保证是一种连通图。
A．5 B．6 C．7 D．8
28、10个顶点构成无向完全图中，有( )条弧。
A．45 B．90 C．100 D．200
29、对于次序存储有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素12比较次数为(　　)。
A. 2 B. 3 C. 4 D. 5
30、假定对线性表(38,25,74,52,48)进行哈希存储，采用H(k)=k%7作为哈希函数，采用开放定址法处理冲突，则在建立哈希表过程中，将会碰到( )次存储冲突。
A. 4 B. 5 C. 6 D. 7
二、程序完型填空题10%（请将答案填入答题卡对应位置，1题5空，每空2分，共10分）
得分

已知图邻接表定义如下：
const MAX_VERTEX_NUM=20;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
int info;//InfoType *info;
}ArcNode；//边结点
typedef char VertexType;
typedef struct VNode
{
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM]；//顶点数组中顶点结点
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
}ALGraph；//图
请将下列有向图创立算法补充完整：

void CreateUDG(ALGraph *G)
{　//假设所需变量皆已经定义
scanf("%d,%d"，&(G->vexnum)，&(G->arcnum));//输入图顶点数与弧数
//构造顶点数组
for(i=0；i<G->vexnum；i++)
{
getchar();//吸取输入回车符
scanf("%c"，___(1)___);//输入图顶点信息
___(2)___;
}
//构造边结点
for(k=0；k<G->arcnum；k++)
{
getchar();//吸取回车符
scanf("%c,%c"，&v1,&v2);//输入弧两个端点
i=LocateVex(G,v1);//起点编号
j=LocateVex(G,v2);//终点编号
pi=___(3)___；
pi->adjvex=___(4)___;
pi->nextarc=___(5)___;
G->vertices[i].firstarc=pi;
}
}
(1) A．&(G->vertices[j].data) B. &(G->vertices[i].data)
C. &(G->vertices[j].adjvex) D. &(G->vertices[i].adjvex)
(2) A．G->vexnum++ 　　 B. 此处不需要添加代码
C. G->data[i].firstarc=NULL D. G->vertices[i].firstarc=NULL
(3) A．new Node 　　 B. new VNode
C. new ArcNode D. new ALGraph
(4) A．i B. j C. v1 D. v2
(5) A．G->vertices[i].firstarc B. G->vertices[j].firstarc
C. G->vertices[i].nextarc D. G->vertices[j].nextarc

三、填空题30%（请将答案填入答题卡对应位置，除第3题第一空为4分外，别旳都为2分，共30分）
得分

1、已知记录 (46,74,53,14,26,38,86,65,27,34)，请给出归并排序第一趟排序成果(以第一种元素作为基准)：______
2、从一棵二叉排序树中查找一种元素时，若元素值不不不小于根结点值，则继续向______查找。
3、假设一棵二叉树后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请画出该二叉树______(4分)，并写出该二叉树先序遍历序列______。　
4、已知二叉树二叉链表体现法定义如下：
typedef char TElemType;
typedef struct BiTnode
{ TElemType data;
struct BiTnode *lchild，*rchild;
}BiTNode，*BiTree;
请将下列二叉树查找算法补充完整：
int LocateElem(BiTree T，TElemType e)//e为要查找元素
{ int floor;//用于记录层数
if(T)//若树不空
{ if(___(1)___)//若在根处找到
return 1;
floor = LocateElem(___(2)___);//在左子树查找
if(floor>0)//若在左子树中找到
return ___(3)___;
floor = LocateElem(___(4)___);
if(floor>0)
return ___(5)___;
}
return 0;//若树为空，则直接返回0，阐明找不到
}
5、已知图邻接表定义如第二题所示，下列程序段为图深度优先搜索算法，请将算法中缺失语句补充完整：
void DFS (ALGraph G,　int v) //从编号为v顶点出发进行深度优先搜索遍历
{ //假设所有变量、函数皆已定义
visited[v]=true;//访问标志数组，true体现访问过，false体现未被访问过
VisitFunc(v)；//访问v标点
for(p=___(1)___；p；___(2)___)
//for(用p指向第一种邻接顶点；若该邻接顶点存在；p指向下一种邻接顶点)
{ w=p->___(3)___;//用w记录邻接顶点编号
if(___(4)___)//若该邻接顶点未被访问过
___(5)___;//从邻接顶点开始递归深度优先搜索遍历
}
}