数据结构-题集.doc

选择题

1.c语言版数据结构中自定义结构通常用………………（）

A、结构体B、共同体C、变量D、类

2.算法分析的目的是（C）。

A．找出数据结构的合理性B．分析算法的效率以求改进

C．研究算法中的输入和输出的关系D．分析算法的易懂性和文档性

3.以下说法错误的是（C）。

A．完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达

B．在三叉链表上，二叉树的求双亲操作很容易实现

C．在二叉链表上，求双亲操作的时间性能很好

D．在二叉链表上，求根以及求左、右孩子等操作很容易实现

4.将含有41个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为21的双亲结点编号为（D）。

A．20B．11C．41D．10

5.设指针P指向双链表的某一结点，则双链表结构的对称性可用（C）式来刻画。

A．p-prior-next==p-next-prior；B．p-prior-prior==p-next-prior；

C．p-next-next==p-prior-prior；D．p-prior-next==p-next-next；

6.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数最少为（B）个。

A．k+1B．2k-1C．2kD．2k+1

7.一个栈的入栈序列是a，b，c，d，e，则栈的不可能输出序列（C）。

A．e，d，c，b，aB．d，e，c，b，a

C．d，c，e，a，bD．a，b，c，d，e

8.设森林T中有4棵树，结点个数分别是n1、n2、n3、n4，当把森林T转换成一棵二叉树后，根结点的右子树上有（D）个结点。

A．n1-1B．n1C．n1+n2+n3D．n2+n3+n4

9.从栈顶指针为Top的链栈中删除一个结点，并将被删结点的值保存到x中其操作步骤为（A）。

A．x=Top-data;Top=Top-next;B．Top=Top-next;x=Top-data;

C．x=Top;Top=Top-next;D．x=Top-data;

10.n个结点的线索二叉树中的线索数目为（C）。

A．（n-1）个B．(n+1)个C．n个D．(n+2)个

11.设串S1=‘ABCDEFG’，S2=‘PQRST’，函数StringConcat(X，Y)返回X和Y串的连接串，SubString(S，I，J)返回串S中从序号I的字符开始的J个字符组成的子串，StringLength(S)返回串S的长度，则StringConcat(SubString(S1，2，StringLength(S2))，SubString(S1，StringLength(S2)，2))的结果串是（C）。

A．‘BCDEF’B．‘BCDEFG’C．‘BCDEFEF’D．‘BCDQRST’

12.二维数组A[1..10，1..20]采用列序为主序方式存储，每个数据元素占1个存储单元，且A[1，1]的存储地址是200，则A[6，12]的存储地址是（）。

A．317B．730C．313D．315

13.将长度为n的单链表接在长度为m的单链表之后的算法的时间复杂度为（C）

A、O(1)B、O(n)C、O(m)D、O(m+n)

a

a

d

c

e

b

填空题

1.设n为正数，试确定以下程序段中前面加@的语句的频度：

k=0

for(i=1,i=n;i++)

for(j=i;j=n;j++)

@k++

2.常见时间复杂度的量级有：常数阶O（）、对数阶O（）、线性阶O（）、平方阶O（）和指数阶O（）。通常认为，具有指数阶量级的算法是