数据结构填空

16.数据结构由数据的逻辑结构、存储结构和数据的_运算___________三部分组成。17.在单链表中某结点后插入一个新结点，需要修改_______2________个结点指针域的值。18.设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是_______3_________。19.长度为零的串称为______空串__________。20.广义表G=(a,b，(c，d，(e，f))，G)的长度为________4________。21.一棵树T采用孩子兄弟链表存储，如果树T中某个结点为叶子结点，则该结点在二叉链表中所对应的结点一定是______左右指针域均为空__________。22.一个有n个顶点的无向连通图，最少有_____n-1___________条边。23.当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是_______直接插入排序_________。24.在一棵深度为h的具有n个结点的二叉排序树中，查找任一结点的最多比较次数是______h________。25.不定长文件指的是文件的______记录含有的信息长度______大小不固定。16.下面程序段的时间复杂度为____O(n)_______。sum=1；for（i=0；sumn;i++）sum+=1；17.已知链表结点定义如下：typedefstructnode{chardata［16］；structnode*next;}LinkStrNode；如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是____4/5_______。18.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为_____99______。19.3个结点可以组成____5_______种不同树型的二叉树。20.用5个权值{3,2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是____33_______。21.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为____2m_______。22.影响排序效率的两个因素是关键字的____比较_______次数和记录的移动次数。23.对任一m阶的B树，每个结点中最多包含____m-1_______个关键字。24.若两个关键字通过散列函数映射到同一个散列地址，这种现象称为_____冲突______。25.如果要为文件中的每个记录建立一个索引项，则这样建立的索引表称__稠密索引_______。16．数据元素及其关系在计算机存储器内的表示称为__数据的存储结构_______。17．长度为n的线性表采用单链表结构存储时，在等概率情况下查找第i个元素的时间复杂度是___O（n）______。18．下面是在顺序栈上实现的一个栈基本操作，该操作的功能是__取栈顶元素_______。typedefstruct{DataTypedata[100]；inttop；}SeqStack；DataTypef18(SeqStack*S){if(StackEmpty(S))Error(”Stackisempty”)；returnS-data[S-top]；}19．在串匹配中，一般将主串称为目标串，将子串称为____模式串_____。20．已知广义表C=(a(b，c)，d)，则：tail(head(tail(C)))=____（c）_____。21．用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为___219______。22．已知有向图如下所示，其中顶点A到顶点C的最短路径长度是____35_____。23．对序列{55，46，13，05，94，17，42}进行基数排序，第一趟排序后的结果是__{42,13,94,55,05,46,17}_______。24．高度为3的3阶B-树最少的关键字总数是____7_____。25．VSAM通常作为大型索引顺序文件的标准组织，其动态索引结构采用的是____B+树_____。16．数据的链式存储结构的特点是借助___指针_____表示数据元素之间的逻辑关系。17．如果需要对线性表频繁进行___插入_____或____删除____操作，则不宜采用顺序存储结构。18．如图所示，可以利用一个向量空间同时实现两个类型相同的栈。其中栈1为空的条件是top1=0，栈2为空的条件是top2=n-1，则“栈满”的判定条件是__top2+1=top1______。19．静态存储分配的顺序串在进行插入、置换和___链接_____等操作时可能发生越界。20．广义表L=（a，（b，()））的深度为____3____。21．任意一棵完全二叉树中，度为1的结点数最多为____1____。22．求最小生成树的克鲁斯卡尔(Kruskal)算法耗用的时间与图中____边____的数目正相关。23．在5阶B-树中，每个结点至多含4个关键字，除根结点之外，其他结点至少含___2_____个关键字。24．若序列中关键字相同的记录在排序前后的相对次序不变，则称该排序算法是____稳定____的。25．常用的索引顺序文件是____ISAM____文件和___VSAM_____文件。16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的__规模函数_______。17.在双向循环链表中插入一个新的结点时，应修改__4_______个指针域的值。18.若进栈序列为a，b，c，且进栈和出栈可以穿插进行，则可能出现_____5____个不同的出栈序列。19.链串的结点大小定义为结点的___数据域______中存放的字符个数。20.广义表(a，(d，(c)))的深度为____3_____。21.在含有3个结点a，b，c的二叉树中，前序序列为abc且后序序列为cba的二叉树有____4_____棵。22.若用邻接矩阵表示有向图，则顶点i的入度等于矩阵中__第i列的非零个数_______。23.对关键字序列(15，18，11，13，19，16，12，17，10，8)进行增量为5的一趟希尔排序的结果为_15,12,11,10,8,16,18,17,13,19________。24.索引顺序查找的索引表由各分块中的最大关键字及各分块的____起始地址_____构成。25.VSAM文件的实现依赖于操作系统中的___虚拟______存取方法的功能。16.数据的存储结构是其逻辑结构__映像_____。17.输入线性表的n个元素建立带头结点的单链表，其时间复杂度为____O（n）_______。18.假设循环队列的元素存储空间大小为m，队头指针f指向队头元素，队尾指针r指向队尾元素的下一个位置，则在少用一个元素空间的前提下，表示“队满”的条件是____（rear+1）%m=f_______。19.给定串的联接操作函数：char*strcat(char*to,char*from);//将串from联接到串to的末尾，并返回联接后的串若字符串s1=〞point〞,s2=〞of〞,则strcat(s1,strcat)(s2,s1))的操作结果是_____pointofpoint______。20.假设二维数组A[8][10]按行优先顺序存储,若每个元素占2个存储单元,元素A[0][0]的存储地址为100,则元素A[4][5]的存储地址为___190_______。21.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为____499_______。22.已知一个有向网如图所示,从顶点1到顶点4的最短路径长度为_____55______。23.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有____快速排序_______。24.假设散列表的表长为11,散列函数为H(key)=key%7,若用线性探测处理冲突,则探查地址序列hi的计算公式为（H（key）+i-1）___________)10,,2,1(i。25.VSAM文件由__索引集_________，顺序集___________和数据集三部分组成。