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

书山有路勤为径，学海无涯苦作舟！ 住在富人区的她兰州大学22春“计算机科学与技术”数据结构离线作业（一）辅导答案一.综合考核(共50题)1.如何知道循环队列是空还是满?参考答案：采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：(1)设置一个布尔变量以区别队满还是队空；(2)浪费一个元素的空间，用于区别队满还是队空；(3)使用一个计数器记录队列中元素个数(即队列长度)。我们常采用方法(2)，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。判断循环队列队空标志是：f=rear；队满标志是：f=(r+1)%N2.在对含n个结点的二叉树进行先序、中序和后序遍历时，其时间复杂度()。A.都不相同B.完全相同C.先序和中序相同，而与后序不同D.中序和后序相同，而与先序不同参考答案：B3.采用分快查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分()个结点最佳。A.10B.25C.6D.625参考答案：B4.栈是限定在表尾进行插入或删除操作的线性表。()A、正确B、错误参考答案：B5.中序遍历二叉排序树可以得到一个有序的序列。()A.正确B.错误参考答案：A6.一个栈的入栈序列是A、B、C、D、E，五个元素都入栈后，首次出栈的元素是()。A.AB.EC.BD.D参考答案：B7.若用单链表示列队，那么应选用()。A、带尾指针的循环链表B、带尾指针的非循环列队C、带头指针的非循环链表D、带头指针的循环链表参考答案：A8.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为()。A.(n-1)2B.n2C.(n+1)2D.n参考答案：C9.堆的形状是一棵()。A.二叉排序树B.满二叉树C.完全二叉树D.平衡二叉树参考答案：C10.序例278、109、930经过一趟基数排序后结果为()。A、930、278、109B、109、930、278C、109、278、930D、278、109、930参考答案：A11.数据结构是带有结构的数据元素的集合。()A.正确B.错误参考答案：A12.设某完全无向图中有n个顶点，则该完全无向图中有()条边。A、n(n-1)/2B、n(n-1)C、nD、n-1参考答案：A13.Prim(普里姆)算法适用于求()的网的最小生成树; kruskal(克鲁斯卡尔)算法适用于求()的网的最小生成树。A.边稠密，边稀疏B.边稀疏，边稠密C.边稠密，边稠密D.边稀疏，边稀疏参考答案：A14.栈是后进先出的线性表。()A、正确B、错误参考答案：A15.在数据结构中，图形结构中元素之间存在()关系。A.一对一B.一对多C.多对一D.多对多参考答案：D16.分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。()A.正确B.错误参考答案：A17.数据的逻辑结构是指各数据元素之间的逻辑关系。()A.正确B.错误参考答案：A18.设有一棵算术表达式树，用什么方法可以对该树所表示的表达式求值?参考答案：方法有二。一是对该算术表达式(二叉树)进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符(、-、*、/等)进行最后求值。19.在单链表中设置头结点的作用是()。A.主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变B.便于查找C.便于连接D.快速插入记录参考答案：A20.归并排序是一种稳定的排序方法。()A.正确B.错误参考答案：A21.线性表中的所有元素都有一个前驱元素和后继元素。()A.正确B.错误参考答案：A22.堆排是一种()排序。A、插入B、选择C、交换D、归并参考答案：B23.满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。()A.正确B.错误参考答案：A24.单链表的结点包含()和()。A、结点域，符号域B、数据域，符号域C、结点域，指针域D、数据域，指针域参考答案：D25.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储()。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法参考答案：C26.顺序存储结构是通过()表示元素之间的关系的;链式存储结构是通过()表示元素之间的关系的。A.物理上相邻，指针B.逻辑上相邻，指针C.逻辑上相临，结点D.物理上相邻，结点参考答案：A27.数据结构是指()。A.数据元素的组织形式B.数据类型C.据存储结构D.数据定义参考答案：A28.中序遍历的递归算法平均空间复杂度为()。A.2(n)B.n(2)C.0(n)D.2n参考答案：C29.非空的双向循环链表中任何结点的前驱指针均不为空。()A.正确B.错误参考答案：A30.先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。()A.正确B.错误参考答案：A31.稀疏矩阵(名词解释)参考答案：对于那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵称为稀疏矩阵。32.线性表的唯一存储形式就是链表。()A.正确B.错误参考答案：A33.对于哈希函数，冲突只能尽可能的少，不可能完全避免。()A、正确B、错误参考答案：A34.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是()。A.6B.4C.3D.2参考答案：C35.平衡二叉树的平衡因子只可能是-1、0、1。()A.正确B.错误参考答案：A36.如果某种排序算法是不稳定的，则这种算法不可用。()A.正确B.错误参考答案：A37.如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用()方法最快。A、起泡排序B、快速排列C、Shell排序D、堆排序E、单单选择排序参考答案：D38.二叉排序树上左子树上所有结点的值均小于它的根结点的值。()A.正确B.错误参考答案：A39.从未排序序列中挑选元素，并将其依次插入已排序序列(初始时为空)的一端的方法，称为()。A.希尔排序B.归并排序C.插入排序D.选择排序参考答案：D40.若用n表示图中顶点数目，则有()条边的无向图成为完全图。A.nB.n-1C.n(n-1)2D.n(n+1)2参考答案：C41.序列49、38、65、97、76、13、27、49进行一趟冒泡排序后的序列为()。A.49、38、65、97、76、13、27、49B.13、27、38、49、49、65、76、97C.38、49、65、76、13、27、49、97D.38、49、65、13、27、49、76、97参考答案：C42.对n个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多()。A、从小到大排列好的B、从大到小排列好的C、元素无序D、元素基本有序参考答案：B43.链表不具备的特点是()。A.可随机访问任意一个结点B.插入和删除不需要移动任何元素C.不必事先估计存储空间D.所需空间与其长度成正比参考答案：A44.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是()。A.(rear+1)%n=frontB.rear=frontC.rear+1=frontD.(rear-l)%n=front参考答案：B45.线性表若采用顺序存储结构时，要求内存中的可用存储单元的地址必须连续。()A、正确B、错误参考答案：A46.不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。()A.正确B.错误参考答案：A47.邻接表法只能用于有向图存储。()A.正确B.错误参考答案：B48.对于哈希函数，冲突只能尽可能得少，不可能完全避免。()A.正确B.错误参考答案：A49.哈希表不需要进行比较便可以直接取得所查记录。()A.正确B.错误参考答案：A50.完全二叉树中的叶子结点只可能在最后两层中出现。()A.正确B.错误参考答案：A