2022年泉州师范学院计算机科学与技术专业《数据结构与算法》科目期末试.pdfVIP

2022年泉州师范学院计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、n个结点的完全有向图含有边的数目（）。

A.n*nB.n(n+1)C.n/2D.n*(n-1)

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、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛V1，V2，

V1，V3，V1，V4，V2，V5，V3，V5，V3，V6，V4，V6，V5，V7，

V6，V7｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7，D.V1V2，V5，V3，V4，V6，V7

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，

则根结点的孩子结点（）。

A．只有eB．有e、b．C有e、c．无D法确定

7、已知字符串S为“abaabaabacacaabaabcc，”模式串t为“abaabc，”采用KMP算法进行

匹配，第一次出现失配“”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别

（）。

A．i＝1，j＝0B．i＝5，j＝0．Ci＝5，j＝2．Di＝6，j＝2

8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结

果为（）。

A.CBEFDAB.FEDCBAC.CBEDFA不定D.

9、有n（n0）个分支结点的满二叉树的深度是（）。

A.n-1

2

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果

为（）。

A.（2，5，12，16）26（60，32，72）

B.（5，16，2，12）28（60，32，72）

C.（2，16，12，5）28（60，32，72）

D.（5，16，2，12）28（32，60，72）

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排

序树检索时，平均比较次数为______。

12、无用单元是指______，例______

13、VSAM系统是由______、______、______构成的。

14、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用

______的排序方法。

15、数据结构中评价算法的两个重要指标是______。

16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]

与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。

17、模式串P=‘abaabcac’的next函数值序列为______。

18、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（