苏州大学872考研试题1215

1、1、 在任何需要数据反转的问题里，首先应考虑用 来保存数据。2、在顺序线性表下，根据位置position来进行元素的插入和删除，主要的时间 花费在；在单链表下进行元素的插入和删除，主要时间花费在。3、一个10X10的矩阵，如果以行为主序存入内存，则其容量为。 设a11是第一个元素，其存储地址为1,每元素占1个地址空间，则a85的地址 为。4、在线性表改进的单链表实现方法中，我们定义了一个current指针指向最近访 问过的结点，定义的方法是：mutable Node *current；请解释这里 mutable 的作用： 。5、 用二分查找方法进行查找，要求数据文件应为，且限于 存储结构。6、

2、在哈希查找中，评判一个哈希函数优劣的两个主要指标是：和。7、快速排序的最坏时间复杂度为；平均时间复杂度 为。8、 图的遍历算法有两种： 和 。9、 由三个结点构成的二叉树，共有 种不同的结构。二、应用题（40分）1、设有n个无序记录的顺序表（每一条记录由一个对应的关键字），简述利用二 叉查找树对此记录表进行树排序的方法。（10分）2、队列采用顺序结构实现（linear implementation）时，随着元素的出队，数组 开始处的空间不能再次利用。如何解决这个问题？ （10分）3、简述拓扑排序的实际意义，并写出下图的两个拓扑序列。（10分）G4、简述堆排序的基本方法，并对键值集合，72, 7

3、3, 71, 23, 94, 16, 05, 68对应的二叉树建大顶堆。(10分)三、算法设计题（30分）1、设计一个递归算法，计算二叉树叶结点数目。（10分）template int Binary_tree : recursive_leafcount（Binary_node *sub_root） const2、以顺序存储结构实现两个有序表A、B的合并，合并结果放在A中。不可采 用另外的辅助数组空间。(10分)Error_code connect(List &a , const List &b)3、已知线性表的元素按递增顺序排列，并以带头结点的单链表作为存储结构。 试编写算法删除表中所有值大于

4、min且小于max的元素(若表中存在这样的元 素)的算法。(10分)template Error_code List : delete_min_max (List_entry min, List_entry max )1、 下面程序段中带下划线的语句的执行次数的数量级是。i=1;while (in)for (j=1 ;j=n; j+)x=x+1;i=i*2;2、线性结构是一种一对一的结构，元素之间的关系是一对一的；树形结构是一种 的结构。3、 若某个线性表的最常用的操作是存取第i个元素及其前驱的值，则采用存储方式比较好。4、在双向循环链表中，设指针p指向待删除的结点，则删除结点*p需执行的语句

5、为:5、设有一个空栈，栈顶指针为1000H，现有输入序列为1, 2, 3, 4, 5,经过push、 push、 pop、 push、 pop、 push、 push 操作，输出 的序列 为。6、对一棵完全2-树的每个结点从1开始进行编号，编号的方法是从根开始，从 左到右，从上到下。则编号为k的结点，其左孩子如果存在则编号 为，右孩子如果存在编号为。7、按 遍历二叉排序树，可以得到按值递增的关键字序列，在图 中所示的二叉树中，查找关键字85的过程中，需与85进行比较的关键字序列 为。8、 哈希查找中解决冲突的方法主要有：、。9、 判断一个有向图是否存在回路，可以米用 方法。10、二维表格在计算

6、中的存储表示的实质即是把二维的表格一维化，通常采用的方法有： 和 方式。11、对记录进行顺序查找时，有时我们可以先把待查记录插入到查找表的尾部， 然后再从头到尾进行查找，这种做法称为采用监视哨的方法。该方法的优点 是：。二、应用题（40分）_1、已知一组元素为（45, 25, 80, 60, 18, 30, 12, 40, 70），试画出按元素输 入排列顺序而生成的二叉排序树，求出等概率情况下查找成功与不成功时的平均 查找长度。（10分）2、已知一个图G=(V,E)，其中：(10分)V=a,b,c,d,e,fE=,请画出该图，并写出邻接矩阵。根据邻接矩阵，分别给出从顶点a出发的深度优先和优先遍

7、历序列。 画出由此得到的深度优先和广度优先生成树。3、已知一棵二叉树的中序序列为：BAFDJGCKHLEIM3、BFJGDKLHMIECA。请完成：（10 分）（1）构造这棵二叉树。（2）将这棵二叉树转化成树或森林。4、一项工程P由P1、P2、P3P6六项子工程组成，这些工程之间有下列关系， P1P2,P3P6,P4P3,P2P6,P4P5,P1P3,P5P6，符号“”表示“先于”关系， 例如P2P6,表示P2完成后P6才能开始。请给出工程P4、（10 分）二、算法设计题（30分）1、单链表中存放着n个字符，试设计算法判断该字符串是否中心对称，如xyzzyx 即为中心对称的字符串。（可利用栈作

8、为辅助量）（10分）bool List : is_ symmetrical （）2、以二叉链表作为存储结构写出求二叉树结点总数的递归算法。(10分)template int Binary_tree : recursive_nodecount(Binary_node *sub_root) const3、将循环队列类定义为含有一个数组entry0.maxqueue-1以存放循环队列中的 元素，还含有两个变量rear和len分别指示循环队列中队尾元素的位置和内含元 素的个数。请设计此队列类和相应的出队的算法。（10分）1、 排序算法的性能下限用时间复杂度表示为。2、在有序表A1.20中，采用二分查找

9、算法查找元素值等于A12的元素，所比 较过的元素的下标依次为：。4、在有n个顶点的有向图中，每个顶点的度最大可达5、在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动 个元素。6、在拓扑排序中，拓扑排序的第一个顶点必定是的顶点。7、 常用图的存储结构有 、和 。8、 无向图的生成树是指含有图中所有的n个顶点 的子图。9、 树的后序序列与对应二叉树的 序列相同，任何一棵二叉树是否都能转换成树？ 。10、 树与二叉树转换的依据是。11、 限定在线性表的一端进行插入和删除的数据结构是，满足先进先出原则的数据结构是 。12、设哈希函数H（k）=k mod 7,哈希表的地址空

10、间为06，对关键字序列32，13, 49, 55, 22, 29，按线性探测法解决冲突（探测地址按线性递增），产生的哈希表 中地址为3处的关键字为：。二、应用题1、完成下列与队列有关的问题。（10分）（1）写出队列的类定义。（2）循环队列不能很好地判断队空和队满，用图示的方法进行举例说明。2、对于下图所示的带权图，利用Dijkstra算法求出从源点v1到其余各顶点的最 短路径及其长度，并写出在算法执行过程中，每求得一条最短路径后，当前从源 点v1到其余各顶点的最短路径及其长度的变化。（10分）43、设待排序文件的关键字为（512,275,908,677,503,765,612,897,154,

11、170）以第 一元素为分界元素进行快速排序（按关键字值递增顺序），画出一趟排序过程的示意图，并给出一趟扫描后的结果。（8分）4、画出对长度为10的有序表进行折半查找的判定树，并求其等概率情况下查找 成功与不成功时的平均查找长度。（10分）三、算法设计题1、有一个带头结点的单链表，写出在其值为x的结点之后插入m个结点的算法。（10 分）Error_code insert_m（const List_entry &x, List a_list, int m）2、设计在二叉排序树下根据关键字进行查找的递归算法。(10分)template Binary_node * Search_tree:search

12、_for_node(Binary_node *subroot,const record &target)const3、用字符串表示一个表达式，利用栈类完成括号匹配算法，允许出现的括号有 圆括号和中括号两类，匹配返回true，否则返回false。bool is_matched（char *s）1、 下列算法的时间复杂度是。x=n;y=0;while （x= （y+1）* （y+1）y=y+1;4、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 存储结构。迪杰斯特拉提出了一个按 次序产生最短路径的算法。9、在 情况下，链队列的出队操作需要修改尾

13、指针。2、 有向图的 称为有向图的强连通图。5、 中序遍历一个二叉排序树所得到的结点访问序列为 序列。6、以关键字序列为k0,k1,k2,kn-1建立一个堆。首先将该序列中的关键字依次排列到一棵完全二叉树上，然后从最后一个非叶结点开始到根结点为止，依次插 入结点至已经完成的部分堆中。此非叶结点的编号 个元素 开始筛选。7、假设二叉树根结点的层次为0，则二叉树的第k层上的结点总数最多为 个。8、假设一个12阶的下三角矩阵A按行优先顺序压缩存储在一维数组B0.MAX-1 中，则B的容量MAX至少为。如A矩阵的第一个元素为a00, 则非零元素a98在B中的存储位置k=。10、n个顶点的无向连通图至少

14、含有 条边，无向非连通图的连通分量是指：。二、应用题1、判别以下说法是否正确，并简单说明原因。（1）队列是一种先进后出的数据结构。（2）队列的顺序存储方案通常采用循环队列的方法。（3）队列的顺序存储结构比链式存储结构更优越。22、3、设表达式a+b*(c-d)-e/f可以表示成如下二叉树结构。请将此二叉树的结点填写完整。如果表达式以二叉树表示，简述对一个表达式进行求值的过程。(提示:可利用二叉树的后序遍历来进行)4.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动 大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不 能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都 能够克服上述三个弱点，试讨论之。三、算法设计题1、为简单单链表类设计拷贝构造函数。(10分)template List : List(const List ©)2、在递增有序顺序表下，完成顺