大数据的结构复习的题目及问题解释

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

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

3、一种的存储结构。A.随机存取B.顺序存取C.索引存取D.HASH存取(13)在一个长度为的顺序表中，向第i个元素(1 i 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 ;(17)设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为AA. p-n ext=p-n ext- nextB. p=p-nextC. p=p-n ext- nextD. p_n ext=p(18)下列说法哪个正确？DA. 堆栈是在两端操作、先进后出的线性表B.

4、 堆栈是在一端操作、先进先出的线性表C. 队列是在一端操作、先进先出的线性表D. 队列是在两端操作、先进先出的线性表(19) 栈和队列的共同点是 C。A. 都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点(20) 栈与一般线性表的区别主要在 D。A、元素个数B 、元素类型 C 、逻辑结构 D、插入、删除元素的位置(21) 链栈与顺序栈相比，比较明显的优点是 D。A、插入操作更加方便B删除操作更加方便A.队列B.栈C.线性表D.二叉树(23)C若已知一个栈的入栈序列是1，。2，3,，n，其输出序列为 p1，p2，p3,，pn，若p1= n，贝U pi为A. iB. B.

5、 n=iC. n-i+1D.不确定(24)当利用大小为N的一维数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个兀素时，首先应执行B语句修改top指针。A. top+B. top-C. top=0D. top(25) 4 个兀素进S栈的顺序是A,B,C,D，经运算POP(S)后，栈顶兀素是C。A. AB. BC. CD. D(26)一个栈的输入序列是a,b,c,d,e,则栈的不可能的输出序列是C。A. edcbaB. decbaC.dceabD.abcde(27)设输入序列是1、2、3、n，经过栈的作用后输出序列的第一个兀素是n，则输出序列中第i个输出元素是C。A. n-iB.

6、 n-1-iC. n+1-iD.不能确定DO(28)字符AD依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成CB个不同的(22)以下数据结构中哪一个是非线性结构C不会出现下溢的情况D不会出现上溢的情况字符串?A. 15B. 14C. 16D. 21(29)设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为A. top=top+1;B. top=top-1;C. top-n ext=top;D. top=top-n ext;(30)设栈S和队列Q的初始状态为空，元素 E1、E2、E3、E4、E5和E6依次通过栈S, 个元素出栈后即进入队列Q若6个元素出列的顺序为 E2

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

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

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

10、返回x和y串的连接串,subs(s,i,j) 返回串s的从序号i的 字符开始的j个字符组成的子串，len(s)返回串s的长度，则 con(subs(s1,2,1en(s2) ，subs(sl,len(s2) ，2) 的结果串是D _。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF(41) 函数 substr(“ DATASTRUCTU”E 5，9)的返回值为 _ A。A. STRUCTUREB. “DATAC. “ ASTRUCTURD. “ DATASTRUCTURE(42) 设串 S=” I AM A TEACHER! ”，其长度是 D。A. 16B. 11C.

11、 14D. 15(43) 假定在一棵二叉树中，双分支结点数为15个，单分支结点数为 32个，则叶子结点数为 B。A. 15 B. 16 C. 17 D. 47(44) 假定一棵二叉树的结点数为18个，则它的最小高度 B。A. 4 B. 5 C. 6 D. 18(45) 在一棵二叉树中第五层上的结点数最多为 C。A.8 B. 15 C. 16 D. 32(46) 在一棵具有五层的满二叉树中，结点总数为 A。A. 31 B. 32 C. 33 D.16(47) 已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为

12、B。A. 1B. 2 C. D. 4(48) 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 C。A. 23 B. 37 C. 44 D. 46(49) 在树中除根结点外，其余结点分成 m (m0)个A的集合T1,T2,T3.Tm,每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点(1 i m)。A.互不相交B.可以相交C叶结点可以相交D.树枝结点可以相交(50) 如果结点A有三个兄弟，而且B是A的双亲，贝U B的出度是 B。A. 3B. 4 C. 5 D. 1(51) 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。A. 1/2

13、B. 1 C. 2 D. 4(52) 具有n个顶点的无向完全图，边的总数为 D条。A. n-1 B. n C. n+1 D. n *( n-1)/2(53) 在无向图G的邻接矩阵A中，若Ai,j 等于1,则Aj,i 等于C。A. i+j B. i-j C. 1D. 0(54) 图的深度优先或广度优先遍历的空间复杂性均为A 。(访问标志位数组空间)A. 0(n) B. 0(e) C. 0(n-e)D. 0(n+e)(55) 请指出在顺序表2、5、7、10、14、15、18、23、35、41、52中，用折半法查找关键码 12需做C _次关键码比较。A.2B.3C.4D.5(56) 对线性表进行折半

14、查找时，必须要求线性表 C。A.以顺序方式存储B.以链接方式存储C. 以顺序方式存储，且结点按关键字有序排列D. 以链接方式存储，且结点按关键字有序排列(57)设一叉排序树中有 n个结点，则在一叉排序树的平均查找长度为B。A. O(1)B. O(log 2n)C. O( n)2D. O(n )(58)依次插入序列(50 , 72, 43,85, 75,20, 35,45, 65, 30)后建立的二叉搜索树中，查找兀素35要进行 A兀素间的比较。A.4次B.5次C.7次D.10 次(59)设散列表中有m个存储单元，散列函数H(key)=key % p ，则p最好选择B。A.小于等于白人戸._.来

15、&B.m的最大奇数小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数(60).D是HASH查找的冲突处理方法。A.求余法 B.平方取中法C. 二分法 D. 开放地址法(61) 当a的值较小时，散列存储通常比其他存储方式具有 B 的查找速度。A.较慢B.较快C.相同 D. 不确定(62) 对线性表进行折半查找最方便的存储结构是 B。A.顺序表B.有序的顺序表C.链表D.有序的链表如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用D查找方法。A.分块 B .顺序 C .折半 D .散列散列函数有一个共同性质，即函数值应按C取其值域的每一个值。A.最大概率B .最小

16、概率 C .同等概率 D .平均概率下述排序算法中，稳定的是B 。A.直接选择排序B.直接插入排序C.快速排序D.堆排序下列排序算法中， A需要的辅助存储空间最大。A.快速排序B.插入排序C.希尔排序D.基数排序下列各种排序算法中平均时间复杂度为0(n2)是_ D。A.快速排序B.堆排序C.归并排序D.冒泡排序在基于关键码比较的排序算法中， C算法在最坏情况下，关键码比较次数不高于O(nlog2n)。A.起泡排序B.直接插入排序C.二路归并排序D.快速排序一组记录为46 , 79 , 56, 38, 84, 40，则采用冒泡排序法按升序排列时第一趟排序结果是B 。A. 46,79,56,38,

17、40,84B.46,56,38,79,40,84C. 38,40,46,56,84,79D.38,46,79,56,40,84每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做A 排序。A.插入 B. 堆 C. 快速 D. 归并每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做B 排(63)(64)(65)(66)(67)(68)(69)(70)(71) 序。(72)C_(73)(74)采用(75)A.插入 B. 堆 C. 快速D. 归并设一组初始记录关键字序列(5 , 2, 6, 3, 8),以第一个记录关键字5为基准进行一趟快速排序的结

18、果为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 QR,S , Y,X是_ C 方法对初始序列进行第一趟扫描的结果。A.直接插入排序B.二路归并排序C.以第一元素为分界元素的快速排序D.基数排序在待排序文件已基本有序的前提下，下述排序方法中效率最高的是_ C。A.直接插入排序B

19、.直接选择排序C.快速排序D .归并排序(76) 若需在0(nlog 2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选排序方法是CA.快速排序B堆排序C.归并排序D直接插入排序(77) 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是_ B。A. n B 2n-1 C . 2n D .n-1(78) 下列排序算法中， C 算法可能会出现下面情况：初始数据有序时，花费的间反而最多。A. 堆排序 B冒泡排序C快速排序D . SHELL排序、填空题。(每空1分，共10分)(1) 数据结构是一门研究非数值计算的程序设计问题中计算机的 数据以及它们之间的_关系和运算等的学科。(2

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

21、两方面进行度量，分别称为 空间复杂度和时间复杂度 分析。(9) 算法的效率可分为 空间效率和时间效率。(10) for(i=1 , t=1 , s=0; i=n ; i+) t=t*i ; s=s+t ; 的时间复杂度为 O (n)。(11) 线性表是n个元素的 有限序列。(12) 线性表的存储结构有 顺序存储和链式存储 。(13) 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为O (n)，在链式存储结构上实现顺序查找的平均时间复杂度为 O(n) 。(14) 设顺序线性表中有 n个数据元素，则第i个位置上插入一个数据元素需要移动表中n-i+1 个数据元素；删除第i个

22、位置上的数据元素需要移动表中n-i 个元素。(15) 若频繁地对线性表进行插入与删除操作，该线性表应采用 链式存储结构。(16) 链式存储结构中的结点包含 数据域和指针域。(17) 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_0(1)，在表尾插入元素的时间复杂度为 O (n) 。(18) 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为FIL0 表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为FIFO表。(19) s= ” I am a man ” 长度为10 。(20) s1= ” hello “ ,s2

23、= ” boy”，s1,s2 连接后为： hello boy 。(21) s= ” this is the main string” ,sub= ” string ” ,strindex(s,sub)是: 13。(22) int a1010,已知 a=1000,sizeof(int)=2, 求 a33 地址： 1066 。(23) 设有两个串p和q,求q在p中首次出现的位置的运算称为 模式匹配 。(24) 在树型结构中，树根结点没有 前趋结点，其余每个结点有且仅有 一个前驱结点；树叶结点没有 后继结点，其余每个结点的 后继结点数不受限制。(25) 在一棵二叉树中，度为0的结点的个数为n0，度为

24、2的结点的个数为n2，则：n0 =n2 +1。(26) 由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树，则带权路径长度为 55。(27) 在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的 度数，对于有向图来说等于该顶点的 出度数。(28) 假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 O(n2 ) ，采用邻接表表示的空间复杂性为 O(n+e)。(29) 对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O(n);若采用折半法查找，则时间复杂度为O(log 2n)。(30) 假设在有序线性表 A1.20上进行折半查找，则比较一

25、次查找成功的结点数为 1，则比较二次查找成功的结点数为 2，则比较三次查找成功的结点数为 4，则比较四次查找成功的结点数为8，则比较五次查找成功的结点数为 5，平均查找长度为 log 2(n+1)-1 。(31) 在一棵二叉排序树中，每个分支结点的左子树上所有结点的值一定小于该结点的值，右子树上所有结点的值一定 大于该结点的值。(32) 对一棵二叉排序树进行中序遍历时，得到的结点序列是一个 增序序列 。(33) 对于线性表(70，34，55，23，65，41，20)进行散列存储时，若选用 H ( K)=K %7作为散列函数，则散列地址为0的元素是 70，散列地址为 6的是34,20,55 。(

26、34) 在线性表的散列存储中，装填因子 ：又称为装填系数，若用m表示散列表的长度，n表示待散列存储的元素的个数，贝H a 等于n/m 。(35) 散列表中解决冲突的两种方法是 开放地址法和链地址法。(36) 在散列存储中，装填因子a的值越大，则产生冲突的可能性就越大 ;a的值越小，则产生冲突的可能性就越小 。(37) 散列法存储的基本思想是由 关键码直接决定数据的存储地址。(38) 构造哈希函数的方法有(写二个)直接定址法，数字分析法，平方取中法，折叠法，除留余数法，随机数法。精彩文档(39) 在分块查找中首先查找 索引，然后再查找相应的 块。(40) 散列表的查找效率主要取决于散列表造表时选

27、择的 哈希函数 和装填因子 。(41) 对两棵具有相同关键字集合而形状不同的二叉排序树，中序 遍历它们得到的序列的顺序是一样的。(42) 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用快速排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用归并排序。(43) 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为O(log 2n)，整个堆排序过程的时间复杂度为 O(nlog 2n)。(44) 当向一个大根堆插入一个具有最大值的元素时，需要逐层 向上调整，直到被调整到 根结点位置为止。(45) 对一组初始关键字序列(40，50，95，20，15，70，60，45，

28、10)进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为_8，在整个排序过程中最多需要进行 8趟排序才可以完成。(46) 在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是快速，需要内存容量最多的是 归并。(47) 堆排序是不稳定，空间复杂度为 0(1)。在最坏情况下，其时间复杂度也为O(nlog 2n)(48) 若待排序的文件中存在多个关键字相同的记录，经过某种排序方法排序后，具有相同关键字的记录间的相对位置保持不变，则这种排序方法是 稳定的排序方法。(49) 在对一组记录(50,40,95 ，20，15,70,60,45,80)进行直接插入排序时，当

29、把第7个记录60插入到有序表时，为寻找插入位置需比较3次。(50) 二路归并排序的时间复杂度是O(nlog 2n)。(51) 对于n个记录的集合进行归并排序，所需的附加空间消耗是_ 0(n) 。(52) 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其仍按递增顺序进行排序，则 冒泡排序 最省时间， 快速排序最费时间。三、判断题。(每小题1分，共10分)(x )1 .数据元素是数据的最小单位。(x )2 数据项是数据的基本单位。(V )3 .顺序存储的线性表可以随机存取。(V )4 .线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因

30、此，是属于同一数据对象。(x )5 在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查找任何一个元素。(x )6 .在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。(X )7 链表的每个结点中，都恰好包含一个指针。(x )8 数组是同类型值的集合。(V )9 使用三元组表示稀疏矩阵的元素，有时并不能节省存储时间。(V )10.线性表可以看成是广义表的特例，如果广义表中的每个元素都是原子，则广义表便成为线性表。(V )11.由树转换成二叉树，其根结点的右子树总是空的。(X )12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同。(

31、X )13.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。(V )14.若一个树叶是某子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点。(X )15.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树，因为不知道树的根结点是哪一个。(X )16.在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应作特殊处理。(V )17.有回路的图不能进行拓扑排序。(X )18.连通分量是无向图中的极小连通子图。(V )19.散列法存储的基本思想是由关键码的值决定数据的存储地址。(V )20.散

32、列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法。(V )21. m 阶B-树每一个结点的子树个数都小于或等于m(V )22.中序遍历二叉排序树的结点就可以得到排好序的结点序列。(V )23.在二叉排序树上插入新的结点时，不必移动其它结点，仅需改动某个结点的指针，由空变为非空即可。(V )24.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂性的主要因素。(V )25.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)(V )26.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)(V )27.堆中所有非

33、终端结点的值均小于或等于(大于或等于)左右子树的值。(X )28.磁盘上的顺序文件中插入新的记录时，必须复制整个文件。(X )29.在索引顺序文件中插入新的记录时，必须复制整个文件。(X )30.索引顺序文件是一种特殊的顺序文件，因此通常存放在磁带上。四、简答题。(共6小题，每小题约5分，共32分)1. 简述下列术语：数据、数据项、数据元素、数据逻辑结构、数据存储结构、数据类型和算法。数据：数据是信息的载体，是计算机程序加工和处理的对象，包括数值数据和非数值数据。数据项：数据项指不可分割的、具有独立意义的最小数据单位，数据项有时也称为字段或域。数据元素：数据元素是数据的基本单位，在计算机程序中

34、通常作为一个整体进行考虑和处理，一个数据元素可由若 干个数据项组成。数据逻辑结构：数据的逻辑结构就是指数据兀素间的关系。数据存储结构：数据的物理结构表示数据兀素的存储方式或者数据兀素的物理关系。数据类型：是指变量的取值范围和所能够进行的操作的总和。 算法：是对特定问题求解步骤的一种描述，是指令的有限序列。2. 简述栈和线性表的区别。答：一般线性表使用数组来表示的。线性表一般有插入、删除、读取等对于任意元素的操作。而栈只是一种特殊的线性表。栈只能在线性表的一端插入(称为入栈，push )或者读取栈顶元素或者称为“弹出、出栈” (pop)。3. 简述栈和队列这两种数据结构的相同点和不同点。答：相同

35、点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端(栈顶)进行插入，删除操作；队列在一端(top )删除，一端(rear)插入。4. 如果进栈的元素序列为 A, B, C, D,则可能得到的出栈序列有多少种？写出全部的可能序列。答：可能序列有 14 种：ABCD; ACBD;ACDB; ABDC; ADCB; BACD; BADC; BCAD;BCDA; BDCA;CBAD; CBDA; CDBA; DCBA5. 如果进栈的元素序列为1，2，3, 4，5，6，能否得到4，3，5，6，1，2和1，3，5，4，2，6的出栈序列？并说明为什么不能得到或如何得到。答：不能得

36、到4, 3, 5，6, 1, 2，最先出栈的是4,则按321的方式出，不可能得到 1在2前的序列，可以得到1,3，5, 4, 2, 6，按如下方式进行 push(1), pop(), push(2), push(3), pop(),push(4), push(5), pop(), pop(),pop(), push (6), pop() 。“GOO” , q= “WORKER。求：StrLength (s) , StrLength(t) , SubStr( s, 8,7) , SubStr(t , 2, 1), StrIndex(s,A” ) , StrIndex (s ,t) , StrRe

37、p(s，“ STUDENT , q) , SubStr (SubStr (s 答：StrLength (s)=14, StrLength (t)=4, SubStr( sStrIndex(s,“A” )=3, StrIndex (s, t)=0, StrRep(s,6 , 2) , StrC on cat (t , SubStr(s , 7 , 8)。,8 , 7)= ” STUDENT , SubStr(t , 2 , 1)=” O”“STUDENT, q)= ” I AM A WORKER”6. 设 s= “ I AM A STUDENT” ,t=7. 简述下列每对术语的区别：空串和空格串

38、；串变量和串常量；主串和子串；串变量的名字和串变量的值。 答：空串：不含任何字符；空格串：所含字符都是空格。串变量和串常量：串常量在程序的执行过程中只能引用不能改变；串变量的值在程序执行过程中是可以改变和重新 赋值的。主串与子串：子串是主串的一个子集。串变量的名字与串变量的值：串变量的名字表示串值的标识符。8. 设有二维数组 A(6 X 8),每个元素占6个字节存储，顺序存放，A的起地址为1000，计算:(1) 数组A的体积(即存储量)；(2) 数组的最后一个元素 A的起地址；(3) 按行优先存放时，元素 A1,4的起地址；(4) 按列优先存放时，元素 A4,7的起地址。(1) 6*8*6=2

39、88(2) 1000+47*6=1282(3) 1000+(8+4)*8=1096(4) 1000+(6*7+4)*8=13689. 分别画出含三个结点的无序树与二叉树的所有不同形态。 答：无序树形态如下：二叉树形态如下：10. 分别写出图1中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。BCDE FGHI)图1J答：先序遍历序列：ABDEHICFJG中序遍历序列：DBHEIAFJCG后序遍历序列：DHIEBJFGCA11. 试找出分别满足下列条件的所有二叉树。(1) 先序序列与中序序列相同。(2) 后序序列与中序序列相同。空树或缺左子树的单支树； 空树或缺右子树的单支树； 空树或只

40、有根结点的二叉树。(3) 先序序列与后序序列相同。答：(1)先序序列和中序序列相同:(2) 后序序列和中序序列相同:(3) 先序序列和后序序列相同:12. 已知一棵二叉树的中序序列和后序序列分别为BDCEAFH和 DECBHGFA试画出这棵二叉树。答：这棵二叉树为13. 分别写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。BDEFGHH2答：先序遍历序列：ABDGCEHF中序遍历序列：DGBAEHCF后序遍历序列：GDBHEFCA14. 给定权值(7,18,3,32,5,26,12,8)，构造的哈夫曼树。答：哈夫曼树为：1114665，试为这815. 假设用于通信的电文仅由8

41、个字母组成，字母在电文中出现的频率分别为7,19,2,6,32,3,21,10个设计哈夫曼编码。答：哈夫曼树为：在上述哈夫曼树的每个左分支上标以0，右分支上标以1并设这8个字母分别为 AB、CD、E、F、G和H,则它们的哈夫曼树为分别为：A: 0000 B : 10 C : 00110 D : 0010 E : 01 F : 00111 G : 11 H : 000116. 画出无向图G1的邻接矩阵和邻接表示意图，并写出每个顶点的度。0 111010 0 11M=10001110 0 10 1110(2)邻接链表:(3)每个顶点的度：顶点度V1 3V2 3V3 2V4 3V5 317. 画出有向图G2的邻接矩阵、邻接表和逆邻接表示意图，并写出每个顶点的入度和出度。答：（1）邻接链表:VIAV2V3V4V5V63oF、40A1A42ZJ