数据结构模拟卷(含答案)经典习题

数据结构模拟试卷一一、单选题（每小题2分，共20分）1. 在数据结构的讨论中把数据结构从逻辑上分为（）。

A．内部结构与外部结构 B. 静态结构与动态结构 C. 线性结构与非线性结构 D. 紧凑结构与非紧凑结构2. 采用线性链表表示一个向量时，要求占用的存储空间地址（）。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 可连续可不连续3. 采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。

A. nB. n/2C. (n-1)/2D. (n+1)/24. 在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。

A. s→link = p→link; p→link = s;B. p→link = s; s→link = q;C. p→link = s→link; s→link = p;D. q→link = s; s→link = p;5. 如果想在4092个数据中只需要选择其中最小的10个，采用（）方法最好。

A.冒泡排序B. 堆排序C. 直接插入排序D. 快速排序6. 设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。

A. 求子串B. 模式匹配C. 串替换D. 串连接7. 在数组A中，每一个数组元素A[i][j]占用3个存储单元，行下标i从1到8，列下标j从1到10。

所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储单元是（）。

A. 80B. 100C. 240D. 2708. 将一个递归算法改为对应的非递归算法时，通常需要使用（）。

A. 栈B. 队列C. 循环队列D. 优先队列9. 一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。

A. 4, 3, 2, 1B. 2, 4, 3, 1C. 1, 2, 3, 4D. 3, 2, 1, 410. 在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。

数据结构设计课程代码：7399一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

每小题2分，共40分）1、串的长度是（）。

A、串中不同字母的个数B、串中不同字符的个数C、串中所含字符的个数，且大于0D、串中所含字符的个数2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。

为这两个栈分配空间的最佳方案是（）。

A、S1的栈底位置为0，S2的栈底位置为n+1B、S1的栈底位置为0，S2的栈底位置为n/2C、S1的栈底位置为1，S2的栈底位置为nD、S1的栈底位置为1，S2的栈底位置为n/23、队列操作的原则是（）。

A、先进先出B、后进先出C、只能进行插入D、只能进行删除4、有64个结点的完全二叉树的深度为（）（根的层次为1）。

A、8B、7C、6D、55、在有n个结点的二叉链表中，值为非空的链域的个数为（）。

A、n-1B、2n-1C、n+1D、2n+16、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。

A、第i行非∞的元素之和B、第i列非∞的元素之和C、第i行非∞且非0的元素个数D、第i列非∞且非0的元素个数7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。

A、0(n)B、0(log2n)C、0(nolg2n)D、0(n2)8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。

A、直接插入排序B、快速排序C、归并排序D、选择排序9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。

A、选择B、冒泡C、归并D、堆10、若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（）存储方式节省时间。

A、单链表B、双链表C、单循环链表D、顺序表11、对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）遍历实现编号。

单元测验1一．判断题（ㄨ）（1）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（2）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（3）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（4）数据的存储结构是数据的逻辑结构的存储映像。

（ㄨ）（5）数据的逻辑结构是依赖于计算机的。

（√）（6）算法是对解题方法和步骤的描述。

二．填空题1．数据有逻辑结构和存储结构两种结构。

2. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

3．树形结构和图形结构合称为非线性结构。

4．数据的存储结构又叫物理结构。

5．数据的存储结构形式包括：顺序存储和链式存储6．线性结构中的元素之间存在一对一的关系。

7．树形结构中的元素之间存在一对多的关系，8．图形结构的元素之间存在多对多的关系。

9．数据结构主要研究数据的逻辑结构、存储结构和二者之间的相互运算三个方面的内容。

10．一个算法的时间复杂度是问题规模的函数。

11．若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为O（nlog2n）。

12．若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为O（n2）。

三．选择题1．数据结构通常是研究数据的（D ）及它们之间的相互联系。

A.联系与逻辑B.存储和抽象C.联系和抽象D.存储结构和逻辑结构2．数据在计算机内存储时，数据元素在存储器内相对位置可以表示元素之间的逻辑关系，称为（D）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3．链接存储的存储结构所占存储空间（A）。

A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数4．在数据结构中，与所使用的计算机无关的是（B）A.物理结构B.逻辑结构C.存储结构D.逻辑和存储结构5．算法能正确的实现预定功能的特性称为（A）A.正确性B.易读性C.健壮性D.高效性6．算法在发生非法操作时可以作出处理的特性称为（B）A.正确性B.健壮性C.易读性D.高效性7．下列时间复杂度中最坏的是（A）A.O（n2）B.O（log2n）C.O（n）D.O（1）8. 算法分析的两个主要方面是（C）。

数据结构试卷（一）一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.树最适合用来表示( )。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

数据结构模拟试卷及参考答案一、简答题（共10题，每题10分，共计100分）1. 什么是数据结构？请简要解释。

数据结构是计算机中用于组织和存储数据的方式，它包含了一系列的数据元素，以及这些数据元素之间的关系和操作。

通过使用不同的数据结构，可以更高效地存储、查找和操作数据。

2. 请解释什么是栈，并给出一个栈的应用场景。

栈是一种具有特定操作限制的数据结构，它遵循"先进后出"（LIFO）的原则。

栈的应用场景包括函数调用、表达式求值、撤销操作以及浏览器中的历史记录。

3. 什么是队列？请给出一个队列的实际应用例子。

队列是一种具有特定操作限制的数据结构，它遵循"先进先出"（FIFO）的原则。

一个实际应用例子是操作系统的进程调度，进程按照到达时间加入队列，并按照一定规则出队执行。

4. 请解释什么是链表，并给出一个链表的优点和缺点。

链表是一种动态数据结构，它由一系列节点构成，每个节点包含数据和指向下一个节点的指针。

链表的优点是可以动态地分配内存空间，且插入和删除节点的时间复杂度为O(1)。

缺点是访问链表某个具体节点的时间复杂度为O(n)，且需要额外的内存空间存储指针。

5. 请解释什么是树，并给出一个树的实际应用例子。

树是一种分层次的数据结构，它由一系列节点和节点之间的关系构成。

一个实际应用例子是文件系统的目录结构，文件和文件夹通过树的结构进行组织和存储。

6. 请解释什么是图，并给出一个图的实际应用例子。

图是一种由节点和节点之间的连接关系组成的数据结构。

一个实际应用例子是社交网络，人与人之间的关系可以用图来表示，每个人是一个节点，节点之间的连接表示关系。

7. 请解释什么是散列（哈希）表，以及它的优势和劣势。

散列表是一种根据关键字直接访问的数据结构，它通过将关键字映射到表中的位置来实现快速的查找操作。

散列表的优势是查找操作的平均时间复杂度为O(1)。

劣势是如果存在多个关键字映射到同一个位置，就会发生冲突，需要解决冲突问题。

数据结构试卷（一）一、选择题（20分）1．组成数据的基本单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（）的逻辑结构。

(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（）个。

(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题(30分)1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

数据结构模拟题1一、判断题。

判断下列各题是否正确，若正确，在答题卡中涂“A”，否则涂“B”。

1．数据的存储结构也称为物理结构，指数据的逻辑结构在计算机中的映象，它包括数据元素的映象和数据元素关系的映象。

√2．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。

Χ3．在顺序表中，插入和删除时移动元素的个数与该元素的位置有关。

√4．链表的每个结点中都恰好包含一个指针。

Χ5．链表只能借助于指针和动态变量来实现。

Χ6．对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。

√7．若一个队列入队的次序为1234，则出队的次序也一定是1234。

√8．若一棵二叉树的任意一个非叶子结点的度都为2，则该二叉树是满的。

Χ9．二叉树中所有结点个数是2k-1-1，其中k是树的深度。

Χ10．用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

√11．满二叉树不一定是完全二叉树。

Χ12．使用递归也可以实现二叉树的先序、中序和后序遍历。

√13．对二叉排序树进行中序遍历得到的序列是由大到小的。

14．哈夫曼树是带权路径长度最小的二叉树，路径上权值较大的结点离根较近。

√15．邻接表存储结构只用于有向图的存储，邻接矩阵对有向图和无向图的存储都适用。

Χ二、单选题。

1．数据的最小单位是【】。

AA、数据项B、数据类型C、数据元素D、数据变量2．从逻辑上可以把数据结构分为【】两大类。

CA、动态结构、静态结构B、顺序结构、链式结构C、线性结构、非线性结构D、初等结构、构造型结构3．【】不是要关注程序的时间复杂性的原因。

BA、确定程序运行时间的上限B、判断一个计算机系统是否有足够的内存来运行该程序C、正在开发的程序可能需要提供一个满意的实时响应D、在多种可选的方案中决定采用哪一个4．【】是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性数据结构。

CA、线性表B、栈C、队列D、树5．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为【】。

《数据结构》模拟试题13一、填空题（每小题2分，共18分）1、数据的逻辑结构包括，和三种结构。

2、队列是操作受限的线性结构，只能在插入元素，而在删除元素。

3、串是一种特殊的线性表，其特殊性体现在。

4、有一个10阶对称矩阵A，采用压缩存储方式采用压缩存储方式，以行为主存储下三角形到一个一维数组中，A[0][0]的地址是100（每个元素占2个基本存储单元），则A[5][9]的地址是。

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。

6、对于一个有n个顶点和e条边的无向图，若采用邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。

7、对线性表进行二分查找时，要求线性表必须是，且要求。

8、对于文件，按物理结构划分，可分为顺序文件、文件、文件和多关键字文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、如下函数是求1!+2!+…+n!，其时间复杂度是（）。

Long int Sum (int n){ long int sum=0 , t=1 ; int p ;for (p=1; p<=n ;p++) { t=t*p ; sum+=t ; }return(sum) ;}（A）O(n) （B）O(n2) （C）O(㏒2n) （D）O(n㏒2n)2、设有一个栈顶指针为top的顺序栈S，则弹出S的栈定元素的操作是（）。

（A）p=S[top++]；（B）p=S[++top]；(C)p=S[top--]；（D）p=S[--top]；3、广义表((a),((b),c),(((d))))的表头是，表尾是。

（）（A）(a) ((b),c),(((d))) （B）(a) (((b),c),(((d))))（C）((a),((b),c)),(((d))) （D）(a) (((d)))4、一棵二叉树，其先序遍历序列是abdgehicf，中序遍历序列是gdbheiafc，则其后序遍历序列是( )。

《数据结构》模拟试卷及参考答案模拟试卷一一、单选题（每题2 分，共20分）1.以下数据结构中哪一个是线性结构？( )A. 有向图B. 队列C. 线索二叉树D. B树2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3.以下哪一个不是队列的基本运算？（）A. 在队列第i个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( )个不同的字符串？A.14B.5C.6D.85.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

以下6-8题基于图1。

6.该二叉树结点的前序遍历的序列为( )。

A.E、G、F、A、C、D、BB.E、A、G、C、F、B、DC.E、A、C、B、D、G、FD.E、G、A、C、D、F、B7.该二叉树结点的中序遍历的序列为( )。

A. A、B、C、D、E、G、FB. E、A、G、C、F、B、DC. E、A、C、B、D、G、FE.B、D、C、A、F、G、E8.该二叉树的按层遍历的序列为( )。

A．E、G、F、A、C、D、B B. E、A、C、B、D、G、FC. E、A、G、C、F、B、DD. E、G、A、C、D、F、B9.下面关于图的存储的叙述中正确的是( )。

A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建堆的结果?( )A. a，g，h，m，n，p，q，x，zB. a，g，m，h，q，n，p，x，zC. g，m，q，a，n，p，x，h，zD. h，g，m，p，a，n，q，x，z二、填空题（每空1分，共26分）1.数据的物理结构被分为_________、________、__________和___________四种。

《数据结构》模拟试题03一、单项选择题（每题 2 分，共30分）1．算法指的是（ ）A ．计算机程序B ．解决问题的计算方法C ．排序算法D ．解决问题的有限运算序列 2．线性表采用链式存储时，结点的存储地址（ ） A ．必须是不连续的 B ．连续与否均可 C ．必须是连续的D ．和头结点的存储地址相连续3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（ ） A ．O （1） B ．O （n ） C ．O （m ） D ．O （m+n ） 4．由两个栈共享一个向量空间的好处是：（ ） A ．减少存取时间，降低下溢发生的机率 B ．节省存储空间，降低上溢发生的机率 C ．减少存取时间，降低上溢发生的机率 D ．节省存储空间，降低下溢发生的机率5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作后其头指针front 值为（ ）A ．front=front+1B ．front=(front+1)%(m-1)C ．front=(front-1)%mD ．front=(front+1)%m 6．如下陈述中正确的是（ ）A ．串是一种特殊的线性表B ．串的长度必须大于零C ．串中元素只能是字母D ．空串就是空白串7．若目标串的长度为n ，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）A ．O （n3） B ．O （n ） C ．O （n2） D ．O （n3）8．一个非空广义表的表头（ ）A ．不可能是子表B ．只能是子表C ．只能是原子D ．可以是子表或原子 9．假设以带行表的三元组表表示稀疏矩阵，则和下列行表对应的稀疏矩阵是（ ）5A.08067000000050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥B.08067000504000000300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥C.08060000020050400000--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥D.08060000700050400300--⎡⎣⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥10．在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( ) A．4 B．5 C．6 D．711．在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )A．e B．2e C．n2－e D．n2－2e12．假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是（）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进行高效率查找的组织结构是（）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长文件是指（）A．文件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定二、填空题（每题2分，共20分）1．数据的逻辑结构是从逻辑关系上描述数据，它与数据的无关，是独立于计算机的。