福建师范大学16年8月课程考试《数据结构概论》作业考核试题资料.doc

谋学网一、 选择：(答案写在相应框格内，每题2分，共30分)题目123456789101112131415答案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、一个向量的第一个元素的地址是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.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=i=n)和求第i个结点的直接前趋(2=i=n)B.在第i个结点后插入一个新的结点(1=i=n)C.删除第i个结点(1=i=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(LinkList L,ListNode *p)/L是有头结点的单链表 ListNode *q=L-next; while(q&q-next!=p) q=q-next; if(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(&s)后的s。Void f31(stack *s) queue q; stack t; int i=0; Initqueue(&q); initstack(&s); while(!stackempty(s) if(i=!i)!=0) push(&T,pop(S); else enqueue(&q,pop(s);