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

《华师网络学院作业答案-数据结构填空题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、在无头结点的双链表中，指针P所指结点是第一个结点的条件是____。答案:p->prior==NULL某无向图有28条边，则其顶点数最少为____。答案:8在顺序表中做插入操作时首先检查____。答案:上溢或表满查找表的逻辑结构是____。答案:集合运算定义在逻辑结构上，算法定义在____结构上；运算指出“做什么”，算法指出____。答案:储存；怎么做深度为k的二叉树，叶子数至多为____，叶子数至少为____。答案:2k-1、1数组A[1..8][1..10]中，每个元素占3个单元，从首地址SA开始存放，若该数组按列存放，则元素A[8][5]的地址是____答案:SA+117在150个结点

2、的有序表中二分法查找，不论成功与否，键值比较次数最多为____。答案:8下面程序段的时间复杂性为____。for(i=0;inext==NULLn(≥1)个顶点的强连通图至少____条边，最多____条边。答案:n、n(n-1)排序算法的稳定性是指____。答案:对相同关键字排序前后相对位置不变对400个结点的完全二叉树，度为1的结点数为____。答案:0算法满足的五个重要特性是：____、____、____、输入、输出；其中区别于程序的地方是_

3、___。答案:有穷性、确定性、可行性；有穷性。散列表中要解决的两个主要问题是：____、____。答案:散列函数的构造、冲突的处理设循环链队列的长度为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遍历

4、类似树的____遍历，是其推广。答案:先根树的三种主要的遍历方法是：____、____和层次遍历。答案:先根、后根n个结点的二叉链表中，指针总数为____个，其中____个指针为空。答案:2n、n+1对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为____，在查找不成功时的平均查找长度为____。答案:50/2、100(或101)从n个结点的二叉排序树中查找一个元素，平均时间复杂性大致为____。答案:O(log2n)对广义表L=((a,b),c,d)进行操作head(tail(L))的结果是：____。答案:c非空单循环链表L中结点*p是尾结点的条件是____。答案:p

5、->next==L对n个顶点和e条边的无向图，采用邻接矩阵和邻接表表示时，求任一顶点度数的时间复杂性分别为____和____。答案:O(n)、O(e/n)n个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。答案:2(n-1)某二叉树中双分支结点数为5个，单分支结点数为4个，则叶子结点数为____个。答案:6下面程序段的时间复杂度为____。y=n;while(y>1)y=y/2;答案:O(log2n)散列表既是一种____方式又是一种____方法。答案:储存、查找稀疏矩阵的三元组表示中，三元组是指非零元素的____、____和____三项。答案:行号、列号、值下图所示带权无

6、向图的最小生成树的权为____。答案:17串"The"含有的子串个数为____。答案:7对广义表((x),(a,b))，长度是____，深度是____。答案:2、2在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作____。答案:储存密度可以将排序算法分为：插入排序、____、选择排序、____、分配排序。答案:交换排序、归并排序所有基于比较的排序方法，平均时间复杂性最好时为____。答案:O(nlog2n)n个顶点的无向图，最少有____条边，最多有____条边。答案:0、n(n-1)/2散列表的冲突处理方法有____和____两种，对应的散列表分别称为开散列表和闭散列表

7、。答案:开放地址法、链地址法(或拉链法)对100个结点的树，所有结点的度数之和为____。答案:99线索二叉树中，线索的含义是____。答案:某种遍历的前趋或后继信息两个串相等的充分必要条件是两个串的长度相等且____。答案:对应字符相同希尔排序的增量序列中，最后一个增量为____。答案:1以行优先存储的一维数组A[1..10]，每个元素占4字节，A[5]的地址是1020，则数组的首地址是____。答案:1004评价排序