中级软件设计师简单单选试卷（中级软件设计师）_2.docVIP

试卷第 PAGE 8 页共 NUMPAGES 8 页 中级软件设计师简单单选试卷（中级软件设计师） 姓名:_____________ 年级:____________ 学号:______________ 题型 选择题 填空题 解答题 判断题 计算题 附加题 总分 得分 评卷人 得分 1、表达式“(a+b)*(c-d)”的后缀表示为______。 A.ab+cd-* B.abcd+-* C.ab+*cd- abcd*+-2、 一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (80)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则 (81)。80（ ） A.m+2 B.m+1 C.m m-13、 一个具有m个结点的二叉树，其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为 (80)个。为形成中序(先序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则 (81)。81（ ） A.s-＞right指向的结点一定是s所指结点的直接后继结点 B.s-＞left指向的结点一定是s所指结点的直接前驱结点 C.从s所指结点出发的right链可能构成环 s所指结点的left和right指针一定指向不同的结点4、表达式“X=A+B×(C-D)/E”的后缀表示形式可以为______(运算符优先级相同时，遵循左结合的原则)。 A.XAB+CDE/-x= B.XA+BC-dE/x= C.XABCd-xE/+= XABCDE+x-/=5、已知某二叉树的中序、层序序列分别为DBAFCE、FDEBCA，则该二叉树的后序序列为______。 A.BCDEAF B.ABDCEF C.DBACEF DABECF6、 已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (97)。对于任意一棵二叉树，叙述错误的是 (98)。97（ ） A.②、③、①、⑤、④ B.①、②、③、④、⑤ C.②、④、⑤、③、① ④、⑤、③、②、①7、 已知一个二又树的先序遍历序列为①、②、③、④、⑤，中序遍历序列为②、①、④、③、⑤，则该二叉树的后序遍历序列为 (97)。对于任意一棵二叉树，叙述错误的是 (98)。98（ ） A.由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列 B.由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列 C.由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列 由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列8、拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定______。 A.包含回路 B.是强连通图 C.是完全图 是有向树9、对n个元素的数组进行______，其平均时间复杂度和最坏情况下的时间复杂度都是O(nlogn)。 A.希尔排序 B.快速排序 C.堆排序 选择排序10、用插入排序和归并排序算法对数组＜3，1，4，1，5，9，6，5＞进行从小到大排序，则分别需要进行______次数组元素之间的比较。 A.12，14 B.10，14 C.12，16 10，1611、在活动图中，结点表示项目中各个工作阶段的里程碑，连接各个结点的边表示活动，边上的数字表示活动持续的时间。在下面的活动图1-1中，从A到J的关键路径是 (15) ，关键路径长度是 (16) ，从E开始的活动启动的最早时间是 (17) 。15（ ） A.ABEGJ B.ADFHJ C.ACFGJ ADFIJ12、在活动图中，结点