数据结构四套综合测试及答案 .pdfVIP

A卷

一、选择（共20分每题只有一个正确答案每题2分）

1．数据结构是（）

A．一种数据类型

B．数据的存储结构

C．一组性质相同的数据元素的集合

D．相互之间存在一种或多种特定关系的数据元素的集合

2．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（）

A．3，2，6，1，4，5B．3，4，2，1，6，5

C．1，2，5，3，4，6D．5，6，4，2，3，1

3．求单链表中当前结点的后继和前驱的时间复杂度分别是（）

A．O（n）和O（1）B．O（1）和O（1）

C．O（1）和O（n）D．O(n)和O（n）

4．已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所

指结点之后插入上述链表应执行的语句为()

A．q-next=s-next；s-next=p；B．s-next=p；q-next=s-next；

C．p-next=s-next；s-next=q；D．s-next=q；p-next=s-next；

5．已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若

字符串S=″SCIENCESTUDY″，则调用函数Scopy(S,Sub(S,1,7))后得到()

A．P=″SCIENCE″B．P=″STUDY″

C．S=″SCIENCE″D．S=″STUDY″

6．对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为()

A．（N+1）/2B．N/2C．ND．[（1+N）*N]/2

7．下列陈述中正确的是()

A．二叉树是度为2的有序树

B．二叉树中结点只有一个孩子时无左右之分

C．二叉树中必有度为2的结点

D．二叉树中最多只有两棵子树，并且有左右之分

8．设有一个10阶的对称矩阵A，采用下三角压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素

占一个地址空间，则a85的地址为（）。

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

9．设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为()

A．r-fB．r-f+1C．(r-f)modn+1D．(r-f+n)modn

10．下列关键字序列中，构成小根堆的是()

A．{84，46，62，41，28，58，15，37}

B．{84，62，58，46，41，37，28，15}

C．{15，28，46，37，84，41，58，62}

D．{15，28，46，37，84，58，62，41}

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

1．链式存储结构的特点是借助_______来表示数据元素之间的逻辑关系。

2．假设带头结点的非空单循环链表中仅设尾指针L，则在第1个数据元素结点之前插入指针s所指结点的语句依次是______；

______。

3．无表头结点的链队列Q为空的条件是_______。

4．不含任何字符的串称为_______。

5．表达式“a*b+c/d*f-g”的后缀表达式为___________。

6．如果排序过程称该排序方法是稳定的

7．由权值分别为4，6，2，3的叶子生成一个哈夫曼树，它的带权路径长度为

8．从空树起，依次插入关键字73，1l，35，48，52，27，66构造所得的二叉排序树，在等概率查找的假设下，查找成功时

的平均查找长度为____________________。

9．判断线索二叉树中某结点指针P所指结点有左孩子的条件是_______。

三、应用题（共50分）

1．简述顺序表和链表存储方式的特点。（6分）

2．（1）已知一个二叉树如图1所示：写出该二叉树的先序，中序，后序遍历序列（3分）

（2）把图1对应的二叉树转换为所对应的森林。（3分