北理工17春《实用数据结构与算法》在线作业答案
北理工《实用数据结构与算法》在线作业一、单选题：
1.顺序表是线性表的( ) (满分:2)
A. 链式存储结构
B. 顺序存储结构
C. 索引存储结构
D. 散列存储结构
2.下列排序方法中效率最高的排序方法是( )。 (满分:2)
A. 起泡排序
B. 堆排序
C. 快速排序
D. 直接插入排序
3.以下说法错误的是( ) (满分:2)
A. 每个存储结点只能存放一个数据元素
B. 数据元素之间的关联方式可由存储结点之间的关联方式直接表达
C. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
D. 语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示
4.下述几种排序方法中，平均查找长度最小的是( )。 (满分:2)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
5.n 个顶点的连通图至少有( )条边。 (满分:2)
A. n-1
B. n
C. n+1
D. 0
6.在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( ). (满分:2)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
7.长度为256的表,采用分块查找,每块最佳长度为( )。 (满分:2)
A. 14
B. 16
C. 18
D. 26
8.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。 (满分:2)
A. 插入
B. 选择
C. 交换
D. 二路归并
9.一个具有767个结点的完全二叉树，其叶子结点个数为( )。 (满分:2)
A. 383
B. 384
C. 385
D. 386
10.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，( )次比较后查找成功。 (满分:2)
A. 1
B. 2
C. 4
D. 8
11.对于经常要存取线性表任意指定位置元素的应用，线性表应采用( )存储结构。 (满分:2)
A. 顺序存储结构
B. 链式存储结构
C. 线性链表
D. 栈
12.快速排序方法在( )情况下最不利于发挥其长处。 (满分:2)
A. 被排序的数据量太大
B. 被排序数据中含有多个相同值
C. 被排序数据已基本有序
D. 被排序数据数目为奇数
13.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为( )。 (满分:2)
A. 15
B. 16
C. 17
D. 31
14.任何一个无向连通图的最小生成树( )。 (满分:2)
A. 只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
15.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用( )法。 (满分:2)
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 基数排序
16.以下说法错误的是( ) (满分:2)
A. 树形结构的特点是一个结点可以有多个直接前趋
B. 线性结构中的一个结点至多只有一个直接后继
C. 树形结构可以表达(组织)更复杂的数据
D. 树(及一切树形结构)是一种"分支层次"结构
17.下列说法哪个是不正确的( )。 (满分:2)
A. 快速排序属于不稳定排序。
B. 希尔排序属于不稳定排序。
C. 直接插入排序属于不稳定排序。
D. 堆排序属于不稳定排序。
18.含4个结点（元素值均不相同）的二叉搜索树有( )种。 (满分:2)
A. 12
B. 14
C. 5
D. 15
19.以下说法错误的是( ) (满分:2)
A. 求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B. 顺序存储的线性表可以随机存取
C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D. 线性表的链式存储结构优于顺序存储结构
20.若构造一棵具有n个结点的二叉排序树，最坏情况下，其深度不会超过( )。 (满分:2)
A. n/2
B. n
C.(n+1)/2
D. n+1
二、多选题：
1.图的存储结构有( ) (满分:2)
A. 邻接矩阵
B. 邻接表
C. 数组表示法
D. 十字链表
2.以下不稳定的排序方法是( ) (满分:2)
A. 快速排序
B. 冒泡排序
C. 希尔排序
D. 堆排序
3.对于顺序表的优缺点，以下说法正确的是( ) (满分:2)
A. 无需为表示结点间的逻辑关系而增加额外的存储空间
B. 可以方便地随机存取表中的任一结点
C. 插入和删除运算较方便
D. 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
4.某堆栈的输入序列为a, b，c，d,下面的四个序列中，可能是它的输出序列的是( ) (满分:2)
A. a，c，b，d
B. b, c，d，a
C. c, d，b, a
D. d, c，a，b
5.对于单链表表示法，以下说法正确的是( ) (满分:2)
A. 指向链表的第一个结点的指针，称为头指针
B. 单链表的每一个结点都被一个指针所指
C. 任何结点只能通过指向它的指针才能引用
D. 尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
6.以下说法正确的是( ) (满分:2)
A. 二叉树可以是空集
B. 二叉树的任一结点至多有两棵子树
C. 二叉树与树具有相同的树形结构
D. 二叉树的子树有次序之分
7.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法正确的是( ) (满分:2)
A. 任何指针都不能用打印语句输出一个指针型变量的值
B. 如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
C. 若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
D. 对于一个指针型变量P的值。只需知道它指的是哪个结点
8.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是( ) (满分:2)
A. G中有弧<Vi，Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有<Vi,Vj>
D. G中有一条从Vj到Vi的路径
9.以下说法正确的是( ) (满分:2)
A. 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）
B. 读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构
C. 在链表上实现读表元运算的平均时间复杂性为O（1）
D. 插入、删除操作在链表上的实现可在O（1）时间内完成
10.下面几个符号串编码集合中，是前缀编码的是( ) (满分:2)
A. {0,10,110,1111}
B. {11,10,001,101,0001}
C. {00,010,0110,1000}
D. {b,c,aa,ac,aba,abb,abc}
三、判断题：
1.若有向图有n个顶点，则其强连通分量最多有n个。 (满分:2)
A. 错误
B. 正确
2.广义表中原子个数即为广义表的长度。 (满分:2)
A. 错误
B. 正确
3.对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。 (满分:2)
A. 错误
B. 正确
4.一个循环链表可以由所给定的头指针或者尾指针惟一地确定。 (满分:2)
A. 错误
B. 正确
5.深度为6的二叉树最多有64个结点。 (满分:2)
A. 错误
B. 正确
6.顺序存储方式只能用于存储线性结构。 (满分:2)
A. 错误
B. 正确
7.用带表头结点的单链表表示队列，则判断队列为空的标准是头指针和尾指针均指向同一个结点。 (满分:2)
A. 错误
B. 正确
8.算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。 (满分:2)
A. 错误
B. 正确
9.散列法存储的基本思想是由关键码的值决定数据的存储地址。 (满分:2)
A. 错误
B. 正确
10.快速排序是排序算法中平均性能最好的一种排序。 (满分:2)
A. 错误
B. 正确
11.层次遍历初始堆可以得到一个有序的序列。 (满分:2)
A. 错误
B. 正确
12.空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现 。 (满分:2)
A. 错误
B. 正确
13.线性表的逻辑顺序与物理顺序总是一致的。 (满分:2)
A. 错误
B. 正确
14.哈夫曼树又称为最优二叉树。 (满分:2)
A. 错误
B. 正确
15.队列和栈都是运算受限的线性表。 (满分:2)
A. 错误
B. 正确
16.设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。 (满分:2)
A. 错误
B. 正确
17.一个栈的输入序列是12345，则栈的输出序列可以是54312。 (满分:2)
A. 错误
B. 正确
18.空栈就是所有元素都为0的栈。 (满分:2)
A. 错误
B. 正确
19.哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 (满分:2)
A. 错误
B. 正确
20.完全二叉树的某结点若没有左孩子，则它必是叶子结点。 (满分:2)
A. 错误
B. 正确
无忧网不错，哈哈
页:
[1]