数据结构复习之运算操作题(答案).docVIP

[习题4-1]运算题。 1．有6个元素A、B、C、D、E、F依次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。 （1）CDBEFA （2）ABEDFC （3）DCEABF （4）BAEFCD 2．有4个元素a,b,c,d依次进栈，任何时候都可以出栈，请写出所有可能的出栈序列和所有不存在的序列。 3．用一维数组a[7]顺序储一个循环队列，队首和队尾指针分别用front和rear表示，当前队列中已有5个元素：23，45，67，80，34，其中，23为队首元素，front的值为3，请画出对应的存储状态，当连续做4次出队运算后，再让15，36，48元素依次进队，请再次画出对应的存储状态。 4．用于顺序存储一个队列的数组的长度为N,队首和队尾指针分别为front和rear,写出求此队列长度(即所含元素个数)的公式. 参考答案（从简） 1，(1)能: push(S,A), push(S,B), push(S,C), pop(S), push(S,D), pop(S), pop(S), push(S,E), pop(S), push(S,F), pop(S), pop(S). (2)能:push(S,A), pop(S), push(S,B), pop(S), push(S,C), push(S,D), push(S,E), pop(S), pop(S), push(S,F), pop(S), pop(S). (3)不能: 当E出栈时，AB必需在栈内，而后继A出栈先于B，不符合后进先出原则。 (4)不能: 当F出栈时，CD必需在栈内，而后继C出栈先于D，不符合后进先出原则。 2，所有可能的出栈序列: abcd; abdc; acbd; acdb; adcb; bacd; badc; bcad; bcda; bdca; cbad; cbda; cdba; dcba. 所有不存在的序列: adbc; bdac; cabd; cadb; cdab; dabc; dacb; dbac; dbca; dcab. 3， 0 1 2 3 4 5 6 ------------------------------------------------------------------ [80 34 23 45 67] ↑rear ↑front [ 34 15 36 48 ] ↑front ↑rear 4，队列长度L的计算公式为： L = ( N+rear-front ) % N [ 说明： 当rearfront 时，L = rear - front = ( N+rear-front ) % N; 当rearfront 时，队列被分为两个部分，前部分在数组的尾部，其元素个数为 N-1-front , 后部分在数组的首部，其元素个数为 rear+1 , 所以： L =( rear+1+N-1 - front )%N= ( N+rear-front ) % N; ] [习题6-1]运算题 1.已知一组元素为(46,25,78,62,12,37,70,29),画出按元素排列顺序输入生成的一棵二叉有哪些信誉好的足球投注网站树,再以广义表的形式给出该二叉有哪些信誉好的足球投注网站树. 2.已知一棵有哪些信誉好的足球投注网站树的广义表表示为28(12(,16),49(34(30),72(63))),若从中依次删除72,12,49,28,等4个结点,试分别画出每删除一个结点后得到的图形表示的二叉有哪些信誉好的足球投注网站树,并写出对应的广义表表示. 3.从空堆中开始依次向小根堆中插入集合{38,64,52,15,73,40,48,55,26,12}中的每个元素,试以顺序表的形式给出每插入一个元素后堆的状态. 4.已知一个堆为{12,15,40,38,26,52,48,64},若从堆中依次删除4个元素,请给出每删除一个元素后的堆的状态. 5.有7个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶子结点构造一棵哈夫曼树,给出其广义表表示.并计算出带权路径长度WPL. *6.在一份电文中共使用5种字符,即a.b.c.d.e,它们的出现频率依次为4,7,5,2,9,试画出对应的哈夫曼编码和传送电文的总长度. *7.一棵二叉树的广义表表示为A(B(,D(