华师网络学院作业答案-数据结构填空题

在无头结点的双链表中，指针P所指结点是第一个结点的条件是____。答案:p-prior==NULL某无向图有28条边，则其顶点数最少为____。答案:8在顺序表中做插入操作时首先检查____。答案:上溢或表满查找表的逻辑结构是____。答案:集合运算定义在逻辑结构上，算法定义在____结构上；运算指出“做什么”，算法指出____。答案:储存；怎么做深度为k的二叉树，叶子数至多为____，叶子数至少为____。答案:2k-1、1数组A[1..8][1..10]中，每个元素占3个单元，从首地址SA开始存放，若该数组按列存放，则元素A[8][5]的地址是____答案:SA+117在150个结点的有序表中二分法查找，不论成功与否，键值比较次数最多为____。答案:8下面程序段的时间复杂性为____。for(i=0;in;i++)for(j=0;j10;j++)A[i][j]=0；答案:O(n)带头结点的单链表L为空的判定条件是____。答案:L-next==NULLn(≥1)个顶点的强连通图至少____条边，最多____条边。答案:n、n(n-1)排序算法的稳定性是指____。答案:对相同关键字排序前后相对位置不变对400个结点的完全二叉树，度为1的结点数为____。答案:0算法满足的五个重要特性是：____、____、____、输入、输出；其中区别于程序的地方是____。答案:有穷性、确定性、可行性；有穷性。散列表中要解决的两个主要问题是：____、____。答案:散列函数的构造、冲突的处理设循环链队列的长度为n，若只设尾指针，则出队和入队的时间复杂度分别是____和____。答案:O(1)、O(1)头指针为F、尾指针为R、带头结点的链队列为空的条件是____。答案:R==F在带头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：____；L-next=p-next；deletep；答案:p=L-next在邻接矩阵和邻接表上对图进行BFS或DFS遍历时，时间复杂性分别为____、____。答案:O(n2)、O(n+e)图的DFS遍历类似树的____遍历，是其推广。答案:先根树的三种主要的遍历方法是：____、____和层次遍历。答案:先根、后根n个结点的二叉链表中，指针总数为____个，其中____个指针为空。答案:2n、n+1对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为____，在查找不成功时的平均查找长度为____。答案:50/2、100(或101)从n个结点的二叉排序树中查找一个元素，平均时间复杂性大致为____。答案:O(log2n)对广义表L=((a,b),c,d)进行操作head(tail(L))的结果是：____。答案:c非空单循环链表L中结点*p是尾结点的条件是____。答案:p-next==L对n个顶点和e条边的无向图，采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂性分别为____和____。答案:O(n)、O(e/n)n个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。答案:2(n-1)某二叉树中双分支结点数为5个，单分支结点数为4个，则叶子结点数为____个。答案:6下面程序段的时间复杂度为____。y=n;while(y1)y=y/2;答案:O(log2n)散列表既是一种____方式又是一种____方法。答案:储存、查找稀疏矩阵的三元组表示中，三元组是指非零元素的____、____和____三项。答案:行号、列号、值下图所示带权无向图的最小生成树的权为____。答案:17串The含有的子串个数为____。答案:7对广义表((x),(a,b))，长度是____，深度是____。答案:2、2在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作____。答案:储存密度可以将排序算法分为：插入排序、____、选择排序、____、分配排序。答案:交换排序、归并排序所有基于比较的排序方法，平均时间复杂性最好时为____。答案:O(nlog2n)n个顶点的无向图，最少有____条边，最多有____条边。答案:0、n(n-1)/2散列表的冲突处理方法有____和____两种，对应的散列表分别称为开散列表和闭散列表。答案:开放地址法、链地址法(或拉链法)对100个结点的树，所有结点的度数之和为____。答案:99线索二叉树中，线索的含义是____。答案:某种遍历的前趋或后继信息两个串相等的充分必要条件是两个串的长度相等且____。答案:对应字符相同希尔排序的增量序列中，最后一个增量为____。答案:1以行优先存储的一维数组A[1..10]，每个元素占4字节，A[5]的地址是1020，则数组的首地址是____。答案:1004评价排序效率的主要标准是____。答案:关键字比较次数、移动次数某树所有结点的度数之和为100，则树中边数为____。答案:100“就地排序”是指排序算法辅助空间的复杂度为____。答案:O(1)个顶点的连通图至少____条边，最多____条边。答案:n-1、n(n-1)/2在深度为7的二叉树中，第5层上的结点数最少为____，最多为____。答案:1、16程序设计的实质是：数据的表示和____，或者说，程序=数据结构＋____。答案:数据的处理；算法设循环队列用C语言数组A[m]表示，front指针指向真正队头的前一个位置，rear指针指向真正队尾，队列中当前元素个数为n，则(1)若已知front、rear，则n=____。(2)若已知front、n，则rear=____。(3)若已知rear、n，则front=____。答案:n=(rear-front+m)%mrear=(front+n)%mfront=(rear-n+m)%m带头结点的循环单链表L为空的条件分别是____。答案:L-next==L或L-prior==L若有向图有2个有向回路，则其拓扑序列有____个。答案:0某二叉树有50个结点，根的右子树有45个结点，则对应的森林中第一棵树的结点数为____。答案:55将长度为2n和n的有序表归并成一个有序表，至少进行____次键值比较。答案:n单链表中结点*p有且仅有一个后继结点的条件是____。答案:p-next!=NULL&&p-next-next==NULL用head()和tail()函数表示在广义表A=(a,(x,y,z),b)中取出原子x的运算是：____。答案:head(head(tail(A)))如果从无向图的某个顶点出发，进行一次广度优先搜索，可访问到图的每个顶点，则该图一定是____图。答案:连通下面程序段的时间复杂性为____。for(i=0;in;i++)for(j=0;ji;j++)A[i][j]=0；答案:O(n2)对广义表((x),(a,b))，表头是____，表尾是____。答案:(x)、((a,b))顺序栈在进行____运算时，可能发生栈的上溢，在进行____运算时，可能发生栈的下溢。答案:进栈、退栈对n个结点的线索二叉树，线索有____个。答案:n+1四种基本逻辑结构是：____、____、树、图；可把它们分成两类：____和____。答案:集合、线性；线性、非线性n个顶点的有向图，最少有____条边；最多有____条边。答案:0、n(n-1)若I和O分别表示入栈和出栈，对元素a、b、c、d、e依次执行IIOIOIIOOO，则栈的容量至少为____。答案:3某有向图有28条边，则其顶点数最少为____。答案:7某哈夫曼树有109个结点，则其叶子数是____，度为2的结点数是____。答案:55、54设待排序数据中最大者为2010，则对基数为10的基数排序，需要进行____趟排序。答案:4设元素a1，a2，a3，a4，a5和a6依次入栈，出栈顺序为a3，a5，a4，a6，a2，a1，则栈的容量至少为____。答案:4内排序是指____。答案:数据全部在内存中进行排序设循环队列用C语言数组A[m]表示，front指针指向真正队头的前一个位置，rear指针指向真正队尾，则(1)队满的条件为____，(2)队空的条件为____。答案:front=(rear+1)%mrear==front已知哈夫曼树有100个叶子，则其结点总数是____。答案:199索引顺序表上的查找分两个阶段：____、____。答案:索引表查找、块内查找设C数组A[20][10]每个元素占2个存储单元，且第1个元素的首地址为2000，则元素A[8][9]的存储地址为____。答案:2178四种基本存储结构是：顺序、____、索引、____；其中最基本的是：____和____。答案:链式、散列；顺序、链式在有向无环图中，若存在一条从顶点i到顶点j的弧，则在顶点的拓扑序列中，顶点i与顶点j的先后次序是____。答案:i在j之前某完全二叉树的第5层只有6个结点，则其叶子结点数是____。答案:11由权值为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为____。答案:53Prim算法求最小生成树的时间为____，对____图比较有利。答案:O(n2)、稠密对n个顶点和e条边的图，采用邻接矩阵和邻接表表示时，空间复杂性分别为____和____。案:O(n2)、O(n+e)Kruskal算法求最小生成树的时间为____，对____图比较有利。答案:O(elog2e)、稀疏十字链表中的结点需存储非零元素的五个信息：行号、列号、值、____、____。答案:行指针、列指针在一个双链表中删除指针p所指结点，可执行以下操作：p-next-prior=____；p-prior-next=____；____；答案:p、p、deletep对400个结点的完全二叉树，叶子数为____。答案:200评价查找效率的主要标准是____。答案:键值比较次数(或平均查找长度)深度为k的二叉树，结点数至多为____，结点数至少为____。答案:2k-1、k将对称矩阵A[1..n][1..n]的下三角(含对角线)按行序存入一维数组B[1..n(n+1)/2]中，设A[i][j]对应位置B[k]，则k=____。答案:i(i-1)/2+j对100个结点的完全二叉树按层编号(编号1~100)，则编号为49的结点，其双亲的编号为____，编号最小的叶子结点的编号为____。答案:24、51图的BFS遍历类似树的____遍历，是其推广。答案:层次n个顶点的连通图至少____条边，最多____条边。答案:n-1、n(n-1)/2设链栈结点结构为(data,next)，top为栈顶指针，当执行入栈操作时需执行下列语句：p=newnode;p-data=x;p-next＝top;____;答案:top=p用尾指针表示单循环链表的好处是____。答案:找头、找尾都方便在堆排序的过程中，对n个记录建立初始堆需要进行____次筛运算，由初始堆到堆排序结束，需要对树根结点进行____次筛运算。答案:∟n/2」,n-1某图所有顶点的度数之和为200，则边数为____条。答案:100