数据结构课程三套作业及答案分析.doc

数据构造课程作业_A
一、单项选择题。
1.(7分)对完全二叉树表达正确的选项是〔 C 〕。
 A. 完全二叉树就是满二叉树
 B. 完全二叉树与满二叉树编号不对应
 C. 完全二叉树同一层上左子树未满不会有右子树
 D. 以上都不正确
知识点： 第六章
解析第六章第二节二叉树的性质
2.(7分)堆的形状是一棵〔 C 〕。
 A. 二叉排序树
 B. 满二叉树
 C. 完全二叉树
 D. 一般的二叉树
知识点： 第十章
解析第十章第四节堆排序
3.(7分)设一棵完全二叉树中有65个结点，那么该完全二叉树的深度为〔 B 〕。
 A. 8
 B. 7
 C. 6
 D. 5
知识点： 第六章
解析第六章第六节二叉树的性质
4.(7分)以下数据构造中哪一个是非线性构造？〔 D 〕
 A. 队列
 B. 栈
 C. 线性表
 D. 二叉树
知识点： 第一章
解析第一章第二节综合题目
5.(7分)线性表的顺序存储构造是一种?的存储构造〔 A 〕。
 A. 随机存取
 B. 顺序存取
 C. 索引存取
 D. 散列存取
知识点： 第二章
解析第二章第二节综合题目
6.(7分)带头节点的单链表L为空的判定条件是〔 C 〕。
 A. L = =null
 B. L->data= =null
 C L->next= =null
 D. L->next= =data
知识点： 第二章
解析第二章第三节线性链表
7.(7分)设一组初始记录关键字序列为(45，80，55，40，42，85)，那么以第一个记录关键字45为基准而得到一趟快速排序的结果是〔 C 〕。
 A. 40，42，45，55，80，83
 B. 42，40，45，80，85，88
 C. 42，40，45，55，80，85
 D. 42，40，45，85，55，80
知识点： 第十章
解析第十章第三节综合题目
8.(7分)设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，那么以20为基准记录的一趟快速排序完毕后的结果为〔 A 〕。
 A. 10，15，14，18，20，36，40，21
 B. 10，15，14，18，20，40，36，21
 C. 10，15，14，20，18，40，36，2l
 D. 15，10，14，18，20，36，40，21
知识点： 第十章
解析第十章第三节综合题目
9.(7分)设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进展一趟快速排序的结果为〔 C 〕。
 A. 2，3，5，8，6
 B. 3，2，5，8，6
 C. 3，2，5，6，8
 D. 2，3，6，5，8

知识点： 第十章
解析第十章第三节综合题目
10.(7分)设指针变量p指向单链表结点A，那么删除结点A的后继结点B需要的操作为〔 A 〕。
 A. p->next=p->next->next
 B. p=p->next
 C. p=p->next->next
 D. p->next=p
知识点： 第二章
解析第二章第三节线性链表
二、判断。
1.(6分)栈与队列都是操作受限的线性表。
答案：正确。
解析第三章综合题目
2.(6分)分块查找的平均查找长度不仅及索引表的长度有关，而且及块的长度有关。
答案：正确。
解析第九章第一节索引顺序表的查找
3.(6分)数据项是数据的根本单位。
答案：错误。
解析第一章第二节数据项
4.(6分)希尔排序是一种稳定的排序方法。
答案：错误。
解析第十章第二节希尔排序
5.(6分)二叉排序树上左子树上所有结点的值均小于它的根结点的值。
答案：正确。
解析第九章第二节二叉排序树与平衡二叉树
数据构造课程作业_B
一、单项选择题。
1.(7分)设某强连通图中有n个顶点，那么该强连通图中至少有〔 C 〕条边。
 A. n(n-1)
 B. n+1
 C. n
 D. n(n+1)
知识点： 第七章
解析第七章第一节综合题目
2.(7分)链式队列Q为空的判定条件〔 A 〕。
 A. 
 B. Q.front==Q
 C. 
 D. 没有正确答案
知识点： 第三章
解析第三章第四节队列的链式表示与实现
3.(7分)设某无向图中有n个顶点e条边，那么建立该图邻接表的时间复杂度为〔 A 〕。
 A. O(n+e)
 B. O(n2)
 C. O(ne)
 D. O(n3)
知识点： 第七章
解析第七章第二节邻接表
4.(7分)图的广度优先遍历算法类似于二叉树的〔 D 〕。
 A. 先序遍历
 B. 中序遍历
 C. 后序遍历
 D. 层次遍历
知识点： 第七章
解析第七章第三节广度优先搜索
5.(7分)图的邻接矩阵表示法适用于表示〔 C 〕。
 A. 有向图
 B. 无向图
 C. 稠密图
 D. 稀疏图
知识点： 第七章
解析第七章第二节数组表示法
6.(7分)设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，那么输出序列中第i个输出元素是〔 C 〕。
 A. n-I
 B. n-1-I
 C. n+1-I
 D. 不能确定
知识点： 第三章
解析第三章第一节栈的表示与实现
7.(7分)顺序查找适用于存储构造为〔 B 〕的线性表。
 A. 散列
 B. 顺序或者链式
 C. 压缩
 D. 索引
知识点： 第九章
解析第九章第一节顺序表的查找
8.(7分)线性表假设采用链式存储构造时，要求内存中的可用存储单元的地址? 〔 D 〕。
 A. 必须连续
 B. 局部连续
 C. 一定不连续
 D. 可连续可不连续
知识点： 第二章
解析第二章第三节综合题目
9.(7分)设无向图G中有n个顶点，那么该无向图的最小生成树上有〔 B 〕条边。
 A. n
 B. n-1
 C. 2n
 D. 2n-1
知识点： 第七章
解析第七章第四节最小生成树
10.(7分)设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，那么执行出队操作后其头指针front值为〔 D 〕。
 A. front=front+1
 B. front=(front+1)%(m-1)
 C. front=(front-1)%m
 D. front=(front+1)%m
知识点： 第三章
解析第三章第四节队列的顺序表示与实现
二、判断。
1.(6分)二叉排序树上左子树上所有结点的值均小于它的根结点的值。
答案：正确。
解析第九章第二节二叉排序树与平衡二叉树
2.(6分)常用的图的遍历方法有深度优先遍历与广度优先遍历。
答案：正确。
解析第七章第三节综合题目
3.(6分)数据项是数据的根本单位。
答案：错误。
解析第一章第二节数据项
4.(6分)二维数组与多维数组均不是特殊的线性构造。
答案：错误。
解析第五章综合题目
5.(6分)分块查找的平均查找长度不仅及索引表的长度有关，而且及块的长度有关。
答案：正确。
解析第九章第一节索引顺序表的查找
数据构造课程作业_C
一、单项选择题。
1.(7分)设按照从上到下、从左到右的顺序从1开场对完全二叉树进展顺序编号，那么编号为i结点的左孩子结点的编号为〔 B 〕。
 A. 2i+1
 B. 2i
 C. i/2
 D. 2i-1
知识点： 第六章
解析第六章第六节二叉树的性质
2.(7分)假设采用孩子兄弟链表作为树的存储构造，那么树的先根遍历应采用二叉树的〔 B 〕。
 A. 层次遍历
 B. 先序遍历
 C. 中序遍历
 D. 后序遍历
知识点： 第六章
解析第六章第四节树的存储构造
3.(7分)假设有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进展二分查找，那么查找A［3］的比拟序列的下标依次为〔 D 〕。
 A. 1，2，3
 B. 9，5，2，3
 C. 9，5，3
 D. 9，4，2，3
知识点： 第九章
解析第九章第一节有序表的查找
4.(7分)设有序表中有1000个元素，那么用二分查找查找元素X最多需要比拟〔 B 〕次。
 A. 25
 B. 10
 C. 7
 D. 1
知识点： 第九章
解析第九章第一节有序表的查找
5.(7分)单链表的结点包含____与_____。〔 D 〕
 A. 结点域，符号域
 B. 数据域，符号域
 C. 结点域，指针域
 D. 数据域，指针域
知识点： 第二章
解析第二章第三节线性链表
6.(7分)设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，那么后序遍历该二叉树得到序列为〔 A 〕。
 A. BADC
 B. BCDA
 C. CDAB
 D. CBDA
知识点： 第六章
解析第六章第三节遍历二叉树
7.(7分)序列278、109、930经过一趟基数排序后结果为〔 A 〕。
 A. 930、278、109
 B. 109、930、278
 C. 109、278、930
 D. 278、109、930
知识点： 第十章
解析第十章第六节多关键字的排序
8.(7分)设某有向图中有n个顶点，那么该有向图对应的邻接表中有〔 B 〕个表头结点。
 A. n-1
 B. n
 C. n+1
 D. 2n-1
知识点： 第七章
解析第七章第二节邻接表
9.(7分)设一维数组中有n个数组元素，那么读取第i个数组元素的平均时间复杂度为〔 C 〕。
 A. O(n)
 B. O(nlog2n)
 C. O(1)
 D O(n2)
知识点： 第五章
解析第五章第二节综合题目
10.(7分)一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是〔 B 〕。
 A. A
 B. E
 C. B
 D. D
知识点： 第三章
解析第三章第一节综合题目
二、判断。
1.(6分)一棵二叉树的先序序列与后序序列，那么能够唯一确定出该二叉树的形状。
答案：错误。
解析第六章第三节遍历二叉树
2.(6分)归并排序是一种稳定的排序方法。
答案：正确。
解析第十章第五节综合题目
3.(6分)邻接表法只能用于有向图存储。
答案：错误。
解析第七章第二节邻接表
4.(6分)设初始记录关键字根本有序，那么快速排序算法的时间复杂度为O(nlog2n)。
答案：错误。
解析第十章第三节综合题目
5.(6分)非空的双向循环链表中任何结点的前驱指针均不为空。
答案：正确。
解析第二章第三节循环链表
第 14 页