数据结构练习附答案

一、单项选择题逻辑关系是指数据元素间的()A•类型B.存储方式 C•结构D.数据项对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为()A•顺序表 B.用头指针表示的单循环链表C.用尾指针表示的单循环链表D.单链表设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为( )A．front=front+1 B．front=(front+1)%(m-1)C．front=(front-1)%m D．front=(front+1)%m在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为()。A．rear％n==frontB．(front+l)％n==rear在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为()。A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front已知一颗二叉树上有92个叶子结点，则它有 个度为2的结点。()A.90B.91C.92D.93在一棵非空二叉树的中序遍历序列中，根结点的右边 。A.只有右子树上的所有结点 B.只有右子树上的部分结点C.只有左子树上的所有结点 D.只有左子树上的部分结点有n条边的无向图的邻接表存储法中，链表中结点的个数是()个＜A.n B.2n C.n/2 D.n*n判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用( )。A.求关键路径的方法 B•求最短路径的方法C.深度优先遍历算法 D•广度优先遍历算法对线性表进行二分查找时，要求线性表必须()。A•键值有序的顺序表 B•键值有序的链接表C•链接表但键值不一定有序 D•顺序表但键值不一定有序第2页共14页A.O(1) B.O(n)C.O(log2n)D.O(n2)12.若某线性表的常用操作是取第个元素及其前趋元素，则采用()存储方式最节省时间？A•顺序表 B•单链表C.双链表D•单向循环在一个单链表HL中，若要向q所指结点之后插入一个由指针p指向的结点，则执行()A．HL=p;p->next=HL B．p->next=HL;HL=pC．p->next=q->next;q->next=pD．p->next=q->next;q=p>next栈和队列是两种特殊的线性表，只能在它们的()处添加或删除结点。A.中间点 B•端点 C•随机存取点 D•结点一个栈的输入序列为1，2，3，4，5，则下列序列中不可能是站的输出序列的是___A.2,3,4,1,5 B.5,4,1,3,2C.2,3,1,4,5 D.1,5,4,3,2广义表((a),a)的表尾是。()A.a B.A C.(a) D.((a))将含100个结点的完全二叉树从根这一层开始，每层从左至右依次对结点编号，根结点的编号为1。编号为47的结点X的双亲的编号为()A.24 B.25 C.23 D.无法确定有n个顶点的无向图的邻接矩阵是用 数组存储。A.n行n列B—维 C.任意行n列D.n行任意列有一个有序表｛1，4，6，10，18，35，42，53，67，71，78，84，92，99｝，当用二分查找法查找键值为84的结点时，经 比较后查找成功。A.2 B.3 C.4 D.12在一个带有附加表头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，贝g执行( )A.HL=p;p->next=HL; B.p->next=HL->next;HL->next=p;C.p->next=HL;p=HL; D.p->next=HL;HL=p;若采用单链表表示循环队列，则应该选用（）A.带尾指针的非循环链表 B.带尾指针的循环链表C.带头指针的非循环链表 D.带头指针的循环链表栈和队列是两种特殊的线性表，只能在它们的 处添加或删除结点。（）A.中间点B.端点C.随机存取点D.结点首先访问结点的左子树，然后访问该结点，最后访问结点的右子树这种遍历称为（ ）A•前序遍历 B•后序遍历 C•中序遍历 D•层次遍历树最适合用来表示（）A.有序数据元素 B.无序数据元素C.元素之间具有分支层次关系的数据 D•元素之间无联系的数据已知一颗二叉树上有92个叶子结点，则它有 个度为2的结点。（）A.90 B.91 C.92 D.93对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是（ ）A、小于 B、大于 C、等于 D、不小于28.对关键字序列19，11，27，18，33进行快速排序，则要进行多少次

第5页共14页A.5次B.6次C.7次D.8次设有一个二维数组A[m][n],假设A[0][0]存放位置在644(io),A[2][2]存放位置在676，每个元素占一个空间，问A⑶⑶存放在什么位TOC\o"1-5"\h\z(1o) (1o)置？脚注(10)表示用10进制表示。(C)A.688 B.678 C.692 D.696设有6个结点的无向图，该图至少应该有(A )条边才能确保是一个连通图。A.5 B.6 C.7 D.8根据二叉树的定义可知二叉树共有(B)种不同的形态。A.4 B.5 C.6 D.7假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为(B)个。A．15 B．16 C．17 D．47任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序(A)。A•不发生改变 B•发生改变C•不能确定 D•以上都不对在一个具有n个顶点的无向完全图中，所含的边数为(C)。若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)},则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为(B)。A．A,B,C,F,D,EB．A,C,F,D,E,BC．A,B,D,C,F,ED．A,B,D,F,E,C8.假定对元素序列(7,3,5,9,1,12)进行堆排序，采用小顶堆，则初始数据构成的初始堆为(B)。A．1,3,5,7,9,12 B．1,3,5,9,7,12C．1,7,3,5,9,12 D．1,3,5,7,9,12二、填空题TOC\o"1-5"\h\z1.根据值的不同特性，高级程序语言中的数据类型可分为两类： 和线性表有两种存储结构： 和 。在以HL为表头指针的循环单链表中，链表为空的条件为 。设栈S和队列Q的初始状态皆为空，元素a1,a2,a3,a4,a5和a6—次通过一个栈后即进入队列Q,若6个元素出对的顺序是a3,a5,a4,a6,a2,a1，则栈S至少可以容纳 个元素。对于—棵具有30个结点的二叉树，若—个结点的编号为5，则它的左孩子结点的编号为 ，右孩子结点的编号为 ，双亲结点的编号为 。对于一个具有n个结点的二叉树，当它存储在二叉链表中时，其指针字段的总数为 个，其中 个用于链接孩子结点， 个空闲。设图中有n个顶点，e条边，则含有e二— —条边的无向图称作完全图，含有e= 条弧的有向图称作有向完全图。对于线性表(7&4，56，30，65)进行哈希存储时，若选用H(K)二K%5作为哈希函数，则哈希地址为0的元素有 个。TOC\o"1-5"\h\z在单链表上难以实现的排序方法有 和 。根据值的不同特性，高级程序语言中的数据类型可分为两类： 和在单链表中，删除指针P所指节点的后继结点的语句是 。栈又称为 的线性表，队列又称为 的线性表。N个结点的二叉树采用二叉链表存放，共有空链域个数为 。一棵深度为k的满二叉树的结点总数为 ，一棵深度为k的完全二叉树的结点总数的最小值为 ，最大值为 。具有80个结点的完全二叉树，若按层次从上到下、从左到右对其编号（根结点为1号），则编号最大的分支结点序号为 ，编号最小的分支结点序号为 ，编号最大的叶子结点序号为 ，编号最小的叶子结点序号为 。采用二分法进行查找的查找表，应选择 的存储结构。假设在有序表A[0…19]中进行二分查找，比较二次查找成功的结点数为 ，比较三次查找成功的结点数为 。—个有向图G中若有弧＜Vj,Vi＞、＜Vi,Vk＞和＜Vj,Vk＞，则在图G的拓朴序列中，顶点Vi,Vj和Vk的相对位置为 。对于—个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为 ，在表尾插入元素的时间复杂度为 。栈又称为 的线性表，队列又称为 的线性表。对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为 个，其中 个指针是空闲的。在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 为主序、 为辅序的次序排列。—颗深度为K且有 个结点的二叉树称为满二叉树。若对—棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到—维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[i]元素的左孩子元素为 ，双亲元素为 。25•对于线性表（7&4，56，30，65）进行哈希存储时，若选用H（K）=K%5作为哈希函数，则哈希地址为0的元素有 个，哈希地址为4的有 个。26.以折半查找方法从长度为8的有序表中查找—个元素时，平均查找长度为27.假定—个有向图的顶点集为{a,b,c,d,e,f}，边集{＜a,c＞,＜a,e＞,＜c,f＞,＜d,c＞,＜e,b＞,＜e,d＞},则出度为0的顶点个数为 ，入度为1的顶点个数为 。28•设有向图G中有向边的集合E={＜1，2＞，＜2，3＞，＜1，4＞，＜4，2＞，＜4,第8页共14页TOC\o"1-5"\h\z3＞｝，则该图的一种拓扑序列为 。对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为2n个，其中 个用于链接孩子结点， 个空闲着。设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于 。根据初始关键字序列（19，22，01，38，10）建立的二叉排序树的高度为 。32.三．应用题顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？回文。假设一字符序列已存入计算机，请分析用线性表、堆栈和队列等方式正确输出其回文的可能性？假设正读和反读都相同的字符序列为"回文”，例如，‘abba'和‘abcba'是回文，‘abcde'和‘ababab'则不是。设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。至少有14种。全进之后再出情况，只有1种：4，3，2，1进3个之后再出的情况，有3种，3,4,2,13,2,4,13,2,1,4进2个之后再出的情况，有5种，2,4,3,12,3,4,1 2,1,3,42,1,4,32,1,3,4进1个之后再出的情况，有5种，1,4,3,21,3,2,41,3,4,21,2,3,41,2,4,34.对给定的权值｛2,3,4,7,8,9｝，构造出相应的赫夫曼树，并求出带权路径的长度WPL。

33159952183315995218WPL=2*4+3*4+4*3+9*2+7*2+8*2=805.对于下图的无向图，绘出从a出发，用普利姆算法构造的最小生成树的过程。过程略）6.请画出右图的邻接矩阵和邻接表6.请画出右图的邻接矩阵和邻接表01110101011101110101011101 1 22卄3一►】——•4-H1□rH5\.pKL >7.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？在什么情况下用链表比顺序表好？①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（岂？），存储空间利用率高。缺点：插入或删除元素时不方便。②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。顺序表适宜于做查找这样的静态操作；链表宜于做插△、删除这样的动态操作。若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。8.按照下列给定二叉树的先序遍历序列、中序遍历序列和后序遍历序第11页共14页

列，分别构造出二叉树。先序遍历序列：EBADCFHGIKJ中序遍历序列：ABCDEFGHIJK中序遍历序列：ACBGEDF 后序遍历序列：ABCDEFG9.EBADGCJ1KGCAB如下列所示的连通图，请画出：1）以顶点a9.EBADGCJ1KGCAB如下列所示的连通图，请画出：1）以顶点a为根的深度优先生成树；10.给定表{19