数据结构填空总题目

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

2、据元素之间的逻辑关系，也称（数据的逻辑结构）数据的逻辑结构可以形式的用一个二元组B= （ K , R ）来表示，其中K是（结点的有穷集合）R是* （ K上关系的有穷集合）一个数据元素可以有若干个（数据项）组成考虑：如何做；（数据项）是具有独立含义的最小表示单位（数据的运算）既对数据施加的操作（数据的逻辑结构）可以看做是从具体问题抽象出来的数学模型数据元素及其关系在计算机存储；内的表示称为（数据的存取结构）数据的存储结构是逻辑结构用（计算机语言）的实现对机器语言而言，存储结构是具体的。一般至在（高级语言）层 次上讨论存储机构所谓（抽象的操作），是至只知道这些操作是“做什么”，而无需较早的软件开发

3、用结构法层序设计方法。层序的定律是;程序=（算法）+（数据结构）算法是一个独立的整体，数据结构也是一个独立的整体俩者分开 设计以（算法）为主数据结构是介于（数学）（计算机硬件）（计算机软件）三者之间的一门核心课程24.数据的范畴包括（整数）（实数）（字符串）（像）和（声音）25.下面程序的时间复杂度为）（0（ sqrt（ n）Void prime(int n)(for(i=2;(n%i)!=)0&(isqart(n)Printf(d is a prime number”,n);Else print(d is a prime number”,n); 下面程序的时间复杂度为(0( n)Float

4、suml (int n) ( p=1;suml=0; For(i=1;i=n;+i)(p=p*i;suml=suml+p; )27.下面的时间复杂度为(0 ( 2 )Float sum2(int n)( sum2=0;For(i=1;i=n;i+) p=1；For(j=1;jnext= p-next;p-next=s;t=p-data;p-data= s-data(5)s-data= t根据线性表的链式存储结构中每个结点所含指针的个数，链表可分 为（单链表）和（双链表）；而根据指针的联系方式，链表又可分为 （非循环链表）和（循环链表）b 5.对于线性表的顺序存储，需要预先分配好存储空间。若分配

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

6、相邻的元素物理位置（一定）紧邻，单链表中逻 辑上相邻的元素物理位置（不一定）紧邻。如果线性表的存储空间变化较大，则适用（链）表。在链表中，每个结点中含8个字符，1个指针域。其中每个字符 占1个字节，每个指针占4个字节。则该结点的存储密度是（2/3 *当向一个顺序表插入一个元素时，从插入位置开始向后的所有元 素均（后移）一个位置，移动过程是从（后）向（前）依次移动没一 个元素。要从一个顺序表删除一个元素时，被删除元素之后的所有元素均 需（前移）一个位置，移动过程是从（前）向（后）依次移动一个元 素。15在单链表中，若要在指针P所指结点后插入指针S所指结点，则需要执行下列两条语句（s-next=p

7、-next）和（p-next=s *在带有头结点的双链表1中，指针P所指结点是第一个元素结点 的条件是（p=L-next）b在线性表的单链存储中，若一个元素所在结点的地址为P，则其 后继结点的地址为（p-next），若假定P为一数组A中的下标， 则其后继结点的下标为（a【p】-next、在一个带头结点的单循环链表中，P指向尾结点的直接前驱，则指向头结点的指针head可用P表示为head=（ p-next-next既无前驱也没有后继的结点在所在线性表长度为（1）,结点指针 域的值为（空）b在单链表中，除了元结点外，任一结点的存储位置由（其直接前 驱结点的链域的值）指示。静态链表是用（数组）描述的

8、链表。22、循环链表的特点是表中（最后）一个结点的指针域指向（头结点），整个链表形成一个环。23、双向链表的结点中苞质个指针域其一指向（直接后继 ） 另一指向（直接前驱） 24、设P点为结点a的指针，如果要删除a的后一个结点，修改指针的语句为（p-next=p-next-next ）25、在单链表中，任何两个元素的存储位置之间都有固定的联系，因 为可以从（头结点）进行查找任何一个元素 26、链表的每个结点中只包含一个指针域，该链表称为（ 线性链 表）或（单链表） 27、链式存储结构的特点是用一组（任意）的存储单元存储线性 表的数据元素28、在单链表中，若要在指针P所指结点后插入指针s所指结点，

9、 则需要执行下列两条语句，s-next=p-next，（ p-next=s ）29、一个向量第一个元素的存储地址是100，每个元素的长度是2， 则第5个元素的地址是（108 ）30、向顺序表中第i个元素之前插入一个新元素时，首先从（位置 i ）开始向后的所有元素均需（后移）一个位置，接着把新元素 写入（位置i）上，最后使线性表的长度（加1 *从顺序表中删除第 i个元素时，首先把第i个元素赋给（工作单位），接着从（位置i+1） 开始向后，所有元素均（前移），最后使线性表的长度（减1）31、在一个长度为n的顺序表中删除第i个元素，要移动（n-i）个元 素，如果要在第i个元素前插入一个元素，要后移（

10、n+i-1）个元素在双向循环链表中，在p所指的结点之后插入s指针所指的结 点，其操作是S-next=p-next;（p-next-prior ）=s;s-prior=（ p ）;p-next =s;对于一个长度为n的顺序存储的线性表，在表头插入元素的时间 复杂度为（O（n），在表尾插入元素的时间复杂度为（0（1）在双向循环表中，在p所指的结点之后插入指针f所指的结点， 其操作为F-next=p-next;（ p-next-prior=f ）（f-prior=p）。在顺序表中，插入或删除一个元素，需要平均移动（约表长的一 半）个元素，具体移动的元素个数与（该元素在线性表中的位置）有 关在线性表的

11、顺序存储中，元素之间的逻辑关系是通过（物理存储 位置）决定的，在线性表的链接存储中，元素之间的逻辑关系是通过对于一个具有n个结点的单链表中，在已知的结点后插入一个新 结点的时间复杂度为（O（1）在给定值为X的结点后插入一个新结 点的时间复杂度为（O（n）在线性表中，若结构是一个非空集，则第一个结点称为（开始结 点），且此结点（没有）前驱结点，其余各个结点有且仅有（一个前 驱结点），最后一结点称为（终端结点），它（没有）后继结点，其 余各个结点有且仅有1个后继结点只要确定了存储线性表的起始位置，线性表中任何一个数据元素 都可以（随机存取），这个特点也铸成了这种存储结构的弱点，在执 行（插入）和（

12、删除）操作时，需要移动大量元素从一个顺序存储的循环队列中删除一个元素时，应该（先移动队 首指针，反取出元素）若L是splist类型的顺序表，则表中的第 i个数据元素是（Lelemi-1）已知一个顺序存储的线性表，设每个结点需占用m个存储单元， 若第一个结点的地址为di，则第1个结点的地址为（dl+（I-1）*m）第四份：CH03一个栈的输入序列号12345，则栈的输出序列是12345是（可能的）b队列的插入操作在（队尾）进行，删除操作在（对头）进行。栈又称为（后进先出）的表，队列称为（先进先出）的表。设长度为n的链队列用单循环链表表示，若只设头指针，则入队和 出队操作的时间复杂度分别为（O（n

13、）和（0（1）;若只设尾 指针则入队和出对操作的时间复杂度分别为（0（1）和（0（1）6向一个栈顶指针为HS的链中插入一个S所指结点时，则执行（S-next=HS,HS=S;*设S（ 1 ： maxsize）为一个顺序存储的栈，变量top只是栈顶位置， 栈为空的条件是（top=0），栈为满的条件是（top=maxsize ）.向一个顺序栈插入一个元素时，受限使（栈顶指针）后移一个位 置，然后把待插入元素（写入）到这个位置上。从一个栈删除元素时，需要前移一位（栈顶指针*仅允许在表的同一端插入和删除运算的线性表被称为（栈）。设sp（ toplink=top）和（top=p）操作。链队列实际上是一个

14、同时带有头指针和尾指针的单链表，尾指针 指向该单链表的（最后一个结点）。设输入元素的顺序为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）。在栈中存取数据遵从的原则是（后退先出 24、从一个栈顶指针为top的非空链式栈中删除节点并不需要返回 栈顶结点的值和回收结点时，应执行（top=toplink ）操作。25、假定front和rear分别为一个链式队列的对头和队尾

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

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

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

18、sh，push 后，输出序列为（2， 3）,栈顶指针是（ 1003H*38、设有一空栈，现有输入队列12345，经push，push，pop，push， pop，push，push，后，输出队列是（2,339、用数组Q表示一个环形队列，f为当前对头元素的钱一位置，r 为队尾元素的位置。假定队列中元素个数总小于n，求队列中元素个 数公式是（r-f+n ） %n ）。40、用循环链表表示的队列长度为n ,若只设头指针，则出对和入对 的时间复杂度分别是（0（ 1）和（0（ n）;若只设尾指针，则出队 和入队的时间复杂度分别是（0（n）和（0（1 ）b41、向栈中压入元素的操作是（先移动栈顶指针，后存

19、入元素*42、向栈进行出栈时的操作是（先取出元素，后移动栈顶指针*43、在一个循环队列中，队首指针指向对周元素的（前一个位置*44、从循环队列中删除一个元素时，其操作是（先移动队首指针，后 取出位置）b45、假设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 B1、 空串是 零个字符的串，其长度等于 。2

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

21、储地址是200，则A612的地址是200+(6x20+12 ) x1 o13、有一个10阶对称矩阵A,采用压缩存储方式(以行序列为主存储，且 A00=1 )，则 A85的地址是 42 o14、 串的逻辑结构和线性表极为相似，区别在于串的数据对象约束 o15、串的基本操作中，通常以串的整体 为操作对象。16、 广义表(a),( b),c),(d)的表头是(a)，表尾是(b),c)(d) o17、 广义表(a )( b),c),(d)的长度是 ，深度是4。18、子串的定操作通常称为串的堕式匹。19、由零个或多个字符组成的有限序列，称为。20、通常称字符在序列中的序号为该字符在串中的芷。21、两个字

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

23、串P= abaabcac ”的next函数值序列为01122312 o27、数组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、其非零元素较零元素少，且分布没有一定规律的矩阵，称为S

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

25、两种存储方式即以行序为主序的存储方式和一 HYPERLINK l bookmark206 o Current Document 列序为主序的存储方式。38、三元组顺序标又称有序的双下标法，它的特点是非零元素在表中按行序有序存储。39、设广义表 L=(),(),则 Head ( L )是 Head(L)=0 ; Tail(L )是Tail(L)=(0); L的长度是 ，深度是 。设高度为h的二叉树上只有度为0和度为2的结点，则此类二 叉树中所包含的结点数至少为鲍已知某二叉树的后序遍历为dabcc，中序遍历为debac，则它 的前序遍历为 cedba如果t2是出有序树t转换而来的二叉树，那么t中的

26、结点的前序就是 t2 结点中的前序。如果t2是由序树t转换而来的二叉树，那么t中的结点的后序 就是些=_结点中的中序。某二叉树的前序遍历结点顺序为abdgcefg，中序遍历结点顺序为dgbacchf，则后序遍历的结点顺序为_ gdbehfca按照二叉树的定义，具有3个结点的二叉树有_二种深度为5的二叉树至多以有_二史二个结点树最适合用来表示元素之间具有二分支层次关系二的数据任何一颗二叉树的叶结点在前序，中序，后序遍历中的相对次序不发生改变在一非空二叉树的中，根结点的右边只有_查型=_上的 所有结点实现任意二叉树的后序遍历的非递归算法而不适用栈结构，最 佳的二叉树方法是采用三叉列表的存储结构如果

27、某二叉树的前序为stuwv,中序为uwtvs，那么二叉 树的后序为_wuvts具有五层结点的二叉树平衡树至少有_个结点线索二叉树是一种二物理二结构设n m为一棵二叉树上的两个结点，在中序遍历中，n在m 的前面的条件是_ n在m的上方_二叉树按照某种线索化后，任意结点均有指向其前驱和后继的 线索，这种说法是错误的=_二叉树的前序遍历中，任意 一个结点均处于其子女结点的前面，这种说法是二正确的由于二叉树中每个结点的度最大为2 ,所以二叉树是一种特殊的树，这种说法是二错误的设F是一个森林，B是由F转换得到的二叉树，F中有n个非 终端结点，则b中有指针域为空的结点有_n+1 个对于二个具有a个结点的二

28、又树.当它为一裸_完成二_二 叉树时具有最小高度，即为【log2n】+1 _.当它为一裸单支树具有二最大._高度.即为_ n在二叉搜素排序树上进行搜索查找时.其时间复杂度为o(logN ) _进行侧除时其时间复杂度为_o (log n ) _山带权为3, ,、6,2,5的5个叶子结点构成一裸哈夫爱树.则带 权路径长度为 55在一裸二叉排序树上按_中班_遍历得到的结点序列是 一个有序序列。25对于一裸具有n个结点的二又树.当进行链接存储时.其二又 链表中的指针城的总数为四二_个.其中(n-1 )个用于链接孩子结点二n+1一个 空闲着。26.在一操二叉树中.度为0的结点个数为no.度为2的结点个数

29、为 n2 则 n0=n2+127在具有”个结点的二叉排序树上播人一个新结点时.其时间复 杂度大致 o(log2n)为，n个数据元众生成一裸二又排序树时，其时间复杂度大致为(O (log2n )已知8个数据元素由(35,75,40,15,20,55,95,65 )按照依次搔入结 点的方法生成一裸二叉排序树后.最后两层上的结点总数史 2_由a, b, c三个结点构成的二叉树.共有二5 种不同结构。30假定一裸三叉树的结点放为50,则它的最小高度为_ 5 31 ,在一裸二叉树上的第5层的结点数最多为1632.由带权为，9、2. 5,7，的四个叶子结点构造一裸哈夫曼树.该树 的带权路径长度为_44 3

30、3假定在一操二又树中.双分支结点数为15.单分支结点致为30个. 则叶子结点数为_16 在一裸度为3的树中.度为3的结点数为2个 度为2的结点数为. 个。度为.的结点数为2个.则度为0的结点数为 6个，假定一裸树的广义表表示为A(B(E),C(F(H,I,J),G),D), (Il该树的 深度为 4 有12个结点的平衡二叉树的最大深度是5设森林F中有三裸树，第一、第二和第只裸树的结点个数分别为 ml, m2, m3.则与森林F对应的二又树根结点的右子树I.的结点个致 是_ m2+m3 。若二又树采用的是二又链表存储结构.要交换其所有分支结点左 右子树的位置利用中序 遍历方斌最合适。在计算递归曲

31、数时，如不使用递归过程.则一般悄况下必须借 助于_栈 数据结构。40树(及一切树形结构)是一种二分支层次“结构，在树 上根_结点没有育接晌驭，对树上任一结点x来说.x是它的任一子树 的根结点惟一的直接前驱。一裸树上的任何结点(不包括根本身)称为根的二子孙。若 B是A的子孙.则称A是B的_祖先一般的二又树有 空 二又树、只含根 的二叉树、只有_ 非空左子树 的二又树，只有非空右子树二的二叉树、同时有 非空左右子树 的二又树五种幕本形态：43二又树第i (i=1)层上至多有2t-1 个结点。44.深度为k(k=1 )的二叉树至多有2k-1 个结点.45对任何二又树.若度为2的结点数为n2:，则叶子

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

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