西安交通大学23春《数据结构》在线作业

西交《数据结构》在线作业00001
试卷总分100得分100
西安交通大学2023年春季学期作业
一、单选题(共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.2n1
答案
12.设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是。
A.ni
B.n1i
C.n+li
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.2n1
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，其元素个数为rearfront。（）
答案正确
50.线性表的顺序存储结构比链式存储结构更好。
答案错误

本内容由易百教育整理并发布