2011-2012学年第1学期数据结构期末试卷A.doc

南 京 信 息 职 业 技 术 学 院 试 卷 2011 / 2012 学年第一学期期末考试试卷 [A]卷 课程名称： 数据结构 考试时间：100分钟 命题人 边长生 2011 年 12 月 15 日 审批人 年 月 日 使用班级：41043X 成绩： 。。 题号 一 二 三 四 总分 阅卷人 得分 一、选择题（请将答案填在下表中 30分，每题3分） 1 2 3 4 5 6 7 8 9 10 1、采用链式存储结构存储时，要求占用的存储空间地址 。 A.必须是连续的 B.部分地址必须是连续的 C.一定是不连续的 D.可连续可不连续 2、若让元素a，b，c依次进栈，则出栈次序不可能出现 种情况。 A．c，b，a B．b，a，c C．c，a，b D．a，c，b 3、快速排序的平均时间复杂度是： 。 A.O(n2) B. O(n) C. O(n*log2n) D. O( log2n) 4、一颗二叉树上第4层的结点数最多为 。 A .8 B.16 C. 15 D. 4 5、在一棵二叉树中，度数为2的结点数等于n2，度数为1的结点数等于n1，那么度数为0的结点数等于是_______。 A.n1+1 B.n1+2 C.n2+1 D.n2+2 6、在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号 。 A.2i-1 B.2i C.2i+1 D.2i+2 7、在一个具有n个顶点的有向完全图中，所含的弧数为 。 A．n B.n*(n-1) C.n*(n+1) D.n*(n-1)/2 8、n 个顶点的连通图至少有 条边。 A.n-1 B.n C.n+1 D.0 9、顺序查找法适合于存储结构为 的线性表。 A.只能是顺序存储 B. 顺序存储或链接存储都可以 C.只能是链式存储 D. 压缩存储 10、对线性表进行折半查找时，要求线性表必须 。 A.以顺序存储方式存储 B.以链式存储方式存储 C.以顺序存储方式存储，且数据元素有序 D.以链式存储方式存储，且数据元素有序 二、填空题（15分，每空3分） 1．在一个单链表中删除p所指结点的下一个结点时，应执行以下操作： q=p-next; p-next= ； delete q； 2.下图是单链表的插入算法示意图 newPtr-next=tmpPtr-next； tmpPtr-next= 3.函数insert_sort(int a[],int count)是用直接插入排序法对指定数组的前count个元素从小到大排序。 void insert_sort(int a[], int count) { int i,j,t; for(i=1;icount;i++) /*控制a[i], …,a[count-1]的比较和插入*/ { t=a[i]; j= ； while(j=0ta[j]) /*在有序部分中寻找元素a[i]的插入位置*/ { ; j--; } ; } return； } 三、应用题（28分，每题7分） 1..已知权值{16，6，3，5}，试画出它对应的哈夫曼树（要求每个结点的左子结点的值小于右子结点的值） 2..已知一棵二叉树的先序序列与中序序列分别如下,试画出此二叉树。 先序序列：ABCDFGI 中序序列：CBDAGFI 3.直接写出下面图的最小生成树（普里姆算法或克鲁斯卡尔算法均可） 4.已知序列{4，1，6，3，8，5}，试构造二叉排序树，并写出中序遍历结果。 四、写程序题（27分） 1. 线性链表类如下： template class T //T为虚拟类型 struct node { T d; node