数据结构复习试题和答案解析12级

1、.一、选择题。计算机识别.存储和加工处理的对象被统称为_A_。A.数据 B.数据元素 C.数据结构 D.数据类型 数据结构通常是研究数据的_ A_及它们之间的联系。A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 不是数据的逻辑结构是_ A_。A.散列结构 B.线性结构 C.树结构 D.图结构 数据结构被形式地定义为,其中D是_ B_的有限集,R是_ C_的有限集。A.算法 B.数据元素 C.数据操作 D.逻辑结构 组成数据的基本单位是_ A_。A.数据项 B.数据类型C.数据元素 D.数据变量 设数据结构A=,其中D=1,2,3,4,R=r,r=,则数据结构A是_ A_。A

2、.线性结构 B.树型结构 C.图型结构 D.集合 数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为_ C_。A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构 在数据结构的讨论中把数据结构从逻辑上分为_ A_。A.内部结构与外部结构 B.静态结构与动态结构C.线性结构与非线性结构 D.紧凑结构与非紧凑结构 对一个算法的评价,不包括如下_ B_方面的内容。A.健壮性和可读性 B.并行性 C.正确性 D.时空复杂度 算法分析的两个方面是_ A_。A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性 线性表是具有n个_ C_的

3、有限序列n0。A.表元素 B.字符 C.数据元素 D.数据项 线性表的存储结构是一种_ B_的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.HASH存取 在一个长度为n 的顺序表中,向第i个元素1 i n之前插入一个新元素时,需要向后移动_ B_个元素。A.n-i B.n-i+1 C.n-i-1 D.i 链表是一种采用_ B_存储结构存储的线性表；A.顺序 B.链式 C.星式 D.网状 下面关于线性表的叙述错误的是_ D_。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存

4、储便于插入和删除操作的实现 设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B之间插入结点X的操作序列为_ B_。A. s-next=p-next；p-next=-s；B. q-next=s； s-next=p；C. p-next=s-next；s-next=p；D. p-next=s；s-next=q； 设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为_ A_。A. p-next=p-next-next B. p=p-nextC. p=p-next-next D. p-next=p下列说法哪个正确？_ D _A.

5、堆栈是在两端操作、先进后出的线性表B. 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表栈和队列的共同点是_ C _。A. 都是先进后出 B. 都是先进先出C. 只允许在端点处插入和删除元素 D. 没有共同点栈与一般线性表的区别主要在_D_。A、元素个数 B、元素类型 C、逻辑结构 D、插入、删除元素的位置链栈与顺序栈相比,比较明显的优点是_D_。A、插入操作更加方便 B、删除操作更加方便C、不会出现下溢的情况 D、不会出现上溢的情况 以下数据结构中哪一个是非线性结构_ D _。A.队列B.栈C.线性表D.二叉树若已知一个栈的入

6、栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1=n,则pi为_ C _。A. iB. B. n=i C. n-i+1D.不确定当利用大小为N的一维数组顺序存储一个栈时,假定用top=N表示栈空,则向这个栈插入一个元素时,首先应执行_ B _语句修改top指针。A. top+ B. top- C. top=0D. top 4个元素进S栈的顺序是A,B,C,D,经运算POP后,栈顶元素是_ C _。A. AB. BC. CD. D一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是_ C _。A. edcbaB. decbaC. dceabD. abcde设输入序列是

7、1、2、3、n,经过栈的作用后输出序列的第一个元素是n,则输出序列中第i个输出元素是_ C _。A. n-iB. n-1-iC. n+1-iD.不能确定字符A、B、C、D依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成_ B _个不同的字符串？A. 15B. 14C. 16D. 21 设指针变量top指向当前链式栈的栈顶,则删除栈顶元素的操作序列为_ D _。A. top=top+1; B. top=top-1; C. top-next=top; D. top=top-next; 设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进

8、入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是_ C _。A. 6B. 4C. 3D. 2若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3。当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为_B_。A. 1和5B. 2和4C. 4和2D. 5和1设顺序循环队列Q0：M-1的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为_ C_。A. R-FB. F-RC. %MD. %M设指针变量front表示链式队列的队头指针,指针

9、变量rear表示链式队列的队尾指针,指针变量s指向将要入队列的结点X,则入队列的操作序列为_ C_。A. front-next=s；front=s；B. s-next=rear；rear=s；C. rear-next=s；rear=s；D. s-next=front；front=s； 如下陈述中正确的是_ A _。A. 串是一种特殊的线性表B. 串的长度必须大于零C. 串中元素只能是字母D. 空串就是空白串 下列关于串的叙述中,正确的是_ D _。A. 串长度是指串中不同字符的个数B. 串是n个字母的有限序列C. 如果两个串含有相同的字符,则它们相等D. 只有当两个串的长度相等,并且各个对应位

10、置的字符都相符时才相等 字符串的长度是指_ C _。A. 串中不同字符的个数B. 串中不同字母的个数C. 串中所含字符的个数D. 串中不同数字的个数 两个字符串相等的充要条件是_ C _。A. 两个字符串的长度相等B. 两个字符串中对应位置上的字符相等C. 同时具备和两个条件 D. 以上答案都不对 串是一种特殊的线性表,其特殊性体现在_ B _。A. 可以顺序存储B. 数据元素是一个字符C. 可以链接存储D. 数据元素可以是多个字符 设有两个串p和q,求q在p中首次出现的位置的运算称作_ B _。A. 连接B. 模式匹配C. 求子串D. 求串长 设串sI=ABCDEFG,s2=PQRST,函数

11、con返回x和y串的连接串,subs返回串s的从序号i的字符开始的j个字符组成的子串,len返回串s的长度,则consubss1,2,1en,subssl,len,2的结果串是_ D _。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF 函数substr的返回值为_ A _。A. STRUCTUREB. DATA C. ASTRUCTUR D. DATASTRUCTURE 设串S=I AM A TEACHER!,其长度是_ D _。A. 16B. 11C. 14D. 15 假定在一棵二叉树中,双分支结点数为15个,单分支结点数为32个,则叶子结点数为_B_。A. 15

12、 B. 16 C. 17 D. 47 假定一棵二叉树的结点数为18个,则它的最小高度_B_。A. 4 B. 5 C. 6 D. 18 在一棵二叉树中第五层上的结点数最多为_C_。A. 8 B. 15 C. 16 D. 32 在一棵具有五层的满二叉树中,结点总数为_A_。A. 31 B. 32 C. 33 D. 16 已知8个数据元素为,按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为_B_。A. 1 B. 2 C. D. 4 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为_C_。A. 23 B. 37 C. 44 D. 46 在树中除根结点外,

13、其余结点分成m个_A_的集合T1,T2,T3.Tm,每个集合又都是树,此时结点T称为Ti的父结点,Ti称为T的子结点。A. 互不相交 B. 可以相交C. 叶结点可以相交 D. 树枝结点可以相交 如果结点A有三个兄弟,而且B是A的双亲,则B的出度是_B_。A. 3 B. 4 C. 5 D. 1 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的_B_倍。A. 1/2 B. 1 C. 2 D. 4 具有n个顶点的无向完全图,边的总数为_D_条。A. n-1 B. n C. n+1 D. n*/2 在无向图G的邻接矩阵A中,若Ai,j等于1,则Aj,i等于_C_。A. i+j B. i-j

14、C. 1 D. 0 图的深度优先或广度优先遍历的空间复杂性均为_A_。A. O B. O C. O D. O 请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中,用折半法查找关键码12需做_ C _次关键码比较。A.2 B.3 C.4 D.5 对线性表进行折半查找时,必须要求线性表 _ C _。A. 以顺序方式存储 B. 以链接方式存储C. 以顺序方式存储,且结点按关键字有序排列D. 以链接方式存储,且结点按关键字有序排列 设二叉排序树中有n个结点,则在二叉排序树的平均查找长度为_ B _。A. O B. O C. O D. O 依次插入序列后建立的二叉搜索树中,查找元

15、素35要进行_ A _元素间的比较。A.4次B.5次C.7次D.10次 设散列表中有m个存储单元,散列函数H= key % p,则p最好选择_ B _。A. 小于等于m的最大奇数B. 小于等于m的最大素数C. 小于等于m的最大偶数D. 小于等于m的最大合数 _ D _是HASH查找的冲突处理方法。A.求余法 B. 平方取中法 C. 二分法 D. 开放地址法 当的值较小时,散列存储通常比其他存储方式具有_ B _的查找速度。A. 较慢B. 较快C. 相同 D. 不确定 对线性表进行折半查找最方便的存储结构是_ B _。A顺序表 B有序的顺序表C链表 D有序的链表 如果要求一个线性表既能较快的查找

16、,又能适应动态变化的要求,可以采用_ D _查找方法。A分块 B顺序 C折半 D散列 散列函数有一个共同性质,即函数值应按_ C _取其值域的每一个值。A最大概率 B最小概率 C同等概率 D平均概率 下述排序算法中,稳定的是_ B _。A.直接选择排序 B. 直接插入排序 C.快速排序 D.堆排序 下列排序算法中,_ A _需要的辅助存储空间最大。A.快速排序B.插入排序C.希尔排序D.基数排序 下列各种排序算法中平均时间复杂度为O是_ D _。A. 快速排序 B. 堆排序 C. 归并排序 D. 冒泡排序 在基于关键码比较的排序算法中,_ C _算法在最坏情况下,关键码比较次数不高于O。A.

17、起泡排序B. 直接插入排序C. 二路归并排序D. 快速排序 一组记录为46,79,56,38,84,40,则采用冒泡排序法按升序排列时第一趟排序结果是_ B _ 。A. 46,79,56,38,40,84 B.46,56,38,79,40,84C. 38,40,46,56,84,79 D.38,46,79,56,40,84 每次从无序表中取出一个元素,把它插入到有序表中的适当位置,此种排序方法叫做_ A _ 排序。A. 插入 B. 堆 C.快速 D.归并 每次从无序表中挑选出一个最小或最大元素,把它交换到有序表的一端,此种排序方法叫做_ B _排序。A. 插入 B. 堆 C.快速 D.归并 设

18、一组初始记录关键字序列,以第一个记录关键字5为基准进行一趟快速排序的结果为_ C _。A. 2,3,5,8,6B. 3,2,5,8,6C. 3,2,5,6,8D. 2,3,6,5,8 下列排序方法中,哪一种方法的比较次数与纪录的初始排列状态无关_ D _。A. 直接插入排序 B. 起泡排序C. 快速排序 D. 直接选择排序 设有关键码初始序列Q,H,C,Y,P,A,M,S,R,D,F,X,新序列F,H,C,D,P,A,M,Q,R,S,Y,X是采用_ C _ 方法对初始序列进行第一趟扫描的结果。A. 直接插入排序 B二路归并排序C以第一元素为分界元素的快速排序 D基数排序 在待排序文件已基本有序

19、的前提下,下述排序方法中效率最高的是_ C _。A. 直接插入排序 B. 直接选择排序C 快速排序 D 归并排序 若需在O的时间内完成对数组的排序,且要求排序是稳定的,则可选排序方法是_ C _ 。A. 快速排序 B 堆排序C 归并排序 D 直接插入排序 将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是_ B _。A n B 2n-1 C 2n D n-1 下列排序算法中,_ C _ 算法可能会出现下面情况：初始数据有序时,花费的间反而最多。A. 堆排序 B冒泡排序 C快速排序 D SHELL排序二、填空题。 数据结构是一门研究非数值计算的程序设计问题中计算机的数据以及它们之间的

20、关系和运算等的学科。 数据结构包括数据的逻辑结构结构和物理结构结构。 数据结构从逻辑上划分为三种基本类型：_线性数据结构_、_树型结构_和_图结构_。 数据的物理结构被分为_顺序存储_、_链式存储_、_索引存储_和_散列表Hash存储_四种。 一种抽象数据类型包括_变量的取值范围_和_操作的类别_两个部分。 数据的逻辑结构是指数据元素间的逻辑关系,数据的存储结构是指数据元素存储方式或者数据元素的物理关系。 数据结构是指数据及其相互之间的_关系_。当结点之间存在M对NM：N的联系时,称这种结构为_网状结构_。当结点之间存在1对N1：N的联系时,称这种结构为_树结构_。 对算法从时间和空间两方面进

21、行度量,分别称为空间复杂度和时间复杂度分析。 算法的效率可分为_空间_效率和_时间_效率。 fori=1,t=1,s=0；i t=t*i；s=s+t；的时间复杂度为_。 线性表是n个元素的_有限序列_。 线性表的存储结构有_顺序存储和链式存储_。 设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为_,在链式存储结构上实现顺序查找的平均时间复杂度为_ O_。 设顺序线性表中有n个数据元素,则第i个位置上插入一个数据元素需要移动表中_ n-i+1_个数据元素；删除第i个位置上的数据元素需要移动表中_ n-i_个元素。 若频繁地对线性表进行插入与删除操作,该线性表应采用_链式

22、_存储结构。 链式存储结构中的结点包含_数据_域和_指针_域。 对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为_,在表尾插入元素的时间复杂度为_。栈的插入和删除只能在栈的栈顶进行,后进栈的元素必定先出栈,所以又把栈称为_ FILO _表；队列的插入和删除运算分别在队列的两端进行,先进队列的元素必定先出队列,所以又把队列称为_ FIFO _表。s= I am a man 长度为_10_。 s1=hello ,s2=boy,s1,s2连接后为：_ hello boy _。 s=this is the main string,sub=string,strindex是：_13_。 i

23、nt a1010,已知a=1000,sizeof=2,求a33地址：_1066_。设有两个串p和q,求q在p中首次出现的位置的运算称为_模式匹配_。在树型结构中,树根结点没有_前趋_结点,其余每个结点有且仅有_一_个前驱结点；树叶结点没有_后继_结点,其余每个结点的_后继_结点数不受限制。在一棵二叉树中,度为0的结点的个数为n0 ,度为2的结点的个数为n2 ,则：n0 =_n2 +1_。由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树,则带权路径长度为_55_。在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的_度数_,对于有向图来说等于该顶点的_出度

24、数_。假定一个图具有n个顶点和e条边,则采用邻接矩阵表示的空间复杂性为_O _,采用邻接表表示的空间复杂性为_O _。对于长度为n的线性表,若进行顺序查找,则时间复杂度为_ O_；若采用折半法查找,则时间复杂度为_ O_。 假设在有序线性表A1.20上进行折半查找,则比较一次查找成功的结点数为_1_,则比较二次查找成功的结点数为_2_,则比较三次查找成功的结点数为_4_,则比较四次查找成功的结点数为_8_,则比较五次查找成功的结点数为_5_,平均查找长度为_ log2-1_。在一棵二叉排序树中,每个分支结点的左子树上所有结点的值一定_小于_该结点的值,右子树上所有结点的值一定_大于_该结点的值

25、。对一棵二叉排序树进行中序遍历时,得到的结点序列是一个_增序序列_。对于线性表70,34,55,23,65,41,20进行散列存储时,若选用HK=K %7作为散列函数,则散列地址为0的元素是_70_,散列地址为6的是_34,20,55_。在线性表的散列存储中,装填因子又称为装填系数,若用m表示散列表的长度,n表示待散列存储的元素的个数,则等于_ n/m _。 散列表中解决冲突的两种方法是_开放地址法_和_链地址法_。在散列存储中,装填因子a的值越大,则_产生冲突的可能性就越大_；a的值越小,则_产生冲突的可能性就越小_。散列法存储的基本思想是由_关键码直接_决定数据的存储地址。构造哈希函数的方

26、法有_直接定址法,数字分析法,平方取中法,折叠法,除留余数法,随机数法_。在分块查找中首先查找 _索引_,然后再查找相应的_块_。散列表的查找效率主要取决于散列表造表时选择的_哈希函数_ 和_装填因子_。 对两棵具有相同关键字集合而形状不同的二叉排序树,_中序_ 遍历它们得到的序列的顺序是一样的。 当待排序的记录数较大,排序码较随机且对稳定性不作要求时,宜采用_快速_排序；当待排序的记录数较大,存储空间允许且要求排序是稳定时,宜采用_归并_排序。 在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_ O_,整个堆排序过程的时间复杂度为_ O_。 当向一个大根堆插入一个具有最大值的元素时,

27、需要逐层_向上_调整,直到被调整到_根结点_位置为止。 对一组初始关键字序列40,50,95,20,15,70,60,45,10进行冒泡排序,则第一趟需要进行相邻记录的比较的次数为_8_,在整个排序过程中最多需要进行_8_趟排序才可以完成。 在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中,平均比较次数最少的排序是_快速_,需要内存容量最多的是_归并_。 堆排序是不稳定,空间复杂度为 _ O_。在最坏情况下,其时间复杂度也为_ O_。 若待排序的文件中存在多个关键字相同的记录,经过某种排序方法排序后,具有相同关键字的记录间的相对位置保持不变,则这种排序方法是_稳定_的排序方法。

28、在对一组记录进行直接插入排序时,当把第7个记录60插入到有序表时,为寻找插入位置需比较_3_次。 二路归并排序的时间复杂度是_ O_。 对于n个记录的集合进行归并排序,所需的附加空间消耗是_ O_。 设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序,则_冒泡排序_最省时间,_快速排序_最费时间。三、判断题。1数据元素是数据的最小单位。2数据项是数据的基本单位。3顺序存储的线性表可以随机存取。4线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此,是属于同一数据对象。5在单链表中,任何两个元素的存储位置之间都有固定

29、的联系,因为可以从头结点查找任何一个元素。6在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构。7链表的每个结点中,都恰好包含一个指针。8数组是同类型值的集合。 9使用三元组表示稀疏矩阵的元素,有时并不能节省存储时间。10. 线性表可以看成是广义表的特例,如果广义表中的每个元素都是原子,则广义表便成为线性表。11. 由树转换成二叉树,其根结点的右子树总是空的。12. 后序遍历树和中序遍历与该树对应的二叉树,其结果不同。13. 若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点。14.若一个树叶是某子树的中序

30、遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点。15. 已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点是哪一个。16. 在哈夫曼编码中,当两个字符出现的频率相同时,其编码也相同,对于这种情况应作特殊处理。17. 有回路的图不能进行拓扑排序。18. 连通分量是无向图中的极小连通子图。 19. 散列法存储的基本思想是由关键码的值决定数据的存储地址。20. 散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。21. m阶B-树每一个结点的子树个数都小于或等于m。22. 中序遍历二叉排序树的结点就可以得到排好序的结点序列。23. 在

31、二叉排序树上插入新的结点时,不必移动其它结点,仅需改动某个结点的指针,由空变为非空即可。24. 当待排序的元素很多时,为了交换元素的位置,移动元素要占用较多的时间,这是影响时间复杂性的主要因素。25. 对于n个记录的集合进行快速排序,所需要的平均时间是O。26. 对于n个记录的集合进行归并排序,所需要的平均时间是O。27. 堆中所有非终端结点的值均小于或等于大于或等于左右子树的值。28. 磁盘上的顺序文件中插入新的记录时,必须复制整个文件。29. 在索引顺序文件中插入新的记录时,必须复制整个文件。30. 索引顺序文件是一种特殊的顺序文件,因此通常存放在磁带上。四、简答题。1. 简述下列术语：数

32、据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。数据：数据是信息的载体,是计算机程序加工和处理的对象,包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位,数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理,一个数据元素可由若干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据元素间的关系。数据存储结构：数据的物理结构表示数据元素的存储方式或者数据元素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。算法：是对特定问题求解步骤的一种描述,是指令的有限序列。2.简述栈和线性表的

33、区别。答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。而栈只是一种特殊的线性表。栈只能在线性表的一端插入称为入栈,push或者读取栈顶元素或者称为弹出、出栈。3.简述栈和队列这两种数据结构的相同点和不同点。答：相同点：栈和队列都是特殊的线性表,只在端点处进行插入,删除操作。不同点：栈只在一端栈顶进行插入,删除操作；队列在一端top删除,一端插入。4.如果进栈的元素序列为A,B,C,D,则可能得到的出栈序列有多少种? 写出全部的可能序列。答：可能序列有14种：ABCD; ACBD; ACDB; ABDC; ADCB; BACD; BADC; BCAD; BCDA

34、; BDCA; CBAD; CBDA; CDBA; DCBA。5. 如果进栈的元素序列为1,2,3,4,5,6,能否得到4,3,5,6,1,2和1,3,5,4,2,6的出栈序列?并说明为什么不能得到或如何得到。答：不能得到4,3,5,6,1,2,最先出栈的是4,则按321的方式出,不可能得到1在2前的序列,可以得到1,3,5,4,2,6,按如下方式进行push, pop, push, push, pop, push, push, pop, pop, pop, push, pop。6. 设s=I AM A STUDENT,t=GOOD,q=WORKER。求：StrLength , StrLeng

35、th ,SubStr,SubStr,StrIndex,StrIndex ,StrRep,SubStr SubStr ,StrConcat t,SubStr。答：StrLength =14, StrLength =4, SubStr= STUDENT, SubStr=O,StrIndex=3, StrIndex =0, StrRep= I AM A WORKER,7. 简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。答：空串：不含任何字符；空格串：所含字符都是空格。串变量和串常量:串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可

36、以改变和重新赋值的。主串与子串：子串是主串的一个子集。串变量的名字与串变量的值:串变量的名字表示串值的标识符。8. 设有二维数组A,每个元素占6个字节存储,顺序存放,A的起地址为1000,计算：数组A的体积；数组的最后一个元素A的起地址；按行优先存放时,元素A1,4的起地址；按列优先存放时,元素A4,7的起地址。6*8*6=2881000+47*6=12821000+*8=10961000+*8=13689. 分别画出含三个结点的无序树与二叉树的所有不同形态。答：无序树形态如下：二叉树形态如下：10. 分别写出图1中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。答：先序遍历序列:AB

37、DEHICFJG 中序遍历序列:DBHEIAFJCG 后序遍历序列:DHIEBJFGCA11. 试找出分别满足下列条件的所有二叉树。 先序序列与中序序列相同。 后序序列与中序序列相同。 先序序列与后序序列相同。答： 先序序列和中序序列相同：空树或缺左子树的单支树； 后序序列和中序序列相同：空树或缺右子树的单支树； 先序序列和后序序列相同：空树或只有根结点的二叉树。12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA,试画出这棵二叉树。答：这棵二叉树为:13. 分别写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。答：先序遍历序列:ABDGCEHF中

38、序遍历序列:DGBAEHCF后序遍历序列:GDBHEFCA14. 给定权值,构造的哈夫曼树。答：哈夫曼树为:15. 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为7,19,2,6,32,3,21,10,试为这8个设计哈夫曼编码。答：哈夫曼树为:在上述哈夫曼树的每个左分支上标以0,右分支上标以1,并设这8个字母分别为A、B、C、D、E、F、G和H,则它们的哈夫曼树为分别为:A：0000 B：10 C：00110 D：0010 E：01 F：00111G：11 H：000116. 画出无向图G1的邻接矩阵和邻接表示意图,并写出每个顶点的度。答：1邻接矩阵:2邻接链表：3每个顶点的

39、度：顶点 度 V1 3 V2 3 V3 2 V4 3 V5 3 17. 画出有向图G2的邻接矩阵、邻接表和逆邻接表示意图,并写出每个顶点的入度和出度。答：1邻接链表：2逆邻接链表：3 顶点 入度 出度 V1 3 0 V2 2 2 V3 1 2 V4 1 3 V5 2 1 V6 2 318. 对应图G3,写出从v1出必的深度优先遍历序列和广度优先遍历序列各三个。答：深度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V5 V4 V2; V1 V4 V3 V5 V2广度优先查找遍历序列：V1 V2 V3 V4 V5; V1 V3 V2 V4 V5; V1 V4 V3 V2 V519. 何谓二叉排序树?答：一棵二叉排序树或者是一棵空树,或者是一棵同时满足下列条件的二叉树： 若它的左子树不空,则左子树上所有结点的键值均小于它根结点键值。 若它的右子树不空,则右子树上所有结点的键值均大于它根结点键值。 它的左、右子树也分别为二叉排序树。20. 顺序查找时间为O,二分查找时间为O,散列查找时间为O,为什么有高效率的查找方法而不放弃低效率的方法?