数据结构填空练习题
数据结构填空练习题
一
1. 通常从四个方面评价算法的质量：_________、_________、_________和________。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为__________个，树的深度为___________，树的度为_________。
4. 后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。
5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩
子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。
6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。
7. AOV网是一种___________________的图。
8. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
9. 假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。
11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。
12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。
1. 正确性易读性强壮性高效率
2. O(n)
3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / -
5. 2n n-1 n+1
6. e 2e
7. 有向无回路8. n(n-1)/2 n(n-1)
9. （12，40）（）（74）（23,55，63）10.增加1
11.O(log2n) O(nlog2n) 12.归并
二
1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第
二个栈顶指针top2的初值为n，则判断共享栈满的条件是______________。 2. 在图的邻接表中用顺序存储结构存储表头结点的优点是________________。 3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包
括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。
4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把
栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。 5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的
前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。
6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有
__________个叶子结点。
7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素
个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。
8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2
而言满足的条件为_______________________________。
9.下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。
10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。
}
答案
1. top1+1=top2
2. 可以随机访问到任一个顶点的简单链表
3. i(i+1)/2+j-1
4. FILO，FIFO
5. ABDECF，DBEAFC，DEBFCA
6. 8，64
7. 出度，入度
8. ki<=k2i && ki<=k2i+1
9. n-i，r[j+1]=r[j]
10. mid=(low+high)/2，r[mid].key>k
三
1. 数据结构按逻辑结构可分为两大类，分别是______________和_________________。
2. 数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。
3. 线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。
4. 一个算法的效率可分为__________________效率和__________________效率。
5. 在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。
6. 在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。
7. 线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。
8. 下面程序段的时间复杂度是__________________。
第8题9题10题11题
9. 下面程序段的时间复杂度是__________________。
10. 下面程序段的时间复杂度是__________________。
11. 下面程序段的时间复杂度是__________________。
12. 衡量算法正确性的标准通常是____________________________________。
13. 算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。
答案
1.线性结构，非线性结构
2.集合，线性，树，图
3. 一对一，一对多或多对多
4. 时间，空间
5. 前趋，一，后继，多
6. 有多个
7. 一对一，一对多，多对多
12. 程序对于精心设计的典型合法数据输入能得出符合要求的结果。
13. 事后统计，事前估计
四
1. 线性表是一种典型的_________结构。
2. 在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。
3. 顺序表中逻辑上相邻的元素的物理位置________。
4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。
5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。
6. 在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。
7. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。
8. 顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。
9. 线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。
10. 根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。
11. 在单链表中设置头结点的作用是________。
12. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。
13. 对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。
14. 设有一空栈，现有输入序列1，2，3，4，5，经过push, push, pop, push, pop, push, push 后，输出序列是_________。
15. 无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。
答案
1．线性 2．n-i+1 3．相邻 4．前移，前，后
5．物理存储位置，链域的指针值 6．前趋，后继
7．顺序，链接 8．一定，不一定
9．线性，任何，栈顶，队尾，队头
10．单链表，双链表，非循环链表，循环链表
11．使空表和非空表统一；算法处理一致12．O(1)，O(n)
13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇
14．2、3 15．O(1)
五
1. 计算机软件系统中，有两种处理字符串长度的方法：一种是___________，第二种是___________________。
2. 两个字符串相等的充要条件是_____________________和___________________。
3. 设字符串S1= “ABCDEF”，S2= “PQRS”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。
4. 串是指___________________。
5. 空串是指___________________，空格串是指___________________。
1. 固定长度，设置长度指针
2. 两个串的长度相等，对应位置的字符相等
3. “BCDEDE”
4. 含n个字符的有限序列（n≥0）
5. 不含任何字符的串，仅含空格字符的字符串
六
1. 一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。
2. 对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。
3. 一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。
4. 一个稀疏矩阵为如右图，则对应的三元组线性表为
_____________。
5. 一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。
6. 已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。
7. 设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a85的地址为______________。
8. 已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。
9. 三维数组R[c1…d1,c2…d2,c3…d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）
10. 数组A[1…10，-2…6，2…8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。
1.线性结构，顺序结构，以行为主序，以列为主序
2. i×n+j个元素位置
3. 5，3
4.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））
5. n×(n+1)/2
6. e
7. 41
8. head(head(tail(Ls)))
9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1）10. 913
七
1. 假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。
2. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。
3. 对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。
4. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。
5. 在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。
6. 对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。
7. 在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。
8. 一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。
9. 由三个结点构成的二叉树，共有____种不同的形态。
10. 设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。
11. 一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。
12. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。
13. 对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。
14. 哈夫曼树是指________________________________________________的二叉树。
15. 空树是指________________________，最小的树是指_______________________。
16. 二叉树的链式存储结构有______________和_______________两种。
17. 三叉链表比二叉链表多一个指向______________的指针域。
18. 线索是指___________________________________________。
19. 线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。
20. 本节中我们学习的树的存储结构有_____________、___________和___________。
1. 3，4，6，1，1，2，A，F，G
2. n+1
4. 55
5. 中序
6. 2n，n-1，n+1
7. n2+1
8. 2k-1，2k-1，2k-1 9. 5 10. 2h-1
11. 单支树，完全二叉树12. 2i，2i+1，i/2i/213. 2n，n-1，n+1
14. 带权路径长度最小15. 结点数为0，只有一个根结点的树
16. 二叉链表，三叉链表17. 双亲结点18. 指向结点前驱和后继信息的指针19. 1，RChild 20. 孩子表示法，双亲表示法，长子兄弟表示法
八
1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。
2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。
3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{
4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。
5.表示图的两种存储结构为__________和__________。
6.在一个连通图中存在着________个连通分量。
7. 图中的一条路径长度为k，该路径所含的顶点数为________。
8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________个连通分量。
9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为________ ________。
10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结点的个数分别为________和________。
11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有________和________结点。
12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂度分别为________和________。
13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空间复杂度分别为________和________。
14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为____________。
15. 一个图的边集为{
16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法需要使用队列。
17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为________和________。
18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/不唯一）的。
19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。
20. 假定一个有向图的边集为{
1. 2
2. n(n-1)/2，n(n-1)
3. 2，4
4. n-1
5. 邻接矩阵，邻接表
6. 1
7. k+1
8. 3
9. n，n 10. 2e，e 11. 出边，入边 12. O（n），O（e/n）
13.O（n2），O（n+e） 14. acdeb，acedb （答案不唯一）
15. acfebd，acefbd （答案不唯一）16. 深度，广度17. n，n-1
18.唯一19. 唯一 20. aebdcf（答案不唯一）
九
1. 以顺序查找方法从长度为n的顺序表或单链表中查找一个元素时，平均查找长度为________，时间复杂度为________。
2. 对长度为n的查找表进行查找时，假定查找第i个元素的概率为pi,查找长度（即在查找过程中依次同有关元素比较的总次数）为ci，则在查找成功情况下的平均查找长度的计算公式为________。
3. 假定一个顺序表的长度为40，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长度________，在查找不成功情况下的平均查找长度________。
4. 以折半查找方法从长度为n的有序表中查找一个元素时，平均查找长度约等于________的向上取整减1，时间复杂度为________。
5. 以折半查找方法在一个查找表上进行查找时，该查找表必须组织成________存储的________表。
6. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43和56元素时，其比较次数分别为________和________。
7. 假定对长度n=50的有序表进行折半查找，则对应的判定树高度为________，最后一层的结点数为________。
8. 假定在索引查找中，查找表长度为n，每个子表的长度相等，设为s，则进行成功查找的平均查找长度为____________。
9. 在索引查找中，假定查找表（即主表）的长度为96，被等分为8个子表，则进行索引查找的平均查找长度为________。
10. 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定________该结点的值，右子树上所有结点的值一定________该结点的值。
11. 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个________。
12. 从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明_______，若元素的值小于根结点的值，则继续向________查找，若元素的值大于根结点的值，则继续向________查找。
13. 向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则接着向根结点的
________插入，若元素的值大于根结点的值，则接着向根结点的________插入。
14. 根据n个元素建立一棵二叉排序树的时间复杂度大致为________。
15. 在一棵平衡二叉排序树中，每个结点的左子树高度与右子树高度之差的绝对值不超过________。
16. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则在建立哈希表的过程中，将会碰到________次存储冲突。
17. 假定对线性表(38,25,74,52,48)进行哈希存储，采用H(K)=K % 7作为哈希函数，采用线性探测法处理冲突，则平均查找长度为________。
18. m表示哈希表的长度，n表
________。
19. 对线性表(18,25,63,50,42,32,90)进行哈希存储时，若选用H(K)=K % 9作为哈希函数，则哈希地址为0的元素有________个，哈希地址为5的元素有________个。
1. (n+1)/2, O(n)
3. 20.5, 41
4. log2(n+1)O(log2n)
5. 顺序有序
6. 1，3
7. 6， 19
8. (n/s+s)/2+1
9. 11 10.小于，大于11. 有序序列 12. 查找成功，左子树，右子树
13. 左子树，右子树 14. O(nlog2n) 15. 1
16. 5 17. 2 18. n/m 19. 3， 2
《数据结构》填空作业题答案
《数据结构》填空作业题答案 第1章绪论（已校对无误） 1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。 2．程序包括两个内容：数据结构和算法。 3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。 4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。 5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。 6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。 7. 在树形结构中，数据元素之间存在一对多的关系。 8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。 9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。 10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。 11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。 12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。 13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。 14. 数据结构在物理上可分为顺序存储结构和链式存储结构。 15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。 16. 数据元素可由若干个数据项组成。 17. 算法分析的两个主要方面是时间复杂度和空间复杂度。 18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。 19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。 20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切 的定义，并在有穷时间内计算出结果。 n 。 21. 下面程序段的时间复杂度为㏒ 3
电大考试数据结构(本)试题集附答案
数据结构（本）期末综合练习 2017年5月 有得看就不难 综合练习一 一、单项选择题 1．设有头指针为head的带有头结点的非空单向循环链表, 指针p指向其尾结点, 要删除头结点,并使其仍为单向循环链表,则可利用下述语句head =head->next ;（）。 A．p =head; B．p=NULL; C．p->next =head; D．head=p; 2．在一个单链表中p指向结点a, q指向结点a的直接后继结点b，要删除结点b，可执 行（）。 A．p->next=q->next ; B．p=q->next; C．p->next=q; D．p->next=q; 3. 以下说法不正确的是 A. 线性表的链式存储结构不必占用连续的存储空间 B．一种逻辑结构只能有唯一的存储结构 C. 一种逻辑结构可以有不同的存储结构 D．线性表的顺序存储结构必须占用连续的存储空间 4．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行（）;和 p->next=s; A．p= s; B． p->next=s->next; C．p=s->next; D． s->next=p->next; 5．把数据存储到计算机中，并具体体现( )称为物理结构。 A. 数据元素间的逻辑关系 B．数据的处理方法 C．数据的性质 D．数据的运算 6．设有一个长度为23的顺序表，要删除第8个元素需移动元素的个数为（）。 A．16 B．14 C．15 D．13 7．链表所具备的特点之一是（）。 A．可以随机访问任一结点 B．需要占用连续的存储空间 C．插入元素的操作不需要移动元素 D．删除元素的操作需要移动元素 8．设一棵有8个叶结点的二叉树，度数为1的结点有3个,则该树共有（）个结点。 A．20 B．18 C．17 D．16 9．图状结构中数据元素的位置之间存在（）的关系。 A．一对一 B．多对多 C．一对多 D．每一个元素都有一个直接前驱和一个直接后继10．一棵具有5层的完全二叉树，最后一层有4个结点，则该树总共有（）个结点。 A．14 B．15 C．19 D．18 11．元素15，9，11，13按顺序依次进栈，则该栈的不可能输出序列是（） （进栈出栈可以交替进行）。 A．13，11，9，15 B．15，9，11，13 C．13，11，15，9 D．9， 15，13，11 1
(完整版)数据结构练习题(含答案)
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ② A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 1、数据结构按结点间的关系，可分为4种逻辑结构： 集合、线性结构、树形结构、图状结构。 2、数据结构中的数据元素存在多对多的关系称为图 状结构结构。 3、在一个长度为n的顺序存储结构的线性表中，向第 i(1≤i≤n+1)个元素之前插入新元素时，需向后移动n-i+1个数据元素。 4、从长度为n的采用顺序存储结构的线性表中删除第 i(1≤i≤n+1)个元素，需向前移动n-i个元素。5、数据的逻辑结构在计算机中的表示称为物理结构 或存储结构。 6、除了第1个和最后一个结点外，其余结点有且只有一 个前驱结点和后继结点的数据结构为线性结构，每个结点可有任意多个前驱和后继结点数的结构为非线性结构。 7、算法的5个重要特性是有穷性、确定性、可形 性、有零个或多个输入、有零个或多个输出。 8、数据结构中的数据元素存在一对多的关系称树 形结构结构。 9、往栈中插入元素的操作方式是：先移动栈顶指针， 后存入元素。 10、数据结构中的数据元素存在一对一的关系称为线 性结构结构。 11、要求在n个数据元素中找其中值最大的元素，设基本 操作为元素间的比较。则比较的次数和算法的时间复杂度分别为n-1和O(n)。 12、在一个单链表中p所指结点之后插入一个s所指结点 时，应执行__s->next=p->next;__和p->next=s;的操作。 13、设有一个头指针为head的单向循环链表，p指向链 表中的结点，若p->next= =head，则p所指结点为尾结点。 14、在一个单向链表中，要删除p所指结点，已知q指向 p所指结点的前驱结点。则可以用操作q->next=p->next; 。 15、设有一个头指针为head的单向链表，p指向表中某 一个结点，且有p->next= =NULL,通过操作p->next=head;,就可使该单向链表构造成单向循环 链表。 16、每个结点只包含一个指针域的线性表叫单链表。 17、线性表具有顺序存储和链式存储两种 存储结构。 18、数据的逻辑结构是从逻辑关系上描述数据，它与数据 的关系存储结构无关，是独立于计算机的。19、在双向循环链表的每个结点中包含两个指针域，其 中next指向它的直接后继，prior指向它的直接前驱，而头结点的prior指向尾结点，尾结点的next指向头结点。 20、单向循环链表是单向链表的一种扩充，当单向链表带 有头结点时，把单向链表中尾结点的指针域由空指针改为头结点的指针；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向指向第一个结点的指针。 21、线性链表的逻辑关系时通过每个结点指针域中的指 针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种链式存储结构，又称为链表。 22、栈是限定在表的一端进行插入和删除操作的线性表， 又称为后进先出表。 23、队列的特性是先进先出表。 24、删除栈中元素的操作方式是：先取出元素，后移 动栈顶指针。 25、循环队列队头指针在队尾指针下一个位置，队列是 “满”状态 26、在队列的顺序存储结构中，当插入一个新的队列元素 时，尾指针增1 ，当删除一个元素队列时，头指针增1。 27、循环队列的引入，目的是为了克服假上溢。 28、向顺序栈插入新元素分为三步：第一步进行栈是否 满判断，判断条件是s->top=MAXSIZE-1 ；第二步是修改栈顶指针；第三步是把新元素赋给栈顶对应的数组元素。同样从顺序栈删除元素分为三步：第一步进行栈是否空判断，判断条件是s->top=-1。第二步是把栈顶元素；第三步修改栈顶指针。 29、假设以S和X分别表示入栈和出栈操作，则对输入序 列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为bceda。 "题目1：把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。: 逻辑结构 ; 算法的具体实现 ; 给相关变量分配存储单元 ; 物理结构" "题目2：下列说法中，不正确的是（）。 : 数据元素是数据的基本单位 ; 数据项可由若干个数据元素构成 ; 数据项是数据中不可分割的最小可标识单位 ; 数据可有若干个数据元素构成" "题目3：一个存储结点存储一个（）。 : 数据类型 ; 数据元素 ; 数据结构 ; 数据项" "题目4：数据结构中，与所使用的计算机无关的是数据的（）。 : 物理结构 ; 逻辑结构 ; 存储结构 ; 物理和存储结构" "题目5：在线性表的顺序结构中，以下说法正确的是（）。 : 数据元素是不能随机访问的 ; 逻辑上相邻的元素在物理位置上也相邻 ; 进行数据元素的插入、删除效率较高 ; 逻辑上相邻的元素在物理位置上不一定相邻" "题目6：对链表, 以下叙述中正确的是（）。 : 插入删除元素的操作一定要要移动结点 ; 不能随机访问任一结点 ; 可以通过下标对链表进行直接访问 ; 结点占用的存储空间是连续的" "题目7：下列的叙述中，不属于算法特性的是（）。 : 输入性 ; 可读性 ; 可行性 ; 有穷性" "题目8：算法的时间复杂度与（）有关。 : 数据结构 ; 计算机的操作系统 ; 所使用的计算机 ; 算法本身" "题目9：设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素），插入一个元素，则移动元素个数为（）。 : n-i+1 ; n-i-1 ; i ; n-i" "题目10：设有一个长度为n的顺序表，要删除第i个元素移动元素的个数为（）。 : n-i-1 ; n-i ; i ; n-i+1" "题目11：在一个单链表中，p、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除q所指结点，可用语句（）。 : p->next=q->next ; q->next=NULL ; p->next=q ; p=q->next" "题目12：在一个单链表中p所指结点之后插入一个s所指的结点时，可执行（）。 : s->next=p->next; p->next=s; ; p->next=s->next; ; p->next= s; s->next= p->next ; p=s->next" "题目13：非空的单向循环链表的尾结点满足（）（设头指针为head，指针p指向尾结点）。 : p== head ; p->next==NULL ; p->next==head ; p==NULL" "题目14：链表不具有的特点是（）。 : 插入删除不需要移动元素 ; 不必事先估计存储空间 ; 逻辑上相邻的元素在物理位置上不一定相邻 ; 可随机访问任一元素" "题目15：带头结点的链表为空的判断条件是（）（设头指针为head）。 : head->next==head ; head->next==NULL ; head!=NULL ; head ==NULL" "题目16：在一个长度为n的顺序表中为了删除第5个元素，由第6个元素开始从后到前依次移动了15个元素。则原顺序表的长度为（）。 : 19 ; 21 ; 25 《数据结构-C语言版》 第一章绪论 单项选择题 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. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对 《数据结构》程序填空复习题 说明：本文档中涉及到的算法并非本书的全部，有些可根据此处的情况自行看书和作业题，黑色为综合练习上的题目，红色为我另增加的题，这些空的选择是根据我个人的经验来决定的并不能完全代表中央电大的出卷老师，因此一定不能有肯定就考这些题目的想法。不能放弃其他内容的复习，切记！！！ 一、线性表 1.设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 #define NULL 0 void main( ) {NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; d.data=4; /*d是尾结点*/ head= （1）; a.next=&b; b.next=&c; c.next=&d; （2）; /*以上结束建表过程*/ p=head; /*p为工作指针，准备输出链表*/ do {printf(“%d\n”, （3）); （4）; }while( （5）); } 答案： （1）&a （2）d next=NULL （3）p->data （4）p=p->next （5）p!=NULL 2. 以下函数在head为头指针的具有头结点的单向链表中删除第i个结点， struct node { int data; struct node *next; }; typedef struct node NODE int delete(NODE *head,int i ) { NODE *p,*q; int j; q=head; j=0; while((q!=NULL)&&( ___(1)_____)) { ___(2)_____; j++; } if(q==NULL) return(0); p= ___(3)_____; ___(4)_____=p->next; free(___(5)_____); return(1); } 答案： （1）j 习题一 一、填空题 1. 算法具有有穷性、确定性、可行性、输入和输出五大特征。 2. 数据结构的内容包括以下三个方面：数据元素、数据关系和运算集合。 3. 数据结构的存储结构分为顺序、链式、索引、散列。 4. 评价算法性能的标准主要从算法执行时间和空间两方面考虑。 5. 在线性结构、树形结构和图状结构中，数据元素之间分别存在着1对1 、1对多和多对多关系。 二、分析题 2.设n为整数，分析下列程序段中，用*标明的语句的语句频度及时间复杂度。（1）for(n =1;n<=10;n++) *s=s+n; (2) for(i =1;i<=n;i++) *s=s+n; (3) for(i =1;i<=n;i++) for(j=1;j<=n;j++) *s=s+n (4) for(i =1;i<=n;i++) for(j=1;j<=i ;j++) *s=s+n; （5）for(i =1;i<=n;i++) for(j=1;j<=n;j++) { c[i][j]=0; for(k=1;k<=n;k++) *c[i][j]=c[i][j]+a[i][k]*b[k][j]; } 习题二 3.填空题 1.在顺序表中，逻辑上相邻的元素，其物理位置上一定相邻。 2.在单链表中，逻辑上相邻的元素，其物理位置上不一定相邻。 3.设单链表中，指针p指向结点s，若要删除s之后的结点（若存在），则需修改指针的操作为P=s->next;s->next=s->next->next;free(p); 。 4.在一个长度为n的顺序表中，如果要删除第i个元素，需移动n-i+1 个元素。 二、选择题 1.某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算，则采用（C ）存储方式的时间性能最好。 A.双向链表 B.双向顺环链表 C.顺序表 D.单向顺环链表 2.在一个单链表中，已知q结点是p结点的前驱结点，若在p和q之间插入s结点，则需执行（ C ）。 A.s->next=p->next;p->next=s B.p->next=s->next;s->next=p C.q->next=s;s->next=p D.p->next=s;s->next=q 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 数据结构习题 习题一绪论 .1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。 ①A．操作对象Ｂ．计算方法Ｃ．逻辑存储Ｄ．数据映象 ②A．结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。 ①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．逻辑结构 ②A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成①。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 线性表的顺序存储结构是一种①的存储结构，线性表的链式存储结构是一种②的存储结构。 A．随机存取B．顺序存取C．索引存取D．散列存取 5. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 6. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ①A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 7. 线性表的逻辑顺序与存储顺序总是一致的，这种说法①。 A. 正确 B. 不正确 8. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址①。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续或不连续都可以 9. 在以下的叙述中，正确的是①。 A.线性表的线性存储结构优于链表存储结构 B.二维数组是其数据元素为线性表的线性表 C.栈的操作方式是先进先出 D.队列的操作方式是先进后出 10. 每种数据结构都具备三个基本运算：插入、删除和查找，这种说法①。 A. 正确 B. 不正确 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括①、②和③三种类型，树形结构和图形结构合称为④。 集合、线性结构、树型结构非线性结构 2. 在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；最后一个结点③后续结点，其余每个结点有且只有④个后续结点。 无、一、无、一 3. 在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点，叶子结点没有③结点，其余每个结点的后续结点可以④。 前驱、一、后继、零个至多个 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以①。 任意多个 5. 线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。 一对一、一对多、多对多 6. 算法的五个重要特性是 7. 下面程序段的时间复杂度是①。 for (i=0;i 栈和队列 3.1 单项选择题 1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是。 A. edcba B. decba C. dceab D. abcde 2. 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为。 A. i B. n=i C. n-i+1 D. 不确定 3. 栈结构通常采用的两种存储结构是。 A.顺序存储结构和链式存储结构 B. 散列方式和索引方式 C. 链表存储结构和数组 D. 线性存储结构和非线性存储结构 4. 判定一个顺序栈ST（最多元素为m0）为空的条件是。 A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST（最多元素为m0）为栈满的条件是。 A. top！=0 B. top= =0 C. top！=m0 D.top= =m0-1 6. 栈的特点是 B ，队列的特点是 A 。 A. 先进先出 B. 先进后出 7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行。 (不带空的头结点) A. HS—＞next=s; B. s—＞next= HS—＞next; HS—＞next=s; C. s—＞next= HS; HS=s; D. s—＞next= HS; HS= HS—＞next; 8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行。(不带空的头结点) A. x=HS; HS= HS—＞next; B. x=HS—＞data; C. HS= HS—＞next; x=HS—＞data; D. x=HS—＞data; HS= HS—＞next; 9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是。 A. 4，3，2，1 B. 1，2，3，4 C. 1，4，3，2 D. 3，2，4，1 10. 判定一个循环队列QU（最多元素为m0）为空的条件是。 A. rear - front= =m0 B. rear-front-1= =m0 C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是。 A. ((rear- front)+ Maxsize)% Maxsize = =m0 B. rear-front-1= =m0 C. front= =rear D. front= = rear+1 12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。 A. (rear-front+m)%m B. rear-front+1 电大数据结构（本）考核作业答案 作业1 一、单项选择题 1．C 2．D 3．B 4．C 5．D 6．C 7．B 8．C 9．A 10．B 11．C 12．D 13．C 14．A 15．B 16．C 17．C 18．B 19．B 20．D 二、填空题 1．n-i+1 2．n-i 3．集合线性结构树形结构图状结构 4．物理结构存储结构 5．线性结构非线性结构 6．有穷性确定性可形性有零个或多个输入有零个或多个输出 7．图状结构 8．树形结构 9．线性结构 10．n-1 O(n) 11．s->next=p->next; 12．head 13．q->next=p->next; 14．p->next=head; 15．单链表 16．顺序存储链式存储 17．存储结构 18．两个直接后继直接前驱尾结点头结点 19．头结点的指针指向第一个结点的指针 20．链式链表 三、问答题 1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答： 顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间， 数据结构课程平时作业1 一．单项选择题 1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科。 ①A．操作对象B．计算方法C．逻辑存储D．数据映象 ②A．结构B．关系C．运算D．算法 2．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。 ①A．算法B．数据元素C．数据操作D．逻辑结构 ②A．操作B．映象C．存储D．关系 3．在数据结构中，从逻辑上可以把数据结构分成( )。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 4. 线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 5. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 二.填空题（将正确的答案填在相应的空中） 1．在线性结构中，第一个结点①前驱结点，其余每个结点有且只有②个前驱结点；最后一个结点③后续结点，其余每个结点有且只有④个后续结点。 2．在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后续结点可以④。 3．在图形结构中，每个结点的前驱结点数和后续结点数可以①。 4．线性结构中元素之间存在①关系，树形结构中元素之间存在②关系，图形结构中元素之间存在③关系。 5. 数据结构包括数据的、数据的和数据的这三个方面的内容。6．下面程序段的时间复杂度是①。 for（i=0；i＜n；i++） for（j=0；j＜m；j++） A[i][j]=0； 7．下面程序段的时间复杂度是①。 S＝0； 数据结构程序填空题 Last revision date: 13 December 2020. 数据结构程序填空题S设有一个头指针为head的不带头结点单向链表, 且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a（设链表中没有结点的数据域与结点 a的数据域相同）, 写出相关语句 答案 （1）q->next=head;（2）p=p->next;（3）q->next=p->next; 设有一个头指针为head的不带头结点单向链表，p、q是指向链表中结点类型的指针变量，p指向链表中结点a, （设链表中没有结点的数据域与结点a 的数据域相同）,写出相关语句 答案：（1）q->next=head (2) p=p->next; （3）q->next=p->next 设有一个不带头结点的单向链表，头指针为head，p、prep是指向结点类型的指针，该链表在输入信息时不慎把相邻两个结点的信息重复输入，以下程序 段是在该单向链表中查找这相邻两个结点，把该结点的数据域data打印 出来，并把其中之一从链表中删除，填写程序中的空格。 （1）p=p->next;（2）p->data或prep->data（3）p->next 设线性表为（6，10，16，4），以下程序用说明结构变量的方法建立单向链表， 并输出链表中各结点中的数据。 答案：（1）&a（2）（3）p->data（4）p=p->next（5）p!=NULL 设线性表为（16，20，26，24），以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。 答案：（1）p->data（2）p=p->next（3）p!=NULL 设线性表为（1，3，7，5），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。 答：（1）&a（2）d->next=NULL（3）p->data（4）p=p->next（5）P指向NULL X 学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1] 中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标（数组元素的下标）。失败时返回-1，完成程序中的空格。 （1）low<=high（2）mid（3）a[mid].num 数据结构习题 一、名词解释 1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、 算法、时间复杂度、空间复杂度。 2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头 指针、头结点、首元结点（第1个元素结点）。 3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。 4. 树、叶子结点、结点的度、树的度、树的高（深）度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL哈夫曼编码。 5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、 （最小）生成树、邻接矩阵、邻接表、DFS BFSO 6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。 7. 排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2 路归并。 一、填空题 1. 数据结构是研究数据的 _逻辑结构_和—物理结构_ ,并在这种结构上定义相关的运算，设计实 现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为—时间复杂度和空间复杂度—。 2. 数据的基本单位是数据元素，数据的最小单位是数据项。 3. 算法是对特定问题求解—步骤___的一种描述，是指令的有限序列。 4. 一个算法的时间复杂度为（3n3+2n — 7）,其数量级表示为_0 （ n3） __。 5. 一个算法具有5个特性：_确定性、—可行性_、_有穷性_、输入和输出。 6. 算法性能的分析和度量，可以从算法的时间复杂度一和—空间复杂度—来评价算法的优劣。 7. 数据的逻辑结构包括集合结构、_线性结构 _、—树形结构_和_图型结构—四种类型。 8. 数据结构在计算机中的表示称为数据的物理结构，它可以采用 _顺序存储_ 或_链式存储_ 两种存储方法。 9. 线性表有两种存储结构，分别为_顺序存储 _ 和___________ 链式存储_。 10. 链式存储的特点是利用指针—来表示数据元素之间的逻辑关系。 11. 若频繁地对线性表进行插入和删除操作，该线性表宜采用链式存储—存储结构。 12. 线性表中的数据元素之间具有 _一对一_的线性关系，除第一个和最后一个元素外，其他数据元素有且只有 一个_直接后继和直接前趋。 13. 在一个单链表中 P所指结点之后插入一个S所指结点时，应执行 s->next=_ p->next ___________ 和 p->next=_ S ________ 的操作。 中央电大计算机科学与技术专业 数据结构（本科）试卷7 2003年7月已考 一、选择题（每小题1分，共10分） 1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。 A. O(n) B. O(n/2) C. O(1) D. O(n2) 2.带头结点的单链表first为空的判定条件是： A. first == NULL; B. first->link == NULL; C. first->link == first; D. first != NULL; 3.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 4.在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。 A. 空间 B. 副本 C. 返回地址 D. 地址 5.在一棵树中，（）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 6.在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。 A. 2 B. 1 C. 0 D. –1 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长 度为（）的值除以9。 A. 20 B. 18 C. 25 D. 22 8.在有向图中每个顶点的度等于该顶点的（）。 A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差 9.在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于 O(nlog2n)。 A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序 10.当α的值较小时，散列存储通常比其他存储方式具有（）的查找速度。 A. 较慢 B. 较快 C. 相同 二、填空题（每小题1分，共10分） 1.二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或 直接后继）。开放大学数据结构2020年考试必备填空题
电大数据结构(本)形考作业1-阶段性学习测验1答案
数据结构复习题目和答案
数据结构习题及参考答案 .
《数据结构》程序填空复习题
数据结构习题
数据结构试题答案
数据结构课后练习题
数据结构复习题
电大数据结构形成性考核册答案(作业1-4)
2020年国家开放大学电大数据结构题库
数据结构程序填空题
数据结构复习题及答案
中央电大计算机科学与技术专业数据结构(本科)试卷7