北京语言20秋《数据结构》作业4（100分）

skystar

[北京语言大学]20秋《数据结构》作业4
试卷总分:100    得分:100
第1题,下列四种排序中___的空间复杂度最大。
A、插入排序
B、冒泡排序
C、堆排序
D、归并排序
正确答案:


第2题,
A、A
B、B
C、C
D、D
正确答案:


第3题,顺序查找法适合于存储结构为___的线性表。
A、散列存储
B、顺序存储或链式存储
C、压缩存储
D、索引存储
正确答案:


第4题,由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为___。
A、24
B、71
C、48
D、53
正确答案:


A、A
B、B
C、C
D、D
正确答案:


第6题,设一组初始记录关键字序列为（345,253,674,924,627），则用基数排序需要进行___趟的分配和回收才能使得初始关键字序列变成有序序列。
A、3
B、4
C、5
D、8
正确答案:


第7题,如果最常用的操作是取第i个结点及其前驱，则采用___存储方式最节省时间。
A、单链表
B、双链表
C、单循环链表
D、顺序表
正确答案:


第8题,设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有___个空指针域。
A、2m-1
B、2m
C、2m+1
D、4m
正确答案:


第9题,
A、A
B、B
C、C
D、D
正确答案:


若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用___存储方式最节省运算时间。
A、单链表
B、给出表头指针的单循环链表
C、双链表
D、带头结点的双循环链表
正确答案:


第11题,设某棵二叉树中有2000个结点，则该二叉树的最小高度为___。
A、9
B、10
C、11
D、12
正确答案:


若有18个元素的有序表存放在一堆数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为___。
A、1,2,3
B、9,5,2,3
C、9,5,3
D、9,4,2,3
正确答案:


第13题,若已知一个栈序列是1,2,3,...,n，其输出序列为p1,p2,p3,...,pn，若p1=n，则pi为___。
A、i
B、n-i
C、n-i+1
D、不确定
正确答案:


第14题,下述哪一条是顺序存储结构的优点___。
A、插入运算方便
B、可方便地用于各种逻辑结构的存储表示
C、存储密度大
D、删除运算方便
正确答案:


线性表的链式存储结构是一种___。
A、随机存取的存储结构
B、顺序存取的存储结构
C、索引存取的存储结构
D、Hash存取的存储结构
正确答案:


第16题,
A、A
B、B
C、C
D、D
正确答案:


第17题,
A、a
B、b
C、c
D、d
正确答案:


第18题,在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为___。
A、n
B、n/2
C、(n+1)/2
D、(n-1)/2
正确答案:


第19题,线性表是具有n个___的有限序列。
A、字符
B、数据元素
C、数据项
D、表元素
正确答案:


A、A
B、B
C、C
D、D
正确答案: