2011-2012学年第1学期数据结构期末试卷a

《2011-2012学年第1学期数据结构期末试卷a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、密封线内禁止答题南京信息职业技术学院试卷2011/2012学年第一学期期末考试试卷[A]卷课程名称：数据结构考试时间：100分钟命题人边长生2011年12月15日审批人年月日使用班级：41043X成绩：。。题号一二三四总分阅卷人得分一、选择题（请将答案填在下表中30分，每题3分）123456789101、采用链式存储结构存储时，要求占用的存储空间地址。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.可连续可不连续2、若让元素a，b，c依次进栈，则出栈次序不可能出现种情况。A．c，b，aB

2、．b，a，cC．c，a，bD．a，c，b3、快速排序的平均时间复杂度是：。A.O(n2)B.O(n)C.O(n*log2n)D.O(log2n)4、一颗二叉树上第4层的结点数最多为。A.8B.16C.15D.45、在一棵二叉树中，度数为2的结点数等于n2，度数为1的结点数等于n1，那么度数为0的结点数等于是_______。A.n1+1B.n1+2C.n2+1D.n2+26、在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号。A.2i-1B.2iC.2i+1D.2i+27、在一个具有n个

3、顶点的有向完全图中，所含的弧数为。A．nB.n*(n-1)C.n*(n+1)D.n*(n-1)/28、n个顶点的连通图至少有条边。A.n-1B.nC.n+1D.09、顺序查找法适合于存储结构为的线性表。A.只能是顺序存储B.顺序存储或链接存储都可以C.只能是链式存储D.压缩存储10、对线性表进行折半查找时，要求线性表必须。A.以顺序存储方式存储B.以链式存储方式存储C.以顺序存储方式存储，且数据元素有序D.以链式存储方式存储，且数据元素有序二、填空题（15分，每空3分）1．在一个单链表中删除p所指结点

4、的下一个结点时，应执行以下操作：q=p->next;p->next=；deleteq；2.下图是单链表的插入算法示意图数据结构考试试卷A卷第3页共3页密封线内禁止答题newPtr->next=tmpPtr->next；tmpPtr->next=3.函数insert_sort(inta[],intcount)是用直接插入排序法对指定数组的前count个元素从小到大排序。voidinsert_sort(inta[],intcount){inti,j,t;for(i=1;i

5、i],…,a[count-1]的比较和插入*/{t=a[i];j=；while(j>=0&&t

6、12341926463825ABEDCF4.已知序列{4，1，6，3，8，5}，试构造二叉排序树，并写出中序遍历结果。数据结构考试试卷A卷第3页共3页密封线内禁止答题四、写程序题（27分）1.线性链表类如下：template//T为虚拟类型structnode{Td;node*next;};template//模板声明,数据元素虚拟类型为Tclasslinked_LList//线性链表类{private://数据成员node*head;//链表头指针public:

7、//成员函数linked_LList();//（1）构造函数,建立空链表voidprt();//（2）扫描输出链表中的元素voidins(Tx,Tb);//（3）在元素x的结点前插入新元素bintdel(Tx);//（4）删除元素x的结点};请写出（3）的成员函数(13分)要求：如果找不到元素x，将新元素b插入到链尾。2.写出希尔排序程序（14分）要求：应用希尔排序算动漫对数组A[n]进行由小到大排序voidshellsort(intA[],intn){}数据结构考试试卷A卷第3页共3页