2022年武汉纺织大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

2022年武汉纺织大学计算机科学与技术专业《数据结构与算法》科目

期末试卷A（有答案）

一、选择题

1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组

表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.33

2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿

链移动的操作为（）。

A.j=r[j].nextB.j=j+lC.j=j-nextD.j=r[j]-next

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

A.效率B.复杂性C.现实性D.难度

4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。

A.543612B.453126C.346521D.234156

5、向一个栈顶指针为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

6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字

3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

7、若元素a，b，c，d，e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三

次进行退栈操作，则不可能得到的出栈序列是（）。

8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

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

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

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

10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，

4，8，20，9，7}则该次采用的增量是（）。

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

二、填空题

11、在哈希函数H（key）=key%p中，p值最好取______。

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

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

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

______的排序方法。

14、文件由______组成；记录由______组成。

15、文件可按其记录的类型不同而分成两类，即______和______文件。

16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是

BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵

树转换而成，则该树的前序序列是______。

17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。

18、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为

______。

三、判断题

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

20、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。

（）

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

22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）

23、树形结构