资源描述：
《计算机水平考试-软件设计师分类模拟题数据结构与算法(三)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、软件设计师分类模拟题数据结构与算法（三）23的5个叶子结点构造的哈夫曼树为1，其带权路径长度为2o2、3、12,15,6,1>栈是一种按''后进先出〃原则进行插入和删除操作的数据结构，因此单项选择题由权值为29,必须用栈。A.实现函数或过程的递归调用及返回处理时B.将一个元素序列进行逆置时C.链表结点的申请和释放D.可执行程序的装入和卸载4、求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按的顺序求源点到各顶点的最短路径的。A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增5、若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结
2、点)时，。A.插入和删除操作的时间复朵度都为0(1)B.插入和删除操作的时间复杂度都为0(n)C.插入操作的时间复杂度为0(1),删除操作的时间复杂度为0(n)D.插入操作的吋间复杂度为0(n),删除操作的时间复杂度为0(1)6、与逆波兰式ab+-c*d-对应的中缀表达式是A.a-b-c*dB.-(a+b)*c-dC.-a+b*c-dD.(a+b)*(-c-d)7、表达式(a-b)*(c+5)的后缀表示是A.abc5+*-B.ab-c+5*C.abc-*5+D.ab-c5+*利用贪心法求解0-1背包问题时，8能够确保获得最优解。用动态规划方法求解背包问题时，将''用前i个物品来装容量是X的
3、背包〃的背包问题记为KNAP(1,i,X),设：(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为叫和pjj=l〜n)。则依次求解f0(X)4,f2(X),fn(X)的过程中使用的递推关系式为9o8、A.优先选取重量最小的物品B.优先选取效益最大的物品C.优先选取单位重量效益最大的物品D.没有任何准则9、A.f.(X)=min{f(X),f.^(X)+p.}B・f.(X)=max{fi_1(X),f._x(X-W.)+p.}C.fi(X)=min{f._x(X-W.),(X-WJ+p.}D.f.(X)=max{fi_1(X-WJ,f.^(X)+pj1
4、0、分治算法设计技术oA.一般由三个步骤组成：问题划分、递归求解、合并解B.一定是用递归技术来实现C.将问题划分为k个规模相等的子问题D.划分代价很小而合并代价很大1K一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通过将已经实现的基本操作执行冇限次来实现。这句话说明算法具冇特性。A.有穷性B.可行性C.确定性D.健壮性12＞若总是以待排序列的第一个元素作为基准元素进行快速排序，那么在最好情况下的时间复杂度为。A.0(log2n)B.0(n)C・0(n；Log2n)D・0(r?)13、设循环队列Q的定义中冇rear和Mn两个域变量，其中氓ar表示队尾元素的指针，Mn表示队
5、A.实现函数或过程的递归调用及返回处理时B.将一个元素序列进行逆置时C.链表结点的申请和释放D.可执行程序的装入和卸载4、求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按的顺序求源点到各顶点的最短路径的。A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增5、若对一个链表最常用的操作是在末尾插入结点和删除尾结点，则采用仅设尾指针的单向循环链表(不含头结点)时，。A.插入和删除操作的时间复朵度都为0(1)B.插入和删除操作的时间复杂度都为0(n)C.插入操作的时间复杂度为0(1),删除操作的时间复杂度为0(n)D.插入操作的吋间复杂度为0(n),删除操作的时间复杂度为0(
6、1)6、与逆波兰式ab+-c*d-对应的中缀表达式是A.a-b-c*dB.-(a+b)*c-dC.-a+b*c-dD.(a+b)*(-c-d)7、表达式(a-b)*(c+5)的后缀表示是A.abc5+*-B.ab-c+5*C.abc-*5+D.ab-c5+*利用贪心法求解0-1背包问题时，8能够确保获得最优解。用动态规划方法求解背包问题时，将''用前i个物品来装容量是X的背包〃的背包问题记为KNAP(1,i,X),设：(X)是KNAP(1,i,X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为叫和pjj=l〜n)。则依次求解f0(X)4,f2(X),fn(X)的过程中使用的递
7、推关系式为9o8、A.优先选取重量最小的物品B.优先选取效益最大的物品C.优先选取单位重量效益最大的物品D.没有任何准则9、A.f.(X)=min{f(X),f.^(X)+p.}B・f.(X)=max{fi_1(X),f._x(X-W.)+p.}C.fi(X)=min{f._x(X-W.),(X-WJ+p.}D.f.(X)=max{fi_1(X-WJ,f.^(X)+pj10、分治算法设计技术oA.一般由三个步骤组成：问题
