北京交通大学数据结构与算法期末考试参考答案.docx

1、北京交通大学数据结构与算法期末考试参考答案2011-2012北京交通大学数据结构与算法期末考试参考答案北 京 交 通 大 学 考 试 试 题 （A卷）课程名称:数据结构与算法 2011-2012学年第一学期 出题教师:张勇(请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场)题号一二三四五六总分得分阅卷人一、 填空题（每空2分，共20分）1. 在顺序表中访问任意一个元素的时间复杂度均为 ，因此顺序表也称为 的数据结构。 2三维数组a432(下标从0开始)，假设a000的地址为50，数据以行序优先方式存储，每个元素的长度为2字节，则a211的地址是 。3.

2、直接插入排序用监视哨的作用是 。4. 已知广义表Ls=(a, (b, c), (d, e), 运用head和tail函数取出Ls中的原子d的运算是 。 5对有14个元素的有序表A1.14进行折半查找，当比较到A4时算法结束。被比较元素除A4外，还有 。6. 在AOV网中，顶点表示 ，边表示 。 7. 有向图G可进行拓扑排序的判别条件是 。 8. 若串S1=ABCDEFGHIJK,S2=451223,S3=#,则执行Substring(S1,Strlength(S3),Index(S2,12,1)的结果是 。二、 选择题（每空2分，共20分）1. 在下列存储形式中，哪一个不是树的存储形式？（ ）

3、A双亲表示法 B孩子链表表示法 C孩子兄弟表示法 D顺序存储表示法2. 查找n个元素的有序表时，最有效的查找方法是（ ）。A顺序查找 B分块查找 C折半查找 D二叉查找3. 将所示的s所指结点加到p所指结点之后，其语句应为（ ）。(A) s-next=p+1 ; p-next=s;(B) (*p).next=s; (*s).next=(*p).next;(C) s-next=p-next ; p-next=s-next;(D) s-next=p-next ; p-next=s;4. 在有向图的邻接表存储结构中，顶点v在链表中出现的次数是（ ）。A. 顶点v的度 B. 顶点v的出度 C. 顶点v

4、的入度 D. 依附于顶点v的边数5. 算法的时间复杂度为O（nlog2n）、空间复杂度为O(1)的排序算法是（ ）。A. 堆排序 B. 快速排序 C. 归并排序 D.直接选择6. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如右图所示）按行序存放在一维数组B 1, n(n-1)/2 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是（ ）：i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j7. 由一个长度为11的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功的平均查找长度是（ ）。A29/11

5、B. 31/11 C. 33/11 D.35/118. AVL树是一种平衡的二叉排序树，树中任一结点的（ ）。A. 左、右子树的高度均相同 B. 左、右子树高度差的绝对值不超过1 C. 左子树的高度均大于右子树的高度 D. 左子树的高度均小于右子树的高度 9. 下列四种排序方法中，不稳定的方法是（ ）。A. 直接插入排序 B. 冒泡排序C. 归并排序 D. 堆排序10. 设树的度为4，其中度为1,2,3,4的结点个数分别为4, 2, ,1, 1, 则T中的叶子数为（ ）。A5 B6 C7 D8三、 判断题（10分，每小题1分）1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）

6、2. 数组不适合作任何二叉树的存储结构。（ ）3. 广义表的取表尾运算，其结果通常是个表，但有时也可是个原子。（ ）4. 在含有n个结点的树中，边数只能是n-1条。（ ）5. 所谓一个排序算法是否稳定，是指该算法在各种情况下的效率是否相差不大。（ ）6. 简单选择排序在最好情况下的时间复杂度为O(n)。（ ）7. 在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）8. 采用线性探测处理冲突，当从哈希表中删除一个记录时，不应将该记录所在位置置空，因为这会影响以后的查找。（ ）9. 有n个数存放在一维数组A1.n中，在进行顺序查找时，这n个数的排列有序或无序，其平均查找长度不同。（ ）10

7、. 广义表中原子个数即为广义表的长度。( ) 四、 应用题（24分）1. （6分）将下列由三棵树组成的森林转换为二叉树。 2(6分)给定下列图，完成以下问题 （1）画出该图的邻接矩阵和邻接表（2）根据所画的邻接表，从顶点B出发，画出图的深度优先搜索树（3）根据普里姆（Prim）算法，求它的最小生成树（不必写出全部过程，在生成树中标出边生成的次序即可）3（6分）输入一个正整数序列（53,17,12,66,58,70,87,25,56,60），试完成下列各题：（1）构造一棵二叉排序树，计算查找成功的平均查找长度；（2）依此二叉排序树，如何得到一个从大到小的有序序列；（3）画出在此二叉排序树中，删除

8、“66”后的树结构.4. （6分）将序列25, 34, 12, 7, 15, 47, 65, 79，47+，16 中的关键字按升序重新排列，请写出（1）冒泡排序一趟扫描的结果（2）以第一个元素为分界点的快速排序一趟扫描的结果（3）堆排序所建的初始堆和第一趟排序结果。五、 程序填空题（10分，每空1分）1. 下列算法是建立单链表的算法，请填写适当的语句，完成该功能。typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList;Status CreatList_L(LinkList &L, int n) /正序输入

9、n个元素的值,建立带表头结点的单链线性表L L=(LinkList) malloc(sizeof(LNode); if(!L) return ERROR; L-next=NULL; p= ( 1 ) ; for(i=0;idata); (2) ; (3) ; p-next=NULL; return OK;/CreatList_L2. 下列算法是经典模式匹配算法程序，请填写适当的语句，完成该功能。#define MAXSTRLEN 255typedef unsigned char SStringMAXSTRLEN+1; /0号单元存放串长int Index(SString S, SString

10、T, int pos) if(pos=1&pos=S0) i=pos; j= (4) ; while(i=S0 & jT0) return (7) ; else return 0; else return 0; 3. 用链表实现的简单选择排序。设链表头指针为L, 链表无头结点，请填写适当的语句，完成该功能。void SelectSort(LinkList L) p=L; while(p) q=p; r=q-next; while( r ) if( (8) ) q=r; r= (9) ; tmp=q-data; q-data=p-data; p-data=tmp; p= (10) ; 六、 算法

11、设计题（16分）1.（8分）已知一个带有头结点的单链表，假设该链表只给出了头指针L。在不改变链表结构的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），若查找成功，则打印该结点的值，并返回1；否则，只返回0。 链表结构定义为：typedef struct Lnode ElemType data; struct Lnode *next; LNode, *LinkList;2、(8分) 下题中任选一题（1）给定一棵赫夫曼树T，编写算法，求该赫夫曼树T的带权路径长度。赫夫曼树T采用如下定义的存储结构：typedef struct BiTNodeTElemType d

12、ata; /此处data代表结点的权值struct BiTNode *lchild, *rchild;BiTNode, *BiTree;（2）假设一棵二叉树以二叉链表表示，元素值为整数，且元素值无重复，编写算法，打印以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。二叉树T采用如下定义的存储结构：typedef struct BiTNodeTElemType data; struct BiTNode *lchild, *rchild;BiTNode, *BiTree;（3）设计一算法，要求将二叉树的叶结点按从左到右的顺序连成一个单链表，表头指针为head, 二叉树按二叉链表方式存储，链

13、接时用叶结点的右指针域来存放单链表指针，分析算法的时间、空间复杂度。假设二叉树T采用如下定义的存储结构：typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree;一、 填空题1. O(1) 随机存取2. 803. 防止数组下标越界4. Head【Head【Tail【Tail（LS）】5. A3 A5 A76. 活动 活动之间的先后关系7. 该有向图无环8. DEF二、 选择题1.D 2.C 3.D 4.C 5.A6.B 7.C 8.B 9.D 10.D三、 判断题1. 2. 3.

14、4. 5.6. 7. 8. 9. 10.四、 应用题1. 2. (1) 邻接矩阵：邻接表：(2) 深度优先搜索树为：(3)最小生成树：3. (1)二叉排序树如下：平均查找长度ASL=(1+2X2+4X3+3X4)/10=2.9(2)按照右子树根节点左子树的顺序遍历该二叉树，即可得到从大到小的顺序(3) (4)25、12、7、15、34、47、65、47+、16、7916、15、12、7、25、47、65、79、47+、34初始堆：79、47+、65、34、16、47、12、7、25、15第一趟排序后：65、47+、47、34、16、15、12、7、25、79（二叉树表示方法也可）五、 程序填空

15、题1. L2. p-next = s3. p = s4. 15. i = i - j + 26. j = 17. i j + 18. q-data r-data9. r-next10. p-next六、 算法设计题1. 三种基本思路，（1）设一指针p指向链表的第1个结点，之后找到离p距离为k的结点q（如果有的话），然后p与q同时移动，直到q指向链表尾部。（2）计算出单链表的长度，从而计算出要查找的节点在正向的位置，再从头遍历，将其找出。（3）将单链表所有节点入栈，出栈过程中找到第K个节点。第一种思路可得满分，后两种扣2分。第二种方法参考代码：int Search(LinkList L, int

16、 k) Lnode *p; int length = 0, i; if(!L | !L-next) return -1; p = L-next; while(p) length+; p = p-next; if(length next; for(i=0; inext; printf(“该元素为：%dn”, p-data); return p-data;2. (1)int Hvalue(BiTree T, int h) int lvalue, rvalue; if(!T) return 0; if(T-lchild = NULL & T-rchild = NULL) return h*T-dat

17、a; lvalue = Hvalue(T-lchild, h+1); rvalue = Hvalue(T-rchild, h+1); return lvalue + rvalue;(2)采用先序遍历方式遍历整棵树，设置标志位，标识是否找到所需节点，若找到，则打印其子树，同时后续监视是否已经返回，若返回则关闭标志，停止打印bool flag=false;int Print(BiTree T, int k) if(!T) return 0; if(T-data = k) flag = true; if(flag) printf(“%d ”, T-data); Print(T-lchild, k);

18、 Print(T-rchild, k); if(T-data = k) flag=false;（3）采用先序遍历方式遍历整棵树，如果找到叶子结点，则将其串到链表中。bool FirstLeafNode=TRUE; /全局变量BiTree L, q; /全局变量void ChainLeafNode(BiTree T)if(!T) return;if(!T-lchild & !T-rchild) if(FirstLeafNode) L=T; FirstLeafNode=FALSE; else q-rchild=T; q=T; else if(T-lchild) ChainLeafNode(T-lchild); if(T-rchild) ChainLeafNode(T-rchild);