精品语大学计算机科学与技术专业《数据结构与算法》科目期末试卷A精品 .pdf

2022年北京外国语大学计算机科学与技术专业《数据结构与算法》科

目期末试卷A(有答案)

一、选择题

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

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

2、设有一个10阶的对称矩阵A,采用压缩存储方式，以行序为主存储，al为第一元素,

其存储地址为1,每个元素占一个地址空间，则a85的地址为()。

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

3、线性表的顺序存储结构是一种()。

A■随机存取的存储结构顺序存取的存储结构

C.索引存取的存储结构存取的存储结枸ash

4、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7),E4V1,V2,

V1,V3,V1,V4,V2,V5,V3,V5,V3V6,V4,V6,V5,V7,

V6,V7},G的拓扑序列是()。

A.VI,V3,V4,V6,V2,V5,V7,V骞AA12,V6,V4,V5,V7

C.V1,V3,V5,V2,V6,V7,V2,V5,IWV4,V6,V7

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

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

6、循环队列放在一维数A中，endl指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M—1个元素。初始时为空，

下列判断队空和队满的条件中，正确的是()。

A.队空：endl==end2;队满:endl==(end2+l)modM

B.队空：endl==end2;队满:end2==(endl+1)mod(M—1)

C.队空：end2==(endl+1)modM队满：endl==(end2+l)modM

D.队空：endl==(end2+l)modM队满：end2==(endl+1)mod(M—1)

13、已知有序表为（12,18,24,35,47,50,62,83,90,115,134）当用二分法查

找90时，需次查找成功，查找47时成功，查找100时，需次才能确

定不成功。

14、建立索引文件的目的是o

15、一个算法具有5个特性：.、、有零个或多个输入、有一个或多个输

出。

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

为O

17、已知一循环队列的存储空间为[m..n],其中nm,队头和队尾指针分别为front和

rear,则此循环队列判满的条件是。

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

三、判断题

19、倒排序文件的优点是维护简单。（）

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

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

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

23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）

24、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）

25、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与

链表的长度无关。（）

26、在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（）

27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加

闲置空间的碎片。（）

28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的

所在位置置空，因为这会影响以后的查找。（）

四、简答题

29、对于具有n个叶结点且所有非叶结