一、选择：(答案写在相应框格内，每题2分，共30分)题目123456789101112131415答案1、非空循环链表head的尾结点p满足下列()条件。A.head->next==pB.head==pC.p->next==headD.p->next==nil2、设栈s的类型为sqstack，判定栈空的条件是()。A.s==nilB.s->top==0C.s.top==0D.s.top==nil3、具有4个顶点的无向完全图有()边。A.20B.12C.6D.84、一个向量的第一个元素的地址是100，每个元素的长度是2，则第五个元素的地址是()。A.102B.110C.108D.1205、一个栈的输入序列是a,b,c,d,e，则不可能输出是()。A.ecdabB.cdebaC.decbaD.abcde6、已知二叉树的前、中根序列分别是abdefcg和defbagc，则该二叉树的后根遍历序列是()。A.defbgcaB.fedbgcaC.abcdefgD.gfedcba7、深度为4的二叉树至多有个()结点。A.12B.13C.14D.158、具有6个顶点的无向图至少要有()条边才能确保是一个连通图。A.4B.5C.6D.79、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为()A.da1+(i-1)*mB.da1+i*mC.da1-i*mD.da1+(i+1)*m10、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:A.访问第i个结点(1<=i<=n)和求第i个结点的直接前趋(2<=i<=n)B.在第i个结点后插入一个新的结点(1<=i<=n)C.删除第i个结点(1<=i<=n)D.将n个结点从小到大排序.11、用邻接表表示图进行深度优先遍历时,通常采用()来实现算法.A.栈B.队列C.树D.图12、非线性结构中,每个结点()A.无直接前趋.B.只有一个直接前驱和后继C.只有一个直接前驱和个数不受限制的直接后继D.有个数不受限制的直接前驱和后继.13、在最好和最坏情况下的时间复杂度均为O(n*logn)且稳定的排序方法是：A.快速排序B.堆排序C.归并排序D.基数排序14、设高度为h的二叉树中只有度为0，2的结点，则该二叉树至少有()个结点。A.2hB.2h-1C.2h+1D.h+115、若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为：()A.4B.5C.6D.7二、填空题：(每空2分，共20分)1、在n个结点的顺序表中,删除一个结点需平均移动_______个结点,具体的移动次数取决于____________.2、在循环链表中,可根据在一结点的地址遍历整个链表,而单链表中需要知道_________才能遍历整个链表。3、在栈中存取数据的原则是：____________.4、在栈结构中，允许插入，删除的一端称为______，另一端称为_________。5、顺序表相对于链表的优点有_______和_________.6、某二叉树的前序和后序正好相反，则该二叉树一定是__________二叉树。7、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为：_________三、解答题：(每题6分，共30分)1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？2、若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,分别写出以第一个记录为基准得到的前三次划分结果。3、在具有n个结点的K（k>=2)叉树的K叉链表表示中，有多少个空指针。4、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请画出该二叉树。5、无向图G有6个结点和9条边,并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点0出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。四、算法题：(每题10分，共20分)1、下述两个算法的功能是什么?ListNode*Demo1(LinkListL,ListNode*p){//L是有头结点的单链表ListNode*q=L->next;while(q&&q->next!=p)q=q->next;if(q)returnq;elseError("*pisnotinL");}voidDemo2(ListNode*p,ListNode*q){//*p,*q是某个链表中的两个结点DataTypetemp;temp=p->data;p->data=q->data;q->data=temp;}2、设栈S=(1,2,3,4,5,6,7)，其中7为栈顶元素。(1)简述函数f31中第一个循环语句的功能；(2)写出调用f31(&s)后的s。Voidf31(stack*s){queueq;stackt;inti=0;Initqueue(&q);initstack(&s);while(!stackempty(s))if((i=!i)!=0)push(&T,pop(S));elseenqueue(&q,pop(s));while(!stackempty(t))push(s,pop(T));while(!queueempty(&q))push(s,dequeue(&q));}
