期末样卷参考答案一 是非题（每题1分共10分）1. 线性表的链式存储结构优于顺序存储结构。 F2. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行插入/删除操作。F3 栈是数据对象特定的线性表。F4 在单链表P指针所指结点之后插入S结点的操作是：P-next= S ; S- next = P-next; F5 一个无向图的连通分量是其极大的连通子图。T6 邻接表可以表示有向图，也可以表示无向图。T7 假设B是一棵树，B是对应的二叉树。则B的后根遍历相当于B的中序遍历。 T8 通常，二叉树的第i层上有2i-1个结点。F9 对于一棵m阶的B-树，树中每个结点至多有m 个关键字。除根之外的所有非终端结点至少有m/2个关键字。F10对于任何待排序序列来说，快速排序均快于起泡排序。F二选择题（每题2分共28分）1在下列排序方法中，（ c ）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（ d ）方法所有情况下时间复杂度均为0(nlogn)。a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中，空指针数为（ b ）。 a.不定 b.n+1 c.n d.n-13. 下列二叉树中，（ a ）可用于实现符号不等长高效编码。a.最优二叉树 b.次优查找树 c.二叉平衡树 d.二叉排序树4. 下列查找方法中，（ a ）适用于查找有序单链表。a.顺序查找 b.二分查找 c.分块查找 d.哈希查找5. 在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用（ a ）方法。a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找6. 在下列数据结构中，（ c ）具有先进先出特性，（ b ）具有先进后出特性。a线性表 b栈 c队列 d广义表7具有m个结点的二叉排序树，其最大深度为（ f ），最小深度为（ b ）。a. log 2 m b. log2 m +1 c. m/2d . m/2 -1 e. m/2 f. m 8已知一组待排序的记录关键字初始排列如下：56,34,58,26,79,52,64,37,28,84,57。下列选择中（ c ）是快速排序一趟排序的结果。（ b ）是希尔排序（初始步长为4）一趟排序的结果。（ e ）是起泡排序一趟排序的结果。（ a ）是初始堆（大堆顶）。a. 84，79，64，37，57，52，58，26，28，34，56。b. 28，34，57，26，56，52，58，37，79，84，64。c. 28，34，37，26，52，56，64，79，58，84，57。d. 52，34，64，84，56，26，37，57，58，28，79。e. 34，56，26，58，52，64，37，28，79，57，84。f. 34，56，26，58，52，79，37，64，28，84，57。三填空题（每题2分共20分）1有向图的存储结构有（邻接矩阵）、（邻接表）、（十字链表）等方法。2已知某二叉树的先序遍历次序为afbcdeg，中序遍历次序为cedbgfa。其后序遍历次序为（edcgbfa）。层次遍历次序为（afbcgde）。3已知如下程序段for( i=n; i0; i-) 语句1x+; 语句2for( j=n; j=i; i-) 语句3y+; 语句4;语句1执行的频度为（n+1）；语句4执行的频度为（n(n+1)/2）。 4请在下划线上填入适当的语句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e)/先序非递归遍历二叉树。Initstack ( S ); Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )& p ) visit (p-data ) ; push(S, p-lchild ; Pop ( S , p ); If ( !stackempty(s) ) pop(S, p) ; push( S, p-rchild ); return ok;四简答题（每题5分共25分）1将图示森林转换为二叉树，并对该二叉树中序全序线索化。 abdjcehfgmlki abdjcehfgmlki2已知Hash函数为 H（K）=K mod 13 ，散列地址为0 -14，用二次探测再散列处理冲突，给出关键字（23，34，56，24，75，12，49，52，36，92，06，55）在散列表中的分布，并求在等概率情况下查找成功的平均查找长度。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 52 925556360634 75 23241249ASL=22/12=11/6 3. 右图为一棵3阶B 树。 （20，25）a. 画出在该树上插入元素15后的B 树。 b. 接着，再删除元素35，画出删除后的B 树。 (10,14)（21）（35）14 20101521,2520142510152135 a. b. 4.已知某无向图的邻接表存储结构如图所示。 a.请画出该图。b.根据存储结构给出其深度优先遍历序列及广度优先遍历序列。c.画出其深度优先生成树及广度优先生成树。0 a 2 4 /1 b 2 3 4 /2 c 0 1 4 /3 d 1 / 4 e 0 1 2 /abecdabecdabecd b. d. c. DFS:acbde; BFS:acebd5. 设在某通信系统中使用了八个字符，它们出现的频率分别为0.08，0.05，0.1，0.12，0.26，0.18，0.14，0.07，试构造一棵赫夫曼树，并给出赫夫曼编码。赫夫曼编码2610121481875: 赫夫曼树： 0.08:000 0.05:0110 0.10:002 0.12:010 0.26:10 0.18:110 0.14:111 0.07:0111五算法设计题（共17分）1. 单链表结点的类型定义如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist;写一算法，将带头结点的有序单链表A和B合并成一新的有序表C。(注:不破坏A和B的原有结构.)Merge(Linklist A, Linklist B, Linklist &C )void Merge(Linklist A, Linklist B, Linklist &C) C=(Linklist)malloc(sizeof(LNode); pa=A-next; pb=B-next; pc=C; while(pa&pb) pc-next=(Linklist)malloc(sizeof(LNode);pc=pc-next;if(pa-datadata) pc-data=pa-data; pa=pa-next;else pc-data=pb-data; pb=pb-next;if(!pa) pa=pb;while(pa) pc-next=(Linklist)malloc(sizeof(LNode); pc=pc-next; pc-data=pa-data; pa=pa-next;pc-next=NULL;2. 二叉树用二叉链表存储表示。typedef struct BiTNode TelemType data; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree;编写一个复制一棵二叉树的递归算法。BiTree CopyTree(BiTree T) if (!T ) return NULL;if (!(newT = (BiTNode*)malloc(sizeof(BiTNode) exit(Overflow);newT- data = T- data;newT- lchi