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

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

2、法查找，不论成功与否，键值比较次数最多为答案 : 8下面程序段的时间复杂性为 .for(i=0;i< n;i+)for(j=0;j< 10;j+)Aij=0；沟熠金富爱建谴净。答案 : O(n)带头结点的单链表L 为空的判定条件是.答案 : L-> next=NULLn( >1)个顶点的强连通图至少 条边，最多条边.答案: n、 n(n-1)排序算法的稳定性是指.答案: 对相同关键字排序前后相对位置不变对 400 个结点的完全二叉树，度为 1 的结点数为 .答案 : 0算法满足的五个重要特性是： 、 、 、输入、输出；其中区别于程序的地方是答案 : 有穷性、确定性、可行

3、性；有穷性.散列表中要解决的两个主要问题是： 、 .答案 : 散列函数的构造、冲突的处理设循环链队列的长度为n,若只设尾指针，则出队和入队的时间复杂度分别是?口.答案 : O(1) 、 O(1)头指针为F、尾指针为R、带头结点的链队列为空的条件是 .答案 : R=F在带头结点的单链表L 中，若要删除第一个结点，则需执行下列三条语句：； L-> next=p-> next ； delete p ；残鹫楼静铸源湃淑sm。答案 : p=L-> next在邻接矩阵和邻接表上对图进行 BFS或DFSS历时，时间复杂性分别为 、. 2答案 : O(n2) 、 O(n+e)图的DFS遍历类

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

5、: p-> 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(log 2n)散列表既是一种方式又是一种方法.答案：储存、查找稀疏矩阵的三元组表示中，三元组是指非零元素的 、和 三项.答案：行号、列号、值下图所示带权无向图的最

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

7、: 99线索二叉树中，线索的含义是.答案 : 某种遍历的前趋或后继信息两个串相等的充分必要条件是两个串的长度相等且 .答案 : 对应字符相同希尔排序的增量序列中，最后一个增量为 .答案 : 1以行优先存储的一维数组 A1.10 ，每个元素占 4 字节， A5 的地址是1020，则数组的首地址是养技箧志类蒋蔷。答案 : 1004评价排序效率的主要标准是.答案 : 关键字比较次数、移动次数某树所有结点的度数之和为100，则树中边数为答案 : 100“就地排序”是指排序算法辅助空间的复杂度为答案 : O(1)个顶点的连通图至少条边，最多 条边 .答案 : n-1 、 n(n-1)/2在深度为 7 的

8、二叉树中，第 5 层上的结点数最少为 ，最多为答案 : 1、 16程序设计的实质是：数据的表示和，或者说，程序=数据结构答案 : 数据的处理；算法 设循环队列用C语言数组Am表示，front指针指向真正队头的前一个位置，rear指针指向真正队尾, 队列中当前元素个数为n,则(1) 若已知 front 、 rear ，则 n=.(2)若已知 front、n, WJ rear=.(3)若已知 rear、n,贝U front=.厦礴恳蹒骈日寺翥继骚。答案 :n=(rear-front+m)%mrear=(front+n)%mfront=(rear-n+m)%m茕桢广鲫献选块网踊泪。带头结点的循环单链

9、表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)答案 : head(head(t

10、ail(A)如果从无向图的某个顶点出发，进行一次广度优先搜索，答案 : 连通下面程序段的时间复杂性为 .for(i=0;i< n;i+)for(j=0;j< i;j+)Aij=0;髓丛妈趣为赡债蛭练浮。答案 : O(n 2)对广义表 (x),(a,b) ，表头是 ，表尾是 .答案 : (x) 、 (a,b)顺序栈在进行运算时，可能发生栈的上溢，在进行答案 : 进栈、退栈对 n 个结点的线索二叉树，线索有个 .答案 : n+1次键值比较.中取出原子x的运算是：.鹅娅尽揖鹤惨屣梆可访问到图的每个顶点， 则该图一定是图 .运算时，可能发生栈的下溢四种基本逻辑结构是： 、 、树、图；可把它

11、们分成两类： 和.答案 : 集合、线性；线性、非线性n 个顶点的有向图，最少有条边；最多有条边 .答案 : 0、 n(n-1)若I和。分别表示入栈和出栈，对元素 a、b、c、d、e依次执行IIOIOIIOOO,则栈的容量至少为3tm圣横蕨龈讶骅汆。答案 : 3某有向图有28 条边，则其顶点数最少为 .答案 : 7某哈夫曼树有109个结点，则其叶子数是，度为 2 的结点数是.答案 : 55 、 54设待排序数据中最大者为2010，则对基数为10 的基数排序，需要进行趟排序 .答案 : 4设元素al, a2, a3, a4, a5和a6依次入栈，出栈顺序为 a3, a5, a4, a6, a2,

12、al,则栈的容量至少为 .渗呛俨匀谓鳖调砚金帛。答案 : 4内排序是指.答案 : 数据全部在内存中进行排序设循环队列用C语言数组Am表示，front指针指向真正队头的前一个位置，rear指针指向真正队尾，则(1) 队满的条件为 ，(2)队空的条件为.钱卧泻嵯圣骋睨限期答案 :front=(rear+1)%mrear=front已知哈夫曼树有100 个叶子，则其结点总数是.答案 : 199索引顺序表上的查找分两个阶段： 、 .答案 : 索引表查找、块内查找设 C 数组 A2010 每个元素占 2 个存储单元，且第 1 个元素的首地址为2000，则元素A89 的存储地址为_.凤袜备音叫®

13、轮烂蔷。答案 : 2178四种基本存储结构是：顺序、 、索引、 ；其中最基本的是： 和答案 : 链式、散列；顺序、链式 在有向无环图中，若存在一条从顶点 i 到顶点 j 的弧，则在顶点的拓扑序列中，顶点 i 与顶点 j 的先后 次序是. irn俣阉蕨直阊邺钱鼠 答案 : i 在 j 之前某完全二叉树的第 5 层只有 6 个结点，则其叶子结点数是.答案 : 11由权值为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 .答案 : 53Prim 算法求最小生成树的时间为 ，对 图比较有利 .2答案 : O(n2) 、稠密对 n 个顶点和 e 条边的图，采用邻接矩阵和邻接表表示时

14、，空间复杂性分别为 和.2案: O(n2) 、 O(n+e)Kruskal 算法求最小生成树的时间为 ，对 图比较有利 .答案 : O(elog 2e) 、稀疏十字链表中的结点需存储非零元素的五个信息：行号、列号、值、 、 .答案 : 行指针、列指针在一个双链表中删除指针 p 所指结点，可执行以下操作：p-> next-> prior= ； p-> prior-> next= ； ；坛搏乡it忏篓锲铃演。答案 : p、 p、 delete p对 400 个结点的完全二叉树，叶子数为 .答案 : 200评价查找效率的主要标准是.答案 : 键值比较次数( 或平均查找长度)深

15、度为 k 的二叉树，结点数至多为 ，结点数至少为 .答案 : 2k-1 、 k将对称矩阵A1.n1.n的下三角 (含对角线 )按行序存入一维数组B1.n(n+1)/2 中，设 Aij 对应位置Bk,贝U k=.蜡燮夥帐铉锚金市赘。答案 : i(i-1)/2+j对 100 个结点的完全二叉树按层编号(编号 1100) ， 则编号为 49 的结点，其双亲的编号为 ， 编号最小的叶子结点的编号为. io而皤昙松闫撷凄。答案 : 24 、 51图的BFS遍历类似树的 遍历，是其推广.答案 : 层次n 个顶点的连通图至少条边，最多 条边 .答案 : n-1 、 n(n-1)/2设链栈结点结构为 (data,