Jelly27th

# 给出一个算法求解最大生成树。这比求解最小生成树更难吗？ 将 Kruskal 算法生成最小生成树关于最小值选择比较的语句改成最大值比较即可，和求解最小生成树相比一样难度。 # 证明寻找割点的算法的正确性 假设存在一个矛盾，即非根节点aaa 和后代节点和正确的祖先节点没有正确的建立联系，因为存在这个矛盾且确实存在，因此存在寻找割点的算法的可能。 # 证明：在一个有向图的深度优先生成森林所有的交叉边都是从右到左的。 设(v,w)(v,w)(v,w) 为交叉边，当检查点www 时，标记，若点vvv 不是www 的后代，按照左右子树的规定，则应该是w−>vw ->...

# 编写个程序执行对一个图的拓扑排序 拓扑排序简单的来说是求有向无环图的一条从顶点vvv 到顶点uuu 的路径。 拓扑排序参考链接/*----- -----| 1 | -> | 2 |----- ----- | \ /|\ \ / _\/ |----- ----- | 4 | | 3 |----- ----- / \ \ | | _\/ \|/----- ----- | 6 | -> | 5 |----- ----- */void Topological_Sort(Graph G){ /* * Create an array of in-degrees for...

# 编写一个程序来确定路径压缩法和各种求并方法的效果。你的程序应该使用六种可能的方法处理一系列等价操作。 题意是叫你实现 2 种 find 操作和 3 种 union 操作，常规任意并查集初始化为 0，但灵巧求并算法的初始化为 - 1。测试数据可以用书上习题 8.1 的，还挺有用的。 void DisjSet_Init_0(DisjSet S){ for(int i = NumSets; i > 0; i--) S[i] = 0;}// it apply in DisjSet_Union_Size() and...

# 设我们交换元素 A [i] 和 A [i+k], 它们最初是无序的。证明去掉的逆序最少为 1 个最多为 2k-1 个 若 N=1, 则只存在一个逆序数。 若 N=K, 则 A [i] 和 A [i+k] 各存在 K-1 的逆序数，且有一个重复，即 (A [i],A [i+k]), 总共 2K-1 个。 所以去掉的逆序最少为 1 个最多为 2k-1 个。 # 下述两种对图 7 一 4 所编写的希尔排序例程的修改影响最坏情形的运行时间吗？ # a. 如果 lncrement 是偶数，则在第 2 行前从减 1。 不会，希尔排序的一个重要特性是增量之间最好不要有公因子，即增量之间互素，原始增量排序...

# 编写在二叉堆中进行上滤和下滤的例程 这是二叉堆的最重要操作步骤。 上滤波static int percolateUp(BinHeap H, BinHeapElementType X, int Pos){ int i; for(i= Pos;H->Elements[i/2]>X;i/=2) H->Elements[i] = H->Elements[i/2]; return i;}下滤波static int percolateDown(BinHeap H, BinHeapElementType LastElement, int...

# 编写一个程序，计算使用线性探测、平方探测以及双散列插入的长随机序列所需要的冲突次数 线性探测: F(i)=iF(i) = iF(i)=i 平方探测: F(i)=i2F(i) = i^2F(i)=i2 双散列: F(i)=i∗h(X)F(i) = i*h(X)F(i)=i∗h(X), 其中h(X)=7−(Xmod7)h(X) = 7-(X mod 7)h(X)=7−(Xmod7) 计算冲突次数直接在函数里面加个静态变量就行。 #define R 7enum KindOfEntry { Legitmate, Empty, Deleted};typedef...

# 写出生成具最少节点、高度为 H 的 AVL 树的程序，函数得运行时间是多少？ AvlTree MinGenTree(int height, int* lastNode){ AvlTree T; if(height>=0) { T = malloc(sizeof(AvlNode)); T->left = MinGenTree(height-1,lastNode); T->data = ++(*lastNode); T->height = 0; T->right = MinGenTree(height-2,lastNode);...

# 证明在 N 个节点的二叉树中，存在 N+1 个 NULL 指针代表 N+1 个儿子 证明：假设有 N 个节点，则指针 point 有 2N 个，非 NULL 指针为 N-1 个，则 NULL 指针为2N−(N−1)=N+12N-(N-1)=N+12N−(N−1)=N+1 个，所以存 N+1 个 NULL 指针未来可代表 N+1 个儿子。 # 证明在高度为 H 的二叉树中，节点的最大个数是2H+1−12^{H+1}-12H+1−1 证明：假设这是一颗完全二叉树，则有最大节点，其中高度为 H 时，层数为 H+1。 则第一层，节点数N=20N = 2^0N=20, 第二层，节点数N=21N =...

~~~~         ~~~~         ~~~~     虽然我一直以自己只是喜欢看动漫玩游戏自称，不是个二次元。但从周围人看来，我就是个喜欢二次元的家伙，而且我现在也大致认为自己算是个普遍意义上的 ACG 爱好者吧。     ~~~~         ~~~~         ~~~~    ...

# 缘由 最近刚推完了雪雪雪和新章，至此，9nine 系列完结，我想要几张里面好看的图片，谷歌找了一晚加一上午我才弄出来，离谱的是，网上一堆推荐 GalGame 解包工具的文章居然不给工具原链接，而是网盘链接，有些甚至没有，我真的无语，于是有了这篇文章。 # 游戏资源 9nine 系列 (樱空汉化组) 资源来源于 9nine 吧，一切所有权归樱空汉化组所有，我给出的网址也是樱空汉化组自己提供的，无效了就自己去 9nine 吧找吧，不过这次链接的手段挺高明的。 # 解包工具 GARbro KrkrExtract 4.0.1.5 # KrkrExtract 解包...