2022年河海大学计算机科学与技术专业《数据结构与算法》科目期末...

一、选择题

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

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

2、下述文件中适合于磁带存储的是（　　）。

A.顺序文件

B.索引文件

C.哈希文件

D.多关键字文件

3、连续存储设计时，存储单元的地址（　　）。

A.一定连续  B.一定不连续 C.不一定连续D.部分连续，部分不连续

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、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（　　）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）

C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M

D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）

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

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

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

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

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

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。

A.二叉排序树         B.哈夫曼树           C.AVL树          D.堆

10、数据序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的（　　）的两趟排序后的结果。

A.选择排序  B.起泡排序  C.插入排序   D.堆排序

二、填空题

11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。

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

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

14、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树 T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。

15、已知有序表为（12，18，24，35，47，50，62，83，90，115， 134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。

16、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。

17、阅读下列程序说明和程序，填充程序中的______。

【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。

本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：

（1）把根结点放入堆栈。

（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。

（3）重复（2）直到堆栈为空时为止。

18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为 l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH， PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。

三、判断题

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

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

21、在链队列中，即使不设置尾指针也能进行入队操作。（　　）

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

23、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（　　）

24、树形结构中元素之间存在一对多的关系。（　　）

25、抽象数据类型与计算机内部表示和实现无关。（　　）

26、数据元素是数据的最小单位。（　　）

27、B-树中所有结点的平衡因子都为零。（　　）

28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（　　）

四、简答题

29、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。

(1)试问这种二叉树的结点总数是多少?

(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。

30、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87， 95）进行折半查找，试回答下列问题：

（1）画出描述折半查找过程的判定树。

（2）若查找元素54，需依次与哪些元素比较?

（3）若查找元素90，需依次与哪些元素比较?

（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。

31、已知一个整数序列A＝（a0，a1，…，an－1），其中0≤ai＜

n（0≤i≤n），若存在ap1＝ap2＝…＝apm＝x且m＞n/2（0≤pk≤n， 1≤k≤m），则称x为A的主元素。例如A＝（0，5，5，3，5，7，5， 5），则称5为主元素；又如A＝（0，5，5，3，5，1，5，7）则A中没有主元素。假设A中的n个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出－1。要求：

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

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

五、算法设计题

32、设二叉树用二指针结构存储（可以是动态存储结构），元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

33、按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i≠j)

34、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法delete（Linklist&L）。

35、设键盘输入n个英语单词，输入格式为n，w1，w2，…，wn，其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：

（1）如果单词重复出现，则只在链表上保留一个。

（2）除满足（1）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前k（k<=n）个单词。

参

一、选择题

1、【答案】A

2、【答案】A

3、【答案】A

4、【答案】D

5、【答案】C

6、【答案】A

7、【答案】A

8、【答案】C

9、【答案】D

10、【答案】C

二、填空题

11、【答案】

（1）p!=NULL //链表未到尾就一直进行

（2）q //将当前结点作为头结点后的第一元素结点插入

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

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

14、【答案】free（T）；q&&q->data!=A；q=q->rchild；p->lchild=null；p->rchild=null

15、【答案】2；4；3

【解析】二分法查找元素次数列表

查找100是找到115就停止了。

16、【答案】（rear+1）%（n-m+1）==front

17、【答案】stack[tp]=t；p=stack[tp--]；p；++tp

【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。

18、【答案】23；100CH

三、判断题

19、【答案】×

20、【答案】√

21、【答案】√

22、【答案】×

23、【答案】×

24、【答案】√

25、【答案】√

26、【答案】×

27、【答案】√

28、【答案】×

四、简答题

29、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。

（2）证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一

个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。

30、答：（1）判定树如图所示：

（2）    若查找元素54，需依次和元素30、63、42、54比较，查找成功。

（3）    若查找元素90，需依次和元素30、63、87、95比较，查找失败。

（4）

31、答：（1）算法的策略是从前向后扫描数组元素，标记出一个可能成为主元素的元素Num。然后重新计数，确认Num是否是主元素。

算法可分为以下两步：

①选取候选的主元素：依次扫描所给数组中的每个整数，将第一个遇到的整数Num保存到c中，记录Num的出现次数为1；若遇到的下一个整数仍等于Num，则计数加1，否则计数减1；当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，即从当前位置开始重复上述过程，直到扫描完全部数组元素。

②判断c中元素是否是真正的主元素，再次扫描该数组，统计c中元素出现的次数，若大于n/2，则为主元素；否则，序列中不存在主元素。

（2）算法实现如下：

（3）时间复杂度为O（n），空间复杂度为O（1）。

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：定义结点数据类型如下：

(1)算法如下：

(2)算法如下：