《数据结构》习题汇编&参考答案.docx

第 1 页 共 15 页数据结构习题汇编 B. first->next = NULL;C. first->next = first; D. first != NULL;10. 带头结点的单链表 first 为空的判定条件是：（ ）A. first = NULL; B. first->next = NULL;C. first->next = first; D. first != NULL;11. 设单链表中结点的结构为（data, next） 。已知指针 p 所指结点不是尾结点，若在*p 之后插入结点*s，则应执行下列哪一个操作？（ ）A. s->next = p; p->next = s; B. p->next = s; s->next = p;C. s->next = p->next; p = s; D. s->next = p->next; p->next = s;12. 设单链表中结点的结构为（data, next） 。若想摘除结点*p(*p 既不是第一个也不是最后一个结点)的直接后继，则应执行下列哪一个操作？（ ）A. p->next = p->next->next; B. p = p->next; p->next = p->next->next;C. p->next = p->next; D. p = p->next->next;13. 非空的循环单链表 first 的尾结点（由 p 所指向）满足：（ ）A. p->next = NULL; B. p = NULL;C. p->next = first; D. p = first;第 3 页 共 15 页14. 若让元素 1,2,3 依次进栈，则出栈次序不可能出现（ ）种情况。A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 215. 当利用大小为 n 的数组顺序存储一个队列时，该队列的最大长度为（ ） 。A. n-2 B. n-1 C. n D. n+116. 从一个顺序存储的循环队列中删除一个元素时，需要（ ） 。A. 队头指针加一 B. 队头指针减一C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素17. 假定一个顺序存储的循环队列的队头和队尾指针分别为 front 和 rear，则判断队空的条件为（ ） 。A. front+1 = rear B. rear+1 = frontC. front = 0 D. front = rear18. 树中所有结点的度等于所有结点数加（ ） 。A. 0 B. 1 C. -1 D. 219. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ） 。A. 2 B. 1 C. 0 D. -120. 在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（ ） 。A. n B. n-1 C. n+1 D. 2*n21. 在一棵具有 n 个结点的二叉树的第 i 层上（假定根结点为第 1 层，i 大于等于 1 而小于等于树的高度） ，最多具有（ ）个结点。A. 2i B. 2i+1 C. 2i-1 D. 2n第 4 页 共 15 页22. 在一棵高度为 h（假定根结点的层号为 1）的完全二叉树中，所含结点个数不小于（ ） 。A. 2h-1 B. 2h+1 C. 2h-1 D. 2h23. 在一棵具有 35 个结点的完全二叉树中，该树的高度为（ ） 。假定空树的高度为 0。A. 5 B. 6 C. 7 D. 824. 在一棵具有 n 个结点的完全二叉树中，分支结点的最大编号为（ ） 。假定树根结点的编号为 1。A. (n-1)/2 B. n/2 C. n/2 D. n/2 -125. 在一棵完全二叉树中，若编号为 i 的结点存在左孩子，则左子女结点的编号为（ ） 。假定根结点的编号为 1A. 2i B. 2i-1 C. 2i+1 D. 2i+226. 在一棵完全二叉树中，假定根结点的编号为 1，则对于编号为 i（i1）的结点，其双亲结点的编号为（ ） 。A. (i+1)/2 B. (i-1)/2 C. i/2 D. i/2 -127. 设无向图的顶点个数为 n，则该图最多有（ ）条边。A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)28.n 个顶点的连通图至少有（ ）条边。A. n-1 B. n C. n+1 D. 029. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。A. 3 B. 2 C. 1 D. 1/2第 5 页 共 15 页30. 图的深度优先搜索类似于树的（ ）次序遍历。A. 先根 B. 中根 C. 后根 D. 层次31. 图的广度优先搜索类似于树的（ ）次序遍历。A. 先根 B. 中根 C. 后根 D. 层次32.n (n1) 个顶点的强连通图中至少含有（ ）条有向边。A. n-1 B. n C. n(n-1)/2 D. n(n-1)33. 具有 n 个顶点的有向无环图最多可包含（ ）条有向边。A. n-1 B. n C. n(n-1)/2 D.n(n-1)34. 一个有 n 个顶点和 n 条边的无向图一定是（ ） 。A. 连通的 B. 不连通的 C. 无环的 D. 有环的35. 在 n 个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。A. n B. n(n-1)/2 C. n(n+1)/2 D. n(n-1)36. 为了实现图的广度优先遍历，BFS 算法使用的一个辅助数据结构是（ ） 。A. 栈 B. 队列 C. 二叉树 D. 树37. 若搜索每一个元素的概率相等，则在长度为 n 的顺序表上搜索到表中任一元素的平均搜索长度为（ ） 。A. n B. n+1 C. (n-1)/2 D. (n+1)/238. 对长度为 10 的顺序表进行搜索(从表头开始搜索)，若搜索前面 5 个元素的概率相同，均为 1/8，搜索后面 5 个元素的概率相同，均为 3/40，则搜索到表中任一元素的平均搜索长度为（ ） 。第 6 页 共 15 页A. 5.5 B. 5 C. 39/8 D. 19/439. 对于长度为 n 的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向上取整。A. log2(n+1) B. log2n C. n/2 D. (n+1)/240. 对于长度为 n 的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向下取整加一。A. log2(n+1) B. log2n C. n/2 D. (n+1)/241. 对于长度为 9 的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以 9。A. 20 B. 18 C. 25 D. 2242. 对于长度为 18 的有序顺序表，若采用折半搜索，则搜索第 15 个元素的搜索长度为（ ） 。A. 3 B. 4 C. 5 D. 643. 对具有 n 个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（ ） 。A. O(n) B. O(n2) C. O(1) D. O(log2n)44. 对 5 个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较？A. 8 B. 10 C. 15 D. 2545. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序46. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最慢结束？第 7 页 共 15 页A. 起泡排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序二、填空题1. 算法的五个重要特性是 有穷性 、确定性、可行性、输入和输出。2. 设单链表中结点的结构为（data, next） 。若想摘除结点*p 本身，则应执行操作：q=p->next; p->data=q->data; p->next=q->next ; free(q) ;3. 设循环队列 Q 的队头和队尾指针分别为 front 和 rear，队列的最大容量为 MaxSize，且规定判断队空的条件为 Q.front = Q.rear，则判断队满的条件为 (Q.rear+1)%MaxSize=Q.front ，而计算队列长度的表达式为(Q.rear-Q.front+MaxSize)%MaxSize 。4. 设有一个顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，如果 6 个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为 3 。5. 如果进栈序列是 1, 2, 3, 4, 5, 6, 7, 8。则可能的出栈序列有 1430 种。6. 用简单的模式匹配算法在主串“aaaaaab“中检索子串”aab” ，则总的比较次数为 15 。7. 用简单的模式匹配算法在主串“data_structure“中检索子串”string” ，总的比较次数为12 。8. 假定一棵三叉树（即度为 3 的树）的结点个数为 50，则它的最小高度为 5 。假定根结点的高度为 1。第 8 页 共 15 页9. 在一棵高度为 3 的四叉树中，最多含有 21 结点。10. 在一棵三叉树中，度为 3 的结点数有 2 个，度为 2 的结点数有 1 个，度为 1 的结点数为 2个，那么度为 0 的结点数有 6 个。11. 一棵高度为 5 的完全二叉树中，最多包含有 31 个结点。假定根结点的高度为 1。12. 在一棵二叉树中，假定度为 2 的结点个数为 5 个，度为 1 的结点个数为 6 个，则叶结点数为 6 个。13. 假定一棵二叉树的结点个数为 18，则它的最小高度为 5 。假定根结点的高度为1。14. 按照二叉树的定义，具有 5 个结点的二叉树有 42 种形态。15. 以顺序搜索方法从长度为 n 的顺序表或单链表中搜索一个元素时，其时间复杂度为 O(n)。16. 对长度为 n 的搜索表进行搜索时，假定搜索第 i 个元素的概率为 pi，搜索长度（即在搜索过程中依次同有关元素比较的总次数）为 ci，则在搜索成功情况下的平均搜索长度的计算公式为 。17. 假定一个顺序表的长度为 40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为 20.5 。18. 以折半搜索方法从长度为 n 的有序表中搜索一个元素时，时间复杂度为 O(log2n)。1niASLpc第 9 页 共 15 页19. 从有序表(12,18,30,43,56,78,82,95)中折半搜索元素 56 时，其搜索长度为 3 。20. 假定对长度 n = 50 的有序表进行折半搜索，则对应的判定树中最后一层的结点数为 19个。21. 直接插入排序在最好情况下的比较次数为 ，最坏情况下为 。（正序最好 C=n-1，逆序最坏 C=n*(n-1)/2）22. 直接插入排序在最好情况下的移动次数为 ，最坏情况下为 。（最好 M=0，最坏 M=(n+4)*(n-1)/2）23. 简单选择法排序时比较数据的次数为 。 （任何情况下 C=n*(n-1)/2）24. 简单选择法排序在最好情况下的移动次数为 ，最坏情况下为 。（最好正序 M=0，最坏（非逆序，如 6,1,2,3,4,5）M=3*(n-1)）25. 起泡排序在最好情况下的比较次数为 ，最坏情况下为 。（最好正序 C=n-1，最坏逆序 C=n*(n-1)/2）26. 起泡排序在最好情况下的移动次数为 ，最坏情况下为 。（最好正序 M=0，最坏（逆序）M=3*n*(n-1)/2）27. 在直接选择排序中，排序码比较次数的时间复杂度为 O( n2 )。28. 在直接选择排序中，数据对象移动次数的时间复杂度为 O( n )。第 10 页 共 15 页29. 快速排序在平均情况下的时间复杂度为 O( nlog2n )。30. 快速排序在最坏情况下的时间复杂度为 O( n2 )。三、简答题1. 下面程序段的时间复杂度是 O(n*m) 。for(i=0;i<n;i+)for(j=0;j<m;j+)Aij=0;2. 下面程序段的时间复杂度是 O(n0.5) 。i=s=0; while(s<n) i+; s+=i; 3. 下面程序段的时间复杂度是 O(n2) 。s=0;for(i=0;i<n;i+)for(j=0;j<n;j+)s+=Bij;sum=s;4. 下面程序段的时间复杂度是 O(log3n) 。i=1; while(i<=n) i=i*3;5. 写出下列程序段的输出结果: 514263 。void main( ) SqStack S; SqQueue Q; int i,j,n=6,e;for(i=1;i<=n;+i)Push(for(i=1;i<=n;+i)Pop( EnQueue( DeQueue( EnQueue(