数据结构概论期末考试 一、 选择：(答案写在相应框格内，每题2分，共30分)题目123456789101112131415答案CCCCABDBAAADCBB1、非空循环链表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叉链表表示中，有多少个空指针。答：n个结点的k叉数共有n*k个指针域，已使用的指针域为n-1，所以空指针的个数为：n(k-1)+1A4、 已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,请画出该二叉树。CB答：EDFIHG5、 无向图G有6个结点和9条边,并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点0出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。答：深度优先搜索法：0-2-3-4-5-1广度优先搜索法:0-1-2-4-5-3四、 算法题：(每题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);算法功能：寻找*p结点的直接前驱结点*q。void Demo2(ListNode *p,ListNode *q)/*p,*q是某个链表中的两个结点 DataType temp;temp=p-data;p-data=q-data;q-data=temp;算法功能：*p结点和*q结点的值互换。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); while (!stackempty(t) push(s,pop(T); while(!queueempty(&q) push(s,dequeue(&q);答：（1）将栈S中的元素依次出栈，同时将第奇数次的元素入栈T，将第偶数次的元素入队列Q。 （2）s=（1,3,5,7,6,4,2） 数据结构概论 试卷 共3页（第1页） 选择题答案写在选择题答题区内，其它各题在答案区域内作答，超出黑色边框区域的答案无效！