中级软件设计师单项选 择考试卷模拟考试题

1、姓名：_ 班级：_ 学号：_-密-封 -线- 中级软件设计师单项选 择考试卷模拟考试题考试时间：120分钟 考试总分：100分题号一二三四五总分分数遵守考场纪律，维护知识尊严，杜绝违纪行为，确保考试结果公正。1、在下面几个符号串编码集合中，不是前缀编码的是_。 （ ）a.0,10,110,101b.(00,10,010,110,1110)c.00,010,0110,1000)d.(b,c,aa,ac,aba,abb,abc)2、某工程计划图如图3-68所示，弧上的标记为作业编码及其需要的完成时间(天)，那么，作业e最迟应在第（ ）天开始。 （ ）a.7b.9c.12d.133、_的特点是数据结

2、构中元素的存储地址与其关键字之间存在某种映射关系。 （ ）a.树形存储结构b.链式存储结构c.索引存储结构d.散列存储结构4、一个具有n(n0)个顶点的连通无向图至少有（ ）条边。 （ ）a.n+1b.nc.n/2d.n-15、如果只想得到5000个元素组成的序列中最小的20个元素序列，用_方法最合适。 （ ）a.lb.99c.100d.1018、具有n个结点且互不相似的二叉树的总数是（ ）a.b.c.d.9、已知某二叉树的后序遍历序列是dabec，中序遍历序列是deabc，它的前序遍历序列是_。 （ ）a.abcedb.cedbac.deabcd.decab10、利用逐点插入法建立序列(50

3、，72，43，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素30要进ld.不确定13、若广义表l=(1，2，3)，则l的长度和深度分别为_。 （ ）a.1和1b.1和2c.1和3d.2和214、已知二叉树有50个叶子结点，则该二叉树的总结点数至少是_。 （ ）a.96b.99c.100d.11315、一棵树高为k的完全二叉树至少有_个结点。 （ ）a.2k-1b.2k-1-1c.2k-1d.2k16、下面有关线性表的叙述中，错误的是_。 （ ）a.线性表采用顺序存储，必须占用一片连续的存储单元。b.线性表采用顺序存储，便于进行插入和删除操作。c.线性表采用链接存储，不

4、必占用一片连续的存储单元。d.线性表采用链接存储，便于插入和删除操作。17、在非空双向循环链表结点中，prior域指向该结点的直接前驱，next域指向直接后续，那么在q所指的结点后面插入p所指的结点的过程为_。 （ ）a.qnext=p；pprior=q；qnextprior=p；pnext=qnext。b.pnext=qnext；qnext=p；qnextprior=p；pprior=q。c.pprior=q；pnext=qnext；qnext=p；qnextprior=p。d.pnext=qnext；qnextprior=p；pprior=q；next=p。18、假设根结点的层数为1，并设

5、具有n(n3)个结点的二叉树的最大高度为h，设达到最大高度h时，不同的二叉树的数目为m。有以下说法：hn h=log2n+1 m=1 m=2 m=2n-1其中正确的个数有_个。 （ ）a.1b.2c.3d.419、已知一算术表达式的中缀形式为(a+b)*c-d/e，其前缀形式为_。 （ ）a.-*a+bc/deb.-*+abc/dec.-*+bac/ded.-*ab+c/de20、若采用邻接矩阵来存储简单有向图，则其某一个顶点i的人度等于该矩阵_。 （ ）a.第i行中值为1的元素个数b.所有值为1的元素总数c.第i行及第i列中值为1的元素总个数d.第i列中值为1的元素个数21、关于哈夫曼树、最

6、优二叉树、哈夫曼算法，有以下说法：最优二叉树的形态不唯一，但是其wpl值是唯一确定的。哈夫曼树一定是最优二叉树，但最优二叉树不一定由哈夫曼算法来构造。则_。 （ ）a.正确错误b.错误正确c.都对d.都错22、关键路径是指aoe(activity on edge)网中_。 （ ）a.最长的回路b.最短的回路c.从源点到汇点(结束顶点)的最长路径d.从源点到汇点(结束顶点)的最短路径23、对于二维数组a0. 4,1. 5，设每个元素占1个存储单元，且以列为主序存储，则元素a2,2相对于数组空间起始地址的偏移量是_。 （ ）a.5b.7c.10d.1524、算法是对问题求解过程的一类精确描述，算法

7、中描述的操作都是可以通过已经实现的基本操作在限定时间内执行有限次来实现的，这句话说明算法具有_特性。 （ ）a.正确性b.确定性c.可行性d.健壮性25、一棵二叉树的前序遍历序列为abcdefg，它的中序遍历序列可能是_。 （ ）a.cabdefgb.abcdefgc.dacefbgd.adbcfeg26、先序遍历能得到abc序列的不同二叉树的最大个数为_。 （ ）a.4b.5c.6d.727、关于森林的遍历有以下说法：森林的先序遍历等同于其对应的二叉树的先序遍历。森林的中序遍历等同于其对应的二叉树的中序遍历。森林的后序遍历等同于其对应的二叉树的后序遍历。森林的后序遍历等同于其对应的二叉树的中

8、序遍历。其中正确的是_。 （ ）a.b.c.d.28、一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有_个零元素。 （ ）a.eb.2ec.n2-ed.n2-2e29、堆排序是一种基于(1)的排序方法，(2)不是堆。1（ ）a.计数b.插入c.选择d.归并30、堆排序是一种基于(1)的排序方法，(2)不是堆。2（ ）a.15，28，25，56，68，63，30b.15，28，25，30，68，63，56c.68，28，63，25，15，56，30d.68，56，39，63，28，25，1531、在下列算法设计方法中，(1)在求解问题的过程中并不从整体最优上加以考虑，而是做出在当

9、前看来是最好的选择。利用该设计方法可以解决(2la.b.c.d.34、关于满二叉树、完全二叉树有以下说法： 满二叉树不仅是一种特殊形态的二叉树，而且是一种特殊的完全二叉树。 具有n个结点的满二叉树的高度为+1。 具有n个结点的完全二叉树的高度为+1。 具有n个结点的满二叉树的高度为log2(n+1)。 具有n个结点的满二叉树共有叶子结点。 其中（ ）最全面、最准确。 （ ）a.b.c.d.全对35、在数据压缩编码的应用中，哈夫曼(huffman)算法可以用来构造具有(1)的二叉树，这是一种采用了(2)的算法。1（ ）a.前缀码b.最优前缀码c.后缀码d.最优后缀码36、在数据压缩编码的应用中，

10、哈夫曼(huffman)算法可以用来构造具有(1)的二叉树，这是一种采用了(2)的算法。2（ ）a.贪心b.分治c.递推d.回溯37、一般情况下，将递归程序转化成为非递归程序应该设置(1)，但是消除(2)时不需要使用。1（ ）a.堆栈b.队列c.堆栈或队列d.数组38、一般情况下，将递归程序转化成为非递归程序应该设置(1)，但是消除(2)时不需要使用。2（ ）a.直接递归b.间接递归c.尾递归d.递推39、某带权有向图如图3-67所示。若忽略边上的权，并将其看做aov网，那么该aov网的拓扑排序为 (1) 。若将该图视为aoe网，那么该aoe网的关键路径有 (2) 条，其长度为 (3) 。该a

11、oe网的所有关键活动共有 (4) 个，v5的最早开始时间和最迟开始时间分别是 (5) 。1（ ）a.v1、v2、v3、v4、v6、v5、v7、v8b.v1、v3、v5、v2、v4、v6、v7、v8c.v1、v2、v3、v4、v5、v6、v7、v8d.v1、v2、v3、v5、v6、v4、v7、v840、某带权有向图如图3-67所示。若忽略边上的权，并将其看做aov网，那么该aov网的拓扑排序为 (1) 。若将该图视为aoe网，那么该aoe网的关键路径有 (2) 条，其长度为 (3) 。该aoe网的所有关键活动共有 (4) 个，v5的最早开始时间和最迟开始时间分别是 (5) 。2（ ）a.1b.2

12、c.3d.441、某带权有向图如图3-67所示。若忽略边上的权，并将其看做aov网，那么该aov网的拓扑排序为 (1) 。若将该图视为aoe网，那么该aoe网的关键路径有 (2) 条，其长度为 (3) 。该aoe网的所有关键活动共有 (4) 个，v5的最早开始时间和最迟开始时间分别是 (5) 。3（ ）a.15b.16c.17d.1842、某带权有向图如图3-67所示。若忽略边上的权，并将其看做aov网，那么该aov网的拓扑排序为 (1) 。若将该图视为aoe网，那么该aoe网的关键路径有 (2) 条，其长度为 (3) 。该aoe网的所有关键活动共有 (4) 个，v5的最早开始时间和最迟开始时间分别是 (5) 。4（ ）a.5b.9c.10d