数据结构复习内容

数据结构》复习内容一．单选题链栈与顺序栈相比，有一个比较明显的优点是B插入操作更加方便通常不会出现栈满的情况不会出现栈空的情况删除操作更加方便从未排序序列中挑选元素，将其放在已排序序列的一端，这种排序方法称为A选择排序 B.插入排序 C.快速排序 D.冒泡排序若n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵是一个B一般矩阵 B.对称矩阵 C.对角矩阵 D.稀疏矩阵一个n*n的对称矩阵，如果以行或列为主序放入内存，则其容量为Cn*n B.n*n/2 C.(n+1)*n/2 D.(n+1)*(n+1)/2当栈中的元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为Bn-1 B.n C.n+1 D.n/2在单链表中，增加头结点的目的是C使单链表至少有一结点标志表中首结点位置方便运算的实现说明单链表是线性表的链式存储实现TOC\o"1-5"\h\z在一个图中，所有顶点的度数之和等于所有边数的 倍。C1/2 B.1 C.2 D.4下列排序方法中，排序趟数与序列的原始状态有关的方法是D选择排序 B.希尔排序 C.堆排序 D.冒泡排序在一棵具有五层的满二叉数中，结点总数为AA.31 B.32 C.33 D.16线性表是A一个有限序列，可以为空一个有限序列，不能为空一个无限序列，可以为空一个无限序列，不能为空下列排序算法中， 排序在每趟结束后不一定能选出一个元素放到其排好序的最终位置上。CA.选择 B.冒泡 C.归并 D.堆二维数组a的每个元素是由6个字符组成的串，行下标的范围从0到8，列下标的范围从1到10，则存放a至少需要 个字节。DA.90 B.180 C.270 D.540对有14个元素的有序表A[1..14]作二分查找，查找元素A[4]时的被比较元素依次为CA[1],A[2],A[3],A[4]A[1],A[14],A[7],A[4]A[7],A[3],A[5],A[4]A[7],A[5],A[3],A[4]以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中(n>0)，空链域的个数为CA.2n-1 B.n-1 C.n+1 D.2n+1向顺序栈中压入元素时A先移动栈顶指针，后存人元素先存人元素，后移动后移动栈顶指针谁先谁后无关紧要同时进行下列存储形式中，哪一个不是树的存储形式DA.双亲表示法B.孩子链表表示法 C.孩子兄弟表示法 D.顺序存储表示法对n个记录的文件进行堆排序，最坏情况下的执行时间为A.O(logn) B.O(n) C.O(nlogn) D.O(n2)19用链表表示线性表的优点是C 2便于随机存取花费的存储空间比顺序表少便于插入和删除数据元素的物理顺序与逻辑顺序相同20•下列有关线性表的叙述中，正确的是A线性表中的元素之间是线性关系线性表中至少有一个元素线性表中任何一个元素有且仅有一个直接前驱线性表中任何一个元素有且仅有一个直接后继线性表的顺序存储结构中，一般情况下，在第i(lWiWn)个元素之前插入一个元素时，需向后移动()个元素。1n-i+1 ②n-i ③i ④i+1若一个栈的进栈序列为1，2，3，4，则()不可能为一个出栈序列。4①1,2，3，4 ②4,3，2，1 ③3,2，1，4 ④4,2，3，1链队列中，用于判断队列为“空”的条件是()。3①Q.next二Q.front ②Q.front二NIL ③Q.front二Q.rear ④Q.rear二NIL在线性表的存储结构中，能从当前结点出发访问任一点的存储结构是()。4①单链表②双向链表③循环链表④②和③空串是指()。3①由一个或多个空格组成的串 ②串中字符是若干个“空”的串③零个字符的串 ④只有结尾字符的串需要预分较大空间，删除操作时需要移动元素的线性表的存储结构是()。2①单链表 ②顺序表 ③循环链表④静态链表树中结点的()称为树的深度。3①最小层次②平均层次③最大层次④子树层次哈夫曼树或最优二叉树是()最小的二叉树。2①路径长度②带权路径长度③深度④度若采用顺序存储结构存储满二叉树的全部结点，设每一个结点占用2个存储单元，则深度为K的满二叉树共占用()个存储单元。4①2k ②2k+1 ③2k+1 ④2k+1-2下面二叉树中一定是完全二叉树的是()。2①平衡二叉树②满二叉树③单枝二叉树④二叉排序树在n个顶点，e条边的连通图中，连通分量个数为()2①0 ②1 ③n ④e下列排序算法中，不稳定的算法是()。1①快速排序②基数排序③直接插入排序④简单选择排序不需要进行关键字之间比较的排序方法是()。4①简单排序②快速排序③归并排序④基数排序()遍历二叉排序树可得到一个关键字的有序序列。2①前序 ②中序 ③后序 ④随意在数据结构中，从逻辑关系上可以把数据结构分成()3①动态结构和静态结构②紧凑结构和非紧凑结构③线性结构和非线性结构④内部结构和外部结构

对一个满二叉树，m个树叶，n个结点，深度为h,贝1」（）。4@n=h+m ②h+m=2n ③m=h-l ④n=2h-lL是带表头的单向链表的表头指针，该表为空的条件是（ ）。CA、n==0 B、L==null C、L->next==null D、L->next=L设数组申bm-1］中有一循环队列，F,R是队头队尾指针，空队列的条件是（B）A、n=0BA、n=0B、F=RC、F=R-1D、F=R+140.栈上可进行的操作是（C40.栈上可进行的操作是（CA、访问栈的第i个元素C、在栈顶后插入一个元素X）。B、在栈的第i个元素之后插入元素D、删除栈底元素41具有n个顶点的强连通图，其弧条数的最小值为（B）。A、n+1 B、n C、n-1 D、n-242.具有n个顶点的DAG图（有向无环图），其入度为0的的顶点个数至少有（D）。A、n B、n/2 C、n/4 D、143.一个三对角矩阵A 已按行压缩存储到一维数组B中，则B的长度至少是（D■43.一个三对角矩阵A 已按行压缩存储到一维数组B中，则B的长度至少是（D■nXB、3n）。A、3n+1 B、3n C、3n-1首先访问结点的左子树，然后访问该结点①前序遍历栈的特点是（1 ）①先进后出②先进先出在线性表L=（a1，a2，……①直接后继 ②直接前驱双重链表表示线表时，较之单链表更易进行（4①结点的插入 ②结点的删除 ③线性表的扩充快速排序执行一遍后，已经到位的元素个数至少是①1 ②2 ③n④2/n50.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的（4）。②后序遍历③中序遍历D、3n-2最后访问结点的右子树，这种遍历称为（3）④层次遍历③任意进出a）中，a称为a.的n i+1 i③孩子④两断进出（1）。④兄弟）。④对结点的访问）。①先根遍历 ②中根遍历③后根遍历 ④按层遍历带头结点的单链表head为空的判定条件是（2）。①head==NULL ②head->next==NULL③head->next==head ④head!==NULL一个栈的入栈序列是a,b,c,d,e贝栈的不可能的输出序列是（3）。①edcba ②decba ③dceab ④abcde不是串a='ABCABDEABX'的子串是（4 ）。①串b=‘ABC'②串b=‘BX' ③串b=‘AB' ④串b=‘AC'数组通常具有的两种基本操作是（C）A.建立与删除 B.索引和修改 C.查找和修改 D.查找与索引55•设有一个足够大的栈，入栈序列为x,y,z,u,v,下列哪一个出栈序列是不可能序列（A）A、x,v,u,y,z B、z,y,u,v,x C、z,y,u,x,v D、y,z,u,v,x中序遍历和后序遍历所得序列完全相同的二叉树是（C）A、空二叉树 B、所有左儿子域为空C、所有右儿子域均为空 D、儿子域中至少有一个为空对五个不同的数据进行排序，最多需要比较B次。A.8 B.10 C.15 D.25在线性表的存储结构中，能从当前结点出发访问任一点的存储结构是（4）①单链表②双向链表③循环链表④②和③空串是指（3）。①由一个或多个空格组成的串②串中字符是若干个“空”的串

③零个字符的串④只有结尾字符的串在一般树中，结点M、N分别为结点P的第i、第i+1个孩子，则该树转化为二叉树后，结点N为结点M的(2)①左孩子②右孩子③兄弟④双亲顺序存储结构仅适合于(2)。①平衡二叉树②完全二叉树③二叉排序树④单枝二叉树具有n个顶点的强连通图，其弧条数的最小值为(3)。①n(n-l) ①n(n-l) ②呼③n n-1)②活动持续时间最短的活动④源点到汇点路径长度最长的路径上的活动关键活动是(4)。②活动持续时间最短的活动④源点到汇点路径长度最长的路径上的活动(2)遍历二叉排序树可得到一个关键字的有序序列。①前序 ②中序 ③后序 ④随意在堆排序过程中，当初始堆建成后(设堆顶为最小)，初始堆满足(3)。①前序遍历结果有序②中序遍历结果有序③任一结点的关键字均小于等于它的儿子的关键字④任一结点的关键字均小于它左儿子的关键字，大于等于它右儿子的关键字在数据结构中，从逻辑关系上可以把数据结构分成(3)①动态结构和静态结构②紧凑结构和非紧凑结构③线性结构和非线性结构④内部结构和外部结构对采用二分查找法进行查找运算的查找表，要求按(3)方式进行存储①顺序存储链式存储①顺序存储链式存储顺序存储且结点按关键字有序④链式存储且结点按关键字有序69．若要在一棵完全二叉村中寻找任意结点的双亲，则最佳存储方案为(B)。A、A、带有双亲信息的三叉链表B、顺序存储C、二叉链表DC、二叉链表70.在下面各种链表结构中，能在0(1)时间内完成在指定结点P之前搜入元素X的结构是(D)。A、单链表B、单向循环链表 C、带表头的单链表 D、双向循环链表二判断正误题(正确的在题后的括号内划“丿,错误的划“X”)由于栈只能在栈顶进行插入或删除操作，所以栈不是线性表。()Xn个结点有向图，若它有n(n-1)条边，则它一定是强连通的。()X邻接矩阵存储图时所需存储空间大小与图的结点数有关，而与边数无关。()n个结点的树的各结点度数之和为n-1。()所谓冲突即是两个关键字的值相同的元素，其哈希地址相同。()任何有向无环图都存在一个唯一的拓扑序列。()X二叉树是树的一种特殊情况。()X在用线性探查法解决冲突所构造的散列表中，每组同义词中至少有一个元的地址正好等于其散列地址。()X线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。()X二叉树中任何一个结点的度都是2。()X用直接选择排序方法分别对序列S1= (1，2,3, 4, 5, 6, 7)和序列S2=(