2022年重庆工商大学计算机科学与技术专业《数据结构与算法》科目期末试...

一、选择题

1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（　　）。

A.5       B.6     C.8          D.9

2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。

A.13    B.33       C.18         D.40

3、算法的计算量的大小称为计算的（　　）。

A.效率 复杂性 现实性 难度

4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（　　）。

A.h->next=s

B.s->next=h

C.s->next=h;h->next=s

D.s->next=h-next;h->next=s

5、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。

A.（rear+1）MOD n=front

B.rear=front

C.rear+1=front

D.（rear-1）MOD n=front

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b， c，d，e，a，则根结点的孩子结点（　　）。

A．只有e  B．有e、b．有e、c．无法确定

7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。 

Ⅰ．简单选择排序Ⅱ．希尔排序 Ⅲ．快速排序 Ⅳ．堆排 Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、Ⅳ．仅Ⅰ、Ⅱ、Ⅲ  C．仅Ⅱ、Ⅲ、Ⅳ．仅Ⅲ、Ⅳ、Ⅴ

8、一个具有1025个结点的二叉树的高h为（　　）。

A.11     B.10       C.11至1025之间  至1024之间

9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（　　）。

A.1           B.4              C.3               D.2

二、填空题

11、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。

12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。

13、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子， rflag=1，right指向其后继。

14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。

15、设单链表的结点结构为（data，next），next为指针域，已知指针px 指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y 插入结点x之后，则需要执行以下语句：______

16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。

17、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。

18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85的地址为______。

三、判断题

19、直接访问文件也能顺序访问，只是一般效率不高。（　　）

20、倒排文件是对次关键字建立索引。（　　）

21、数组不适合作为任何二叉树的存储结构。（　　）

22、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（　　）

23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（　　）

24、深度为k的二叉树中结点总数小于等于2k-1。（　　）

25、为了很方便地插入和删除数据，可以使用双向链表存放数据。

（　　）

26、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（　　）

27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（　　）

28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（　　）

四、简答题

29、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。

30、设有n个元素采用起泡排序法进行排序，通常需要进行多少趟排序? 对于第J趟起泡通常需要进行多少次关键字比较?在程序设计中如何设置判断条件，有可能使起泡趟数可以减少并且能完成排序。

31、设将n（n＞1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循左移P（0＜P＜ n）个位置，即将R中的数据由（X0，X1，…，Xn－1）变换为（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：

（1） 给出算法的基本设计思想。

（2） 根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。

五、算法设计题

32、已知字符串s1中存放一段英文，写出算法format（s1，s2，s3，n），将其按给定的长度n格式化成两端对齐的字符串s2，其多余的字符送 s3。

33、设从键盘输入一整数的序列：a1，a2，a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai入栈；当ai=-l时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。

34、编写程序，统计在输入字符串中各个不同字符出现的频度并将结果存入文件（字符串中的合法字符为A～Z这26个字母和0～9这10个数字）。

35、写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag，lc，data，rc， rtag）。其中，data存放结点的值；lc、rc为指向左、右孩子或该结点前驱、后继的指针，ltag、rtag为标志域，若值为0，则lc、rc为指向左、右孩子的指针；若值为1，则lc、rc为指向其前驱、后继结点的指针。

参

一、选择题

1、【答案】A

2、【答案】B

3、【答案】B

4、【答案】D

5、【答案】B

6、【答案】A

7、【答案】A

8、【答案】C

9、【答案】C

10、【答案】B 

二、填空题

11、【答案】2(N-1)

12、【答案】n(n-1)/2 

13、【答案】node->rflag==0；*x=bt；*x=node->right；prior（t，x）

14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M ,Y）；（F，H， C，D，a，A，M，Q，R，S，Y，X）

15、【答案】py->next=px->next；px->next=py

16、【答案】FEGHDCB；BEF

【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。

17、【答案】

【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。

18、【答案】33

三、判断题

19、【答案】×

20、【答案】√

21、【答案】×

22、【答案】×

23、【答案】×

24、【答案】√

25、【答案】√

26、【答案】×

27、【答案】×

28、【答案】√

四、简答题

29、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个

栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：

30、答：n个元素采用起泡排序法进行排序，通常需要进行n-1趟排序。第j趟起泡排序要进行n-j次比较。在一趟排序中，若没有记录交换，则表示排序完成。因而，可通过设标记来控制排序结束，下面语句段说明了标记 flag的使用。

31、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…， xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再将数组R中的前n－P个数和后P个数分别原地逆置，最终得到结果xp，xp＋1，…，xn－1，x0，x1，…，xp－1。

（2）用C语言算法描述如下：

（3）说明算法的复杂性：上述算法中3个Reverse函数的时间复杂度分别为O（p/2）、O（（p－2）/2）为O（n/2），故算法的时间复杂度为O（n），算法的空间复杂度为O（1）。

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：