//八大排序：（插入排序）：1直接插入排序2希尔排序（交换排序）：3冒泡排序4快速排序：寻找中点，对左右递归排序（选择排序）：5简单选择排序6堆排序7归并排序8基数排序习题一1．在数据结构中，数据的基本单位是_________。

A. 数据项B. 数据类型C. 数据元素D. 数据变量2. 计算算法的时间复杂度是属于一种_______。

A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法3. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址_______。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续不连续都可以4. 在顺序表存储结构下，插入操作算法。

A. 需要判断是否表满B. 需要判断是否表空C. 不需要判断表满D. 需要判断是否表空和表满5. 在一个单链表中，若删除p所指结点的后继结点，则执行。

A. p.next = p.next.next;B. p.next = p.next;C. p = p.next.next;D. p = p.next; p.next = p.next.next;6. 若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用的存储方式是。

A. 单链表B. 双向链表C. 单循环链表D. 顺序表7. 在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，进行一次删除操作后，此时栈顶元素是。

A. ｃB.ｄC.ｂD. ｅ8. 栈和队列的共同点是。

A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有共同点9. 判定一个循环队列QU（最多元素为m0）为满队列的条件是。

A. QU.front==QU.rearB. QU.front!=QU.rearC. QU.front==(QU.rear+1) % m0D. QU.front!=(QU.rear+1) % m010．以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋B.线性结构中的一个结点至多只有一个直接后继C.树形结构可以表达(组织)更复杂的数据D.树(及一切树形结构)是一种"分支层次"结构11. 如下图所示的4 棵二叉树中，不是完全二叉树。

12. 深度为5 的二叉树至多有个结点。

//设深度为k (2^k)-1A. 16B. 32C.31D.1013．在一棵二叉树中，度数为2的结点数等于n2，度数为1的结点数等于n1，那么度数为0的结点数等于是_______。

A.n1+1B. n2+1C. n1+2D.n2+214. 对含有个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

A.0B.1C.2D.不存在这样的二叉树15. 在一个图中，所有顶点的度数之和等于所有边数的倍。

A. 1/2B. 1C. 2D. 4无向图：顶点度数之和为边数的两倍有向图：在一条边AB（A→B）都会给A提供一个出度，给B提供一个入度则顶点度数之和=2*顶点入度之和=2*顶点出度之和=顶点入度之和+顶点出度之和=2*边数16. 具有6 个顶点的无向图至少应有条边才能确保是一个连通图。

A. 5B. 6C. 7D. 8设边数为x，x>=6-1,x=n-1时图为树，任取顶点s、t，从s到t有且只有一条无向路，若有向s→t则t→s有向必不存在。

无向图最多n*(n-1)/2，有向图最多n*(n-1)17. 对于一个具有n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是。

A. nB. (n-1)2C. n-1D. n218. 对线性表进行折半(二分)查找时，要求线性表的存储方式是。

A. 顺序存储B. 链接存储C. 以关键字有序排序的顺序存储D. 以关键字有序排序的链接存储//二分查找要使用下标，数据按递增或递减排好19. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。

A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序（扫描最小）//插入排序：希尔排序、冒泡排序20. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。

A. 38，40，46，56，79，84B. 40，38，46，79，56，84C. 40，38，46，56，79，84D. 40，38，46，84，56，7921. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为。

A. 希尔排序B. 归并排序C. 插入排序D. 选择排序22. 快速排序的平均时间复杂度是：。

A.O(n2)B. O(n)C. O(n*log2n)D. O( log2n)23. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号。

A.2i-1B.2iC.2i+1D.2i+224. 在一个具有n个顶点的有向完全图中，所含的弧数为。

A．n B.n*(n-1)C.n*(n+1)D.n*(n-1)/225.顺序查找法适合于存储结构为的线性表。

A.只能是顺序存储B. 顺序存储或链接存储都可以C.只能是链式存储D. 压缩存储二、填空题（20分，每空1分）1. 数据结构在物理上可分为顺序存储结构和链式存储结构。

2. 在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的___前一__结点。

3.在单链表中，指针p所指结点为最后一个结点的条件是p.next==null;。

4. 在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是n-i+1。

//i-1，n-(i-1)5. 在非空线性链表中由p所指的链结点后面插入一个由q所指的链结点的过程是依次执行动作q.next = p.next; 。

6. 设有一个空栈，现输入序列为1，2，3，4，5。

经过push，push，pop，push，pop，push，pop，push后，输出序列是2、3、4。

7. 根据下图中的树回答问题：（1）这棵树的根结点是；（2）这棵树的叶子结点是；（3）结点k3 的度是；（4）这棵树的度为；（5）这棵树的深度是；（6）结点k3 的孩子是；（7）结点k3 的双亲结点是。

8. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态9. 在无向图G 的邻接矩阵A 中，若A[i][j]等于1，则A[j][i]等于1//无向图的邻接矩阵是对称矩阵10. 在有向图的邻接矩阵上，由第i行可得到第个结点的出度。

11. 在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第8 个记录45 插入到有序表时，为寻找插入位置需比较5次。

12. 在插入和选择排序中，若初始数据基本正序，则选用插入排序//关键字比较次数和记录移动次数都很少；若初始数据基本反序则选用选择排序//两者关键字比较次数差不多，选择排序的记录移动次数很少。

三、应用题（20分，每题4分）1. 分别写出图中二叉树的先序、中序和后序遍历序列。

先序序列：中序序列：后序序列：2..已知权值{16，6，3，5，11，9}，试画出它对应的哈夫曼树（要求每个结点的左子结点的值小于右子结点的值）○27/ \○11○16/ \ / \○5○6○7○9/ \○2○33.请写出下面图的最小生成树（普里姆算法或克鲁斯卡尔算法均可）4.有序列{38，19，64，13,96,49,41},采用冒泡排序方法由小到大进行排序，请写出每趟的结果。

略。

5. 请写出无向图的邻接矩阵略。

四、写程序题（10分）1. 在顺序表中第i个位置插入一个新元素studentID (3分)public class SqList {finalintmaxlen = 1000;int data[] = new int[maxlen];intlen = 0;public void insertElementAt(intstudentID,inti){if(len == maxlen ){System.out.println("溢出");return;}else{for(int j = len ; j>=i-1; j--)date[j+1] = data[j];date[j]= studentID;len++;return;}}}2. 删除单链表中的第i个结点(3分)//单链表节点定义classLnode{publicint data;publicLnode next;}//单链表的定义public class LinkedList {Lnode h = null; //头指针public void remove(inti){int j = 0;Lnode p = h.next;Lnode q;while(p.next != null){j++;if(j == i-1){q=p;p=p.next;q = null;return;}elsep = p.next;}}}3. 请写出冒泡排序的代码（4分）static void mppx(int r[],int n){intflag,temp;for(inti=1;i<n;i++){flag = 0;for(int j=0;j<n-i;j++){if(r[j+1]<r[j]){//请补全代码flag++;int count =r[j];r[j]=r[j+1];r[j+1]=count;}}if(flag == 0)return;}}习题二1、在一个单链表中，删除p所指结点的直接后继的操作是。

A. p.next=p.next.nextB.p=p.next;p.next=p.next.nextC. p.next=p.nextD.p= p.next.next2、在数据结构中，数据的最小单位是_________。

A. 数据项B. 数据类型C. 数据元素D. 数据变量3、若让元素a，b，c，d依次进栈，则出栈次序不可能出现种情况。

A．a，b，c，d B．d，c，b，a C．a，d，b，c D．a，d，c，b4、树形结构最适合用来描述。

A. 有序的数据元素B. 无序的数据元素C. 数据元素之间具有层次关系的数据D.数据元素之间没有关系的数据5、若二叉树中度为2的结点有15个，度为1的结点有10个，则有个树叶结点。

A．25 B. 15 C. 16 D. 416、线性表若采用链式存储结构时，要求内存中可用存储单元的地址_______。

A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续不连续都可以7、若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用的存储方式是。