数据结构填空

《数据结构填空》由会员分享，可在线阅读，更多相关《数据结构填空（1页珍藏版）》请在金锄头文库上搜索。

1、1. 数据结构研究的三个方面有：数据间的 存储结构、数据间的逻辑结构和在数据上 施加的运算。2. 数据的存储结构可用四种基本的存储方 法表示，它们分别是顺序存储方式、链式 存储方式、索引存方式和散列方式。3. 数组采用顺序存储方式表示是因为通常 不对数组进行插入删除操作。4. 队列的修改是按先进先出一的原则进行 的；栈的修改是按先进后出的原则进行的。5. 数据的逻辑结构在计算机存储器内的表 示，称为数据的存储结构6. 设某双链表的结点形式为prior data next，若要在指针q所指结点(中间结点) 的后面插入一个新结点s，则需执行下述 语句段： sprior=q ； s-next=q-n

2、ext ； q-next-prior=s； qnext=s;7. 串 S=Ioamoaoworker(注: 为一个空 格)的长度是138. 数据的逻辑结构分为有四种，分别是集 合结构、树状结构、网状结构和线性结构9. 下列程序段的时间复杂度为向product =1;for (i = n;i0; i-)for (j = i+1; j next =p - next - next 的作用是 删除P的直接后继结点。21. 假设一个6阶的下三角矩阵B按列优先 顺序压缩存储在一维数组A中，其中A0 存储矩阵的第一个元素b11,则A 14存 储的元素是b63。22. 栈的操作是按先进后出的原则进行的。23.

3、 空串的长度是0；空格串的长度是空格 的个数。24. 如果入栈序列是1，3, 5,，97, 99, 且出栈序列的第一个元素为99,则出栈序 列中第30个元素为4T25. 若一棵满三叉树中含有121个结点，则 该树的深度为5。26. 假设S和X分别表示进栈和出栈操作， 列“ABC得到输出序列“BCA”的操作序列 为 SSXSXX,则由“a*b+c/d”得到“ab*cd/+” 的操作序列为sxssxxssxssxxx28. 栈下溢是指在栈空时进行出栈操作。29. 某二叉树的先根遍历序列是 ABDGCEFH ；中根遍历序列是 DGBAECHF ；则其后根遍历序列是 GDBEHFCA30. 链栈s在进

4、行出栈操作时首先要判断栈 空31. 图的存储结构包括有邻接矩阵和邻接 表32. 在一棵度为3的树中，度为2的结点个 数是1,度为0的结点个数是6,则度为3 的结点个数是233. 将一个n阶对称矩阵的下三角各元素 (包括对角线上的元素)存储在一维数组v 中，则v至少有n(1+n) /2个元素。34. 任意一棵具有n个结点的二叉树，若它 有m个叶子，则该二叉树上度数为1的结 点数n-2m+1个。35. 结点数为20的二叉树可能达到的最大 高度为2026.在单链表中，若在p所指结点前插入 一个新结点，时间复杂度为0(n)37. 引起循环队列队头位置发生变化的操 作是(。，front+1)%maxsi

5、ze38. 树中结点的最大层次称为树的高度。39. 对n个元素进行起泡排序时，最少的比 较次数是n-140. 在n个结点的顺序表中删除一个结点需 平均移动(n-1)/2个结点。41. 在n个结点的顺序表中插入一个结点需 平均移动击个结点。42. 若二叉树中度为2的结点有n个，则度 为0的结点个数为n+1。43. 已知完全二叉树T的第5层只有7个结 点，则该树共11个叶子结点。45 .两个串相等的充分必要条件是两个串 的长度相等且对应位置的字符相同47. 已知substr(s,i,len)函数的功能是返回串 s中第i个字符开始长度为len的子串， strlen(s)函数的功能是返回串s的长度。若

6、 s=”ABCDEFGHIJK”,t=”ABCD”，执行运算 substr(s,strlen(t), strlen(t)后的返 回值为 “DEFG”。48. 去除广义表LS=(a1,a2,a3,.，an)中第 1个元素，由其余元素构成的广义表称为 LS的表尾49. 对关键字序列(50，34，92，19，11，68， 56, 41，79)进行直接插入排序，当将第7 个关键字56插入到当前的有序子表中时， 为寻找插入位置需进行3次关键字之间的 比较。50. 在文本编辑程序中查找某一特定单词 在文本中出现的位置，可以利用串的模式 匹配或子串定位运算。51. 若以邻接矩阵表示有向图，则邻接矩阵 上第i

7、行中非零元素的个数即为顶点vi的 以vi为起始点的个数52. 已知广义表LS为空表，则其深度为153. 假设以行优先顺序存储三维数组 A56，其中元素A00 的地址为1100, 且每个元素占2个存储单元，则A43 的地址是H54O54. 已知一棵二叉树的先序序列为ABCD， 中序序列为BCAD，则它的后序序列为 CBDA。56.在含n个顶点的连通图中，任意两个不 同顶点之间的一条简单路径最多包含n-i 条边。60. 图的遍历包括深度优先遍历和广度优 先遍历61. 假设以行优先顺序将一个n阶的5对角 矩阵压缩存储到一维数组Q中，则数组Q 的大小至少为5-662. 在含100个结点的完全二叉树中，

8、叶子 结点的个数为5063. 广义表LS=(a1,a2,a3,.，an)中第 1 个 元素，称为LS的表头64. 将有序表中n个元素依次插入到一棵空 的二叉排序树中，则在等概率查找的情况 下，该二叉排序树在查找成功时的平均查 找长度是(n+1) /2。66. 在有向图中，以顶点v为起点的弧的数 目称为v的出度67. 对长度为20的有序表进行二分查找的 判定树的高度为568. 已知在一棵含有n个结点的树中，只有度为k的分支结点和度为0的叶子结点， 则该树中含有的叶子结点的数目为n-(n-1/k)69. 在如图所示的链表中，若在指针p所指 的结点之后插入数据域值相继为a和b的 两个结点，则可用下列

9、两个语句实现该操 作，它们 依次是 snextnext=pnext;70. 假设一个10阶的下三角矩阵A按列优 顺序压缩存储在一维数组C中，则C数组 的大小应为5571. 在无向图中，若从顶点a到顶点b存在 路径，则称a与b之间是连通的。72. 已知完全二叉树T的第4层只有3个结 点，则该树共有5个叶子结点。74. 设 S1=good,S2= ,S3=book，则 S1，S2和S3依次联接后的结果是 “good_book75. 在n个结点的线索二叉链表中，有n+1 个线索指针。76. 对关键字序列(50，34，92，19，11，68，56, 41，79)进行直接插入排序，当将第8 个关键字41

10、插入到当前的有序子表中时， 为寻找插入位置需进行5次关键字之间的 比较。81.在队列中，允许进行插入操作的一端称 为队尾，允许进行删除操作的一端称为队 头84. 对于二叉排序树的查找，若根结点元素 的键值大于被查找元素的键值，则应该在 该二叉树的右半区上继续查找。85. 对关键字序列(52, 80，63, 44, 48, 91) 进行一趟快速排序之后得到的结果为【8 44】52【63 80 91】/【44】48 52 63【80 91】 /44 48 52 63 80【91】86. 假设以S和X分别表示进栈和退栈操 作，则对输入序列a,b,c,d,e进行一系列栈 操作SSXSXSSXXX之后，

11、得到的输出序 列为bceda88. 如果在排序前，关键字序列已接近正序 或逆序，则在堆排序和快速排序两者之中， 选用堆排序较为适当。89. 对长度为20的有序表进行二分法查找 的判定树的高度为【log,20】 +1=590. 由10000个结点构成的二叉排序树，在 等概率查找的假设下，查找成功时的平均 查找长度的最大值可能达到50005000。93. 若一个算法中的语句频度之和为 T(n)=3720n+4nlogn，则算法的时间复杂度 为 0 (nlogn)94. 若采用邻接矩阵结构存储具有n个顶点 的图，则对该图进行广度优先遍历的算法 时间复杂度为丽1. 数据结构研究的三个方面有：数据间的

12、存储结构、数据间的逻辑结构和在数据上 施加的运算。2. 数据的存储结构可用四种基本的存储方 法表示，它们分别是顺序存储方式、链式 存储方式、索引存方式和散列方式。3. 数组采用顺序存储方式表示是因为通常 不对数组进行插入删除操作。4. 队列的修改是按先进先出一的原则进行 的；栈的修改是按先进后出的原则进行的。5. 数据的逻辑结构在计算机存储器内的表 示，称为数据的存储结构6. 设某双链表的结点形式为prior datanext，若要在指针q所指结点(中间结点) 的后面插入一个新结点s,则需执行下述 语 句段：sprior=q ； s-next=q-next ； q-next-prior=s； qnext=s;7. 串 S=IamanworkerM(注: 为一个空 格)的长度是138. 数据的逻辑结构分为有四种，分别是集 合结构、树状结构、网状结构和线性结构9. 下列程序段的时间复杂度为丽product = 1;for (i = n;i0; i-)for (j = i+1; j next =p - next - next 的作用是 删除P的直接后继结点。21. 假设一个6阶的下三角矩阵B按列优先 顺序压缩存储在一维数组A中，其中A0 存储矩阵的第一个元素b11,则A 14存 储的元素是拓3。