北京语言大学计算机科学与技术专业《数据结构》作业及答案4
1、下列四种排序中()的空间复杂度最大。
A.插入排序
B.冒泡排序
C.堆排序
D.归并排序
本题答案：
D
D
2、在一个图中所有顶点的度数之和等于所有边数的()倍。
A.1/2
B.2
C.1
D.4
本题答案：
B
B
3、顺序查找法适合于存储结构为()的线性表。
A.散列存储
B.顺序存储或链式存储
C.压缩存储
D.索引存储
本题答案：
B
B
4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为()。
A.24
B.71
C.48
D.53
本题答案：
B
B
5、下列说法中，不正确的是()。
A.数据元素是数据的基本单位
B.数据项是数据中不可分割的最小可标识单位
C.数据可由若干个数据元素构成
D.数据项可由若干个数据元素构成
本题答案：
D
D
6、设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行()趟的分配和回收才能使得初始关键字序列变成有序序列。
A.3
B.4
C.5
D.8
本题答案：
A
A
7、如果最常用的操作是取第i个结点及其前驱，则采用()存储方式最节省时间。
A.单链表
B.双链表
C.单循环链表
D.顺序表
本题答案：
D
D
8、设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有()个空指针域。
A.2m-1
B.2m
C.2m+1
D.4m
本题答案：
B
B
9、线性表的链接实现有利于()运算。
A.插入
B.读表元
C.查找
D.定位
本题答案：
A
A
10、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用()存储方式最节省运算时间。
A.单链表
B.给出表头指针的单循环链表
C.双链表
D.带头结点的双循环链表
本题答案：
D
D
11、设某棵二叉树中有2000个结点，则该二叉树的最小高度为()。
A.9
B.10
C.11
D.12
本题答案：
C
C
12、若有18个元素的有序表存放在一堆数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A3的比较序列的下标依次为()。
A.1，2，3
B.9，5，2，3
C.9，5，3
D.9，4，2，3
本题答案：
D
D
13、若已知一个栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为()。
A.i
B.n-i
C.n-i+1
D.不确定
本题答案：
C
C
14、下述哪一条是顺序存储结构的优点?()
A.插入运算方便
B.可方便地用于各种逻辑结构的存储表示
C.存储密度大
D.删除运算方便
本题答案：
C
C
15、线性表的链式存储结构是一种()。
A.随机存取的存储结构
B.顺序存取的存储结构
C.索引存取的存储结构
D.Hash存取的存储结构
本题答案：
A
A
16、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度(即x与元素的平均比较次数，假定查找每个元素的概率都相等)为()。
A.n
B.n/2
C.(n+1)/2
D.(n-1)/2