数据结构练习题C

数据结构练习题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)方法压缩存储。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.任意有限个字符构成的序列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,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.元素按值有序，且采用顺序存储结构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.有一棵或多棵C.一定有多棵D.可能不存在22.下列说法不正确的是（C）。A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.遍历的基本算法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程二、填空题1．在n个结点的顺序表中插入一个结点需平均移动_2/n__个结点，具体移动次数取决于_位置与表长_。2．在双链表中每个结点有两个指针域，一个指向__前驱节点_，另一个指向__后继节点__。3．数据结构的三个方面：数据的逻辑结构、物理结构、运算。4．算法分析的两个主要方面是___时间复杂度___和__空间复杂度__。5．深度为8的（根的层次号为1）满二叉树有128个叶子结点。6．设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为_k，2k-1_7．队列中允许进行插入的一端称为__队尾___。8．若连通网络上各边的权值均不相同，则该图的最小生成树有___1___棵。9．二叉树的遍历方式有三种：先根遍历、中序遍历、____后根遍历___。10．由一棵二叉树的后序序列和_中序序列__唯一确定这棵二叉树。11若一棵二叉树有10个叶结点，则该二叉树中度为2的结点个数为____9__。12．一个具有n个顶点的图采用邻接矩阵表示，则该矩阵的大小为n*n。三、应用题1．将表达式((a+b)-c*(d+e)-f)*(g+h)改写成后缀表达式。解答：后缀表达式：ab+cde+*-f-gh+*2．给定表（45,36,56,6,64,32,8,41），按数据元素在表中的次序构造一棵二叉查找树。3．已知一棵二叉树的中序和前序序列如下，求该二叉树的后序序列。中序序列：c，b，d，e，a，g，i，h，j，f前序序列：a，b，c，d，e，f，g，h，i，j4.用普里姆算法(Prim)算法求出下图的最小支撑树。5.应用直接插入排序算法，对键值序列49,38,65,97,76,13,27,45从小到大进行排序，写出每趟排序的结果。解：应用直接插入排序算法，对键值序列49,38,65,97,76,13,27,45从小到大进行排序，每趟排序的结果如下：初始序列：4938659776132745第一趟排序结果：[49]38659776132745第二趟排序结果：[3849]65977613274520135648915721065123第三趟排序结果：[384965]9776132745第四趟排序结果：[38496597]76132745第五趟排序结果：[3849657697]132745第六趟排序结果：[133849657697]2745第七趟排序结果：[13273849657697]45第八趟排序结果：[1327384549657697]四、算法设计题1．假设线性表用带表头结点的单向链表head表示，试写出删除表中所有data域值为零的元素的算法。解：intDeleteItem(Node*head)//线性表用带头结点的单向链表示，删除表中所有data域为零的元素的算法{Node*p=head;//声明指针p，并令其指向链表头结点while(p-nextNode()!=NULL){if(p-nextNode()-data==0)p-next=p-nextNode()-next.elsep=p-nextNode();//指针下移}}2．设一棵二叉树以二叉链表为存储结构，试写一算法求该二叉树上1度结点的个数。解答：voidcount1(BinTreeNode*t,int&count)//求出二叉树中1度结点个数{if(t!=NULL){if((t-left==NULL)&&(t-right!=NULL))||((t-left!=NULL)&&(t-right==NULL))count++;count1(t-left,count);count1(t-right,count);}}3.试设计一算法，计算带头结点的单链表head(head指向表头)的结点个数。解答：intLength()//计算带表头结点的单链表head的长度{Node*p=head-next;intcount=1;while(p-next!=NULL){p=p-next;count++;}returncount;}