《数据结构》试题汇编(带答案)

《数据构造》试题汇编(带答案) - 《数据构造》习题汇编 一、单项选择题 1. 在数据构造中，从逻辑上可以把数据构造分成〔 〕 A. 动态构造和静态构造 C. 线性构造和非线性构造 2. 数据构造在计算机内存中的表示是指〔 〕 A. 数据的存储构造 C. 数据的逻辑构造 3. 在数据构造中，与所使用的计算机无关的是数据的〔 〕构造 A. 逻辑 4. 计算机算法指的是〔 ① 〕，它必须具备输入、输出和〔 ② 〕等5个特性 ①A. 计算方法 B. 排序方法 D. 调度方法 B. 可行性、确定性和有穷性 D. 易读性、稳定性和平安性 C. 解决问题的有限运算序列 C. 确定性、有穷性和稳定性 5. 在一个长度为n的顺序表中向第i个元素〔1≤i≤n+1〕位置插入一个新元素时，需要从后向前依次后移〔 〕个元素 A. n-i 6. 在一个长度为n的顺序表中删除第i个元素〔1≤i≤n〕时，需要从前向后依次前移〔 〕个元素 A. n-i 7. 在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为〔 〕 A. O(n) 8. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为〔 〕。

A. O(n) 9. 不带头结点的单链表first为空的断定条件是：〔 〕 A. first == NULL; B. first->next == NULL; D. first != NULL; C. first->next == first; B. O(n/2) C. O(1) D. O(n2) B. O(1) C. O(n2) D. O(log2n) B. n-i+1 C. n-i-1 D. i B. n-i+1 C. n-i-1 D. i B. 存储 C. 逻辑和存储 D. 物理 B. 数据构造 D. 数据元素之间的关系 B. 紧凑构造和非紧凑构造 D. 内部构造和外部构造 ②A. 可行性、可移植性和可扩大性 10. 带头结点的单链表first为空的断定条件是：〔 〕 A. first == NULL; B. first->next == NULL; D. first != NULL; C. first->next == first; 11. 设单链表中结点的构造为〔data, next〕指针p所指结点不是尾结点，假设在*p之后插入结点*s，那么应执行以下哪一个操作？〔 〕 A. s->next = p; p->next = s; C. s->next = p->next; p = s; 1 B. p->next = s; s->next = p; 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; D. p == first; C. p->next == first; 14. 假设让元素1,2,3依次进栈，那么出栈次序不可能出现〔 〕种情况 A. 3, 2, 1 15. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为〔 〕 A. n-2 16. 从一个顺序存储的循环队列中删除一个元素时，需要〔 〕 A. 队头指针加一 17. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，那么判断队空的条件为〔 〕 A. front+1 == rear C. front == 0 18. 树中所有结点的度等于所有结点数加〔 〕。

A. 0 19. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加〔 〕 A. 2 20. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于〔 〕 A. n 21. 在一棵具有n个结点的二叉树的第i层上〔假定根结点为第1层，i大于等于1而小于等于树的高度〕，最多具有〔 〕个结点 A. 2i 22. 在一棵高度为h〔假定根结点的层号为1〕的完全二叉树中，所含结点个数不小于〔 〕 A. 2h-1 23. 在一棵具有35个结点的完全二叉树中，该树的高度为〔 〕假定空树的高度为0 A. 5 24. 在一棵具有n个结点的完全二叉树中，分支结点的最大编号为〔 〕假定树根结点的编号为1 A. ?(n-1)/2? 2 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 B. n-1 C. n D. n+1 B. 队头指针减一 D. 取出队尾指针所指的元素 C. 取出队头指针所指的元素 B. rear+1 == front D. front == rear B. 1 C. -1 D. 2 B. 1 C. 0 D. -1 B. n-1 C. n+1 D. 2*n B. 2i+1 C. 2i-1 D. 2n B. 2h+1 C. 2h-1 D. 2h B. 6 C. 7 D. 8 B. ?n/2? C. ?n/2? D. ?n/2? -1 25. 在一棵完全二叉树中，假设编号为i的结点存在左孩子，那么左子女结点的编号为〔 〕。

假定根结点的编号为1 A. 2i 26. 在一棵完全二叉树中，假定根结点的编号为1，那么对于编号为i〔i＞1〕的结点，其双亲结点的编号为〔 〕 A. ?(i+1)/2? 27. 设无向图的顶点个数为n，那么该图最多有〔 〕条边 A. n-1 28. n个顶点的连通图至少有〔 〕条边 A. n-1 B. n C. n+1 D. 0 29. 在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍 A. 3 30. 图的深度优先搜索类似于树的〔 〕次序遍历 A. 先根 A. 先根 32. n (n＞1) 个顶点的强连通图中至少含有〔 〕条有向边 A. n-1 33. 具有n个顶点的有向无环图最多可包含〔 〕条有向边 A. n-1 34. 一个有n个顶点和n条边的无向图一定是〔 〕 A. 连通的 35. 在n个顶点的有向无环图的邻接矩阵中至少有〔 〕个零元素 A. n 36. 为了实现图的广度优先遍历，BFS算法使用的一个辅助数据构造是〔 〕。

A. 栈 37. 假设搜索每一个元素的概率相等，那么在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为〔 〕 A. n 38. 对长度为10的顺序表进展搜索(从表头开场搜索)，假设搜索前面5个元素的概率一样，均为1/8，搜索后面5个元素的概率一样，均为3/40，那么搜索到表中任一元素的平均搜索长度为〔 〕 A. 5.5 3 B. 2i-1 C. 2i+1 D. 2i+2 B. ?(i-1)/2? C. ?i/2? D. ?i/2? -1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) B. 2 C. 1 D. 1/2 B. 中根 C. 后根 D. 层次 31. 图的广度优先搜索类似于树的〔 〕次序遍历 B. 中根 C. 后根 D. 层次 B. n C. n(n-1)/2 D. n(n-1) B. n C. n(n-1)/2 D.n(n-1) B. 不连通的 C. 无环的 D. 有环的 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) B. 队列 C. 二叉树 D. 树 B. n+1 C. (n-1)/2 D. (n+1)/2 B. 5 C. 39/8 D. 19/4 39. 对于长度为n的有序顺序表，假设采用折半搜索，那么对所有元素的搜索长度中最大的为〔 〕的值的向上取整。

A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 40. 对于长度为n的有序顺序表，假设采用折半搜索，那么对所有元素的搜索长度中最大的为〔 〕的值的向下取整加一 A. log2(n+1) 41. 对于长度为9的有序顺序表，假设采用折半搜索，在等概率情况下搜索成功的平均搜索长度为〔 〕的值除以9 A. 20 42. 对于长度为18的有序顺序表，假设采用折半搜索，那么搜索第15个元素的搜索长度为〔 〕 A. 3 43. 对具有n个元素的有序顺序表进展折半搜索，那么搜索任一元素的时间复杂度为〔 〕 A. O(n) 44. 对5个不同的数据元素进展直接插入排序，最多需要进展〔 〕次比拟？ A. 8 45. 假如输入序列是已经排好顺序的，那么以下算法中〔 〕算法最快完毕？ A. 起泡排序 46. 假如输入序列是已经排好顺序的，那么以下算法中〔 〕算法最慢完毕？ A. 起泡排序 二、填空题 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. 用简单的形式匹配算法在主串\中检索子串”aab”，那么总的比拟次数为 B. log2n C. n/2 D. (n+1)/2 B. 18 C. 25 D. 22 B. 4 C. 5 D. 6 B. O(n2) C. O(1) D. O(log2n) B. 10 C. 15 D. 25 B. 直接插入排序 C. 直接选择排序 D. 快速排序 B. 直接插入排序 C. 直接选择排序 D. 快速排序 15 。

4 7. 用简单的形式匹配算法在主串\中检索子串”string”，总的比拟次数为 12 8. 假定一棵三叉树〔即度为3的树〕的结点个数为50，那么它的最小高度为 为1 9. 在一棵高度为3的四叉树中，最多含有 21 结点 10. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6 个 11. 一棵高度为5的完全二叉树中，最多包含有 31个结点假定根结点的高度为1 12. 在一棵二叉树中，假定度为2的结点个数为5个，度为1的结点个数为6个，那么叶结点数 为 6个 13. 假定一棵二叉树的结点个数为18，那么它的最小高度为 14. 按照二叉树的定义，具有5个结点的二叉树有 5 假定根结点的高度为1假定根结点的高度42 种形态 15. 以顺序搜索方法从长度为n的顺序表或单链表中搜索一个元素时，其时间复杂度为 O(n) 16. 对长度为n的搜索表进展搜索时，假定搜索第i个元素的概率为pi，搜索长度〔即在搜索过程中依次同有关元素比拟的总次数〕为ci，那么在搜索成功情况下的平均搜索长度的计算公式为 n 。

ASL?pici i?1?17. 假定一个顺序表的长度为40，并假定搜索每个元素的概率都一样，那么在搜索成功情况下的平均搜索长度为 20.5 18. 以折半搜索方法从长度为n的有序表中搜索一个元素时，时间复杂度为 O(log2n) 3 19. 从有序表(12,18,30,43,56,78,82,95)中折半搜索元素56时，其搜索长度为 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)〕 5 第 17 页 共 17 页。