数据结构-试题汇编(带答案解析).doc

《数据结构-试题汇编(带答案解析).doc》由会员分享，可在线阅读，更多相关《数据结构-试题汇编(带答案解析).doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.*数据结构习题汇编一、单项选择题1. 在数据结构中，从逻辑上可以把数据结构分成（ ）。A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构2. 数据结构在计算机内存中的表示是指（ ）。A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系3. 在数据结构中，与所使用的计算机无关的是数据的（ ）结构。A. 逻辑B. 存储C. 逻辑和存储D. 物理4. 计算机算法指的是（ ），它必须具备输入、输出和（ ）等5个特性。A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法A. 可行性、可移植性和可扩充性B. 可

2、行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性5. 在一个长度为n的顺序表中向第i个元素（1in+1）位置插入一个新元素时，需要从后向前依次后移（ ）个元素。A. n-iB. n-i+1C. n-i-1D. i6. 在一个长度为n的顺序表中删除第i个元素（1in）时，需要从前向后依次前移（ ）个元素。A. n-iB. n-i+1C. n-i-1D. i7. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（ ）。A. O(n)B. O(1)C. O(n2)D. O(log2n)8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）

3、。A. O(n)B. O(n/2)C. O(1)D. O(n2)9. 不带头结点的单链表first为空的判定条件是：（ ）A. first = NULL;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，则应

4、执行下列哪一个操作？（ ）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.

5、非空的循环单链表first的尾结点（由p所指向）满足：（ ）A. p-next = NULL; B. p = NULL;C. p-next = first;D. p = first;14. 若让元素1,2,3依次进栈，则出栈次序不可能出现（ ）种情况。A. 3, 2, 1B. 2, 1, 3C. 3, 1, 2D. 1, 3, 215. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。A. n-2 B. n-1C. n D. n+116. 从一个顺序存储的循环队列中删除一个元素时，需要（ ）。A. 队头指针加一B. 队头指针减一C. 取出队头指针所指的元素D. 取出队尾指针所

6、指的元素17. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（ ）。A. front+1 = rearB. rear+1 = frontC. front = 0D. front = rear18. 树中所有结点的度等于所有结点数加（ ）。A. 0B. 1C. -1D. 219. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ ）。A. 2B. 1C. 0D. -120. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（ ）。A. n B. n-1C. n+1D. 2*n21. 在一棵具有n个结点的二叉树的第i层上（假定根结点为第1层

7、，i大于等于1而小于等于树的高度），最多具有（ ）个结点。A. 2iB. 2i+1C. 2i-1D. 2n22. 在一棵高度为h（假定根结点的层号为1）的完全二叉树中，所含结点个数不小于（ ）。A. 2h-1B. 2h+1C. 2h-1D. 2h23. 在一棵具有35个结点的完全二叉树中，该树的高度为（ ）。假定空树的高度为0。A. 5B. 6C. 7D. 824. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为（ ）。假定树根结点的编号为1。A. (n-1)/2B. n/2 C. n/2 D. n/2 -125. 在一棵完全二叉树中，若编号为i的结点存在左孩子，则左子女结点的编号为（

8、 ）。假定根结点的编号为1A. 2iB. 2i-1C. 2i+1D. 2i+226. 在一棵完全二叉树中，假定根结点的编号为1，则对于编号为i（i1）的结点，其双亲结点的编号为（ ）。A. (i+1)/2B. (i-1)/2C. i/2D. i/2 -127. 设无向图的顶点个数为n，则该图最多有（ ）条边。A. n-1 B. n(n-1)/2C. n(n+1)/2 D. n(n-1)28. n个顶点的连通图至少有（ ）条边。A. n-1 B. nC. n+1D. 029. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。A. 3B. 2C. 1D. 1/230. 图的深度优先搜

9、索类似于树的（ ）次序遍历。A. 先根B. 中根C. 后根D. 层次31. 图的广度优先搜索类似于树的（ ）次序遍历。A. 先根B. 中根C. 后根D. 层次32. n (n1) 个顶点的强连通图中至少含有（ ）条有向边。A. n-1 B. nC. n(n-1)/2D. n(n-1)33. 具有n个顶点的有向无环图最多可包含（ ）条有向边。A. n-1B. n C. n(n-1)/2 D.n(n-1)34. 一个有n个顶点和n条边的无向图一定是（ ）。A. 连通的 B. 不连通的 C. 无环的 D. 有环的35. 在n个顶点的有向无环图的邻接矩阵中至少有（ ）个零元素。A. nB. n(n-1

10、)/2 C. n(n+1)/2D. n(n-1)36. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据结构是（ ）。A. 栈 B. 队列C. 二叉树 D. 树37. 若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为（ ）。A. nB. n+1C. (n-1)/2D. (n+1)/238. 对长度为10的顺序表进行搜索(从表头开始搜索)，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（ ）。A. 5.5B. 5C. 39/8D. 19/439. 对于长度为n的有序顺序表，若采用折

11、半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向上取整。A. log2(n+1)B. log2nC. n/2D. (n+1)/240. 对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（ ）的值的向下取整加一。A. log2(n+1)B. log2nC. n/2D. (n+1)/241. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（ ）的值除以9。A. 20B. 18C. 25D. 2242. 对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（ ）。A. 3B. 4 C. 5 D. 643. 对具有

12、n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（ ）。A. O(n)B. O(n2)C. O(1)D. O(log2n)44. 对5个不同的数据元素进行直接插入排序，最多需要进行（ ）次比较？A. 8B. 10C. 15D. 2545. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最快结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序46. 如果输入序列是已经排好顺序的，则下列算法中（ ）算法最慢结束？A. 起泡排序B. 直接插入排序C. 直接选择排序D. 快速排序二、填空题1. 算法的五个重要特性是 有穷性 、确定性、可行性、输入和输出。2. 设单

13、链表中结点的结构为（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个元素的出栈顺

14、序为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。9. 在一棵高度为3的四叉树中，最多含有 21 结点。10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个

15、，度为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，则在搜

16、索成功情况下的平均搜索长度的计算公式为 。17. 假定一个顺序表的长度为40，并假定搜索每个元素的概率都相同，则在搜索成功情况下的平均搜索长度为20.5。18. 以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为O(log2n)。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. 直接插入排序在最好情况下的移动次

17、数为 ，最坏情况下为 。（最好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 )。

18、28. 在直接选择排序中，数据对象移动次数的时间复杂度为O(n)。29. 快速排序在平均情况下的时间复杂度为O(nlog2n)。30. 快速排序在最坏情况下的时间复杂度为O(n2)。三、简答题1. 下面程序段的时间复杂度是 O(n*m) 。for(i=0;in;i+) for(j=0;jm;j+) Aij=0;2. 下面程序段的时间复杂度是 O(n0.5) 。i=s=0; while(sn) i+; s+=i; 3. 下面程序段的时间复杂度是O(n2) 。s=0;for(i=0;in;i+) for(j=0;jn;j+) s+=Bij;sum=s;4. 下面程序段的时间复杂度是O(log3n)

19、 。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(&S,i);for(i=1;i=n;+i)Pop(&S,&e); EnQueue(&Q,e); DeQueue(&Q,&e); EnQueue(&Q,e); for(i=1;i=n;+i) DeQueue(&Q,&e); Push(&S,e); for(i=1;ilength-1; ElemType t; for(;ielemi;L-elemi=L-elemj;

20、L-elemj=t; 2. 试编写一个函数，用以删除顺序表L中所有值为x的元素（要求就地工作）。void DeleteX(SqList *L, ElemType x) int j=0; for(i=0;ilength;+i) if(L-elemi!=x)if(ij) L-elemj=L-elemi; +j; L-length=j;3. 试编写一个函数，在数组R（已正序排列）中进行折半查找某个值k，找到则返回其位置，否则返回0。int SearchBin(int R, int n, int k)/有序（正序）的顺序表的二分查找，n为数组元素个数，k为待查找的值int low=0,high=n-1,mid;while(lowk) high=mid-1;else low=mid+1;return 0;4. 试编写一个函数，对数组r进行选择法排序（结果为正序）。void SelectSort(ElemType r,int n)/对顺序表r作简单选择排序，n为数组元素个数int i,j,k;ElemType tmp;for(i=0;in-1;+i)k=i;for(j=i+1;jn;+j)if(rjrk)k=j;/k指向rin-1中的最小元素if(k!=i)tmp=ri; ri=rk; rk=tmp;