报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！
试卷代号：1252
国家开放大学2021年秋季学期期末统一考试
数据结构（本） 试题
2022年1月
一、单项选择题（把合适的选项编号填写在括号内。每小题3分，共45分）
1.下列说法中，不正确的是( )。
www.bnjyedu.cn
A.数据元素是数据的基本单位
B.数据项是数据中不可分割的最小可标识单位
C.数据可有若干个数据元素构成
D.数据项可由若干个数据元素构成‘
2.每个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是( )存储方式。
A.顺序B.链接
C.索引D.散列
3.在一个单链表中p指向结点a，q指向结点a的直接后继结点b，要删除结点b，可执行( )。
A.p->next=q->nextB.p=q->next
C.p->next=qD.p->next=q
4.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行( )。
A.p->next=s;s->next=p->next
B.p->next=s->next
C.p=s->next
D.s->next=p->next,p->next=s
5.向顺序栈中压入新元素时，应当( )。
A.先移动栈顶指针，再存入元素B.先存入元素，再移动栈顶指针
C.先后次序无关紧要D.同时进行
6.一般情况下，将递归算法转换成等价的非递归算法应该设置( )。
A.栈B.队列
C.堆栈或队列D.数组
7.判断一个循环队列Q(最多元素为m)为满的条件是( )。
A.Q->front==Q->rear
B.Q->front!=Q->rear
C.Q->front==(Q->rear+l)%m
D.Q->front!=(Q->rear+l)%m
8.空串与空格串( )。
A.相同B.不相同
C.可能相同D.无法确定
9.广义表(f，h，(a，b，d，c)，d，e，((i，j)，k))的长度是( )。
A.6B.10
C.8D.4
10.二叉树第k层上最多有( )个结点。
A.2kB.2k-l
C.2k-lD.2k-l
11.树中的结点数等于所有结点的度数加( )。
A.1B.O
C.2D.-1
12.对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为( )。
A.nB.n2
C.n-lD.(n-l)2
13.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为( )。
A.nB.e
C.2nD.2e
14.采用折半查找方法查找长度为n的线性表时，其算法的时间复杂度为( )。
A.O(n2)B.O(nlog2n)
C.O(n)D.0(1og2n)
15.从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。将其放人已排序序列的正确的位置上，此方法称为( )。
A.插入排序B.交换排序
C.选择排序D.归并排序
二、判断题（根据叙述正确与否在其后面的括号内打对号“√”或打叉号“×”。每小题2分，共30分）
16.数据元素可以有一个或多个数据项组成。( )
17.数据结构中，元素之间存在多对多的关系称为图状结构。( )
18.设有一个单向链表，结点的指针域为next，头指针为head，p指向尾结点，为了使该单向链表改为单向循环链表，可用语句p->next=head。( )
19.设有一个单向循环链表，结点的指针域为next，头指针为head，指针p指向表中某结点，若逻辑表达式p->next==head;的结果为真，则p所指结点为尾结点。( )
20.循环队列队头指针在队尾指针前一个位置，队列是“满”状态。( )
21.栈是限定在表的两端进行插入和删除操作的线性表，又称为先进先出表。( )
22.向一个栈顶指针为h的链栈(结点的指针域为next)中插入一个s所指结点时，先执行s->next=h，再执行h=s操作。( )
23.串的两种最基本的存储方式是顺序和链接。( )
24.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的行号、列号和元素值三项信息。( )
25.深度为k的完全二叉树至少有2k-l个结点。( )
26.如果结点A有3个兄弟，而且B是A的双亲，则B的度是4。( )
27.用邻接矩阵存储图的时候，占用空间大小不但与图的结点个数有关还与图的边数有关。( )
28.对连通图进行深度优先遍历可以访问到该图中的所有顶点。( )
29.二叉排序树在呈单支二叉树时，查找效率最低。( )
30.冒泡排序是一种比较简单的插入排序方法。( )
三、综合应用及程序设计题（每小题5分，共25分）
31.设有一个头指针为head的不带头结点单向链表中(结点类型为NODE)，p为指向链表中某个结点的指针。以下程序段为插入一个指针为s的结点，使它成为p结点的直接驱，请选择其中空格的选项。
NODE*q；
q=head；
while(q->next!=p)
① ；
s->next=p；
② ；
①(3分)
A.p=p->nextB.q=q->next
C.s=s->nextD.head=head->next
②(2分)
A.p->next=qB.p->next=s
C.q->next=sD.q->next=p
32.以下为求二叉树深度的算法，完成程序中空格部分。
intBTreeDepth(BTreeNode*BT)
{if (BT==NULL)
return O；
else
{(int dep1=BTreeDepth(BT->left)；／*计算左子树的深度*／
Int dep2=BTreeDepth(BT->right)；／*计算右子树的深度*／
if( )
return depl+l；
else
return dep2+!；
}
}
A.depl>dep2B.depl<dep2
C.BT-->left==NULLD.BT->right==NULL
33.设有数据集合：{50，39，17，83，91，14，65)
(1)依次取集合中各数据构造一棵二叉排序树是下图中的( )。（3分）
(2)二叉排序树的( )遍历是有序序列。（2分）
A.先序B.中序
C.后序D.按层
34.已知某带权图的邻接矩阵如下所示：
从顶点1出发的广度优先搜索序列为( )。
A.1,2,3,4,5,6B.1,4,3,2,6,5
C.1,3,2,4,6,5D.1,2,4,3,5,6
35.以下函数在a[0]到a[n-l]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-l，完成程序中的空格选项。
typedef struct
{int key;
……
}NODE；
Int Binary_Search(NODE a[],int n,int k)
{int low,mid,high;
low=0;
high=n-l;
while( ① )
{ mid=( ② )
if(a[mid].key==k)
return mid;
else
if(a[mid].key<k)
low=mid+l,
else
high=mid-l,
}
return-1
｝
①（3分）
A.a[mid].key==kB.a[mid].key>k
C.a[mid].key<kD.low<=high
②（2分）
A.(low+high)/2B.mid+l
C.mid-1D.low+high
微信扫码添加好友
如二维码无法识别，可拨打 13662661040 咨询。
