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

一、选择题

1、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a， e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（　　）。

A.a，b，e，c，d，f，c，f,e，b，d

C.a，e，b，c，f，e，d，f，c，b

2、将线性表的数据元素进行扩充，允许带结构的线性表是（　　）。

A.串 树 广义表 栈

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、已知串S='aaab'，其next数组值为（　　）。

A.0123    B.1123    C.1231         D.1211

6、下列选项中，不能构成折半查找中关键字比较序列的是（　　）。

A．500，200，450，1．500，450，200，180

C．180，500，200，4．180，200，500，450

7、下列关于无向连通图特性的叙述中，正确的是（　　）。

Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1

A．只有Ⅰ．只有Ⅱ  C．Ⅰ和Ⅱ．Ⅰ和Ⅲ

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

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

9、在下述结论中，正确的有（　　）。

①只有一个结点的二叉树的度为0。

②二叉树的度为2。

③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A.①②③

B.⑦③④

C.②④

D.①④

10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（　　）。

A.每次分区后，先处理较短的部分

B.每次分区后，先处理较长的部分

C.与算法每次分区后的处理顺序无关

D.以上三者都不对

二、填空题

11、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。

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

13、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。

14、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。

15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。

16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么

（1） 存放该数组至少需要的单元数是______。

（2） 存放数组的第8列的所有元素至少需要的单元数______。

（3） 数组按列存储时，元素A[5，8]的起始地址是______。

17、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。

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

三、判断题

19、文件系统采用索引结构是为了节省存储空间。（　　）

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

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

22、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（　　）

23、二叉树是一般树的特殊情形。（　　）

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

25、算法的优劣与算法描述语言无关，但与所用计算机有关。（　　）

26、排序算法中的比较次数与初始元素序列的排列无关。（　　）

27、无环有向图才能进行拓扑排序。（　　）

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

四、简答题

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

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

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

30、下面程序段的时间复杂度是什么？

31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：

世界六大城市交通里程表(单位：百公里)

（1）画出这六大城市的交通网络图。

（2）画出该图的邻接表表示法。

（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。

五、算法设计题

32、在一个循环链队中只有尾指针（记为rear，结点结构为数据域data，指针域next），请给出这种队列的入队和出队操作的实现过程。

33、串以静态存储结构存储，结构如下所述，试实现串操作equal算法。

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

35、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用 llink—rlink法存储。

参

一、选择题

1、【答案】D

2、【答案】C

3、【答案】A

4、【答案】D

5、【答案】A

6、【答案】A

7、【答案】A

8、【答案】C

9、【答案】D

10、【答案】A

二、填空题

11、【答案】480+8=488；480-32=448

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

13、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。

14、【答案】有穷性；确定性；可行性

15、【答案】O（1）；O（n）

16、【答案】270；27；2204

17、【答案】

【解析】最大的分支结点是最后一个叶子结点的父结点。

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、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。

31、答：(1)这六大城市的交通网络图如图所示：

(2)该图的邻接表表示法如图所示：

(3)最小生成树有6个顶点与条边：V(G)={Pe，N，Pa，L，T，M} E(G)=｛(L，Pa，3)，(Pe，T，21)，(M，N，32)，(L，N，55)，(L， Pe，81)}

五、算法设计题

32、答：算法如下：

33、答：算法如下：

34、答：算法如下：

35、答：算法如下：