1．(10分)什么是广义表?请简述广义表与线性表的主要区别。
2．(10分)下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价。
①请分别给出该图的邻接表和邻接矩阵，要求每种存储结构能够表达出该图的全部信息，并分别对这二种形式中每个部分的含义(物理意义)予以简要说明。
②若假设每个域(包括指针域)的长度为一个字节，请分别计算出这二种结构所占用的空间大小。
3．(10分)已知如下所示长度为12的表：
(Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec)
①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。
③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
4．(10分)在起泡排序过程中，有的关键字在某趟排序中可能朝着与最终排序相反的方向移动，试举例说明之。快速排序过程中有没有这种现象? 5．(10分)调用下列函数f(n)，回答下列问题： ①试指出f(n)值的大小，并写出f(n)值的推导过程；
②假定n=5，试指出f(5)值的大小和执行f(5)的输出结果。 C函数 int f(int n)
{ int i，j，k，sum=0； for(j=1；i { for(j=n；j>i-1；j--) for(k=1；k prinft(”sum=%d\\n”，sum)； } return(sum)； } Pascal函数 FUNCTION f(n：integer)：integer； VAR i，j，k，sum，integer； BEGIN ． sum：=0； FOR i：=1 TO n DO 31 BEGIN FOR j：=n DOWN i DO FOR k：=1 TO j DO sum：=sum+1 writeln(?sum=?，sum) END； f：=sum END； 四、编写算法 (应届生限做1、2、3、4题，在职生任选四题，每题10分，共40分) 1．(10分)利用两个栈S1和S2模拟一个队列，写出入队和出队的算法(可用栈的基本操作)。 栈的操作有： makeEmpty(s：stack)； 置空栈 push(s：stack；value：datatype)； 新元素value进栈 pop(s：stack)：datatype； 出栈，返回栈顶值 isEmpty(s：stack)：boolean； 判栈空否 队列的操作有 enQtleue(s1：stack；s2：stack；value：datatype)；元素value进队 deQueue(s1：stack；s2：stack)：datatype； 出队列，返回队头值 2．(10分)试写出给定的二叉树进行层次遍历的算法，在遍历时使用一个链接队列。 3．(10分)试写一个算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i<>j)。假设分别基于下述策略： 1)图的深度优先搜索； 2)图的广度优先搜索； 4．(10分)设二叉排序树中关键字由1至1000的整数构成，现要检索关键字为531的结点，下述关键字序列中哪些可能是二叉排序树上搜索到的序列，哪些不可能是二叉排序树上搜索到的序列，哪些不可能是二叉排序树上搜索到的序列？ a)800，399，588，570，500，520，566，531 b)730，355，780，390，701，401，530，531 c)732，321，712，385，713，392，531 d)8，578，555，340，433，551，550，450，531 通过对上述序列的分析，试写一个算法判定给定的关键字序列(假定关键字互不相同)是否可能是二叉排序树的搜索序列。若可能则返回真，否则返回假。可假定被判定的序列已存入数组中。 5．(10分)编写一个在非空的带表头结点的单链表上实现就地排序的程序。(不额外申请新的链表空间) 32 华中理工大学2001年数据结构试题 说明：在有数据类型定义和算法设计的各题中，任取C语言、PASCAL语言之一作答，但不许使用所谓“类C”或“类PASCAL”。 一、选择题(从下列各题四个备选答案中选出一至四个正确答案，将其代号(A，B，C，D)写在题干前面的括号内。答案选错或未选全者，该题不得分。每小题1分，共计20分) ( )1．一个算法具有 等特点。 A．可行性 B．至少有一个输入量 C．确定性 D．健壮性 ( )2. 是一个线性表。 A．(A，B，C，D) B．{?A?，?B?，?C?，?D?} C．(1，2，3，…) D．(40，-22，88) ( )3．可使用 作压缩稀疏矩阵的存储结构。 A．邻接矩阵 B．三元组表 C．邻接表 D．十字链表 ( )4．采用一维数组表示顺序存储结构时，可用它来表示 。 A．字符串 B．2度树 C．二叉树 D．无向图 ( )5．假设进入栈的元素序列为d，c，a，b，e，那么可得到出栈的元素序列 。 A．a，b，c，d，e B．a，b，e，d，c C．d，b，a，e，c D．d，b，a，c，e ( )6．对队列的操作有 。 A．在队首插入元素 B．删除值最小的元素 C．按元素的大小排序 D．判断是否还有元素 ( )7．假设有60行70列的二维数组a[1．．60，1．．70]，以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32，58]的存储地址为 。(无第0行第0列元素) A．16902 B．16904 C．14454 D．答案A，B，C均不对 ( )8. 是C语言中\的子串。 A．abed B．32lAB C．”abeABC” D．”2lAB” ( )9．在下列各广义表中，长度为3的广义表有 。 A．(a，b，c，()) B．((g)，(a，b，c，d，f)，()) C．(a，(b，(c))) D．((())) ( )10．一个堆(heap)又是一棵 。 A．二叉排序树 B．完全二叉树 C．平衡二叉树 D．哈夫曼(Huffman)树 ( )11．折半查找有序表(4，6，10，20，30，50，70，88，100)，若查找元素58，则 33 它将依次与表中元素 比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70 C．20，50 D．30，88，50，70 ( )12．对27个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A．3 B．4 C．5 D．6 ( )13．具有12个结点的完全二叉树有 。 A．5个叶子 B．5个度为2的结点 C．7个分支结点 D．2个度为1的结点 ( )14．具有n(n>0)个结点的完全二叉树的深度为 。 A．?log2(n)? B．?log2(n+1)? C．?log2(n)?+1 D．?loge(n) +1? ( )15．用5个权值{3，2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是 。 A．32 B．33 C．34 D．15 ( )16．对14个记录的表进行2路归并排序，共需移动 次记录。 A．42 B．56 C．91 D．84 ( )17．对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是 。 A．O(n) B．O(n2) C．O(nlog2n) D．O(2n) ( )18．在最好情况下，下列算法中 排序算法所需比较关键字次数最少。 A．冒泡 B．归并 C．快速 D．直接插入 ( )19．置换选择排序的功能是 。 A．选出最大的元素 B．产生初始归并段 C．产生有序文件 D．置换某个记录 ( )20．可在 构造一个散列文件。 A．内存 B．软盘 C．磁带 D．硬盘 二、试用2种不同表示法画出下列二叉树B1的存储结构，并评述这2种表示法的优、缺点。(共10分) 二题图B1 三题图G 三、对图G： 34 1． 从顶点A出发，求图G的一棵深度优先生成树； 2． 从顶点B出发，求图G的一棵广度优先生成树； 3．求图G的一棵最小生成树。(共12分) 四、设哈希(Hash)函数为：H(k)=kMODl4，其中k为关键字(整数)，MOD为取模运算，用线性探测再散列法处理冲突，在地址范围为0~14散列区中，试用关键字序列(19，27，26，28，29，40，64，21，15，12)造一个哈希表，回答下列问题： 1．画出该哈希表的存储结构图； 2．若查找关键字40，必须依次与表中哪些关键字比较大小？ 3．假定每个关键字的查找概率相同，试求查找成功时的平均查找长度。(共13分) 五、给定头指针为ha的单链表A，和头指针为hb的递增有序单链表B。试利用表A和表B的结点，将表A和表B归并为递增有序表C，其头指针为hc，允许有相同data值(数据元素)的结点存在，表A，B，C均带表头结点。 例如，给定： 将它们归并为： 1．在下列C算法merge中有下划线的位置填空，使之成为完整的算法，要求在填空后加注释，以提高算法的可读性。 2．假定单链表A和B的长度分别为m和n(m>0，n>0)，试分别就最好情况、最坏情况和平均性能，分析算法merge的时间复杂度。(共15分) 结点类型定义如下： struct node 、 { int data； struct node *next； }； 算法如下： Void merge(struct node*ha，struct node *hb，struct node*hc) { struct node *pc，*qc，*pa，*fa； int search； hc=hb； hb=NULL； pa=ha->next； free(ha)； 35