数据结构综合练习.doc

综合练习一、单项选择题1. 数据在计算机存储器内表示时，物理地址与逻辑地址不一样的，称之为C 。 A.存储构造B.逻辑构造 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中，每一个数据元素所占的存储单元的数目为4，且第0个数据元素的存储地址为100，那么第7个数据元素的存储地址是 D 。 A.5. 在线性表中假设经常要存取第i个数据元素及其前趋，那么宜采用 A 存储方式。 A.顺序表B. 带头结点的单链表 C.不带头结点的单链表D. 循环单链表6. 在链表中假设经常要删除表中最后一个结点或在最后一个结点之后插入一个新结点，那么宜采用 C 存储方式。 A.顺序表B. 用头指针标识的循环单链表 C. 用尾指针标识的循环单链表D. 双向链表7. 在一个含有n个结点的有序单链表中插入一个新结点，使单链表仍然保持有序的算法的时间复杂度是 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. 需要判断栈元素的类型 D. 无需对栈作任何差异12. 在顺序栈中，假设栈顶指针top指向栈顶元素的存储单元，且顺序栈的最大容量是maxSize，那么顺序栈的判空条件是B。 Atop=0 B=-1 C. top=maxSize D=maxSize-113. 在顺序栈中，假设栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxSize。那么顺序栈的判满的条件是C 。 Atop=0 B=-1 C. top=maxSize D=maxSize-114. 在队列中存取数据元素的原那么是 A 。 A先进先出 B. 先进后出 C. 后进后出 D. 没有限制15. 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满与判空的条件，front与rear分别为队首与队尾指针，它们分别指向队首元素与队尾元素的下一个存储单元，队列的最大存储容量为maxSize，那么队列的判空条件是 A 。 Afront=rear B. front!=rear C. front=rear+1 D. front=(rear+1)% maxSize 16. 在循环顺序队列中，假设以少用一个存储单元的方法来区分队列判满与判空的条件，front与rear分别为队首与队尾指针，它们分别指向队首元素与队尾元素的下一个存储单元，队列的最大存储容量为maxSize，那么队列的判满条件是 D 。 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的链队列采用单循环链表加以表示，假设只设一个头指针指向队首元素，那么入队操作的时间复杂度为 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. 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 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使二叉树的遍历结果唯一30.设F是一个森林，B是由F变换得的二叉树。假设F中有n个非终端结点，那么B中右指针域为空的结点有 C个。An1BnCn + 1Dn + 231.在一个有个顶点的有向图中，假设所有顶点的出度之与为，那么所有顶点的入度之与为A。 A.B.C.D.32.具有6个顶点的无向图至少应有A条边才能确保是一个连通图。33.一个有n个顶点的无向图最多有C条边。 A.B.C.D.34.n个顶点的连通图用邻接距阵表示时，该距阵至少有 B 个非零元素。An B2(n-1) Cn/2 Dn2 35.对某个无向图的邻接矩阵来说，以下表达正确的选项是A。 A.第行上的非零元素个数与第列上的非零元素个数一定相等 B.矩阵中的非零元素个数等于图中的边数 C.第行与第列上的非零元素的总数等于顶点的度数 D.矩阵中非全零行的行数等于图中的顶点数 .32.任何一个无向连通图的最小生成树B。 A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在36.下面 B 方法可以判断出一个有向图是否有环。 A 深度优先遍历 B拓扑排序 C求最短路径 D求关键路径37.对线性表进展二分查找时，要求线性表必须( B ) A.以顺序方式存储 B.以顺序方式存储，且结点按关键字值有序排列 C.以链接方式存储 D.以链接方式存储，且结点按关键字值有序排列38.用二分查找法查找具有n个结点的顺序表时，查找每个结点的平均比拟次数是( D ) A.O(n2) B.O(nlog2n) C.O(n) D.O(log2n)39.假设有一个长度为64的有序表，现用二分查找方法查找某一记录，那么查找不成功，最多需要比拟( B )次。40.假设结点的存储地址与其关键字之间存在某种映射关系，那么称这种存储构造为( D )41. 设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，那么放入的位置是 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.插入排序    45.一组记录的关键字为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)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 )最不利于其优势的发挥。49.在待排序序列局部有序时，效率最高的排序算法是( B )。50.数据表中有10000个元素，如果仅要求求出其中最大的10个元素，那么采用( D )算法最节省时间。A冒泡排序 B快速排序 C简单项选择择排序 D堆排序二、填空题1. 一个串的任意连续字符组成的子序列称为串的 子串 ，该串称为 主串 。2. 假设两个串的长度相等且对应位置上的字符也相等，那么称两个串 相等 。3. 寻找子串在主串中的位置，称为 模式匹配 。其中，子串又称为 模式串 。4. 设数组A1.5,1.6的基地址为1000，每个元素占5个存储单元，假设以行序为主序顺序存储，那么元素A5,5的存储地址为 1140 。5. 一个n×n的对称矩阵，如果以一样的元素只存储一次的原那么进展压缩存储，那么其元素压缩后所需的存储容量为 n(n+1)/2 。6. 对矩阵压缩的目的是为了 节省存储空间 。7. 循环顺序队列是将顺序队列的存储区域看成是一个首尾相连的环，首尾相连的状态是通过数学上的 求模或取余 运算来实现的。8. 一棵具有100个结点的完全二叉树，其叶结点的个数为 50 。9. 以5，9，12，13，20，30为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。10. 有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。11. 假设一棵完全二叉树的第4层(根结点在第0层)有7个结点，那么这棵完全二叉树的叶子结点总数是 11 。12. 在深度为k的完全二叉树中至少有 k个结点，至多有 2k-1 个结点。13. 假定待查找记录个数为n,那么在等概率的情况下，顺序查找在查找成功情况下的平均查找长度为 (n+1)/2 ；在查找失败情况下的平均查找长度为 n+1 。14. 对线性表进展二分查找时，要求线性表必须以顺序方式存储，且数据有序 。15. 分块查找分为两个阶段，分别是确定待查元素所在的块 与 在块内查找待查的元素。16. 哈希法存储中，冲突指的是不同关键字值对应到一样的存储地址。17. 一棵二叉排序树用中序遍历输出的信息是 递增 序列。18. 哈希法存储的根本思想是根据 关键字 来决定存储地址。19. 假设用表示图中顶点数，那么有条边的无向图称为完全图。20. 个顶点的连通无向图至少有条边，至多有条边。21. 假设有向图的邻接矩阵为： 那么顶点的入度是3。22. 对于一个有向图，假设一个顶点的度为，出度为，那么对应逆邻接表中该顶点单链表中的边结点数为。23. 在求最小生成树的两种算法中，克鲁斯卡尔算法适合于稀疏图。24. 数据构造中的迪杰斯特拉算法是用来求某个源点到其余各顶点的最短路径。25. 执行排序操作时，根据使用的存储器可将排序算法分为 内排序 与 外排序 。26. 在对一组记录序列50,40,95,20,15,70,60,45,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、希尔排序，快速排序、堆排序、二路归并排序,写出一趟的结果、判断稳定否。(参考课件)四、 算法设计 参考实验及书上经典算法第 13 页