数据结构模拟题ds

数据结构_模拟测验题1-4(带答案)单元测验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）。

模拟试卷一、选择题1.对有14个元素的有序表A[l]-A[14]作对半查找，查找元索A[4]时的被比较元索依次为() A. A[1],A[2],A[3],A[4] C. A[1],A[2],A[7],A[4] B.A[7],A[3],A[5],A[4] D.A[7], [A5],A ⑶,A[4]2.关键路径是AOE 网中 A.从起点到终点的最长路径 C.最长的回路()B.从起点到终点的最长路径 D.最短的回路3.以数组QlO..m-l]存放循坏队列屮的元索，变量rear 和qulen 分别指示循环队列屮队尾元索 的实际位置和当前队列中元素的个数，队列第一个元素的实际位置是 ()A. rear —qulen C. m —qulenB. rear —qulcn+m D. 1 + (rear+m —qulen)% m4、设有一个长度为1()()且已排好序的表，用对半搜索进行杳找，若搜索不成功，则至少要比佼 ________ 次。

( ) A. 9 B. 8 C. 7 D. 65、高度为h 的二叉树中只有度为0和度为2的结点，则此类二叉树中包含的结点数至少是多少?( )10. n 个记录的文件被分成m 个初始游程，采用k 路合并时，总的比较次数为 _____ 。

()A. n(k-l )P10gkITlB. n(k-l)|~log2in~|C. (k-l )Piogkm~|D. m(k-l )PlogkH~|二、填空题1. 数据结构研究的三个方面是逻辑结构、 _____________ 和 ___________ OA. O(n*e)B• O(n+e )C. O(e)D ・ O(n)9、用某种排序方法对关 键字序列 (25, 84, 21, 47, 15, 27, 68, 35, 排序结果如下：20, 15, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 47, 27, 68, 35, 8415, 20, 21, 25, 35, 27, 47, 68, 8415, 20, 21, 25, 27, 35, 47, 68, 8415, 20, 21, 25, 27, 35, 47, 68, 84C.冒泡排序20)进行排序时，各趟8、假设一个冇n 个顶点和c 条弧的冇向图用邻接表表示, 时间复杂度是 则所采用的排序方法是 _________ oA.选择排序B.直接插入排序 A. h-1 B. h+1C. 2h-lD. 2h+l则删除与某个顶点W 相关的所冇弧的 ( ) D.快速排序2.数据的逻辑结构是指_______________________ ,有__________ 结构、线性结构、 _____ 结构和图结构四类。

数据结构复习样题一. 单项选择题（共12分）请将所选项的编号填入各题左边的括号内【】 1. 组成数据的基本单位是[A] 数据项 [B] 数据元素 [C] 数据类型 [D] 数据变量【】 2. 采用链式存储结构便于实现对线性表的[A] 插入 [B] 遍历 [C] 查找 [D] 定位【】 3. 若循环队列用数组A[0..m-1]存放元素，其头尾指针分别为front和rear，则当前队列的长度是[A] (rear–front+m)% m [B] rear–front+1[C] rear–front–1 [D] (rear–front)% m【】 4. 已知广义表 A =（（a，b，c），（d，e，f）），从表A中取出原子e的运算是[A] tail(tail(head(A))) [B] head(tail(tail(A)))[C] tail(head(tail(head(A)))) [D] head(tail(head(tail(A))))【】 5. 具有2000个结点的二叉树，其高度至少为[A] 9 [B] 10 [C] 11 [D] 12【】 6. 在邻接矩阵A中，第i顶点的入度为A中[A] 第i行非∞元素个数 [B] 第i列非∞元素个数[C] 第i行非∞且非0元素个数 [D] 第i列非∞且非0元素个数【】 7. 对一个长度为12 的有序表进行等概率的折半查找，查找成功所需的关键字比较平均次数为[A] 35/12 [B] 37/12 [C] 39/12 [D] 43/12【】 8. 如果对下列顺序表分别作快速排序，所需比较次数最少的是[A] (4,1,3,7,5,2,6,8) [B] (4,2,8,6,1,7,5,3)[C] (5,1,4,3,7,2,8,6) [D] (1,2,3,4,5,6,7,8)二. 填空题(共12分)9. 构成抽象数据类型的三个要素是___________________、___________________和___________________。

一．填空题1、数据结构被形式地定义为（D, R），其中D是（1）的有限集合，R是D上的（2）有限集合。

2、线性结构中元素之间存在（3）关系，树形结构中元素之间存在（4）关系，图形结构中元素之间存在（5）关系。

3、向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动（6）个元素。

4、从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为（7）。

5、在具有n个结点的二叉链表中，有（8）个空链域。

6、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为19的结点的左孩子的编号为（9）。

7、含有4个结点的不相似的二叉树有（10）棵。

8、任何一棵二叉树，若n0，n2分别是度为0，2的结点的个数，则n0和n2的关系为（11）。

9、有n个顶点的强连通有向图G至少有（12）条弧。

10、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个（13）。

11、Prim算法的功能是（14）。

12、若含n个顶点的图形成一个环，则它的生成树有（15）种。

二．选择题1、算法分析的两个主要方面是：（）A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性2、栈和队列都是（）A．限制存取位置的线性结构 B．顺序存储的线性结构C．链式存储的线性结构 D．限制存取位置的非线性结构3、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动( )个元素A. 8B. 63.5C. 63D. 74、链表是一种采用( ) 存储结构存储的线性表；A. 顺序B. 链式C. 星式D. 网状5、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A s→next=p→next; p→next =s;B p→next =s; s→next =q;C p→next =s→next; s→next =p;D q →next =s; s→next =p;6、栈的插入和删除操作在（）进行。

第一部分选择题一、单项选择题（本大题共20小题，每小题1分，共20分）1．计算机算法指的是，它必须具备输入、输出和【】A．计算方法B．排序方法C．解决问题的有限运算步骤D．程序设计方法2．下列算法的时间复杂度是【】for（i=0；i<n；i++）c[i][j]＝i＋j；A .O（l） B.O（n） C.O（log2n） D.O（n2）3．在单链表的一个节点中有【】A．l个指针B．2个指针C．0个指针D。

3个指针4．在具有n个节点的单链表中做插入、删除运算，平均时间复杂度为【】A．O（l）B。

O（n）C．O（log2n）D．O（n2）5．向一个栈顶指针top的链栈中插入一个S所指节点时，执行【】A．top－＞next＝s；B．s－＞next＝top－＞next；top一＞next＝s；C．s－＞next＝top；top＝s；D．s－＞next＝top；top＝top－＞next；6．栈结构通常采用的两种存储结构是【】A．散列方式和索引方式B．顺序存储结构和链表存储结构C．链表存储结构和数组D．线性存储结构和非线性存储结构7．设s1＝””，则strlen(s1)＝【】A．0 B．1 C。

2 D．38．设目标串T＝”aabbccddbbaa”，模式P=”bb”，则该模式匹配的有效位移为【】A．1 B．2 C．3 D．49．数组与一般线性表的区别主要在【】A．存储方面B．元素类型一致C．逻辑结构方面D．不能进行插入、删除运算10设二线数组A［0。

m-l］[0。

n-1]按行优先顺序存储在内存中，每个元素占d个字节，则元素A[i][j]的地址为【】A．LOC（A[1][1]）＋［（i-1）*n＋j-l］*dB．LOC（A[0][0]）＋［（i-l）*n＋j-1］*dC．LOC（A[1][1]）＋［(j-l)* n＋i–1］*dD．LOC（A[0][0]）＋［（j-l）*n＋i-1］*d11具有n个节点的完全二叉树的深度为【】A．log2n +1 B．log2n＋lC．log2n D．log2n12在具有n（n>l）个节点的完全二叉树中，节点i（2i＞n）的左孩子节点是【】A．2i B．2i＋lC．不存在D．是2i-l13．在一个图中，所有顶点的度数之和等于图的边数的几倍。

模拟试卷二一、选择题（每小题2分，共10分）在下列备选答案中选出一个正确的，将其号码填在“”上。

1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。

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

（1）先序（2）中序（3）后序（4）从根开始的层次遍历3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二叉树。

（1）空或只有一个结点（2）高度等于其结点数（3）任一结点无左孩子（4）任一结点无右孩子4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（nlog2n）的是。

（1）堆排序（2）冒泡排序（3）直接选择排序（4）快速排序5．下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

（1）堆排序（2）冒泡排序（3）快速排序（4）SHELL排序二、判断题（每小题1分，共10分）判断下列各题是否正确，若正确，在（）内打“√”，否则打“×”。

1．（）在循环队列中，若尾指针Rear大于头指针Front，则其元素数为Rear-Front。

2．（）串是N个字母的有限序列（N =0）。

3．（）若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。

4．（）二叉树只采用二叉多链表来存储。

5．（）有向图用邻接矩阵表示后，顶点I的出度等于第I行中非0且非的元素个数。

6．（）图Ｇ的最小生成树的代价一定小于其他生成树的代价。

7．（）给定结点数的平衡二叉树的高度是唯一的。

8．（）９阶Ｂ树中，除根以外的任一结点中的关键字个数不少于４。

9．（）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。

10．（）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。

三、填空（每小题２分，共２０分）1．在单链表中，册除指针Ｐ所指的后继结点的语句是。

《数据结构》模拟试题一、单项选择题（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___。

模拟试卷七一、选择题（每小题2分，共10分）在下列备选答案中选出一个正确的，将其号码填在“”上。

１．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则采用存储方式最节省时间。

（１）顺充表（２）双链表（３）带头结点的双循环链表（４）单循环链表２．在用邻接表表示图时，求最短路径的Dijkstra算法的时间复杂度为。

（１）O（n）（２）O（n+e）（３）O(n2)（４）O（n3）３．依次将待排序列中的元素和有序子序列合并为一个新的有序子序列的算法是。

（１）快速排序（２）插入排序（３）冒泡排序（４）堆排序４．在平稳二叉树中插入一个结点造成了不平稳，设最低的不平稳结点为A，并已知A 的左孩子的平稳因子为O，右孩子的平稳因子为1，则应作型调整以使其平衡。

（１）LL（２）LR （３）RL （４）RR５．已知数据表A中每个元素距其终位置不远，则采用排序算法最节省时间。

（１）堆排序（２）插入排序（３）快速排序（４）直接选择排序二、判断题（每小题1分，共10分）判断下列各题是否正确，若正确，在（）内打“√”，否则打“×”。

１．（）线性表就是顺序表。

２．（）链表只能借助于指针和动态变量来实现。

３．（）线性表的长度是指其中元素所占用的存储空间的字节数。

４．（）对广义表A=（a,(b,c),d）的运算head(tail(A))的结果不是b。

５．（）若一棵树中某结点的度为1，则该结点仅有一棵子树。

６．（）所谓平稳二叉树是指左右子树的高度差的绝对值不大于1的二叉树。

７．（）AOE网所表示的工程至少所需的时间等于从源头到汇点的最短路径的长度。

８．（）若从某顶点开始对有向图G进行深度遍历，所得的遍历序列唯一，则可断定其弧数为n-1。

９．（）理想情况下，在散列表中查找一个元素的时间复杂度为O（1）１０．（）快速排序算法在每一趟排序中都能找到一个元素放在其最终的位置上。

三、填空（每空2分，共20分）１．在带头结点的双循环链表L中，最后一个结点的指针是。

《数据结构》练习题（期末试卷题型：选择题15个，共15分；判断题10个，共10分；综合题5个，共50分；算法题2个，第1题算法填空15分，第2题算法设计10分。

）一、单项选择题(本大题共10小题，每小题2分，共20分)1.在决定选取何种存储结构时，一般不考虑( )A．各结点的值如何 B．结点个数的多少C．对数据有哪些运算 D．所用的编程语言实现是否方便2.设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作（ B ）A s->next=p->next; p->next=s;B q->next=s; s->next=pC p->next=s->next; s->next=p;D p->next =s; s->next=q;3. 在头指针为head的非空单循环链表中，指针p指向尾结点，下列关系成立的是（）。

A. p->next= =headB. p->next->next= =headC. p->next= =NULLD. p= =head4.一个栈的入栈序列为a，b，c，则出栈序列不可能的是( B )。

A c,b,aB b,a,cC c,a,bD a,c,b5.当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（）A n-2B n-1C nD n+16. 两个字符串相等的条件是（ D ）。

A. 串的长度相等B. 含有相同的字符集C. 都是非空串D. 串的长度相等且对应的字符相同7.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ 71 ）A 24B 73C 48D 538. 已知一棵完全二叉树有131个叶子结点，则该树可能达到的最大深度（B）。

A．7 B．8C．9 D．109. 如图所示的有向无环图下列哪一个序列不是其拓扑序列（）。

数据结构模拟试题一一、判定题（每题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．（第18页，第（5）题）确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。

(1) i=1; k=0;do {k=k+10*i; i++;} while(i<=n-1)划线语句的执行次数为 n-1 。

(2）i=1; x=0;do{x++; i=2*i;} while （i<n）;划线语句的执行次数为⎡logn⎤。

2(3) for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)for (int k=1;k<=j;k++)x++;划线语句的执行次数为n(n+1)(n+2)/6 。

(4）x=n;y=0;while(x>=(y+1)*(y+1)) y++;划线语句的执行次数为⎣√n ⎦。

第二章线性表1．第37页习题(2).2在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。

不利用类SeqList 提供的操作直接实现。

template <class T>void SeqList<T>::Invert(){T e;for (int i=1;i<=length/2;i++){e=elements[i-1];elements[i-1]=elements[length-i];elements[length-i]=e;}}2．第37页习题(5)在类SingleList中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。

template <class T>void SingleList<T>::invert(){Node<T> *p=first,*q;first=NULL;while (p){q=p->link; p->link=first;first=p; p=q;}}第三章栈与队列1．第50页习题(1）设A、B、C、D、E五个元素依次进栈(进栈后可立即出栈)，问能否得到下列序列。

模拟试卷一一、单项选择题1．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用存储方式最节省运算时间。

（1）单链表（2）双链表（3）单循环链表（4）带头结点的双循环链表2．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是。

（1）A,B,C,D （2）D,C,B,A （3）A,C,D,B （4）D,A,B,C3．串是。

（1）不少于一个字母的序列（2）任意个字母的序列（3）不少于一个字符的序列（4）有限个字符的序列4．链表不具有的特点是。

（1）可随机访问任一元素（2）插入删除不需要移动元素（2）不必事先估计存储空间（4）所需空间与线性表长度成正比5．在有n个叶子结点的哈夫曼树中，其结点总数为。

（1）不确定（2）2n （3）2n+1 （4）2n-16．任何一个无向连通图的最小生成树。

（1）只有一棵（2）有一棵或多棵（3）一定有多棵（4）可能不存在7．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为。

（1）98 （2）99 （3）50 （4）488．下列序列中，是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。

（1）[da,ax,eb,de,bb]ff [ha,gc] （2）[cd,eb,ax,da]ff[ha,gc,bb]（3）[gc,ax,eb,cd,bb]ff [da,ha] （4）[ax,bb,cd,da]ff[eb,gc,ha]9．用n个键值构造一棵二叉排序树，最低高度为。

（1）n/2 （2）n （3）⎣log2n ⎦（4）⎣log2n+1⎦10．二分查找法要求查找表中各元素的键值必须是排列。

（1）递增或递减（2）递增（3）递减（4）无序11．对于键值序列（12,13,11,18,60,15,7,18,25,100）,用筛选法建堆，必须从键值为的结点开始。

数据结构DS-练习题-3第3章栈和队列一选择题1. 对于栈操作数据的原则是（）。

【青岛大学】A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。

当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。

为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢③: A. n-1 B. n C. n+1 D. n/2④: A. 长度 B. 深度 C. 栈顶 D. 栈底⑤: A. 两个栈的栈顶同时到达栈空间的中心点.B. 其中一个栈的栈顶到达栈空间的中心点.C. 两个栈的栈顶在栈空间的某一位置相遇.D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.【上海海运学院】3. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。

A. 不确定B. n-i+1C. iD. n-i【中山大学 1999 一、9(1分)】6. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（）A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 6【北方交通大学】7. 设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。

【中科院计算所】A. 1，2，4，3，B. 2，1，3，4，C. 1，4，3，2，D. 4，3，1，2，E. 3，2，1，4，8. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 2【南开大学1】【山东大学】【北京理工大学】9. 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。

数据结构模拟卷（含答案）经典习题.doc 练习题⼀、单项选择题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. 散列存储和顺序存储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；ifor(j=1；js+=i*j；A.O(1)B.O(logn)C.O(n)D.O(n2)20. 已知指针p和q分别指向某单链表中第⼀个结点和最后⼀个结点。

《数据结构》模拟题一、单项选择题1、在数据结构中，从逻辑上可把数据结构分成（）A.动态结构和静态结构B.线性结构和非线性结构C.紧凑结构和非紧凑结构D.内部结构和外部结构2、线性表的顺序存储结构是一种（）的存储结构。

A.顺序存取B.索引存取C.散列存取D.随机存取3、组成数据的基本单位是（）A.数据项B.数据元素C. 数据类型D.数据变量4、线性表的链接实现有利于（）运算。

A. 查找B.读表元C.插入D.定位5、串的逻辑结构与（）的逻辑结构不同。

A.树B.栈C.队列D. 线性表6、串的长度是（）A.串中不同字符的个数B.串中所含字符的个数C.串中所含字符的个数且字符个数大于0D. 串中不同字母的个数7、下列不是数据的逻辑结构的是（）A.线性结构B.树型结构C.图型结构D.物理结构8、带头结点的单链表L为空的判定条件是（）A.L->next==NULLB.L==NULLC.L->next==LD.L!=NULL9、一个队列的入列序列是a,b,c,d，则队列的输出序列是（）A.d,c,b,aB. a,b,c,dC.d,b,c,aD.c,b,d,a10、下列程序段的时间复杂度为（）j=0;sum=0;while(sum<n){ j++; sum=sum+j;}n) D.O(n2)A. O(n)B. O(n)C.O(log411、下列程序段的时间复杂度为（）s=s0;for( i=1; i<=n; i++)for(j=n; j>=n-i; j- -)s=s+1;n) C.O(n2) D.O(n3/2)A.O(n)B.O(nlog212、判定一个循环队列Q（最多元素个数为m）为满队列的条件是（）A.Q.front==Q.rearB.(Q.rear+1)%m==Q.frontC.(Q.rear-1)%m==Q.frontD.(Q.front+1)%m==Q.rear13、判定一个栈S为空的条件是（）A.S.top!=0B.S.top!=S.lengthC.S.top==S.baseD. S.top=S.length14、已知广义表LS=(a,(b,c,d),e),则运用GetHead(GetHead(GetTail(LS)))所得结果为（）A.bB. (b,c,d)C.(b,c)D.e15、在一个长度为n的顺序表中向第i个元素（0<i≤ n+1）之前插入一个新的元素时，需向后移动的元素个数为（）A.n-iB.n-i-1C.iD.n-i+116、在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。

DS复习题2⼀、单项选择题（请将正确答案的字母填写在每⼩题对应的括号内，每⼩题1分，共20分）1、从逻辑上可以把数据结构分为（C ）两⼤类。

A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、⾮线性结构D．初等结构、构造型结构2、设有向图．．．的顶点个数为n，则该图最多有（ B ）条边。

A．n (n-1) B．n(n-1)/2 C．n(n+1)/2 D．n(n+1)3、设⼆维数组A[0..10,0..20]按⾏优先顺序存储，每个元素占4个存储单元，A[2,1]的存储地址是1000，则A[5,6]的存储地址是（B ）。

A．1021 B．1056 C．1260 D．12004、与线性表的链接存贮不相符合的特性是（C ）。

A．便于插、删运算B．需要连续的存贮空间C．只能顺序查找D．存贮空间动态分配5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数为（B ）。

A．(rear-front+m)%m B．rear-front+1C．(front+rear+m)%m D．(rear-front)%m6、⼀个连通图的⽣成树是⼀个（A ）连通⼦图，n个顶点的⽣成树有n-1条边。

A．极⼩B．极⼤C．最⼩D．最⼤7、设栈的⼊栈序列是1，2，3，4，则（）不可能是其出栈序列。

A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2，8、⼴义表（a,(b,c),d,e）的表头和表尾分别为（C ）。

A．a和(b,c),d,e B．（a）和(b,c),d,eC．a 和((b,c)，d,e) D．(a) 和((b,c)，d,e)9、栈和队都是（D ）A．顺序存储的线性结构B．链式存储的⾮线性结构C．限制存取点的⾮线性结构D．限制存取点的线性结构10、下列数据中不可能是平衡⼆叉树上结点的平衡因⼦的是（D ）。

A．-1 B．0 C．1 D．211、下列四个序列中，哪⼀个是堆（A．）。

题型：1.单选题：25*22.填空题：6*23.应用题：284.算法题：10数据结构与算法（样例）一．单项选择题：共10小题、每题2分，满分20分；将答案填入题中的括号中。

1．在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。

A、n-iB、n-i+1C、n-i-1D、i2．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行。

A、HL = p; p->next = HL;B、p->next = HL; HL = p;C、p->next = HL; p = HL;D、p->next = HL->next; HL->next = p;3．在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行。

A、p = q->next ; p->next = q->next;B、p = q->next ; q->next = p;C、p = q->next ; q->next = p->next;D、q->next = q->next->next; q->next = q;4．栈的插入与删除操作在进行。

A、栈顶B、栈底C、任意位置D、指定位置5．若让元素1，2，3依次进栈，则出栈次序不可能出现种情况。

A、3，2，1B、2，1，3C、3，1，2D、1，3，2 6．在一个循环顺序队列中，队首指针指向队首元素的位置。

A、前一个B、后一个C、当前D、后面7．在所有排序方法中，关键字比较次数与记录的初始排列次序无关的是。

A、直接插入排序B、起泡排序C、快速排序D、直接选择排序8．假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是。

A、front==rearB、front!=NULLC、rear!=NULLD、front==NULL9. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。