2013年9月份考试数据结构第三次作业.doc

2013年9月份考试数据结构第三次作业一、填空题（本大题共30分，共 15 小题，每小题 2 分）1. 由３个结点所构成的二叉树有 ______ 种形态。2. 对不同的关键字可能得到同一哈希地址，即key1!=key2，而f(key1)=f(key2)，这种现象称为 ______ 。具有相同函数值的关键字对该哈希函数来说称作_____________。3. 在AOE网中，路径长度最长的路径叫做 ______ 。4. 在一个循环队列中，队尾指针指向队尾元素的 ______ 位置。5. 构造最小生成树的方法主要有： ______ 和 ______ 。6. 带表头结点的空循环双向链表的长度等于 ______ 。7. 为了实现逐层访问，算法中使用了一个 ______ ，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。8. 顺序表中逻辑上相邻的元素的物理位置 ______ 相邻。单链表中逻辑上相邻的元素的物理位置 ______ 相邻。9. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按 ______ 次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 ______ 。10. 基数排序法、堆排序法与归并排序法中， ______ 排序方法需要的辅助存储单元最少。11. 在串S=“structure”中，以t为首字符的子串有 ______ 个12. 邻接多重表是 ______ 的另一种链式存储结构。13. 快速排序算法在最坏情况下的时间复杂度为 ______ 。14. 线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示： 05U17X23V31Y47Z^^100120其中指针X，Y，Z的值X= ______ Y= ______ Z= 该线性表的首结点起始地址为多少？末结点的起始地址为 首址= ______ 末址= ______ 15. AOV网络用 ______ 表示活动，用 ______ 表示活动间的优先关系。二、程序阅读题（本大题共10分，共 2 小题，每小题 5 分）1. 指出下述程序段的功能是什么? void Demo1(SeqStack *S){ 　　　　int i; arr[64] ; n=0 ; 　　　　while ( StackEmpty(S)) arr[n++]=Pop(S); 　　　　for (i=0, i n; i++) Push(S, arr[i]); 　　　} //Demo1 2. 指出下述程序段的功能是什么? CirQueue Q1, Q2; // 设DataType 为int 型　　int x, i , n= 0; 　　... // 设Q1已有内容， Q2已初始化过　　while ( ! QueueEmpty( Q1) ) 　　　{ x=DeQueue( Q1 ) ; EnQueue(Q2, x); n++;} 　　for (i=0; i n; i++) 　　　{ x=DeQueue(Q2) ; 　　EnQueue( Q1, x) ; EnQueue( Q2, x);} 三、简答题（本大题共50分，共 10 小题，每小题 5 分）1. 多重链表存储结构的特点。2. 利用Dijkstra算法求下图中从顶点a到其他各顶点间的最短路径3. 简述KRUSKAL算法的思想。4. 给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。5. 二叉排序树的删除可能会有哪三种情况。6. 列出（至少三种）构造散列函数的方法？7. 何时选用顺序表、何时选用链表作为线性表的存储结构为宜?8. 给出下图的广度优先有哪些信誉好的足球投注网站序列。9. 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?10. 空串和空格串有无区别？四、程序设计题（本大题共10分，共 2 小题，每小题 5 分）1. 设以带头结点的双向循环链表表示的线性表L=(a1，a2，... ，an)，试写一时间复杂度为O（n）的算法，将L改造为L=(a1，a3，... ，an... ，a4，a2)2. 以