北京理工大学《实用数据结构与算法》在线作业四

奥鹏北京理工大学新学期作业参考

北理工《实用数据结构与算法》在线作业-00004

1.在一棵具有5层的满二叉树中结点总数为()。
选项A：31
选项B：32
选项C：33
选项D：16
正确答案问询微信：424329

2.n 个顶点的连通图至少有()条边。
选项A：n-1
选项B：n
选项C：n+1
选项D：0
正确答案问询微信：424329

3.含4个结点（元素值均不相同）的二叉搜索树有()种。
选项A：12
选项B：14
选项C：5
选项D：15
正确答案问询微信：424329

4.用线性链表存储线性表时，要求存储空间()
选项A：必须是连续的
选项B：连续不连续都可以
选项C：部分元素的存储空间必须是连续的
选项D：必须是不连续的
正确答案问询微信：424329

5.一个数组第一个元素的存储地址是100，每个数组元素的长度为2，则第5个元素的地址是()。
选项A：110
选项B：108
选项C：100
选项D：120
正确答案问询微信：424329

6.具有2000个结点的二叉树，其高度至少为()。
选项A：9
选项B：10
选项C：11
选项D：12
正确答案问询微信：424329

7.下列说法哪个是不正确的()。
选项A：快速排序属于不稳定排序。
选项B：希尔排序属于不稳定排序。
选项C：直接插入排序属于不稳定排序。
选项D：堆排序属于不稳定排序。
正确答案问询微信：424329

8.一个栈的入栈序列是abcde，则栈的不可能的输出序列是()。
选项A：edcba
选项B：decba
选项C：dceab
选项D：abcde
正确答案问询微信：424329

9.有一个有序表为｛1，3，9，12，32，41，45，62，75，77，82，95，100｝，当采用折半查找值为82的节点时，()次比较后查找成功。
选项A：1
选项B：2
选项C：4
选项D：8
正确答案问询微信：424329

10.在一个具有n个顶点的无向图中,要连通全部顶点至少需要()边。
选项A：n
选项B：n+1
选项C：n-1
选项D：n/2
正确答案问询微信：424329

11.3个结点的无向完全连通图至少有()条边。
选项A：3
选项B：4
选项C：5
选项D：6
正确答案问询微信：424329

12.长度为256的表,采用分块查找,每块最佳长度为()。
选项A：14
选项B：16
选项C：18
选项D：26
正确答案问询微信：424329

13.某二叉树的前序和后序序列正好相同，则该二叉树一定是()的二叉树。
选项A：空或只有一个结点
选项B：高度等于其结点数
选项C：任一结点无左孩子
选项D：任一结点无右孩子
正确答案问询微信：424329

14.快速排序属于那种排序类型()。
选项A：选择排序
选项B：插入排序
选项C：交换排序
选项D：基数排序
正确答案问询微信：424329

15.若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为()。
选项A：CDBGFEA
选项B：CDBFGEA
选项C：CDBAGFE
选项D：BCDAGFE
正确答案问询微信：424329

16.由于数据的逻辑结构通过不同的存储映像方法可得到不同的存储结构，常见的数据存储结构没有()。
选项A：邻接存储结构
选项B：顺序存储结构
选项C：索引存储结构
选项D：散列存储结构
正确答案问询微信：424329

17.下列关于AOE网的叙述中，不正确的是()。
选项A：关键活动不按期完成就会影响整个工程的完成时间
选项B：任何一个关键活动提前完成，那么整个工程将会提前完成
选项C：所有的关键活动提前完成，那么整个工程将会提前完成
选项D：某些关键活动提前完成，那么整个工程将会提前完成
正确答案问询微信：424329

18.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为()
选项A：front=front+1
选项B：front=(front+1)% m
选项C：rear=(rear+1)%m
选项D：front=(front+1)%(m+1)
正确答案问询微信：424329

19.一棵高度（假定树根结点为第0层）为4的完全二叉树中的结点数最少为()。
选项A：15
选项B：16
选项C：17
奥鹏北京理工大学新学期作业参考 选项D：31
正确答案问询微信：424329

20.下述几种排序方法中，平均查找长度最小的是()。
选项A：插入排序
选项B：选择排序
选项C：快速排序
选项D：归并排序
正确答案问询微信：424329

21.对于顺序表的优缺点，以下说法正确的是（）
选项A：无需为表示结点间的逻辑关系而增加额外的存储空间
选项B：可以方便地随机存取表中的任一结点
选项C：插入和删除运算较方便
选项D：由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
正确答案问询微信：424329

22.下面关于哈希(Hash)查找的说法不正确的是（）
选项A：哈希函数构造的越复杂越好，因为这样随机性好，冲突小
选项B：除留余数法是所有哈希函数中最好的
选项C：不存在特别好与坏的哈希函数，要视情况而定
选项D：若需在哈希表中删去一个元素，不管用何种方法解决冲突都只要简单的将该元素删去即可
正确答案问询微信：424329

23.以下不稳定的排序方法是（）
选项A：快速排序
选项B：冒泡排序
选项C：希尔排序
选项D：堆排序
正确答案问询微信：424329

24.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法正确的是（）
选项A：任何指针都不能用打印语句输出一个指针型变量的值
选项B：如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可
选项C：若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值
选项D：对于一个指针型变量P的值。只需知道它指的是哪个结点
正确答案问询微信：424329

25.以下说法正确的是（）
选项A：直接插入排序的空间复杂度为O(1)
选项B：快速排序附加存储开销为O(log2n)
选项C：堆排序的空间复杂度为O(n)
选项D：二路归并排序的空间复杂度为O(n)
正确答案问询微信：424329

26.对于单链表表示法，以下说法正确的是（）
选项A：指向链表的第一个结点的指针，称为头指针
选项B：单链表的每一个结点都被一个指针所指
选项C：任何结点只能通过指向它的指针才能引用
选项D：尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
正确答案问询微信：424329

27.对线性表，可进行如下基本操作（）
选项A：随机存取
选项B：插入
选项C：删除
选项D：查找
正确答案问询微信：424329

28.下列说法正确的是（）
选项A：栈是限定在表尾进行插入或删除操作的线性表
选项B：栈是限定在表头进行插入或删除操作的线性表
选项C：对列是先进先出的线性表
选项D：栈是后进先出的线性表
正确答案问询微信：424329

29.二叉树的遍历方式有（）
选项A：先序遍历
选项B：中序遍历
选项C：后序遍历
选项D：线索遍历
正确答案问询微信：424329

30.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形可能出现的是（）
选项A：G中有弧Vi，Vj
选项B：G中有一条从Vi到Vj的路径
选项C：G中没有Vi,Vj
选项D：G中有一条从Vj到Vi的路径
正确答案问询微信：424329

31.层次遍历初始堆可以得到一个有序的序列。
选项A：错误
选项B：正确
正确答案问询微信：424329

32.完全二叉树中，若一个结点没有左孩子，则它必是树叶。
选项A：错误
选项B：正确
正确答案问询微信：424329

33.哈夫曼树又称为最优二叉树。
选项A：错误
选项B：正确
正确答案问询微信：424329

34.快速排序是排序算法中平均性能最好的一种排序。
选项A：错误
选项B：正确
正确答案问询微信：424329

35.广义表中原子个数即为广义表的长度。
选项A：错误
选项B：正确
正确答案问询微信：424329

36.散列法存储的基本思想是由关键码的值决定数据的存储地址。
选项A：错误
选项B：正确
正确答案问询微信：424329

37.任何一棵二叉树中至少有一个结点的度为2。
选项A：错误
选项B：正确
正确答案问询微信：424329

38.做进栈运算时应先判别,栈是否为空。
选项A：错误
选项B：正确
正确答案问询微信：424329

39.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。
选项A：错误
选项B：正确
正确答案问询微信：424329

40.对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。
选项A：错误
选项B：正确
正确答案问询微信：424329

41.算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。
选项A：错误
选项B：正确
正确答案问询微信：424329

42.完全二叉树的某结点若没有左孩子，则它必是叶子结点。
选项A：错误
选项B：正确
正确答案问询微信：424329

43.哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。
选项A：错误
选项B：正确
正确答案问询微信：424329

44.若有向图有n个顶点，则其强连通分量最多有n个。
选项A：错误
选项B：正确
正确答案问询微信：424329

45.队列和栈都是运算受限的线性表。
选项A：错误
选项B：正确
正确答案问询微信：424329

46.若采用三元组存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。
选项A：错误
选项B：正确
正确答案问询微信：424329

47.顺序存储方式只能用于存储线性结构。
选项A：错误
选项B：正确
正确答案问询微信：424329

48.一个栈的输入序列是12345，则栈的输出序列可以是54312。
选项A：错误
选项B：正确
正确答案问询微信：424329

49.中序遍历二叉排序树可以得到一个有序的序列。
选项A：错误
选项B：正确
正确答案问询微信：424329

50.一个循环链表可以由所给定的头指针或者尾指针惟一地确定。
选项A：错误
选项B：正确
正确答案问询微信：424329