数据结构复习题

1、数据结构考试题：一、选择题1.数据结构是指（ ）。A.数据元素的组织形式 B.数据类型C.数据存储结构 D.数据定义2. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。A.存储结构B.逻辑结构 C.链式存储结构D.顺序存储结构3. 树形结构是数据元素之间存在一种（ ）。A.一对一关系B.多对多关系 C.多对一关系D.一对多关系4. 设语句x+的时间是单位时间，则以下语句的时间复杂度为（ ）。for(i=1; i<=n; i+)for(j=i; j<=n; j+)x+;A.O(1)B.O()C.O(n)D.O()5. 数据在计算机内有链式和顺序两种存储方式，在

2、存储空间使用的灵活性上，链式存储比顺序存储要（ ）。A.低 B.高 C.相同D.不好说6. 线性表是（ ）。A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空7. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是（ ）。A p.next=s; s.prior=p; p.next.prior=s; s.next=p.next;B s.prior=p; s.next=p.next; p.next=s; p.next.prior=s;C p.next=s; p.next.prior=s; s.prior=p; s.next=p.ne

3、xt;D s.prior=p; s.next=p.next; p.next.prior=s; p.next=s;8. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ ）。Ap.next=p.next.next;Bp=p.next;Cp=p.next.next; Dp.next=p;9. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ ）。As.next=p.next; p.next=sBq.next=s; s.next=pCp.next=s.next; s.next=pDp.next=s; s.next=q10. 以下关于

4、线性表的说法不正确的是（ ）。  A线性表中的数据元素可以是数字、字符、记录等不同类型。B线性表中包含的数据元素个数不是任意的。C线性表中的每个结点都有且只有一个直接前趋和直接后继。D存在这样的线性表：表中各结点都没有直接前趋和直接后继。11. 线性表的顺序存储结构是一种（ ）的存储结构。  A随机存取B顺序存取C索引存取D散列存取12. 在顺序表中，只要知道（ ），就可在相同时间内求出任一结点的存储地址。A基地址B结点大小 C向量大小 D基地址和结点大小13. 堆栈和队列的共同点（ ）。A.都是先进先出 B.只能在端点处插入和删除元素 C.都是后进后出 D.在任意位置进行

5、插入和删除元素14. 一个栈的进栈序列是A B C,D，则栈的不可能的输出序列是（ ）。A.C A B D B.C B A D C.A B D C D.B A D C15. 在一个链队中，假设front和rear分别为对头和队尾指针，则删除一个结点的运算为 A. rear=front.next; B. rear=rear.next; C. front=front.next; D. front=rear.next;16. 两个字符串相等的条件是（ ）。A.两串的长度相等 B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同17. （ ）是”

6、abcd321ABCD”的子串A.”acAB” B.”cdC” C .“ 321D ” D.”ABCD”18. S1=”DataStructure” S1的长度为（ ）。A.10 B .13 C .16 D. 1819. 一维数组A，A0的内存单元地址为1000，每个数据元素占用4个存储单元，下标为6的数据元素的存储地址是（ ）。A.1024 B .1016 C .1000 D.102020. 将对称矩阵进行压缩存储，当我们存放下三角数据时通常采用（ ）。A列序为主序 B随意存储C依次存储 D行序为主序21.下图所示树的结点A的孩子结点为（ ）。 ABCDEFGHA.B C B .C D C

7、.B D.B C D22.下图所示树的结点B的兄弟结点为（ ）。 ABCDEFGHA.C B .D C .C D D.B C D23.下图所示树的结点A的度为（ ）。 ABCDEFGHA.1 B .2 C .3 D.024. 下图4棵树中，（ ）不是完全二叉树。 A. B. C. D.25. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为()。A. sB. s-1C. s+1D. n26. 采用邻接表存储的图的深度优先遍历类似于二叉树的( )。 A中序遍历 B. 先序遍历 C. 后序遍历 D. 按层次遍历27. 在一个具有n个顶点的无向图中，若具有e条边，则

8、所有顶点的度数之和为()。A. n B. eC. n+eD. 2e28. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。 A. n B. n+1 C. n-1 D. n/229. 下列数据中，（ ）是非线性数据结构。 A栈 B. 队列 C. 完全二叉树 D. 堆30. 下面关于串的的叙述中，哪一个是不正确的？（ ） A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要运算 D串既可以采用顺序存储，也可以采用链式存储31. 设有三个元素 X，Y，Z 顺序进栈（进的过程中允许出栈） ，下列得不到的出栈排列是( )。 AXYZ B. YZX C. ZXY D. Z

9、YX32. 一棵二叉树中度为0的结点有7个，那么度为2的结点有（ ）个。A.3 B .6 C .8 D.1533. 在对n个元素进行冒泡排序的过程中，第一趟排序至多需要进行（ ）对相邻元素之间的交换。 A. n B. n-1 C. n+1 D. n/234.线性表的链接实现有利于（ ）运算。 A. 插入 B. 读表元 C. 查找 D. 定位35.二叉树的第i（i>=1）层最多有（ ）个结点。 A.2i B.2i C.2i-1 D.2i-136. 一棵二叉树中度为2的结点有7个，那么度为0的结点有（ ）个。A.3 B .6 C .8 D.1537. 假定对元素序列（7, 3, 5, 9,

10、1, 12, 8, 15）进行快速排序，则进行第一次划分后，得到的左区间中元素的个数为（ ）。 A. 2 B. 3 C. 4 D. 538. 在对n个元素进行直接插入排序的过程中，共需要进行（ ）趟。A. n B. n+1 C. n-1 D. 2n39. 下列哪个不是二叉树的存储结构（ ）。A顺序存储B二叉链表C三叉链表D四叉链表40. 算法分析的目的是（ ）。A.找出数据结构的合理性 B.研究算法中的输入和输出关系C.分析算法的效率以求改进 D.分析算法的易懂性和文档性41.算法分析的两个主要方面是（ ）。A.空间复杂度和时间复杂度 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序

11、复杂性42. 计算机算法指的是（ ）。A.计算方法 B.排序方法C.解决问题的有限运算序列 D.调度方法43. 计算机算法它具备输入，输出和（ ）等五个特性。 A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性44. 空串与空格字符组成的串的区别在于（ ）。A.没有区别 B.两串的长度不相等C.两串的长度相等D.两串包含的字符不相同45. 一个子串在包含它的主串中的位置是指（ ）。A.子串的最后那个字符在主串中的位置B.子串的最后那个字符在主串中首次出现的位置C.子串的第一个字符在主串中的位置D.子串的第一个字符在主串中首次出现的位

12、置46. 对稀疏矩阵进行压缩存储目的是（ ）。 A便于进行矩阵运算 B便于输入和输出 C节省存储空间 D降低运算的时间复杂度47. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为( )。A. k B. k+1 C. k+2 D. 2k48. 在一个具有n个单元的顺序栈中，假设以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做入栈（堆栈未满）处理时，top的变化为（）。 A.top不变 B.top=0 C.top- D.top+49. 对于一个无向图，下面( )种说法是正确的。A. 每个顶点的入度等于出度 B. 每个顶点的度等于其入度与出度之和C. 每个顶点的入度为0

13、D. 每个顶点的出度为050. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找查找元素26的比较次数为（）。A.2 B .3 C .4 D. 551.已知8个元素（34，76，45，18，26，54，92，65）按照依次插入结点的方法生成一棵二叉排序树，该树的深度为（）。A. 4 B. 5 C. 6 D. 752中序遍历一棵二叉排序树所得到的结点访问序列是键值的（ ）序列。A递增或递减 B.递减 C.递增 D.无序53在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ ）。A插入B删除C排序D查找54在内部排序中，排序时不稳定的有（）A. 插

14、入 B.快速 C. 冒泡 D. 归并55. 判断一个顺序栈ST (元素最多为MaxSize)为空的条件是（ ）。 A.STtop= =0 B .STtop!=0 C. STtop= =MaxSize D. C. STtop! =MaxSize 56在一个具有n个单元的顺序栈中，假设以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top的变化为（）。 A.top不变 B.top=0 C.top- D.top+57总共三层的完全二叉树，其结点总数至少有（ ）个。A. 3 B.7 C. 8 D. 458队列操作的原则是（）。A. 先进先出 B.只能进行插入 C.后进先出 D.

15、先进后出59栈操作的原则是（）。A. 先进先出 B.只能进行插入 C.后进先出 D. 顺序60具有 10 个叶结点的二叉树中有（ ）个度为 2 的结点？ A8 B9 C10 Dll二、填空题： 1. 衡量算法的效率的有時間效率和空間效率。2. 在树型结构中，树根结点没有前驱结点。3树型结构中，除根之外其余每个结点的有且只有1个前驱结点。4.在树型结构中，叶子结点没有后继结点。5. 数据结构是研讨数据的逻辑结构和物理结构，以及它们之间的相互关系。6.线性结构中元素之间存在一对一关系，树型结构中元素之间存在一对多关系。7.线性表、栈和队列都是线性结构。8.栈只能在栈顶位置插入和删除元素；对于队列只

16、能在队尾位置插入元素。9. 线性表的存储方法有顺序存储和链式存储。10. 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表。11.栈的入栈操作规则是后进先出。12.队列的入队规则是先进先出。13.结点所拥有子树的个数称为该结点的度。14.度为零的结点称为叶子节点。15.树中所有结点的层数为树的深度，树中各结点度的最大值称为树的度。16.在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉对称为满二叉树。17.一棵层数为5的满二叉树上有31个结点。18.一棵非空二叉树的第i层上最多有2i-1。19.一棵深度为k的二叉树

17、中最多具有2k-1个结点。20.对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树称为最优二叉树 或 哈夫曼树。21.在图中，序列中顶点不重复出现的路径称为简单路径。22.在图中，路径中第一个顶点与最后一个顶点相同的路径称为简单回路。23. indexOf(“DATASTRUCTURE”，“STR”）=4。24. 在一个长度为n的顺序表中删除第i个元素（0<i<n）时，需向前移动n-i个元素。 25.折半查找的前提是要求在有序表中进行。26.直接插入排序从稳定性上说是一种稳定的排序方法。27.快速排序稳定性上是一种不稳定的排序方法。28.交换排序可分为两大类：冒泡排

18、序和快速排序。29.冒泡排序与快速排序相比，快速效率更高些。30. 在一个长度为n的顺序表中的第i个元素（0<i<n）之前插入一个元素时，需向后移动n-i+1个元素。31. 数组的存储结构采用順序存储方式。32. 在一棵二叉排序树上按中序遍历得到的结点序列是一个有序序列。33. 树结构常采用链式存储结构。34. 对矩阵压缩是为了节约空间。35. 在一棵二叉树中，度为零的结点的个数为 N0,度为 2 的结点的个数为N2,则有N0 =n2+1。36. 在一个具有n个顶点的无向完全图中，包含有n(n+1)/2条边37. 从有序表(12,18,30,43,56,78,82,95)中分别折半查找43元素时，其比较次数分别为1次。38. 在所有排序方法中，二路归并方法采用的是两两有序表合并