填空题 数据结构.pdf

《填空题 数据结构.pdf》由会员分享，可在线阅读，更多相关《填空题 数据结构.pdf（1页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 数据结构由数据的逻辑结构、存储结构和数据的运算三部分组成。2 在单链表中某结点后插入一个新结点，需要修改2 个结点指针域的值。3 设栈 s 的初始状态为空，若元素 a.b.c.d.e.f 依次进栈，得到的出栈序列是 b、d、c、f、e、a，则栈 s 的容量至少是 3.5 某二叉树的后根遍历为ABKCBPM，则该二叉树的根为 M6 一棵树 T 采用孩子兄弟链表存储，如果树 T 中某个节点为叶子结点，则该结点在二叉链表中所对应的结点一定是左右指针域为空。7 一个有 n 个顶点的无向连通图，最少有n-1 条边8 当排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效

2、率最高的是直接插入排序。9 在一棵深度为 h 的具有 n 个结点的二叉排序树中，查找任一结点的最多比较次数是n。10 在一棵树中，根结点没有前驱结点。11 数据元素及其关系在计算机存储器内的表示称为数据的存储结构。12 长度为 n 的线性表采用单链表结构存储时，在等概率情况下查找第i 个元素的时间复杂度是 O（n）。13 下面是在顺序栈上实现的一个栈基本操作，该操作的功能是求栈顶。Typedef strictDatatype data100;Int top;seqstack;Datatype f18(seqstack*s).if(stackempty(s)Error(“stack is emp

3、ty”);Return s-datas-top;14 在串匹配中，一般将主串称为目标串，将子串称为模式串。15 在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该后继结点的。16 用 6 个权值分别为 6、13、18、30、7 和 16 的结点构造一颗哈夫曼树，该树的带权路径长度为 219。17 已知有向图如下所示，其中顶点A 到顶点 C 的最短路径是 35。18 对序列55、46、13、05、94、17、42进行比较交换排序，第一趟排序后的结果是 46、13、05、55、17、42、94。19 对于一颗满二叉树，若有m 个叶子，则树中结点数为 2m-1。20 长度为零的串称为空串。