下载文档原格式
数据结构一、单选题1. 计算机算法指的是（b ）。
A．程序B．问题求解步骤的描述C．调度方法D．排序方法2. 以下数据结构中，（a ）个是非线性数据结构。
A．树B．字符串C．队D．栈3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。
A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。
A.p->next=s;s->next=p->nextB.s->next=p->next; p->next=sC.p->next=s;p->next=s->nextD.p->next=s->next; p->next=s5. n个顶点的有向图中,含有向边的数目最多为( d )A．n-1 B．n C．n(n-1)/2 D．n(n-1)6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ）A．rear=rear+1 B．rear=(rear+1)mod(m-1)C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1)7. 字符串‟ababaabab‟的next函数为（d ）A.011232232B.012341234C.011122334D. 0112342348. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。
A．BA+141 B．BA+180 C．BA+222 D．BA+22510. n个顶点的带权无向连通图的最小生成树包含(b )个顶点A．n-1 B．nC．n/2 D．n+111．有关二叉树的下列说法正确的是（ b ）A．二叉树的度为2 B．一棵二叉树的度可以小于2C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为212．关键路径是AOE网中（ a ）。
第6章 二叉树与树一、回答题1. 图6-1所示的树的叶子结点、非中端结点、每个结点的度及树的深度各是多少？图6-1 树2. 已知一棵树边的集合表示为：{ ( L, N ), ( G, K ), ( G, L ), ( G, M ), ( B, E ), ( B, F ), ( D, G ), ( D, H ), ( D, I ), ( D, J ), ( A, B ), ( A, C ), ( A, D ) }，画出这棵树，并回答以下问题：(1) 树的根结点是哪个？哪些是叶子结点？哪些是非终端结点？ (2) 树的度是多少？各个结点的度是多少？ (3) 树的深度是多少？各个结点的层数是多少？(4) 对于结点G ，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点？3. 如果一棵度为m 的树中，度为1的结点数为n 1，度为2的结点数为n 2，……，度为m 的结点数为n m ，那么该树中含有多少个叶子结点？有多少个非终端结点？ABECDFGHJI4. 任意一棵有n 个结点的二叉树，已知有m 个叶子结点，能否证明度为2结点有m-1个？5. 已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点，那么该树含有的叶子结点的数目是多少？6. 一棵含有n 个结点的k 叉树，可能达到的最大深度和最小深度各为多少？7. 对于3个结点A 、B 、C ，可以过程多少种不同形态的二叉树？8. 深度为5的二叉树至多有多少个结点？9. 任何一棵二叉树的叶子结点在先序、中序和后序遍历中的相对次序是发生改变？不发生改变？不能确定？10. 设n 、m 为一棵二叉树上的两个结点，在中序遍历时，n 在m 前的条件是什么？ 11. 已知某二叉树的后续遍历序列是dabec ，中序遍历序列是debac ，那么它的前序遍历序列是什么？12. 对一棵满二叉树，m 个树叶，n 个结点，深度为h ，则n 、m 和h 之间的关系是什么？ 13. 对图6-2(a)和(b)所示的二叉树，它们的经过先序、中序和后序遍历后得到的结点序列分别是什么？画出它们的先序线索二叉树和后序线索二叉树。
数据结构练习题（含答案）1.1单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象1/ 62② A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
①2/ 62A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法② A. 可行性、可移植性和可扩充性B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性1.2填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有3/ 62结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
数据结构各章强化练习题线性表一、选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
3．线性表是具有n个（）的有限序列（n>0）。
A．表元素 B．字符 C．数据元素 D．数据项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表 B．双链表C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表 B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．. 链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比二、判断1. 链表中的头结点仅起到标识的作用。
2. 顺序存储结构的主要缺点是不利于插入或删除操作。
3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
5. 对任何数据结构链式存储结构一定优于顺序存储结构。
6．顺序存储方式只能用于存储线性结构。
7. 取线性表的第i个元素的时间同i的大小有关.8. 循环链表不是线性表.9. 线性表只能用顺序存储结构实现。
10. 线性表就是顺序存储的表。
11．为了很方便的插入和删除数据，可以使用双向链表存放数据。
12. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
13. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。
中南大学网络教育课程考试复习题及参考答案数据结构一、填空 :1.设需要对 5 个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较 __________ 次。
2.设二叉排序树的高度为h，则在该树中查找关键字key 最多需要比较 _________次。
3.设在长度为 20 的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有 _________个。
4.数据结构从逻辑上划分为三种基本类型：___________、__________ 和 ___________。
5.在一个具有 n 个顶点的无向完全图中，包含有________条边，在一个具有 n 个顶点的有向完全图中，包含有 ________条边。
6.向一棵 B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为 ________。
8.在快速排序、堆排序、归并排序中，_________排序是稳定的。
9.在有 n 个叶子结点的哈夫曼树中，总结点数是_______ 。
10.一棵树 T 采用二叉链表存储，如果树T 中某结点为叶子结点，则在二叉链表BT 中所对应的结点一定_______。
11.3. 已知数组 A［10］［ 10］为对称矩阵，其中每个元素占5个单元。
现将其下三角部分按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素A［ 5， 6］对应的地址是 _______。
12.在有 n 个结点的无向图中，其边数最多为_______。
13.取出广义表 A=(x,(a,b,c,d))中原子 x的函数是 _______。
14.对矩阵采用压缩存储是为了_______。
15.带头结点的双循环链表 L 为空表的条件是 _______。
16.设线性表中元素的类型是实型，其首地址为1024 ，则线性表中第 6 个元素的存储位置是。
二、填空题：1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和______________。
2、数据结构算法中，通常用时间复杂度和__________________两种方法衡量其效率。
3、一个算法一该具有______,______,____,______和____这五种特性。
4、若频繁地对线性表进行插入与删除操作，该线性表应采用____________存储结构。
5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_______；除最后一个元素之外，集合中每个数据元素均只有一个_________。
6、线性表中的每个结点最多有________前驱和____________后继。
7、______链表从任何一个结点出发，都能访问到所有结点。
8、链式存储结构中的结点包含____________域，_______________域。
9、在双向链表中，每个结点含有两个指针域，一个指向______结点，另一个指向________结点。
10、某带头结点的单链表的头指针head，判定该单链表非空的条件______________。
11、在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_____结点。
12、已知指针p指向单链表中某个结点，则语句p->next=p->next->next的作用__删除p 的后继结点_。
13、已知在结点个数大于1的单链表中，指针p指向某个结点，则下列程序段结束时，指针q指向*p的_____________结点。
q=p;while(q->next!=p)q=q->next;14、若要在单链表结点*P后插入一结点*S，执行的语句_______________。
15、线性表的链式存储结构地址空间可以_________，而向量存储必须是地址空间___________。
16、栈结构允许进行删除操作的一端为_____________。
树和二叉树习题及答案一、填空题1. 不相交的树的聚集称之为森林。
2. 从概念上讲，树与二叉树是两种不同的数据结构，将树转化为二叉树的基本目的是_树可采用孩子-兄弟链表（二叉链表）做存储结构，目的是利用二叉树的已有算法解决树的有关问题。
3. 深度为k的完全二叉树至少有2 k-1个结点。
至多有2 k-1个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是2 k-2+1。
4. 在一棵二叉树中，度为零的结点的个数为n，度为2的结点的个数为n2，则有n= n2+1。
5. 一棵二叉树的第i（i≥1）层最多有2 i-1个结点；一棵有n （n>0）个结点的满二叉树共有（n+1）/2个叶子和（n-1）/2个非终端结点。
6.现有按中序遍历二叉树的结果为abc，问有5种不同形态的二叉树可以得到这一遍历结果。
7. 哈夫曼树是带权路径最小的二叉树。
8. 前缀编码是指任一个字符的编码都不是另一个字符编码的前缀的一种编码方法，是设计不等长编码的前提。
9. 以给定的数据集合{4，5，6，7，10，12，18}为结点权值构造的Huffman树的加权路径长度是 165 。
10. 树被定义为连通而不具有回路的（无向）图。
11. 若一棵根树的每个结点最多只有两个孩子，且孩子又有左、右之分，次序不能颠倒，则称此根树为二叉树。
12. 高度为k，且有个结点的二叉树称为二叉树。
2k-1 满13. 带权路径长度最小的二叉树称为最优二叉树，它又被称为树。
Huffman14. 在一棵根树中，树根是为零的结点，而为零的结点是结点。
入度出度树叶15. Huffman树中，结点的带权路径长度是指由到之间的路径长度与结点权值的乘积。
结点树根16. 满二叉树是指高度为k，且有个结点的二叉树。
二叉树的每一层i上，最多有个结点。
2k-1 2i-1二、单选题1. 具有10个叶结点的二叉树中有 (B) 个度为2的结点。
(A)8 (B)9 (C)10 (D)112．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_（3）次序的遍历实现编号。
数据结构习题和答案习题课填空1、对于⼀棵⼆叉树，若⼀个结点的编号为i，则它的左孩⼦结点的编号为，双亲结点的编号为。
2、向⼀个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动个元素。
3、在⼀棵⼆叉树中，若双分⽀结点数为5个，单分⽀结点数为6个，则叶⼦结点数为个。
4、为了实现折半查找，线性表必须采⽤⽅法存储。
顺序5、⼀种抽象数据类型包括数据对象和。
6、在以L为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为__________和_______。
7、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。
8、队列的插⼊操作在进⾏，删除操作在进⾏。
9、⼆叉搜索树的中序遍历得到的结点序列为____ ____。
10、在顺序表中插⼊或删除⼀个元素，需要平均移动元素，具体移动的元素个数与有关。
11、栈的特点是。
12、在单链表中，除了⾸元结点外，任⼀结点的存储位置由。
13、在⼀个具有n个顶点的⽆向图中，要连通所有顶点则⾄少需要条边。
14、深度为k（设根的层数为1）的完全⼆叉树⾄少有个结点，⾄多有个结点。
15、⼀棵深度为6的满⼆叉树有个分⽀结点和个叶⼦结点。
16、⼀个算法的效率可分为效率和效率。
17、队列的特点是。
18、⼀棵深度为5的满⼆叉树中的结点数为个。
19、在⼀个具有n个顶点的⽆向完全图中，包含有________条边，在⼀个具有n个顶点的有向完全图中，包含有________条边。
简答题1、已知⼀组元素为（38，26，62，94，35，50，28，55），画出按元素排列顺序输⼊⽣成的⼀棵⼆叉搜索树。
答:2、假设有⼆维数组A[0..5,0..7]，每个元素⽤相邻的6个字节存储，存储器按字节编址。
已知A的起始存储位置（基地址）为1000，计算：（1）末尾元素A57的第⼀个字节地址为；（2）若按列存储时，元素A47的第⼀个字节地址为。
(3) 数组A的体积（存储量）；(4) 若按⾏存储时，元素A14的第⼀个字节地址为。
习题五树与二叉树一、选择题1、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足。
A、所有的结点均无左孩子B、所有的结点均无右孩子C、只有一个叶子结点D、是任意一棵二叉树2、一棵完全二叉树上有1001个结点，其中叶子结点的个数是。
A、250B、500C、254D、505E、以上答案都不对3、以下说法正确的是。
A、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树后序遍历序列中的最后一个结点B、若一个树叶是某二叉树前序遍历序列中的最后一个结点，则它必是该子树中序遍历序列中的最后一个结点C、在二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点D、在二叉树中，具有一个子女的父结点，在中序遍历序列中，它没有后继子女结点4、以下说法错误的是。
A、哈夫曼树是带权路径长度最短得数，路径上权值较大的结点离根较近B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点，则它必是该子树后序遍历序列中的第一个结点C、已知二叉树的前序遍历和后序遍历并不能唯一地确定这棵树,因为不知道树的根结点是哪一个D、在前序遍历二叉树的序列中,任何结点其子树的所有结点都是直接跟在该结点之后的5、一棵有124个叶结点的完全二叉树，最多有个结点。
A、247B、248C、249D、250E、2516、任何一棵二叉树的叶结点在前（先）序、中序和后序遍历序列中的相对次序。
A、不发生变化B、发生变化C、不能确定7、设a、b为一棵二叉树上的两个结点。
在中序遍历时，a在b前面的条件是。
A、a在b的右方B、a在b的左方C、a是b的祖先D、a 是b的子孙8、设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含的结点总数为。
A、不确定B、2kC、2k-1D、2k+19、设有13个值，用它们组成一棵哈夫曼树，则该哈夫曼树共有个结点。
A、13B、12C、26 D、2510、下面几个符号串编码集合中，不是前缀编码的是。
一、填空题1.数据结构包括、和三方面的内容。
2.数据的逻辑结构分为、、、。
3.数据的逻辑结构分为和两大类。
4.数据的存储结构被分为、、、。
5.数据的存储方式有、、和四种基本存储方式。
6.顺序存储和链式存储相比较的存储密度大，的插入删除方便。
7.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫域，另一个叫域。
8.在线性表的单链接存储中，若一个元素所在结点的地址为P，则其后继结点的地址为，若假定P为一个数组a中的下标，则其后继结点的下标为。
9.在顺序存储的向量中，设第一个元素的地址为loc(k1)，每个元素占用的空间为M，则第i个元素ki的地址为loc(ki)=loc(k1)+(i-1)*M 。
10.在循环单链表中，最后一个结点的指针域指向结点。
11.队列的插入操作在进行，删除操作在进行。
12.一棵n个结点的树，其边数为条。
13.设二叉树根结点的层数为0，则第i层上最多有个结点。
14.在一棵二叉树中，第5层上的结点数最多为。
15.深度为 K 的完全二叉树，至少有个结点，至多有个结点。
16.深度为 8 (根的层次号为 1 )的满二叉树有个叶子结点。
17.深度为K的二叉树结点总数最大为。
18.深度为 k (根的层次号为 1 )的满二叉树有个叶子结点。
19.在完全二叉树中，对结点按层次编号，根结点编号为1。
若结点i有右子女，则右子女的编号为，左子女的编号为。
20.按后根次序周游树林，正好等同于按次序周游与之对应的二叉树。
21.按先根次序周游树林，正好等同于按次序周游对应的二叉树。
22.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个。
23.在一个具有n个顶点的无向完全图中，包含有条边。
24.设有m个结点的无向图中，如果其边数为就称为完全图。
25.在图中，与结点相关的边的数目称为该结点的。
26.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有和结点。
27.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。
一、判断题四．串1、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。
（）2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。
（）3、一个任意串是其自身的子串。
（）1、∨2、Χ3、∨五．数组和广义表1、多维数组是向量的推广。
（）/*数组和广义表线性表在含义上的扩展*/2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。
（）/*顶点*/3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。
（）4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。
（）/*稀疏矩阵中0元素的分布无规律*/5. 如果采用如下方式定义一维字符数组：const int maxSize = 30;/*常变量在程序运行中不能进行修改*/char a[maxSize];则这种数组在程序执行过程中不能扩充。
6. 如果采用如下方法定义一维字符数组：int maxSize = 30;char * a = new char[maxSize];则这种数组在程序执行过程中不能扩充。
7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。
/*对于数组一旦规定了它的维数和各维长度，便可为它分配存储空间*/8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。
10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。
1-5ΧΧΧΧ∨6-10ΧΧ∨∨∨11、一个广义表的深度是指该广义表展开后所含括号的层数。
（）12. 一个广义表的表头总是一个广义表。
( )13. 一个广义表的表尾总是一个表。
( )14. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。
( )15. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是（ ( (b), c), ( ( (d) ) )）。
一、选择题1、下列关于数据和逻辑结构的叙述中，哪一个是不正确的（Ｃ）。
A ) 数据的逻辑结构是数据间关系的描述B) 数据的逻辑结构抽象反映数据元素间的逻辑关系C) 数据的逻辑结构具体反映数据在计算机中的存储方式D) 数据的逻辑结构分为线性结构和非线性结构2、以下关于数据的存储结构的叙述中哪一条是正确的（Ｂ）。
A) 数据的存储结构是数据间关系的抽象描述B) 数据的存储结构是逻辑结构在计算机存储器中的实现C) 数据的存储结构分为线性结构和非线性结构D) 数据的存储结构对数据运算的具体实现没有影响3、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B .（A）正确（B）错误4、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是(A)空或只有一个结点(B) 完全二叉树(C)二叉排序树(D) 高度等于其节点数5、深度为5的二叉树至多有 C 多少个结点.(A)16 (B)32 (C)31 (D)106、根据使用频率为5个字符设计的哈夫曼编码不可能是C（A）111，110，10，01，00 （B）000，001，010，011，1（C）100，11，10，1，0 （D）001，000，01，11，107、一个n个顶点的无向图最多有条边。
(A) n (B) n(n-1) (C) n(n-1)/2 (D) 2n8、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。
（A）1/2 （B）1 （C）2 （D）49、关键路径是事件结点网络中。
（A）从源点到汇点的最长路径（B）最长的回路（C）从源点到汇点的最短路径(D）最短的回路10、下面不正确的说法是。
A、关键活动不按期完成就会影响整个工程的完成时间B、任何一个关键活动提前完成，将使整个工程提前完成C、所有关键活动都提前，则整个工程提前完成D、某些关键活动若提前完成，将使整个工程提前完成。
11、采用顺序查找法查找长度为n的线性表时，则查找成功时的平均查找长度为 C 。
东华理工大学2021 —2021学年第 一 学期考试模拟试卷 A一、 填空题〔50分〕1、数据构造是一门研究非数值计算的程序设计问题中的 数据元素 以及它们之间 关系 和运算等的科学。
〔2分〕2、数据构造的类型通常分为： 集合、线性构造、树形构造、图状构造或网状构造 ；从逻辑上可以把它们分成： 线性构造和非线性构造 。
3、数据的 逻辑构造 只抽象反映数据元素的 逻辑关系 ；数据的 存储〔物理〕构造 是数据的逻辑构造 在计算机存储器中的实现 。
4、算法分析的目的是分析算法的 效率以求改良 ，算法分析的两个主要方面是 空间复杂度和时间复杂度 。
A5、计算机算法是解决问题的 有限运算序列 ，它必须具备 输入、输出、确定性、有穷性和稳定性 等5个方面的特性。
6、线性构造中元素之间的关系存在 一对一 关系，树形构造中元素之间的关系存在 一对多 关系，图形构造中元素之间的关系存在 多对多 关系。
7、试写出以下算法的时间复杂度i=s=0while (s<n) {i++;s += i;}7、试写出以下算法的时间复杂度i = 1 while( i <= n) )(n Oi = i*2O(log2n)8、抽象数据类型的定义由三元组来定义：(D,S,P)其中，D是数据对象， S是D上的关系集，P是对D的根本操作集。
9、写出抽象数据类型线性表的定义ADT List{数据对象：D={ai | ai ∈Elemset, i=1,2,…,n,n≥0}数据关系：R={< ai-1 , ai> | ai-1 , ai ∈D, i=2,…,n}根本操作：InitList(&L) //构造一个空的线性表LDestroyList(&L) //消毁线性表LListLength(L) //返回L中数据元素的个数ListInsert(&L,i,e) // 1 ≤ i ≤ ListLength(L)+1,在L中第i个位置之前插入数据元素e,L长度加1ListDelete(&L,i,&e) // 1 ≤ i ≤ ListLength(L),删除L中的第i个元素，并用e 返回ListTraverse(L,visit()) //依次对L的每个元素调用函数visit()…………} ADT List10、指出线性表顺序存储、链式存储构造的优缺点。
绪论一、填空题1.数据的逻辑结构被分为集合、(线性结构)、(树形结构)和(图状结构)四种。
2.物理结构是数据结构在计算机中的表示，又称为(存储结构)。
3.数据元素的逻辑结构包括( 线性)、(树)和图状结构3种类型，树形结构和图状结构合称为(非线性结构)。
4.(数据元素)是数据的基本单位，(数据项)是数据不可分割的最小单位。
5.线性结构中元素之间存在(一个对一个)关系，树形结构中元素之间存在(一个对多个)关系，图状结构中元素之间存在(多个对多个)关系。
6.数据结构是一门研究非数值计算的程序设计问题中：计算机的(数据元素)以及它们之间的(关系)和(运筹)等的学科。
7.算法的五个重要特性为有穷性、确定性、(输入)、(输出)和(可行性)。
二、选择题1.数据的不可分割的基本单位是(D)。
A.元素B.结点C.数据类型D.数据项*2.线性表的逻辑顺序与存储顺序总是一致的，这种说法(B)。
A.正确B.不正确C.不确定D.无法选择3.线性结构是指数据元素之间存在一种(D)。
A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.在数据结构中，从逻辑上可以把数据结构分成(A)。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构5.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( D)。
A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以三、简答题1.算法的特性是什么。
答：有穷性确定性可行性有0或多个输入有1或多个输出线性结构一、填空题1.在一个长度为n的线性表中删除第i个元素（1≤i≤n）时，需向前移动(n-i)个元素。
2.从循环队列中删除一个元素时，其操作是(先移动队首指针，后取出元素)。
3.在线性表的单链接存储中，若一个元素所在结点的地址为p，则其后继结点的地址为(p->next)。
4.在一个单链表中指针p所指向结点的后面插入一个指针q所指向的结点时，首先把(p->next)的值赋给q->next，然后(q->date)的值赋给p->next。
数据结构第二单元练习题答案一、选择1.树最适合用来表示( )A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2.在下述结论中，正确的是( )①只有一个结点的二叉树的度为0; ②二叉树的度为2；③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③B.②③④C.②④D.①④3.以下说法正确的是( )A.任何一棵二叉树中至少有一个结点的度为2B.任何一棵二叉树中每个结点的度都为2C.任何一棵二叉树的度肯定等于2D.任何一棵二叉树的度可以小于24.在下列情况中，可称为二叉树的是( )A.每个结点至多有两棵子树的树B.哈夫曼树C.每个结点至多有两棵子树的有序树D.每个结点只有一棵右子树E.以上答案都不对5.深度为h的满m叉树的第k层有( )个结点(1=<k=<h)A.m k-1B.m k-1C.m h-1D.m h-16.在一棵高度为k的满二叉树中，结点总数为( )A.2k-1B.2kC.2k-1D.⎣log2k⎦+17.在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为( )个A.4B.5C.6D.78.具有10个叶结点的二叉树中有( )个度为2的结点。
A.8B.9C.10D.ll9.二叉树有n个结点，则其深度为（）A.n-1B.nC.(log2n)+`1 D.无法确定该题是二叉树不是完全二叉树由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。
10.一个具有1025个结点的二叉树的高h为( )A.11 B．10 C.11至1025之间 D.10至1024之间11.一棵具有 n个结点的完全二叉树的深度是( )A.⎣log2n⎦+1 B.log2n+1 C.⎣log2n⎦ D.log2n-112.将有关二叉树的概念推广到三叉树，则一棵有244个结点的完全三叉树的高度( )A.4B.5C.6D.713.将一棵有100个结点的完全二叉树从根结点这一层开始，每一层上从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的左孩子编号为（）A.98B.99C.50D.48利用二叉树的性质514.在完全二叉树中，若一个结点是叶结点，则它没( )A.左子结点B.右子结点C.左子结点和右子结点D.左子结点，右子结点和兄弟结点15.当一棵有n个结点的二叉树按层次从上到下，同层次从左到右将数据存放在一维数组A[l..n]中时，数组中第i个结点的左孩子为( )A.A[2i](2i=<n)B.A[2i+1](2i+1=<n)C.A[i/2]D.无法确定16.在下列存储形式中，( )不是树的存储形式？A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法17.以下说法错误的是( )A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达B.三叉链表，二叉树求双亲运算很容易实现C．在二叉链表上，求左.右孩子等很容易实现D.在二叉链表上，求双亲运算的时间性能很好18.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用（）次序的遍历实现编号。
