数据结构试题 试卷四 含答案.pdfVIP

模拟试题四

模拟试题四

一、选择题（20分）

1.由两个栈共享一个存储空间的好处是()。

A)减少存取时间，降低下溢发生的几率

B)节省存储空间，降低上溢发生的几率

C)减少存取时间，降低上溢发生的几率

D)节省存储空间，降低下溢发生的几率

2.设有两个串p和q，求q在p中首次出现位置的运算称做()。

A)连接B）模式匹配C）求子串D）求串长

3.n个顶点的连通图中边的条数至少为()。

A)0B)lC)n-lD）n

4.对一个具有n个元素的线性表，建立其有序单链表的时间复杂度为()。

A)O(n)B)O(1)C)O(n2)D)O(log2n)

5.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是()。

A)p-next=s;s-prior=n;p-next-prior=s;s-next:p-next.

B)s-priOFp;s-next-p-next;p-next=s;p-next-priOFS。

C)p-next=s;p-next-priOFS;s-prior=p;s-next=p-next.

D)s-prior=p;s-next=p-next;p-next-priOFS;p-next=S。

6，串的长度是()。

A)串中不同字符的个数B）串中不同字母的个数

C)串中所含字符的个数n(n0)D)串中所含字符的个数n(n≥0)

7.若有一个钱的输入序列是l，2，…，n，输出序列的第一个元素是n，则第i个输出

元

素是()。

A)n-iB)n-i-lC）n-i+lD）不确定

8.设有一个栈，元素的进栈次序为A，B，C，D，E，下列()是不可能的出栈序列。

A)A,B,C,D,EB)B,C,D,E,A

C)E,A,B,C,DD)E,D,C,B,A

9.在一棵度为3的树中，度为3的结点数有2个，度为2的结点数有1个，度为l的结

点数有2个，那么度为0的结点数有()个。

A)4B)5C)6D)7

10.在一个具有n个结点的无向完全图中，包含有()条边。

A)n(n-l)/2B)n(n-l)C)n(n+l)/2D)nn

二、填空题（每小题2分，共20分）

1.数据逻辑结构包含__________三种类型，树型结构和图形结构合称__________。

2.某算法在求解一个10阶方程组时，运算次数是500，求解二个30阶方程组时，运算

次数是4500，则该算法的时间复杂度为__________。

3.在一个长度为n的顺序表个插入一个元素，最少需要移动__________个元素，最多需

要移动__________个元素。

4.如果某有向图的所有顶点可以构成一个拓扑排序序列，则说明该有向图__________。

5.在双向循环链表中，在指针p所指的结点之后插入指针f所指的结点，其操作为___

_______。

6.一数组的长度为20，用于存放一个循环队列，则队列最多只能有__________个元素。

7.无向图用邻接矩阵存储，其所有元素之和表示无向图的__________。

8.一个具有n个结点的线性表采用堆排序，在建堆之后还要进行__________次堆调整。

9.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和__________。

10.若频繁地对线性表进行插入与删除操作，该线性表应采用__________存储结构。

三、简答题(36分)