数据结构(同名10800)

《数据结构(同名10800)》由会员分享，可在线阅读，更多相关《数据结构(同名10800)（15页珍藏版）》请在金锄头文库上搜索。

1、数据结构综合复习资料一、填空题1. 数据结构是（ ）。2. 堆栈的特点是（ ） ，队列的特点是（ ），字符串中的数据元素为（ ）。3. 列举三种树的存储方式（ ）、（ ）和（ ）。4. 哈希表查找技术的性能取决于三个因素，它们是（ ）、（ ）和（ ）。5. ADT称为抽象数据类型，它是指（ ）。6. 求下列程序的时间复杂度，并用大O表示方法表示（ ）。for( i=1 ; i=n ; + + i)for( j=1 ; j=i; + + j ) +x;aij = x;7.用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（ ）。8.含零个字符的串称为（ ）串，用表示。其他串

2、称为（ ）串。任何串中所含字符的个数称为该串的（ ）。9.设有字母序列Q,D,F,X,A,P,N,B,Y,M,C,W，请写出按2路归并排序方法对该序列进行一趟排序后的结果（ ）。10.数据的逻辑结构被分为（ ）、（ ）、（ ）和（ ）四种。11.算法设计的评价标准为（ ）、（ ）、（ ）、（ ）。12.在线性表的单链接存储中，若一个元素所在结点的地址为p， 则其后继结点的地址为（ ），若假定p为一个数组a中的下标，则其后继结点的下标为（ ）。13.（ ）通常称作串的模式匹配。在一个主串中查找子串是否存在，存在返回（ ）；不存在返回( )。14.在一棵二叉树中，第5层上的结点数最多为（ ）；在一

3、棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为（ ）个。15.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵、邻接表表示时，求任一顶点度数的时间复杂度依次为（ ）、（ ）。16.给出一组关键字序列29，18，25，47，58，12，15，10，增量为4的希尔（SHELL）排序结果为（ ）。17.数据结构的四种基本形式为集合、（ ）、（ ）和（ ）。18.线性表的常见链式存储结构有（ ）、（ ）和（ ）。19.设T是一个m*n阶矩阵，T按列序存储在一组连续的存储单元中，每个元素占用w个存储单元，若T1,1的存储地址为base，则Ti,j的存储地址为（ ）。20.

4、在邻接表上，无向图中顶点vi的度恰为（ ）。对有向图，顶点vi的出度是（ ）。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的值为（ ）的结点的个数是顶点vi的入度。21.一般情况下，当待排序序列关键字是随机情况时，快速分类是所有数量级（ ）的排序方法中最好的。对快速排序来讲，其最好情况下的时间复杂度是（ ），其最坏情况下的时间复杂度是（ ）。22.以下为冒泡排序的算法。请分析算法，并在_上填充适当的语句。 void bulbblesort(int n,list r) int i, j, flag; /*flag为特征位*/for(i=1;i=n;i+) _ _;for(j=1;

5、_;j+) if(rj+1.keyrj.key) ; p=rj; rj=rj+1; rj+1=p; if(flag) return ;二、选择题1、关于算法，下面描述正确的是（ ）。A、时间复杂度就是算法的执行时间B、算法必须有输入量和输出量C、算法就是程序D、时间复杂度仅反映算法运行时间关于问题规模的增长率2、若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表3、以下说法错误的是（ ）。 A、对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表。B、对单链表来说，只有从头结点开始才

6、能扫描表中全部结点。C、双链表的特点是找结点的前趋和后继都很容易。D、对双链表来说，某个结点的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。4、一个堆栈的入栈序列为abcde，若出栈和入栈操作可间隔进行，则出栈序列不可能的为（ ）。A、edcba B、decba C、decab D、 abcde5、 设定树根的层次为1，则有64个结点的完全二叉树的深度为（ ）。 A、8 B、 7 C、 6 D、 5 6、在二叉树的先序遍历，中序遍历和后序遍历算法中，所有叶子结点的先后顺序（ ）。 A、都不相同B、前序遍历和中序遍历相同，而与后序遍历不同 C、完全相同D、前序遍历

7、和后序遍历相同，而与中序遍历不同7、关于逻辑结构和存储结构，正确的描述是（ ）。A、线性数据结构必须采用链式存储结构B、一种逻辑结构，可以用不同的存储结构来存储，反之亦然C、一种逻辑结构，可以用不同的存储结构来存储，反之不然D、一种存储结构只能表示一种逻辑结构8、关于链表的特点描述不正确的是（ ）。A、存储空间不一定连续；B、元素之间的后继关系是由指针来体现的；C、逻辑上相邻，物理上不一定相邻；D、随机存取（顺序存取），即访问任何一个元素的时间相同。9、树最适合用来表示（ ）。A、元素之间具有分支层次关系的数据 B、无序数据元素 C、有序数据元素 D、元素之间无联系的数据 10、下列说法不正确

8、的是（ ）。A、图的遍历是从给定的源点出发每一个顶点仅被访问一次B、图的深度遍历不适用于有向图C、遍历的基本算法有两种：深度遍历和广度遍历D、图的深度遍历是一个递归过程11、在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是（ ）。A、快速排序 B、堆排序 C、归并排序 D、基数排序12、下程序段的时间复杂度为（ ）。for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai，j=x; A、O（1） B、O（n） C、O（） D、O（）13、设矩阵A是一对称矩阵(aij=aji, 1=i,j=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按

9、行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（ ）。A、1031 B、1093 C、1096 D、103214、已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于（ ）。A、1.0 B、2.9 C、3.4 D、5.515、已给下图，哪一项是该图的拓扑排序？（ ）。51234A、1，2，3，4，5 B、1，3，2，4，5C、1，2，4，3，5 D、1，2，3，5，416、以下说法错误的是（ ）。A、散列法存储的基本思想是由关键码的值决定数据的存储地址。B、散列表的结点中只包含数据元素自身的信息，不包含任何指针。C、装填

10、因子是散列法的一个重要参数，它反映散列表的装填程度。D、散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。17、以下说法正确的是（ ）。A、平衡二叉树一定是满二叉树。B、虽然关键字序列的顺序不一样，但依次生成的二叉排序树是一样的。C、在二叉排序树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变为非空即可。D、在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指针域置空即可。18、以下判断不正确的是（ ）。A、顺序存储的线性表可随机存取。B、同一线性表中的数据元素应具有相同的特性。C、顺序存储方式的优点是存储密度大，插入、删除操效率

11、高。D、在线性表的链式存储结构中，逻辑上相邻的数据元素在物理位置上不一定相邻。19、下列判断正确的是（ ）。A、如果两个串含有相同的字符，则这两个串相等。B、数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。C、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每一块中元素个数有关。D、对任意图，从它的某个顶点出发，进行一次深度优先或广度优先搜索，即可访问图的每个顶点。20、对广义表L=(a,b),c,d)进行操作tail (head (L)的结果是（ ）。A、 (c,d ) B、 (d) C、 b D、 (b)21、下列说法正确的是(

12、 )。A、树的先根遍历序列与其对应的二叉树的先根遍历序列相同B、树的先根遍历序列与其对应的二叉树的后根遍历序列相同C、树的后根遍历序列与其对应的二叉树的先根遍历序列相同D、树的后根遍历序列与其对应的二叉树的后根遍历序列相同22、以下说法错误的是（ ）。A、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关。B、邻接表法只能用于有向图的存储，而邻接矩阵法对于有向图和无向图的存储都适用。C、存储无向图的邻接矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分即可。D、用邻接矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径

13、相连，则只要检查A的第 i行第j列的元素是否为0即可。23、希尔排序属于（ ）。A、插入排序 B、选择排序 C、归并排序 D、交换排序三、基本技能测试题1、已知一任意关键字序列 19, 14, 22, 01, 66, 21, 83, 27, 56, 13，按元素在序列中的次序构造一棵平衡二叉树，给出构造过程（当有调整时给出调整后的平衡二叉树）并求查找成功的平均查找长度。2、有待排序的元素序列72，13，70，23，95，16，5，68，26，45，请用快速排序的方法对上述序列排序，给出每一趟排序后的结果。 3、画出下图的邻接表存储结构示意图，并根据邻接表存储结构示意图求出图的深度优先遍历序列和广度优先遍历序列。 4、学习数据结构的目的是什么？5、已知二叉树的先序序列为ABDEGCFHIJ，中序序列为DBGEAHFIJC，画出这个二叉树。6、已知字符A、B、C、D、E、F的使用频率分别为9、15、32、22、18、4，