《数据结构》模拟题五

1、.螇芄蒃蚄衿膇荿蚃羂莂芅蚂肄膅薃蚁螄羈葿螀袆膃莅蝿羈羆芁螈蚈膁膇螈袀羄薆螇羂芀蒂螆肅肂莈螅螄芈芄螄袇肁薃袃罿芆葿袂肁聿莅袂螁芅芁蒈羃肇芇蒇肆莃薅蒆螅膆蒁蒅袈莁莇蒅羀膄芃蒄肂羇薂薃螂膂蒈薂袄羅莄薁肆膁莀薀螆肃芆薀袈艿薄蕿羁肂蒀薈肃芇莆蚇螃肀节蚆袅芅膈蚅羇肈薇蚄螇芄蒃蚄衿膇荿蚃羂莂芅蚂肄膅薃蚁螄羈葿螀袆膃莅蝿羈羆芁螈蚈膁膇螈袀羄薆螇羂芀蒂螆肅肂莈螅螄芈芄螄袇肁薃袃罿芆葿袂肁聿莅袂螁芅芁蒈羃肇芇蒇肆莃薅蒆螅膆蒁蒅袈莁莇蒅羀膄芃蒄肂羇薂薃螂膂蒈薂袄羅莄薁肆膁莀薀螆肃芆薀袈艿薄蕿羁肂蒀薈肃芇莆蚇螃肀节蚆袅芅膈蚅羇肈薇蚄螇芄蒃蚄衿膇荿蚃羂莂芅蚂肄膅薃蚁螄羈葿螀袆膃莅蝿羈羆芁螈蚈膁膇螈袀羄薆螇羂芀蒂螆肅肂莈

2、螅螄芈芄螄袇肁薃袃罿芆葿袂肁聿莅袂螁芅芁蒈羃肇芇蒇肆莃薅蒆螅膆蒁蒅袈莁莇蒅羀膄芃蒄肂羇薂薃螂膂蒈薂袄羅莄薁肆膁莀薀螆肃芆薀袈艿薄蕿羁肂蒀薈肃芇莆蚇螃肀节蚆袅芅膈蚅羇肈薇蚄螇芄蒃蚄衿膇荿蚃羂莂芅蚂肄膅薃蚁螄羈葿螀袆膃莅蝿羈羆芁螈蚈膁膇螈袀羄薆 数据结构模拟题五一、单选题（每小题3分，共24分）（1）用单链表表示的链式队列的队头在链表的（）位置。A链头 B链尾C链中（2）如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（）方法最快。A起泡排序 B快速排序C简单选择排序 D堆排序（3）如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定

3、的。（）就是不稳定的排序方法。A起泡排序 B归并排序C直接插入法排序 D简单选择排序（4）线性表是一个具有n个（）的有限序列。A表元素 B字符C数据元素 D数据项（5）设无向图的顶点个数为n，则该图最多有（）条边。An-1 Bn(n-1)/2Cn(n+1)/2 C0（6）对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序周游的结果为（）ADBFEAC BDFEBCACBDFECA DBDEFAC（7）设有50行60列的二维数组A5060，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A1825的存储地址为（）。A3700 B4376C3900 D46

4、20（8）5阶B树中，每个结点最多有（）个关键码。A2 B3C4 D5二、阅读理解题：说明下面递归的功能（10分） void unknown(ListNode *f，Type &x) /指针f 是带表头结点的单链表的表头指针，数值x是给定值。ListNode * temp;If (fàlink!=NULL) While(fàlinkàdata= =x) Temp= fàlink; fàlink= tempàlink ;delete temp;unknown(fàlink , x);三、简答题（每小题12分，共36分）

5、 1、假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。试为这8个字母设计不等长Huffman编码，并输出该电文的总码数。 A b c d e f g h电文总长度： 2、设有顺序表中的元素依次为017，094，154，170，275，503，512，553，612，677，675，897，908。试画出对其进行折半搜索时做性能分析用的扩充二叉搜索树（判定树），并计算搜索成功时的平均搜索长度和搜索不成功进的平均搜索长度。搜索成功时的平均搜索长度ASLsucc=搜索不成功时的平均搜索长度ASLunsucc

6、= 3、一棵高度为h的满k叉树有如下性质：第h层上的结点都是叶结点，其余各层上每个结点都有k棵非空子树，如果按层次自顶向下，同一层上自左向右，顺序从1开始对全部结点进行编号，试问：(1)第j层的结点个数是多少(j=0,1,2,3,4.h)(2)编号为I的结点(若存在)的编号是多少？(3)编号为I的结点(若存在)的编号是多少？(4)编号为I的结点有右兄弟的条件是什么？它的右兄弟结点的编号是多少？四、已知一个图的邻接矩阵如下，请分别写出从顶点V0出发按深度和广度优先遍历时得到的顶点序列。(10分)深度优先遍历的结点的序列：广度优先遍历的结点的序列：五、综合算法题：(10分)下面是对二叉树进行操作的

7、算法，请仔细阅读。 Template <class Type > Void BinTree<Type> : unknown( BinTreeNode<Type> * t ) BinTreeNode<Type> *p= t , * temp ; If (p!=NULL) Temp=pàleftchild ; pàleftchild= pàrightchild pàrightchild=temp unknown(pàleftchild); unknown(pàrightchild); （1）

8、指出该算法完成了什么功能。（2）试写一个算法，不用栈将以上算法中的第二个递归语句消去。（3）试再写一个算法，用栈将以上算法中的第一个递归语句也消去。六、程序填空题（10分）本题给出一个施加于链表的选择排序的算法。算法中用到一个临时的表头结点head，作为结果链表的表头结点，每次从first链上摘下的值最大的结点current链入head之后。算法结束前，将head删除。Template<class Type > void List<Type>：ListSelectSort( ) ListNode<Type> * head = new ListNode<

9、Type> *current , * pre , p , q ; Int I=0 ; While( 1 ) P=current=first ; q=NULL ; While ( p!=NULL) If (pàdataà 2 )pre=q ; current=p; q=p ; p=pàlink ; if (current=first) 3 ; else preàlink=currentàlink; if (! I ) last=current ; I+; currentàlink=headàlink; 4 ; first

10、=headàlink ; delete head;（1）请将缺失语句部分补上：（4分）1、2、3、4、（2）设待排序的记录数n=7，当前各记录关键码的初始顺序为40，20，60，30，70，50，80，试根据上述算法，画出每一趟排序时各结点指针的变化。（6分）参 考 答 案 一、单选题1  A2D3D4C5B6B7D8C二、阅读理解题在单链表中删除所有值为x的结点。三、解答题1、  其huffman编码为abcdEfgH01001000000101001011110001电文总码数为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257 1

11、00 39 61 17 22 7 10 11 11 3 4 5 62、  其判定树为： 519 154 677017 275 553 897094 170 503 512 612 765 908搜索成功时的平均搜索长度为：ASLsucc=(1+2*2+3*4+4*7)/14=45/14搜索不成功时的平均搜索长度为：ASLunsucc=(3+4*14)/15=59/153、解答（1）       kj (j=0,1,.,h) （2） （3）（i-1）*k+m+1 （4）（i-1）mod k0 或 i*k 时有右兄弟，右兄弟为i

12、+1。四、深度优先遍历的结点序列为：0，1，3，7，4，5，2，6广度优先遍历的结点序列为：0，1，2，3，4，5，6，7五、综合算法题（1）       交换二叉树各结点的左、右子树的递归算法。（4分）（2）       不用栈消去算法中的第二个递归语句：（3分）Void BinTree<Type> ： unknown( BinTreeNode<Type> * t ) BinTreeNode<Type> *p= t , * temp ;

13、While(p!=NULL) Temp=pàleftchild ; pàleftchild= pàrightchild pàrightchild=temp unknown(pàleftchild); p= pàrightchild ; （3）       用栈消去算法中的两个递归语句：（3分） Void BinTree<Type> ： unknown( BinTreeNode<Type> * t ) BinTreeNode<Type> *p

14、= t , * temp ; int finish=0; Stack <Type> S ; S.makeEmpty ( ) ; While(!finish) While(p!=NULL) Temp=pàleftchild ; pàleftchild= pàrightchild pàrightchild=temp S.push(p) ; p= pàleftchild ; if (!S.Empty() p=S.getTop() ; S.pop( ) ; p= pàrightchild ; else finish=1 ; 六、程

15、序填空题（10分）（1）       将缺失的语句补上（4分）1、  first !=NULL2、  currentàdate3、  first=firstàlink4、  headàlink=current （2）排序前各记录关键码的初始顺序为40，20，60，30，70，50，80，根据上述算法，画出每一趟排序时各结点指针的变化如下： firstà40à20à60à30à70à50à80 he

16、ad pre current firstà40à20à60à30à70à50 headà80 pre current firstà40à20à60à30à50 headà70à80 pre current firstà40à20à30à50 headà60à70à80 pre current firstà40à20à30 headà50à

17、60à70à80 pre currentfirstà20à30 headà40à50à60à70à80 pre current firstà20 headà30à40à50à60à70à80 pre current first headà20à30à40à50à60à70à80 firstà20à30à40à50à60à70à80 last 腿莅蚂袅膈蒇蒅螁膈膇蚁蚇膇艿蒃羅芆莂虿袁芅蒄蒂螇芄膄蚇螃袁莆薀虿袀蒈螆羈衿膈薈袄袈芀螄螀袇莃薇蚆羆蒅荿羄羆膅薅袀羅芇莈袆羄葿蚃螂羃腿蒆蚈羂芁蚁羇羁莃蒄袃羀蒆蚀蝿肀膅蒃蚅聿芈蚈薁肈蒀蒁羀肇膀螆袆肆节蕿螂肅莄螅蚈肄蒇薇羆肄膆莀袂膃艿薆螈膂莁荿蚄膁肀薄蚀膀芃莇罿腿莅蚂袅膈蒇蒅螁膈膇蚁蚇膇艿蒃