在堆排序的过程中, 每次弹出根结点(也就是 deleteMin)的时间复杂度为多少?

整个堆排序过程的时间复杂度是多少?

对于有序表 $\{1, 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100\}$, 当使用二分法查找值为 82 的结点时, 不必超过多少次比较就可以找到.

设表中有100个元素, 如果用二分搜索法查找数据元素 $x$, 则最多需要比较多少次就可以断定数据元素 $x$ 是否在表中.

后缀表达式 $6\ 5\ 2\ 3\ +\ 8\ *\ +\ 3\ +\ *$ 的值为什么?

中缀表达式 $a+b*c+(d*e+f)*g$ 对应的后缀表达式是什么?

[Def] 内部路径长(internal path length)

一棵树的所有结点的深度之和称为内部路径长.

设 $D(N)$ 是具有 $N$ 个结点的某棵树 $T$ 的内部路径长. $D(1)=0$.

对于二叉查找树, 其平均内部路经长（仍记为 $D(N)$, 确切地应该记为 $E[D(N)]$）满足

\[
D(N)=\frac{2}{N}\biggl[\sum_{j=0}^{N-1}D(j)\biggr]+N-1.
\]

由此求出 $D(N)=O(N\log N)$.

我们知道一棵非空二叉树, 其满结点个数比叶子结点数目少一. (参见问题1097)

若记满结点个数是 $M$, 则叶子结点个数是 $M+1$. 现在设只有一个儿子的结点个数是 $N$,

显然 $N$ 可以是 $0$ 或 $1$. 比如完全二叉树.

$N$ 实际上与 $M$ 没有关系. 也就是说对于任意的 $N, M$, 都存在这样的二叉树.

例如:

若某二叉树有 $20$ 个叶子结点, 有 $30$ 个结点仅有一个儿子, 则该二叉树的总的结点数是 69.

这是因为满结点个数为 $19$, 从而总的结点数就是 $19+30+20=69$.

如果加上深度、高度这些限制, 可能会得到更多有趣的结论.

证明 $X^{62}$ 可以只用 8 次乘法算出.

当然, $X^{62}$ 可以用 9 次乘法算出.

\[
\begin{aligned}
X^{62}&=X^{31}\cdot X^{31}\\
X^{31}&=X^{15}\cdot X^{15}\cdot X\\
X^{15}&=X^{7}\cdot X^{7}\cdot X\\
X^{7}&=X^{3}\cdot X^{3}\cdot X\\
X^{3}&=X^{1}\cdot X^{1}\cdot X\\
\end{aligned}
\]

证明:

二项树 $B_k$, 以二项树 $B_0,B_1,B_2,\ldots,B_{k-1}$ 作为其根的儿子. (其中 $B_j$ 指高度为 $j$ 的二项树.

高度为 $k$ 的二项树恰有 $2^k$ 个结点, 在深度 $d$ 处的结点数是二项系数 $\binom{k}{d}$.

将序列 $a_1,a_2,\ldots a_n$ 入栈、出栈, 共有多少种可能方式?

实验: 对于输入的序列, 比如 $1,2,3,\ldots,n$, 输出所有入栈、出栈的可能序列.

我们列出出栈的序列.

例如:

当一个数时, 只有一种方式. $a_1$

当 $n=2$ 时, 有 $a_1,a_2$ 和 $a_2,a_1$ 两种出栈序列.

当 $n=3$ 时, 有 5 种.

\[
\begin{array}{ccc}
a_1 & a_2 & a_3,\\
a_1 & a_3 & a_2,\\
a_2 & a_1 & a_3,\\
a_2 & a_3 & a_1,\\
a_3 & a_2 & a_1,\\
\end{array}
\]

当 $n=4$ 时, 有 14 种.

 按一次进入的个数来进行分类

至少有14种。

(1) 全进之后再出情况，只有 1 种：$a_4,a_3,a_2,a_1$.

(2) 进3个之后再出的情况，有 3 种: $a_3,a_4,a_2,a_1$,  $a_3,a_2,a_4,a_1$,  $a_3,a_2,a_1,a_4$.

(3) 进2个之后再出的情况，有 5 种: $a_2,a_4,a_3,a_1$,   $a_2,a_3,a_4,a_1$,   $a_2,a_1,a_3,a_4$,   $a_2,a_1,a_4,a_3$,  $a_2,a_3,a_1,a_4$.

(4) 进1个之后再出的情况，有 5 种: $a_1,a_4,a_3,a_2$,   $a_1,a_3,a_2,a_4$,   $a_1,a_3,a_4,a_2$,   $a_1,a_2,a_3,a_4$,   $a_1,a_2,a_4,a_3$.

当 $n=5$ 时,

(1) 全进之后再出情况，只有 1 种
(2) 进4个之后再出的情况，有 4 种:
(3) 进3个之后再出的情况，有 9 种:
(4) 进2个之后再出的情况，有 14 种
(5) 进1个之后再出的情况，有 14 种

总共有 42 种.

一般的, 证明有 $\frac{1}{n+1}\binom{2n}{n}$ 种可能. (这个数实际上就是 Catalan 数)

Hint. 不过上述思路对于证明并没太大有帮助, 应该考虑第 1 个入栈元素第 $i$ 个出栈的种类数.

问题 1：关于void insert(const T &x,BinaryNode * &t)

   老师您上课讲了*&t，说是加引用是为了改变t所指向的地址，我觉得讲得不是太清楚。我的理解是，比如，

struct BinaryNode
{
    string element;
    BinaryNode* left;
    BinaryNode* right;
    TreeNode(BinaryNode* m=NULL,BinaryNode* n=NULL):left(m),right(n){}
};

insert(x,p);

则BinaryNode*类型的变量只是结构体中的一个成员,void insert(const T &x,BinaryNode * &t)改为void insert(const T &x,BinaryNode * t)，则此时的p仅仅表示一个成员的地址，而不是这个结构体的地址。故此时的*&t我认为是代表这个结构体的地址。

问题 2:

  æˆ‘在网上查了相关命令行参数输入的问题，可是还是不懂如何在codeblocks输入参数。。。请老师给出具体的步骤啊

如我下面的例子（c++primer相关章节)， ä¿å­˜è·¯å¾„D:\My Documents\c++\argc_argv

#include <iostream>
#include <string>
#include <vector>
#include <ctype.h>
#include<cstdlib>
using namespace std;
const char *const program_name = "comline";
const char *const program_version = "version 0.01 (08/07/97)";
inline void usage( int exit_value = 0 )
{
// 输出一个格式化的用法信息
// 并用 exit_value 退出...
cerr<< "usage:\n"
<< program_name << " "
<< "[-d] [-h] [-v] \n\t"
<< "[-o output_file] [-l limit] \n\t"
<< "file_name\n\t[file_name [file_name [ ... ]]]\n\n"
<< "where [] indicates optional option: \n\n\t"
<< "-h: help.\n\t\t"
<< "generates this message and exits\n\n\t"
<< "-v: version.\n\t\t"
<< "prints version information and exits\n\n\t"
<< "-d: debug.\n\t\tturns debugging on\n\n\t"
<< "-l limit\n\t\t"
<< "limit must be a non-negative integer\n\n\t"
<< "-o ofile\n\t\t"
<< "file within which to write out results\n\t\t"
<< "by default, results written to standard output \n\n"
<< "file_name\n\t\t"
<< "the name of the actual file to process\n\t\t"
<< "at least one file_name is required --\n\t\t"
<< "any number may be specified\n\n"
<< "examples:\n\t\t"
<< "$command chapter7.doc\n\t\t"
<< "$command -d -l 1024 -o test_7_8 "
<< "chapter7.doc chapter8.doc\n\n";
exit( exit_value );
}
int main( int argc, char* argv[] )

{
bool debug_on = false;
bool ofile_on = false;
bool limit_on = false;
int limit = -1;
string ofile;
vector<string> file_names;
cout << "illustration of handling command line arguments:\n"
<< "argc: " << argc << endl;
for ( int ix = 1; ix < argc; ++ix )
{
cout << "argv[ " << ix << " ]: "
<< argv[ ix ] << endl;
char *pchar = argv[ ix ];
switch ( pchar[ 0 ] )
{
case '-':
{
cout << "case \'-\' found\n";
switch( pchar[ 1 ] )
{
case 'd':
cout << "-d found: "
<< "debugging turned on\n";
debug_on = true;
break;
case 'v':
cout << "-v found: "
<< "version info displayed\n";
cout << program_name
<< " :: "
<< program_version
<< endl;
return 0;
case 'h':
cout << "-h found: "
<< "help information\n";
// 这里没必要用 break 了, usage() 可以退出
usage();
case 'o':
cout << "-o found: output file\n";
ofile_on = true;
break;
case 'l':
cout << "-l found: "
<< "resource limit\n";

limit_on = true;
break;
default:
cerr << program_name
<< " : error : "
<< "unrecognized option: - "
<< pchar << "\n\n";
// 这里没必要用 break 了, usage() 可以退出
usage( -1 );
}
break;
}
default: // 或文件名
cout << "default nonhyphen argument: "
<< pchar << endl;
if ( ofile_on ) {
ofile_on = false;
ofile = pchar;
}
else
if ( limit_on ) {
limit_on = false;
limit = atoi( pchar );
if ( limit < 0 ) {
cerr << program_name
<< " : error : "
<< "negative value for limit.\n\n";
usage( -2 );
}
}
else file_names.push_back( string( pchar ));
break;
}
}
if ( file_names.empty() ) {
cerr << program_name
<< " : error : "
<< "no file specified for processing.\n\n";
usage( -3 );
}
if ( limit != -1 )
cout << "User-specifed limit: "
<< limit << endl;
if ( ! ofile.empty() )
cout << "User-specified output file: "
<< ofile << endl;
cout << (file_names.size() == 1 ? "File " : "Files ")
<< "to be processed are the following:\n";
for ( int inx = 0; inx < file_names.size(); ++inx )
cout << "\t" << file_names[ inx ] << endl;
}
 

平面 $\mathbb{R}^2$ 中坐标均为整数的点称为整点(或格点), 它们组成的集合称为格(lattice).

两个格点 $(a,b)$ 与 $(c,d)$ 是互相可见的, 如果连接它们的线段不包含其他格点.

假设 $\Delta_n=\{(x,y)\mid 0\leq x\leq n-1, 0\leq y\leq n-1, x,y\in\mathbb{Z}\}$.

请构思这样的一个小程序,

首先显示 $\Delta_n$ 中的所有格点,

(1) 点击 $\Delta_n$ 中的某个点 $p$, 即显示 $p$ 的所有可见点, 并用虚线连接.

(2) 点击 $\Delta_n$ 中的某个点 $p$, 将 $p$ 的所有可见点消除.

[Def] 设 $M,N\subset\Delta_n$, 称 $M$ 可从 $N$ 看见, 或 $N$ 中的点可以直达 $M$, 如果对于 $M$ 中的任一点, 都存在 $N$ 中的某一点看到它.

令

\[f(n)=\min\{|M|\mid \Delta_n\ \text{可被}\ M\ \text{看见}\}\]

这里 $|M|$ 指 $M$ 中点的个数, 尝试编程求 $f(n)$ 的值.

 H.L. ABBOTT 于 1974 年证明了 $f(n)$ 满足如下不等式

\[
\frac{\log n}{2\log\log n}<f(n)<4\log n.
\]

References:

H.L. ABBOTT, Some results in combinatorial geometry. Discrete Mathematics, 9 (1974) 199-204.