2020-2021学年第一学期计算机科学与技术专业《数据结构》期末考试题及答案(试卷B).pdf

XXX大学2020-2021学年第一学期

计算机科学与技术专业《数据结构》期末考试题及答案

（试卷B）

题号一二三四合计

满分30103030100

实得分

-1-

一、填空题（每空1.5分，共30分）。

⒈任何一个算法的设计取决于选定的数据（逻辑）结构，而算

法的实现依赖于采用的。

⒉数据结构是一门研究的程序设计问题中计算

机的操作对象以及它们之间的等等的学科。

⒊带头结点的单向链表L为空的判定条件是；

非空的循环单链表head的尾结点p满足条件。

⒋栈和队列是两种特殊的线性表，栈的特点是，

栈的典型应用有和。

⒌在具有n个单元的循环队列中，队列满时共有

个元素。

⒍若串的长度不能确定，可采用动态存储结构，为串值分配一

个存储空间，同时建立一个串的描述子以指示串值的长度和串在存储

空间中的位置，称该结构为。

⒎稀疏矩阵一般的压缩存储方法有两种，即和十字

链表。

⒏二维数组A[10][20]采用列序为主方式存储，每个元素占10

个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址

是。

⒐一棵高度为h的满二叉树共有个终端结点。

⒑已知一棵完全二叉树的第5层有3个结点，其叶子结点数

-2-

是。

⒒具有8个顶点的有向完全图有条弧。

⒓在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]

等于。

⒔对线性表进行二分查找时，要求线性表必须以

方式存储，且结点按关键字排列。

⒕在分块查找方法中，首先查找索引，然后再查找相应

的。

⒖与快速排序和堆排序相比，归并排序的最大特点是，它是一

种的排序方法。

二、判断题（每小题1分，共10分）若正确，填入“T”，否则

填入“F”。

⒈线性表的逻辑顺序与存储顺序总是一致的。（）；

⒉一个栈的入栈序列是12345，则栈的输出序列12345是不可

能的。（）；

⒊将递归算法转换成对应的非递归算法时，通常需要使用栈。

（）；

⒋设有两个串p和q，求q在p中首次出现的位置的运算称作

求子串。（）；

⒌二维数