《软件设计师数据结构与算法(二)》由会员分享，可在线阅读，更多相关《软件设计师数据结构与算法(二)（19页珍藏版）》请在金锄头文库上搜索。
1、模拟软件设计师数据结构与算法（二）选择题第1题：迪杰斯特拉（Diiks tra）算法按照路径长度递增的方式求解单源点最短路径问 题，该算法运用了算法策略。A. 贪心B. 分而治之C. 动态规划D. 试探+回溯 参考答案：A第2题： 关于算法与数据结构的关系，是正确的。A. 算法的实现依赖于数据结构的设计B. 算法的效率与数据结构无关C. 数据结构越复杂，算法的效率越高D. 数据结构越简单，算法的效率越高参考答案：A第3题：若一个问题既可以用迭代方式也可以用递归方式求解，则方法具有更高的时空效率。A. 迭代B. 递归C. 先递归后迭代D. 先迭代后递归参考答案：A第4题：若有数组声明a0.3,
2、0.2,1.4，设编译时为a分配的存储空间首地址为 base_a，且每个数组元素占据一个存储单元。当元素以行为序存放（即按a0， 0，1，a0，0，2，a0，0，3，a0，0，4，a0，1，1，a0，1，2,a3, 2, 4顺序存储)时，则数组元素a2, 2, 2在其存储空间中相 对 base_a 的偏移量是。A. 8B. 12C. 33D. 48参考答案：C已知一个线性表(16, 25, 35, 43, 51, 62, 87, 93),采用散列函数 H(Key)二Key mod 7将元素散列到表长为9的散列表中。若采用线性探测的开放定址法解决冲 突(顺序地探查可用存储单元),则构造的哈希表为
3、 (5) ,在该散列表上进 行等概率成功查找的平均查找长度为 (6) (为确定记录在查找表中的位置, 需和给定关键字值进行比较的次数期望值称为查找算法在查找成功时的平均查 找长度)。第 5 题：A.参考答案：C第6题：A. (5*1+2+3+6)/8B. (5*1+2+3+6)/9C. (8*1)/8D. (8*1)/9参考答案：A第7 题：若将某有序树丁转换为二叉树T1，则T中结点的后(根)序序列就是T1中结点的遍历序列。例如，如图l-8(a)所示的有序树转化为二叉树后如图1-8(b)所示。A. 先序B. 中序C. 后序D. 层序参考答案：B设一个包含W个顶点、E条边的简单有向图采用邻接矩阵
4、存储结构(矩阵元素 Aij等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目 为 (8) ，其中非零元素数目为 (9)。第8题：A. E2B. N2C. N22-E2D. N2+E2参考答案：B第9 题：A. NB. N+EC. ED. N-E第 10 题：一个算法是对某类给定问题求解过程的精确描述，算法中描述的操作都可以通 过将已经实现的基本操作执行有限次来实现。这句话说明算法具有特性。A. 有穷性B. 可行性C. 确定性D. 健壮性 参考答案：B第 11 题：A. 5B. 6C. 7D. 8参考答案：C第 12 题：A. 动态规划B. 分治C. 回溯D. 分支限界参考答案：
5、B第 13 题：若总是以待排序列的第一个元素作为基准元素进行快速排序，那么在最好情况 下的时间复杂度为。A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)参考答案：C第14题：表达式(a-b) *(c+5)的后缀表示是A. a b c 5+*-B. a b-c+5*C. a b c-*5+D. a b-c 5+*参考答案：D一个具有m个结点的二叉树，其二叉链表结点（左、右孩子指针分别用left 和right表示）中的空指针总数必定为（15）个。为形成中序（先序、后序）线索二叉树，现对该二叉链表所有结点进行如下操作：若结点P的左孩子指针为 空，则将该左指针改为指向p在中
6、序（先序、后序）遍历序列的前驱结点；若p的 右孩子指针为空，则将该右指针改为指向p在中序（先序、后序）遍历序列的后继 结点。假设指针s指向中序（先序、后序）线索二叉树中的某结点，则（16）。第15题：A. m+2B. m+1C. mD. m-1参考答案：B第16题：A. s-right指向的结点一定是s所指结点的直接后继结点B. s-left指向的结点一定是s所指结点的直接前驱结点C. 从s所指结点出发的right链可能构成环D. s所指结点的left和right指针一定指向不同的结点第17题：（ ）的邻接矩阵是一个对称矩阵A. 无向图B. AOV 网C. AOE 网D. 有向图参考答案：A第
7、18题：将一个无序序列中的元素依次插入到一棵，并进行中序遍历，可得到一个有序序列。A. 完全二叉树B. 最小生成树C. 二叉排序树D. 最优二叉树参考答案：C第19题：广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是A. 链表B. 静态数组C. 动态数组D. 散列表参考答案：A第20题： 某一维数组中依次存放了数据元素12，23，30，38，41，52，54，76，85，在 用折半（二分）查找方法（向上取整）查找元素54时，所经历“比较”运算的数据 元素依次为。A. 41，52，54B. 41，76，54C. 41，76，52，54D. 41，30，76，54参考答案：B第 2
8、1 题：具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优 先遍历运算的时间复杂度均为。A. O(n2)B. O(e2)C. O(n*e)D. O(n+e)参考答案：D第 22 题：给定一组长度为n的无序序列，将其存储在一维数组aOn-l中。现采用如 下方法找出其中的最大元素和最小元素：比较a0和an-l,若a0较大， 则将二者的值进行交换；再比较a1和an-2,若al较大，则交换二者的 值；然后依次比较a2和an-3、a3和an-4、，使得每一对元素中的 较小者被交换到低下标端。重复上述方法，在数组的前n/2个元素中查找最小 元素中在后n/2个元素中查找最大元素，从而得到整
9、个序列的最小元素和最大 元素。上述方法采用的算法设计策略是。A. 动态规划法B. 贪心法C. 分治法D. 回溯法参考答案：C第 23 题：设某算法的计算时间表示为递推关系式T(n)二T(n-l)+n(n0)及T(O)=1，则该 算法的时间复杂度为。A. O(lgn)B. O(nlgn)C. O(n)D. O(n2)第 24 题： 下面关于查找运算及查找表的叙述，错误的是。A. 哈希表可以动态创建B. 二叉排序树属于动态查找表C. 二分查找要求查找表采用顺序存储结构或循环链表结构D. 顺序查找方法既适用于顺序存储结构，也适用于链表结构参考答案：C第 25 题： 下面关于图(网)的叙述，正确的是。
10、A. 连通无向网的最小生成树中，顶点数恰好比边数多1B. 若有向图是强连通的，则其边数至少是顸点数的2倍C. 可以采用AOV网估算工程的工期D. 关键路径是AOE网中源点至汇点的最短路径参考答案：A第26 题：下面关于二叉排序树的叙述，错误的是。A. 对二叉排序树进行中序遍历，必定得到结点关键字的有序序列B. 依据关键字无序的序列建立二叉排序树，也可能构造出单支树C. 若构造二叉排序树时进行平衡化处理，则根结点的左子树结点数与右子树 结点数的差值一定不超过 1D. 若构造二叉排序树时进行平衡化处理，则根结点的左子树高度与右子树高 度的值一定不超过 1参考答案：C第27 题： 下面关于栈和队列的
11、叙述，错误的是。A. 栈和队列都是操作受限的线性表B. 队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的 时间复杂度都为 O(1)C. 若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高D. 利用两个栈可以模拟一个队列的操作，反之亦可参考答案：D第 28 题： 下面关于二叉树的叙述，正确的是。A. 完全二叉树的高度h与其结点数n之间存在确定的关系B. 在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储 结构C. 完全二叉树中一定不存在度为1的结点D. 完全二叉树中必定有偶数个叶子结点参考答案：A第 29 题：设L为广义表，将head(L)定义为取
12、非空广义表的第一个元素，tail(L)定义为 取非空广义表除第一个元素外剩余元素构成的广义表。若广义表L=(x，y， z)，a， (u，t，w)，则从L中取出原子项y的运算是。A. head(tail(tail(L)B. tail(head(head(L)C. head(tail(head(L)D. tail(tail(head(L)参考答案：C第 30 题：以下的算法设计方法中，以获取问题最优解为目标A. 回溯法B. 分治法C. 动态规划D. 递推参考答案：C第 31 题：归并排序采用的算法设计方法属于A. 归纳法B. 分治法C. 贪心法D. 回溯法参考答案：B已知一个二又树的先序遍历序列为
13、、，中序遍历序列为、 、，则该二叉树的后序遍历序列为(32)。对于任意一棵二叉 树，叙述错误的是 (33)。第32题：A. 、B. 、C. 、D. 、 参考答案：C第33题：A. 由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列B. 由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列C. 由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列D. 由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列 参考答案：B第34 题：邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边 的图，。A. 进行深度优先遍历运算所消耗的时间与采用哪一种存储结
14、构无关B. 进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C. 采用邻接表表示图时，查找所有顶点的邻接顶点的时间复杂度为O(n*e)D. 采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为 O(n2)第 35 题： 单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指 针指向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链 表头结点的叙述中，错误的是。A. 若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为0(1)B. 在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处 理C. 加入头结点后，代表链表的头指针不因为链表为空而改变D. 加入头结点后，在链表中进行查找运算的时间复杂度为O(1)参考答案：D第 36 题：对于长度为m(m 1)的指定序列，通过初始为空的
