给女生做网站,智慧旅游平台建设方案,军事新闻内容摘抄,网站关键词添加多少个目录 1. 排序 1.1 冒泡排序的改进 2. 二叉树 2.1 二叉树的性质 3. 栈 队列 3.1 循环队列 3.2 链式队列 4. 平衡二叉搜索树——AVL树、红黑树 5 优先级队列#xff08;堆#xff09; 1. 排序
1.1 冒泡排序的改进 下面的排序方法中#xff0c;关键字比较次数与记录的初… 目录 1. 排序 1.1 冒泡排序的改进 2. 二叉树 2.1 二叉树的性质 3. 栈 队列 3.1 循环队列 3.2 链式队列 4. 平衡二叉搜索树——AVL树、红黑树 5 优先级队列堆 1. 排序
1.1 冒泡排序的改进 下面的排序方法中关键字比较次数与记录的初始排列无关的是______。 A. 希尔排序 B. 冒泡排序 C. 直接插入排序 D. 直接选择排序 答案D
基础的冒泡排序是与初始排列无关的但是改进的冒泡排序当一趟排序之后没有交换则说明序列已经有序则可退出排序例如一个已经排好序的序列第一次循环之后就可以退出排序了
所以说对比B选项和D选项D选项肯定时最优解
2. 二叉树
2.1 二叉树的性质
① 对于任意一颗二叉树设叶子节点个数为n0度为二的节点的个数为n2则满足n0 n2 1 某二叉树共有 399 个结点其中有 199 个度为 2 的结点则该二叉树中的叶子结点数为 A. 不存在这样的二叉树 B. 200 C. 198错误 D. 199 答案B
②深度
根节点的深度为0
③ 完全二叉树每一层的节点个数 一棵完全二叉树第六层有9个叶结点根为第一层则结点个数最多有 A. 112 B. 111 C. 107 D. 109 2^6-1 2^(7-1)-9*2 109) 答案D :第六层满节点题目要求第六层有9个叶子节点则需要第六层的9个节点不挂叶子节点所以第七层节点有2^(7-1)-9*2个节点
1. 满二叉树第i层节点个数2^(i-1);
2. 总共i层的满二叉树所有节点个数2^i - 1
3. 队列
3.1 循环队列 现有一循环队列其队头指针为front队尾指针为rear循环队列长度为N。其队内有效长度为“左闭右开” A. (rear - front N) % N 1错误 B. (rear - front N) % N C. (rear - front) % (N 1) D. (rear - front N) % (N - 1) 答案B 3.2 链式队列 用不带头结点的单链表存储队列其队头指针指向队头结点队尾指针指向队尾结点则在进行出队操作时 A. 仅修改队头指针错误 B. 仅修改队尾指针 C. 队头、队尾指针都可能要修改 D. 队头、队尾指针都要修改 答案C
※当队列只有一个节点时出队列对头队尾指针均需要修改、 4. 栈
4.1 运算表达式 表达式3*2^(42*2-6*3)-5求值过程中当扫描到6时,对象栈和运算符栈为(),其中^为乘幂 A. 3,2,4,1,1;(*^(*- B. 3,2,8;(*^-错误 C. 3,2,4,2,2;(*^(- D. 3,2,8;*^(- 答案D
数据栈有数据就直接入栈
运算符栈设遍历到当前的运算符位x如果栈不为空比较栈顶与当前运算符优先级x当栈顶运算符优先级大于或者等于x的优先级则出栈并将两个数据栈的数据出栈计算出对应的数据加入到数据栈中否则将运算符入栈
/*根据上述原理模拟实现一个计算器*/
#include iostream
#include unordered_map
#include stack
#include functional
#include string#define MAX_PRI INT_MAXusing namespace std;
int main() {//数据栈stackdouble _data; //运算符栈stackchar _operator; //运算符优先级unordered_mapchar, int pri{ {, 0}, {-, 0}, {*, 1}, {/, 1}, {^, 2}, {(, MAX_PRI }, {), MAX_PRI}};unordered_mapchar, functiondouble(double, double) func{{, [](double x, double y) - double { return x y; }},{-, [](double x, double y) - double { return x - y; }}, {*, [](double x, double y) - double { return x * y; }},{/, [](double x, double y) - double { return x / y; }},{^, [](double x, double y) - double { return pow(x, y); }}};string exp;cin exp;auto calculate [_data, _operator, func]() {char op _operator.top();_operator.pop();double x _data.top();_data.pop();double y _data.top();_data.pop();_data.push(func[op](y, x)); //运算顺序与出栈顺序相反};auto stringtonum [exp, pri](int i) - double {int j i 1;while (j exp.length() pri.find(exp[j]) pri.end()) j;double num stod(exp.substr(i, j - i));i j - 1; return num;};for (int i 0; i exp.length(); i) {char e exp[i];if (pri.find(e) pri.end()) { //当前字符不是运算符则切割数字_data.push(stringtonum(i));} else if (e () {_operator.push(();} else if (e )) {while (_operator.top() ! () {calculate();}_operator.pop();} else {//当前运算符优先级栈顶运算符优先级则出栈计算while (!_operator.empty() pri[_operator.top()] pri[e] _operator.top() ! () {calculate();}_operator.push(e);}}while (!_operator.empty()) {calculate();}cout _data.top() endl;
}
5. 平衡二叉搜索树——AVL树、红黑树 若将关键字1234567 依次插入到初始为空的平衡二叉树 T 中则 T 中平衡因子为 0 的分支结点的个数是 A. 0 B. 1 C. 2 D. 3 答案D 分支节点不包含叶子节点 6. 优先级队列堆 下述二叉树中哪一种满足性质从任一结点出发到根的路径上所经过的结点序列按其关键字有序 A. 二叉排序树错误 B. 哈夫曼树 C. AVL树 D. 堆 答案D
知识点小根堆与大根堆详细看数据结构一、1.2节
7. 哈希表 采用哈希表组织100万条记录以支持字段A快速查找则 A. 理论上可以在常数时间内找到特定记录错误发生哈希冲突 B. 所有记录必须存在内存中 C. 拉链式哈希曼最坏查找时间复杂度是On D. 哈希函数的选择跟A无关 答案C
