[语言类考试复习资料大全]中级软件设计师上午试题分类模拟16

1、书山有路勤为径，学海无涯苦作舟。祝愿天下莘莘学子：学业有成，金榜题名！语言类考试复习资料大全中级软件设计师上午试题分类模拟16中级软件设计师上午试题分类模拟16单项选择题问题:1. 采用顺序表和单链表存储长度为n的线性序列，根据序号查找元素，其时间复杂度分别为_。A.O(1)、O(1)B.O(1)、O(n)C.O(n)、O(1)D.O(n)、O(n)答案:B解析 顺序表存储位置是相邻连续的，可以随即访问的一种数据结构，一个顺序表在使用前必须指定起始长度，一旦分配内存，则在使用中不可以动态更改。它的优点是访问数据比较方便，可以随机访问表中的任何一个数据。链表是通过指针来描述元素关系的一种数据结构

2、，它可以是物理地址不连续的物理空间。不能随即访问链表元素，必须从表头开始，一步一步搜索元素。它的优点是：对于数组，可以动态地改变数据的长度，分配物理空间。因此两者的查找复杂度就显而易见了。问题:2. 设元素序列a、b、c、d、e、f经过初始为空的栈S后，得到出栈序列c e d f b a，则栈S的最小容量为_。A.3B.4C.5D.6答案:B解析 此题考查栈的用法，根据题中出栈的顺序，当元素c出栈后，栈中有元素a、b，当元素e出栈之前，栈中有元素a、b、d、e，此时栈中的元素达到最多。因此栈S最小容量为4。问题:3. 输出受限的双端队列是指元素可以从队列的两端输入、但只能从队列的一端输出，如下

3、图所示。若有e1、e2、e3、e4依此进入输出受限的双端队列，则得不到输出队列_。 A.e4、e3、e2、e1B.e4、e2、e1、e3C.e4、e3、e1、e2D.e4、e2、e3、e1答案:D解析 此题考查队列的性质，队列为先进先出的线性结构，题中给出的受限的双端队列，两端都可以进，而一段可出，假设分a和b端，b端可以进出，由D选项的出序列，可以看出e1、e2、e3按顺序从a端进入，而e4从b端进入，当e4从b端出来之后，无法将后面的e2出队列，故D选项有误。问题:4. 对于一个长度大于1且不存在重复元素的序列，令其所有元素依次通过一个初始为空的队列后，再通过一个初始为空的栈。设队列和栈的

4、容量都足够大，一个序列通过队列(栈)的含义是序列的每个元素都入队列(栈)且出队列(栈)一次且仅一次。对于该序列在上述队列和栈上的操作，正确的是_。A.出队序列和出栈序列一定相同B.出队序列和出栈序列一定互为逆序C.入队序列和出队序列一定相同，入栈序列和出栈序列不一定相同D.入栈序列和出栈序列一定互为逆序，入队序列和出队序列不一定互为逆序答案:C解析 队列具有先进先出的特点，也就是说最先入队的元素最先出队，所以入队序列和出队序列一定相同。栈则具有先进后出的特点，如果所有元素进栈后再依次出栈，则入栈序列和出栈序列互为逆序，否则不一定。问题:5. 对于线性表(由n个同类元素构成的线性序列)，采用单向

5、循环链表存储的特点之一是_。A.从表中任意结点出发都能遍历整个链表B.对表中的任意结点可以进行随机访问C.对于表中的任意一个结点，访问其直接前驱和直接后继结点所有时间相同D.第一个结点必须是头结点答案:A解析 对于单向循环链表，可以从表中任意结点出发都能遍历整个链表。但并不能对表中的任意结点进行随机访问，需要从设置的第一个节点开始，沿着指针访问表中的结点。当然访问某一结点的直接后继结点最快，访问其直接前驱结点最慢，因为首先要遍历到表尾，然后从表头遍历到其前驱结点。问题:6. 设循环队列Q的定义中有rear和len两个域变量，其中rear表示队尾元素的指针，len表示队列的长度，如下图所示(队列

6、长度为3，队头元素为e)。设队列的存储空间容量为M，则队头元素的指针为_。 A.(Q.rear+Q.len-1)B.(Q.rear+Q.len-1+M)/MC.(Q.rear-Q.len+1)D.(Q.rear-Q.len+1+M)/M答案:D解析 设队列的队头指针为front，front指向队头元素。队列的存储空间容量为M，说明队列中最多可以有M个元素；队列的长度为len，说明当前队列中有len个元素。则有： O.rear=(Q.front+Q.len-1)/M O.front=(Q.rear-Q.len+1+M)/M 问题:7. 栈是一种按“后进先出”原则进行插入和删除操作的数据结构，因此

7、，_必须用栈。A.实现函数或过程的递归调用及返回处理时B.将一个元素序列进行逆置C.链表结点的申请和释放D.可执行程序的装入和卸载答案:A解析 栈是一种后进先出的数据结构。将一个元素序列逆置时，可以使用栈也可以不用。链表结点的申请和释放次序与应用要求相关，不存在“先申请后释放”的操作要求。可执行程序的装入与卸载，也不存在“后进先出”的操作要求。对于函数的递归调用与返回，一定是后被调用执行的先返回。问题:8. 某双向链表中的结点如下图所示，删除t所指结点的操作为_。A.t-prior-next=t-next; t-next-prior=t-prior;B.t-prior-prior=t-prio

8、r; 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解析 本题考查双向链表的基本操作。 双向链表每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。 删除t节点，只需把t原来的前驱的next指向t现在的后继，t原来后继的prior指向t现在的前驱即可。 问题:9. 单向链表中往往含有一个头结点，该结点不存储数据元素，一般令链表的头指针指

9、向该结点，而该结点指针域的值为第一个元素结点的指针。以下关于单链表头结点的叙述中，错误的是_。A.若在头结点中存入链表长度值，则求链表长度运算的时间复杂度为O(1)B.在链表的任何一个元素前后进行插入和删除操作可用一致的方式进行处理C.加入头结点后，代表链表的头指针不因为链表为空而改变D.加入头结点后，在链表中进行查找运算的时间复杂度为O(1)答案:D解析 本题考查单链表头结点的相关知识。 A选项：由于在头结点中存入链表长度值，在遍历链表时先从头指针开始，头指针指向头结点，头节点的数据域即为链表长度，故A正确。 B选项：插入运算是将值为X的新结点插入到表的第i个结点的位置上，即插入到ai-1与

10、ai之间。因此，必须首先找到ai-1的存储位置P，然后生成一个数据域为x的新结点，并令q指针指向该新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1、x和ai之间的逻辑关系的变化。 定位ai-1并将指针P指向它，代码如下。 q = new LNode; q-data=x; q-next=p-next; P-next=q; 删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中，所以必须首先找到ai-1的存储位置P。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。 代码如下。 r=p-next;

11、P-next=r-next; delete r; 故B正确。 C选项：头结点引入，即增加一个表头结点，数据域可根据需要使用或不用。特点如下。 表中第一个结点和在表的其他位置上的操作一致，无须进行特殊处理。 无论链表是否为空，其头指针是指向头结点。因此空表和非空表的处理统一。 故C正确。 D选项：查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。算法如下。 LNode *locatenode(head, key) LNode *P; p=head-next; while( P return p; 该算法的执行时间亦与输入实例中的取值key有关，其平均时间复杂度的分析类似于按序号

12、查找。故D错误。 问题:10. 对于长度为m(m1)的指定序列，通过初始为空的一个栈、一个队列后，错误的叙述是_。A.若入栈和入队的序列相同，则出栈序列和出队序列可能相同B.若入栈和入队的序列相同，则出栈序列和出队序列可以互为逆序C.入队序列与出队序列关系为1:1，而入栈序列与出栈序列关系是1:n(n1)D.入栈序列与出栈序列关系为1:1，而入队序列与出队序列关系是1:(n1)答案:D解析 如果入栈和入队的序列相同，则出栈序列和出队序列既可以相同，也可以互为逆序。例如，设入栈和入队序列为1、2、3。对于栈来说，如果每次进去一个后就出来，则出栈序列为1、2、3，而出队序列也为1、2、3。因为栈是

13、“后进先出”的数据结构，而队列是“先进先出”的数据结构，因此二者可互为逆序。如果入队序列与出队序列关系为1:1，那么由于栈的后进先出的特性，则入栈序列与出栈序列关系是1:n(n1)。比如，abcde入队，它出队只可能是abcde，而入栈abcde，则出栈的序列却不止一种。所以A、B、C选项都是正确的。问题:11. 字符串采用链表存储方式时，每个结点存储多个字符有助于提高存储密度。若采用结点大小相同的链表存储串，则串比较、求子串、串连接、串替换等串的基本运算中，_。A.进行串的比较运算最不方便B.进行求子串运算最不方便C.进行串连接最不方便D.进行串替换最不方便答案:B解析 在用链表作为字符串的

14、存储方式时，如果每个结点存储多个字符，进行串连接、串替换和串的比较等操作时，不会有很大影响，但是在进行子串求解时，因为有可能涉及所求的子串不在一个结点上存储，所以会比较麻烦，因此总的来说，进行求子串时最不方便。问题:12. 下面关于栈和队列的叙述，错误的是_。A.栈和队列都是操作受限的线性表B.队列采用单循环链表存储时，只需设置队尾指针就可使入队和出队操作的时间复杂度都为O(1)C.若队列的数据规模n可以确定，则采用顺序存储结构比链式存储结构效率更高D.利用两个栈可以模拟一个队列的操作，反之亦可答案:D解析 栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为

15、栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。栈的修改是按后进先出的原则进行的，所以，栈称为后进先出(LIFO)的线性表。 队列(Oueue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(Front)，允许插入的一端称为队尾(Rear)。先进入队列的成员总是先离开队列。队列亦称做先进先出(First In First Out)的线性表，简称FIFO表。 尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便。设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置

16、分别是rear-next-next和rear，查找时间都是O(1)。 链表是指用一组任意的存储单元来依次存放数据，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。 顺序存储是把数据按逻辑顺序依次存放在一组地址连续的存储单元中。 因此如果队列的数据规模确定，则在顺序存储结构中存取数据的速度会比链式存储结构中的要快。 假设两个栈A和B，且都为空。可以认为栈A提供入队列的功能，栈B提供出队列的功能。 入队列：入栈A。 出队列：如果栈B不为空，直接弹出栈B的数据；如果栈B为空，则依次弹出栈A的数据，放入栈B中，再弹出栈

17、B的数据。 因此两个栈可以模拟一个队列的操作，但反之不可。 设栈S和队列Q的初始状态为空，元素按照a、b、c、d、e的次序进入栈S，当一个元素从栈中出来后立即进入队列Q。若队列的输出元素序列是c、d、b、a、e，则元素的出栈顺序是_，栈S的容量至少为_。 13.A.a、b、c、d、eB.e、d、c、b、aC.c、d、b、a、eD.e、a、b、d、c答案:C14.A.2B.3C.4D.5答案:B问题:15. 对于m(n0)个元素构成的线性序列L，在_时适合采用链式存储结构。A.需要频繁修改L中元素的值B.需要频繁地对L进行随机查找C.需要频繁地对L进行删除和插入操作D.要求L存储密度高答案:C问

18、题:16. 设下三角矩阵(上三角部分的元素值都为0)A0.n，0.n如下所示，将该三角矩阵的所有非零元素(即行下标不小于列下标的元素)按行优先压缩存储在容量足够大的数组M1.m中，则元素Ai,j0in，ji)存储在数组M的_中。 A B C D 答案:A解析 第0行有1个元素保存在数组M中，第1行有2个元素保存在数组M中，第i-1行中有i个元素保存在数组M中，第i行之前有1+2+3+.+i=i(i+1)/2个元素保存在数组M中，元素Ai,j是第i行的j+1个元素。由于数组M的下标从1开始，因此Ai,j的值存储在中。问题:17. 设有如下所示的下三角矩阵A0.8,0.8，将该三角矩阵的非零元素(

19、即行下标不小于列下标的所有元素)按行优先压缩存储在数组M1.m中，则元素Ai,j(08,ji)存储在数组M的_中。 A B C D 答案:A解析 如图所示，按行方式压缩存储时，Ai,j之前的元素数目为(1+2+.+i+j)个，数组M的下标从1开始，因此Ai,j的值存储在中。问题:18. 设L为广义表，将head(L)定义为取非空广义表的第一个元素，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(h

20、ead(L)D.tail(tail(head(L)答案:C解析 对于广义表L=(x,y,z)，a，(u,t,w)，head(L)定义为取非空广义表的第一个元素，tail(L)定义为取非空广义表除第一个元素外剩余元素构成的广义表。head(tail(head(L)即为先取L的第一个元素(x,y,z)；接着取除第一个元素外的剩余元素y、z；然后取第一个元素即y。问题:19. 广义表中的元素可以是原子，也可以是表，因此广义表的适用存储结构是_。A.链表B.静态数组C.动态数组D.散列表答案:A问题:20. 若有数组声明a0.3，0.2，1.4，设编译时为a分配的存储空间首地址为base_a，且每个数

21、组元素占据一个存储单元。当元素以行为序存放(即按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问题:21. 一个高度为h的满二叉树的节点总数为2h-1，从根结点开始，自上而下、同层次结点从左至右，对结点按照顺序依次编号，即根节点编号为1，其左、右孩子节点编号分为2和3，再下一层从左到右的编号为4、5、6、7，依次类推。那么，在一颗满二叉树中，对于编号为m和n的两个节点，若n=2m+1，则_结点。A.m是n的左孩子B.m是n的右孩

22、子C.n是m的左孩子D.n是m的右孩子答案:D解析 由于该二叉树为满二叉树，且根节点编号从1开始，由满二叉树的性质可知父节点m和右孩子之间的关系为n=2m+1。问题:22. 若某二叉树的后序遍历序列为KBFDCAE，中序遍历序列为BKFEACD，则该二叉树为_。 A B C D 答案:A解析 本题考查二叉树的遍历算法，根据中序遍历序列和另一种遍历序列的结果，可以确定该二叉树。后序遍历是按照左子树、右子树、根结点的顺序进行遍历，中序遍历是按照左子树、根结点、右子树的顺序进行遍历。E为根结点，K为B的右子树，因此应选A项描述的二又树。问题:23. 下图所示为一棵N阶B-树，N最有可能的值为_。 A

23、.1B.2C.3D.4答案:D解析 一颗N阶B-树为满足以下特性的N叉树： 树中每个结点至多有N棵子树； 若根结点不是叶子结点，则至少有两棵子树； 除根之外的所有非终端结点至少有棵子树； 所有的非终端结点中包含下列数据信息(n,A0,K1,A1,K2,A2,Kn,An)。其中，Ki(i=1,2,n)为关键字(如3,47,53,63)，且KiKi+1,Ai(i=0,1,2,n)为指向子树根结点的指针，n为结点中关键字的个数，且 所有的叶子结点都出现在同一层次上，并且不带信息。 由上图可知，N最有可能的值为4。 问题:24. 若n2、n1、n0分别表示一个二叉树中度为2、度为1和叶子结点的数目(结

24、点的度定义为结点的子树数目)，则对于任何一个非空的二叉树，_。A.n2一定大于n1B.n1一定大于n0C.n2一定大于n0D.n0一定大于n2答案:D解析 由二叉树的性质可知，度为0的结点比度为2的结点数多1，即n0=n2+1，因此n0一定大于n2。问题:25. 一棵满二叉树，其每一层结点个数都达到最大值，对其中的结点从1开始顺序编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依此类推，每一层都从左到右依次编号，直到最后的叶子结点层为止，则用_可判定编号为m和n的两个结点是否在同一层。 Alog2m=log2n B C D 答案:B解析 由于是

25、满二叉树，只有m个结点的二叉树一定是完全二叉树，只有n个结点的二叉树也一定是完全二叉树，因此，具有m个节点的完全二叉树的深度为具有n个节点的完全二叉树的深度为如果编号为m和n的两个结点是在同一层，则有即问题:26. _是由权值集合8,5,6,2构造的哈夫曼树(最优二叉树)。 A B C D 答案:C解析 哈夫曼树是带权路径最短的树。选项A、B、C、D四棵树的带权路径长度分别如下。 选项A：8*2+5*2+6*2+2*2=42 选项B：8*3+5*3+6*2+2=53 选项C：8+6*2+2*3+5*3=41 选项D：2+5*2+6*3+8*3=54 问题:27. 在_中，任意一个结点的左、右子

26、树的高度之差的绝对值不超过1。A.完全二叉树B.二叉排序树C.线索二叉树D.最优二叉树答案:A解析 对于完全二叉树，若设二叉树的高度为h，除第h层外，其他各层(1h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。 二叉排序树(Binary Sort Tree)又称二叉查找树。它或者是一棵空树；或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值：若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树。对于二叉排序树，由于左子树或

27、右子树可能为空，不能保证每一个结点的左、右子树的高度之差的绝对值不超过1。 按照某种遍历方式对二叉树进行遍历，可以把二叉树中所有结点排序为一个线性序列。在改序列中，除第一个结点外每个结点有且仅有一个直接前驱结点；除最后一个结点外每一个结点有且仅有一个直接后继结点。这些指向直接前驱结点和指向直接后续结点的指针被称为线索(Thread)，加了线索的二叉树称为线索二叉树。线索二叉树只是加了线索的二叉树，对结点的排列没有要求，不能保证每一个结点的左、右子树的高度之差的绝对值不超过1。 给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树，不能

28、保证每一个结点的左、右子树的高度之差的绝对值不超过1。 问题:28. 下面关于哈夫曼树的叙述中，正确的是_。A.哈夫曼树一定是完全二叉树B.哈夫曼树一定是平衡二叉树C.哈夫曼树中权值最小的两个结点互为兄弟结点D.哈夫曼树中左孩子结点小于父结点、右孩子结点大于父结点答案:C解析 哈夫曼树即最优二叉树，是一类带权路径长度的最短的树。树的带权路径为书中所有叶子节点的带权路径长度之和，记为 式中，n为带权叶子节点的数目，wk为叶子节点的权值，lk为叶子节点到根的路径长度。 则哈夫曼树是指权值为w1，w2，wn的n个叶子节点的二叉树中带权路径长度最小的二叉树。 哈夫曼树与完全二叉树、平衡二叉树之间没有必

29、然的联系。选项A、B中的说法是错误的。在哈夫曼树的构建中，由哈夫曼树的构造算法可知，哈夫曼树中权值最小的两个结点互为兄弟结点，根结点的权值为其左、右子树根结点的权值之和。 问题:29. 已知一棵度为3的树(一个结点的度是指其子树的数目，树的度是指该树中所有结点的度的最大值)中有5个度为1的结点，4个度为2的结点，2个度为3的结点，那么，该树中的叶子结点数目为_。A.10B.9C.8D.7答案:B解析 树的结点总数为5+42+23+1=20，叶子节点数为20-5-4-2=9。问题:30. 若用n个权值构造一棵最优二叉树(哈夫曼树)，则该二叉树的结点总数为_。A.2nB.2n-1C.2n+1D.2

30、n+2答案:B解析 二叉树具有以下性质：度为2的结点(双分支结点)数比度为0的结点(叶子结点)数正好少1。而根据最优二叉树(哈夫曼树)的构造过程可知，最优二叉树中只有度为2和0的结点，因此，其结点总数为2n-1。问题:31. 用关键字序列10、20、30、40、50构造的二叉树排序(二叉查找树)为_。 A B C D 答案:C解析 根据关键字序列构造二叉排序树的基本过程是，若需插入的关键字大于树根，则插入到右子树上，若小于树根，则插入到左子树上，若为空，则作为数根结点。 已知一个二叉树的先序遍历序列为、，中序遍历序列为、，则该二叉树的后序遍历序列为_。对于任意一棵二叉树，叙述错误的是_。 32

31、.A.、B.、C.、D.、答案:C33.A.由其后序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列B.由其先序遍历序列和后序遍历序列可以构造该二叉树的中序遍历序列C.由其层序遍历序列和中序遍历序列可以构造该二叉树的先序遍历序列D.由其层序遍历序列和中序遍历序列不能构造该二叉树的后序遍历序列答案:B解析 本题考查二叉树的遍历。 二叉树的先序遍历为根、左、右，中序遍历的顺序为左、根、右。根据二叉树的先序遍历序列为、，中序遍历序列为、，可知该二叉树的根为，而在中序遍历中在的左边，是左子树，、为其右子树，以此类推，可知是左子树的根，是右子树的根，是的左孩子，是的右孩子。由此可知，该二叉树的后序遍

32、历为、。 从二叉树的遍历过程可知，从先序遍历序列和后续遍历序列中无法将左子树和右子树上的结点区分开，因此，由某棵二叉树的先序遍历和后序遍历序列不能构造出该二叉树的中序遍历序列。 问题:34. 下面关于二叉树的叙述，正确的是_。A.完全二叉树的高度h与其结点数n之间存在确定的关系B.在二叉树的顺序存储和链式存储结构中，完全二叉树更适合采用链式存储结构C.完全二叉树中一定不存在度为1的结点D.完全二叉树中必定有偶数个叶子结点答案:A解析 如果一棵具有门个结点的深度为k的二叉树，它的每一个结点都与深度为k的满二叉树中编号为1n的结点一一对应，称之为完全二叉树。由其性质：具有n个节点的完全二叉树的深度

33、为|log2n|+1。可知A正确。 对于B，按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树的结点元素。因此用顺序存储结构更利于完全二叉树的结点访问。 对于C，如图(a)所示为完全二叉树，但它有度为1的结点，即2号结点。对于D，如图(b)所示为完全二叉树，但它有奇数个叶子结点。 问题:35. 表达式(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表示)中的空指针总数必定为_。为形成中序(先

34、序、后序)线索二叉树，现对该二叉链表所有结点进行如下操作：若结点p的左孩子指针为空，则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点；若p的右孩子指针为空，则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点，则_。 36.A.m+2B.m+1C.mD.m-1答案:B37.A.sright指向的结点一定是s所指结点的直接后继结点B.sleft指向的结点一定是s所指结点的直接前驱结点C.从s所指结点出发的right链可能构成环D.s所指结点的left和right指针一定指向不同的结点答案:C问题:38. 若将某有序树T转换

35、为二叉树T1，则T中结点的后(根)序列就是T1中结点的_遍历序列。例如，图(a)所示的有序树转化为二叉树后如图(b)所示。 A.先序B.中序C.后序D.层序答案:B问题:39. 表达式“X=A+B(C-D)/E”的后缀表示形式可以为_(运算符优先级相同时，遵循左结合的原则)。A.XAB+CDE/-x=B.XA+BC-DE/x=C.XABCD-xE/+=D.XABCDE+x-/=答案:C 对于二叉查找树(Binary Search Tree)，若其左子树非空，则左子树上所有结点的值均小于根结点的值；若其右子树非空，则右子树上所有结点的值均大于根结点的值；左、右子树本身就是两棵二叉查找树。因此，对

36、任意一棵二叉查找树进行_遍历可以得到一个结点元素的递增序列。在具有n个结点的二叉查找树上进行查找运算，最坏情况下的算法复杂度为_。 40.A.先序B.中序C.后序D.层序答案:B41.A.O(n2)B.O(nlog2n)C.O(log2n)D.O(n)答案:D问题:42. 表达式“(a+b)*(c-d)”的后缀表示为_。A.ab+cd-*B.abcd+-*C.ab+*cd-D.abcd*+-答案:A问题:43. 已知某二叉树的中序列为CBDAEFI、先序列为ABCDEFI，则该二叉树的高度为_ 。A.2B.3C.4D.5答案:C问题:44. 下图所示平衡二叉树(树中任一结点的左右子树高度之差不

37、超过1)中，结点A的右子树AR高度为h，结点B的左子树HL高度为h，结点C的左子树CL、右子树CR高度都为h-1。若在CR中插入一个结点并使得CR的高度增加1，则该二叉树_。 A.以B为根的子二叉树变为不平衡B.以C为根的子二又树变为不平衡C.以A为根的子二叉树变为不平衡D.仍然是平衡二叉树答案:C问题:45. 拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点ViVj有一条路径，则顶点Vi必然在顶点Vj之前。对于下面所示的有向图，_是其拓扑序列。 A.1234576B.1235467C.2135476D.2134567答案:C解析 对AOV网进行拓扑排序

38、的方法如下。 在AOV网中选择一个入度为0(没有前驱)的顶点且输出它； 从网中删除该顶点及与该顶点有关的所有边； 重复上述两步，直至网中不存在入度为零的顶点为止。 本题中只有序列“2135476”是其拓扑序列。 问题:46. 从存储空间的利用率角度来看，以下关于数据结构中图的存储的叙述，正确的是_。A.有向图适合采用邻接矩阵存储，无向图适合采用邻接表存储B.无向图适合采用邻接矩阵存储，有向图适合采用邻接表存储C.完全图适合采用邻接矩阵存储D.完全图适合采用邻接表存储答案:C解析 邻接矩阵是用矩阵来指出顶点和顶点之间是否存在着关系。如果图有n个结点，则需要用n2个元素来表示顶点间的关系。 邻接表

39、是图的一种链式存储结构。在邻接表中，图中的每一个顶点都需要建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边。对于无向图，若无向图有n个顶点，e条边，则它的邻接表需要n个头结点和2e个表结点。对于有向图，若有n个顶点、e条边，则它的邻接表需要，2个头结点和e个表结点。等Pn(n-1)/2时，采用邻接表表示图比用矩阵节省空间。可见，完全图适合采用邻接矩阵存储。 问题:47. 无向图中一个顶点的度是指图中与该顶点相邻接的顶点数。若无向图G中的顶点数为n，边数为e，则所有项点的度数之和为_。A.n*eB.n+eC.2nD.2e答案:A解析 在无向图中，一条边与两个顶点相连，边数为e的无向图所

40、有顶点的度数之和为2e。问题:48. 设一个包含N个顶点、E条边的简单无向图采用邻接矩阵存储结构(矩阵元素Aij等于1/0分别表示顶点i与顶点j之间有/无边)，则该矩阵中的非零元素数据为_。A.NB.EC.2ED.N+E答案:C解析 邻接矩阵是一个用来存放顶点间关系(边或弧)数据的二维数组，如果顶点间存在边，则用1表示，用0表示不存在的边。在无向图中，邻接矩阵中的内容是对称的，如果顶点A和顶点B之间存在公共边，则表示顶点A可以到达顶点B，顶点B也可到达顶点A。如果简单无向图有E条边，则邻接矩阵中非零元素数据有2E个。问题:49. _是下图的合法拓扑序列。 A.6 5 4 3 2 1B.1 2

41、3 4 5 6C.5 6 3 4 2 1D.5 6 4 2 1 3答案:A解析 拓扑排序是将AOV网中所有顶点排成一个线陛序列的过程。对AOV网进行拓扑排序的方法如下 在AOV网中选择一个入度为0的顶点，输出它。 从网中删除该顶点及其与该顶点有关的所有边。 重复上述两步，直至网中不存在入度为0的顶点为止。 本题的拓扑排序过程如下： 得到的拓扑序列为6 5 4 3 2 1。 问题:50. 邻接矩阵和邻接表是图(网)的两种基本存储结构，对于具有n个顶点、e条边的图，_。A.进行深度优先遍历运算所消耗的时间与采用哪一种存储结构无关B.进行广度优先遍历运算所消耗的时间与采用哪一种存储结构无关C.采用邻

42、接表表示图时，查找所有顶点的邻接顶点的时间复杂度为D(ne)D.采用邻接矩阵表示图时，查找所有顶点的邻接顶点的时间复杂度为(n2)答案:D解析 深度优先遍历图实质上是对某个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当图采用邻接矩阵表示时，查找所有邻接点所需要的时间是O(n2)，若以邻接表作为图的存储结构，则需要O(e)的时间复杂度查找所有顶点的邻接点。广度优先遍历和深度优先遍历的时间复杂度相同，其实质都是通过边或弧找邻接点的过程。问题:51. 下面关于图(网)的叙述，正确的是_。A.连通无向网的最小生成树中，顶点数恰好比边数多1B.若有向图是强连通的，则其边数至少是顶点数的2

43、倍C.可以采用AOV网估算工程的工期D.关键路径是AOE网中源点至汇点的最短路径答案:A解析 生成树即极小连通子图，包含图的所有n个结点，但只含图的n-1条边。在生成树中添加一条边之后，必定会形成回路或环。所以A正确。 在有向图G中，如果对于每一对Vi，VjViVVJ，从ViVj和从VjVi都存在路径，则称G是强连通图。下图为强连通图，但其边数等于顶点数。 AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图。 AOE网：用顶点表示事件，弧表示活动，权表示活动持续的时间。通常AOE网用来估算工程的完成时间。 关键路径：由于在AOE网中有些活动可以并行地进行，所以完成工程的最短时间是从开始

44、点到完成点的最长路径的长度(指路径上各活动持续时间之和，不是路径上弧的数目)，最长的路径叫做关键路径。 问题:52. _的邻接矩阵是一个对称矩阵。A.无向图B.AOV网C.AOE网D.有向图答案:A问题:53. 具有n个顶点、e条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运算的时间复杂度均为_。A.O(n2)B.O(e2)C.O(ne)D.O(n+e)答案:D 设一个包含N个顶点、E条边的简单有向图采用邻接矩阵存储结构(矩阵元素Aij等于1/0分别表示顶点i与顶点j之间有/无弧)，则该矩阵的元素数目为_，其中非零元素数目为_。 54.A.E2B.N2C.N2-E2D.N2+E2答

45、案:B55.A.NB.N+EC.ED.N-E答案:C问题:56. 拓扑排序是指有向图中的所有顶点排成一个线性序列的过程，若在有向图中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。因此，若不能得到全部顶点的拓扑排序序列，则说明该有向图一定_。A.包含回路B.是强连通图C.是完全图D.是有向树答案:A 某工程计划如图所示，各个作业所需的天数如表所示，设该工程从第0天开工，则该工程的最短工期是_天，作业J最迟应在第_天开工。 作业 A B C D E F G H I J 所需 天数 7 6 8 10 7 3 2 4 3 757.A.17B.18C.19D.20答案:D58

46、.A.11B.13C.14D.16答案:B问题:59. 拓扑序列是无环有向图中所有顶点的一个线性序列，图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系，_为图所示有向图的一个拓扑序列。 A.1 2 3 4 5 6 7B.1 5 2 6 3 7 4C.5 1 2 6 3 4 7D.5 1 2 3 7 6 4答案:B问题:60. 一个含有n个顶点和e条边的简单无向图，在其邻接矩阵存储结构中共有_个零元素。A.eB.2eC.n2-eD.n2-2e答案:D问题:61. 若采用邻接矩阵来存储简单有向图，则其某一个顶点i的入度等于该矩阵。A.第i行中值为1的元素个数B.所有值为1的元素总数C.第i行

47、及第i列中值为1的元素总个数D.第i列中值为1的元素个数答案:D问题:62. 以下关于哈希(Hash，散列)查找的叙述中，正确的是_。A.哈希函数应尽可能复杂些，以消除冲突B.构造哈希函数时应尽量使关键字的所有组成部分都能起作用C.进行哈希查找时，不再需要与查找表中的元素进行比较D.在哈希表中只能添加元素不能删除元素答案:B解析 哈希表中的元素是由哈希函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系(称为哈希函数)计算出的值，即为该元素的存储地址。所以在构造哈希函数时应尽量使关键字的所有组成部分起作用。问题:63. 在13个元素构成的有序表M1.13中进行折半查找(向下取整)，若找到的元素为M4，则被比较的元素依次为_。A.M7、M3、M5、M4B.M7、M5、M4C.M7、M6、M4D.M7、M4答案:A解析 由于该有序表中共有13个元素，且元素下标为1至13，即low=1，high=13，用折半公式(low+high)/2，可以计算出首次被比较元素的下标是7，即M7。当与M7比较完毕以后，发现不是要找的数据，所以继续查找。此时，low=1，high=6，用折半公式(low+high)/2并向下取整，可以计算出首次被比较元素的下标是3，即