数据结构典型习题

数据结构典型习题第一章至第五章算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构下列程序段的时间复杂度为()。{for(i=0；ifor(j=0；jx=x+1；}A.O(5)B.O(5+n)C.O(n5)D.O(n)当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。对于栈操作数据的原则是（）。A.先进先出B.后进先出C.后进后出D.不分顺序有六个元素6，5，4，3，2，1的顺序进栈，问下列哪一个不是合法的出栈序列？（）A.543612B.453126C.346521D.234156设栈的输入序列是1，2，3，4,则（）不可能是其出栈序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，E.3，2，1，4，表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（），其中^为乘幂。A.3,2,4,1,1；(*^(+*-B.3,2,8；(*^-C.3,2,4,2,2；(*^(-D.3,2,8；*^(-下面关于串的的叙述中，哪一个是不正确的？（）A．串是字符的有限序列B．空串是由空格构成的串A．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）A．求子串B．联接C．匹配D．求串长串的长度是指（）A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符的个数D．串中所含非空格字符的个数对稀疏矩阵进行压缩存储目的是（）。A.便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度设广义表L=（（a,b,c）），则L的长度和深度分别为（）。A.1和1B.1和3C.1和2D.2和3广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）。Head(Tail(Head(Tail(TailA))))A.(g)B.DC.cD.d编程实现线性链表的基本操作如GetElem（）,ListInsert(),ListDelete(),CreateList()，MergeList（）等。第六章树和二叉树一、选择题1．树最适合用来表示（）。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据2．深度为5的二叉树至多有（）个结点。A．16B．32C．31D．103．有32个结点的完全二叉树的深度为（）（根的层次为1）。A．8B．7C．6D．54．若二叉树中度为2的结点有15个，度为1的结点有10个，则有（）个叶结点。A．25B．15C．16D．416．有64个结点的完全二叉树的深度为（）（根的层次为1）。A．8B．7C．6D．57．对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。A．3B．1C．2D．不存在8．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（）二叉树。A．空或只有一个结点B．高度等于其结点数C．任一结点无左孩子D．任一结点无右孩子9．前序遍历与中序遍历结果相同的二叉树为（）；前序遍历和后序遍历结果相同的二叉树为（）。A．一般二叉树B．只有根结点的二叉树C．根结点无左孩子的二叉树D．根结点无右孩子的二叉树E．所有结点只有左子树的二叉树F．所有结点只有右子树的二叉树14．设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所含的结点数至少为（）。A．2hB．2h-1C．2h+1D．h+116．设一棵二叉树中没有度为1的结点，已知叶子结点数为n，此树的结点数为（）。A．2n+2B．2n+1C．2nD．2n-117．设哈夫曼树的叶子结点数为n，则它的结点总数为（）。A．2n-1B．2nC．2n+1D．不确定18．由带权9、1、3、5、6的5个叶子结点生成的哈夫曼树的带权路径长度为（）。A．50B．60C.52D.6519．二叉树的先序遍历序列和中序遍历序列分别为：EFHIGJK和HFIFJKG,该二叉树根的右子树的根是（）。A．EB．FC.GD.H21．二叉树上叶结点数等于（）。A．分支结点数加１B．单分支结点数加１C.双分支结点数加１D.双分支结点数减１二、填空题1.具有n个结点的完全二叉树的深度为。2.二叉树第i层上最多有个结点。3.深度为k的二叉树最多有个结点7．分别画出和下列树对应的二叉树。AB8．画出和下列二叉树相应的森林。AB9．以数据集{4，5，6，7，10，12，18}为结点权值构造的Huffman树，并求其带权路径长度。10．假设一棵二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK，请画出该树并给出其后序序列。12.已知某二叉树按后序遍历序列为CEDBHJIGFA，按中序遍历序列为CBEDAHGIJF,试画出该二叉树形状（要求写出中间过程），并写出它的先序遍历序列。13.设a,b,c,d,e,f六个字母出现的次数分别为7,19,2,6,32,3,试为这六个字母设计huffman编码并画出对应huffman树。14.对给出的数据序列4,5,6,7,10,12,15,18,23，构造一棵huffman树，并求其带权路径长度。15．设a,b,c,d,e,f,g,h,i九个字母出现的次数分别为4,5,6,7,10,12,15,18,23，构造一棵huffman树，并给出每个字符的huffman编码。16.设一棵二叉树的先序、中序遍历序列分别为EBADCFHGIKJ和ABCDEFGHIJK，要求：(1)画出该二叉树(要求写出中间步骤);(2)将这棵二叉树转换成对应的树(或森林)。17.设一份电文中a,b,c,d,e,f,g,h八个字母出现的次数分别为7,19,2,6,32,3,21,10,要求：(1)为每个字母设计huffman编码,(2)给出八个字母二进制表示的等长编码并比较两方案的优缺点。18.编程实现二叉树的三种遍历方法，并统计特殊元素，如最大值，最小值,和值，终端节点。第七章图1．在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为()A.n-1B.nC.n+1D.n*22．7.有n个顶点e条边的无向图G,它的邻接表中的表结点总数是()A．2nB．nC．2eD．e3．有4个顶点的无向完全图的边数为()A.6B.12C.16D.204．具有n个叶结点的赫夫曼树共有个结点5．N个顶点的连通图的生成树有条边。6．图的深度、广度优先遍历算法分别类似于二叉树的（）。A.先序遍历和中序遍历B.先序遍历和层序遍历C.后序遍历和中序遍历D.层序遍历和先序遍历7．若某无向图G的邻接表如图所示，试给出以顶点V1为出发点，按深度、广度优先搜索所产生的一棵生成树。8．下图为一无向连通网络，分别根据普里姆(Prim)算法和克鲁斯卡尔(Kruscal)算法从顶点１出发构造出它的最小生成树。（要求写出求解步骤）。9.对如下带权图，请：(1)给出结点的一个拓扑序列；（2）找出一条从v1到v7的最短路径（要求写出求解步骤）。10．对下图所示的AOE网络，给出其关键路径，（要求写出相关时间表格）。第九章查找一、选择题1．顺序查找法适合于存储结构为（）的线性表。A．散列存储B.顺序存储或链式存储C.压缩存储D.索引存储2．二分查找法要求查找表中各元素的关键字必须是（）排列。A．递增或递减B.递增C.递减D.无序6．有一个有序表为{3，9，12，32，41，45，62，75，77，82，99}，用二分查找法查找82成功时的查找次数是()。A．1B．2C．3D．47.平衡二叉树上结点的平衡因子是指。12.在散列函数H(k)=kMODm中，一般来讲，m应取（）。A．奇数B．偶数C．素数D．充分大的数11．若待散列的序列为（18，25，63，50，42，32，9），散列函数为H(key)=keymod9，与18发生冲突的元素有个。三、基础知识题1．简述顺序查找法和二分查找法的区别。2.取适当Hash函数及处理冲突的方法，试在0--12散列地址空间中对关键字序列(2,41,53,46,30,13,01,67)构造Hash表，并求出等概率下查找成功的平均查找长度。4．已知一组元素为(37,70,29,46,25,78,62,12)，画出按元素排列输入生成的一棵二叉排序树，并求其在等概率情况下查找成功的平均查找长度（要求写出每插入一个元素时二叉排序树形状）。第十章内部排序一、选择题1．堆排序属于（）。A．插入排序B交换排序C归并排序D．选择排序2．快速排序属于（）。A．插入排序B交换排序C归并排序D．选择排序3．希尔排序属于（）.A．插入排序B交换排序C归并排序D．选择排序4．冒泡排序属于（）.A．插入排序B交换排序C归并排序D．选择排序14．下列序列中，（）才可能是执行第一趟快速排序后得到的序列。A．{8,6,18}19{16,10,50}B{6,4,8}18{81,19,36,18}C{81,1,2}36{99,81,69}D．{2,3,4}89{78,98,68}15．对于关键字序列{72,73,71,23,94,16,5,68,76,103}，用筛选法建堆，必须从关键字为（）的结点开始。A．103B72C94D．2316．以下序列中，（）不是堆。A．{15,26,38,49,27,51,39,62}B{15,23,26,72,94,71,68,73}C{15,23,71,94,72,68,26,73}D．{15,23,26,68,94,72,71,73}二、填空题2．最简单的交换排序方法是。5.归并排序的时间复杂度为。6.快速排序是一种类型的排序；对含有n个元素的序列进行排序时，快速排序的时间复杂度是。7．对具有n个记录的序列进行快速排序，在最坏情况下的时间复杂度是；在最好情况下的时间复杂度是。三、基础知识题1．以关键字序列（25,84,21,47,15,27,68,35,20）为例，手工执行各种排序算(从小到大），写出每一趟排序结束时的关键字状态。(冒泡排序，快速排序，堆排序)3．试按堆的构造方法，写出对应于序列(26,5,77,1,61,11,59,15,48,19)的初始堆（大根堆、小根堆均可，要求给出调整过程）。4．判别以下序列是否为堆（小根堆或大根堆）。如果不是，则把它调整为堆（要求记录交换次数最少）。(1)(100,86,48,73,35,39,42,58,66,22);（大根堆?）(2)(12,70,33,65,24,56,46,90,86,34)。（小根堆?）