（精品课件）数据结构课程试卷13卷.docVIP

苏州大学 数据结构 课程试卷13卷（共 4 页） 考试形式：闭卷 年 月 院系 ______________ 年级 ______________ 专业 ______________ 学号 ______________ 姓名 ______________ 成绩 ______________ 一、填空题（2分×15） 1、 下面程序段中带下划线的语句的执行次数的数量级是 。 i=1; while (in) for (j=1 ;j=n; j++){ x=x+1; i=i*2; } 2、线性结构是一种一对一的结构，元素之间的关系是一对一的；树形结构是一种 的结构。 3、若某个线性表的最常用的操作是存取第i个元素及其前驱的值，则采用 _______________存储方式比较好。 4、在双向循环链表中，设指针p指向待删除的结点，则删除结点*p需执行的语句为： 。 5、设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push、 push、 pop、 push、 pop、 push、 push操作，输出的序列为 。 6、对一棵完全2-树的每个结点从1开始进行编号，编号的方法是从根开始，从左到右，从上到下。则编号为k的结点，其左孩子如果存在则编号为 ，右孩子如果存在编号为 。 7、按 遍历二叉排序树，可以得到按值递增的关键字序列，在图中所示的二叉树中，查找关键字85的过程中，需与85进行比较的关键字序列为 。 85 95 10 30 55 70 85 8、哈希查找中解决冲突的方法主要有： 、 。 9、判断一个有向图是否存在回路，可以采用 方法。 10、二维表格在计算中的存储表示的实质即是把二维的表格一维化，通常采用的方法有： 和 方式。 11、对记录进行顺序查找时，有时我们可以先把待查记录插入到查找表的尾部，然后再从头到尾进行查找，这种做法称为采用监视哨的方法。该方法的优点是： 。 二、应用题（40分） 1、已知一组元素为（45，25，80，60，18，30，12，40，70），试画出按元素输入排列顺序而生成的二叉排序树，求出等概率情况下查找成功与不成功时的平均查找长度。（10分） 2、已知一个图G=(V,E)，其中：（10分） V={a,b,c,d,e,f} E={a,b,a,d,a,e,d,ee,b,c,b,c,e,c,f,f,e} 请画出该图，并写出邻接矩阵。 根据邻接矩阵，分别给出从顶点a出发的深度优先和优先遍历序列。 画出由此得到的深度优先和广度优先生成树。 已知一棵二叉树的中序序列为：BAFDJGCKHLEIM，后序序列为：BFJGDKLHMIECA。请完成：（10分） 构造这棵二叉树。 将这棵二叉树转化成树或森林。 4、一项工程P由P1、P2、P3…P6六项子工程组成，这些工程之间有下列关系，P1P2,P3P6,P4P3,P2P6,P4P5,P1P3,P5P6，符号“”表示“先于”关系，例如P2P6，表示P2完成后P6才能开始。请给出工程P的三种可能的施工顺序。（10分） 二、算法设计题(30分) 单链表中存放着n个字符，试设计算法判断该字符串是否中心对称，如xyzzyx即为中心对称的字符串。(可利用栈作为辅助量)（10分） bool Listchar :: is_ symmetrical () 2、以二叉链表作为存储结构写出求二叉树结点总数的递归算法。（10分） template class Entry int Binary_treeEntry :: recursive_nodecount(Binary_nodeEntry *sub_root) const 3、将循环队列类定义为含有一个数组entry[0..maxqueue-1]以存放循环队列中的元素，还含有两个变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。请设计此队列类和相应的出队的算法。（1