数据结构期末考试试卷3套

本文格式为Word版，下载可任意编辑——数据结构期末考试试卷3套数据结构

一、判断题（共10分，每题1分）（×）1、数据元素是数据的最小单位。

（×）2、串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中符构成的有限序列。

（×）3、子串定位函数的时间繁杂度在最坏状况下为O（n*m），因此子串定位函数没有实际使用的价值。

（×）4、在线性链表中删除中间的结点时，只需将被删结点释放。

（×）5、邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。（√）6、递归定义的数据结构寻常用递归算法来实现对它的操作。

（√）7、在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有一致的结果。

（√）8、已知指针P指向键表L的某结点，执行语句P=P->next不会删除该链表中的结点。

（√）9、对一个连通图进行一次深度优先探寻可以遍访图中的所有顶点。（√）10、进行折半探寻的表必需是顺序存储的有序表。二、填空题（共20分，每空1分）

1、数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。

2、算法的五个重要特性是有穷性、确定性、可行性、输入、输出。

3、在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。

4、在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个直接

前驱结点，叶子结点没有后续结点，其余每个结点的直接后续结点可以任意多个。

5、在具有n个单元的循环队列中，队满时共有n-1个元素。6、向栈中压入元素的操作是先移动栈顶指针，后存入元素。

7、不包含任何字符（长度为0）的串称为空串；

由一个或多个空格（仅由空格符）组成的串称为空白串。8、假使含n个顶点的图形成一个环，则它有n棵生成树。

9、有向图中的结点前驱后继关系的特征是一个结点可能有若干个前驱，也可能有若干个后继。

10、折半查找的存储结构仅限于_顺序存储结构__，且是有序的。三、选择题（共30分，每题2分）

1.一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是____。A.110B.108C.100D.120

2.线性表的顺序存储结构是一种___的存储结构，而链式存储结构是一种___的存储结构。A．随机存取B．索引存取C．顺序存取D．散列存取

3.线性表的规律顺序与存储顺序总是一致的，这种说法___。A.正确B.不正确

4．设有两个串p和q，求q在p中首次出现的位置的运算称作____。A.连接C.求子串

B.模式匹配D.求串长

5．设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是____。A.BCDEFC.BCPQRST

B.BCDEFG

D.BCDEFEF

6.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为____。

A.SA+141B.SA+144C.SA+222D.SA+225

7.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为____。A.SA+141B.SA+180C.SA+222D.SA+225

8.由于二叉树中每个结点的度最大为2，所以二叉树是一种特别的树，这种说法____。A.正确B.错误

9.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为个。

A．15B．16C．17D．47

10.依照二叉树的定义，具有3个结点的不同形状的二叉树有____种。A.3B.4C.5D.6

11.依照二叉树的定义，具有3个不同数据结点的不同的二叉树有____种。A.5B.6C.30D.32

12.在一个图中，所有顶点的度数之和等于所有边数的____倍。A.1/2B.1C.2D.413．任何一个无向连通图的最小生成树。A.只有一棵

B.有一棵或多棵

C.一定有多棵

D.可能不存在

14．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。A.1/2B.1C.2D.4

15.解决散列法中出现的冲突问题常采用的方法是。

A.数字分析法、除余法、平方取中法B.数字分析法、除余法、线性探测法C.数字分析法、线性探测法、多重散列法D.线性探测法、多重散列法、链地址法四、简答题（共24分，每题6分）

1、根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。答：如图6.10所示

cbaaccabaccbabcb图6.10树形5种

2、试比较顺序存储结构和链式存储结构的优缺点。在什么状况下用顺序表比链表好？答：①顺序存储时，相邻数据元素的存放地址也相邻（规律与物理统一）；要求内存中可用存储单元的地址必需是连续的。

优点：存储密度