贵州大学理学院数学系信息与计算科学专业
《数据结构》期末考试试题及答案
(2003-2004学年第2学期)
一、 单项选择题
1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。
(A)、正确性 (B). 可行性 (C). 健壮性 (D). 输入性
2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。
for(i=n-1；i>=0；i--)
for(j=0；j
(A)、n2 (B). O(nlgn) (C). O(n) (D). O(n2)
3．折半查找法适用于（ ）。
（A）、有序顺序表 （B）、有序单链表
（C）、有序顺序表和有序单链表都可以 （D）、无限制
4．顺序存储结构的优势是（ ）。
（A）、利于插入操作 （B）、利于删除操作
（C）、利于顺序访问 （D）、利于随机访问
5．深度为k的完全二叉树，其叶子结点必在第（ ）层上。
（A）、k-1 （B）、k （C）、k-1和k （D）、1至k
6．具有60个结点的二叉树，其叶子结点有12个，则度过1的结点数为（ ）
（A）、11 （B）、13 （C）、48 （D）、37
7．图的Depth-First Search(DFS)遍历思想实际上是二叉树（ ）遍历方法的推广。
（A）、先序 （B）、中序 （C）、后序 （D）、层序
8．在下列链队列Q中，元素a出队的操作序列为（ ）
Q
（A）、p=Q.front->next; p->next= Q.front->next;
（B）、p=Q.front->next; Q.front->next=p->next;
（C）、p=Q.rear->next; p->next= Q.rear->next;
《数据结构与算法》二
您的姓名： [填空题] *
_________________________________
一、单选题
1. 深度优先搜索遍历类似于二叉树的（）. [单选题] *
A. 先序遍历(正确答案)
B. 中序遍历
C. 后序遍历
D. 按层次遍历
2. 无向图顶点v的度是关联于该顶点（）的数目. [单选题] *
A. 顶点
B. 边(正确答案)
C. 序号
D. 下标
3. 有n个顶点的无向图的邻接矩阵是用（）数组存储。. [单选题] *
A. 一维
B. n行n列(正确答案)
C. 任意行n列
D. n行任意列
4.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）. [单选题] * A. n-1
B. n+1
C. n(正确答案)
D. n+e
5. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）. [单选题] *
A. k1
B. k2(正确答案)
C. k1-k2
D. k1+k2
6. 广度优先遍历类似于二叉树的（）. [单选题] *
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层次遍历(正确答案)
7. 任何一个无向连通图的最小生成树（）. [单选题] *
A. 只有一棵
B. 有一棵或多棵(正确答案)
C.
一定有多棵
D. 可能不存在
二、多选题
8. 在某图中，下列选项中说法不正确的是（）. *
A. 不存在顶点到自身的边，或者重复的边，则该图是简单图 B. 不存在顶点到自身的边，或者重复的边，则该图是复杂图(正确答案)
C. 不存在顶点到自身的边，或者重复的边，则该图是无向图(正确答案)
D. 不存在顶点到自身的边，或者重复的边，则该图是有向图(正确答案)
9. 有关图的说法不正确的是（）. *
A. 有向图的边是有向的，又称为弧
B. 有向图的边是有向的，又称为箭头(正确答案)
2022年北京邮电大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）
一、选择题
1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a，b，e，c，d，f B.a，c，f,e，b，d
C.a，e，b，c，f, d D.a，e，d，f，c，b
2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
A.13 B.33 C.18 D.40
3、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A.单链表 B.仅有头指针的单循环链表 C.双链表 D.仅有尾指针的单循环链表
4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（ ）。
A.（rear+1）MOD n=front
B.rear=front
C.rear+1=front
D.（rear-1）MOD n=front
5、下列关于AOE网的叙述中，不正确的是（ ）。
A.关键活动不按期完成就会影响整个工程的完成时间
B.任何一个关键活动提前完成，那么整个工程将会提前完成
C.所有的关键活动提前完成，那么整个工程将会提前完成
D.某些关键活动若提前完成，那么整个工程将会提前完成
6、下列关于无向连通图特性的叙述中，正确的是（ ）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1
A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ
7、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（ ）。
数据结构本科期末综合练习二填空与判断题剖析
1 / 231
数据结构〔本科〕期末综合练习二〔填空与判断题〕
填空题
数据是__信息__的载体，它能够被计算机程序识别、存储和加工处理。
数据结构包括逻辑结构、__存储结构__和数据的运算三个方面。
数据结构的逻辑结构包括线性结构和__非线性__结构两大类。
数据结构的存储结构包括顺序、__链接___、索引和散列等四种。
5. 根本数据类型是计算机已经实现了的 _数据结构__。
抽象数据类型的特点是__数据封装__、信息隐蔽、使用与实现别离。
算法的一个特性是__有穷性__，即算法必须执行有限步就结束。
面向对象的特征应包括对象、类、__继承__、消息通信。
属性与效劳相同的对象构成类，类中的每个对象称为该类的__实例__。
对象的私有状态只能通过该对象的__操作〔或效劳〕_才能改变。
模板类是一种数据抽象，它把__数据类型_当作参数，可以实现类的复用。
12. 在类的继承结构中，位于上层的类叫做基类，其下层的类那么叫做 __派生〔或子〕__类。
13. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 __下标〔或
顺序号〕__存取的。
在程序运行过程中不能扩充的数组是__静态__分配的数组。这种数组在声明它时必须指定它的大小。
在程序运行过程中可以扩充的数组是__动态___分配的数组。这种数组在声明它时需要使用数组指针。
16. 二维数组是一种非线性结构，其中的每一个数组元素最多有 __两个__个直接前驱〔或直接后
继〕。
17. 假设设一个nn的矩阵A的开始存储地址 LOC(0,0) 及元素所占存储单元数 d，按行存储时
其任意一个矩阵元素 a[i][j] 的存储地址为 __LOC(0,0)+(i*n+j)*d __。1数据结构本科期末综合练习二填空与判断题剖析
2 / 232 18.对称矩阵的行数与列数__相等_且以主对角线为对称轴，aij=aji，因此只存储它的上三角局部或下三角局部即可。
