1、 谋学网 一、 选择：(答案写在相应框格内，每题 2分，共 30分)题目 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15答案1、非空循环链表 head 的尾结点 p 满足下列( )条件。A. head-next=p B. head=p C. p-next=head D. p-next=nil2、设栈 s的类型为 sqstack ，判定栈空的条件是( )。 A. s = =nil B. s-top= =0 C. s.top = =0 D. s.top = = nil3、具有 4个顶点的无向完全图有( )边。A. 20 B. 12 C.6 D.84、一个向量的第一个元素的地
2、址是 100，每个元素的长度是 2 ，则第五个元素的地址是( )。A. 102 B. 110 C. 108 D. 1205、一个栈的输入序列是 a,b,c,d,e ，则不可能输出是( )。A. ecdab B. cdeba C. decba D. abcde6、已知二叉树的前、中根序列分别是 abdefcg 和 defbagc，则该二叉树的后根遍历序列是( )。A. defbgca B. fedbgca C. abcdefg D. gfedcba7、深度为 4 的二叉树至多有个( )结点。A.12 B.13 C.14 D.158、具有 6个顶点的无向图至少要有( )条边才能确保是一个连通图。A
3、.4 B.5 C.6 D.79、已知一个顺序存储的线性表,设每个结点需占 m个存储单元,若第一个结点的地址为 da1,则第 i个结点的地址为()A.da1+(i-1)*m B.da1+i*m C.da1-i*m D.da1+(i+1)*m10、在 n个结点的顺序表中,算法的时间复杂度是 O(1)的操作是:A.访问第 i个结点(1=2)叉树的 K叉链表表示中，有多少个空指针。4、已知一棵二叉树的前序序列和中序序列分别为 abdghcefi和 gdhbaecif,请画出该二叉树。5、无向图 G有 6个结点和 9条边,并依次输入这 9条边为(0,1),(0,2),(0,4),(0,5),(1,2),
4、(2,3),(2,4),(3,4),(4,5),试从顶点 0出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。四、 算法题：(每题 10分，共 20分)1、下述两个算法的功能是什么?ListNode *Demo1(LinkList L,ListNode *p)/L是有头结点的单链表ListNode *q=L-next;while(qif(q) return q;else Error(“*p is not in L“);void Demo2(ListNode *p,ListNode *q)/*p,*q是某个链表中的两个结点DataType temp;temp=p-data;p-data=q-data;q-data=temp;2、设栈 S=(1,2,3,4,5,6,7) ，其中 7为栈顶元素。(1) 简述函数 f31中第一个循环语句的功能；(2) 写出调用 f31( stack t; int i=0;Initqueue( initstack(谋学网 while(!stackempty(s)if(i=!i)!=0) push(else enqueue(while (!stackempty(t) push(s,pop(T);while(!queueempty(
