1、数据结构一、单项选择题（每题2分，共20分）在以下每题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。1.栈和队列都是（CJo2.在一个单链表中,q所指结点是P所指结点的前驱结点,假设在q和P之间插入S结点,那么执行（C）。A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;3 .稀疏矩阵一般的压缩存储方法有两种，即（C）。A.二维数组和三维数组B三元组和散列C.三元组和十字链表D散列和十字链表4 .对于下面的二叉树，按后序遍历所得的结点序列为（D
2、A.1234567B.1245367C.4251637D.45267315 .深度为5的二叉树至多有（C）个结点。A.16B.32C.31D.106 .Huffman树的WPL是指（C）。A.除根以外所有结点的权值之和B.所有结点权值之和C.各叶子结点的带权路径长度之和D.根结点的值7 .以下排序方法中，（D）的比拟次数与记录的初始排列状态无关？A.直接插入排序B.起泡排序C.快速排序D.直接选择排序10个度为2的结点，那么该二叉树的度为0的结点个数是（C）A.9B.11C.12D.不确定9 .设输入序列为1,2,3,4,5,借助一个栈不可能得到的输出序列是（C）。A.1,2,3,4,5B
3、1,4,3,2,5C.4,1,3,2,5D.1,3,2,5,410 .对以下图，不能得到的拓扑序列是（D）,2,3,4,5,6,7,8B.1,5,2,6,3,7,4,8C.1,2,5,6,3,4,7,8D.1,2,3,4,8,7,6,5二、填空题（每空1分，共20分）IL数据元素之间的自差_称为结构，通常有如下四种根本结构：集合结构、线性结构、树形结构和图形结构。12 .具有n个结点的无向图中,有n（nT）2条边的无向图称为完全图;对于具有n个结点有向图,有n（nT）条弧的有向图称为有向完全图。13 .循环队列用数组A0.mT存放其元素值。其头尾指针分别是front和rear,那么当前队列中
4、的元素个数是（rear-front+m）tm,判断队空的条件是素Ont=rear。i层上至多有墨结点。A0.6,0.8,A00存放位置为500,每个元素占2个字节，以行序为主序列，那么A45在位置568O深度优先搜索和广度优先搜索。（a,（a,b）,d,e,（i,j）,k）的长度是5,表头是a_,表尾是（a,b）,d,e,（i,j）,k）。18 .查找算法中的两种最根本的操作是比拟和移动。19 .具有n条记录的顺序表中，在查找概率相等的情况下顺序查找平均查找长度为包母在。20 .算法质量的度量标准有两个：时间复杂度和空间一复杂度。三、设计题（共40分）DCBGEAHFlJK和后序序列为DCEG
5、BFHKJIA请画出该二叉树，并给出先序序列。（6分）二叉树为(4)先序序列为：Abcdgeihfjk(2)22.某系统在通讯联络中只可能出现5种字符符,b,c,d,e,其概率分别为0.10,0.22,0.27,0.15,0.26,试画出赫夫曼树并设计赫夫曼编码。(8分)w=10,22,27,15,26)赫夫曼树为14)赫夫曼编码为：a:010b:00c:11d:Oile:10(4,)(36,48,22,58,46,18),按表中元素的顺序插入一棵初始为空的二叉排序树，并求在等概率的情况下查找成功的平均查找长度。(8分)每棵树1分，共6分ASL=(l*l+2*2+3*3)/6=7/32分24
6、一组关键字(68,32,56,6,38,49,43,9,55,37,35,12)请按哈希函数H(key)=keyM0D13和线性探测处理冲突构造哈希表(表长为13)。(8分)H(68)=68M0D13=3H(32)=32M0D13=6H(56)=56M0D13=4H(6)=6M0D13=6冲突+1H(38)=38M0D13=12H(49)=49M0D13=10H(43)=43M0D13=4冲突+1H(9)=9M0D13=9H(55)=55M0D13=3冲突+5H(37)=37MODI3=11H(35)=35M0D13=9H(12)=12M0D13=12冲突+4789101112冲突+2456
7、0123351268564332655949373825 .一个待排序的关键字序列为56,36,22,86,72,10,28,48,请写出快速排序每一趟排序的结果。(10分)第1趟排序结果:48,36,22,28,10,56,72,86第2趟排序结果：10,36,22,28,48,56,72,86第3趟排序结果:10,36,22,28,48,56,72,86第4趟排序结果：10,22,28,36,48,56,72,86第5趟排序结果：10,22,28,36,48,56,72,86四、算法设计题(每空2分，共20分)折半查找算法：intsearchbin(SSTableST,KeyTypekey)Iow=Ijhigh=ST.length;while(lowhigh)mid=(low+high)2;if(key=ST.elemmid.key)returnmid;elseif(keydata);push(S,p-lchild);向左走到尽头pop(S,p);if(!StackEmpty(三)pop(S,p);push(S,prchild);向右一步while/PreOrderNonrecursive
