数据结构复习题

//八大排序：

（插入排序）：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.rear B. QU.front!=QU.rear C. QU.front==(QU.rear+1) % m0 D. QU.front!=(QU.rear+1) % m0 10．以下说法错误的是。

A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种\分支层次\结构

11. 如下图所示的 4 棵二叉树中，不是完全二叉树。 12. 深度为 5 的二叉树至多有个结点。//设深度为k (2^k)-1 A. 16 B. 32 C.31 D.10

13．在一棵二叉树中，度数为2的结点数等于n2，度数为1的结点数等于n1，那么度数为0的结点数等于是_______。

A.n1+1 B. n2+1 C. n1+2 D.n2+2

14. 对含有个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A.0 B.1 C.2 D.不存在这样的二叉树 15. 在一个图中，所有顶点的度数之和等于所有边数的倍。

A. 1/2 B. 1 C. 2 D. 4 无向图：顶点度数之和为边数的两倍

有向图：在一条边AB（A→B）都会给A提供一个出度，给B提供一个入度则

顶点度数之和=2*顶点入度之和=2*顶点出度之和=顶点入度之和+顶点出度之和=2*边数 16. 具有 6 个顶点的无向图至少应有条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 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. n B. (n-1)2 C. n-1 D. n2

18. 对线性表进行折半(二分)查找时，要求线性表的存储方式是。 A. 顺序存储 B. 链接存储

C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储

//二分查找要使用下标，数据按递增或递减排好

19. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序（扫描最小） //插入排序：希尔排序、冒泡排序

20. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为。

A. 38，40，46，56，79，84 B. 40，38，46，79，56，84 C. 40，38，46，56，79，84 D. 40，38，46，84，56，79

21. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序

22. 快速排序的平均时间复杂度是：。

A.O(n2) B. O(n) C. O(n*log2n) D. O( log2n)

23. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左孩子结点的编号。 A.2i-1 B.2i C.2i+1 D.2i+2

24. 在一个具有n个顶点的有向完全图中，所含的弧数为。 A．nB.n*(n-1)

C.n*(n+1) D.n*(n-1)/2

25.顺序查找法适合于存储结构为的线性表。

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○3 ○

3.请写出下面图的最小生成树（普里姆算法或克鲁斯卡尔算法均可）

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; //头指针