《数据结构》模拟试卷八

模拟试卷七一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。

每小题1分，共10分）1．假设执行语句S的时间为O（1），则执行下列程序段for(i=1;i<=n;i++)for(j=i;j<=n;j++)S;的时间为( )A）O（n）B）O（n2）C）O（n*i）D）O（n+i）2．设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能的出栈序列是（）。

A）1，2，3，4，5，6 B）2，1，3，4，5，6C）3，4，2，1，5，6 D）4，3，2，1，5，63．设单链表的结点结构为(data,next)，已知指针q所指结点是指针p所指结点的直接前驱，如在*q与*p之间插入结点*s，则应执行的操作为（）。

A）s->next=p->next; p->next=s; B）q->next=s; s->next=p;C）p->next=s-next; s->next=p; D）p->next=s; s-next=q;4．串S='ABC DEF'的串长为（）。

A）3 B）4C）7 D）85．下面二叉树按（）遍历得到的序列是FEDBIHGCA。

A）先序B）中序C）后序D）层次6．用Floyd算法求每一对顶点之间的最短路径的时间复杂度为（）。

A）O(n) B）O(n2)C）O(n3) D）O(nlogn)7．具有n个顶点的无向图，它可能具有的边数的最大值为（）。

A）(n2+n)/2 B）n2C）(n2-n)/2 D）n8．二分查找法要求被查找的表是（）。

A）顺序表B）链接表C）顺序表且是按值递增或递减次序排列D）不受上述的任何限制9．在一待散列存储的线性表（18，25，63，50，42，32，90），若选用h(k)=k % 7作为散列函数，则与元素18冲突的元素有( )个。

A）0 B）1C）2 D）310．在下列排序算法中，不稳定的是（）。

试卷一一、选择题（本题共30分,每题2分）1. 计算机识别、存储和加工处理的对象被统称为________。

A. 数据B. 数据元素C. 数据结构D. 数据类型2. 已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。

A．1234 B．4321 C．2143 D．41233.链表不具有的特点是________。

A. 随机访问B. 不必事先估计所需存储空间大小C. 插入与删除时不必移动元素D. 所需空间与线性表长度成正比4. 设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。

经过以下队列操作后，队头的值是________InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x)A. aB. bC.NULLD.x5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。

A．p=q->next; p->next=q->next;free(p);B．p=q->next; q->next=p; free(p);C．p=q->next; q->next=p->next; free(p);D．q->next=q->next->next; q->next=q; free(p);6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。

A．110 B．108 C．100 D．1207. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是________。

A. n-iB. n-i+1C. n-i-1D. i8．下面关于线性表的叙述错误的是________。

A. 线性表采用顺序存储必须占用一片连续的存储空间B. 线性表采用链式存储不必占用一片连续的存储空间C. 线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

数据结构模拟试题一一、判断题（每小题1 分，共15分）1.计算机程序处理的对象可分为数据和非数据两大类。

2.全体自然数按大小关系排成的序列是一个线性表。

3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。

4.顺序栈是一种规定了存储方法的栈。

5.树形结构中的每个结点都有一个前驱。

6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。

7.若某顶点是有向图的根，则该顶点的入度一定是零。

8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。

9.用一维数组表示矩阵可以节省存储空间。

10.广义表的长度与广义表中含有多少个原子元素有关。

11.分块查找的效率与线性表被分成多少块有关。

12.散列表的负载因子等于存入散列表中的结点个数。

13.在起泡排序过程中，某些元素可能会向相反的方向移动。

14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。

15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。

二、填空题（每空1分，共15分）1.顺序表是一种_____________线性表。

2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。

3.栈和队列的区别在于________的不同。

4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。

5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域为空的结点。

6.n个顶点的有根有向图中至少有___条边，至多有___条边。

7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。

8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是_____。

9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。

数据结构模拟试卷八一、选择题1．一个栈的输入序列为1 2 3 4 5 ，则下列序列中不可能是栈的输出序列的是___________。

A.1 2 3 4 5B.5 4 3 2 1C.2 3 4 5 1D.4 1 2 3 52．一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为___________。

A.0B.1C.2D.不确定3．在用邻接表表示图的情况下，拓扑排序算法的时间复杂度为___________。

A.o(n+e)B.o(n2)C.o(n*e)D.o(n3)4．下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是___________。

A.直接插入排序B.快速排序C.直接选择排序D.堆排序5．下列排序算法中，依次将待排序序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是___________。

A.直接插入排序B.冒泡排序C.快速排序D.直接选择排序二、判断题1．设指针P指向单链表中一个结点，则语句序列U:=P^.next;U:=U^.next将删除一个结点。

2．栈和队列都是运算受限的线性表。

3．广义表的长度是指广义表中的原子个数。

4．若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。

5．二叉树在按任一种次序线索化后，都可以很容易地求出相应次序下的前趋和后继。

6．在采用线性探测法处理冲突的散列表中，所有同义词在表中相邻。

7．对B树中任一非叶子结点中的某关键字K,比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。

8．若一个无向图的以顶点1为起点的深度遍历序列唯一，则可唯一确定该图。

9．在对一有向无环图执行拓扑排序算法之后，入度数组中的所有元素的值为0。

10．在数据表基本有序时，冒泡排序算法的时间复杂度一定接近o(n)。

三、填空题1．在单链表中，在指针P所指结点的后面插入一个结点S^的语句序列是___________。

2．已知一个栈的输入序列为123…n，则其输出序列的第二个元素为n的输出序列的个数是___________。

苏州大学《数据结构》课程期中试卷共 10 页参考答案一、单项选择题（20%）1、数据结构是一门研究____的程序设计问题中，计算机的操作对象及其关系和操作等的学科。

[A]:数据类型[B]:抽象数据类型[C]:数值计算[D]:非数值计算[答案1]:D2、计算机科学知识体中，数据结构课程属于____领域的综合性专业基础课。

[A]:离散结构Discrete Structures (DS)[B]:程序设计语言Programming Languages (PL)[C]:算法与复杂性Algorithms and Complexity (AL)[D]:程序设计基础Programming Fundamentals (PF)[答案2]:D3、数据结构中，与计算机存储器无关的是数据的_____结构。

[A]:物理[B]:线性[C]:存储[D]:逻辑[答案3]:D4、数据结构可记为DS = {D, R}，其中D是数据对象，R是D中所有成员之间_____的有限集合。

[A]:操作[B]:组织[C]:运算[D]:关系[答案4]:D5、具有相同性质的数据集合及在这个集合上的一组____，称为数据类型。

[A]:结构[B]:算法[C]:关系[D]:操作[答案5]:D6、数据的物理结构不包括_____。

[A]:顺序(sequence)[B]:链接(link)和数组[C]:索引(index)和散列(Hash)[D]:树(tree)和图(graph)[答案6]:D7、在n较大情况下，下列时间复杂度T(n)中，效率较高的为_____。

[A]:O(2n)[B]:O(10*n2)[C]:O(10*n)[D]:O(100*log2n)[答案7]:D8、顺序表的特点有_____。

[A]:插入、删除效率高[B]:存储空间能动态分配[C]:逻辑关系与物理位置不一致[D]:可方便随机存取数据元素[答案8]:D9、链表的特点有_____。

[A]:插入、删除效率低[B]:逻辑关系与物理位置一致[C]:存储空间不能静态分配[D]:随机存取数据元素效率低[答案9]:D10、链表用一组任意的存储单元来依次存放线性表的结点，这组存储单元_____。

《数据结构》模拟试题一、单项选择题（30分）1．在数据结构的讨论中把数据结构从逻辑上分为C。

A. 内部结构与外部结构B. 静态结构与动态结构C. 线性结构与非线性结构D. 紧凑结构与非紧凑结构。

2．算法分析的两个主要方面是 D。

A. 正确性和简明性B. 可读性和文档性C. 数据复杂性和程序复杂性D. 空间复杂性和时间复杂性3．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储B。

A. 数据的处理方法B. 数据元素的类型C. 数据元素之间的关系D. 数据的存储方法4．设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为c。

A.5B.6C.7D.95．线性表采用链式存储结构时，要求内存中可用存储单元的地址d。

A. 必须是连续的B. 必须是部分连续的C. 一定是不连续的D. 连续和不连续都可以6．对具有n个结点的线性表进行插入和删除操作，所需的算法时间复杂度为 d。

A. O(1)B. O(n)C. O(nlog2n)D. O(n2)7．在单链表中指针p所指结点之后插入指针为s的结点，正确的操作是b。

A. p->next=s;s->next= p->next;B. s->next= p->next; p->next=s;C. p->next=s; p->next = s->nextD. p->next=s->next; p->next=s; 8．栈中元素的进出原则是b。

A．先进先出 B．先进后出 C．栈空则进 D．栈满则出9．长度是n的顺序循环队列，front和rear分别指示队首和队尾，判断队列为满队列的条件是__d____。

A．rear=0 B．front=0C．rear==front D．（rear+1）%n==front10．下面说法不正确的是_____c_____。

A．广义表的表头总是一个广义表 B．广义表的表尾总是一个广义表C．广义表难以用顺序存储结构 D．广义表可以是一个多层次的结构11．已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为____d___。

计算机专业基础综合（数据结构）模拟试卷8(题后含答案及解析) 题型有：1. 单项选择题 2. 综合应用题单项选择题1-40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

1．若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则下面最节省运算时间的存储方式是( )。

A．单链表B．带有头指针的单循环链表C．双链表D．带有尾指针的单循环链表正确答案：D解析：在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。

考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是O(1)，所以答案是D。

知识模块：数据结构2．已知两个长度分别为l和s的降序链表，若将它们合并为一个长度为l+s 的升序链表，则最坏情况下的时间复杂度是( )。

A．D(l)B．D(ls)C．D(min(l，s))D．D(max(l，s))正确答案：D解析：在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是m和n中的最大值。

知识模块：数据结构3．线性表中存放的主要是( )。

A．整型常量B．字符C．数据元素D．信息元素正确答案：C解析：线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。

知识模块：数据结构4．下面的叙述中正确的是( )。

I．线性表在链式存储时，查找第i个元素的时间同i的值成正比Ⅱ．线性表在链式存储时，查找第i个元素的时间同i的值无关Ⅲ．线性表在顺序存储时，查找第i个元素的时间同i的值成正比A．仅ⅠB．仅ⅡC．仅ⅢD．Ⅰ、Ⅱ、Ⅲ正确答案：A解析：在线性表链式存储结构中，查找第i个元素的时间与i的位置成正比。

而在顺序存储结构中查找第i个元素的时间与i的位置无关。

知识模块：数据结构5．对于某线性表来说，主要的操作是存取任一指定序号的元素和在最后进行插入运算，那么应该选择( )存储方式最节省时间。

数据结构模拟卷(含答案)经典习题练习题一、单项选择题1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( )A. 操作的有限集合B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( )A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是( )A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( )A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是( )A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 数据结构是（）A．一种数据类型B．数据的存储结构C．一组性质相同的数据元素的集合D．相互之间存在一种或多种特定关系的数据元素的集合8. 算法分析的目的是（）A．辨别数据结构的合理性B．评价算法的效率C．研究算法中输入与输出的关系D．鉴别算法的可读性9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是（）A．插入B．删除C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )11. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为(）A．15 B．16C．17 D．1812. 二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（）A．1213 B．1209C．1211 D．120713. 在按中序遍历二叉树的算法中，需要借助的辅助数据结构是（）A．队列B．栈C．线性表D．有序表14. 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（）A．不一定相同B．都相同C．都不相同D．互为逆序15. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A．层次遍历算法B．前序遍历算法C．中序遍历算法D．后序遍历算法16. 若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（）A．图中每个顶点的入度B．图中每个顶点的出度C．图中弧的条数D．图中连通分量的数目17. 图的邻接矩阵表示法适用于表示（）A．无向图B．有向图C．稠密图D．稀疏图18. 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为（）A．f,c,b B．f,d,bC．g,c,b D．g,d,b19. 下面程序段的时间复杂度为( )s=0；for(i=1；i<n；i++)for(j=1；j<i；j++)s+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)20. 已知指针p和q分别指向某单链表中第一个结点和最后一个结点。

《数据结构》模拟试卷及参考答案模拟试卷一一、单选题（每题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.数据的物理结构被分为_________、________、__________和___________四种。