《数据结构考试题（2020年整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构考试题（2020年整理）.pdf（20页珍藏版）》请在金锄头文库上搜索。
1、 1 一、单项选择单项选择 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的 C 、数据信息在计算机中的 A 以及一组相关的运算等的 课程。 A操作对象 计算方法 逻辑结构 数据映象 A存储结构 关系 运算 算法 2. 以下数据结构中, D 是线性结构。 A广义表 二叉树 稀疏矩阵 串 3. 从逻辑上可以把数据结构分为 C 两大类。 A动态结构和静态结构 顺序结构和链式结构 线性结构和非线性结构 初等结构和构造型结构 4. 以下数据结构中, D 是线性结构。 A广义表 二叉树 稀疏矩阵 串 5. 以下数据结构中, D 是非线性结构。 A栈 二叉树 队列 字符串 6. 数据结构 D
2、S(Data Struct)可以被形式地定义为 DS=（D，R） ，其中 D 是 B 的有限集合，R 是 D 上的 D 有限集合。 A算法 数据元素 数据操作 数据对象 A操作 映象 存储 关系 7. 线性表的顺序存储结构是一种 A 的存储结构, 线性表的链式存储结构是一种的 B 存储结构。 A随机存取 顺序存取 索引存取 散列存取 2 8. 线性表的逻辑顺序与存储顺序总是一致的，这种说法_B _。 A. 正确 B. 不正确 9. 下面那一条是顺序存储结构的优点? (A) A . 存储密度大 B. 插入运算方便 C. 删除运算方便 D. 可以方便的用于各种逻辑结构的存储表示 10. 线性表采用
3、链式存储结构时, 要求内存中可用的存储单元的地址 . A . 必须是连续的 B. 部分地址必须是连续的 C. 一定不连续 D. 连续和不连续都可以 11. 表长为 n 的顺序存储的线性表, 当在任何位置上插入和删除一个元素的概率相等时, 插入一个元素所需要移动元素的平均次数为 E , 删除一个元素所需要移动元素的平均次数为 A A. (n-1)/2 B.n C. n+1 D. n-1 E. n/2 F. (n+1)/2 G. (n-2)/2 12. 带头结点的单链表 head 为空的判定条件是_B_。 A. head= =NULL B. head-next= =NULL C. head-nex
4、t= =head D. head!=NULL 13. 在一个单链表中, 若删除 p 所指向结点的后继结点, 则执行_A_。 A. p-next= p-next-next B. p=p-next; p-next= p-next-next C. p= p-next-next D. p= p-next 14. 若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，若 p1=n，则 pi 为_C_。 A. i B. n=i C. n-i+1 D. 不确定 3 15. 设栈的输入次序为: 1 , 2, 3, 4, 5, 则 不可能是其出栈序列. A. 54321 B. 4532
5、1 C. 43512 D. 12345 16. 一个递归算法必须包括 B A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部分 17. 用链接方式存储的队列, 在进行删除操作时 D A 仅修改头指针 B. 仅修改尾指针 C. 头尾指针都要修改 D. 头尾指针可能都要修改 18. 数组 Am存放循环队列的元素, 其头尾指针分别是 front 和 rear, 则当前队列的元素个数是_A_。 A. (rear-front+m)%m B. (front-rear+m)%m C. front-rear+1 D. rear-front+1 19. 栈和队列的共同特点_C_。
6、A. 都是先进先出 B. 都是先进后出 C. 允许在端点插入和删除元素 D. 没有共同点 20. 一个栈的入栈序列 a，b，c，d，e，则栈的输出序列是_A_。 A. edcba B. decba C. dceab D. abcde 21. 栈的特点是_B_，队列的特点是_A_。 A. 先进先出 B. 先进后出 22. 从一个栈顶指针 HS 的链表中删除一个结点, 用 x 保存被删除的结点值,执行的语句为_C_。 A. x=HS; HS=HS-next B. HS=HS-next; x=HS-data 4 C. x=HS-data; HS=HS-next D. HS-next=HS; x=HS
7、-data 23. 在链队列 Q 中, 插入 s 所指向的结点执行的语句为_C_。 A. Q.front-next=s; B. Q.rear-next=s; Q.rear=s C. s-next=Q.rear;Q.rear=s D. s-next=Q.front;Q.front=s 24. 空串与空格串是相同的，这种说法_B_。 A. 正确 B. 不正确 25. 下面关于串的叙述, 哪一个是不正确的_B_。 A. 串是字符的有限序列 B. 空串是由空格构成的串 C. 匹配模式是串的一种重要运算 D. 串可以采用链式存储结构 26. 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算
8、称作_B_。 A. 连接 B. 模式匹配 C. 求子串 D. 求串长 27. 若串 s=software, 其子串的数目为 B A. 8 B. 37 C. 36 D. 9 28. 二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在存储器内， 该数组按行存放时，数组元素 A74的起始地址为_C_。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 29. 对稀疏矩阵进行压缩存储的目的是_C_. A. 便于进行矩阵运算 B. 便于输入输出 5 C 节省存储空间 D. 降低运算的时
9、间复杂度 30. 在以下叙述中正确的是 B A. 线性表的线性存储结构优于链表存储结构 B. 二维数组可以看成是其数据元素为线性表的线性表 C. 栈的操作方式是先进先出 D. 队列的操作方式是先进后出 31. 广义表(a),a)的表头为 C , 表尾为 C . A. () B. a C. (a) D. (a) 32. 已知广义表 L=(x,y,z),a,(u,t,w), 从 L 中取出原子项 t 的运算为_D_。 A. Head(Tail(Tail(L) B. Tail(Head(Head(Tail(L) C. Head(Tail(Head(Tail(L) D. Head(Tail(Head(
10、Tail(Tail(L) 33. 树最适合用来表示 B A. 有序的数据元素 B. 数据之间具有分支层次关系的数据 C. 无序的数据元素 D. 无太多关系的数据元素 34. 如果某二叉树的前根次序遍历结果为 stuwv，中序遍历为 uwtvs，那么该二叉树的后序为_B_。 A. uwvts B. vwuts C. wuvts D. wutsv 35. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是_D_。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 36. 在一非空
11、二叉树的中序遍历序列中，根结点的右边_A_。 6 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 37. 设 m 和 n 是一棵二叉树上的两个结点, 在中序遍历, n 在 m 前的条件是 C A. n 在 m 的右方 B. n 是 m 的祖先 C. n 在 m 的左方 D. n 是 m 的子孙 38. 深度为 5 的二叉树至多有_C_个结点。 A. 16 B. 32 C. 31 D. 10 39. 由权(8,2,5,7)的四个叶子结点构造一棵哈夫曼树, 该树的带权路径长度为 D A. 23 B. 37 C. 46 D. 4
12、3 40. 利用二叉链表存储树, 则根结点的右指针是 C A. 指向最左孩子 B. 指向最右孩子 C. 空 D. 非空 41. 下列存储方式中, 哪一个不是树的存储形式? D A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 42. 在一个无向图中，所有顶点的度数之和等于所有边数的_C_倍。 A. 1/2 B. 1 C. 2 D. 4 43. 具有 n 个顶点和多于 n-1 条边的无向图 B . A. 有可能是树 B. 一定不是树 C. 一定是树 D. 以上答案都不对 44. 具有 6 个顶点的无向图至少应有_A_条边才能确保是一个连通图。 7 A. 5 B.
13、 6 C. 7 D. 8 45. 无向图 G=(V,E), 其中: V=a,b,c,d,e,f, E=(a,b),(a,e),(a,c), (b,e),(c,f),(f,d),(e,d), 则对该图进行深度优先遍历, 得到的序列为: D A. abecdf B. acfebd C. aebcfd D. aedfcb 46. 下述几种排序方法中，要求内存量最大的是_D_。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 47. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上 的方法，称为_C_。 A. 希尔排序 B
14、. 起泡排序 C. 插入排序 D. 选择排序 48. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是_A_。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 49. 下列排序算法中, 哪一个是稳定的排序算法? B A. 直接选择排序 B. 二分法插入排序 C. 希尔排序 D. 快速排序 50. 将两个各有 n 个元素的有序表归并成一个有序表, 其最少的比较次数 A A. n B. 2n-1 C. 2n D. n-1 二、二、填空题填空题 1. 算法的五个重要特性是 有穷性,确定性,可行性,输入和输出. 2. 数据的树型结构和图(网)状结构合称 非线性结构 . 3. 抽象数据类型的定义仅取决于它的一组 逻辑特性 , 而与 数据在计算机中的表示和实现 无关. 4. 评价算法质量的指标是 正确性,易读性,健壮性,高效性. 8 5. 数据结构中评价算法的两个重要指标是: 时间复杂度和空间复杂度. 6. 分析下面算法（程序段） ，的时间复杂度是_ O (mn) _。 s=0; for (i=0;in;i+) for (j=0;jprior=q-prior; q-prior-next=p; p-next=q; q-prior=p; 16. 一般情况下, 将递归算法
