全真试题(三) 本试卷分两部分,第一部分为选择题,1页至3页,第二部分为非选择题,4页至12页,共12页; 选择题30分,非选择题70分,满分100分。考试时间150分钟。 第一部分选择题(共30分) 单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个选项中只有一个 是符合题目要求的,请将其代码填在题后的括号内。错选或未选均无分。 1.下面程序段的时间复杂度是() for(i=0; i<n; 1++) for(=1;j<m;j++) A O(n) B O(m+n-1) C O(m+n) D O(m*n 2在单链表中,指针p指向元素为x的结点,实现“删除x的后继”的语句是() A p=p->next; B. p->next=p->next->next C. p->next=p: D p=p->next->next; 3在头指针为head且表长大于1的单循环链表中,指针p指向表中某个结点,若p>next>next=head 则() Ap指向头结点B.p指向尾结点 C·*p的直接后继是头结点D.*p的直接后继是尾结点 4判定“带头结点的链队列为空”的条件是() A.Q. front==NULL B.Q. REARNULL C.Q. front=Q rear D.Q. front!=Qrear 5设有两个串T和P,求P在T中首次出现的位置的串运算称作() A.联接B求子串C字符定位D子串定位 6广义表A=(a(b),O(cd,e)的长度为() A.4B.5C.6D.7 7.一棵含18个结点的二叉树的高度至少为() A.3B.4C.5D6 8已知二叉树的先序序列为 ABDECF,中序序列为 DBEAFC,则后序序列为() A DEBAFC B DEFBCA C DEBCFA D. DEBFCA 9无向图中一个顶点的度是指图中() A通过该项点的简单路径数B与该顶点相邻接的顶点数 C通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示,从顶点a出发 进行广度优先遍历可能得到的序列为() A. fbd Bac bdf Dacd bfe 11在下列排序方法中,平均时间性能为 O(nologn)且空间性能最好的是() A快速排序B堆排序C归并排序D基数排序全真试题（三） 本试卷分两部分，第一部分为选择题，1 页至 3 页，第二部分为非选择题，4 页至 12 页，共 12 页； 选择题 30 分，非选择题 70 分，满分 100 分。考试时间 150 分钟。 第一部分 选择题（共 30 分） 一、单项选择题（本大题共 15 小题，每小题 2 分，共 30 分）在每小题列出的四个选项中只有一个 是符合题目要求的，请将其代码填在题后的括号内。错选或未选均无分。 1.下面程序段的时间复杂度是（ ） for (i=0; i＜n; i++) for (j=1; j＜m; j++) A[i][j]=0; A.O (n) B.O(m+n-1) C.O(m+n) D.O(m*n) 2.在单链表中，指针 p 指向元素为 x 的结点，实现“删除 x 的后继”的语句是（ ） A.p=p-＞next; B.p-＞next =p-＞next -＞next ; C.p-＞next =p; D.p=p-＞next-＞next; 3.在头指针为 head 且表长大于 1 的单循环链表中，指针 p 指向表中某个结点，若 p-＞next-＞next=head， 则（ ） A.p 指向头结点 B.p 指向尾结点 C.*p 的直接后继是头结点 D.*p 的直接后继是尾结点 4.判定“带头结点的链队列为空”的条件是（ ） A.Q.front ==NULL B.Q.REAR==NULL C.Q.front==Q.rear D.Q.front!=Q.rear 5.设有两个串 T 和 P，求 P 在 T 中首次出现的位置的串运算称作（ ） A.联接 B.求子串 C.字符定位 D.子串定位 6.广义表 A=(a,(b),(),(c,d,e))的长度为（ ） A.4 B.5 C.6 D.7 7.一棵含 18 个结点的二叉树的高度至少为（ ） A.3 B.4 C.5 D.6 8.已知二叉树的先序序列为 ABDECF，中序序列为 DBEAFC，则后序序列为（ ） A.DEBAFC B.DEFBCA C.DEBCFA D.DEBFCA 9.无向图中一个顶点的度是指图中（ ） A.通过该项点的简单路径数 B.与该顶点相邻接的顶点数 C.通过该顶点的回路数 D.与该顶点连通的顶点数 10.已知一个图如下所示，从顶点 a 出发 进行广度优先遍历可能得到的序列为（ ） A.a c e f b d B.a c b d f e C.a c b d e f D.a c d b f e 11.在下列排序方法中，平均时间性能为 O(nologn)且空间性能最好的是（ ） A.快速排序 B.堆排序 C.归并排序 D.基数排序 a f b c d e