软件设计师数据结构与算法(一).pdf

《软件设计师数据结构与算法(一).pdf》由会员分享，可在线阅读，更多相关《软件设计师数据结构与算法(一).pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 模拟 软件设计师数据结构与算法(一)选择题第 1 题：循环链表的主要优点是 _。A.不再需要头指针了B.已知某个结点的位置后，能很容易找到它的直接前驱结点C.在进行删除操作后，能保证链表不断开D.从表中任一结点出发都能遍历整个链表参考答案：D 第 2 题：表达式 a*(b+c)-d的后缀表达式为 _。A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd 参考答案：B 第 3 题：若二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则其后序遍历序列为_。A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 参考答案：D 第 4 题：无向图中

2、一个顶点的度是指图中_。A.通过该顶点的简单路径数B.通过该顶点的回路数C.与该顶点相邻的顶点数2 D.与该顶点连通的顶点数参考答案：C 第 5 题：利用逐点插入法建立序列(50，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素30 要进行 _次元素间的比较。A.4 B.5 C.6 D.7 参考答案：B 第 6 题：在常用的描述二叉排序树的存储结构中，关键字值最大的结点_。A.左指针一定为空B.右指针一定为空C.左、右指针均为空D.左、右指针均不为空参考答案：B 第 7 题：一个具有 n(n0)个顶点的连通无向图至少有_条边。A.n+1 B.n C.n/2

3、D.n-1 参考答案：D 第 8 题：由权值为 9，2，5，7 的 4 个叶子结点构造一棵哈夫曼树，该树的带权路径长度为_。A.23 3 B.37 C.44 D.46 参考答案：C 第 9 题：在最好和最坏情况下的时间复杂度均为O(nlog2n)且稳定的排序方法是_。A.基数排序B.快速排序C.堆排序D.归并排序参考答案：D 第 10 题：己知一个线性表(38，25，74，63，52，48)，假定采用散列函数h(key)=key%7 计算散列地址，并散列存储在散列表A0，6 中，若采用线性探测方法解决冲突，则在该散列表上进行等概率成功查找的平均查找长度为_。A.1.5 B.1.7 C.2.0

4、D.2.3 参考答案：C 为了在状态空间树中(11)，可以利用 LC-检索(Least Cost Search)快速找到一个答案结点。在进行LC-检索时，为避免算法过分偏向于纵深检查，应该(12)。第 11 题：A.找出任一个答案结点B.找出所有的答案结点C.找出最优的答案结点D.进行遍历参考答案：C 4 第 12 题：A.B.C.D.参考答案：D 第 13 题：以比较为基础的排序算法在最坏情况下的计算时间下界为_。A.O(n)B.O(n2)C.O(log2n)D.O(nlog2n)参考答案：D 第 14 题：利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest

5、 path problem)时，设有向图 G=V,E共有 n 个结点，结点编号1n，设 C是G的成本邻接矩阵，Dk(i,j)即为图 G中结点 i 到 j 并且不经过编号比 k 还大的结点的最短路径长度(Dn(i,j)即为图 G中结点 i 到 j的最短路径长度)，则求解该问题的递推关系式为_。A.Dk(i,j)=Dk-1(i,j)+C(i,j)B.Dk(i,j)=minDk-1(i,j),Dk-1(i,j)+C(i,j)5 C.Dk(i,j)=Dk-1(i,k)+Dk-1(k,j)D.Dk(i,j)=minDk-1(i,j),Dk-1(i,k)+Dk-1(k,j)参考答案：D 在活动图中，结点表

6、示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图 1-1 中，从 A到 J 的关键路径是(15)，关键路径长度是(16)，从 E开始的活动启动的最早时间是(17)。第 15 题：A.ABEGJ B.ADFHJ C.ACFGJ D.ADFIJ 参考答案：B 第 16 题：A.22 B.49 C.19 D.35 参考答案：B 第 17 题：A.10 B.12 C.13 D.15 参考答案：C 6 第 18 题：已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为_。A.BCDEAF B.ABDCEF C.DBACE

7、F D.DABECF 参考答案：B 第 19 题：在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n 个结点，采用三叉链表存储时，每个结点的数据域需要d 个字节，每个指针域占用 4 个字节，若采用顺序存储，则最后一个结点下标为k(起始下标为 1)，那么_时采用顺序存储更节省空间。A.B.C.D.参考答案：A 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有 n个结点，其邻接矩阵为A1.n，1.n，且压缩存储在B1.k中，则 k 的值至少为(20)。若按行压缩存储对称矩阵的上三角元素，则当n 等于

8、 10 时，7 边(V6，V3)的信息存储在 B (21)中。第 20 题：A.B.C.D.参考答案：D 第 21 题：A.18 B.19 C.20 D.21 参考答案：C 第 22 题：在 11 个元素的有序表 A1.11中进行折半查找（(low+high)/2），查找元素 A11 时，被比较的元素的下标依次是_。A.6，8，10，11 B.6，9，10，11 C.6，7，9，11 D.6，8，9，11 参考答案：B 8 第 23 题：由元素序列(27，16，75，38，51)构造平衡二叉树，则首次出现的最小不平衡子树的根(即离插入结点最近且平衡因子的绝对值为2 的结点)为_。A.27 B.

9、38 C.51 D.75 参考答案：D 第 24 题：若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。_排序是稳定的。设求解某问题的递归算法如下：F(int n)if (n=1)Move(1)；else F(n-1)；Move(n)；F(n-1)；A.归并B.快速C.希尔D.堆参考答案：A 求解该算法的计算时间时，仅考虑算法 Move所做的计算为主要计算，且 Move为常数级算法。则算法F 的计算时间 T(n)的递推关系式为(25)；设算法Move的计算时间为 k，当 n=4时，算法 F 的计算时间为(26)。第 25 题：A.T(n)=T(n-1)+1 B.T(n)=2T

10、(n-1)C.T(n)=2T(n-1)+1 D.T(n)=2T(n+1)+1 9 参考答案：C 第 26 题：A.14k B.15k C.16k D.17k 参考答案：B 利用贪心法求解 0-1 背包问题时，(27)能够确保获得最优解。用动态规划方法求解 0-1 背包问题时，将“用前i 个物品来装容量是X的背包”的 0-1背包问题记为 KNAP(1，i，X)，设 fi(X)是 KNAP(1，i，X)最优解的效益值，第j个物品的重量和放入背包后取得效益值分别为Wj和pj(j=1n)。则依次求解f0(X)4，f1(X)，fn(X)的 过 程 中使 用 的 递推 关 系 式为(28)。第 27 题：

11、A.优先选取重量最小的物品B.优先选取效益最大的物品C.优先选取单位重量效益最大的物品D.没有任何准则参考答案：D 第 28 题：A.fi(X)=minfi-1(X)，fi-1(X)+pi B.fi(X)=maxfi-1(X)，fi-1(X-Wi)+pi C.fi(X)=minfi-1(X-Wi)，fi-1(X-Wi)+pi D.fi(X)=maxfi-1(X-Wi)，fi-1(X)+pi 参考答案：B 10 第 29 题：与逆波兰式 ab+-c*d-对应的中缀表达式是 _。A.a-b-c*d B.-(a+b)*c-d C.-a+b*c-d D.(a+b)*(-c-d)参考答案：B 第 30

12、题：拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，_为图 1-2 所示有向图的一个拓扑序列。A.1 2 3 4 5 6 7 B.1 5 2 6 3 7 4 C.5 1 2 6 3 4 7 D.5 1 2 3 7 6 4 参考答案：B 第 31 题：为了便于存储和处理一般树结构形式的信息，常采用孩子一兄弟表示法将其转换成二又树(左子关系表示父子，右子关系表示兄弟)，与图 1-3 所示的树对应的二叉树是 _。A.B.11 C.D.参考答案：A 第 32 题：给定一个有 n 个元素的有序线性表。若采用顺序存储结构，则在等概率前提下，删除其中的一

13、个元素平均需要移动_个元素。A.(n+1)/2 B.n/2 C.(n-1)/2 D.1 参考答案：C 第 33 题：在平衡二叉树中，_。A.任意结点的左、右子树结点数目相同B.任意结点的左、右子树高度相同C.任意结点的左、右子树高度之差的绝对值不大于1 D.不存在度为 1 的结点参考答案：C 第 34 题：在_存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映射关系。A.顺序(Sequence)B.链表(Link)C.索引(Index)D.散列(Hash)12 参考答案：D 对于求取两个长度为n 的字符串的最长公共子序列(LCS)问题，利用(35)策略可以有效地避免子串最长公共子序列

14、的重复计算，得到时间复杂度为O(n2)的正确算法。串1，0，0，1，0，1，0，1和 0，1，0，1，1，0，1，1的最长公共子序列的长度为(36)。第 35 题：A.分治B.贪心C.动态规划D.分支限界参考答案：C 第 36 题：A.3 B.4 C.5 D.6 参考答案：D 第 37 题：设某算法的计算时间可用递推关系式T(n)=2T(n/2)+n表示，则该算法的时间复杂度为 _。A.O(lgn)B.O(nlgn)C.O(n)D.O(n2)参考答案：B 第 38 题：_在其最好情况下的算法时间复杂度为O(n)。A.插入排序B.归并排序13 C.快速排序D.堆排序参考答案：A 第 39 题：表

15、达式“X=(A+B)(C-D/E)”的后缀表示为 _。A.XAB+CDE/-x=B.XAB-C-DE/x=C.XAB+CDE-/x=D.NAB-CD-E/x=参考答案：A 结点数目为 n的二叉查找树(二叉排序树)的最小高度为(40)，最大高度为(41)。第 40 题：A.n B.n/2 C.log2n D.log2(n+1)参考答案：D 第 41 题：A.n B.n/2 C.log2n D.log2(n+1)参考答案：A 第 42 题：某双向链表中的结点如图1-4 所示，删除 t 所指结点的操作为 _。14 A.t-prior-next=t-next；t-next-prior=t-prior；

16、B.t-prior-prior=t-prior；t-next-next=t-next；C.t-prior-next=t-prior；t-next-prior=t-next；D.t-prior-prior=t-next；t-next-prior=t-prior；参考答案：A 第 43 题：对于二维数组 a0.4，1.5，设每个元素占1个存储单元，且以列为主序存储，则元素 a2，2 相对于数组空间起始地址的偏移量是_。A.5 B.7 C.10 D.15 参考答案：B 第 44 题：对于 n(n0)个元素构成的线性序列L，在_时适合采用链式存储结构。A.需要频繁修改 L 中元素的值B.需要频繁地对

17、L 进行随机查找C.需要频繁地对 L 进行删除和插入操作D.要求 L 存储密度高参考答案：C 第 45 题：求单源点最短路径的迪杰斯特拉(Dijkstra)算法是按 _的顺序求源点到各顶点的最短路径的。A.路径长度递减B.路径长度递增C.顶点编号递减D.顶点编号递增15 参考答案：B 第 46 题：_算法策略与递归技术的联系最弱。A.动态规划B.贪心C.回溯D.分治参考答案：B 对于具有 n 个元素的一个数据序列，若只需得到其中第k 个元素之前的部分排序，最好采用(47)，使用分治(Divide and Conquer)策略的是(48)算法。第 47 题：A.希尔排序B.直接插入排序C.快速排

18、序D.堆排序参考答案：D 第 48 题：A.冒泡排序B.插入排序C.快速排序D.堆排序参考答案：C 第 49 题：表达式“(a+b)*(c-d)”的后缀表示为 _。A.ab+cd-*B.abcd+-*C.ab+*cd-D.abcd*+-16 参考答案：A 第 50 题：输入受限的双端队列是指元素只能从队列的一端输入，但可以从队列的两端输出，如图 1-5 所示。若有 8，1，4，2 依次进入输入受限的双端队列，则得不到输出序列 _。A.2，8，1，4 B.1，4，8，2 C.4，2，1，8 D.2，1，4，8 参考答案：D 第 51 题：已知某二叉树的中序序列为CBDAEFI，先序序列为 ABC

19、DEFI，则该二叉树的高度为_。A.2 B.3 C.4 D.5 参考答案：C 某工程计划如图 1-6 所示，各个作业所需的天数如下表所示，设该工程从第0天开工，则该工程的最短工期是(52)天，作业 J 最迟应在第(53)天开工。第 52 题：A.17 B.18 17 C.19 D.20 参考答案：D 第 53 题：A.11 B.13 C.14 D.16 参考答案：B 第 54 题：在如图 1-7 所示的平衡二叉树(树中任一结点的左右子树高度之差不超过1)中，结点 A的右子树 AR高度为 h，结点 B的左子树 BL高度为 h，结点 C的左子树 CL、右子树 CR高度都为 h-1。若在 CR中插入

20、一个结点并使得CR的高度增加l，则该二叉树 _。A.以 B为根的子二叉树变为不平衡B.以 C为根的子二叉树变为不平衡C.以 A为根的子二叉树变为不平衡D.仍然是平衡二叉树参考答案：C 第 55 题：设商店有 10 元、5 元、2 元和 1 元的零币，每种零币的数量充足。售货员给顾客找零钱时，零币的数量越少越好。例如给顾客找零29 元：先选 2 张 10 元币，然后选择 1 张 5 元币，再选择两张2 元币。以上的找零钱方法采用了_策略。A.分治B.贪心C.动态规划D.回溯18 参考答案：B 第 56 题：对 n 个元素的数组进行 _，其平均时间复杂度和最坏情况下的时间复杂度都是 O(nlogn

21、)。A.希尔排序B.快速排序C.堆排序D.选择排序参考答案：C 由权值为 29，12，15，6，23 的 5 个叶子结点构造的哈夫曼树为(57)，其带权路径长度为(58)。第 57 题：A.B.C.D.参考答案：A 第 58 题：A.85 B.188 19 C.192 D.222 参考答案：B 第 59 题：表达式“X=A+B(C-D)/E”的后缀表示形式可以为 _(运算符优先级相同时，遵循左结合的原则)。A.XAB+CDE/-x=B.XA+BC-dE/x=C.XABCd-xE/+=D.XABCDE+x-/=参考答案：C 第 60 题：拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在

22、有向图中从顶点 vi 到 vj 有一条路径，则在该线性序列中，顶点vi 必然在顶点 vj 之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_。A.包含回路B.是强连通图C.是完全图D.是有向树参考答案：A 设栈 S和队列 Q的初始状态为空，元素按照 a，b，c，d，e 的次序进入栈 S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c，d，b，a，e，则元素的出栈顺序是(61)，栈 S的容量至少为(62)。第 61 题：A.a，b，c，d，e B.e，d，c，b，a C.c，d，b，a，e D.e，a，b，d，c 参考答案：C 20 第 62 题：A.2 B.3 C.4 D.5 参考答案：B 对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对任意一棵二叉查找树进行(64)遍历可以得到一个结点元素的递增序列。在具有n 个结点的二叉查找树上进行查找运算，在最坏情况下的算法复杂度为(65)。第 63 题：A.先序B.中序C.后序D.层序参考答案：B 第 64 题：A.O(n2)B.O(nlog2n)C.O(log2n)D.O(n)参考答案：D