《数据结构》综合练习共7页.doc

《《数据结构》综合练习共7页.doc》由会员分享，可在线阅读，更多相关《《数据结构》综合练习共7页.doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、如有侵权，请联系网站删除，仅供学习与交流数据结构综合练习【精品文档】第 7 页综合练习一、单项选择题1. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C ）。 A.存储结构B.逻辑结构 C.链式存储结构D.顺序存储结构2. 设语句x+的时间是单位时间，则以下语句的时间复杂度为（ B ）。for(i=1; i=n; i+) for(j=i; j=n; j+) x+; A.O(1)B.O()C.O(n)D.O()3. 链式存储结构的最大优点是（ D ）。 A.便于随机存取B.存储密度高 C.无需预分配空间D.便于进行插入和删除操作 4. 假设在顺序表a0,a1,an1中，每一个

2、数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，则第7个数据元素的存储地址是（ D ）。 A.106 B. 107 C.124 D.1285. 在线性表中若经常要存取第i个数据元素及其前趋，则宜采用（ A ）存储方式。 A.顺序表B. 带头结点的单链表 C.不带头结点的单链表D. 循环单链表6. 在链表中若经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，则宜采用（ C ）存储方式。 A.顺序表B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表D. 双向链表7. 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度

3、是（ C ）。 O(1) B. O(log2n) C. O(n) D. O(n2)8. 要将一个顺序表a0,a1,an-1中第i个数据元素ai(0in-1)删除，需要移动（ B ）个数据元素。 A.i B. n-i-1 C. n-i D. n-i+19. 在栈中存取数据的原则是（ B ）。 A.先进先出 B. 先进后出 C. 后进后出 D. 没有限制10. 若将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ D ）。 A1234 B. 1324 C. 4321 D. 142311. 在链栈中，进行出栈操作时（ B ）。 A需要判断栈是否满 B. 需要判断栈是否为空 C. 需要判断栈元素

4、的类型 D. 无需对栈作任何差别12. 在顺序栈中，若栈顶指针top指向栈顶元素的存储单元，且顺序栈的最大容量是maxSize，则顺序栈的判空条件是（B）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-113. 在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。则顺序栈的判满的条件是（C ）。 Atop=0 B.top=-1 C. top=maxSize D.top=maxSize-114. 在队列中存取数据元素的原则是（ A ）。 A先进先出 B. 先进后出 C. 后进后出 D. 没有限制15. 在循环

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

6、）。 Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize17. 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满和判空的条件，front和rear分别为队首和队尾指针，它们分别指向队首元素和队尾元素的下一个存储单元，队列的最大存储容量为maxSize，则队列的长度是（ C ）。 Arear-front B. rear-front+1 C. (rear-front+maxSize)%maxSize D. (rear-front+1)%maxSize18. 设长度为n的链队列采用单循环链表加以表示，

7、若只设一个头指针指向队首元素，则入队操作的时间复杂度为（ B ）。 AO(1) BO(n) CO(log2n) DO(n2)19. 串的长度是指( A ) A. 串中包含的字符个数 B. 串中包含的不同字符个数 C. 串中除空格以外的字符个数 D. 串中包含的不同字母个数20. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ C ） A求子串 B联接 C模式匹配 D求串长21. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B ）。A. 13 B. 33 C. 18 D.

8、 4022. 7. 有一个二维数组A1.6, 0.7 ，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ D ）个字节。 A. 48 B. 96 C. 252 D. 28823. 在哈夫曼树中，任何一个结点它的度都是（ C ）。 A.0或1 B. 1或2 C. 0或2 D. 0或1或224. 对一棵深度为h的二叉树，其结点的个数最多为（ D ）。 A.2h B. 2h-1 C. 2h-1 D. 2h-1 C. 只有一个根结点 D. 任意一棵二叉树25. 假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ C ） A2

9、 B. 3 C. 4 D. 526. 若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ B ）。 A. FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA27. 在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。 An-1 B. n C. n+1 D. 028. 利用二叉链表存储树，则根结点的右指针是（ C ）。A 指向最左孩子 B指向最右孩子 C空 D非空29. 引入二叉线索树的目的是（ A ）。A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的

10、遍历结果唯一30.设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有（ C）个。An1BnCn + 1Dn + 231.在一个有个顶点的有向图中，若所有顶点的出度之和为，则所有顶点的入度之和为（A）。 A.B.C.D.32.具有6个顶点的无向图至少应有（A）条边才能确保是一个连通图。 A.5B.6C.7D.833.一个有n个顶点的无向图最多有（C）条边。 A.B.C.D.34.n个顶点的连通图用邻接距阵表示时，该距阵至少有（ B ）个非零元素。An B2(n-1) Cn/2 Dn2 35.对某个无向图的邻接矩阵来说，下列叙述正确的是（A）。 A.第行上的

11、非零元素个数和第列上的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第行与第列上的非零元素的总数等于顶点的度数 D.矩阵中非全零行的行数等于图中的顶点数 .32.任何一个无向连通图的最小生成树（B）。 A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在36.下面（ B ）方法可以判断出一个有向图是否有环。 A 深度优先遍历 B拓扑排序 C求最短路径 D求关键路径37.对线性表进行二分查找时，要求线性表必须( B ) A.以顺序方式存储 B.以顺序方式存储，且结点按关键字值有序排列 C.以链接方式存储 D.以链接方式存储，且结点按关键字值有序排列38.用二分查找法查找具

12、有n个结点的顺序表时，查找每个结点的平均比较次数是( D ) A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)39.若有一个长度为64的有序表，现用二分查找方法查找某一记录，则查找不成功，最多需要比较( B )次。 A.9 B.7 C.5 D.340.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( D ) A.顺序存储结构 B.链式存储结构 C.索引存储结构 D.散列存储结构41. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则

13、放入的位置是（ D ）。 A8 B3 C5 D9 42.下面给出的四种排序算法中，( B )是不稳定的排序。 A插入排序 B堆排序 C二路归并排序 D冒泡排序43.在下列排序算法中，哪一种算法的时间复杂度与初始排序序列无关（ D ）。 A直接插入排序 B冒泡排序 C快速排序 D直接选择排序44. 关键字序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中( C )的两趟排序后的结果。A选择排序 B.冒泡排序 C.插入排序 D.堆排序45.一组记录的关键字为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为支点得到的一次划分结果为（ C ）。 A(38,4

14、0,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)46.在对一组关键字序列15，33,55，100，65，50，40，95，进行直接插入排序时，把65插入，需要比较( A )次。 A. 2 B. 4 C. 6 D. 847.从待排序的序列中选出关键字值最大的记录放到有序序列中，该排序方法称为( B )。 A. 希尔排序 B. 直接选择排序 C. 冒泡排序 D. 快速排序48.当待排序序列基本有序时，以下排序方法中，( B )最不利于其优势的发挥。 A. 直接选择排序 B. 快速排序 C.冒泡排

15、序 D.直接插入排序49.在待排序序列局部有序时，效率最高的排序算法是( B )。 A. 直接选择排序 B. 直接插入排序 C. 快速排序 D.归并排序50.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用( D )算法最节省时间。A冒泡排序 B快速排序 C简单选择排序 D堆排序二、填空题1. 一个串的任意连续字符组成的子序列称为串的 子串 ，该串称为 主串 。2. 若两个串的长度相等且对应位置上的字符也相等，则称两个串 相等 。3. 寻找子串在主串中的位置，称为 模式匹配 。其中，子串又称为 模式串 。4. 设数组A1.5,1.6的基地址为1000，每个元素占5个存储单

16、元，若以行序为主序顺序存储，则元素A5,5的存储地址为 1140 。5. 一个nn的对称矩阵，如果以相同的元素只存储一次的原则进行压缩存储，则其元素压缩后所需的存储容量为 n(n+1)/2 。6. 对矩阵压缩的目的是为了 节省存储空间 。7. 循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的 求模（或取余） 运算来实现的。8. 一棵具有100个结点的完全二叉树，其叶结点的个数为 50 。9. 以5，9，12，13，20，30为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。10. 有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。11. 若一棵完

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

18、列。18. 哈希法存储的基本思想是根据 关键字 来决定存储地址。19. 若用表示图中顶点数，则有条边的无向图称为完全图。20. 个顶点的连通无向图至少有条边，至多有条边。21. 若有向图的邻接矩阵为： 则顶点的入度是3。22. 对于一个有向图，若一个顶点的度为，出度为，则对应逆邻接表中该顶点单链表中的边结点数为。23. 在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。24. 数据结构中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。25. 执行排序操作时，根据使用的存储器可将排序算法分为 内排序 和 外排序 。26. 在对一组记录序列50,40,95,20,15,70,60,4

19、5,80进行直接插入排序时，当把第7个记录60插入到有序表中时，为寻找插入位置需比较 3 次。27. 在直接插入排序和直接选择排序中，若初始记录序列基本有序，则选用 直接插入排序 。28. 在对一组记录序列50,40,95,20,15,70,60,45,80进行直接选择排序时，第4次交换和选择后，未排序记录为 50,70,60,95,80。29. n个记录的冒泡排序算法所需的最大移动次数为 3n(n-1)/2 ，最小移动次数为 0 。30. m阶B-树上的结点至多有m棵子树。三、 解答题（知识点)1、 循环队列的特点2、 二叉树的遍历、树和二叉树的转换3、 Huffman编码4、 图的存储及遍历5、 最小生成树6、 拓扑排序7、 折半查找8、 二叉排序树及平衡二叉树9、 哈希表10、希尔排序，快速排序、堆排序、二路归并排序,写出一趟的结果、判断稳定否。(参考课件)四、 算法设计 参考实验及书上经典算法