2025秋数算A 1-6章书面作业 • Cxxdgc's Site

第一章#

第二章#

1.#

双向循环列表中删除节点p的操作伪代码

p->prev->next = p->next;
p->next->prev = p->prev;
delete p;

plaintext

2.#

原地删除数组中重复出现的元素

void deletesamenumber(vector<int> arr){
    if (arr.empty()){
        return;
    }
    int low = 0;
    for (int high = 1; high<arr.sizes();high++){
        if (arr[high] != arr[low]{
            low++;
            arr[low] = arr[high];
        })
    }
    return
}

plaintext

3.#

判断有头单向链表是否含有环

template <class T>
T* ifroll(T* head){
    T* high = head;
    T* low = head;
    if (head = nullptr){
        return nullptr;
    }
    while (True){
        if (high && high->next && high->next->next){
            high = high->next->next;
            low = low->next;
            if (high == low){
                break;
            }
        }
        else{
            return nullptr;
        }
    }
    low = head;
    while (high != low){
        low = low->next;
        high = high->next;
    }
    return low;
}

plaintext

第三章#

记入栈操作为1，出栈操作为-1。合法的序列要求序列部分和始终大于等于0。在不考虑合法性的情况下，共有 $C_{ 2n}^{n}$ 种排列。考虑不合法的序列，不合法的序列中必出现一个前缀序列，该序列和为-1。将该前缀序列反转，则新序列中会出现n+1个1和n-1个-1，这共有 $C_{ 2n}^{n+1}$ 种排列。故而，合法的排列共有 $C_{ 2n}^{n} - C_{ 2n}^{n+1}$ 种，即 $\frac{C_{ 2n}^{n} }{n+1}$ 种排列。

3#

1.#

撤销操作

S2.push(S1.top());
S1.pop();

plaintext

恢复操作

S1.push(S2.top());
S2.pop();

plaintext

2.#

S1:A,B,D（右侧为栈顶）

S2:C（右侧为栈顶）

4#

1.#

思路：使用一个队列来保存。当执行压栈操作时，将压入的元素插入另一个队列的队尾，并将本队列元素一次插入另一个队列的队尾即可。出栈和判断是否为空操作直接进行即可

push(x)的伪代码

if (isEmpty(Q2) && !isEmpty(Q1)){
    enQueue(Q2,x);
    while (!isEmpty(Q1)){
        enQueue(Q2,deQueue(Q1));
    }
}
else if (isEmpty(Q1) && !isEmpty(Q2)){
    enQueue(Q1,x);
    while (!isEmpty(Q2)){
        enQueue(Q1,deQueue(Q2));
    }
}
else{
    cout<<"错误"<<endl;
}

plaintext

pop(x)伪代码

if (!isEmpty(Q1) && isEmpty(Q2)){
    deQueue(Q1);
}
else if (!isEmpty(Q2) && isEmpty(Q1)){
    deQueue(Q2);
}
else{
    cout<<"错误"<<endl;
}

plaintext

2.#

push(x)操作中需要将已有元素全部转移到另一个队列中，故时间复杂度为O(n)

pop(x)操作则直接借助队列弹出操作实现，时间复杂度为O(1)

3.#

push(1)
push(2)
push(3)
pop()   // 返回3
push(4)
pop()   // 返回4
pop()   // 返回2

plaintext

第四章#

1#

对于模式P=ababaca而言，其KMP算法的next数组为[-1,0,0,1,2,3,0]，而有限自动机通过状态匹配来确定，此处构造一个有限自动机的状态转移表

状态	a	b	c
状态0（起始状态）	a→1	b→0	c→0
状态1	a→1	b→2	c→0
状态2	a→3	b→2	c→0
状态3	a→3	b→4	c→0
状态4	a→5	b→4	c→0
状态5	a→1	b→0	c→6
状态6	a→7	b→2	c→0
状态7（接受状态）	a→1	b→2	c→0

联系：二者在运行时均利用前缀后缀信息优化了匹配过程。有限状态自动机根据状态转移表依据现有状态和输入进行状态转移，达到下一个状态，当达到接受状态后即判别为真。而KMP算法中的next数组与有限状态机的状态转移在原理上来说是相同的，其设置k=next[k]这一过程即相当于有限状态自动机中的状态转移过程。

区别：有限状态自动机需要维护一个庞大的状态转移表，而DMP算法仅需维护一个简单的next数组，在输入可能性较多时，DMP算法将相较于有限状态自动机产生巨大的优势，即DMP算法能够更好的适应我们日常处理中字符集较大的情景。

2#

str = input()
p1,p2 = 0,-1
start = 0
len = 0
dic = {}
while (p2<len(str)-1):
    p2+=1
    if (str[p2] not in dic.keys()):
        dic[str[p2]] == p2
        if (p2 - p1 + 1 > len):
            len = p2 - p1 + 1
            start = p1
    else:
        if (dic[str[p2]] >= p1):
            p1 = dic[str[p2]]+1
        dic[str[p2]] = p2 
print(str[start:start+len],start)

python

3#

思路#

使用双指针从左向右遍历，指针i表示现在扫到的位置，指针j表示新字符串当前写到的位置。j<=i恒成立。扫到b则不写入，扫到c则检查j-1是否为a，若是则j-1删除a。

伪代码#

string str = "acbac";
int i=0,j=0;
while(i<str.length()){
    if (str[i]=='b'){
        i++;
    }
    else if (str[i] == 'c' && j>=1 && str[j-1]=='a'){
        j--;
        i++;
    }
    else{
        str[j] = str[i];
        i++;
        j++;
    }
}
return str,j

plaintext

时间复杂度分析#

该算法仅遍历字符串一次，遍历的时间复杂度为O(n),而单次遍历内部复杂度均为常数，故总时间复杂度为O(n)。

4#

思路说明#

首先计算出模式字符串P的next数组，随后利用与KMP算法中相同的方法匹配字符串，不过此时对相应短字符串位置进行记录。

伪代码#

// 计算next数组
string P;
int next[m];
next[0] = -1;
int i, k;
i = 0;
k = -1;
while (i<m-1){
    while (k>=0 && P[i]!=P[k]){
        k = next[k];
    }
    i++;
    k++;
    next[i] = k;
}

// 进行匹配
string T;
int first_pos[m+1] = 0;
for (int i=0;i<m+1;i++){
    first_pos = -1;
}
int j = 0;
i = 0;
while (j<m && i<n){
    while (j>0 && T[i]!=P[j]){
        j = next[j];
    }
    if (t[i]==p[j]){
        j = j+1;
        if (first_pos[j] == -1){
            first_pos[j] = i - j + 1;
        }
    }
    // 搜索到完成匹配字符串后说明已经有所有前缀，退出
    if (j==m){
        break;
    }
    i++;
}

return first_pos;

plaintext

第五章#

第五章张铭班补充作业#

1#

二叉树打印中缀表达式

#include <iostream>
using namespace std;

bool getFirst(string op) {
	if (op == "+" || op == "-") {
		return 1;
	}
	else if (op == "*" || op == "/") {
		return 2;
	}
	return 0;
}

template <class T>
void printbds(BinaryTreeNode<T>* p, int temp) {
	if (p->left == nullptr && p->right == nullptr) {
		cout << p->content;
		return;
	}
	else if (p->left == nullptr || p->right == nullptr) {
		cout << endl;
		cout << "检测到非法表达式！" << endl;
		return;
	}
	int temp_1;
	bool flag = false;
	temp_1 = getFirst(p->content);
	if (temp_1 < temp) {
		flag = true;
		cout << "(";
	}
	printbds(p->left, temp_1);
	cout << p->content;
	printbds(p->right, temp_1);
	if (flag) {
		cout << ")";
	}
	return;
};

template <class T>
void Expression(BinaryTreeNode<T>* root) {
	if (root == nullptr) {
		return;
	}
	printbds(root, 0);
	return;
};

plaintext

2#

BST删除节点

template <class T>
void BinarySearchTree<T>::removeVal(BinaryTreeNode <T>*& rt, const T val) {
	if (rt->left == nullptr && rt->right == nullptr) {
		rt = nullptr;
		return;
	}
	else if (rt->left = nullptr) {
		rt = rt->right;
		return;
	}
	else if (rt->right = nullptr) {
		rt = rt->left;
		return;
	}
	else {
		BinaryTreeNode <T>* p1, p2;
		p1 = rt->right;
		if (p1->left == nullptr) {
			p1->left = rt->left;
			rt = p1;
			return;
		}
		p2 = p1->left;
		while (p2->left != nullptr) {
			p1 = p2;
			p2 = p1->left;
		}
		if (p2->right != nullptr) {
			p1->left = p2->right;
		}
		p2->right = rt->right;
		p2->left = rt->left;
		rt = p2;
		return;
	}
}

plaintext

3#

判断二叉树是否为堆

const int treesize = 1145141919810;
const int array[1145141919810] = { ........ };

template <class T>
bool MinHeap<T>::Isheap(int position,bool flag_small) {
	if (position >= treesize || position < 0) {
		return false;
	}

	int temp;
	// 左节点
	temp = 2 * position + 1;
	bool flag = true;
	if (temp >= treesize) {
		return true;
	}
	else {
		if (flag_small) {
			if (array[temp] < array[position]) {
				return false;
			}
			else {
				flag = Isheap(temp, flag_small);
				if (!flag) {
					return flag;
				}
			}
		}
		else {
			if (array[temp] > array[position]) {
				return false;
			}
			else {
				flag = Isheap(temp, flag_small);
				if (!flag) {
					return flag;
				}
			}
		}
	}
	// 右节点
	temp = 2 * position + 2;
	if (temp >= treesize) {
		return flag;
	}
	else {
		if (flag_small) {
			if (array[temp] < array[position]) {
				return false;
			}
			else {
				flag = Isheap(temp, flag_small);
				if (!flag) {
					return flag;
				}
			}
		}
		else {
			if (array[temp] < array[position]) {
				return false;
			}
			else {
				flag = Isheap(temp, flag_small);
				if (!flag) {
					return flag;
				}
			}
		}
	}
	return flag;
}

plaintext

第六章#

1#

树形表示法和括号表示法：

       A
     / | \	  
    B  C  D
   / \    |
  E   F   G
 / \  |
H  I  J

plaintext

(A(B(E(H)(I))(F(J)))(C)(D(G)))

求高度和高度伪代码

高度为4

def getheight(node* parent)->int:
	if (child == None):
		return 1
	max_height = 1
	for x in child:
		max_height = max(max_height,getheight(x))

	return max_height

python

转换为二叉树和前序序列

   A
   |
   B
  / \
 E   C
/ \   \
H  F   D
\  /   /
I J   G

plaintext

先序遍历：ABEHIFJCDG

2#

由 $\sum_{i=0}^{L-1}K^{i} = \frac{1-K^{L} }{1-K}$ 知，当L=1时，为单根树，N=1。当L不为1时，N的取值范围为 $(\frac{1-K^{L-1} }{1-K},\frac{1-K^{L} }{1-K}]$ 。

$\left \lceil \frac{n-1}{K} \right \rceil$

$K(n-1)+i+1$

n%k!=1时有右兄弟。右兄弟编号为n+1。

3#

[2,2,2,4,2,2,2,2,7,9]

plaintext

根据按规模合并的规则，在合并过程中，只有在较小树中的节点，其节点深度会增加1，较大树中的节点深度则不变。由于较大树的节点多于较小树的节点，故在合并前后对较小树而言其节点数至少翻倍。故一个节点最多在较小树中被合并 $log_{2}N$ 次，故树的高度为 $O(log N)$ 。

第六章补充习题#

1#

森林镜面映射

#include <vector>
template <class T>
void MirrorReverse(TreeNode<T>* root) {
	if (root == nullptr) {
		return;
	}
	TreeNode<T>* p1 = root;
	vector<TreeNode<T>*> tmp;
	while (p1) {
		tmp.push_back(p1);
		MirrorReverse(p1->left);
		p1 = p1->right;
	}
	auto p = tmp.end()-1;
	while (true) {
		if (p == tmp.begin()) {
			(*p)->right = nullptr;
			break;
		}
		(*p)->right = *(p - 1);
		p--;
	}
}

plaintext

2#

输出先根序列

int i = -1;
template<class T>
void ltagrlink_Seq(LtagRlinkTreeNode<T>* nodeArray, LtagRlinkTreeNode<T>* root, int parent = -1) {
    if (root == nullptr) return;
    i++;
    cout << root->info << " ";
    nodeArray[i][0] = parent;
    nodeArray[i][1] = root->info;
    if (root->left == nullptr) {
        nodeArray[i][2] = 1;
    }
    else {
        nodeArray[i][2] = 0;
        ltagrlink_Seq(nodeArray, root->left,i);
    }
    ltagrlink_Seq(nodeArray, root->right,parent);
}

plaintext