《数据结构》全真模拟试题与解答02

数据结构模拟题及答案一、填空题（每小题 1 分，共 20 分）：1、栈是一种 _____________的线性表，队列是一种_____________的线性表(要求填特性)。

2、___________________是数据的基本单位，可由若干个_______________ 组成，______________是数据的最小单位。

3、具有 354个结点的完全二叉树深度为 ________________，树中度为1的结点数为______________。

4、数组的运算有______________________________________ 和____________________________。

5、稀疏矩阵的压缩存储一般采用_____________________________存储方式。

6、广义表运算：tail ((( a, b ), ( c , ( d, e )))) = _______________________ 。

7、数据结构中评价算法的两个重要指标是__________ 、__________ 。

8、一个算法具有 5个特性: 、、，有零个或多个输入、有一个或多个输出。

9、已知指针p指向单链表L中的某结点，则删除其后继结点的语句是: 。

10、Prim（普里姆）算法适用于求______ 的网的最小生成树；kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。

11、 N个顶点的连通图的生成树含有 ______ 条边。

12、顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为 __ __ 次；当使用监视哨时，若查找失败，则比较关键字的次数为_ _ __ 。

13、若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。

14、直接插入排序用监视哨的作用是 ___________________。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

模拟试卷二一、选择题（每小题2分，共10分）1．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用存储方式节省时间。

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

a．无序 b．中序c．后序 d．从根开始的层次遍历3．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是的二又树。

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

a．堆排序 b. 冒泡排序c．直接选择排序 d. 快速排序5. 下列排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。

a．堆排序 b．冒泡排序c．快速排序 d. SHELL排序二、判断题（每小题1分，共10分）1．（）在循环队列中，若尾指针Rear大于头指针Front，则其元素个数为 Rear - Front。

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

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

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

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

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

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

8.（）9阶B树中，除报以外的任一结点中的关键字个数不少于4。

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

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

三、项空（每小题2分，共20分）l. 在单链表中，删除指针P所指结点的后继结点的语句是。

2．取出广义表A = ((x，y，z），（a，b，c，d）)中原子b的函数是。

第一章概论一、名词解释数据表示2.数据处理3.数据4.数据元素5.逻辑关系6.逻辑结构7.结构8.运算9.基本运算10.存储结构11.顺序存储结构12.链式存储结构13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构二、填空题1.计算机专业人员必须完成的两项基本任务是：_________和__________。

2.数据在计算机存储器中的存在形式称为_________。

3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据的__________的实现。

此外，该课程还要考虑各种结构和实现方法的__________。

4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。

5.存储结构是逻辑结构的__________实现。

6.数据表示任务是逐步完成的，即数据表示形式的变化过程是__________->__________->__________。

7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。

8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、__________和__________。

9.根据需要，数据元素又被称为__________、__________、__________或__________。

10.在有些场合下，数据项又称为__________或__________，它是数据的不可分割的最小标识单位。

11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个__________构成，数据元素可由若干个__________构成。

《数据结构》模拟试题一、单项选择题（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）(1/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

第1题堆排序的最坏时间复杂度为( )A.O(n)B.O(10g2n)C.O(nlog2n)D.O(n2)下一题(2/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

第2题对广义表((a)，(b))进行下面的操作head(head((a)，(b)))后的结果是( )A.aB.(a)C.( )D.不确定上一题下一题(3/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

第3题已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是( )A.a c b e dB.d e c a bC.d e a b cD.c e d b a上一题下一题(4/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

第4题判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )A.求关键路径的方法B.求最短路径的Dijkstra方法C.广度优先遍历方法D.深度优先遍历方法上一题下一题(5/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

第5题将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为( )A.42C.21D.20上一题下一题(6/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

第6题设数组A[0,m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作的语句是( )A.sq.front=(sq.front+1)%mB.sq.front=(sq.front+1)%(m+1)C.sq.rear=(sq.rear+1)%mD.sq.rear=(sq.rear+1)%(m+1)上一题下一题(7/15)单项选择题在每小题列出的四个选项中只有一个选项是符合题目要求的。

数据结构模拟卷(含答案)经典习题练习题一、单项选择题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.数据的物理结构被分为_________、________、__________和___________四种。

数据结构模拟考试（总分100分，考试时长90分钟）一、单项选择题（每小题2 分，共 100分）1、一棵具有 n 个结点的完全二叉树的树高度(深度)是( A )A、「log2n」+1B、log2n+1C、「log2n」D、log2n-12、若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为A、O(n)B、O(0)C、O(1)D、O(n^2)3、一个顺序栈S,空栈时top的初始值为0,其栈顶指针为top,则将元素e入栈的操作是( )。

A、*S->top=e;S->top++;B、S->top++;*S->top=e;C、*S->top=eD、S->top=e;4、下列几种排序方法中要求辅助空间最大的是( )A、堆排序B、直接选择排序C、归并排序D、快速排序5、给定排序码值序列为{F，B，J，C，E，A，I，D，C，H}，对其按字母的字典序列的次序进行排列，冒泡排序(大数下沉)的第一趟排序结果应为A、{B，F，C，J，A，E，D，I，C，H}B、{C，B，D，A，E，F，I，C，J，H}C、{B，F，C，E，A，I，D，C，H，J}D、{A，B，D，C，E，F，I，J，C，H}6、对含有 10 个数据元素的有序查找表执行折半查找,当查找失败时,至少需要比较( )次。

A、2B、3C、4D、57、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A、r-fB、(n+f-r)%nC、n+r-fD、（n+r-f)%n8、若长度为 n 的线性表采用顺序存储结构，访问其第 i 个元素的算法时间复杂度为（）A、0 ( 1 )B、0 ( n )C、0 ( n2 )D、0 ( log2n )9、(6分)若希望1000个无序元素中尽快求得前10个最大元素,应借用(A)。

数据结构模考试题及答案一、单选题（共100题，每题1分，共100分）1、下面关于生成树的描述中，不正确的是( )A、生成树是树的一种表现形式B、生成树一定是连通的C、生成树一定不含有环D、若生成树顶点个数为n，则其边数一定为n-1正确答案：A2、用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。

A、图B、栈C、队列D、树正确答案：C3、下列四种基本的逻辑结构中，结构结点间不存在任何逻辑联系的是（）A、集合B、树形结构C、图形结构D、线性结构正确答案：A4、以下数据结构中，哪一个是线性结构（）。

A、线索二叉树B、二叉树C、有向图D、串正确答案：D5、n个顶点的连通图至少中含有( )边。

A、n-1B、n+1C、nD、0正确答案：A6、G是一个非连通无向图，共有28条边，则该图至少有( )个顶点。

A、7B、8C、6D、9正确答案：D7、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（）。

A、rear=front->nextB、front=rear->nextC、front=front->nextD、rear=rear->next正确答案：C8、一个栈的输入序列是 1 2 3 4 5，则下列序列中是栈的输出序列的是（）。

A、1,4,2,5,3B、3,1,2,4,5C、2,3,4,1,5D、5,4,1,3,2正确答案：C9、假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正确答案：B10、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。

A、存储结构B、操作C、逻辑结构D、算法正确答案：C11、深度为k的完全二叉树中最少有（）个结点。

《数据结构》模拟试题A一、单项选择题（每题 3 分，共24分）1．下面关于线性表的叙述错误的是（）。

(A) 线性表采用顺序存储必须占用一片连续的存储空间(B) 线性表采用链式存储不必占用一片连续的存储空间(C) 线性表采用链式存储便于插入和删除操作的实现(D) 线性表采用顺序存储便于插入和删除操作的实现2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

(A)2m-1 (B)2m (C) 2m+1 (D) 4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。

(A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

(A) BADC (B) BCDA (C) CDAB (D) CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。

(A) n(n-1)/2 (B) n(n-1) (C) n2 (D) n2-16．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。

(A) 9(B) 10(C) 11(D) 127．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

(A) n-1 (B) n (C) n+1 (D) 2n-18．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。

(A) 2，3，5，8，6 (B) 3，2，5，8，6(C) 3，2，5，6，8 (D) 2，3，6，5，8二、填空题（每题2分，共16分）1.为了能有效地应用HASH查找技术，必须解决的两个问题是（）和（）。

2.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

模拟试题二模拟试题二一、选择题（28分）1.设一数列的顺序为l，2，3,4，5,通过栈结构不可能排成的顺序数列为( )。

A)3,2，5，4，l B)1，5,4，2，3C）2，4，3,5,l D）4，5，3，2,l2。

二叉树的第3层最少有（)个结点。

A)0 B）1 C)2 D）33。

—个n个顶点的连通无向图，其边的个数至少为( )。

A) n-l B)n C）n+l D）nlogn4。

下列排序方法中，( ）的比较次数与记录的初始排列状态无关。

A）直接插入排序 B）起泡排序C）快速排序 D）直接选择排序5.-棵哈夫曼树总共有II个结点，则叶子结点有( ）个。

A）5 B）6 C）7 D)96.已知某算法的执行时间为（n+n2)+log2(n+2)，n为问题规模,则该算法的时间复杂度是( ）。

A)O（n）B）O（n2) C）O（log2n）D）O(nlog2n)7。

如果一棵树有10个叶子结点，则该树总共至少有( )个结点。

A）lO B）11 C）19 D) 218。

—个100×100的三角矩阵a采用行优先压缩存储后，如果首元素a[0]［0]是第一个元素，那么a[4] [2］是第( )个元素。

A）13 B) 401 C) 402 D）4039.有一棵二叉树如题图1,该树是（）。

A）二叉平衡树B)二叉排序树C)堆的形状D)以上都不是10。

对于含有n个顶点e条边的无向连通图，利用Prim算法生成最小代价生成树，其时间复杂度为（)，利用Kruska算法的时间复杂度为（).A）O（log2n) B）0(n2) C)O（ne) D）O（elog2ne)11.具有n个顶点的完全有向图的边数为( ）.A）n（n—l)/2 B）n（n-l） C) n2 D）n2—112。

设有100个元素，用折半查找时,最大比较次数为（)，最小比较次数为（）。

A）25 B)7 C) 10 D)l13。

在内部排序中，排序时不稳定的有（).A）插入排序B）冒泡排序C）快速排序D）归并排序14.串是一种特殊的线性表，其特殊性体现在（)。

数据结构试卷试题及答案一、选择题（每题4分，共40分）1. 下列关于线性表的说法错误的是：A. 线性表可以是空表B. 线性表中的元素必须具有相同的数据类型C. 线性表中元素的顺序可以改变D. 线性表中的元素必须是整数答案：D2. 在单链表中，要删除第i个元素，需要：A. 找到第i个元素，然后删除B. 找到第i-1个元素，然后删除第i个元素C. 找到第i+1个元素，然后删除第i个元素D. 找到第i个元素，然后修改指针答案：B3. 下列关于栈的说法正确的是：A. 栈是一种先进先出的数据结构B. 栈是一种后进先出的数据结构C. 栈中元素只能在一端插入和删除D. 栈中元素只能在两端插入和删除答案：B4. 下列关于队列的说法错误的是：A. 队列是一种先进先出的数据结构B. 队列是一种后进先出的数据结构C. 队列中元素只能在队尾插入D. 队列中元素只能在队头删除答案：B5. 二分查找算法的时间复杂度为：A. O(1)B. O(n)C. O(logn)D. O(nlogn)答案：C6. 在二叉树中，度为0的节点数n0与度为2的节点数n2的关系是：A. n0 = n2 + 1B. n0 = n2 - 1C. n0 = n2D. n0 = n2 + 2答案：A7. 下列关于图的说法错误的是：A. 图是一种复杂的数据结构B. 图中顶点之间的关系可以是多对多的C. 图中顶点之间的关系可以是单向的D. 图中顶点之间的关系不能是双向的答案：D8. 下列排序算法中，时间复杂度最低的是：A. 冒泡排序B. 选择排序C. 快速排序D. 堆排序答案：D9. 下列关于哈希表的说法正确的是：A. 哈希表的查找时间复杂度为O(n)B. 哈希表的插入时间复杂度为O(n)C. 哈希表的查找时间复杂度为O(1)D. 哈希表的插入时间复杂度为O(1)答案：C10. 下列关于动态规划的说法错误的是：A. 动态规划是一种解决组合问题的方法B. 动态规划可以用于求解最优化问题C. 动态规划的基本思想是递归D. 动态规划的基本思想是记忆化搜索答案：C二、填空题（每题5分，共30分）1. 在单链表中，插入操作的时间复杂度是______。

全真模拟试题（二）一、单项选择题（在每个小题的4个备选答案中，选出正确的答案，并将其号码填在题后的括号内。

每小题2分，共24分）1．一个具有n个顶点的无向完全图的边数为（）①n(n+1)/2 ②n(n-1)/2 ③n(n-1) ④n(n+1)2．在索引顺序表中查找一个元素，可用的且最快的方法是（）①用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找②用顺序查找法确定元素所在块，再用二分查找法在相应块中查找③用二分查找法确定元素所在块，再用顺序查找法在相应块中查找④用二分查找法确定元素所在块，再用二分查找法在相应块中查找3．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（）存储方式最节省运算时间。

①单链表②双链表③带头结点的双循环链表④容量足够大的顺序表4．串是（）①一些符号构成的序列②有限个字母构成的序列③一个以上的字符构成的序列④有限个字符构成的序列5．堆排序在最坏情况下，其时间复杂性为（）①O(nlog2n) ②O(n2)③O(log2n2) ④O(log2n)6．快速排序的记录移动次数（）比较次数，其总执行时间为O(nlog2n)。

①大于②大于等于③小于等于④小于7．一棵二叉树有n个结点，要按某顺序对该二叉树中的结点编号，（号码为1-n），编号须具有如下性质：二叉树中任一结点V，其编号等于其左子树中结点的最大编号加1。

而其右子树中结点的最小编号等于V的编号加1。

试问应按（）遍历顺序编号。

①前根②中根③后根④层次8.3个结点可构成（）个不同形态的二叉树。

① 2 ②3 ③4 ④59．对有n个记录的有序表采用二分查找，其平均查找长度的量级为（）①O(log2n) ②O(nlog2n) ③O(n) ④O(n2)10．对有n个记录的表按记录键值有序的顺序建立二叉树，在这种情况下，其平均查找长度的量级为（）①O(n) ②O(nlog2n) ③O(1) ④(log2n)11．栈操作的原则是（）①先进先出②后进先出③栈顶插入④栈顶删除12．设矩阵A是一对称矩阵(aij =aji,1<=i,j<=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（）①1031 ②1093 ③1096 ④1032二、判断题（判断下列各题是否正确，正确在括号内打“√”，错的打“×”。

《数据结构》模拟题一、单项选择题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个顶点的无向图中，要连通全部顶点至少需要（）条边。

数据结构模拟试题（含答案）一、单选题（共100题，每题1分，共100分）1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。

A、5B、6C、7D、4正确答案：B2、假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。

A、15B、47C、16D、17正确答案：C3、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。

A、100B、99C、102D、101正确答案：A4、一棵含18个结点的二叉树的高度至少为( )A、5B、4C、6D、3正确答案：A5、有关栈的描述，正确的是（）A、栈是一种先进先出的特殊的线性表B、只能从栈顶执行插入、删除操作C、只能从栈顶执行插入、栈底执行删除D、栈顶和栈底均可执行插入、删除操作正确答案：B6、若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的（）A、中序遍历算法B、前序遍历算法C、后序遍历算法D、层次遍历算法正确答案：A7、若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) typedef struct node { char data[8]; struct node *next; } LinkStrNode;A、s->next=p; p->next=s->next;B、s->next=p->next; p->next=s;C、p->next=s->next; s->next=p;D、p->next=s; s->next=p->next;正确答案：B8、在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。

A、O(n)B、O(1)C、O(n2)D、O(n／2)正确答案：A9、执行一趟快速排序能够得到的序列是（）。

A、[45，34，12，41] 55 [72，63，27]B、[63，12，34，45，27] 55 [41，72]C、[12，27，45，41] 55 [34，63，72]D、[41，12，34，45，27] 55 [72，63]正确答案：D10、带权有向图G用邻接矩阵A存储，则顶点i 的入度等于A中（）。

《数据结构》（本）模拟试题二一、填空题（每小题2分，共24分）1．结构中的数据元素存在多对多的关系称为_____ ___结构。

2．要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。

则比较的次数和算法的时间复杂度分别为________和。

3．设有一个头指针为head的单向循环链表，p指向链表中的结点，若p->next= =_______，则p所指结点为尾结点。

4．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s->next=h和。

5．在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为________和r=s; (结点的指针域为next)6．设有n阶对称矩阵A，用数组S进行压缩存储，当i<j时，A的数组元素a ij相应于数组S的数组元素的下标为_______。

（数组元素的下标从1开始）7．一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为_____ _、___ _____。

8．一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为2，则该树共有_______个叶结点。

9．________遍历二叉排序树可得到一个有序序列。

10．如图1所示的二叉树，其前序遍历序列为_______ __。

图111．二叉树为二叉排序的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法是__________的。

(回答正确或不正确)12．按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。

二、单项选择题（每小题2分，共30分）1．在C语言中，顺序存储长度为3的字符串，需要占用（）个字节。

A．4 B．3 C．6 D．122．数据的物理结构（）。

A．与数据的逻辑结构无关 B．仅仅包括数据元素的表示C．只包括数据元素间关系的表示 D．包括数据元素的表示和关系的表示3．串函数StrCat（a,b）的功能是进行串（）。

第一章概论一、名词解释数据表示2.数据处理3.数据4.数据元素5.逻辑关系6.逻辑结构7.结构8.运算9.基本运算10.存储结构11.顺序存储结构12.链式存储结构13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构二、填空题1.计算机专业人员必须完成的两项基本任务是：_________和__________。

2.数据在计算机存储器中的存在形式称为_________。

3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据的__________的实现。

此外，该课程还要考虑各种结构和实现方法的__________。

4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数学模型的建立、选择和实现是数据结构的核心问题。

5.存储结构是逻辑结构的__________实现。

6.数据表示任务是逐步完成的，即数据表示形式的变化过程是__________->__________->__________。

7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。

8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、__________和__________。

9.根据需要，数据元素又被称为__________、__________、__________或__________。

10.在有些场合下，数据项又称为__________或__________，它是数据的不可分割的最小标识单位。

11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据可由若干个__________构成，数据元素可由若干个__________构成。