数据结构模拟试题一及答案

数据结构模拟测试一一、对错(每项1分，共15分)1.计算机程序处理的对象可以分为两类：数据和非数据。2.根据大小关系排列的所有自然数的序列是一个线性表。3.描述单向链表的节点类型时，必须先描述数字字段，然后描述指针字段。4.顺序堆栈是指定存储方法的堆栈。5.树结构中的每个节点都有一个前身。6.在任何完整的二叉树中，最多有一个1度的分支节点。7.如果一个顶点是有向图的根，那么该顶点的关联度必须为零。8.如果一个图的邻接矩阵全是零行，而不是全是零列，那么它必须是有向的。9.用一维数组表示矩阵可以节省存储空间。广义列表的长度与它包含多少原子元素有关。11.块搜索的效率取决于线性表被分成多少块。12.哈希表的负载因子等于哈希表中存储的节点数。13.在气泡分选过程中，一些元素可能会向相反的方向移动。14.根据逻辑关系组织的记录集合称为逻辑记录。15.索引非顺序文件的特点是索引表中的索引项不一定按照关键字的大小有序排列。二、填空(每空1分，共15分)1.顺序表是_ _ _ _ _ _ _ _ _ _ _ _ _ _线性表。2.如果Q1Qm用作非循环顺序队列的存储空间，则该队列最多只能插入_ _ _次。3.堆栈和队列的区别在于_ _ _ _ _ _。4.高度为h(h0)的二叉树中至少有_ _ _个节点，最多有_ _ _个节点。5.如果使用二进制链表来存储具有M个叶子和N个分支节点的树，则二进制链表具有带空左指针字段的_ _ _个节点和带空右指针字段的_ _ _个节点。6.有n个顶点的根有向图至少有_ _ _条边，最多有_ _ _条边。7.如果具有10行20列的矩阵由行优先级表表示，则矩阵中第8行和第7列的元素是序列表中的_ _。8.在每个元素的搜索概率相等的情况下，使用顺序搜索法从包含12个元素的有序表中找到一个元素，元素之间的平均比较次数为_ _ _ _ _。9.当合并两个长度为m的有序表时，有序代码的比较时间至少为_ _ _次，最多为_ _ _次。10.在高度为3的6阶B树中，至少有_ _ _个关键字，最多有_ _ _个关键字。三、选择题(每题2分，共30分)1.计算机处理的数据通常有某种内部联系，这是指_ _ _ _ _ _。A.元素b之间有某种关系。数据和数据之间有某种关系C.元素d内部有某种结构。数据项和数据项之间有某种关系2.假设当前序列表中有4个元素，第I个元素位于i中，1i4。如果新插入的元素存储在6中，则_ _ _ _ _ _。A.操作错误将发生在1号6号没有形成一个序列表序列表的长度大于序列表中元素的数量，这将降低存储空间的利用率D.序列表元素的序号与数组元素的下标不一致，这会给使用带来麻烦。3.设H为没有头节点的循环单向链表的指针，P为与H相同类型的变量。当P指向链表的最后一个节点时，_ _ _ _ _ _ _ _ _ _。a.p指示的节点指针字段的值为空，b.p的值等于h的值。c.p表示的节点地址等于h的值，d.p表示的节点指针字段的值等于h的值。4.堆栈的定义不涉及数据的_ _ _ _ _ _ _ _ _ _。A.逻辑结构b .存储结构c .操作d .逻辑结构和存储结构5.如果五个元素在堆栈中的排列顺序是1、2、3、4、5，那么它们在堆栈中的排列顺序可能是_ _ _ _ _ _ _ _ _ _ _ _ _ _。a2，4，1，3，5 B3，4，1，5，2 C3，2，4，1，5 D4，1，3，2，56.如果二叉树节点的前序序列和前序序列相同，那么二叉树_ _ _ _ _ _ _ _ _ _ _。A.只有一个节点b，每个节点都没有左子节点c，每个节点都没有右子节点d8.如果有n个顶点的有向图在拓扑上是有序的，那么有向图就可以归结为abgcehfd图_ _ _ _ _ _ _ _ _ _。A.包含N个强连通分量。具有唯一顶点，入口度为0。具有多个顶点，出口度为0d是带根的有向图9.特殊矩阵由行优先级表_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _表示A.简化矩阵元素之间的逻辑关系b .促进按行处理矩阵元素c、矩阵元素的存储地址d不能根据行列数计算，节省了存储空间10.对于非空的含义列表，_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。A.可能不包含任何原子元素b .至少一种原子元素其长度不小于任何子表d的长度，至少包含一个非空的子表元素11.使用二进制搜索方法在有序表上找到13(2，4，6，8，10，12，14，16，18，20)，然后比较_ _ _ _ _ _ _ _ _。a10，16，12，14 b10，16，12 c12，16，14 D10，16，12，1312.具有14个节点的平衡二进制排序树的最大深度为_ _。a4 b . 5 c . 6d . 713.如果元素R1和R2具有相同的排序代码，并且在合并排序之前R1在R2前面，那么当排序完成时，_ _ _ _ _ _ _ _ _ _。A.R1可能落后于R2。R1一定在R2的后面C.R1必须在R2维面前选择R1或R2中的一个留在线性表中14.在下面的4个序列中，只有_ _ _满足堆的定义。A.13，27，49，76，76，38，85，97 B.76，38，27，49，76，85，13，9713，76，49，76，27，38，85，9715.在以下四种排序方法中，不稳定排序方法是_ _ _ _ _ _ _ _ _ _ _排序和_ _ _ _ _ _ _ _ _ _ _排序。A.快速b .合并c .简单选择d .半插入四.图表问题1.众所周知，树节点的前序序列是abcdefgh，后序序列是cdebfhga。请画出这棵树的逻辑结构图。2.使用基数排序方法，将排序代码序列572、586、413、15、724、529、525、608、37、119从小到大排序。请在每次收集后写下线性表格。五、算法填空设G是有n个顶点的连通无向图的邻接矩阵