数据结构练习题（1）

xhao

2020-05-03

关注关注

逻辑上通常可以将数据结构分为（线性结构和非线性结构）
如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（树）
在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：n-i+1
在非空线性链表中由p所指结点的后面插入一个由q所指的结点，应依次执行（q->next=p->next;p->next=q）
已知栈的最大容量为4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（3，2，5，4，1，6）
设栈S和队列Q初始均为空，若6个元素入栈的顺序为1，2，3，4，5，6，一个元素出栈以后立即入队列Q，若6个元素出队列的顺序为2、4、3、6、5、1，则栈S的容量至少为（3）
在计算机内实现递归算法时所需的辅助数据结构是（栈）
循环队列存储在数组A[0..m-1]，则出队时的操作为（front=(front+1) mod m
若以S和X分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列合法的是（SSSXXSXX）
在具有m个单元的循环队列中，队头指针为front，队尾指针尾rear，则队满的条件是（（rear+1）%m==front）
在表长为n的顺序表上做插入运算，平均要移动的结点数为（n/2）
元素的进栈次序为A，B，C，D，E，则退栈中不可能的序列是（E,A,B,C,D)
下述二叉树中，（哈夫曼树）满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。
若用邻接矩阵表示一个有向图，则其中每一行包含的″1″的个数为(图中每个顶点的出度)
具有6个顶点的无向图至少应该有（5）条边才能确保是一个连通图
下面（拓扑排序）方法可以判断出一个有向图中是否有环（回路）
采用邻接表存储的图的深度优先遍历算法类似于二叉树的（先序遍历）
对线性表进行二分查找时，要求线性表必须是（以顺序方式存储，且结点按关键字有序排列）
由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（44）
快速排序方法在（要排序的数据已基本有序）情况下最不利于发挥其长处。
一组记录的排列码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为（84,79,56,38,40,46 ）
下列陈述中正确的是（二叉树中最多只有两棵子树，并且有左右之分）
树的先根序列等同于与该树对应的二叉树的（先序序列）
以下有关广义表的表述中，正确的是（由0个或多个原子或子表构成的有限序列）
下列各项键值序列中不是堆的为（{5，23，16，73，94，72，71，68}）
线性表采用链式存储结构时，要求内存中可用存储单元的地址(连续和不连续都可以)
对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(用尾指针表示的单循环链表)
线性表是n个具有相同类型（数据元素）的有限序列(n>=0)
在线性表的下列运算中，不改变数据元素之间结构关系的运算是（定位）
链表中逻辑上相邻的元素其物理地址（不一定）相邻
4
有一个有序表为（1,3,9,12,32,41,45,62,75,77,82,95,100），当二分查找值为82的结点时，（）次比较后查找成功。4
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（1倍）
下列叙述中不符合m阶B树定义要求的是（叶结点之间通过指针链接）
线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（错）结点内部空间是连续的
在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。（对）
顺序存储的线性表可以随机存取。（对）
若一个广义表的表头为空表，则此广义表亦为空表。（错）例如: 广义表()和(())不同。前者是长度为0的空表,对其不能做求表头和表尾的运算;而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表),对其可进行分解,得到的表头和表尾均是空表() ”
任何一个非空广义表，其表头可能是单元素或广义表，其表尾必定是广义表。（对）
广义表是由零或多个原子或子表所组成的有限序列，所以广义表可能为空表。（对）
用树的前序遍历和中序遍历可以导出树的后序遍历。（对）
在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应特殊处理。（错）
将一棵树转换成二叉树后，根结点没有左子树。（错）
在n个结点的无向图中，若边数〉n-1，则该图必是连通图。（错）
一个图的广度优先遍历生成树是唯一的（错）
对两棵具有相同关键字集合而形状不同的二叉排序树，按中序遍历它们得到的顺序是一样的.（对）
负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。（错）
对一个堆，按二叉树层次进行遍历可以得到一个有序序列。（错）
对于n个记录的集合进行冒泡排序，在最坏情况下所需要的时间是O(n平方)。（对）
设串sl=″Data Structures withJava″,s2=“it″，则子串定位函数index(s1,s2)的值为（18）
广义表((a,b),c,d)的表头是( ) (a,b)
若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字b的过程中，先后进行比较的关键字依次为 ( )f,c,b
假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（head–>next= =head）
二维数组A[8][9]按行优先顺序存储，若数组元素A[2][3]的存储地址为1087，A[4][7]的存储地址为1153，则数组元素A[6][7]的存储地址为（1207）
已知二叉树的中序序列和后序序列均为ABCDEF，则该二叉树的先序序列为（FEDCBA）
已知在顺序表中每个元素需占用8个存储单元，且LOC（a1）=100,则LOC（a5）=(132)
广义表GetTail[GetHead[GetTail[((a,b),(c,d))]]]操作的结果为（(d)）
深度为5的二叉树至多有31个结点
广义表（（（））,a,((b,c),(),d),(((e)))）的长度为（4）