发帖
雷达卡
历年东北大学计算机复试上机真题解析
以下为部分经典机试题目整理与说明，涵盖数据结构与算法常见考点。
出栈入栈序列合法性判断
题目描述：
Time Limit: 1000 ms
Memory Limit: 256 mb
设计一个算法，用于判定由字符'A'和'D'组成的字符串是否构成合法的入栈出栈序列。其中，'A'表示入栈操作，'D'表示出栈操作，字符串仅包含这两个字符。初始时栈为空。例如，序列“ADAADDDD”是非法的，而“ADAADDAD”是合法的。
输入格式：
输入一行字符串，仅包含字符'A'和'D'。
输出格式：
若序列为合法序列，输出“yes”；否则输出“no”。
样例输入：
复制
ADAADDDD
样例输出：
复制
no
K上升段问题
该题型通常要求在给定数组中寻找满足特定条件的连续子段数量或最长子段长度，其中“K上升段”指子段内至多允许K个非递增位置，其余均为严格递增关系。具体实现需结合滑动窗口或动态规划策略进行处理。
连通数计算
题目一般给出一个有向图的邻接矩阵，要求统计图中所有可达点对的数量，即满足从顶点i可以到达顶点j（i≠j）的有序对(i,j)总数。常用解法包括Floyd算法传递闭包或多次DFS/BFS遍历求解。
判断二叉树是否对称
给定一棵二叉树的结构，要求编写程序判断其是否为镜像对称（即关于根节点左右对称）。可通过递归方式比较左子树与右子树的对应节点值及其子结构，也可使用队列进行层序遍历比对实现非递归判断。
京公网安备 11010802022788号
