资源描述：
《数据结构练习题C.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构练习题C一、单项选择题1．线性链表中各结点之间的地址（D）。A.必须连续B.一定不连续C.部分地址必须连续D.连续与否无所谓2．在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（A）。A.2B.1C.0D.–13．某二叉树的前序和后序序列正好相同，则该二叉树一定是(A)的二叉树。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子4．设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（D）。A.51234B.45132C.43125D.321545．稀疏矩阵一般采用(C)方法压缩
2、存储。A.三维数组B.单链表C.三元组表D.散列表6．设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（D）。A．3700B．4376C．3900D．46207．在含n个顶点e条边的无向图的邻接矩阵中，零元素的个数为（D）。A．eB．2eC．n2-eD．n2-2e8．邻接表的存储结构下图的深度优先遍历类似于二叉树的(A)。A．先序遍历B.中序遍历C.后序遍历D.按层遍历9．串是（D）。A.一些符号构成的序列B.一些字母构成的序列C.一个以上字符构成的序列D.任
3、意有限个字符构成的序列10．若在线性表中采用折半查找法查找元素，该线性表必须满足（C）。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且采用顺序存储结构D.元素按值有序，且采用链式存储结构11.深度为n的二叉树中所含叶子结点的个数最多为（C）个。A.2nB.nC.2nD.2n-112.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用(C)法。A.冒泡排序B.快速排序C.堆排序D.基数排序13．下列四个关键字序列中,(C)不是堆。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68
4、,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}14．任何一个无向连通图的最小生成树(B)。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在15．在一个具有n个顶点的无向图中,要连通全部顶点至少需要(C)边。A.nB.n+1C.n-1D.n/216.按照二叉树的定义,具有3个结点的二叉树有(C)种。A.3B.4C.5D.617.若在线性表中采用折半查找法查找元素，该线性表必须满足（C）。A.元素按值有序B.采用顺序存储结构C.元素按值有序，且采用顺序存储
5、结构D.元素按值有序，且采用链式存储结构18.深度为n的二叉树中所含叶子结点的个数最多为（C）个。A.2nB.nC.2nD.2n-119.设有6000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用(C)法。A.冒泡排序B.快速排序C.堆排序D.基数排序20.对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（C）。A.直接选择排序B.直接插入排序C.快速排序D.起泡排序21.任何一个无向连通图的最小生成树(B)。A.只有一棵B.有一棵或多棵
6、C.一定有多棵D.可能不存在22.下列说法不正确的是（C）。A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.遍历的基本算法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程二、填空题1．在n个结点的顺序表中插入一个结点需平均移动_2/n__个结点，具体移动次数取决于_位置与表长_。2．在双链表中每个结点有两个指针域，一个指向__前驱节点_，另一个指向__后继节点__。3．数据结构的三个方面：数据的逻辑结构、物理结构、运算。4．算法分析的两个主要方面是___时间复杂度___和__空间复杂度__。5．深度为
7、8的（根的层次号为1）满二叉树有128个叶子结点。6．设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为_k，2k-1_7．队列中允许进行插入的一端称为__队尾___。8．若连通网络上各边的权值均不相同，则该图的最小生成树有___1___棵。9．二叉树的遍历方式有三种：先根遍历、中序遍历、____后根遍历___。10．由一棵二叉树的后序序列和_中序序列__唯一确定这棵二叉树。11若一棵二叉树有10个叶结点，则该二叉树中度为2的结点个数为____9__。12．一个具有n个顶点的图采用邻接矩阵表示
8、，则该矩阵的大小为n*n。三、应用题1．将表达式((a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。解答：后缀表达式：ab+
