数据结构题库

A.原子。4列表A.原子。4列表rb.任何元「A.不可能是子表r；只能是子表「卜.只能是原子°b.可以是子表或者原子.在以下的叙述中，正确的是o°A.二维数组可以看做它的每一个数据元素为一个线性表的线性表rb.栈的操作方式是先进先出r1c.线性表的线性存储结构优于链表存储结构 「D.队列的操作方式是先进后出.如下陈述中正确的是o°A.串是一种特殊的线性表rb.串的长度必须大于零r1c.串中元素只能是字母r卜空串就是空白串.如下陈述中正确的是o°A.串是一种特殊的线性表rb・串的长度必须大于零r1c.串中元素只能是字母r两个串S1和S2若长度相同，则这两个串相等.数组A中,每一个元素的长度为3字节，行下标从1到8,列下标从1到10,从首地址SA开始连续存放在存储器中，按行存放时，元素素8][5]地址为orA.SA+141 CB.SA+180°LSA+222rD.SA+225.任何一个非空列表其表头可能是原子,也可能是列表，而其表尾是。素「Id.空.稀疏矩阵普通的压缩存储方法有两种。rA.二维数组和三维数组6b.三元组和散列rL三元组和十字链表Id.散列和十字链表.常对数组进行的两种基本操作是。「 cLA.建立和删除 B.插入和修改"k查找和修改rk查找和索引.假定利用数组a[N]顺序存储一个栈，用top表示栈顶指针，top==0表示栈空，并已知栈未满，当元素x进栈时所执行的操作为ocI cLA.a[-top]=x; B.a[top一]二x;C.a[++top]=x; D.a[top++]二x;.由两个栈共享一个向量空间的好处是A.减少存取时间，降低下溢发生的机率rB.节省存储空间，降低上溢发生的机率⑥C.减少存取时间，降低上溢发生的机率rD.节省存储空间，降低下溢发生的机率.入栈次序是a,b,c,d,e,则出栈次序不可能是 rI,,rIA.e,d,c,b,a B.d,e,c,b,aa rLC.d,c,e,a,bD.a,b,c,d,e.假定利用数组a[N]循环顺序存储一个队列，用front（指向队首元素）和rear（Jh向队尾元素的下一位置）分别表示队首和队尾指针，并已知队列未空，当出队并返回队首元素时所执行的操作为 。A.returnB.returna[++rear%N];A.returnB.returna[++rear%N];a[一rear%N];C.returna[++front%N];(yIr「D.returna[front++%N];.当利用大小为N的一维数组存储一个循环队列时，则该队列的最大长度为orI◎IrIA.N-2B.N-l C.NrId.n+i.假定一个长度为n的循环顺序队列的队首和队尾指针分别为f和r,则判断队满的条件是 o「A.(f+l)%n==r 0B.(r+l)%n=fCC.f=0rD.f=r.假定一个链队列的队首和队尾指针分别为front和rear,则判断队空的条件是A.front二二rear B.front!=NULLr rLC.rear!=NULLD.front二二NULL16.队和栈的主要区别是ora.逻辑结构不同r存储结构不同rb.所包含的运算个数不同°b.限定插入和删除的位置不同17.假定一个顺序队列的队首和队尾指针分别为front和rear,则判断队空的条件是A.fronl+l==rear B.rear+l=rL八6L=frontC.front==0D.front=二rear.链式栈与顺序栈相比，一个比较明显的优点是OrA.插入操作更加方便0b.通常不会浮现栈满的情况「卜.不会浮现栈空的情况r(删除操作更加方便.判定一个栈ST(最多元素为mO)为空的条件是 rA.ST->top<>0⑤B.ST->top=0rI rIST->topOmOD.ST->top=mO.下面算法的时间复杂度为ointf(unsignedintn){if(n==0n==l)return1;elsereturnn*f(n-l);}rA.0(1)⑥B.0(n)rC.0(n2)D.0(n!).在长度为n的顺序存储的线性表中，删除第i个元素(IWiWn)时，需要从前向后挨次前移()个元素。(♦At「Id.1A.n-IIB.n-i+1IC.n-i-lrki.线性表若采用链式存储结构时，要求内存中可用存储单元的地址oCA.必须是连续的rk部份地址必须是连续的「b.一定是不连续的6D.连续，不连续都可以.计算机识别、存储和加工处理的对象被统称为()"A.数据C，数据元素。数据结构b.数据类型.算法指的是。・1a.计算机程序rk解决问题的计算方法rL排序算法D.解决问题的有限运算序列.在对n个元素进行快速排序的过程中，第一趟排序最多需要交换 对元素。「A.n/2 ⑸B.n-1 ,C.nrn+1.若对n个元素进行直接插入排序，在进行i趟(2WiWn)排序时，为寻觅插入位置最多需要进行次元素的比较。CIA rID•1 r-A.i+l IB.i-l C.iD.1.对于哈希函数H(key)=key%13,被称为同义词(即冲突)的关键字是 CA.35和41rB.23和39rL15和44⑸k25和51.若一组记录的排序码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为A.38,40,46,56,79,84IB.40,38,46,79,56,84C.40,38 ， 46,56,79,84ID.40,38,46,84,56,79.在对n个元素进行简单选择排序的过程中，需要进行趟选择。rA.n/2 "B.n-1 ,C.nID.n+1.用某种排序方法对关键字序列(23,72,21,47,15,27,59,35,20)进行排序时,前三趟的结果情况如下：23,21,47,15,27,59,35,20,7221,23,15,27,47,35,20,59,35,20,47,59,72是 7221,15,23,27,

则所采用的排序方法A.选择排序归并排序r7221,15,23,27,

则所采用的排序方法.设哈希表长为14,哈希函数f(k)=k%11,已知表中已有4个元素，关键字分别为15,38,61,84,存储位置分别为4,5,6,7,其它存储位置为空，如用二次探测再散列处理冲突，关键字为49的存储位置是rA.8rB.3rC,5。b.9.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),哨兵位在前,为查找元素26,若采用顺序查找，需要比较次才干查找成功。r1a.3rL4rL5⑥；6.具有e条边的无向图，它的邻接表中有个边结点。CA.e-1CB.e「C.2(e-l)ID.2e.具有e条边的有向图，它的逆邻接表中有个弧结点。A.e-1 •B.e C.2(e-l)rLID.2e.由权值分别为3,8,6,2,5的叶子结点生成一颗哈夫曼树，它的带权路径长度为B.48C.72B.48C.72ID.53.如果某图的邻接矩阵是对角线元素以下元素均为零的上三角矩阵，则此图是a.有向彻底图r；连通图rL强连通图"k有向无环图.下面关于图的存储的叙述中，哪一个是正确的。6A.用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关,而与边数无关rb.用邻接矩阵法存储图，占用的存储空间数只与图中边数有关,而与结点个数无关「上用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关「D.用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关38.图的深度优先遍历类似于树的OA•先序遍历 (B.中序遍历「k后序遍历rId.层次遍历.一个连通图的生成树是包含图中所有顶点的一个子图。r1a.极小「卜连通"h.极小连通CD.无环.有向图的一个顶点的度为该顶点的rA.入度「4出度⑥；.入度与出度之和rID.(入度+出度)/2.在一个有向图中，所有顶点的度数之和等于所有弧数的倍。CA.3 °B.2rC.1ID.1/2.n个顶点的连通图至少有条边。"A.n-lrB.n「C.n+1rID.0.顶点个数为n的无向图最多有条边。A.n-1 B.n(n-l)/2「Ln(n+l)/2・L.n(n-l).树中所有结点的度数之和等于结点总数加orIa.orki"h.t「k2.在一棵树中，每一个结点最多有个直接前驱结点。rA.0k1rC.2rD.任意多个.将一棵有40个结点的彻底二叉树从上到下，从左到右挨次对结点进行编号，根结点的编号为1,则编号为15的结点的左孩子的编号为o。1a,30rb.31。L16rk32.一棵树的广义表表示为a(b(c),d(e(g(h)),f)),则该树的度为2的结点数为Oc c c cA.2B.3C.4D.5.一棵树的广义表表示为a(b(c),d(e(g(h)),f)),则该树的度为o。；2r\.3「1.4「b.5.一棵树的广义表表示为a(b(c),d(e(g(h)),f)),则该树的高度为orIa.2rIb.3rk4"；5.在一棵深度为h的彻底二叉树中，所含结点个数不少于orA.2hrk2h+lCIc.2h-lID.2h-l.在一棵二叉树的第5层上，最多具有 个结点。rA.14 °B.16rC.31rD.32.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于o「A.n,B.n-l0C.n+1「b.2*n.数据结构通常是研究数据的及它们之间的联系。6A.存储和逻辑结构 C卜存储和抽象rb.理想和抽象rk理想与逻辑在含100个结点的彻底二叉树，叶子结点的个数为_50o.一棵含有16个结点的彻底二叉树，对他按层编号，对于编号为7的结点，他的双亲结编号点为_3左孩子编号为__14—、右孩子编号为—15—。.对任何一棵二叉树，若n0,nl,n2分别是度为0,1,2的结点的个数，则n0=_n2+lo.高度为k的二叉树具有的结点数目，最少为—k―,最多为_2kTo.对于一颗具有n个结点的二叉树，对应二叉链表中指针域有个用于指向子结点。.树的双亲表示法便于实现涉及到—双亲 的操作，孩子表示法便于实现涉及到孩子的操作。.在一棵二叉树中，度为2的结点有5个,度为1的结点有6个，那末叶子结点有TOC\o"1-5"\h\z_6 个.假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J))),则结点H的双亲结点为_B o9,假定一棵二叉树的结点个数为32,则它的最小深度为_6o.已知广义表ls=(a,(b,c,d),e),运用head和tail函数取出Is中的原子b的运算是head(head(tail(Is))) 。.广义表(A,(a,b),d,e,((i,j),k)),则广义表的长度为_5,深度为_3 ,表头为 A ,表尾为―((a,b),d,e,((i,j),k))。.稀疏矩阵可用三元组进行压缩存储，存储时需存储非零元的一元素值和行、列数。.在串的链式存储方式中，结点越大，运算处理越不方便)，存储占用量越—小)14.一个串的任意个连续的字符组成的子序列称为该串的—子串—，包含该子序列的串称为—主串,该子序列在串中的位置用—子串的第一个字符在主串中的位置 来表示。.广义表((a))的表头是3)，表尾是0o.广义表((a),a)的表头是(a),表尾是(a)o.数组A中，每一个元素的长度为3个字节,行下标从1到8,列下标从1到10,从首地址开始连续存放在存储器内，存放该数组至少需要的单元数是240o.栈的特点是—后进先出.对于顺序存储的队列，存储空间大小为n,头指针为F,尾指针为Ro若在逻辑上看一个环，则队列中元素的个数为_(R-F+n)%n。.队列又称为—先进先出 的线性表。.栈结构允许进行删除操作的一端为—栈顶O.已知循环队列的存储空间为数组a[21],且头指针(指向队头元素)和尾指针(队尾元素的下一位置)分别为8和3,则该队列的当前长度为_」6o.在初始为空的队列中插入元素A,B,C,D以后，紧接着做了两次删除操作，此时的队尾元素是_Do.在非空线性表中除第一个元素外，集合中每个数据元素惟独一个—直接前驱;除最后一个元素之外，集合中每个数据元素均只有一个一直接后继.在双向链表中，每一个结点含有两个指针域，一个指向—直接前驱结点，另一个指向—直接后继一结点。.在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对―头指针进行特殊处理。.在一个单链表L中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则应进行的操作序列为：_p-next=q->next;q一〉next二p。.顺序表中逻辑上相邻的元素的物理位置一相邻,单链表中逻辑上相邻的元素的物理位置—不一定相邻。.在以L为头指针的带头结点的单链表和单循环链表中，判断链表是否为空的条件分另IJ 为_L—>next二=NULL和_L—>next——L。.已知一顺序存储的线性表，每一个元素占用k个存储单元，若第一个元素的地址为Loci,则第i个元素的地址为_Locl+(i-l)*ko.若时常需要对线性表进行插入与删除操作，该线性表最好采用—链式存储结构。.若时常需要对线性表进行查找操作，则最好采用—顺序存储结构。.若待散列的序列为(18,25,63,50,42,32,9),散列函数为H(key)=key%9,与18发生冲突的元素有_63,9o.一循环链表链表从任何一个结点出发，都能访问到所有结点。.假定一组数据的关键字为(46,79,56,38,40,84),则以第一个记录为枢轴，对其进行第一趟快速排序的结果为_{40,38,46,56,79,84}。.假定一组数据的关键字为{46,79,56,38,40,84},则利用堆排序方法建立的初始小顶堆为_{38,40,56,79,46,84}o.每次直接或者通过“枢轴”元素间接比较两个元素，若浮现逆序罗列时就交换它们的位置，此种排序方法叫做—交换___排序。.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做一插入排序。.每次从无序表中挑选出一个最大或者最小元素，把它交换到有序表的一端，此种排序方法叫做.选择排序。.每次使两个相邻的有序表合并成一个有序表的排序方法叫做_2路归并排序 排序。.先将整个待排序列分割成若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体进行一次直接插入排序，此种排序方法叫做—希尔__排序。.将一个数据元素(或者记录)的任意序列,重新罗列成一个按关键字有序的序列叫.排序o.元素关键字转换为该元素存储位置的函数f称为—哈希函数—o.数据的逻辑结构包括集合、—线性结构、树形结构和图状结构四种类型。.已知有实现同一功能的两个算法，其时间复杂度分别为0(log2n)和0(n),哪个算法的效率更高？0(log2n).假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1;比较两次查找成功的结点数为2；比较四次查找成功的结点数为8；平均查找长度为3.7.在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找.元素关键字转换为该元素存储位置的函数f称为—哈希函数.若要对某二叉排序树进行遍历，保证输出元素的值序列按增序罗列，应对该二叉排序树采用一中序一遍历法。.通常用时间复杂度和—空间复杂度两种方法衡量算法的技率。.在一个无向图中，所有顶点的度数之和等于所有边数的_2倍。.在无向图中，若从顶点A到顶点B存在一路径，则称A与B之间是连通的。.有一个n个顶点的有向彻底图的弧数—n（n-l）o.对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小为_n2o.已知一棵树的前序序列为ABCDEF,后序序列为CEDFBA,则对该树进行层次遍历得到的序列为ABCDFEo.若一棵彻底二叉树含有121个结点，则该树的深度为_7o.度数为0的结点，即没有子树的结点叫作叶子结点。同一个结点的儿子结点之间互称为兄弟结点1.任何一棵二叉树都有nO=n2+l的关系式。（J）.插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也时常被使用。（义）.在彻底二叉树中，若某结点无左孩子，则它必是叶结点。（V）.用树的前序遍历和中序遍历可以导出树的后序遍历。（X）.已知一棵二叉树的前序序列和后序序列可以惟一地构造出该二叉树。（X）.将一棵树转换成二叉树后，根结点没有左子树。（X）.设与一棵树T所对应的二叉树为BT,则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（义）.满二叉树也是彻底二叉树。（V）.哈夫曼树一定是满二叉树。（X）.树的带权路径长度最小的二叉树中必定没有度为1的结点。（V）.度为二的有序树等价于二叉树。（X）.在一棵二叉树中，假定每一个结点惟独左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。（V）.算法和程序都应具有下面一些特征：输入，输出，确定性，有穷性，可行性。（V）.二叉树是一棵无序树。（X）.数据元素是数据的最小单位。（X）.广义表的表头和表尾既可以是单元素，也可以是广义表。（义）.如果两个串中含有相同的字符，则这两个串相等。（X）.稀疏矩阵压缩存储后，必会失去随机存取功能。（J）.在对双向循环链表做删除一个结点操作时，应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。（V）.惟独用面向对象的计算机语言才干描述数据结构算法。（义）.栈和队列都是顺序存取的线性表，但它们对存取位置的限制不同。（X）.栈和队列都是限制取点的线性结构。（V）.若某堆栈的输入序列为1,2,3,4,则4,3,1,2不可能是堆栈的输出序列之一。（J）.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。（V）.单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。（义）.堆栈、队列和数组的逻辑结构都是线性表结构。（X）.链式栈与顺序栈相比，一个明显的优点是通常不会浮现栈满的情况。（V）.递归的算法简单、易懂、容易编写，而且执行效率也高。（义）.顺序表和一维数组一样，都可以按下标随机（或者直接）访问。（V）.堆排序是所需辅助空间至少的排序。（J）.在采用线性探测法处理冲突的散列表中,所有同义词在表中一定相邻。（义）.对n个元素的表用堆排序法进行排序，时间复杂度是0（log2