《软件设计师数据结构与算法(一)》由会员分享，可在线阅读，更多相关《软件设计师数据结构与算法(一)（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.DEBFC
2、A 参考答案： D 第 4 题： 无向图中一个顶点的度是指图中_。 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 题： 一个具
3、有 n(n0)个顶点的连通无向图至少有_条边。 A.n+1 B.n C.n/2 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 中
4、，若采用线性探测方法解 决冲突，则在该散列表上进行等概率成功查找的平均查找长度为_。 A.1.5 B.1.7 C.2.0 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
5、.O(n2) C.O(log2n) D.O(nlog2n) 参考答案： D 第 14 题： 利用动态规划方法求解每对结点之间的最短路径问题(all pairs shortest 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
6、)+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 在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表 示活动，边上的数字表示活动持续的时间。在下面的活动图 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
7、 第 17 题： A.10 B.12 C.13 D.15 参考答案： C 6 第 18 题： 已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序 列为_。 A.BCDEAF B.ABDCEF C.DBACEF D.DABECF 参考答案： B 第 19 题： 在二叉树的顺序存储中，每个结点的存储位置与其父结点、左右子树结点的位 置都存在一个简单的映射关系，因此可与三叉链表对应。若某二叉树共有n 个 结点，采用三叉链表存储时，每个结点的数据域需要d 个字节，每个指针域占 用 4 个字节，若采用顺序存储，则最后一个结点下标为k( 起始下标为 1) ，那么 _时采用顺序
8、存储更节省空间。 A. B. C. D. 参考答案： A 简单无向图的邻接矩阵是对称的，可以对其进行压缩存储。若无向图G有 n 个结点，其邻接矩阵为A1.n ，1.n ，且压缩存储在B1.k中，则 k 的值至 少为(20) 。若按行压缩存储对称矩阵的上三角元素，则当n 等于 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 时，被比较的
9、元素的下标依次是_。 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.38 C.51 D.75 参考答案： D 第 24 题： 若排序前后关键字相同的两个元素相对位置不变，则称该排序方法是稳定的。 _排序是稳定的。 设求解某问题的递归算法如下： F(int n) if (n=1) Move(1) ； else F(n-1) ； Move(n) ；
10、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(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
11、) 能够确保获得最优解。用动态 规划方法求解 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 题： A.优先选取重量最小的物品 B.优先选取效益最大的物品 C.优先选取单位重量效益最大的物品 D.没有任何准则 参考答案： D 第 28 题： A.fi(X)=minfi-1(X
12、)，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 题： 拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶 点在该图的拓扑序列中保持先后关系，_为图 1-2 所示有向图的一
13、个拓扑 序列。 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 个元素的有序线性表。若采用顺序存储结构，则在等概率前提 下，删除其中的一个元素平均需要移动_个元素。 A.(n+1)/2 B.n/2 C.(n-1)/2 D.1 参考答案： C
14、 第 33 题： 在平衡二叉树中， _。 A.任意结点的左、右子树结点数目相同 B.任意结点的左、右子树高度相同 C.任意结点的左、右子树高度之差的绝对值不大于1 D.不存在度为 1 的结点 参考答案： C 第 34 题： 在_存储结构中，数据结构中元素的存储地址与其关键字之间存在某种映 射关系。 A.顺序(Sequence) B.链表(Link) C.索引(Index) D.散列(Hash) 12 参考答案： D 对于求取两个长度为n 的字符串的最长公共子序列(LCS)问题，利用(35) 策略可以有效地避免子串最长公共子序列的重复计算，得到时间复杂度为 O(n2) 的正确算法。 串1，0，0
15、，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 题： 表达式“ 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
