兰州大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案27

《兰州大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案27》由会员分享，可在线阅读，更多相关《兰州大学22春“计算机科学与技术”《数据结构》离线作业（一）辅导答案27（7页珍藏版）》请在装配图网上搜索。

1、书山有路勤为径，学海无涯苦作舟！ 住在富人区的她兰州大学22春“计算机科学与技术”数据结构离线作业（一）辅导答案一.综合考核(共50题)1.数据结构是带有结构的数据元素的集合。()A.正确B.错误参考答案：A2.图的广度优先遍历算法类似于二叉树的()。A、先序遍历B、中序遍历C、后序遍历D、层次遍历参考答案：B3.中序遍历的递归算法平均空间复杂度为()。A.2(n)B.n(2)C.0(n)D.2n参考答案：C4.广度优先遍历类似于二叉树的()。A.先序遍历B.中序遍历C.后序遍历D.层次遍历参考答案：D5.线性表若采用顺序存储结构时，要求内存中的可用存储单元的地址必须连续。()A、正确B、错误

2、参考答案：A6.完全二叉树中的叶子结点只可能在最后两层中出现。()A.正确B.错误参考答案：A7.设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?参考答案：方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(、-、*、/等)进行最后求值。8.数据项是数据的基本单位。()A.正确B.错误参考答案：A9.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是()。A.(rear+1)%n=frontB.rear=frontC.rear+1=

3、frontD.(rear-l)%n=front参考答案：B10.归并排序是一种稳定的排序方法。()A.正确B.错误参考答案：A11.基数排序需要进行关键字的比较。()A.正确B.错误参考答案：B12.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()A.正确B.错误参考答案：A13.若用单链表示列队，那么应选用()。A、带尾指针的循环链表B、带尾指针的非循环列队C、带头指针的非循环链表D、带头指针的循环链表参考答案：A14.稀疏矩阵(名词解释)参考答案：对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。15.分块查找的平均查找长度不仅与索引表的长度有

4、关，而且与块的长度有关。()A.正确B.错误参考答案：A16.图的遍历(名词解释)参考答案：是从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。17.非空的双向循环链表中任何结点的前驱指针均不为空。()A.正确B.错误参考答案：A18.一个队列的入队序列是1、2、3、4，则队列的首次输出元素是()。A.1B.2C.3D.4参考答案：A19.分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。()A.正确B.错误参考答案：A20.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是()。A.希尔排序B.快速排序C

5、.插入排序D.选择排序参考答案：D21.二叉树的第K层的结点数最多为()。A、2k-1B、2K+1C、2(k-1)+1D、2(k-1)参考答案：D22.队列的插入操作是在()。A.队尾B.队头C.队列任意位置D.队头元素后参考答案：A23.快速排序是排序算法中平均性能最好的一种排序。()A.正确B.错误参考答案：A24.在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度()。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B25.森林的先序遍历与其对应的二叉树的中序遍历对应。()A、正确B、错误参考答案：A26.堆的形状是一棵()。

6、A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树参考答案：C27.队列允许在队尾删除，在队头插入。()A.正确B.错误参考答案：A28.数据结构是指()。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A29.一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是()。A.AB.EC.BD.D参考答案：B30.堆排是一种()排序。A、插入B、选择C、交换D、归并参考答案：B31.对线性表进行折半查找时，要求线性表必须()。A.以顺序方式存储B.以链接方式存储C.以顺序方式存储，且结点按关键字有序排序D.以链接方式存储，且结点按关键字有序排序参考答案

7、：C32.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是()。A.6B.4C.3D.2参考答案：C33.如果某种排序算法是不稳定的，则这种算法不可用。()A.正确B.错误参考答案：A34.函数substr(“DATASTRUCTURE”，5，9)的返回为()。A、“STRUCTURE”B、“DATA”C、“ASTRUCTUR”D、“DATASTRUCTURE”参考答案：A35.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用()

8、方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、单单选择排序参考答案：D36.对于双向链表，在两个结点之间插入一个新结点需修改的指针共()个，单链表为()个。A.4，1B.4，2C.1，4D.2，4参考答案：B37.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C38.若用n表示图中顶点数目，则有()条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C39.设某完全无向图中有n个顶点，则该完全无向图中有()条边。A、n(n-1)/2B、n(

9、n-1)C、nD、n-1参考答案：A40.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()A.正确B.错误参考答案：A41.在数据结构中，图形结构中元素之间存在()关系。A.一对一B.一对多C.多对一D.多对多参考答案：D42.由树转化成二叉树，其根节点的右子树总是空。()A.正确B.错误参考答案：A43.栈是限定在表尾进行插入或删除操作的线性表。()A、正确B、错误参考答案：B44.二叉排序树上左子树上所有结点的值均小于它的根结点的值。()A.正确B.错误参考答案：A45.中序遍历二叉排序树可以得到一个有序的序列。()A.正确B.错误参考答案：A46.邻接表法只能用于有向图存储。

10、()A.正确B.错误参考答案：B47.序例278、109、930经过一趟基数排序后结果为()。A、930、278、109B、109、930、278C、109、278、930D、278、109、930参考答案：A48.任何有向网的拓扑排序的结果是唯一的。()A.正确B.错误参考答案：A49.写出二叉树进行前序和中续遍历的过程。参考答案：前序遍历：(1)访问根结点(2)前序遍历左子树(3)前序遍历右子树中序遍历：(1)中序遍历左子树(2)访问根结点(3)中序遍历右子树50.Prim(普里姆)算法适用于求()的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求()的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A