数据结构温习题及答案12级

1、一、选择题。(每题2分，共40分)(I) 运算机识别.存储和加工处置的对象被统称为_A_。A. 数据B.数据元素C.数据结构D.数据类型数据结构一般是研究数据的A及它们之间的联系。A. 存储和逻借结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是A。A. 散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地概念为.其中D是B的有限集，R是C的有限集。A. 算法B.数据元素C.数据操作D.逻辑结构组成数据的大体单位是A。A. 数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构 A=(D, R),其中 D=1, 2, 3, 4, R=r, r=, ,

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

3、有n个C的有限序列(n乂)。A.表兀素B.字符C.数据元素D.数据项(12) 线性表的存储结构是一种B的存储结构。A.随机存取B.顺序存取存取C 索引存取(13) 在一个长度为n的顺序表中，向第i个元素(1 iW n+ 1 )之前插入一个新元素时，需要向后移动B 个元素。+1(14) 链表是一种采纳B存储结构存储的线性表：A.顺序B.链式C.星式D.网状(15) 下而关于线性表的表达错误的选项是DoA. 线性表采纳顺序存储必需占用一片持续的存储空间B. 线性表采纳链式存储没必要占用一片持续的存储空间C. 线性表采纳链式存储便于插入和删除操作的实现D. 线性表采纳顺序存储便于插入和删除操作的实现

4、(16) 设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,那么在结点A和结点B之间插入结点X的操作序列为B。A. s-next=p-next: p-next=-s:B q-next二s； s-nextz:p：C p-next=s-next: s-next=p:(17)那么删除结点A的后继结点B需要的操作为AD p-next二s； s-next=q： 设指针变量p指向单链表结点A,A. p-next=p-next-nextB p二p-next(18)C p=p-next-next以下说法哪个正确？D p-next=p(19)A.堆栈是在两头操作、B.堆

5、栈是在一端操作.C.队列是在一端操作.D.队列是在两头操作、栈和队列的一起点是先进后出的线性表先进先岀的线性表先进先出的线性表先进先出的线性表A.都是先进后出B. 都是先进先出C. 只许诺在端点处插入和删除元素D.没有一起点(20)栈与一样线性表的区别要紧在D.A、元素个数B、元素类型C、逻辑结构D、插入、删除元素的位置(21)链栈与顺序栈相较，比较明显的优势是D.A、插入操作加倍方便B、删除操作加倍方便C、可不能显现下溢的情形D、可不能显现上溢的情形(22) 以下数据结构中哪个是非线性结构_ DcA.队列B.栈C.线性表D.二叉树(23) 假设已知一个栈的入栈序列是1, 2, 3,，n,其输

6、岀序列为pl, p2, p3,，pn,假设pl=n,那么pi为C oB. B n=iC n-i+lD. 不确信(24) 当利用大小为N的一维数组顺序存储一个栈时，假崖用k)p=N表示栈空，那么向那个栈插入一个元素时，第一应执行 B语句修改top指针。A top+B top一一C top=0D. top(25) 4个元素进S栈的顺序是A.B.C.D,经运算POP(S)后，栈顶元素是CA. AB- BC. CD. D(26) 一个栈的输入序列是a.b,c,d,e,那么栈的不可能的输出序列是CA edcbaB decbaC dceabD abcde(27) 设输入序列是1、2、3 n,通过栈的作用后

7、输出序列的第一个元素是n,那么输出序列中第i个输岀元素是C。A. n-iB. n-l-iC. n+l-iD.不能确信(28) 字符A、B、C、D依次进入一个栈，按岀栈的前后顺序组成不同的字符串，最多能够组成B个不同的 字符串？A. 15B. 14C. 16D. 21(29) 设指针变量top指向当前链式栈的栈顶，那么删除栈顶元素的操作序列为D。A. top=top+l;B. top二top-1;C. top-next二top;D. top=top-next;(30) 设栈S和队列Q的初始状态为空，元素El、E2、E3、E4、E5和E6依次通过栈S, 个元素出栈后即进入队列Q，假设6个元素岀列的

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

9、，指针变M rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X,那么入队列的操作序列为CoA. front-next二s: front=s:C rear-next=s： rear=s：(34) 如下陈述中正确的选项是AA.串是一种特殊的线性表C.串中元素只能是字母(35) 以下关于串的表达中，正确的选项是_A.串长度是指串中不同字符的个数B s-next=rear： rear=s；D s-next=front: front=s:B. 串的长度必需大于零D.空串确实是空白串.DoB. 串是n个字母的有限序列C. 若是两个串含有相同的字符，那么它们相等D. 只有当两个串的长度相等，而

10、且各个对应位置的字符都相符时才相等(36) 字符串的长度是指CA.串中不同字符的个数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) 设串sI=ABCDEFG,s2=”PQRST”,

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

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

13、. 2C.D. 4(48) 由別离带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权途径长度为C。A. 23B. 37C. 44D. 46(49) 在树中除根结点外，其余结点分成m (mMO)个A的集合Tl,T2,T3.Tm.每一个集合又都是树，现在结点T称为Ti的父结点，Ti称为T的子结点(1 WiWm)。A.互不相交B.能够相交C.叶结点能够相交D.树枝结点能够相交(50) 若是结点A有三个兄弟，而且B是A的双亲，那么B的岀度是B。A. 3B. 4C. 5D. 1(51) 在一个有向图中，所有极点的入度之和等于所有极点的出度之和的B倍。A. 1/2B. 1C. 2D. 4(52

14、) 具有n个极点的无向完全图，边的总数为D条。A. n-1B. nC. n+1D. n* (n-l)/2(53) 在无向图G的邻接矩阵A中，假设Ai,j等于1,那么Aj,i等于CoA. i+jB. i-jC. 1D. 0(54) 图的深度优先或广度优先遍历的空间复杂性均为A。(访问标志位数组空间)A. 0(n)B. 0(e)C. 0(n-e)D. O(n+e)(55) 请指出在顺序表二、五、7、10、14、1五、1八、23、3五、4 一、52冲，用折半法查找关键码12需做. C次关键码比较。(56) 对线性表进行折半査找时，必需要求线性表 C0A.以顺序方式存储B.以链接方式存储C. 以顺序方

15、式存储，且结点按关键字有序排列D. 以链接方式存储，且结点按关键字有序排列(57) 设二叉排序树中有n个结点，那么在二叉排序树的平均查找长度为_ B-A. 0(1)B. 0(log：n)C. 0(n)D. 0(n_)(58) 依次插入序列(50, 72, 43, 85, 75, 20, 35, 45, 65, 30)后成立的二叉搜索树中,査找元素35要进行_A 元素间的比较。次次次次(59) 设散列表中有m个存储单元，散列函数H(key)= key % p,那么p最好选择BA.小于等于m的最大奇数B.小于等于m的最大素数C.小于等于m的最大偶数D.小于等于m的最大合数(60) _ D是HASH

16、查找的冲突处置方式。A.求余法 B.平方取中法 C.二分法 D.开放地址法(61) 当u的值较小时，散列存储通常比英他存储方式具有 B的查找速度。A.较慢B.较快C.相同 D.不确定(62) 对线性表进行折半査找最方便的存储结构是B。A.顺序表B.有序的顺序表C.链表D.有序的链表(63) 若是要求一个线性表既能较快的查找，又能适应动态转变的要求，能够采纳D査找方式。A.分块B.顺序C.折半D.散列(64) 散列函数有一个一起性质，即函数值应按C取其值域的每一个值。A.最可能率B.最小槪率C. 一样概率D.平均槪率(65) 下述排序算法中，稳固的是_B。A.直接选择排序B.直接插入排序C.快速

17、排序 D.堆排序(66) 以下排序算法中，A需要的辅助存储空间最大。A.快速排序B.插入排序C.希尔排序D.基数排序(67) 以下齐类排序算法中平均时刻复杂度为0(2)是D。A.快速排序B.堆排序C.归并排序D.冒泡排序(68)在基于关键码比较的排序算法中,A.起泡排序C算法在最坏情形下，关键码比较次数不髙于O(nlog2n)B.直接插入排序(69)(70)C.二路归并排序D.快速排序一组记录为46, 79, 56,A. 46,79,56,38,40,84C. 3& 40, 46, 56, 84, 7938,84, 40,那么采纳冒泡排序法按升序排列时第一趟排序结果是_ B,56, 38, 7

18、9, 40, 84,46, 79, 56, 40, 84每次从无序表中掏出一个元素,把它插入到有序表中的适当位置，此种排序方式叫做A排序。A.插入B.堆C.快速D 归并(71)(72)A.插入B.堆C.快速D 归并设一组初始记录关键字序列(5, 2, 6, 3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为C每次从无序表中挑选出一个最小或最大元素，把它互换到有序表的一端，此种排序方式叫做_B排序。A. 2, 3, 5, 8, 6B. 3, 2, 5, 8, 6C. 3, 2, 5, 6, 8D. 2, 3, 6, 5, 8(73) 以下排序方式中，哪一种方式的比较次数与纪录的初始排列

19、状态无关_DoA.直接插入排序B.起泡排序C.快速排序D.直接选择排序(74) 设有关键码初始序列Q, H, C, Y, P, A.M.S.R.DFX,新序列F, H, C, D, P, A, M, Q, R, S, Y.X 是采纳c 方式对初始序列进行第一趟扫描的结果。A.直接插入排序B.二路归并排序C.以第一元素为分界元素的快速排序D.基数排序(75) 在待排序文件已大体有序的前提下，下述排序方式中效率最高的是C。A.直接插入排序B.直接选择排序C.快速排序D. 归并排序(76) 假设需在O(nlog2n)的时刻内完成对数组的排序，且要求排序是稳固的，那么可选排序方式是C。A.快速排序B.

20、堆排序C.归并排序D.直接插入排序(77) 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是_B。A n B. 2n-l C. 2n D. n-1(78) 以下排序算法中，C 算法可能会显现下面情形：初始数据有序时，花费的间反而最多。A. 堆排序B.冒泡排序C.快速排序D. SHELL排序二. 填空题。(每空1分，共10分)(1) 数据结构是一门研究非数值计算的程序设计问题中运算机的数据和它们之间的_关系和运算等的学科。(2) 数据结构包括数据的逻辑结构结构和 物理结构结构 数拯结构从逻辑上划分为三种大体类型：线性数据结构、树型结构和图结构数据的物理结构被分为顺序存储、链式存储、

21、索引存储和散列表(Hash)存储四种。(5) 一种抽象数据类型包括变屋的取值范用和操作的类别两个部份。(6) 数据的逻辑结构是指数据元素间的逻辑关系，数据的存储结构是指数据元素存储方式或数据元素的物理关系(7) 数据结构是指数据及其彼此之间的关系o当结点之间存在M对N (M： N)的联系时，称这种结构为网状结构。当结点之间存在1对N(1：N)的联系时,称这种结构为树结构。(8) 对算法从时刻和空间两方面进行气宇，别离称为空间复杂度和时刻复杂度分析。(9) 算法的效率可分为空间效率和时刻效率。(10) for(i=l, t=l, s=0； i=n； i+)s=s+t： 的时刻复杂度为O (n)。

22、(11) 线性表是n个元素的有限序列(12) 线性表的存储结构有顺序存储和链式存储o(13) 设线性表中有n个数据元素，那么在顺序存储结构上实现顺序查找的平均时刻复杂度为O(n),在链式存储结构上实现顺序查找的平均时刻复杂度为0(n)e(14) 设顺序线性表中有n个数据元素，那么第i个位宜上插入一个数据元素需要移动表中n-i+1个数据元 素：删除第i个位豊上的数据元素需要移动表中n-i个元素。(15) 假设频繁地对线性表进行插入与删除操作，该线性表应采纳链式存储结构。(16) 链式存储结构中的结点包括数据域和指针域。(17) 关于一个长度为n的单链存储的线性表，在表头插入元素的时刻复杂度为_0

23、(1),在表尾插入元素的时刻复杂度为O (n)。(18) 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必然先出栈，因此又把栈称为FILO表：队列的插入和删除运算別离在队列的两头进行，先进队列的元素必然先岀队列，因此又把队列称为FIFO表(19) s= ” I am a man ” 长度为10。(20) sl=” hello ,s2=” boy”，sl,s2 连接后为： hello boy。(21) s=” this is the main string M ,sub=” string M ,strindex(s,sub)是： 13。(22) int a1010,已知 a=1000.sizeo

24、f(int)=2,求 a33地址：1066。(23) 设有两个串p和q,求q在p中第一次显现的位置的运算称为模式匹配。(24) 在树型结构中，树根结点没有前趋结点，其余每一个结点有且仅有一个前驱结点：树叶结点没有后继结点，其余每一个结点的后继结点数不受限制。(25) 在一棵二叉树中，度为0的结点的个数为n0 ,度为2的结点的个数为n2 ,那么：n0=n2+l。(26) 由别离带权为3,962,5的共五个叶子结点组成一棵哈夫曼树，那么带权途径长度为55(27) 在图G的邻接表表示中，每一个极点邻接表中所含的结点数，关于无向图来讲等于该极点的 度数，关于有向图来讲等于该极点的岀度数。(28) 假定

25、一个图具有n个极点和c条边，那么采纳邻接矩阵表示的空间复杂性为0(n2 ),采纳邻接表表示的空间复杂性为O(n+)。(29) 关于长度为n的线性表，假设进行顺序查找，那么时刻复杂度为 0(n):假设采纳折半法查找，那么时刻复杂度为 O(logm)。(30) 假设在有序线性表A1.20进行折半查找，那么比较一次査找成功的结点数为1,那么比较二次査找成功的结点数为2,那么比较三次查找成功的结点数为I,那么比较四次查找成功的结点数为8，那么比较五次査找成功的结点数为5,平均査找长度为log：n+l)-lu(31) 在一棵二叉排序树中，每一个分支结点的左子树上所有结点的值必然小于该结点的值，右子树上所

26、有结点的值必然大于该结点的值。(32) 对一棵二叉排序树进行中序颯历时，取得的结点序列是一个增序序列o(33) 关于线性表(70, 34, 55, 23, 65, 41, 20)进行散列存储时，假设选用H (K) =K %7作为散列函数,那么散列地址为0的元素是70,散列地址为6的是34, 20, 55(34) 在线性表的散列存储中，装填因子a又称为装填系数，假设用m表示散列表的长度，n表示待散列存储的元素的个数，那么a等于n/m。(35) 散列表中解决冲突的两种方式是开放地址法和链地址法。(36) 在散列存储中，装填因子a的值越大，那么产生冲突的可能性就越大: a的值越小，那么生冲突的可能性

27、就越小(37) 散列法存储的大体思想是由关键码直接决定数据的存储地址。(38) 构造哈希函数的方式有(写二个)直接左址法，数字分析法，平方取中法，折叠法，除留余数法,随机数法。(39) 在分块查找中第一査找 索引,然后再查找相应的块o(40) 散列表的査找效率要紧取决于散列表造表时选择的哈希函数 和装填因子(41) 对两棵具有相同关键字集合而形状不同的二叉排序树，中序遍历它们取得的序列的顺序是一样的。(42) 当待排序的记录数较大，排序码较随机且对稳固性不作要求时，宜采纳快速排序；当待排序的记录数较大，存储空间许诺且要求排序是稳固时，宜采纳归并排序。(43) 在堆排序的进程中，对任一分支结点进

28、行筛运算的时刻复杂度为_0(log=n),整个堆排序进程的时刻复杂度为 0(nlog：n)。(44) 当向一个大根堆插入一个具有最大值的元素时，需要逐层向上调整，直到被调整到根结点位宜为止。(45) 对一组初始关键字序列(40, 50, 95, 20, 15, 70, 60, 45, 10)进行冒泡排序，那么第一趟需要进行相邻记录的比较的次数为8,在整个排序进程中最多需要进行8趟排序才能够完成。(46) 在在插入排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是快速，需要内存容量最多的是归并。(47) 堆排序是不稳固，空间复杂度为 0。在最坏情形下，其时刻复杂度也

29、为0(nlog：n)。(48) 假设待排序的文件中存在多个关键字相同的记录，通过某种排序方式排序后，具有相同关键字的记录间的相对位巻维持不变，那么这种排序方式是稳固的排序方式。(49) 在对一组记剥50.40.95, 20, 15.70.60.45,80)进行直接插入排序时，当耙第7个记录60插入到有序表时，为寻觅插入位置需比较3次。(50) 二路归并排序的时刻复杂度是0(nlog：n)(51) 关于n个记录的集合进行归并排序，所需的附加空间消耗是_0(n)。(52) 设表中元素的初始状态是按键值递增的，别离用堆排序、快速排序、冒泡排序和归并排序方式对其仍按递增顺序进行排序，那么冒泡排序最省时

30、刻，快速排序最费时刻。三、判泄题。(每题1分，共10分)(X )1.数据元素是数据的最小单位。(X )2.数据项是数据的大体单位。(V )3.顺序存储的线性表能够随机存取。(V )4.线性表中的元素能够是各类各样的，但同一线性表中的数据元素具有相同的特性，因此，是属于同一数 据对象。(X )5.在单链表中，任何两个元素的存储位置之间都有固泄的联系，因为能够从头结点查找任何一个元素。(X )6.在单链表中，要取得某个元素，只要明白该元素的指针即可，因此，单链表是随机存取的存储结构。(X )7.链表的每一个结点中，都恰好包括一个指针。(X )8.数组是同类型值的集合。(V )9.利用三元组表示稀疏

31、矩阵的元素，有时并非能节省存储时刻。(V )10.线性表能够看成是广义表的特例，若是广义表中的每一个元素都是原子，那么广义表便成为线性表。(V )11.由树转换成二叉树，其根结点的右子树老是空的。(X )12.后序遍历树和中序遍历与该树对应的二叉树，其结果不同。(X )13.假设有一个结点是某二叉树子树的中序遍历序列中的最后一个结点，那么它必是该子树的前序遍历序列 中的最后一个结点。(V )14.假设一个树叶是某子树的中序遍历序列中的最后一个结点，那么它必是该子树的前序遍历序列中的最后 一个结点。(X )15.已知二叉树的前序遍历和后序遍历序列并非能唯一地确信这棵树，因为不明白树的根结点是哪个

32、。(X )16.在哈夫曼编码中，当两个字符显现的频率相同时，苴编码也相同，关于这种情形应作特殊处置。(V )17.有回路的图不能进行拓扑排序。(X )1&连通分量是无向图中的极小连通子图。(V )19.散列法存储的大体思想是由关键码的值决立数据的存储地址。(V )20.散列表的查找效率取决于散列表造表时选取的散列函数和处置冲突的方式。(V )21. m阶B-树每一个结点的子树个数都小于或等于m。(J )22.中序遍历二叉排序树的结点就能够够取得排好序的结点序列。(V )23.在二叉排序树上插入新的结点时，没必要移动英它结点，仅需改动某个结点的指针，由空变成非空即可。(V )24.当待排序的元素

33、很多时，为了互换元素的位置，移动元素要占用较多的时刻，这是阻碍时刻复杂性的要 紧因素。(V )25.关于n个记录的集合进行快速排序，所需要的平均时刻是O(nlog2 n)o(v )26.关于n个记录的集合进行归并排序，所需要的平均时刻是O(nlog2n)。(J )27.堆中所有非终端结点的值均小于或等于(大于或等于)左右子树的值。(X )28.磁盘上的顺序文件中插入新的记录时，必需复制整个文件。(X )29.在索引顺序文件中插入新的记录时，必需复制整个文件。(X )30.索引顺序文件是一种特殊的顺序文件，因此通常寄存在磁带上。四、简答题。(共6小题，每题约5分，共32分)1简述以下术语：数据、

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

35、的区别。答：一样线性表利用数组来表示的。线性表一样有插入、删除、读取等关于任意元素的操作。而栈只是一种特殊的线性表。栈只能在线性表的一端插入(称为入栈,push)或读取栈顶元素或称为“弹岀、出栈” (pop)。3. 简述栈和队列这两种数据结构的相同点和不同点。答：相同点：栈和队列都是特殊的线性表，只在端点处进行插入，删除操作。不同点：栈只在一端(栈顶)进行插入，删除操作：队列在一端(top)删除，一端(rear)插入。4. 若是进栈的元素序列为A, B, C, D,那么可能取得的岀栈序列有多少种？写岀全数的可能序列。答：可能序列有 14 种：ABCD; ACBD; ACDB; ABDC; AD

36、CB; BACD; BADC; BCAD; BCDA; 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(2), push(3), pop0, push(4), push(5), pop(), pop(), p

37、op 0, push (6), pop () o6. 设$= “I AM A STUDENT” ,t= “GOOD”，q= “WORKER”。求：StrLcngth (s), StrLength (t), SubStr( s, 8, 7), SubStr(t, 2, 1), Strlndcx(s, A”)，Strindex (s, t), StrRep(s, “STUDENT , q). SubStr (SubStr (s, 6, 2), StrConcat (t, SubStr(s, 7, 8)。答：StrLength (s)=14, StrLength (t)=4, SubStr( s,

38、8, 7)二” STUDENT”， SubStr(t, 2, 1)二” 0” ,Strindex (s, “A” )=3, Str Index (s, t)=0, StrRep(s, “STCDENT”，q)二” I AM A WORKER,7. 简述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。答：空串：不含任何字符：空格串：所含字符都是空格。串变量和串常量:串常星在程序的执行进程中只能引用不能改变；串变呈的值在程序执行进程中是能够改变和从头 赋值的。主串与子串：子串是主串的一个子集。串变疑的名字与串变量的值:串变量的名字表示串值的标识符。8. 设有

39、二维数组A(6X8),每一个元素占6个字节存储，顺序寄存，A的起地址为1000,计算：(1) 数组A的体积(即存储量)：(2) 数组的最后一个元素A的起地址：(3) 按行优先寄存时，元素A1.4的起地址：(4) 按列优先寄存时，元素A4,7的起地址。(1) 6*8*6=288(2) 1000+47*6=1282(3) 1000+(8+4)*8二1096(4) 1000+(6*7+4)*8=13689. 別离画出含三个结点的无序树与二叉树的所有不同形态。答：无序树形态如下：二叉树形态如下：10. 別离写出图1中所示二叉树的先序遍历.中序遍历、后序遍历的结点访问序列。ABCDE FGH I J图1

40、答：先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIA町CG后序遍历序列:DHIEBJFGCA11试找出别离知足以下条件的所有二叉树*先序序列与中序序列相同。后序序列与中序序列相同。(3) 先序序列与后序序列相同。答：(1)先序序列和中序序列相同：空树或缺左子树的单支树：(2) 后序序列和中序序列相同：空树或缺右子树的单支树：(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。12. 已知一棵二叉树的中序序列和后序序列别离为BDCEAFHG和DECBHGFA,试画出这棵二叉树。 答：这棵二叉树为：13. 别离写出图2中所示二叉树的先序遍历、中序遍历、后序遍历的结点访问序列。AB

41、CDEFGH图2答：先序遍历序列:ABDGCEHF中序遍历序列:DGBAEHCF后序遍历序列:GDBHEFCA14. 给定权值(7,1& 3, 32, 5,26,12, 8),构造的哈夫曼树。 答：哈夫曼树为：15. 假设用于通信的电文仅由8个字母组成，字母在电文中显现的频率别离为7,19,2,6,32,3,21,10,试为这8 个设计哈夫曼编码。答：哈夫曼树为：111在上述哈夫曼树的每一个左分支上标以0,右分支上标以1,并设这8个字母别离为A、B、C. D、E、F、G和H,那 么它们的哈夫曼树为别离为：A： 0000 B： 10 C： 00110 D： 0010 E： 01 F： 00111 G： 11 H： 000116. 画出无向图G1的邻接矩