2015年春季数据结构期末试卷(A卷)

1、华南农业大学期末考试试卷（A卷）2014-2015学年第 2 学期 考试科目： 数据结构 考试类型：（闭卷）考试 考试时间：120 分钟学号 姓名 年级专业 题号一二三四总分得分评阅人考生须知：1. 答案必须写在“答卷”上，写在试卷上不得分；2. 考试结束时，只回收答卷，不回收试卷；3. 必须在答卷上正确填写班级、学号、姓名等内容，否则没有考试成绩。得分一、选择题（本大题共 10 小题，每小题2分，共20分）1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。 A数据的处理方法 B数据元素的类型 C数据元素间的关系 D数据的存储方法2、某链表最常用的操作是在最后一个节点之后插入

2、节点或删除节点，则采用（ ）存储方式最节省运算时间。 A单链表 B给出表头指针的单循环链表C双链表 D有头结点的双循环链表 3、一个栈的进栈序列是a、b、c、d、e，则不可能的出栈序列是（ ）。Aedcba Bdecba Cdceab Dabcde4、二维数组M的每一个元素占用4个字节的存储空间，行下标i的范围从0到4，列下标j的范围从0到5，M按行优先存储时元素M35的地址与M按列优先存储时元素（ ）的地址相同 。 AM24 B M34 CM44 DM355、一个n*n的对称矩阵采用压缩存储，以行优先的方式放入内存，则占用的存储空间为( )。 An*n Bn*n/2 C. n*(n+1)/2

3、 Dn*(n-1)/26、用希尔排序对一个数据序列进行排序时， 若 第 1 趟 排 序 结 果 为9,1,4,13,7,8,20,23,15， 则该趟排序采用的增量（间隔）可能是（ ） 。A 2 B 3 C 4 D 5。7、设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树结点数至少为（ ）。A2hB2h-1C2h+1Dh+18、下列程序段的时间复杂度是（ ）。 x=0; for(k=1;k=n;k=k*2) for(j=1;jnext=NULL; q=*L; printf(请输入%d个数据n,n); for(i=1;idata); （8） q=q-next; （9） 4、对顺序表L作快

4、速排序void QSort(SqList *L,int low,int high) /* 对顺序表L中的子序列L.rlow.high作快速排序。算法10.7 */ int pivotloc; if( （10） ) /* 长度大于1 */ pivotloc=Partition(L,low,high); /* 将L.rlow.high一分为二 */ （11） /* 对低子表递归排序，pivotloc是枢轴位置 */ （12） /* 对高子表递归排序 */ void QuickSort(SqList *L) /* 对顺序表L作快速排序*/ QSort(L,1,(*L).length); 5、对顺序表

5、L作折半插入排序void BInsertSort(SqList *L) int i,j,m,low,high; for(i=2;i=high+1;-j) (*L).rj+1=(*L).rj; /* 记录后移 */ (*L).rhigh+1=(*L).r0; /* 插入 */ 得分四、算法设计题（本大题共 2小题，每小题10分，共20分。请先简要说明算法思想，然后写出算法的C语言源代码实现）1、将头指针为a的单链表A分解成两个单链表A和B，表A头指针为a，表B的头指针为b，表A含有原单链表A序号为奇数的元素，而表B含有原单链表A序号为偶数的元素，且均保持原来的相对次序。单链表存储结构定义如下：struct LNode int data; struct LNode *next; ; typedef struct LNode *LinkList;统一使用函数名：void Split(LinkList &A，LinkList &B)2、一个具有n个结点的完全二叉树采用顺序存储方式，其数据存放在整型一维数组a中，编写非递归算法对其进行先序遍历。算法可以直接调用栈的基本操作：初始化：InitStack(SqStack &S) 入栈：Push(SqStack &S