图的深度优先搜索算法类似于二叉树的哪种遍历

国家开放大学电大《数据结构》网络课形考任务3作业及答案档任务3一、单项选择题（每小题2分，共38分）题目1 假定一棵二叉树中，双分支结点数为15,单分支结点数为30,则叶子结点数为（）。

选择一项： A、47 B、16 C、17 D、15 题目2 二叉树第k层上最多有（）个结点。

选择一项： A、2k-l B、2k-l C、2k-l D、2k 题目3 将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1,则编号为69的结点的双亲结点的编号为（）。

选择一项： A、36 B、35 C、34 D、33 题目4 如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

选择一项： A、二叉树 B、哈夫曼树 C、完全二叉树 D、平衡二叉树在一棵度具有5层的满二又树中结点总数为（ )o 选择一项: A、16 B、3231 D、33 题目6 一棵完全二叉树共有6层，且第6层上有6个结点，该树共有（）个结点。

选择一项: A、31 B、37 C、38 D、72 题目7 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子结点中的最长带权路径长度为（在一棵树中，（）没有前驱结点。

)、选择一项: A、18 B、16 C、30 D、12 题目8 选择一项: A、树根结点 B、叶结点 C、空结点 D、分支结点题目9 设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为2,该树结点中共有20个指针域为空，则该树有（）个叶结点。

选择一项: B、10 C、21 D、22 题目10 在一个图G中，所有顶点的度数之和等于所有边数之和的（）倍。

选择一项： A、2 B、1 C、4 D、1/2 题目11 邻接表是图的一种（）＜、选择一项： A、链式存储结构 B、顺序存储结构C、散列存储结构 D、索引存储结构题目12 图的深度优先遍历算法类似于二叉树的（）遍历。

《数据结构与算法》二您的姓名： [填空题] *_________________________________一、单选题1. 深度优先搜索遍历类似于二叉树的（）. [单选题] *A. 先序遍历(正确答案)B. 中序遍历C. 后序遍历D. 按层次遍历2. 无向图顶点v的度是关联于该顶点（）的数目. [单选题] *A. 顶点B. 边(正确答案)C. 序号D. 下标3. 有n个顶点的无向图的邻接矩阵是用（）数组存储。

. [单选题] *A. 一维B. n行n列(正确答案)C. 任意行n列D. n行任意列4.对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（）. [单选题] *A. n-1B. n+1C. n(正确答案)D. n+e5. 对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为（）. [单选题] *A. k1B. k2(正确答案)C. k1-k2D. k1+k26. 广度优先遍历类似于二叉树的（）. [单选题] *A. 先序遍历B. 中序遍历C. 后序遍历D. 按层次遍历(正确答案)7. 任何一个无向连通图的最小生成树（）. [单选题] *A. 只有一棵B. 有一棵或多棵(正确答案)C. 一定有多棵D. 可能不存在二、多选题8. 在某图中，下列选项中说法不正确的是（）. *A. 不存在顶点到自身的边，或者重复的边，则该图是简单图B. 不存在顶点到自身的边，或者重复的边，则该图是复杂图(正确答案)C. 不存在顶点到自身的边，或者重复的边，则该图是无向图(正确答案)D. 不存在顶点到自身的边，或者重复的边，则该图是有向图(正确答案)9. 有关图的说法不正确的是（）. *A. 有向图的边是有向的，又称为弧B. 有向图的边是有向的，又称为箭头(正确答案)C. 有向图的边是有向的，又称为边角(正确答案)D. 无正确答案(正确答案)10. 关于有向图的说法不正确的是（）。

形考作业三及答案本部分作业覆盖教材第6-7章的内容）一、单项选择题1.假定一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）。

A．15 B．16 C．17 D．472．二叉树第k层上最多有（）个结点。

A．2k B．2k-1C．2k-1 D．2k-13．二叉树的深度为k，则二叉树最多有（）个结点。

A．2k B．2k-1C．2k-1 D．2k-14. 设某一二叉树先序遍历为abdec，中序遍历为dbeac，则该二叉树后序遍历的顺序是（）。

A．abdec B．debac C．debca D．abedc5．将含有150个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点的编号为1，则编号为69的结点的双亲结点的编号为（）。

A．33 B．34 C．35 D．366．如果将给定的一组数据作为叶子数值，所构造出的二叉树的带权路径长度最小，则该树称为（）。

A．哈夫曼树 B．平衡二叉树C．二叉树 D．完全二叉树7．下列有关二叉树的说法正确的是（）。

A．二叉树中度为0的结点的个数等于度为2的结点的个数加1B．二叉树中结点个数必大于0C．完全二叉树中，任何一个结点的度，或者为0或者为2D．二叉树的度是28．在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（）。

A．4 B．5 C．6 D．79．在一棵度具有5层的满二叉树中结点总数为（）。

A．31 B．32 C．33 D．1610. 利用n个值作为叶结点的权生成的哈夫曼树中共包含有( )个结点。

A. nB. n+1C. 2*nD. 2*n-111. 利用3、6、8、12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为( )。

A. 18B. 16C. 12D. 3012．在一棵树中，（）没有前驱结点。

A．分支结点 B．叶结点 C．树根结点 D．空结点13．在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为（）。

一、填空题：（1分*10=10分）1)线性结构中元素之间存在1对1关系，树形结构中元素之间存在1对多，图形结构中元素之间存在多对多关系。

2)顺序表中，逻辑上相邻的元素物理位置一定相邻；单链表中逻辑上相邻的元素位置不一定相邻。

3)线性表、栈和队列都是线性结构。

对于栈只能在栈顶位置插入和删除元素；对于队列只能在队尾位置插入和在对头位置删除元素。

4)由三个结点构成的二叉树，共有_____5____种不同的结构。

5)具有10个顶点的无向图，边的总数最多为10 。

6)评价算法的优劣通常主要考虑算法的时间复杂度和空间复杂度这两方面。

7)链式存储的特点是利用指针来表示数据元素之间的逻辑关系。

8)线性表常见的存储结构有顺序存储结构和链式存储结构。

9)栈的特点是后进先出，队列的特点是先进先出。

10)对于二叉树来说，第i层上最多有___2i-1__个节点。

11)哈夫曼树是指___代权路径长度最短______的二叉树。

12)构造n个结点的强连通图，至少有n 条弧。

13)常见的数据结构有集合结构、线性结构、树形结构、图形结构。

14)计算机程序中加工处理的基本单位是数据元素，数据中不可再分割最小单位是数据项。

15)链式存储的特点是利用指针来表示数据元素之间的逻辑关系。

16)栈的特点是后进先出，队列的特点是先进先出。

17)一棵深度为k的满二叉树的结点总数为____2k-1_____。

18)在有n个顶点的有向图中，每个顶点的度最大可达2（n-1）。

19)线性结构中元素之间存在1对1关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。

20)计算机程序中加工处理的基本单位是数据元素，数据中不可再分割最小单位是数据项。

21)线性表常见的存储结构有顺序存储结构和链式存储结构。

22)栈的特点是后进先出，队列的特点是先进先出。

23)在一颗二叉树中，度为零的结点的个数为n0，度为2的结点的个数为n2，则有n0= n2+1 。

数据结构练习（二）答案一、填空题：1．若一棵树的括号表示为A（B（E，F），C（G（H,I,J,K）,L）,D（M（N））），则该树的度为（1）4，树的深度为（2）4 ，树中叶子结点的个数为（3）8。

2．一棵满二叉树中有m个叶子，n个结点，深度为h，请写出m、n、h之间关系的表达式（4）n=2h-1,m=n+1-2h-1 n=2m-1 。

3．一棵二叉树中如果有n个叶子结点，则这棵树上最少有（5）2n-1 个结点。

一棵深度为k的完全二叉树中最少有2k-1（6）个结点，最多有（7）2k-1个结点。

4．具有n个结点的二叉树，当它是一棵(8)完全二叉树时具有最小高度（9） log2n」+1，当它为一棵单支树时具有高度(10) n 。

5．对具有n个结点的完全二叉树按照层次从上到下，每一层从左到右的次序对所有结点进行编号，编号为i的结点的双亲结点的编号为_(11)__[i/2]__，左孩子的编号为___2i____，右孩子的编号为__2i+1______。

6．若具有n个结点的二叉树采用二叉链表存储结构，则该链表中有__2n_个指针域，其中有_n-1_个指针域用于链接孩子结点，__n+1_个指针域空闲存放着NULL 。

7．二叉树的遍历方式通常有__先序__、___中序__、__后序__和___层序___四种。

8．已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为___DCBFGEA__。

9．已知某完全二叉树采用顺序存储结构，结点的存放次序为A,B,C,D,E,F,G,H,I,J，该完全二叉树的后序序列为___HIDJEBFGCA____。

10．若具有n个结点的非空二叉树有n0个叶结点，则该二叉树有__n0-1_个度为2的结点，____n-2n0+1____个度为1的结点。

11．任何非空树中有且仅有一个结点没有前驱结点，该结点就是树的__根____。

度为k的树中第i层最多有___k i-1_______个结点(i>=1)，深度为h的k叉树最多有___k0+k1+....+k h-1____个结点。

一、单选题C01、在一个图中，所有顶点的度数之和等于图的边数的倍。

A)1/2 B)1 C)2 D)4B02、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。

A)1/2 B)1 C)2 D)4B03、有8个结点的无向图最多有条边。

A)14 B)28 C)56 D)112C04、有8个结点的无向连通图最少有条边。

A)5 B)6 C)7 D)8C05、有8个结点的有向完全图有条边。

A)14 B)28 C)56 D)112B06、用邻接表表示图进行广度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A07、用邻接表表示图进行深度优先遍历时，通常是采用来实现算法的。

A)栈 B)队列 C)树 D)图A08、一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为。

A)O(n) B)O(e) C)O(n+e) D)O(n2)C09、已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是。

A)0 2 4 3 1 5 6 B)0 1 3 6 5 4 2 C)0 1 3 4 2 5 6 D)0 3 6 1 5 4 2B10、已知图的邻接矩阵同上题，根据算法，则从顶点0出发，按广度优先遍历的结点序列是。

A)0 2 4 3 6 5 1 B)0 1 2 3 4 6 5 C)0 4 2 3 1 5 6 D)0 1 3 4 2 5 6D11、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是。

A)0 1 3 2 B)0 2 3 1 C)0 3 2 1 D)0 1 2 3A12、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是。

A)0 3 2 1 B)0 1 2 3 C)0 1 3 2 D)0 3 1 2A13、图的深度优先遍历类似于二叉树的。

A)先序遍历 B)中序遍历 C)后序遍历 D)层次遍历D14、图的广度优先遍历类似于二叉树的。

数据结构考试题库含答案数据结构考试题库含答案Document serial number【KKGB-LBS98YT-BS8CB-BSUT-BST108】数据结构习题集含答案目录选择题第一章绪论1.数据结构这门学科是针对什么问题而产生的（A ）A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据结构这门学科的研究内容下面选项最准确的是（D ）A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（C ）A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.*数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6.算法分析的目的是（C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7.算法分析的主要方法（A ）。

A、空间复杂度和时间复杂度B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性8.计算机内部处理的基本单元是（B ）A、数据B、数据元素C、数据项D、数据库9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（B ）。

A、低B、高C、相同D、不好说10.算法的时间复杂度取决于（ C ）A 、问题的规模B、待处理数据的初始状态C、问题的规模和待处理数据的初始状态D、不好说11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。

数据结构与算法练习题库（含答案）一、单选题（共80题，每题1分，共80分）1、对一棵二叉树的结点从 1 开始顺序编号。

要求每个结点的编号大于其左子树所有结点的编号、但小于右子树中所有结点的编号。

可采用▁▁▁▁▁ 实现编号。

A、中序遍历B、先序遍历C、层次遍历D、后序遍历正确答案：A2、设一段文本中包含4个对象{a,b,c,d}，其出现次数相应为{4,2,5,1}，则该段文本的哈夫曼编码比采用等长方式的编码节省了多少位数？A、5B、4C、2D、0正确答案：C3、两个有相同键值的元素具有不同的散列地址A、一定不会B、一定会C、可能会D、有万分之一的可能会正确答案：C4、将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。

散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。

问：当第一次发现有冲突时，散列表的装填因子大约是多少？A、0.73B、0.27C、0.64D、0.45正确答案：D5、对N个记录进行归并排序，归并趟数的数量级是：A、O(NlogN)B、O(logN)C、O(N)D、O(N2)正确答案：B6、下列说法不正确的是：A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、图的深度遍历不适用于有向图C、遍历的基本算法有两种：深度遍历和广度遍历D、图的深度遍历是一个递归过程正确答案：B7、二叉树的中序遍历也可以循环地完成。

给定循环中堆栈的操作序列如下（其中push为入栈，pop为出栈）： push(1), push(2), push(3), pop(), push(4), pop(), pop(), push(5), pop(), pop(), push(6), pop()A、6是根结点B、2是4的父结点C、2和6是兄弟结点D、以上全不对正确答案：C8、设最小堆（小根堆）的层序遍历结果为{1, 3, 2, 5, 4, 7, 6}。

三、简答1.对于一个队列，如果输入项序列由1,2,3,4所组成，试给出全部可能的输出序列。

答：1,2,3,4。

2. 将表达式 (a+b) *c+d - (e+g)*h 改写成后缀表达式。

答：后缀表达式为：ab+c*d+eg+h*-3.对于一个栈，给出输入序列A，B，C，试给出全部可能的输出序列。

答：解：输出序列为：ABC，CBA,ACB,BAC,BCA。

4．将算术表达式a+b*（c+d/e ）转为后缀表达式。

答： B ．abcde/+*+5.由权值为12，6，5，9 ,10的五个叶子结点构造一棵哈夫曼树，请问该树的带权路径长度是多少？ 答：权值为 95 。

6. 由二叉树的前序和后序遍历序列能否唯一确定一棵二叉树。

若不能请举出反例。

答：不能唯一确定一棵二叉树。

如下图。

7.求出下图所示有向图的邻接矩阵。

答：有向图的邻接矩阵为：8.有n 个顶点的无向连通图至少有多少条边？有n 个顶点的有向连通图至少有多少条边？ 答：有n 个顶点的无向连通图至少有n-1条边，有n 个顶点的有向连通图至少有n 条边。

9．下面列举的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。

试问，哪些排序方法是稳定的？答：起泡排序, 直接插入排序，归并排序是稳定的。

10.为什么说树是一种非线性结构？树中的每个结点除了根结点外，其余每个结点有一个直接前驱，但有多个直接后继，所以说树是一种非线性结构。

11．已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。

前序序列：A, B, C, D, E, F, G, H, I, J 中序序列：C, B, A, F, E, D, I, H, J, G 答：后序序列为：C, B, F, E, I, J, H, G, D, A12．试述顺序存储和链式存储的区别及各自的优缺点。

答：数组占用连续的内存空间，链表不要求结点的空间连续。

1）插入与删除操作：由于数组在插入与删除数据时需移动大量的数据元素，而链表只需要改变一些指针的链接，因此，链表比数组易于实现数据的插入和删除操作。

第6章树和二叉树一、基础知识题1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。

[解答]二叉树的叶结点有⑥、⑧、⑨。

分支结点有①、②、③、④、⑤、⑦。

结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。

2．使用（1）顺序表示和（2）二叉链表表示法，分别画出右图所示二叉树的存储表示。

[解答]（1）顺序表示（2）二叉链表表示3．在结点个数为n（n>1）的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？[解答]结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。

4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

[解答]具有3个结点的树具有3个结点的二叉树5．如果一棵树有n1个度为1的结点，有n2个度为2的结点，…，n m个度为m的结点，试问有多少个度为0的结点？试推导之。

[解答]总结点数n=n0+n1+n2+…+n m总分支数e=n-1= n0+n1+n2+…+n m-1=m×n m+(m-1)×n m-1+…+2×n2+n1则有 n 0=∑=+-mi i n i 21))1((6．试分别找出满足以下条件的所有二叉树：（1） 二叉树的前序序列与中序序列相同； （2） 二叉树的中序序列与后序序列相同； （3） 二叉树的前序序列与后序序列相同。

[解答]（1） 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；（2） 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； （3） 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。

7．填空题（1）对于一棵具有n 个结点的树，该树中所有结点的度数之和为 n-1 。

1判断题（√）1. 数据的逻辑结构与数据元素本身的内容和形式无关。

（）2. 线性表的逻辑顺序与物理顺序总是一致的。

（）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

（）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。

（√）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。

（√）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。

（√）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。

（）8. 连通分量是无向图中的极小连通子图。

（）9. 二叉树中任何一个结点的度都是2。

（）10. 单链表从任何一个结点出发，都能访问到所有结点。

（）11.线性表的长度是线性表占用的存储空间的大小。

（）12.队列只能采用链式存储方式。

（√）13.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。

（√）14.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。

（）15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。

（）16. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（√）17.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

（√）18.线性表中的每个结点最多只有一个前驱和一个后继。

（）19.二叉排序树查找总比顺序查找速度快。

（）20.对具有n个顶点的连通图进行深度优先遍历，所得顶点序列是唯一的。

（）21.线性表中各个数据元素的类型必须是相同的。

（）22.B+树是一种特殊的二叉树。

（）23.栈可视为一种特殊的线性表。

（√）24.快速排序总是比其它排序方法快。

（）25.使用双向链表存储数据，可以提高查找（定位运算）的速度。

（）26.最小生成树是边数最少的生成树。

二、单选题1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ b ）个元素。

《数据结构》第04章在线测试《数据结构》第04章在线测试剩余时间：43:12答题须知：1、本卷满分20分。

2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。

3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。

第一题、单项选择题（每题1分，5道题共5分）1、若串S＝"abcdef"，则其非空子串数目为＿＿＿＿＿＿＿＿。

A、6B、12C、21D、222、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。

A、字符B、字符串C、数字D、字母3、设有三个串，s1＝"How", s2＝" are", s3＝" you",则这三个串连接后得到的结果串是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

A、"Howareyou"B、"How are you"C、"How are you."D、" How are you"4、串是一种特殊的线性表，其特殊性体现在＿＿＿＿＿＿＿＿。

A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符5、空格串的长度为＿＿＿＿＿＿＿＿。

A、0B、1C、串中空格的个数D、第二题、多项选择题（每题2分，5道题共10分）1、在定长顺序存储表示中，对串长的表示方法有＿＿＿＿＿＿＿＿＿＿。

A、用域变量表示B、用下标为0的数组分量表示C、在串值后加结束标记字符D、无法明确表示2、以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。

A、定长顺序表示和堆分配表示都是串的顺序存储表示B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间C、堆分配表示的串的存储空间是在程序执行过程中动态分配的D、堆分配存储表示时的空串不占用连续的存储区3、两个串相等的充分必要条件是＿＿＿＿＿＿＿＿＿＿。

成人高等教育数据结构一、单选题（每题2.5分，共20道小题，总分值50分）1.链表适用于（）查找。

A 顺序B 二分法C 顺序，也能二分法D 随机正确答案A您的答案是未作答回答错误展开2.数据结构在计算机内存储器中的表示是指（）。

A 数据结构B 数据元素之间的关系C 数据的逻辑结构D 数据的物理存储结构正确答案D您的答案是未作答回答错误展开3.线性表的顺序存储结构是一种（）的存储结构。

A 随机存取B 顺序存取C 索引存取D 散列存取正确答案A您的答案是未作答回答错误展开4.如下陈述中正确的是（）。

A 串是一种特殊的线性表B 串的长度必须大于零C 串中元素只能是字母D 空串就是空格串正确答案A您的答案是未作答回答错误展开5.引起循环队列队头位置发生变化的操作是（）。

A 出队B 入队C 取队头元素D 取队尾元素正确答案A您的答案是未作答回答错误展开6.在一个非空二叉树的中序遍历序列中，根结点的右边（）A 只有右子树上的所有结点B 只有右子树上的部分结点C 只有左子树的上的部分结点D 只有左子树上的所有结点正确答案A您的答案是未作答回答错误展开7.在一个具有n 个顶点的无向图中，要连通所有顶点则至少需要（）条边。

A nB 2nC n-1D n=1正确答案C您的答案是未作答回答错误展开8.一棵具有５层满二叉树中节点总数为（）。

A 33B 32C 31D 16正确答案C您的答案是未作答回答错误展开9.快速排序在下列哪种情况下最易发挥其长处（）。

A 被排序的数据中含有多个相同排序码B 被排序的数据已基本有序C 被排序的数据完全无序D 被排序的数据中的最大值和最小值相差悬殊正确答案C您的答案是未作答回答错误展开10.算法分析的主要方法是（）。

A 空间复杂度和时间复杂度B 正确性和简明性C 可读性和文档性D 数据复杂性和程序复杂性正确答案A您的答案是未作答回答错误展开11.一棵含18 个结点的二叉树的高度至少为（）。

习题一一、选择题 ( 每小题 2 分，共 20 分 )1．以下程序段的时间复杂度为（）。

i=0，s=0； while (s<n) {s=s+i；i++；}(A) O(n/2) (B) O(n/3) (C) O(n) (D) O(n2)2．设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用以下（）存储方式最节省运算时间。

(A) 单向链表 (B) 单向循环链表 (C) 双向链表 (D) 双向循环链表3．设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s 指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。

(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．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。

(A) 5，3，4，6，1，2 (B) 3，2，5，6，4，1(C) 3，1，2，5，4，6 (D) 1，5，4，6，2，35．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0] [0]的地址之差为（）。

(A) 10 (B) 19 (C) 28 (D) 556．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。

7. 二叉排序树中左子树上所有结点的值均（）根结点的值。

(A) < (B) > (C) = (D) !=8. 设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。

树一、判断题：1。

二叉树是一棵无序树。

（×）2.在一棵二叉树中，假定每个结点只有左子女，没有右子女,对它分别进行中序遍历和后序遍历，则具有相同的结果。

（√）3。

度为二的有序树等价于二叉树。

（√）4.树的带权路径长度最小的二叉树中必定没有度为1的结点。

（√)5。

哈夫曼树一定是满二叉树。

（×）6.满二叉树也是完全二叉树.（√)7。

设与一棵树T所对应的二叉树为BT,则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。

(×）8.将一棵树转换成二叉树后，根结点没有左子树（×）9。

已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

（√)10用二叉树的前序遍历和中序遍历可以导出树的后序遍历.（√）11.在完全二叉树中，若某结点无左孩子,则它必是叶结点。

（√）。

12．任何一棵二叉树都有n0=n2+1的关系式.（√）13．已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树.( √）二、填空题1.假定一棵二叉树的结点个数为32，则它的最小深度为___6___，最大深度为：32.2.在一棵二叉树中，度为2的结点有5个，度为1的结点有6个，那么叶子结点有__6____ 个.3.树的双亲表示法便于实现涉及到___双亲___的操作，孩子表示法便于实现涉及到孩子的操作。

4.对于一颗具有n个结点的二叉树，对应二叉链表中指针域有__n—1__个用于指向子结点。

5.下图所示二叉树存储在一维数组中，则元素F的下标位置为___11___。

（A为1)6.高度为k的二叉树具有的结点数目，最少为___ K ___,最多为___2K—1___。

7.对任何一棵二叉树,若n0，n1,n2分别是度为0，1，2的结点的个数，则n0=__ n2+1__.8.一棵含有16个结点的完全二叉树，对他按层编号,对于编号为7的结点，他的双亲结编号点为___3___左孩子编号为____14__、右孩子编号为___15___。

数据结构（本）一、单选题1.把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。

A.逻辑结构B.物理结构C.算法的具体实现D.给相关变量分配存储单元正确答案: B2.下列说法中，不正确的是（）。

A.数据元素是数据的基本单位B.数据项是数据中不可分割的最小可标识单位C.数据可有若干个数据元素构成D.数据项可由若干个数据元素构成正确答案: D3.一个存储结点存储一个（）。

A.数据项B.数据元素C.数据结构D.数据类型正确答案: B4.数据结构中，与所使用的计算机无关的是数据的（）。

A.存储结构B.物理结构C.逻辑结构D.物理和存储结构正确答案: C5.在线性表的顺序结构中，以下说法正确的是（）。

A.逻辑上相邻的元素在物理位置上不一定相邻B.数据元素是不能随机访问的C.逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高正确答案: C6.对链表, 以下叙述中正确的是（）。

A.不能随机访问任一结点B.结点占用的存储空间是连续的C.插入删除元素的操作一定要要移动结点D.可以通过下标对链表进行直接访问正确答案: A7.下列的叙述中，不属于算法特性的是（）。

A.有穷性B.输入性C.可行性D.可读性8.算法的时间复杂度与（）有关。

A.所使用的计算机B.计算机的操作系统C.算法本身D.数据结构正确答案: C9.设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。

A.n-i+1B.n-iC.n-i-1D.i正确答案: A10.设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。

A.n-i+1B.n-iC.n-i-1D.i正确答案: B11.在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。

A.p=q->nextB.p->next=qC.p->next=q->nextD.q->next=NULL正确答案: C12.在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。

1判断题（）1. 数据的逻辑结构与数据元素本身的内容和形式无关。

（）2. 线性表的逻辑顺序与物理顺序总是一致的。

（）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

（）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。

（）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。

（）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。

（）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。

（）8. 连通分量是无向图中的极小连通子图。

（）9. 二叉树中任何一个结点的度都是2。

（）10. 单链表从任何一个结点出发，都能访问到所有结点。

（）11.线性表的长度是线性表占用的存储空间的大小。

（）12.队列只能采用链式存储方式。

（）13.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。

（）14.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。

（）15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。

（）16. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（）17.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面。

（）18.线性表中的每个结点最多只有一个前驱和一个后继。

（）19.二叉排序树查找总比顺序查找速度快。

（）20.对具有n个顶点的连通图进行深度优先遍历，所得顶点序列是唯一的。

（）21.线性表中各个数据元素的类型必须是相同的。

（）22.B+树是一种特殊的二叉树。

（）23.栈可视为一种特殊的线性表。

（）24.快速排序总是比其它排序方法快。

（）25.使用双向链表存储数据，可以提高查找（定位运算）的速度。

（）26.最小生成树是边数最少的生成树。

二、单选题1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。