数据结构图练习试题

期末考试《数据结构》A 卷一、单项选择题(请将正确答案的字母填写在每 题对应的括号内，每小题1分，共20分)1、下面关于串的叙述中，哪一个是不正确的？()A .串是字符的有限序列B .空串是由空格构成的串C .模式匹配是串的一种重要运算D .串既可以采用顺序存储，也可以采用链式存储 2、设无向图的顶点个数为n ,则该图最多有()条边。

A . n-1B . n(n-1)/2C . n(n+1)/2D . 0 3、以下数据结构中，()是非线性数据结构。

A .树B .字符串C .队列D .栈4、下面关于线性表的叙述中，错误的是哪一个？()A .线性表采用顺序存储，必须占用一片连续的存储单元。

B .线性表采用顺序存储，便于进行插入和删除操作。

C .线性表采用链接存储，不必占用一片连续的存储单元。

D .线性表采用链接存储，便于插入和删除操作。

5、假设以数组A[m]存放循环队列的元素，其头尾指针分别为front 和rear ,则当前队列中的元素个数为()。

A . (rear-front+m)%mB . rear-front+1C . (front-rear+m)%mD . (rear-front)%m6、在单链表指针为p 的结点之后插入指针为s 的结点，正确的操作是()。

A . p->next=s; s->next=p->next;B . s->next=p->next; p->next=s;C . p->next=s; p->next=s->next;D . p->next=s->next; p->next=s; 7、设栈的输入序列是1, 2, 3, 4,则()不可能是其出栈序列。

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

A . a 和(b,c),d,eB . (a )和(b,c),d,eC . a 和((b,c), d,e)D . (a) 和((b,c), d,e)得分评卷人二、判断题，在正确的题后括号内打“J”，在错误的题后括号内打“X”(每小题1分，共10分)1、算法是由若干条指令组成的有穷序列，而一个程序不一定满足有穷性。

数据结构试题及答案⼀、选择题（共10题，每题1分，共10分）1．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元D．线性表采⽤链接存储，便于插⼊和删除操作2．在⼀个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插⼊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;3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。

A．XYZ B. YZX C. ZXY D. ZYX4．若⽤⼀个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除⼀个元素，再增加两个元素后，rear和front的值分别是( )。

A．1和5 B．2和4 C．4和2 D. 5和15．下列说法中正确的是（）。

A．⼆叉树就是度为2的树 B．⼆叉树中不存在度⼤于2的结点C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 6．在具有n个结点的⼆叉链表中，共有（）个空指针。

A. nB. n-1C. n+1D. 不确定7．根据⼆叉树与树的转换关系可知，深度为h的满⼆叉树对应的森林由（）棵树构成。

A．1 B．log2n C. h/2 D. h8．在⼀个⽆向图中，所有顶点的度数之和等于所有边数的（）倍。

A．1/2 B．1 C. 2 D. 49．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。

A．8,17 Ｂ．5,10,12 C．9,16 D．9,1710．关于排序，下列说法中正确的是（）。

数据结构试题及答案(10套)数据结构试题及答案(10套)根据您的需求，我为您准备了10套数据结构试题及答案。

每套试题包含以下几个部分：选择题、填空题、编程题及答案解析。

下面是试题的具体内容：第一套试题：选择题：1. 在数据结构中，什么是栈？A. 先进先出（FIFO）的数据结构B. 后进先出（LIFO）的数据结构C. 随机访问的数据结构D. 无序排列的数据结构2. 以下哪种操作与队列的特性不相符？A. 入队操作B. 出队操作C. 查找操作D. 获取队首元素填空题：1. ______ 是一种动态集合，支持插入、删除和查找等操作。

2. 在二叉搜索树中，中序遍历的结果是________。

编程题：实现一个栈的数据结构，并包含以下操作：- push(x)：将元素 x 压入栈中- pop()：删除栈顶的元素并返回该元素- top()：获取栈顶元素的值- empty()：检查栈是否为空答案解析：选择题：B、C填空题：1. 集合 2. 升序序列编程题：略第二套试题：选择题：1. 以下哪个数据结构是一种广度优先搜索的应用？A. 栈B. 队列C. 堆D. 链表2. 在链表中，如果要删除一个节点，只给出该节点的指针，那么需要通过什么方式完成删除操作？A. 直接删除该节点B. 指向该节点的前一个节点的指针C. 指向该节点的后一个节点的指针D. 无法完成删除操作填空题：1. 树是一种________的数据结构。

2. 二叉树每个节点最多有______个子节点。

编程题：实现一个队列的数据结构，并包含以下操作：- enqueue(x)：将元素 x 入队- dequeue()：删除队首的元素并返回该元素- peek()：获取队首元素的值- is_empty()：检查队列是否为空答案解析：选择题：B、B填空题：1. 分层组织 2. 2编程题：略（以下部分省略）通过以上的题目，您可以对数据结构的知识点进行综合练习和复习。

每套试题包含了不同难度和类型的题目，能够帮助您全面了解和掌握数据结构的概念和操作。

数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。

A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。

答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。

答案：队尾、队头11. 二叉树中的节点包括______和______。

答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。

答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。

数据结构试题及答案一、单项选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是（）。

A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系答案：A2. 栈（Stack）是一种特殊的线性表，其特点是（）。

A. 只能在一端进行插入和删除操作B. 只能在一端进行插入操作，另一端进行删除操作C. 两端都可以进行插入和删除操作D. 只能在一端进行删除操作，另一端进行插入操作答案：B3. 在二叉树中，度为2的节点数为n，叶子节点数为m，则该二叉树的总节点数为（）。

A. n + mB. n + m - 1C. 2n + m - 1D. 2m - n + 1答案：B4. 哈希表解决冲突的方法不包括（）。

A. 开放定址法B. 链地址法C. 再哈希法D. 排序法答案：D5. 以下哪个算法不是排序算法（）。

A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序答案：C6. 在图的遍历中，深度优先搜索（DFS）使用的是（）。

A. 栈B. 队列C. 链表D. 数组答案：A7. 以下哪个数据结构不是树形结构（）。

A. 二叉树B. B树C. 哈夫曼树D. 链表答案：D8. 在数据库中，索引的作用是（）。

A. 存储数据B. 快速检索数据C. 排序数据D. 压缩数据答案：B9. 以下哪个算法适用于解决图的最短路径问题（）。

A. 迪杰斯特拉算法B. 快速排序算法C. 克鲁斯卡尔算法D. 普里姆算法答案：A10. 以下哪个选项是图的邻接矩阵表示法的特点（）。

A. 只能表示无向图B. 只能表示有向图C. 可以表示无向图和有向图D. 不能表示带权图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，一个算法的时间复杂度为O(n^2)，表示该算法的时间复杂度是随着输入数据规模的增加而______增加。

答案：二次方2. 线性表的两种存储结构是顺序存储结构和______存储结构。

数据结构试题（含答案）数据结构试题（含答案）1．数据逻辑结构包括线性结构、树形结构和图状结构三种类型，树形结构和图状结构合称⾮线性结构2．数据的逻辑结构分为集合、线性结构、树形结构和图状结构4种。

3．在线性结构中，第⼀个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后⼀个结点没有后续结点，其余每个结点有且只有1个后续结点。

4．线性结构中元素之间存在⼀对⼀关系，树形结构中元素之间存在⼀对多关系，图形结构中元素之间存在多对多关系。

5．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶⼦结点没．6．数据结构的基本存储⽅法是顺序、链式、索引和散列存储。

有后续结点，其余每个结点的后续结点可以任意多个。

7．衡量⼀个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。

8．评估⼀个算法的优劣，通常从时间复杂度和空间复杂度两个⽅⾯考察。

9．算法的5个重要特性是有穷性、确定性、可⾏性、输⼊和输出。

10．在单链表中，要删除某⼀指定的结点，必须找到该结点的前驱结点。

11．在单链表中，要删除某⼀指定的结点，必须找到该结点的前驱结点。

12．在双链表中，每个结点有两个指针域，⼀个指向前驱结点，另⼀个指向后继结点。

13．在顺序表中插⼊或删除⼀个数据元素，需要平均移动n个数据元素，移动数据元素的个数与位置有关14．当线性表的元素总数基本稳定，且很少进⾏插⼊和删除操作，但要求以最快的速度存取线性表的元素是，应采⽤顺序存储结构15．根据线性表的链式存储结构中每⼀个结点包含的指针个数，将线性链表分成单链表和双链表。

16．顺序存储结构是通过下标表⽰元素之间的关系的；链式存储结构是通过指针表⽰元素之间的关系的17．带头结点的循环链表L中只有⼀个元素结点的条件是L->next->next=L18．栈是限定仅在表尾进⾏插⼊或删除操作的线性表，其运算遵循后进先出的原则。

19．空串是零个字符的串，其长度等于零。

数据结构练习题第一部分绪论一、单选题1. 一个数组元素a[i]与________的表示等价。

A、 *(a+i)B、 a+iC、 *a+iD、 &a+i2. 对于两个函数，若函数名相同，但只是____________不同则不是重载函数。

A、参数类型B、参数个数C、函数类型3. 若需要利用形参直接访问实参，则应把形参变量说明为________参数A、指针B、引用C、值4. 下面程序段的时间复杂度为____________。

for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A、 O(m2)B、 O(n2)C、 O(m*n)D、 O(m+n)5. 执行下面程序段时，执行S语句的次数为____________。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A、 n2B、 n2/2C、 n(n+1)D、 n(n+1)/26. 下面算法的时间复杂度为____________。

int f( unsigned int n ) {if ( n==0 || n==1 ) return 1; else return n*f(n-1);}A、 O(1)B、 O(n)C、 O(n2)D、 O(n!)二、填空题1. 数据的逻辑结构被分为__________、_________、__________和__________四种。

2. 数据的存储结构被分为__________、_________、__________和__________四种。

3. 在线性结构、树形结构和图形结构中，前驱和后继结点之间分别存在着________、________和________的联系。

4. 一种抽象数据类型包括__________和__________两个部分。

5. 当一个形参类型的长度较大时，应最好说明为_________，以节省参数值的传输时间和存储参数的空间。

数据结构测试卷一、判断题（每小题2.5 分，共 100分）（）1、如果采用邻接表表示图,则需要n个单链表,n是顶点数。

【答案】正确（）2、如果t中存在等于p的子串,就指出该子串在t中的位置,称为匹配成功;否则称为匹配失败。

【答案】正确（）3、归并排序的时间复杂度为O(nlogn)【答案】正确（）4、(3分)选择好的哈希函数就可以避免冲突的发生。

(×)【答案】错误（）5、广义表中原子个数即为广义表的长度。

【答案】错误（）6、栈是线性表的特例,是指元素先进后出【答案】错误（）7、为了很方便的插入和删除数据，可以使用链表存放数据。

【答案】正确（）8、子串的定位运算称为串的模式匹配。

【答案】正确（）9、线性表的逻辑顺序和存储顺序总是一致的。

【答案】错误（）10、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型【答案】错误【解析】错，混淆了逻辑结构与物理结构，链表也是线性表。

（）11、在线性表的顺序储存结构中，实际上相邻的两个元素在物理位置上不一定紧邻。

【答案】错误（）12、算法分析的前提是算法的时空效率高。

【答案】错误（）13、数据元素是3有独立含义的、不可分割的最小单位。

【答案】错误（）14、算法的五个特性为：有穷性、输入、输出、可行性和确定性。

【答案】正确【解析】请编写题目解析（选填）（）15、存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关。

【答案】错误（）16、有n个顶点的完全无向图有n*n条边。

【答案】错误（）17、任意两个顶点都是连通的无向图,称之为连通图。

【答案】正确（）18、哈夫曼树中,非叶子结点的权值等于以该结点为根的子树的所有结点权值之和。

【答案】错误（）19、在邻接矩阵中,有向图的顶点的入度等于第i行元素之和。

【答案】错误（）20、高度为k的二叉树中最多有2^k - 1个结点(k≥0)【答案】正确（）21、带权无向图的最小生成树必是唯一的。

一、填空题1. 一完全二叉树共有500个结点，则在该二叉树中有 个度为2的结点。

2. 设某二叉树的前序遍历序列为:ABCDEFGHI ，中序遍历序列为:BCAEDGHFI ，则该二叉树的后序遍历序列是 。

3. 对于一个稀疏图，在求该图对应的最小生成树时，Prim 算法和kruskal 算法哪一个算法效率更高 。

4. 对于一个n 个结点的满二叉树，假设该树有m 个树叶，深度为h ，则 h= 。

5. 设高度为h 的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为 ，至多为 。

6. 一棵有n 个结点的满二叉树有_ _ 个叶子，该满二叉树的深度为_ __。

7. 设F 是由T1,T2,T3三棵树组成的森林,与F 对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B 的左子树中有__ _个结点。

8. 一颗含有101个结点的完全二叉树存储在数组A[1..101]中，若A[k]为叶子结点，则k 的最小值是 。

9. 一颗深度为h 的完全二叉树上的结点总数最小值为 ，最大值为 。

二、选择题1. 设树T 的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1，则T 中的叶子数为（ ）。

A ．5B ．6C ．7D ．81. 在有向图G 的拓扑序列中，若顶点Vi 在顶点Vj 之前，则下列情形不可能出现的是（ ）。

A ．G 中有弧<Vi ，Vj>B ．G 中有一条从Vi 到Vj 的路径C ．G 中没有弧<Vi,Vj>D ．G 中有一条从Vj 到Vi 的路径 1. 若完全二叉树的结点总数为偶数，则度为1的结点有( )个。

A. 0B. 1C. 2D. 不确定1. 已知一棵二叉树的前序遍历结果为ABCDEF, 中序遍历结果为CBAEDF, 则后序遍历的结果为（ ）。

A ．CBEFDAB ． FEDCBAC ． CBEDFAD ．不定 1. 下述编码中哪一个不是前缀码（ ）。

一、单选题（每题 2 分，共20分）1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。

A. p->next=HL->next; HL->next=p;B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35.AOV网是一种（）。

A．有向图B．无向图C．无向无环图D．有向无环图6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。

A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。

A．值B．函数C．指针D．引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。

A．行号B．列号C．元素值D．非零元素个数9.快速排序在最坏情况下的时间复杂度为（）。

A．O(log2n) B．O(nlog2n)C．0(n) D．0(n2)10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。

A. O(n)B. O(1)C. O(log2n)D. O(n2)二、运算题（每题 6 分，共24分）1.数据结构是指数据及其相互之间的______________。

当结点之间存在M对N （M：N）的联系时，称这种结构为_____________________。

××科技大学成都学院二零零八至二零零九学年第一学期一．填空题（每空2分，共40分）；1.数据结构算法中，通常用时间复杂度和__空间复杂度___两种方法衡量其效率。

2.下面程序段的时间复杂度为___O(n2)______。

(n>1)for(i = 1; i <= n; i++)for(j = 1; j <= i; j++)x = x + 1;3.静态链表中指针表示的是______下一结点的地址______。

4.线型表、栈和队列都是____线型_______结构，可以在线型表的____任意___位置插入和删除元素；对于栈只能在____栈顶_____插入和删除元素；对于队列只能在____队尾___插入元素和_____队头_____删除元素。

5.在具有n个单元的循环队列中，队满时共有_____n-1____个元素。

6.在一个长度为n 的顺序表中第i 个元素（1<=i<=n）之前插入一个元素时，需向后移动__n-i+1__个元素。

7.在n个结点的单链表中要删除已知结点*p，需找到它的_____前驱________。

8.带有一个头结点的单链表head为空的条件是_________head->next==NULL__________。

9.在栈顶指针为hs的链栈中，判断栈空的条件是_________hs= =NULL__________。

10.在hq的链队列中，判定只有一个结点的条件是__hq.front->next==hq.rear________。

11.非空的循环单链表head的尾结点（由p指向），满足条件____p->next==head。

12.两个串相等的充分必要条件是______串长相等且对应字符相等_______。

13.空串是_______长度为0的串______，其长度等于___0________。

14.空格串是______由空格字符组成的串______，其长度等于_____空格的个数_________ 。

数据结构习题(包含全部答案解析)数据结构习题（包含全部答案解析）1. 塔的问题题目描述：有三个塔，分别是A、B和C，A塔上有n个盘子，按照从小到大的顺序叠放。

现在要将这些盘子从A塔移动到C塔，并且每次只能移动一个盘子，并且在移动过程中保持大盘子在下，小盘子在上的顺序。

求移动的步骤。

解析：这道题可以使用递归来解决。

将问题分解为两个子问题：将n-1个盘子从A塔移动到B塔，然后将最后一个盘子从A塔移动到C 塔，最后再将n-1个盘子从B塔移动到C塔。

步骤如下：1）如果n等于1，直接将盘子从A塔移动到C塔；2）否则，执行以下步骤：a) 将n-1个盘子从A塔移动到B塔，使用C塔作为中转塔；b) 将最后一个盘子从A塔移动到C塔；c) 将n-1个盘子从B塔移动到C塔，使用A塔作为中转塔。

2. 链表问题题目描述：给定一个链表，判断链表是否存在环。

解析：这道题可以使用快慢指针的思想来解决。

定义两个指针fast和slow，初始时都指向链表的头节点。

fast指针每次向后移动两个节点，slow指针每次向后移动一个节点。

如果链表中存在环，则fast指针一定会在某个时刻追上slow指针。

步骤如下：1）定义两个指针fast和slow，初始时都指向链表的头节点；2）使用一个while循环，判断条件是fast指针不为空且其下一个节点也不为空；3）在循环中，fast指针每次向后移动两个节点，slow指针每次向后移动一个节点；4）如果fast指针和slow指针相遇，则链表存在环，返回true；5）如果fast指针和slow指针永远不相遇，则链表不存在环，返回false。

3. 栈的应用题目描述：给定一个只包含'('和')'的字符串，判断该字符串是否是有效的括号序列。

解析：这道题可以使用栈来解决。

遍历字符串的每一个字符，如果是左括号，将其压入栈中；如果是右括号，判断栈顶的字符是否与该右括号匹配，若匹配则出栈，若不匹配则该字符串不是有效的括号序列。

数据结构考试试题及答案一、选择题（每题2分，共60分）1. 数据结构是指（）。

A. 用来存储和组织数据的方式和方法B. 构建数据的逻辑关系C. 存储和处理数据的工具和技术D. 对数据进行操作和管理的过程2. 下列哪种数据结构是线性结构（）。

A. 树B. 图C. 队列D. 堆3. 下列哪种数据结构是非线性结构（）。

A. 栈B. 队列C. 数组D. 树4. 栈是一种（）。

A. 先进先出的数据结构B. 先进后出的数据结构C. 后进先出的数据结构D. 后进后出的数据结构5. 在二叉树中，每个节点最多有几个孩子节点（）。

A. 0B. 1C. 2D. 36. 下列哪种排序算法的时间复杂度最好（）。

A. 冒泡排序B. 插入排序C. 快速排序D. 归并排序7. 哈希表的查找时间复杂度是（）。

A. O(1)B. O(logn)C. O(n)D. O(nlogn)8. 链表的插入和删除操作时间复杂度是（）。

A. O(1)B. O(logn)C. O(n)D. O(nlogn)9. 广度优先搜索算法一般使用（）数据结构来实现。

A. 栈B. 队列C. 堆D. 树10. 什么是递归（）。

A. 函数调用自身的过程B. 通过循环完成的过程C. 一种数据结构D. 没有调用其他函数的过程二、填空题（每题2分，共20分）1. 数据结构中，线性表是由一系列 _______________ 元素构成的数据结构。

2. 在树结构中，每个节点可以有 _______________ 个子节点。

3. 在图结构中，节点之间的关系可以用 _______________ 来表示。

4. _______________ 是一种递归定义的数据结构，它由若干个节点组成，每个节点都有零个或多个子节点。

5. 在堆排序中，堆是一种 _______________ 数据结构。

6. _______________ 是一种常用的搜索算法，常用于解决最短路径问题。

7. 在散列表中，使用 _______________ 来解决冲突问题。

第七章 图一、选择题1．图中有关路径的定义是（ ）。

【北方交通大学 2001 一、24 （2分）】A ．由顶点和相邻顶点序偶构成的边所形成的序列B ．由不同顶点所形成的序列C ．由不同边所形成的序列D ．上述定义都不是2．设无向图的顶点个数为n ，则该图最多有（ ）条边。

A ．n-1B ．n(n-1)/2C ． n(n+1)/2D ．0E ．n 2【清华大学 1998 一、5 （2分）】【西安电子科技大 1998 一、6 （2分）】【北京航空航天大学 1999 一、7 （2分）】3．一个n 个顶点的连通无向图，其边的个数至少为（ ）。

【浙江大学 1999 四、4 (4分)】A ．n-1B ．nC ．n+1D ．nlogn ；4．要连通具有n 个顶点的有向图，至少需要（ ）条边。

【北京航空航天大学 2000 一、6(2分）】A ．n-lB ．nC ．n+lD ．2n5．n 个结点的完全有向图含有边的数目（ ）。

【中山大学 1998 二、9 （2分）】A ．n*n Ｂ．n （n ＋１） C ．n ／2 D ．n*（n －l ）6．一个有n 个结点的图，最少有（ ）个连通分量，最多有（ ）个连通分量。

A ．0B ．1C ．n-1D ．n【北京邮电大学 2000 二、5 （20/8分）】7．在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。

【哈尔滨工业大学 2001 二、3 （2分）】A ．1/2B ．2C ．1D ．48．用有向无环图描述表达式(A+B)*（（A+B ）/A ），至少需要顶点的数目为( )。

【中山大学1999一、14】A ．5B ．6C ．8D ．99．用DFS 遍历一个无环有向图，并在DFS 算法退栈返回时打印相应的顶点，则输出的顶点序列是( )。

A ．逆拓扑有序B ．拓扑有序C ．无序的 【中科院软件所1998】10．下面结构中最适于表示稀疏无向图的是（ ），适于表示稀疏有向图的是（ ）。

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构练习题与答案一、单选题（共100题，每题1分，共100分）1、顺序查找法适用于存储结构为( )的线性表。

A、压缩存储B、顺序存储或链式存储C、散列存储D、索引存储正确答案：B2、在索引查找中，若用于保存数据元素的主表的长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。

A、79B、24C、13D、12正确答案：C3、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。

A、2mB、2m-1C、4mD、2m+1正确答案：A4、设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。

A、2nB、n-1C、2n-1D、n正确答案：B5、在完全二叉树中，若一个结点是叶结点，则它没有( )A、左孩子结点B、右孩子结点C、左孩子结点和右孩子结点D、左孩子结点，右孩子结点和兄弟结点正确答案：C6、设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

A、线性结构B、树型结构C、图型结构D、集合正确答案：C7、下列排序算法中，第一趟排序结束后其最大或最小元素一定在其最终位置上的算法是( )。

A、冒泡排序B、直接插入排序C、快速排序D、归并排序正确答案：A8、假设以数组A[m]存放循环队列的元素。

已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为( )A、(rear-length+m+1)％mB、(rear-length+m)％mC、(rear-length+m-1)％mD、(rear-length)％m正确答案：B9、在下面的程序段中，对x的赋值语句的频度为（）。

for ( i=1; n>=i ; i++) for ( j=1; n>=j ; j++) x=x+1;A、O(log2n)B、O(2^n)C、O(n^2)D、O(n)正确答案：C10、具有4个顶点的无向完全图有( )条边。

一、单选题1、设有5个结点的无向图，该图至少应有_________条边才能确保是一个连通图。

A.7B.8C.6D.5正确答案：A2、设图G=(V,VR)，其中: V={A,B,C,D,G}，VR={(A,C),(A,D),( B,C),(B,D) ,(G,C),(B,G)}，则对应的图形为_________。

A.B.C.D.正确答案：C3、设某有向图中有n个顶点，则该有向图对应的邻接表中有_________个表头结点。

A.n-1B.n+2C.nD.n+1正确答案：C4、在一个无向图中所有顶点的度数之和等于所有边数的_________倍。

A.1B.2C.3D.1/2正确答案：B5、一个无向连通图的生成树是该连通图的_____。

A.极小连通子图B.强连通子图C.连通子图D.极大连通子图正确答案：A6、设某无向图中有n个顶点，则该无向图邻接矩阵的大小是_________。

A.n(n+1)/2B.（n-1）2C. n2D. （n+1）2正确答案：C7、设有n个顶点e条边的无向图，采用邻接矩阵作为物理结构，则删除与某顶点Vi 关联的所有边算法的时间复杂度为_________。

A.O(n2)B.O(n+e）C.O(n*e）正确答案：D8、设有n个顶点e条弧的有向图，采用邻接表作为物理结构，则求某顶点Vi度的算法的时间复杂度为_________。

A.O(n）B.O(n*e）C.O(n+e）D.O(n2)正确答案：C9、设无向图G=(V,E)和G'=(V',E')，如果G'是G的生成树，则下列说法中错误的是_____。

A.G'是G的连通分量B.G'是G的一个无环子图C.G'是G的极小连通子图且V=V'D.G'是G的子图正确答案：A10、设G是一个非连通的无向图，共有10条边，则该图至少有_____个顶点。

A.7B.6C.5D.8正确答案：B11、 n个顶点的有向图为强连通图时，至少含有________。

数据构造试卷〔一〕一、单项选择题〔每题 2 分，共20分〕1.栈和队列的共同特点是( a )。

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

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

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.假设有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进展二分查找，那么查找A［3］的比拟序列的下标依次为( c d)A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进展快速排序，所需要的辅助存储空间大致为 cA. 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的元素有〔 c d〕个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( a )条边才能确保是一个连通图。

二、填空题〔每空1分，共26分〕1.通常从四个方面评价算法的质量：____时间正确性_____、____占用内存_易读性____、____复杂度__强壮性___和_____准确度_ 高效率___。

数据结构试题及答案一、选择题1. 以下哪种数据结构是线性结构？A. 树B. 图C. 链表D. 集合答案：C2. 在二叉搜索树中，若删除一个节点，则需要进行的操作是：A. 直接删除B. 删除后不进行任何操作C. 删除后找到其前驱或后继节点替换D. 删除后将树旋转答案：C3. 快速排序算法的时间复杂度在最坏情况下是：A. O(log n)B. O(n)C. O(n log n)D. O(n^2)答案：D4. 下面关于图的遍历描述，正确的是：A. 只能使用深度优先搜索B. 只能使用广度优先搜索C. 可以使用深度优先搜索和广度优先搜索D. 以上都不是答案：C5. 在哈夫曼树中，权值最大的叶子节点与权值最小的叶子节点的深度差是：A. 0B. 1C. 树的高度D. 树的深度减1答案：B二、填空题1. 请写出一个数组的插入操作的时间复杂度：_________。

答案：O(n)2. 请写出一个二叉树的高度计算的递归算法的时间复杂度：_________。

答案：O(n)3. 请写出一个哈希表的查找操作的平均时间复杂度（假设哈希函数是最优的）：_________。

答案：O(1)4. 请写出一个图的邻接矩阵表示法中，查找顶点v的所有邻接顶点的时间复杂度：_________。

答案：O(n)5. 请写出一个二分查找算法的递归实现的时间复杂度：_________。

答案：O(log n)三、判断题1. 链表结构比数组结构更加节省内存。

（）答案：×2. 堆排序是一种稳定的排序算法。

（）答案：×3. 红黑树是一种自平衡二叉搜索树。

（）答案：√4. 拓扑排序适用于有向无环图。

（）答案：√5. 散列表通过开放寻址法解决冲突时，可能需要移动其他元素。

（）答案：√四、简答题1. 请简述栈和队列的区别。

答案：栈和队列都是线性数据结构，但它们的主要区别在于元素的添加和移除顺序。

栈遵循后进先出（LIFO）的原则，即最后添加的元素会最先被移除。

第7章图一、单项选择题1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。

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

A．l/2 B．1D．4C．23．一个具有n个顶点的无向图最多包含______条边。

A．n B．n＋1D ．n(n-1)/2C．n-14．一个具有n个顶点的无向完全图包含______条边。

A．n(n-l) B．n(n+l)D．n(n-l)/2C．n(n-l)/25．一个具有n个顶点的有向完全图包含______条边。

A．n(n-1) B．n(n+l)D．C．n(n-l)/2 n(n+l)/26．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。

nnB．×．An(n-l)×(n-l)．D n-1 C．．无向图的邻接矩阵是一个______。

7 ．零矩阵B ．对称矩阵A．C．上三角矩阵D．对角矩阵8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。

A．n B．eD．2eC．2n9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n B．eDC．2n ．2e10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。

A．入边B．出边D．不是入边也不是出边C．入边和出边11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。

A．入边B．出边D ．不是人边也不是出边C．入边和出边12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。

A．完全图B．连通图D．一棵树．有回路C13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。

A．先序遍历B．中序遍历．按层遍历D ．后序遍历C．14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。