市场部做网站工作职责,杭州做卖房子的工作哪个网站好,wordpress xss,广州哪个区最大第一章 绪论
与数据元素本身的形式、内容、相对位置、个数无关的是数据的 逻辑结构。 第二章 线性表
在一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变#xff0c;平均要移动的元素个数为 63.5。
n/2 单链表的存储密度 小于1。 创建一个包括n个结点的有序单链…第一章 绪论
与数据元素本身的形式、内容、相对位置、个数无关的是数据的 逻辑结构。 第二章 线性表
在一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动的元素个数为 63.5。
n/2 单链表的存储密度 小于1。 创建一个包括n个结点的有序单链表的时间复杂度是O()。 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低。
线性表的链式存储结构在一定场景下优于顺序存储结构。 第三章 栈和队列
若已知一个栈的入栈序列是123...n其输出序列为p1,p2,p3,...,pn若p1n则pi为 n-i1 一个循环队列f为当前队列头元素的前一位置r为队尾元素的位置假定队列中元素的个数小于n计算队列中元素个数的公式为 (nr-f)%n 。
对于非循环队列尾指针和头指针的差值便是队列的长度而对于循环队列差值可能为负数所以需要将差值加上n然后与n求余。 链式栈结点为data,linktop指向栈顶若想删除栈顶结点并将删除结点的值保存到x中则应执行操作 xtop-data;toptop-link; 设栈S和队列Q的初始状态为空元素e1,e2,e3,e4,e5,e6依次进入栈S一个元素出栈后即进入Q若6个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈S的容量至少应该是 3。
画个图就能解决 若一个栈以向量V[1..n]存储初始栈顶指针top设为n1,则元素x进栈的正确操作是 top--;V[top]x 设计一个判别表达式中左、右括号是否配对出现的算法采用 栈 数据结构最佳。 用链接方式存储的队列在进行删除运算时 头、尾指针可能都要修改。
在有头结点的链队列的出队操作中一般只需修改队头指针但当原队列中只有一个结点时该结点既是队头也是队尾故删去此结点时亦需修改队尾指针使其指向头结点且删去此结点后队列变空。 循环队列存储在数组A[0..m]中则入队时的操作为 rear(rear1)mod(m1) 最大容量为n的循环队列队尾指针是rear,队头指针是front,则队空的条件是 rearfront 第四章 串
串是一种特殊的线性表其特殊性体现在 数据元素是单个字符。
串是内容受限的线性表栈和队列是操作受限的线性表 串是字符的有限序列空串是指包括零个字符的串空串的长度为零空格串是由一个或多个空格组成的串模式匹配是串的一种重要运算串既可以采用顺序存储也可以采用链式存储。 串“ababaaababaa的next数组为 011234223456 串”ababaabab的nextval为 010104101 假设以行序为主序存储二维数组A[1..100.1...100]设每个数据元素占2个存储单元基地址为10则LOC[5,5] 818。
前4行总共4*100400第5行前4个元素再加上400个元素总共404个每个元素占2个单元404*2808加上基地址818。 设有数组A[i,j]数组的每个元素长度为3字节i的值为1~8j的值为1~10数组从内存首地址BA开始顺序存储当以列序为主序存储时元素A[5,8]的存储首地址为 BA180
假设数组的坐标是从ij开始,设定一行的长度为M一列的长度为N每个元素占用K个存储单元, 若以行为主序列那么a[5,8]的的位置为[5-i*M(8-j)]*K 同理如果是以列为主序列a[5,8]的的位置为 [(5-i)8-j*N]*K。 题中是以列为主存储那么就应该是[(5-1)(8-1)*8]*3180 设有一个10阶的对此矩阵A采用压缩存储方式以行序为主序存储a11为第一元素其存储地址为1每个元素占一个地址空间则a85的地址为 33
由于是对称矩阵因此压缩存储可以认为只要存储下三角矩阵。
(1,1) 1
(2,1) (2,2) 2
(3,1) (3,2) (3,3) 3
(4,1) (4,2) (4,3) (4,4) 4
(5,1) (5,2) (5,3) (5,4) (5,5) 5
(6,1) (6,2) (6,3) (6,4) (6,5) (6,6) 6
(7,1) (7,2) (7,3) (7,4) (7,5) (7,6) (7,7) 7
(8,1) (8,2) (8,3) (8,4) (8,5) 5
1234567533 B D 第五章 树与二叉树
单选
把一棵树转换为二叉树后这棵二叉树的形态 是唯一的。
二叉树的形态是唯一的。 一颗完全二叉树上有1001个结点其中叶子结点的个数是 501 因为满二叉树的结点数为2 ^ n - 1所以如果是满的那么为1023个但现在是1001说明最后一层空了22个结点。最后一层有512 - (1023 - 1001) 490个结点。最后一层空了22个结点所以倒数第二层有11个叶子结点。490 11 501。 一个具有1025个结点的二叉树的高h为 11~1025。
因为完全二叉树有 个结点n为高此时n为10再加上1个结点为11另一种极端情况为结点全部在最左或最右。 深度为h的满m叉树的第k层有 个结点1kh)。
可以试例子试出答案 利用二叉链表存储树则根节点的右指针 为空。
二叉链表存储树结构那么任意节点的左孩子指向该结点的孩子结点右孩子指针指向该节点的兄弟节点因为这里是树不是森林所以树的根节点没有兄弟结点则右指针是空。 在一棵度为4的树T中若有20个度为4的结点10个度为3的结点1个度为2的结点10个度为1的结点则树T的叶结点个数是 82。 除了根节点之外树的每个节点都有唯一的一个入度因此计算出共有多少个出度再加1就是树中总的节点数目。也就是20*410*31*210*11123个 而四叉树里节点就5类有4个孩子的有3个孩子的有2个孩子的有1个孩子的没有孩子的现在前4类的数目知道了是201011041那么没有孩子的节点自然就是123-4182个。 一颗非空的二叉树的先序遍历序列与后序遍历序列正好相反则该二叉树一定满足 只有一个叶子结点。
一定满足只有一个 叶子结点可能满足 所有的结点均无左孩子或 所有的结点均无右孩子。 设哈夫曼树中有199个结点则该哈夫曼树中有 100 个叶子结点。
首先需要明白两个知识点 1、哈夫曼树中不存在度为1的节点只有度为0和2的节点 2、n0n21
其次要会求解 设叶子结点的个数为n0度为2的节点个数为n2 则求全部节点数为nn0n2 已知n0n21代入上式得nn21n22*n21199题中给的数据 求得n299由此可得叶子结点n0100 若X是二叉中序线索树中一个有左孩子的结点且X不为根则X的前驱为 X的左子树中最右结点。 引入二叉线索树的目的是 加快查找结点的前驱或后继的速度。 设F是森林B是由F变换而得的二叉树。若F中有n个非终端结点则B中右指针域为空的结点有
根据森林转换为二叉树的“左孩子右兄弟”的表示法即对于每棵二叉树每个结点的右指针指向其右邻兄弟。
针对每一个非终端结点一定会有且仅有一个孩子结点没有右邻兄弟即右指针领域为空。因此N个非终端结点就有N个右指针域为空。
看完单棵二叉树再来看这些二叉树是怎么连接成一棵二叉树的。原理是将后一棵二叉树的根节点作为前一棵二叉树的右孩子连接起来所以只有最后一棵二叉树的根结点没有右孩子即右指针域为空。
因此综上N个非终端结点就有(N1)个结点的右指针域为空。 应用题 第六章 图
具有n个顶点的有向图最多有 n(n-1) 条边。 n个顶点的连通图用邻接矩阵表示时该矩阵至少有 2(n-1) 个非零元素。 所谓连通图一定是无向图,有向的叫做强连通图 连通n个顶点,至少只需要n-1条边就可以了,或者说就是生成树 由于无向图的每条边同时关联两个顶点,因此邻接矩阵中每条边被存储了两次也就是说是对称矩阵,因此至少有2(n-1)个非零元素 G是一个非连通无向图共有28条边则该图至少有 9 个顶点。
完全连通图n*(n-1)/228 n8题为非连通图故还要加一个点 也就是9个顶点 若从无向图的任意一个顶点出发进行一次深度优先搜索可以访问图中所有的顶点则该图一定是 连通 图。 普利姆算法 适合构造一个稠密图G的最小生成树。
Prim算法适合构造一个稠密图G的最小生成树Kruskal算法适合构造一个稀疏图G的最小生成树 用邻接表表示图进行广度优先遍历时通常可借助 队列 来实现算法。
用邻接表表示图进行深度优先遍历时通常可借助 栈 来实现算法。 图的深度优先遍历类似于二叉树的 先序遍历
深度优先遍历是先序遍历广度优先遍历是层次遍历 图的BFS生成树的树高比DFS生成树的树高 小或相等。 C 画图可解 D;D
拓扑排序 方法可以判断出一个有向图是否有环。 第七章 查找 对包含n个元素的表进行顺序查找时若查找每个元素的概率相同则平均查找长度为(N1)/2 第一个数的比较次数为1第二个数的比较次数为2。。。以此类推第N个数的比较次数为N所以总的比较次数为12...NN(N1)/2,平均比较次数为(N1)/2,也即平均查找长度。 如果要求一个线性表既能较快地查找又能适应动态变化的要求最好采用 分块查找。
分块查找是折半查找和顺序查找的一种改进方法折半查找查询速度快不适合动态变化。顺序查找查询速度慢适合动态变化。 对22个记录的有序表进行折半查找当查找失败时至少需要比较 4 次关键字。 折半查找与二叉排序树的时间性能 有时不相同。 不一定相同。 二叉排序树不一定是平衡树它是只要求了左右子树与根结点存在大小关系但是对左右子树之间没有层次差异的约束因此通过二叉排序树进行查找不一定能够满足logn的例如一棵只有多层左子树的二叉排序树。 只有是一棵平衡的二叉排序树时其查找时间性能才和折半查找类似。 C
二叉排序树的左子树小于根节点右子树大于根节点。 在平衡二叉树中插入一个结点后造成了不平衡设最低的不平衡结点为A并已知A的左孩子的平衡因子为0右孩子的平衡因子为1则应作 RL 型调整以使其平衡。 关于m阶B-树的说法
根结点至多有m棵子树所有叶子都在同一层次上非叶结点至少有m/2m为偶数或m/21m为奇数棵子树所有结点中的数据都是有序的。 关于B-和B树的叙述中
B-树和B树都是平衡的多叉树B-树和B树都可用于文件的索引结构B-树支持随机检索不支持顺序检索B树都支持 m阶B-树是一棵 m叉平衡排序树。 A A 第八章 排序 D D C D B B C D A 2018-2019第一学期
单选 堆是一种平衡的数据结构。 AVL是一种平衡二叉搜索树。 2021-2022第一学期 2017
单选 B根据二叉树的性质可知度为0的结点个数比度为2结点个数多一个即n0n21。 C 应用 算法 int count(LNode *head){LNode *p;int n0;phead;while(p!NULL){if(p-datax){n;pp-next;}
return(n);
} int Search(SSTable ST, KeyType key){int i;ST.elem[0].keykey;for(iST.length;!EQ(ST.elem[i].key,key);--i){return i;
} 2018
单选 C C B; 小顶堆是根结点小于子结点 应用
