苏州大学872考研试题12-15

2、在顺序线性表下，根据位置position来进行元素的插入和删除，主要的时间花费在       ；在单链表下进行元素的插入和删除，主要时间花费在       。

3、一个10×10的矩阵，如果以行为主序存入内存，则其容量为             。设a11是第一个元素，其存储地址为1，每元素占1个地址空间，则a85的地址为                  。

4、在线性表改进的单链表实现方法中，我们定义了一个current指针指向最近访问过的结点，定义的方法是：mutable Node *current；请解释这里mutable的作用：                                                     。

5、用二分查找方法进行查找，要求数据文件应为                  ，且限于

             存储结构。

6、在哈希查找中，评判一个哈希函数优劣的两个主要指标是：______________         和              。

7、快速排序的最坏时间复杂度为             ；平均时间复杂度为              。

8、图的遍历算法有两种：                      和                    。

9、由三个结点构成的二叉树，共有          种不同的结构。

二、应用题(40分)

1、设有n个无序记录的顺序表（每一条记录由一个对应的关键字），简述利用二叉查找树对此记录表进行树排序的方法。（10分）

2、队列采用顺序结构实现（linear implementation）时，随着元素的出队，数组开始处的空间不能再次利用。如何解决这个问题？（10分）

3、简述拓扑排序的实际意义，并写出下图的两个拓扑序列。（10分）

     A                    

                 D

B                              I                J

                   H

E                                              L

         F                                 

                          K

         G

4、简述堆排序的基本方法，并对键值集合，{72，73，71，23，94，16，05，68}对应的二叉树建大顶堆。（10分）

三、算法设计题（30分）

1、设计一个递归算法，计算二叉树叶结点数目。（10分）

template

int Binary_tree :: recursive_leafcount(Binary_node *sub_root) const

2、以顺序存储结构实现两个有序表A、B的合并，合并结果放在A中。不可采用另外的辅助数组空间。（10分）

Error_code   connect(List  &a , const  List &b)

3、已知线性表的元素按递增顺序排列，并以带头结点的单链表作为存储结构。试编写算法删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。（10分）

template

Error_code List :: delete_min_max (List_entry min, List_entry max )

1、 下面程序段中带下划线的语句的执行次数的数量级是        。

i=1;

while (ifor (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

20    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={,,,,,,,}

(1)请画出该图，并写出邻接矩阵。

(2)根据邻接矩阵，分别给出从顶点a出发的深度优先和优先遍历序列。

(3)画出由此得到的深度优先和广度优先生成树。

3、已知一棵二叉树的中序序列为：BAFDJGCKHLEIM，后序序列为：BFJGDKLHMIECA。请完成：（10分）

（1）构造这棵二叉树。

（2）将这棵二叉树转化成树或森林。

4、一项工程P由P1、P2、P3…P6六项子工程组成，这些工程之间有下列关系，P1二、算法设计题(30分)

1、单链表中存放着n个字符，试设计算法判断该字符串是否中心对称，如xyzzyx即为中心对称的字符串。(可利用栈作为辅助量)（10分）

bool List :: is_ symmetrical ()

2、以二叉链表作为存储结构写出求二叉树结点总数的递归算法。（10分）

template

int Binary_tree :: recursive_nodecount(Binary_node *sub_root) const

3、将循环队列类定义为含有一个数组entry[0..maxqueue-1]以存放循环队列中的元素，还含有两个变量rear和len分别指示循环队列中队尾元素的位置和内含元素的个数。请设计此队列类和相应的出队的算法。（10分）

1、排序算法的性能下限用时间复杂度表示为               。

2、在有序表A[1..20]中，采用二分查找算法查找元素值等于A[12]的元素，所比较过的元素的下标依次为：                              。

4、在有n个顶点的有向图中，每个顶点的度最大可达             。

                  5、在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动               个元素。       

                  6、在拓扑排序中，拓扑排序的第一个顶点必定是                              _________________的顶点。

7、常用图的存储结构有                         、                              

和                           。

8、无向图的生成树是指含有图中所有的n个顶点                    的子图。

9、树的后序序列与对应二叉树的          序列相同，任何一棵二叉树是否都

能转换成树？          。

10、树与二叉树转换的依据是：                             。

11、限定在线性表的一端进行插入和删除的数据结构是_____________________，

满足先进先出原则的数据结构是                        。

12、设哈希函数H(k)=k mod 7,哈希表的地址空间为0～6，对关键字序列｛32，13，49，55，22，29｝，按线性探测法解决冲突（探测地址按线性递增），产生的哈希表中地址为3处的关键字为：         。

二、应用题

1、完成下列与队列有关的问题。（10分）

（1）写出队列的类定义。

（2）循环队列不能很好地判断队空和队满，用图示的方法进行举例说明。

2、对于下图所示的带权图，利用Dijkstra算法求出从源点v1到其余各顶点的最短路径及其长度，并写出在算法执行过程中，每求得一条最短路径后，当前从源点v1到其余各顶点的最短路径及其长度的变化。（10分）

      10        v2    25               v5

                       16       7

v1              3           v4          10

       12           12          2     

                v3         8        v 6

      4

3、 设待排序文件的关键字为（512,275,908,677,503,765,612,7,154,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_for_node

(Binary_node *subroot,const record &target)const

3、用字符串表示一个表达式，利用栈类完成括号匹配算法，允许出现的括号有圆括号和中括号两类，匹配返回true，否则返回false。

bool    is_matched(char *s)

1、下列算法的时间复杂度是                        。

    x=n;

    y=0;

while ((x>=（y+1）*（y+1）))

     y=y+1;    

4、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用______存储结构。

迪杰斯特拉提出了一个按                        次序产生最短路径的算法。

9、在                     情况下，链队列的出队操作需要修改尾指针。

2、有向图的                  称为有向图的强连通图。

5、中序遍历一个二叉排序树所得到的结点访问序列为              序列。

6、以关键字序列为{k0,k1,k2,…kn-1}建立一个堆。首先将该序列中的关键字依次排列到一棵完全二叉树上，然后从最后一个非叶结点开始到根结点为止，依次插入结点至已经完成的部分堆中。此非叶结点的编号                   个元素开始筛选。

7、假设二叉树根结点的层次为0，则二叉树的第k层上的结点总数最多为

            个。

8、假设一个12阶的下三角矩阵A按行优先顺序压缩存储在一维数组B[0..MAX-1]中，则B的容量MAX至少为               。如A矩阵的第一个元素为a00,则非零元素a98在B中的存储位置k=              。

10、n个顶点的无向连通图至少含有         条边，无向非连通图的连通分量是指：                 。

二、应用题

1、判别以下说法是否正确，并简单说明原因。

（1）队列是一种先进后出的数据结构。

（2）队列的顺序存储方案通常采用循环队列的方法。

（3）队列的顺序存储结构比链式存储结构更优越。

2、已知一个无向图的邻接表如下图所示，要求：（10分）

（1）画出该无向图。

（2）根据邻接表，分别写出DFS和BFS算法从顶点v0开始的遍历该图后所得到的遍历序列，并画出DFS生成树和BFS生成树。

0

1

2

3

4

5

6

3、设表达式a+b*(c-d)-e/f 可以表示成如下二叉树结构。

（1）请将此二叉树的结点填写完整。

（2）如果表达式以二叉树表示，简述对一个表达式进行求值的过程。（提示：可利用二叉树的后序遍历来进行）

4.线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。

三、算法设计题

1、为简单单链表类设计拷贝构造函数。（10分）

template 

List :: List(const List ©)

2、在递增有序顺序表下，完成顺序查找的递归算法。（10分）

Error_code sequential_search(const Ordered_List &the_list,const Key &target,int position)

3、二叉树以二叉链表作为存储结构，设计一个递归算法判断二叉树是否为二叉排序树。（10分）

template

int Binary_tree :: recursive_is_searchtree(Binary_node *sub_root) const