2数据结构-复习习题

1、一、填空题1数据结构是彼此具有一定关系的数据元素的集合。可分为逻辑结构和物理结构两个方面。2算法的效率包括两方面，即时间复杂度和空间复杂度。所谓时间复杂度是指一个算法所需运算次数的多少，所谓空间复杂度是指一个算法所需辅助内存空间的大小。3对于两个n阶矩阵相乘,用C语言描述算法,则相应的时间复杂度是O（n3）。4线性表的链式存储结构结点中存储数据元素本身的域称为数据域，存储直接后继元素存储位置的域称为指针域。线性表是n个同类型数据元素的有限序列。5在单链表中,指针p所指结点为最后一个结点的条件是p->next=null。在单向链表结构中，空表的条件为hanext=NULL,而在循环链表结构

2、中，空表的条件是hanext=ha.6栈的操作原则是后进先出(LIFO)，队列的操作原则是先进先出（FIFO）。栈是只能在表的一端进行插入和删除运算的线性表。队列是中能在表的一端进行插入，而在另一端进行删除的线性表。能进行插入的这一端称为队列的尾，能进行删除的一端称为队列的头。7结点所拥有的子树的个数称为结点的度，树中结点的最大层数称为树的深度。8树有三种常用的存储结构，即_孩子链表法、孩子兄弟链表法和双亲表示法。9设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是r->next=s；r=s；r->next=null。10哈夫曼树是带权路径度最短

3、的树，通常权值较大的结点离根较近。11.字符串“beijing”的长度为8。字符串“X123”的长度4。12.树中结点所拥有的子树的个数称为结点的度，树中结点的最大层数称为树的深度。二、选择题1数据结构是（ D ）。（A）一种数据类型（B）数据的存储结构 （C）一组性质相同的数据元素的集合 （D）相互之间存在一种或多种特定关系的数据元素的集合2算法分析的目的是（ B ）。（A）辨别数据结构的合理性（B）评价算法的效率（C）研究算法中输入与输出的（D）段鉴别算法的可读性3在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ）。（A）插入 （B）删除 （C）排序 （D）定位4设串s1

4、=”data structures with java”,s2=“it”,则子串定位函数index(s1,s2)的值为（ D ）。(A) 15(B)16(C)17(D)185在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系（ B ）。（A）不一定相同 （B）都相同（C）都不相同 （D）互为逆序6. 树最适合用来表示 ( C ).(A) 有序数据元素 (B) 无序数据元素 (C) 元素之间具有分支层次关系的数据(D) 元素之间无联系的数据7.深度为6(根的层次为1)的二叉树至多有（ D ）个结点。(A) 64 (B)32 (C)31 (D)638.串是任意有限个（ C ）。(A)

5、 符号构成的序列 (B)符号构成的集合 (C) 字符构成的序列(D) 字符构成的集合9若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用（ D ）存储方式最节省时间。(A) 单链表 (B) 双链表 (C)单向循环(D)顺序表10将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次对结点编号,根结点的编号为1,编号为49的结点X的双亲编号为（ A ）。(A) 24(B) 25 (C)23 (D) 2611.设有字符串S=“thisisastring”则下列哪一个不是S的子串（ C ）。（A）t=“this” （B）u=“isa” （C） v=“astin” （D）w

6、=“string”12设串s1 =”data structures with java”,s2=“ture”,则子串定位函数index(s1,s2)的值为（ C ）。(A) 11(B)12(C)10(D)1813. 设串s1 =”data structures with java”,s2=“java”,则子串判断函数equal(s1,s2)的值为（ A）。(A) 0(B)1 (C)2 (D)314. 设串s1 =”data structures with java”,s2=“with”,则子串判断函数equal(s1,s2)的值为（ A ）。(A) 0(B)1 (C)2 (D)315. 设串s

7、1 =”data structures with java”,则求子串判断函数substr(s1,5,4)的值为（ C ）。(A) with(B)data(C)stru (D)truc16. 设串s1 =”data structures with java”,则求子串判断函数substr(s1,10,4)的值为（ D ）。(A) with(B)data(C)stru (D)ture17设串s1 =”123”,s2=“ture”,则执行函数concat(s1,s2)的值为（ A ）。(A)123ture(B)true123(C)1 (D)018设串s1 =”bei”,s2=“jing” ,则执行

8、函数concat(s1,s2)的值为（ C ）。(A) 1(B)0 (C)beijing(D)jingbei19.在二叉树的第i层上最多有（ A ）个结点。(A) 2i-1(B)2i-1 (C)2i(D) 2i+120.深度为k的二叉树至多有（ B ）个结点。(A) 2k-1(B)2k-1 (C)2k(D) 2k+1三、判断题 1.数据是能输入到计算机中并能被计算机处理的一切对象。只能是整数或实数。（×）2.线性表强调两个特性。一个是强调每个数据元素须是同类型的数据，另一个是强调数据元素的有序性。（）3.中缀表达式转换为相应的后缀表达式的原则是：先乘除后加减，先括号内后括号外，同级运

9、算先左后右的运算次序。（）4.在程序设计语言中，一个能直接或间接调用自身的过程（或函数）称为递归过程（或函数）。（）5队列在现实社会中的应用有：多任务操作系统、等待CPU的处理等。（）6在稀疏矩阵中，非零元素一个挨一个存储的同时，必须同是将它的行号和列号存储起来形成三元组结合存储。（）7在很多实用的串处理系统中，采用一种“堆”结构进行动态存储分配的方法。（）8树中度为0的结点称为叶结点。（）9同为一个双亲结点的孩子彼此称为兄弟结点。（）10二叉树的遍历就是对树中每个结点都访问到且只访问一次。（）四、问答题 （共25分）1.数据结构怎样定义及其研究范围是什么答：数据结构是彼此具有一定关系的数据元

10、素的集合。数据结构研究数据的逻辑结构和物理结构，并在这种结构上定义相关的运算，设计并实现相应的算法，分析算法的效率。2.将中缀表达式（8+3*6）/（2+3*5-4）转化为相应的后缀表达式。答：836*+235*+4-/3编程实现求子串位置的定位函数。答：int index(s,t)Struct string s ,t ;i=1;j=1;while(i<=&&j<=Ifi=j)i=i+1;J=j+1;Else i=i-j+2;j1;If(j>Return;ElseReturn(0);4. 编程实现判断两个函数是否相等的函数，若相等则返回函数值为1，否则为0答：int equal(s,t)Struct string s,t;If!=Return(0);ElseFor(i=0;i&