《数据结构》综合练习

1、综合练习、单项选择题数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C ）。存储结构B.逻辑结构C.链式存储结构D.顺序存储结构设语句X+的时间是单位时间，则以下语句的时间复杂度为（B ）。for（i=1; i=n; i+）for（j=i; j=n; j+）x+;A.0(1)2B.O( n)3C.0(n)D.0( n)链式存储结构的最大优点是（D）o便于随机存取B.存储密度高C.无需预分配空间D.便于进行插入和删除操作假设在顺序表a,ai,an-i中，每一个数据元素所占的存储单元的数目为4,且第0个数据元素的存储地址为100,则第7个数据元素的存储地址是（ D ）o106 B.

2、 107C.124D.128在线性表中若经常要存取第顺序表C.不带头结点的单链表i个数据元素及其前趋，则宜采用（带头结点的单链表D.循环单链表A ）存储方式。在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（C ）存储方式。顺序表B.用头指针标识的循环单链表用尾指针标识的循环单链表D.双向链表在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是（C ）oO（1） B. O（log 2n） C. O（n） D. O（n2）要将一个顺序表a 0,a 1,a n-1中第i个数据元素ai（0 i n-1）删除，需要移动（B ） 个数据

3、元素。A.i B. n-i-1C. n-i D. n-i+1在栈中存取数据的原则是（B ）oA.先进先出B.先进后出C.后进后出D.没有限制若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（D ）oA . 1234 B.1324 C.4321 D.1423A .需要判断栈是否满C.需要判断栈元素的类型12.在顺序栈中，若栈顶指针在链栈中，进行出栈操作时（ B ）o需要判断栈是否为空无需对栈作任何差别top指向栈顶元素的存储单元，且顺序栈的最大容量是maxSize,则顺序栈的判空条件是（B）A . top=0 B.top=-1 C. top=maxSize D.top=maxSize-1

4、在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（C ）。A . top=0 B.top=-1 C. top=maxSize D.top=maxSize-1在队列中存取数据元素的原则是（ A ）。A .先进先出B.先进后出后进后出D.没有限制在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储 单元，队列的最大存储容量为maxSize，则队列的判空条件是（A ）。A. front=rearB. front!=rearC.

5、fron t=rear+1D. fron t=（rear+1）% maxSize在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储 单元，队列的最大存储容量为maxSize，则队列的判满条件是（D ）。A. front=rearB. front!=rearC. fron t=rear+1D. fron t=（rear+1）% maxSize在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件， front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的

6、下一个存储 单元，队列的最大存储容量为maxSize，则队列的长度是（ C ）。A. rear-frontrear-fr on t+1（rear-fro nt+maxSize）%maxSize D. （rear-fro nt+1）%maxSize设长度为n的链队列采用单循环链表加以表示，若只设一个头指针指向队首元素，贝U入队操作的时间复杂度为（B ）。A . 0（1）B. 0（n）C. O（log 2n）D . O（n2）串的长度是指（A ）A.串中包含的字符个数B.串中包含的不同字符个数C.串中除空格以外的字符个数D.串中包含的不同字母个数设有两个串p和q，其中q是p的子串，求q在p中首次出

7、现的位置的算法称为（C ）A .求子串B .联接C.模式匹配D .求串长设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主进行存储，an为第一元素，其存储地址为1,每个元素占一个地址空间，则ass的地址为（B ）。A. 13B.33C. 18D.407.有一个二维数组 A1.6, 0.7，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ D）个字节。A. 48B. 96C. 252D. 288在哈夫曼树中，任何一个结点它的度都是（ C ）。A.0 或 1 B. 1或 2 C. 0 或 2 D. 0或 1 或 224.对一棵深度为h的二叉树，其结点的个

8、数最多为（D ）。A.2hB. 2h-1C. 2D. 2-1C.只有一个根结点D.任意一棵二叉树25.假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3,则这棵二叉树的叶结点的个数是（C ）A.2B. 3C. 4D. 526.若某棵二叉树的先根遍历序列为ABCDEF中根遍历序列为CBDAEF则这棵二叉树的后根遍历序列为（B ）。A. FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。A . n-1 B. n C. n+1 D. 0利用二叉链表存储树，则根结点的右指针是（C ）。A.指向最左孩子B.指

9、向最右孩子C .空 D .非空引入二叉线索树的目的是（ A ）。A.加快查找结点的前驱或后继的速度B .为了能在二叉树中方便的进行插入与删除C.为了能方便的找到双亲D.使二叉树的遍历结果唯一设F是一个森林，B是由F变换得的二叉树。若 F中有n个非终端结点，则 B中右指针 域为空的结点有（C）个。A. n-1B. nC. n + 1D. n + 2在一个有-个顶点的有向图中，若所有顶点的出度之和为I，则所有顶点的入度之和为 （A）。A. B.-C.； - -D.具有6个顶点的无向图至少应有（ A ）条边才能确保是一个连通图。 TOC o 1-5 h z A.5B.6C.7D.8个有n个顶点的无向

10、图最多有（C ）条边。疚沖一i；C.浙:忌D.-n个顶点的连通图用邻接距阵表示时，该距阵至少有（B ）个非零元素。A . nB . 2（n-1）C. n/2D. n2对某个无向图的邻接矩阵来说，下列叙述正确的是（ A ）。第：行上的非零元素个数和第：列上的非零元素个数一定相等矩阵中的非零元素个数等于图中的边数第:行与第：列上的非零元素的总数等于顶点.的度数矩阵中非全零行的行数等于图中的顶点数.32.任何一个无向连通图的最小生成树（ B ）。A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在下面（B ）方法可以判断出一个有向图是否有环。A .深度优先遍历B .拓扑排序C .求最短路径D .

11、求关键路径对线性表进行二分查找时，要求线性表必须（B ）A. 以顺序方式存储 B.以顺序方式存储，且结点按关键字值有序排列以链接方式存储 D.以链接方式存储，且结点按关键字值有序排列38.用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比较次数是2A.O(n ) B.O( nlog2n) C.O( n) D.O(log2n)若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较（B ） 次。A.9B.7C.5D.3若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（D ）A.顺序存储结构B.链式存储结构C.索引存储结构D.散列存储结构设哈

12、希表长为14，哈希函数是H（key）=key%11 ,表中已有数据的关键字为15，38, 61,84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（D ）。A . 8B . 3C. 5D. 942下面给出的四种排序算法中，（B ）是不稳定的排序。A 插入排序B 堆排序C.二路归并排序D 冒泡排序43在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（D ）。A .直接插入排序B .冒泡排序C.快速排序D .直接选择排序关键字序列（8, 9, 10, 4, 5, 6, 20, 1 , 2）只能是下列排序算法中（C ）的两趟排序 后的结果。A 选择排序B.冒

13、泡排序C.插入排序D.堆排序 组记录的关键字为（46, 79, 56, 38, 40, 84）,则利用快速排序的方法，以第一个记 录为支点得到的一次划分结果为（ C ）。A . （38,40,46,56,79,84）B . （40,38,46,79,56,84）C. （40,38,46,56,79,84）D . （40,38,46,84,56,79） 在对一组关键字序列15 , 33,55, 100, 65, 50, 40, 95，进行直接插入排序时，把65 插入，需要比较（A ）次。A. 2B. 4C. 6D. 8从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为 （B ）

14、。A.希尔排序B.直接选择排序C.冒泡排序D.快速排序当待排序序列基本有序时，以下排序方法中，（B ）最不利于其优势的发挥。A.直接选择排序B.快速排序C.冒泡排序D.直接插入排序在待排序序列局部有序时，效率最高的排序算法是（B ）。A.直接选择排序B.直接插入排序C.快速排序D.归并排序50.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（D ）算法最节省时间。A .冒泡排序B .快速排序C.简单选择排序D .堆排序二、填空题一个串的任意连续字符组成的子序列称为串的子串，该串称为 主串 TOC o 1-5 h z 若两个串的长度相等且对应位置上的字符也相等，则称两个串

15、相等。寻找子串在主串中的位置，称为模式匹配。其中，子串又称为模式串 。设数组A1.5,1.6 的基地址为1000 ,每个元素占5个存储单元，若以行序为主序顺序存储，则元素 A5,5的存储地址为1140。一个n x n的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为n（n+1）/2。对矩阵压缩的目的是为了节省存储空间。循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的 求模（或取余）运算来实现的。50 。一棵具有100个结点的完全二叉树，其叶结点的个数为 TOC o 1-5 h z 以5 , 9, 12, 13, 20,

16、 30为叶结点的权值所构造的哈夫曼树的带权路径长度是217有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。若一棵完全二叉树的第 4层(根结点在第0层)有7个结点，则这棵完全二叉树的叶子结点总数是11。在深度为k的完全二叉树中至少有丄个结点，至多有2角个结点。假定待查找记录个数为n,则在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为(n +1)/2;在查找失败情况下的平均查找长度为n+1。对线性表进行二分查找时，要求线性表必须以顺。分块查找分为两个阶段，分和 在块内查找待查的元素。哈希法存储中，冲突指的是不同关键字值对应到相同的存储地址。一棵二叉排序树用中序遍历输出的信息是递增 序

17、列。哈希法存储的基本思想是根据关键字来决定存储地址。若用.表示图中顶点数，则有畑现注 条边的无向图称为完全图。个顶点的连通无向图至少有 条边，至多有 : 条边。若有向图的邻接矩阵为： TOC o 1-5 h z /01C1010 11191011aooo10100/则顶点，的入度是3对于一个有向图，若一个顶点的度为-，出度为二，则对应逆邻接表中该顶点单链表中的边结点数为_- 。在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。执行排序操作时，根据使用的存储器可将排序算法分为内排序 和 外排序 。在对一组记录序列50,40,95,20,15,70,60,45,80进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较3 次。在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用直接插入排序。在对一组记录序列50,40,95,20,15,70,60,45,80进行直接选择排序时，第4次交换和选择后，未排序记录为 50,