数据结构填空总题目

1、 1. 一个算法应该具有以下几个五个特征：（有穷性）（确定性）（输入）（输出）（可行性）2. 算法的复杂度有（时间）和（空间）之分3. 数据结构指的是数据之间的相互关系，既数据的组织形式，一般包括三个方面的内容（逻辑结构）（存储结构）（数据的运算）4. （数据元素）是数据的基本单位5. （算法的复杂度）是算法效率的度量，是评价算法优势的重要依据6. （结构）是元素之间的关系的集合7. 通常来说，一个数据结构的DS可以表示为一个（二元组）8. 最常用的数据结构是（数组结构）和（记录结构）9. 算法设计策略有（递归技术）（分治法）（模拟法）（贪心算法）（随机算法）（动态规划）（状态空间）（搜索法）

2、10. 现实世界中的事物及联系在数据世界中用（数据模型）描述11. 数据元素之间的逻辑关系，也称（数据的逻辑结构）12. 数据的逻辑结构可以形式的用一个二元组B=（K，R）来表示，其中K是（结点的有穷集合）R是*（K上关系的有穷集合）13. 一个数据元素可以有若干个（数据项）组成考虑：如何做；14. （数据项）是具有独立含义的最小表示单位15. （数据的运算）既对数据施加的操作16. (数据的逻辑结构)可以看做是从具体问题抽象出来的数学模型17. 数据元素及其关系在计算机存储；内的表示称为（数据的存取结构）18. 数据的存储结构是逻辑结构用（计算机语言）的实现19. 对机器语言而言，存储结构是

3、具体的。一般至在（高级语言）层次上讨论存储机构20. 所谓（抽象的操作），是至只知道这些操作是“做什么”，而无需21. 较早的软件开发用结构法层序设计方法。层序的定律是;程序=（算法）+（数据结构）22. 算法是一个独立的整体，数据结构也是一个独立的整体俩者分开设计以（算法）为主；23. 数据结构是介于（数学）（计算机硬件）（计算机软件）三者之间的一门核心课程24. 数据的范畴包括（整数）（实数）（字符串）（图像）和（声音）25. 下面程序的时间复杂度为）（0（sqrt（n） Void prime(int n) for(i=2;(n%i)!=)0&(isqart(n)Printf(“%d is

4、 a prime number”,n); Else print(“%d is a prime number”,n); 26. 下面程序的时间复杂度为（0（n） Float suml (int n) p=1;suml=0;For(i=1;i=n;+i) p=p*i;suml=suml+p; 27. 下面的时间复杂度为（0（n2） Float sum2(int n) sum2=0; Fori=1;i=n;i+) p=1;For(j=1;jnext= p-next ; (2) p-next=s;(3)t=p-data;(4)p-data= s-data ;(5)s-data= t ; 4.根据线性表

5、的链式存储结构中每个结点所含指针的个数，链表可分为（单链表）和（双链表）；而根据指针的联系方式，链表又可分为（非循环链表）和（循环链表）。5.对于线性表的顺序存储，需要预先分配好存储空间。若分配太多容易造成存储空间的（浪费），若分配太少又容易在算法中造成（上溢），因而只适用于数据量变化不大的情况；对于线性表的链接存储，不需要（预先分配）存储空间，存储器中的整个（空间）都可供使用，分配和回收结点都非常方便，能有效的利用存储空间，在算法中不必考虑（上溢）的发生，因而适用于数据量变化较大的情况。7.（双向）链表适合从指点结点开始，寻找直接前趋的运算。8.当一个线性表经常进行存取操作而很少进行插入和删

6、除操作时，则采用（顺序）存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用（链接）存储结构为宜。9.在单链表中设置头结点的作用是（使空表和非空表统一，算法处理一致）。10.顺序表中逻辑上相邻的元素物理位置（一定）紧邻，单链表中逻辑上相邻的元素物理位置（不一定）紧邻。11.如果线性表的存储空间变化较大，则适用（链）表。12.在链表中，每个结点中含8个字符，1个指针域。其中每个字符占1个字节，每个指针占4个字节。则该结点的存储密度是（2/3）。13.当向一个顺序表插入一个元素时，从插入位置开始向后的所有元素均（后移）一个位置，移动过程是从（后）向（前）依次移动没一个元素。14.要从一个顺序

7、表删除一个元素时，被删除元素之后的所有元素均需（前移）一个位置，移动过程是从（前）向（后）依次移动一个元素。15在单链表中，若要在指针P所指结点后插入指针S所指结点，则需要执行下列两条语句（s-next=p-next）和（p-next=s）。16. 在带有头结点的双链表1中，指针P所指结点是第一个元素结点的条件是（p=L-next）。17. 在线性表的单链存储中，若一个元素所在结点的地址为P，则其后继结点的地址为（p-next），若假定P为一个数组A中的下标，则其后继结点的下标为（a【p】-next）。18. 在一个带头结点的单循环链表中，P指向尾结点的直接前驱，则指向头结点的指针head可用

8、P表示为head=（p-next-next）。19. 既无前驱也没有后继的结点在所在线性表长度为（1），结点指针域的值为（空）。20. 在单链表中，除了元结点外，任一结点的存储位置由（其直接前驱结点的链域的值）指示。21. 静态链表是用（数组）描述的链表。22、 循环链表的特点是表中（最后 ）一个结点的指针域指向（ 头结点 ），整个链表形成一个环。23、 双向链表的结点中有（ 质 ）个指针域，其一指向（ 直接后继 ），另一指向（ 直接前驱 ）24、 设P点为结点a的指针，如果要删除a的后一个结点，修改指针的语句为（ p-next=p-next-next ）25、 在单链表中，任何两个元素的存储

9、位置之间都有固定的联系，因为可以从（ 头结点 ）进行查找任何一个元素26、 链表的每个结点中只包含一个指针域，该链表称为（ 线性链表 ）或（ 单链表 ）27、 链式存储结构的特点是用一组（ 任意 ）的存储单元存储线性表的数据元素28、 在单链表中，若要在指针P所指结点后插入指针s所指结点，则需要执行下列两条语句，s-next=p-next，（ p-next=s ）29、 一个向量第一个元素的存储地址是100，每个元素的长度是2，则第5个元素的地址是（ 108 ）30、 向顺序表中第i个元素之前插入一个新元素时，首先从（ 位置i ）开始向后的所有元素均需（ 后移 ）一个位置，接着把新元素写入（位

10、置i）上，最后使线性表的长度（加1）。从顺序表中删除第i个元素时，首先把第i个元素赋给（工作单位），接着从（位置i+1）开始向后，所有元素均（前移），最后使线性表的长度（减1）31、 在一个长度为n的顺序表中删除第i个元素，要移动（n-i）个元素，如果要在第i个元素前插入一个元素，要后移（n+i-1）个元素32、 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是S-next=p-next;(p-next-prior )=s;s-prior=( p );p-next=s;33. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（O(n)），在表尾插入元素的时间复

11、杂度为（ O(1) ）34. 在双向循环表中，在p所指的结点之后插入指针f所指的结点，其操作为 F-next=p-next;( p-next-prior=f )( f-prior=p )。35. 在顺序表中，插入或删除一个元素，需要平均移动（约表长的一半）个元素，具体移动的元素个数与（该元素在线性表中的位置）有关36. 在线性表的顺序存储中，元素之间的逻辑关系是通过（物理存储位置）决定的，在线性表的链接存储中，元素之间的逻辑关系是通过（链域的指针）决定的37. 对于一个具有n个结点的单链表中，在已知的结点后插入一个新结点的时间复杂度为（O(1) ）在给定值为X的结点后插入一个新结点的时间复杂度

12、为（O（n）38. 在线性表中，若结构是一个非空集，则第一个结点称为（开始结点），且此结点（没有）前驱结点，其余各个结点有且仅有（一个前驱结点），最后一个结点称为（终端结点），它（没有）后继结点，其余各个结点有且仅有1个后继结点39. 只要确定了存储线性表的起始位置，线性表中任何一个数据元素都可以（随机存取），这个特点也铸成了这种存储结构的弱点，在执行（插入）和（删除）操作时，需要移动大量元素40. 从一个顺序存储的循环队列中删除一个元素时，应该（先移动队首指针，反取出元素）41. 若L是splist类型的顺序表，则表中的第i个数据元素是（Lelemi-1）42. 已知一个顺序存储的线性表，设

13、每个结点需占用m个存储单元，若第一个结点的地址为d1，则第1个结点的地址为（dl+(I-1)*m）第四份：CH031. 一个栈的输入序列号12345，则栈的输出序列是12345是（可能的）。2. 队列的插入操作在（队尾）进行，删除操作在（对头）进行。3. 栈又称为（后进先出）的表，队列称为（先进先出）的表。4. 设长度为n的链队列用单循环链表表示，若只设头指针，则入队和出队操作的时间复杂度分别为（ O(n） ）和（ O(1) ）；若只设尾指针，则入队和出对操作的时间复杂度分别为（ O(1) ）和（ O(1) ）。5. 向一个栈顶指针为HS的链中插入一个S所指结点时，则执行（ S-next=HS

14、,HS=S; ）。6. 设S（1：maxsize）为一个顺序存储的栈，变量top只是栈顶位置，栈为空的条件是（ top=0 ），栈为满的条件是（ top=maxsize ).7. 向一个顺序栈插入一个元素时，受限使（ 栈顶指针 ）后移一个位置，然后把待插入元素（ 写入 ）到这个位置上。8. 从一个栈删除元素时，需要前移一位（ 栈顶指针 ）。9. 仅允许在表的同一端插入和删除运算的线性表被称为（ 栈 )。10. 设sp（toplink=top ）和（ top=p ）操作。21. 链队列实际上是一个同时带有头指针和尾指针的单链表，尾指针指向该单链表的（ 最后一个结点 )。22. 设输入元素的顺序为

15、1,2,3,4,5，要在栈S的输出端得到序列4.3.5.2.1，则进行的操作用栈的基本运算表示应为push(S,1)，push(S,2),push(S,3),push(S,4),pop（S），( pop(s),push(s,5) ），pop(S)，pop（S），pop(S)。23. 在栈中存取数据遵从的原则是（ 后退先出 ）。24、 从一个栈顶指针为top的非空链式栈中删除节点并不需要返回栈顶结点的值和回收结点时，应执行（ top=toplink）操作。25、 假定front和rear分别为一个链式队列的对头和队尾指针，则链式队列中只有一个结点的条件为（front=rear&front！=NU

16、LL）。26、 在一个循环队列中，队首指针指向队首元素的（前一个位置）；从循环队列中删除一个元素时，其操作是先取出队首元素，后（移动队首指针）；在具有n个单元的循环队列中，队满时共有（n-1）个元素。27、 设有一个顺序栈S，元素s1，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2,s3,s6,s5,s1则顺序栈的容量至少应为（3）。28、 假设以数组Qm存放循环队列中的元素，同时以rear和length分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对空条件为（length=0）。29、 中缀表达式3*（X+2）-5所对应的后缀表达式为（3*2+*5

17、）。30、 后缀表达式45*32+-的值为（15）。31、 假设以数组Qm存放循环队列中的元素，同时以rear和length分别只是循环队列中的队尾位置和队列中的所含元素的个数，则该循环的队列的对满条件为（length=Maxsize）。32、 栈的存储结构有（顺序栈）和（链栈）。33、 栈的特点（后进先出），队列的特点是（先进先出），栈和队列的特点是（操作受限的线性表）。34、 设栈S和队列Q的初始状态为空，元素a.b.c.d.e.f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是bdcfea.则栈S的容量至少应是（3）。35、 一个队伍的入队列是1234，则队列的输出顺

18、序是（1、2、3、4）。36、 对于一个栈做进栈运算时，应先判断栈是否为（栈满），做出栈运算时，应先判断别栈是否（栈空），当栈中元素为m时，做栈运算时发生上溢，则说明栈的可用最大容量为（m）。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的（栈底）分别设在这片内存空间的两端，这样只有当（两栈和栈顶空间的某一个位置）时才发生上溢。37、 设有一个空栈，栈顶指针为1000H，现有输入序列为12345，push，push，pop，push，pop，push，push后，输出序列为（2，3），栈顶指针是（1003H）。38、 设有一空栈，现有输入队列1234

19、5，经push，push，pop，push，pop，push，push，后，输出队列是（2,3）。39、 用数组Q表示一个环形队列，f为当前对头元素的钱一位置，r为队尾元素的位置。假定队列中元素个数总小于n，求队列中元素个数公式是（r-f+n）%n）。40、 用循环链表表示的队列长度为n，若只设头指针，则出对和入对的时间复杂度分别是（0（1）和（0（n）；若只设尾指针，则出队和入队的时间复杂度分别是（0（n）和（0（1）。41、 向栈中压入元素的操作是（先移动栈顶指针，后存入元素）。42、 向栈进行出栈时的操作是（先取出元素，后移动栈顶指针）。43、 在一个循环队列中，队首指针指向对周元素的（

20、前一个位置）。44、 从循环队列中删除一个元素时，其操作是（先移动队首指针，后取出位置）。45、 假设Q1,10是一个循环队列，初始状态为front=rear=1，若做完debgh入队和de出队的操作后，rear=（6），front=(3).46、 在具有n个单元的循环队列中，队满时共有（n-1）个元素。47、 将f=1+1/2+1/3+.+1/n转化成速递归函数，其递归出口是（f（1）=1）递归体是（f（n）=f（n-1）+1/n）。1、 空串是 零个字符的串 ，其长度等于 零 。2、 空格串是 有一个或多个空格组成的串 ，其长度等于 串空格字符的个数 。3、 数组的长度是 数组的元素个数

21、。4、 空串与空格串的区别在于 空串的长度为零，而空格串的长度不为零 。5、 两个字符相等的充分必要条件是 长度相等 。6、 串的两种最基本的存储方式是 顺序存储方式和链接存储方式 。7、 两个串相等的充分必要条件是 两个串的长度相等且对应位置的字符相同 。8、 串中任意个连续相等的字符组成的子序列称为 子串 。9、 包含子串的串相应地称为 主串 。10、 当且仅当两个串的值相等，称两个串 相等 。11、 常对数组进行的操作是 查找和修改 。12、 二维数组A1020采用列序为主方式存储，每个元素占一个存储单元，并且A00的存储地址是200，则A612的地址是 200+（6x20+12）x1

22、。13、 有一个10阶对称矩阵A，采用压缩存储方式（以行序列为主存储，且A00=1），则A85的地址是 42 。14、 串的逻辑结构和线性表极为相似，区别在于 串的数据对象约束 。15、 串的基本操作中，通常以 串的整体 为操作对象。16、 广义表（a），（b），c），（d）的表头是 (a) ，表尾是 (b)，c），（d）) 。17、 广义表（a），（b），c），（d）的长度是 3 ，深度是 4 。18、 子串的定操作通常称为串的 模式匹配 。19、 由零个或多个字符组成的有限序列，称为 串 。20、 通常称字符在序列中的序号为该字符在串中的 位置 。21、 两个字符串S1和S2的长度分别为m

23、和n，求这两个字符串最大共同子串的时间复杂度为T（m，n），这最优的时间复杂度为 O(m*n) 。22、 广义表（a，（a，b），d，e，（i，j），k）的长度是5 ，深度是 3 。23、 稀疏矩阵一般的压缩存储方式是 三元组和十字链表 。24、 二位数组A10.205.10采用行序为主方式存储，每个元素占4个存储单元，并且A105的存储地址是1000，则A189的地址是 1208 。25、 二维数组Amn采用行序为主方式存储，每个元素占k个存储单位，并且第一个元素的存储地址是LOC（A00），则Aij的地址是 Loc(A00)+(n*i+j)*k 。26、 写出模式串P=“abaabcac”

24、的next函数值序列为 。27、 数组A-2.5,2.8,1.8以行序存储，设第一个元素的首地址是54，每个元素的长度为5，则元素A0，6，5的存储首址为 319 。28、 设n行n列的下三角矩阵A已压缩到一维数组S1.n*（n+1）/2中，若按行序为主存储，则Aij对应的S中的存储位置是 i*(i+1)/2+j+1 。29、 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A85的起始地址为SA+222 。30、 其非零元素较零元素少，且分布没有一定规律的矩阵，称为SA+180 。31、 数组A中，每个元素

25、A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是 稀疏矩阵 。32、 广义表的表尾总是一个 240 。33、 设按低下标优先存储整数数组A9358时，第一个元素的字节地址是100，每个整数占4个字节，a3125的存储地址是 1784 。34、 假如值相同的元素或零元素在矩阵中的分布有一定规律，称为 特殊矩阵 。35、 为多个值相同的元素分配一个存储空间；对零元素不分配空间，称为 压缩存储 。36、 广义表的深度定义为 广义表中括弧的重数 ，是广义表的一种量度。37、 二维数组可有两种存储方式即 以行序为主序的存储方式和一

26、列序为主序的存储方式 。38、 三元组顺序标又称有序的双下标法，它的特点是 非零元素在表中按行序有序存储 。39、 设广义表L=（），（），则Head（L）是 Head(L)=0 ；Tail（L）是 Tail(L)=(0) ；L的长度是 2 ，深度是 2 。1. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为2h-12. 已知某二叉树的后序遍历为dabcc，中序遍历为debac，则它的前序遍历为cedba3. 如果t2是出有序树t转换而来的二叉树，那么t中的结点的前序就是t2结点中的前序。4. 如果t2是由序树t转换而来的二叉树，那么t中的结点的后序就是t2结

27、点中的中序。5. 某二叉树的前序遍历结点顺序为abdgcefg，中序遍历结点顺序为dgbacchf，则后序遍历的结点顺序为gdbehfca6. 按照二叉树的定义，具有个结点的二叉树有5种7. 深度为的二叉树至多以有31个结点8. 树最适合用来表示元素之间具有分支层次关系的数据9. 任何一颗二叉树的叶结点在前序，中序，后序遍历中的相对次序不发生改变10. 在一非空二叉树的中，根结点的右边只有右子树上的所有结点11. 实现任意二叉树的后序遍历的非递归算法而不适用栈结构，最佳的二叉树方法是采用三叉列表的存储结构12. 如果某二叉树的前序为，中序为uwtvs，那么二叉树的后序为wuvts13. 具有五

28、层结点的二叉树平衡树至少有15个结点14. 线索二叉树是一种物理结构15. 设n m 为一棵二叉树上的两个结点，在中序遍历中，n在m的前面的条件是n在m的上方16. 二叉树按照某种线索化后，任意结点均有指向其前驱和后继的线索，这种说法是错误的二叉树的前序遍历中，任意一个结点均处于其子女结点的前面，这种说法是正确的17. 由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法是错误的18. 设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中有指针域为空的结点有n+1个 21.对于二个具有a个结点的二又树.当它为一裸完成二叉树时具有最小高度，即为【log2n】+1

29、.当它为一裸单支树具有最大.高度.即为_n 22.在二叉搜素排序树上进行搜索查找时.其时间复杂度为o（logN）进行侧除时，其时间复杂度为o（logn） 23.山带权为3,，、6,2,5的5个叶子结点构成一裸哈夫爱树.则带权路径长度为5524.在一裸二叉排序树上按中序遍历得到的结点序列是一个有序序列。25 对于一裸具有n个结点的二又树.当进行链接存储时.其二又链表中的指针城的总数为2n个.其中（n-1）个用于链接孩子结点n+1个空闲着。26.在一操二叉树中.度为0的结点个数为no.度为2的结点个数为n2则n0=n2+127在具有”个结点的二叉排序树上播人一个新结点时.其时间复杂度大致o（log

30、2n）为，n个数据元众生成一裸二又排序树时，其时间复杂度大致为（O（log2n）28.已知8个数据元素由( 35,75,40,15,20,55,95,65 )按照依次搔入结点的方法生成一裸二叉排序树后.最后两层上的结点总数为 2_ 29.由a, b, c三个结点构成的二叉树.共有_ 5 种不同结构。30假定一裸三叉树的结点放为50,则它的最小高度为 5 31，在一裸二叉树上的第5层的结点数最多为_ 16 32.由带权为，9、2. 5,7，的四个叶子结点构造一裸哈夫曼树.该树的带权路径长度为 44 33假定在一操二又树中.双分支结点数为15.单分支结点致为30个.则叶子结点数为 16 34.在一

31、裸度为3的树中.度为3的结点数为2个，度为2的结点数为.个。度为.的结点数为2个.则度为0的结点数为 6 个， 35.假定一裸树的广义表表示为A(B(E),C(F(H,I,J),G),D), (Il该树的深度为 4 36. 有12个结点的平衡二叉树的最大深度是 5 37.设森林F中有三裸树，第一、第二和第只裸树的结点个数分别为ml, m2, m3.则与森林F对应的二又树根结点的右子树I.的结点个致是_ m2+m3 。 38.若二又树采用的是二又链表存储结构.要交换其所有分支结点左右子树的位置利用_中序 遍历方斌最合适。39.在计算递归曲数时，如不使用递归过程.则一般悄况下必须借助于 栈 数据结

32、构。 40树(及一切树形结构)是一种“_ 分支层次 “结构，在树上根_结点没有育接晌驭，对树上任一结点x来说.x是它的任一子树的根结点惟一的_直接前驱 。 41.一裸树上的任何结点(不包括根本身)称为根的_子孙 。若B是A的子孙.则称A是B的 祖先 42.一般的.二又树有 空 二又树、 只含根 的二叉树、只有 非空左子树 的二又树，只有 非空右子树 _的二叉树、同时有 非空左右子树 的二又树五种幕本形态: 43.二又树第i (i=1）层上至多有 2t-1 个结点。 44.深度为k(k=1)的二叉树至多有 2k-1 个结点. 45对任何二又树.若度为2的结点数为n2:，则叶子数n0= n2+1

33、46满二叉树卜各层的结点数以达到了二叉树可以容纳的 最大值 。满二叉树也是_完全 二又树.但反之不然。 47.具有n个结点的完全二又树的深度为_（log2n）+1 。48.如果将一裸有n个结点的完全二X树按层编号.则对任一编号为i(1=i1,则x的双亲PARENT(X)的编号为 Floor（i/2） (2)若2in.则结点x无 左孩子 且无 右孩子 ;否则。x的左孩子LC)iILD(X)的编号为 2i (3)若2i+1n。.则结点x无_ 右孩子 否则.x的右孩子RCHILD(X)的编号为 2i+1 49.二叉树通常有 顺序 存储结构和 链式 存储结构两类存储结构。50.每个二叉链表的访问只能从

34、 根 结点的指针.该指针几有标识二叉链表的作用。51.对二叉链表的访问只能从 根 指针开始.若二叉树为空， 则 root =NULL,1. 有向图G用邻接矩阵A1。n，1。n存储，其第一列的所有元素之和等于顶点1的（入度）。2. 在一个有向图中，所有顶点入度之和等于所有顶点出度之和的（1）倍。3. 对于含有N个顶点E条边的无向连通图，利用Kruskal算法生成最小代价生成树的时间复杂度为（o（elg0）。4. 设G为具有N个顶点的无向连通图，则G至少有（N-1）条边。5. 一棵有N个顶点的生成树有且仅有（N-1）条边。6. 若连通网络上各边的权值均不相同，则该图的最小生成树有（1）棵。7. 不存在拓扑序列的（有向图）是图中存在回路。8. 已知一个图的邻接矩阵表示，删除所有从第一个节点出发的边的方法是（将矩阵第一行全部置为0）.9. 对于一个图G，若边集E（G）为有向边的集合，则该图为（有向图）。10. 对于一个图G，若边集E（G）为无向边的集合，则该图为（无向图）。11. 在一个无向图中，若存在一条边,则称Vi和Vj为该边的两个端点，并称他们互为（邻接点）。12. 对于有向图，顶点V的度分为（入度和出度）。1