2016秋数据结构与算法作业答案
2016秋数据结构与算法作业答案一、单选题：
1.图的存储结构不包括( ) (满分:2.5)
A. 数组表示
B. 邻接表
C. 邻接多重表
D. 孩子兄弟表示
2.当两个元素比较出现反序时就相互交换位置的排序方法称为( )。 (满分:2.5)
A. 归并排序
B. 选择排序
C. 交换排序
D. 插入排序
3.快速排序属于那种排序类型( )。 (满分:2.5)
A. 选择排序
B. 插入排序
C. 交换排序
D. 基数排序
4.中序遍历一棵二叉排序树所得到的结点序列是键值的( )序列。 (满分:2.5)
A. 递增或递减
B. 递减
C. 递增
D. 无序
5.关键路径是指AOE(Activity On Edge)网中( )。 (满分:2.5)
A. 最长的回路
B. 最短的回路
C. 从源点到汇点(结束顶点)的最长路径
D. 从源点到汇点(结束顶点)的最短路径
6.设有一个二维数A，以行序为主序存储。假设A存放位置在644(10)，A存放位置在676(10)，每个元素占一个空间，则A在( )位置，(10)表明用10进数表示。 (满分:2.5)
A. 692(10)
B. 626(10)
C. 709(10)
D. 724(10)
7.当待排序列基本有序时，下列排序方法中( )最好。 (满分:2.5)
A. 直接插入排序
B. 快速排序
C. 堆排序
D. 归并排序
8.在线性表顺序存储结构下，在第i个元素之前插入新元素一般需要( ) (满分:2.5)
A. 移动元素
B. 修改头指针
C. 队头指针
D. 申请新的结点空间
9.A算法的时间复杂度为O（n^3），B算法的时间复杂度为O（2n），则说明( )。 (满分:2)
A. 对于任何数据量，A算法的时间开销都比B算法小
B. 随着问题规模n的增大，A算法比B算法有效
C. 随着问题规模n的增大，B算法比A算法有效
D. 对于任何数据量，B算法的时间开销都比A算法小
10.在数据结构中，与所使用的计算机无关的是数据的( )结构 (满分:2.5)
A. 逻辑
B. 存储
C. 逻辑和存储
D. 物理
11.下列排序方法中，排序趟数与序列的原始状态有关的方法是( )。 (满分:2.5)
A. 选择排序
B. 希尔排序
C. 堆排序
D. 冒泡排序
12.下列关于AOE网的叙述中，不正确的是( )。 (满分:2.5)
A. 关键活动不按期完成就会影响整个工程的完成时间
B. 任何一个关键活动提前完成，那么整个工程将会提前完成
C. 所有的关键活动提前完成，那么整个工程将会提前完成
D. 某些关键活动提前完成，那么整个工程将会提前完成
13.设有一个长度为80的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较( )次。 (满分:2.5)
A. 9
B. 8
C. 7
D. 6
14.判定一个队列Q(最多元素为m0)为满队列的条件是( ) (满分:2.5)
A. rear-front= = m0
B. rear-front-1= =m0
C. front= =rear
D. front= =rear+1
15.对线性表进行二分查找时，要求线性表必须( )。 (满分:2.5)
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排列
D. 以链接方式存储，且结点按关键字有序排列
16.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( ). (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
17.对于经常要存取线性表任意指定位置元素的应用，线性表应采用( )存储结构。 (满分:2.5)
A. 顺序存储结构
B. 链式存储结构
C. 线性链表
D. 栈
18.3个结点的无向完全连通图至少有( )条边。 (满分:2.5)
A. 3
B. 4
C. 5
D. 6
19.数据结构主要研究( )。 (满分:2.5)
A. 数据的逻辑结构
B. 数据的存储结构
C. 数据的逻辑结构和存储结构
D. 数据的逻辑结构、存储结构以及数据在操作上的实现
20.下列说法正确的是( ) (满分:2.5)
A. 堆栈是在两端操作、先进后出的线性表
B. 堆栈是在一端操作、先进后出的线性表
C. 队列是在一端操作、先进先出的线性表
D. 队列是在两端操作、后进先出的线性表
21.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个( )。 (满分:2.5)
A. 上三角矩阵
B. 稀疏矩阵
C. 对角矩阵
D. 对称矩阵
22.具有线性结构的数据结构是( ) (满分:2.5)
A. 赫夫曼树
B. 栈
C. 图
D. 树
23.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为( )。 (满分:2.5)
A. n
B. n/2
C. （n-1）/2
D. （n+1）/2
24.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用( )法。 (满分:2.5)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 基数排序
25.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为( )。 (满分:2.5)
A. 15
B. 16
C. 17
D. 31
26.在表达式求值算法中，需要用( )个栈？ (满分:2.5)
A. 0
B. 1
C. 2
D. 3
27.向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行( )。 (满分:2.5)
A. HS->next=s
B. S->next=HS->next;HS->next=s
C. S->next=HS;HS=s
D. S->next=HS;HS=HS->next
28.根据二叉树的定义可知二叉树共有( )种不同的形态。 (满分:2.5)
A. 4
B. 5
C. 6
D. 7
29.在一棵具有5层的满二叉树中结点总数为( )。 (满分:2.5)
A. 31
B. 32
C. 33
D. 16
30.栈的插入和删除操作在( )进行。 (满分:2.5)
A. 栈顶
B. 栈底
C. 任意位置
D. 指定位置
31.下列排序方法中效率最高的排序方法是( )。 (满分:2.5)
A. 起泡排序
B. 堆排序
C. 快速排序
D. 直接插入排序
32.某二叉树的前序遍历序列为abdgcefh，中序遍历序列为dgbaechf，则其后序遍历序列为( )。 (满分:2.5)
A. bdgecefha
B. gdbecfha
C. bdgaechf
D. gdbehfca
33.若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?( ) (满分:2.5)
A. 单链表
B. 给出表头指针的单循环链表
C. 双向链表
D. 给出表尾指针的双向循环链表
34.以下不稳定的排序方法是( ) (满分:2.5)
A. 直接插入排序
B. 冒泡排序
C. 直接选择排序
D. 二路归并排序
35.n 个顶点的连通图至少有( )条边。 (满分:2.5)
A. n-1
B. n
C. n+1
D. 0
36.以下说法错误的是( ) (满分:2.5)
A. 求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B. 顺序存储的线性表可以随机存取
C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D. 线性表的链式存储结构优于顺序存储结构
37.学习数据结构主要目的是( )。 (满分:2.5)
A. 处理数值计算问题
B. 研究程序设计技巧
C. 选取合适数据结构，写出更有效的算法
D. 是计算机硬件课程的基础
38.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( )。 (满分:2.5)
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不边疆的
D. 连续不连续都可以
39.顺序查找适合于存储结构为( )的查找表。 (满分:2.5)
A. 压缩存储
B. 散列存储
C. 索引存储
D. 顺序存储或链式存储
40.下列排序中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。 (满分:2.5)
A. 直接插入排序
B. 冒泡排序
C. 快速排序
D. 堆排序
**** Hidden Message *****
页:
[1]