西交《数据结构》在线作业-00001
试卷总分:100 得分:100
一、单选题 (共 30 道试题,共 60 分)
1.由权值分别为11,8,6,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()
A.24
B.71
C.48
D.53
答案:
2.由两个栈共享一个向量空间的好处是:()
A.减少存取时间,降低下溢发生的机率
B.节省存储空间,降低上溢发生的机率
C.减少存取时间,降低上溢发生的机率
D.节省存储空间,降低下溢发生的机率
答案:
3.数据的基本单位( )。
A.数据结构
B.数据元素
C.数据项
D.文件
答案:
4.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字45为基准而得到的一趟快速排序结果是( )。
A.40,42,60,55,80,85
B.42,45,55,60,85,80
C.42,40,55,60,80,85
D.42,40,60,85,55,80
答案:
5.下列各种排序算法中平均时间复杂度为O(n)是()。
A.快速排序
B.堆排序
C.归并排序
D.冒泡排序
答案:
6.对于一些特殊矩阵,采用压缩存储的目的是( )。
A.使表达变得更简单
B.对矩阵元素的存取变得简单
C.去掉矩阵中的多于元素
D.减少不必要的存储空间
答案:
7.循环队列占用的空间( )。
A.必须连续
B.不必连续
C.不能连续
D.可以不连续
答案:
8.链式栈与顺序栈相比,一个比较明显的优点是()
A.插入操作更加方便
B.通常不会出现栈满的情况
C.不会出现栈空的情况
D.删除操作更加方便
答案:
9.在二叉排序树中插入一个结点的时间复杂度为()。
A.O(1)
B.O(n)
C.O(log2n)
D.O(n)
答案:
10.设某哈夫曼树中有199个结点,则该哈夫曼树中有()个叶子结点。
A.99
B.100
C.101
D.102
答案:
11.设给定权值总数有n 个,其哈夫曼树的结点总数为( )
A.不确定
B.2n
C.2n+1
D.2n-1
答案:
12.设输入序列1、2、3、?、n经过栈作用后,输出序列中的第一个元素是n,则输出序列中的第i个输出元素是()。
A.n-i
B.n-1-i
C.n+l-i
D.不能确定
答案:
13.设二叉排序树上有n个结点,则在二叉排序树上查找结点的平均时间复杂度为()。
A.O(n)
B.O(n^2)
C.O(nlog2n)
D.O(log2n)
答案:
14.如果要求频繁的对线性表进行插入和删除操作,则线性表应该采用( )存储结构。
A.散列
B.顺序
C.链式
D.任意
答案:
15.下列说法中,正确的是( )。
A.度为2的树是二叉树
B.度为2的有序树是二叉树
C.子树有严格的左、右之分的树是二叉树
D.子树有严格的左、右之分,且度不超过2的树是二叉树
答案:
16.两个字符串相等的条件是( )。
A.两串的长度相等;
B.两串包含的字符相同;
C.两串的长度相等,并且两串包含的字符相同;
D.两串的长度相等,并且对应位置上的字符相同。
答案:
17.设有100个数据元素,采用折半搜索时,最大比较次数为()
A.6
B.7
C.8
D.10
答案:
18.设有5000个待排序的记录关键字,如果需要用最快的方法选出其中最小的10个记录关键字,则用下列()方法可以达到此目的。
A.快速排序
B.堆排序
C.归并排序
D.插入排序
答案:
19.建立一个长度为n的有序单链表的时间复杂度为()
A.O(n)
B.O(1)
C.O(n)
D.O(log2n)
答案:
20.下面关于线性表的叙述错误的是()。
A.线性表采用顺序存储必须占用一片连续的存储空间
B.线性表采用链式存储不必占用一片连续的存储空间
C.线性表采用链式存储便于插入和删除操作的实现
D.线性表采用顺序存储便于插入和删除操作的实现
答案:
21.线性表采用链式存储时,结点的存储地址()
A.必须是不连续的
B.连续与否均可
C.必须是连续的
D.和头结点的存储地址相连续
答案:
22.下列存储形式中,()不是树的存储形式
A.双亲表示法
B.左子女右兄弟表示法
C.广义表表示法
D.顺序表示法
答案:
23.有n个顶点的无向图的邻接矩阵是用( )数组存储。
A.一维
B.n行n列
C.任意行n列
D.n行任意列
答案:
24.若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置,利用( )遍历方法最合适。
A.前序
B.中序
C.后序
D.按层次
答案:
25.设输入序列为1、2、3、4、5、6,则通过栈的作用后可以得到的输出序列为()。
A.5,3,4,6,1,2
B.3,2,5,6,4,1
C.3,1,2,5,4,6
D.1,5,4,6,2,3
答案:
26.在一棵具有5层的满二叉树中结点数为()
A.31
B.32
C.33
D.16
答案:
27.若进队的序列为A、B、C、D,则出队的序列是( )。
A.C、D、A
B.C、B、D
C.B、C、D
D.B、D、A
答案:
28.线性链表各结点之间的地址( )
A.必须连续
B.一定不连续
C.部分地址必须连续
D.连续与否无所谓
答案:
29.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n,则这棵二叉中共有()个结点。
A.2n
B.n+l
C.2n-1
D.2n+l
答案:
30.设一组初始记录关键字序列为(13,18,24,35,47,50,62,83,90,115,134),则利用二分法查找关键字90需要比较的关键字个数为()。
A.1
B.2
C.3
D.4
答案:
二、判断题 (共 20 道试题,共 40 分)
31.满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树。
答案:
32.一般树和二叉树的结点数目都可以为0。 ( )
答案:
33.在使用后缀表表示实现计算器时用到一个栈的实例,其作用是暂存运算对象。
答案:
34.堆是完全二叉树,完全二叉树不一定是堆。
答案:
35.线性表中的所有元素都有一个前驱元素和后继元素。( )
答案:
36.算法与程序没有区别。 ( )
答案:
37.在B+树中查找和在B-树中查找的过程完全相同。 ( )
答案:
38.从本质上看,文件是一种非线性结构。
答案:
39.在线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。( )
答案:
40.如果某种排序算法不稳定,则该排序方法就没有实用价值。( )
答案:
41.栈和队列都是限制存取点的线性结构。
答案:
42.设某堆中有n个结点,则在该堆中插入一个新结点的时间复杂度为O(log2n)。( )
答案:
43.有向图的邻接表和逆邻接表中表结点的个数不一定相等。
答案:
44.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。
答案:
45.如果两个关键字的值不等但哈希函数值相等,则称这两个关键字为同义词。
答案:
46.数据元素是数据的最小单位。( )
答案:
47.除了插入和删除操作之外,数组的操作还包括存取、修改、检索和排序。( )
答案:
48.当向二叉排序树中插入一个结点,则该结点一定成为叶子结点。( )
答案:
49.在循环队列中,若尾指针rear大于头指针front,其元素个数为rear-front。( )
答案:
50.线性表的顺序存储结构比链式存储结构更好。
答案:
奥鹏,国开,广开,电大在线,各省平台,新疆一体化等平台学习
详情请咨询QQ : 3230981406或微信:aopopenfd777