下载文档原格式
2022年职业考证-软考-软件设计师考试全真模拟易错、难点剖析B卷（带答案）一.综合题(共15题)1.单选题为了实现多级中断，保存程序现场信息最有效的方法是使用（）。
问题1选项A.通用寄存器B.累加器C.堆栈D.程序计数器【答案】C【解析】本题考查的是中断相关概念。
在中断过程中，程序现场信息保存在堆栈部分。
本题选择C选项。
通用寄存器、累加器、程序计数器都是属于CPU内部的子部件，与本题无关。
2.案例题【说明】希尔排序算法又称最小增量排序算法，其基本思想是：步骤1：构造一个步长序列delta1、delta2…、deltak，其中delta1=n/2，后面的每个delta是前一个的1/2 ， deltak=1；步骤2：根据步长序列、进行k趟排序；步骤3：对第i趟排序，根据对应的步长delta，将等步长位置元素分组，对同一组内元素在原位置上进行直接插入排序。
【C代码】下面是算法的C语言实现。
（1）常量和变量说明data：待排序数组data，长度为n，待排序数据记录在data[0]、data[1]、…、data[n-1]中。
n：数组a中的元素个数。
delta：步长数组。
（2）C程序#includevoid shellsort(int data[ ], int n){int *delta,k,i,t,dk,j;k=n;delta=(int *)nalloc(sizeof(int)*(n/2));if(i=0)do{( 1 ) ;delta[i++]=k;}while ( 2 ) ;i=0;while((dk=delta[i])>0){for(k=delta[i];k=0&&t【问题1】（8分）根据说明和c代码，填充c代码中的空（1）~ （4）。
【问题2】（4分）根据说明和c代码，该算法的时间复杂度（5）O(n2) （小于、等于或大于）。
该算法是否稳定（6）（是或否）。
【问题3】（3分）对数组（15、9、7、8、20、-1、 4）用希尔排序方法进行排序，经过第一趟排序后得到的数组为（7）。
利用栈来实现算术表达式求值的算法利用栈来实现算术表达式求值的算法算术表达式是指按照一定规则组成的运算式，包含数字、运算符和括号。
在计算机中，求解算术表达式是一项基本的数学运算任务。
根据算术表达式的性质，我们可以考虑利用栈这一数据结构来实现求值算法。
一、算法思路首先，我们需要明确一个重要概念——逆波兰表达式（ReversePolish notation）。
逆波兰表达式是一种没有括号的算术表达式，其运算规则是先计算后面的数字和运算符，再计算前面的数字和运算符。
例如，对于算术表达式“3+4*5-6”，其对应的逆波兰表达式为“3 45 * +6 -”。
那么，我们可以利用栈来实现将中缀表达式转化为逆波兰表达式的过程，具体步骤如下：1. 创建两个栈——操作数栈和操作符栈。
2. 从左到右扫描中缀表达式的每一个数字和运算符，遇到数字则压入操作数栈中，遇到运算符则进行如下操作：（1）如果操作符栈为空或当前运算符的优先级大于栈顶运算符的优先级，则将当前运算符压入操作符栈中。
（2）如果当前运算符的优先级小于或等于栈顶运算符的优先级，则将栈顶运算符弹出并加入操作数栈中，重复此过程直到遇到优先级较低的运算符或操作符栈为空为止，然后将当前运算符压入操作符栈中。
3. 扫描完中缀表达式后，若操作符栈不为空，则将其中所有运算符弹出并加入操作数栈中。
4. 最终，操作数栈中存放的就是逆波兰表达式，我们可以按照逆波兰表达式的计算规则来计算其结果。
二、算法优点利用栈来实现算术表达式求值的算法具有以下优点：1. 代码简洁易懂，易于实现和维护。
2. 由于将中缀表达式转化为逆波兰表达式后，可以减少运算符的优先级关系而消除括号，从而减少求值的复杂度，提高程序的执行效率。
三、代码实现下面是利用栈来实现算术表达式求值的算法的Python代码实现：```pythonclass Stack:def __init__(self):self.items = []def push(self, item):self.items.append(item)def pop(self):return self.items.pop()def peek(self):return self.items[-1]def is_empty(self):return len(self.items) == 0def size(self):return len(self.items)def calculate(op_num1, op_num2, operator):if operator == "+":return op_num1 + op_num2elif operator == "-":return op_num1 - op_num2elif operator == "*":return op_num1 * op_num2elif operator == "/":return op_num1 / op_num2def infix_to_postfix(infix_expr):opstack = Stack()postfix_expr = []prec = {"+": 1, "-": 1, "*": 2, "/": 2, "(": 0} token_list = infix_expr.split()for token in token_list:if token.isdigit():postfix_expr.append(token)elif token == '(':opstack.push(token)elif token == ')':top_token = opstack.pop()while top_token != '(':postfix_expr.append(top_token)top_token = opstack.pop()else:while (not opstack.is_empty()) and(prec[opstack.peek()] >= prec[token]):postfix_expr.append(opstack.pop())opstack.push(token)while not opstack.is_empty():postfix_expr.append(opstack.pop())return " ".join(postfix_expr)def postfix_eval(postfix_expr):opstack = Stack()token_list = postfix_expr.split()for token in token_list:if token.isdigit():opstack.push(int(token))else:op_num2 = opstack.pop()op_num1 = opstack.pop()result = calculate(op_num1, op_num2, token) opstack.push(result)return opstack.pop()infix_expr = "3 + 4 * 5 - 6"postfix_expr = infix_to_postfix(infix_expr)print(postfix_expr)print(postfix_eval(postfix_expr))```四、总结算术表达式求值是一项常见的数学运算任务，利用栈这一数据结构来实现求值算法是一种简单有效的方法，它将中缀表达式转化为逆波兰表达式后，可以消除括号并减少运算符的优先级关系，从而提高程序的执行效率。
利用主方法解递归方程主方法是解决递归方程的一种常用技巧。
它能够运用递归公式的形式特征，使得复杂的递归方程可以转化为易于求解的简单公式。
主方法的核心思想是通过确定递归方程的特征参数来求解递归公式。
主方法需要满足两个条件：首先，必须能将递归方程拆分为两个公式，一般为$f(n)=af(\frac{n}{b})+T(n)$；其次，$T(n)$需要满足一定的算法复杂度条件。
在实际应用中，主方法可以分为三种形式：主方法一、主方法二和主方法三。
主方法一适用于递归层数比较少的情况下，递归深度为$log_b n$。
主方法二适用于递归层数比较深的情况下，递归深度为$n^c$。
主方法三适用于递归层数较深、但 $T(n)$增长率比较特殊的情况。
以下是主方法的具体应用实例。
主方法一：对于递归公式 $f(n)=2f(\frac{n}{2})+n$，其中 $a=2，b=2$，$T(n)=n$。
根据主方法一的公式，可得到$f(n)=\Theta(n\log n)$。
主方法二：对于递归公式 $f(n)=f(\frac{2}{3}n)+1$，其中$a=1,b=\frac{3}{2}$。
根据主方法二的公式，可得到$f(n)=\Theta(1)$。
主方法三：对于递归公式 $f(n)=4f(\frac{n}{2})+n^2\log n$，其中$a=4,b=2$，$T(n)=n^2\log n$。
根据主方法三，将$\log_a b$的值代入公式，可得到$f(n)=\Theta(n^2\log^2n)$。
综上所述，主方法是一种简单易行的递归求解方法。
对于常见的递归问题，我们可以根据实际情况选择合适的主方法，并结合数学知识来求解递归方程，从而得到更为精确的结果。
算法设计与分析复习题目及答案分治法1、二分搜索算法是利用（分治策略）实现的算法。
9. 实现循环赛日程表利用的算法是（分治策略）27、Strassen矩阵乘法是利用（分治策略）实现的算法。
34．实现合并排序利用的算法是（分治策略）。
实现大整数的乘法是利用的算法（分治策略）。
17．实现棋盘覆盖算法利用的算法是（分治法）。
29、使用分治法求解不需要满足的条件是（子问题必须是一样的）。
不可以使用分治法求解的是（0/1背包问题）。
动态规划下列不是动态规划算法基本步骤的是（构造最优解）下列是动态规划算法基本要素的是（子问题重叠性质）。
下列算法中通常以自底向上的方式求解最优解的是（动态规划法）备忘录方法是那种算法的变形。
（动态规划法）最长公共子序列算法利用的算法是（动态规划法）。
矩阵连乘问题的算法可由（动态规划算法B）设计实现。
实现最大子段和利用的算法是（动态规划法）。
贪心算法能解决的问题：单源最短路径问题，最小花费生成树问题，背包问题，活动安排问题，不能解决的问题：N皇后问题，0/1背包问题是贪心算法的基本要素的是（贪心选择性质和最优子结构性质）。
回溯法回溯法解旅行售货员问题时的解空间树是（排列树）。
剪枝函数是回溯法中为避免无效搜索采取的策略回溯法的效率不依赖于下列哪些因素（确定解空间的时间）分支限界法最大效益优先是（分支界限法）的一搜索方式。
分支限界法解最大团问题时，活结点表的组织形式是（最大堆）。
分支限界法解旅行售货员问题时，活结点表的组织形式是（最小堆）优先队列式分支限界法选取扩展结点的原则是（结点的优先级）在对问题的解空间树进行搜索的方法中,一个活结点最多有一次机会成为活结点的是( 分支限界法).从活结点表中选择下一个扩展结点的不同方式将导致不同的分支限界法,以下除( 栈式分支限界法)之外都是最常见的方式.（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。
2022年华中科技大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。
A.NB.2N-1C.2ND.N-12、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序3、算法的计算量的大小称为计算的（）。
A.效率B.复杂性C.现实性D.难度4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。
A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。
A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、下列二叉排序树中查找效率最高的是（）。
第三课栈、队列和数组一选择题1．对于栈操作数据的原则是（）。
A．先进先出B．后进先出C．后进后出D．不分顺序2．一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。
A．不确定B．n-i+1 C．i D．n-i3．若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。
A．i-j-1 B．i-j C．j-i+1 D．不确定的4．设abcdef以所给的次序进栈，若在进栈操作时，允许出栈操作，则下面得不到的出栈序列为（）。
A．fedcba B．bcafed C．dcefba D．cabdef5．输入序列为ABC，可以变为CBA时，经过的栈操作为（）A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,popC．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop6．若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（）。
A．top=top+1; V[top]=x B．V[top]=x; top=top+1C．top=top-1; V[top]=x D．V[top]=x; top=top-17．若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈(i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（）。
A．|top[2]-top[1]|==0 B．top[1]+1==top[2] C．top[1]+top[2]==m D．top[1]==top[2]8．执行完下列语句段后，i值为：（）。
int f(int x){ return ((x>0) ? x* f(x-1):2);}int i;i =f(f(1));A．2 B．4 C．8 D．无限递归9．表达式a*(b+c)-d的后缀表达式是（）。
信息科学技术学院
程序设计实习
郭炜微博 /guoweiofpku
/u/3266490431
刘家瑛微博 /pkuliujiaying
信息科学技术学院《程序设计实习》郭炜刘家瑛用栈替代递归
汉诺塔问题
古代有一个梵塔，塔内有三个座A、B、C，A座上有64个盘子，盘子大小不等，大的在下，小的在上（如图）。
有一个和尚想把这64个盘子从A座移到B座，但每次只能允许移动一个盘子，并且在移动过程中，3个座上的盘子始终保持大盘在下，小盘在上。
在移动过程中可以利用B座，要求输出移动的步骤。
汉诺塔问题递归解法
#include <iostream>
using namespace std;
void Hanoi(int n, char src,char mid,char dest)
//将src座上的n个盘子，以mid座为中转，移动到dest座
{
if( n == 1) { //只需移动一个盘子
cout << src << "->" << dest << endl; //直接将盘子从src移动到dest即可
return ; //递归终止
}
Hanoi(n-1,src,dest,mid); //先将n-1个盘子从src移动到mid
cout << src << "->" << dest << endl; //再将一个盘子从src移动到dest
Hanoi(n-1,mid,src,dest); //最后将n-1个盘子从mid移动到dest
return ;
}
汉诺塔问题递归解法int main()
{
int n;
cin >> n; //输入盘子数目
Hanoi(n,'A','B','C');
return 0;
}
汉诺塔问题手工解法(三个盘子）信封堆,每个信封放一个待解决的问题
汉诺塔问题非递归解法
#include <iostream>
#include <stack>
using namespace std;
struct Problem {
int n;
char src,mid,dest;
Problem( int nn, char s,char m,char d) :n(nn),src(s),mid(m),dest(d) { } }; //一个Problem变量代表一个子问题，将src上的n个盘子，
// 以mid为中介，移动到dest
stack<Problem> stk; //用来模拟信封堆的栈，一个元素代表一个信封 //若有n个盘子，则栈的高度不超过 n * 3
int main() {
int n; cin >> n;
stk.push(Problem(n,‘A’,‘B’,‘C’)); //初始化了第一个信封
while( ! stk.empty()) { //只要还有信封，就继续处理
Problem curPrb = stk.top(); //取最上面的信封，即当前问题
stk.pop(); // 丢弃最上面的信封
if( curPrb.n == 1 ) cout << curPrb.src << "->" << curPrb.dest << endl ;
else { //分解子问题
//先把分解得到的第3个子问题放入栈中
stk.push(Problem(curPrb.n -1,curPrb.mid,curPrb.src,curPrb.dest));
//再把第2个子问题放入栈中
stk.push(Problem(1,curPrb.src,curPrb.mid,curPrb.dest));
//最后放第1个子问题，后放入栈的子问题先被处理
stk.push(Problem(curPrb.n -1,curPrb.src,curPrb.dest,curPrb.mid));
}
}
return 0;
void Hanoi(int n, char src,char mid,char dest) {
if( n == 1) {
(0)cout << src << "->" << dest << endl;
return ;
}
Hanoi(n-1,src,dest,mid);
(2)cout << src << "->" << dest << endl;
Hanoi(n-1,mid,src,dest);
(3)return ;
} int main() {
int n;
cin >> n;
Hanoi(n,'A','B','C');
(1) return 0;
}
编译器生成的代码自动维护一个问题的栈，相当于信封
堆。
栈里每个子问题的描述中多了一项 --- 返回地址，返
回地址可以描述该子问题已经解决到哪个步骤了，下面
的(0) (1),(2),(3)就是返回地址
main中调用Hanoi时，栈形成初
始状态：
n A B C 1
n = 3时，栈的变化状态:
3 A B C 1 3 A B C 1 2 A C B 2 3 A B C 1 2 A C B 2 1 A B C 2 0 A->C
3 A B C 1 2 A C B 2 2 A->B 3 A B C 1
2 A C B 2 1 C A B 3
0 C->B 2 A->C 3 A B C 1 2 B A C 3 3 A B C 1 2 B A C 3 1 B C A 2 0 B->A 2 B->C 3 A B C 1 2 B A C 3
1 A B C 3
0 A->C
3 A B C 1 2 B A C 3 3 A B C 1
void Hanoi(int n, char src,char mid,char dest) { if( n == 1) { (0)cout << src << "->" << dest << endl; return ; } Hanoi(n-1,src,dest,mid); (2)cout << src << "->" << dest << endl; Hanoi(n-1,mid,src,dest);
(3)return ;
int main() {
int n;
cin >> n; Hanoi(n,'A','B','C');
(1) return 0;
}。
