（大题）数据结构练习题(1)

模拟练习题

一、单项选择题

1、若某线性表中最常用的操作是取第i个元素和查找第i个元素的的前驱元素，则采用（ A）的存储方式最节省时间。 A．顺序表 C．单链表

B．双链表 D．单循环链表

2、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ C ）。 A．存储结构 C．逻辑结构

B．存储实现 D．运算实现

3、用链表表示线性表的优点是 （ C）。

A．便于随机存取 B.花费的存储空间较顺序存储少 C．便于插入和删除 D.数据元素的物理顺序与逻辑顺序相同

4、设单向循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（D ） A．s=rear; rear=rear->link; free(s); B．rear=rear->link; free(rear);

C．rear=rear->link ->link; free(rear);

D．s=rear->link->link; rear->link->link=s->link; free(s);

5、设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p所指结点之后（右链方向）插入指针s所指的结点，则应执行下列哪个操作？（ D ） A．p-> rLink =s;s-> lLink=p;p->rLink->lLink=s;s->rLink=p->rLink B．p-> rLink =s; p->rLink->lLink=s;s->lLink=p; s->rLink=p->rLink C．s->lLink=p;s->rLink=p->rLink;p->rLink=s;p->rLink->lLink=s; D．s->lLink=p;s->rLink=p->rLink;p->rLink->lLink=s;p->rLink=s;

6、在具有n个结点的有序单链表中插入一个新结点并使该链表仍然有序的时间复杂度是（ B ）。 A．O(1)

B．O(n) D．O(n2)

C．O(nlogn)

7、设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪个操作？（D ）。 A．s =rear; rear=rear->link; delete s; B．rear=rear->link; delete rear; C．rear=rear->link->link; delete rear;

1

D．s=rear->link->link;rear->link->link=s->link; delete s;

8、将下图所示的s所指结点加到p所指结点之后，其语句为（ C）。

next p next

A．s->next=p+1；p->next=s；

B．(*p).next=s；(*s).next=(*p).next；

s C．s->next=p->next；p->next=s； D．s->next=p->next；p->next=s->next； 9、队列和栈的主要区别是（ D）。 A．逻辑结构不同

B．存储结构不同

D．限定插入和删除操作的位置不同

C．所包含的运算个数不同

10、已知广义表的表头为a，表尾为（b，c），则此广义表为（ B ）。 A．（a，（b，c）） C．（（a），b，c）

B．（a，b，c） D．（（a，b，c））

11、对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（ C ）。 A．(n-1)/2 C．(n+1)/2

B．n/2 D．n

12、如图所示的4棵树中，是满二叉树的为 （A ）。

(A) (B) (C) (D)

13、一个二叉树按顺序方式存储在一个维数组中，如图

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（ C ）层。 A．1 C．3

B、2

D．4

2

14、n个顶点的强连通图中至少含有（ B ）。 A．n-l条有向边

B．n条有向边 D．n(n-1)条有向边

C．n(n-1)／2条有向边

15、对有n个结点的顺序表进行快速排序，在最坏情况下其关键码比较次数为（D ）。 A．O(n)

B．O(log2n) D．O(n2)

C．O(nlog2n)

16、在下面各种链表结构中，能在O(1) 时间内完成在指定结点之前插入元素 X的结构是（ D ）。 A．单链表

B．单向循环链表

C．带表头结点的单链表 D．双向循环链表

17、若让元素1,2,3依次进栈，则出栈次序不可能出现（ A ）。 A．3，1，2 C．3，2，1

B．2，1，3 D．1，3，2

18、如图所示的4棵树中，不是完全二叉树的为 （ C ）。

A． B． C． D．

19、设只包含根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为（ B ）。 A．2k C．2k+1

B．2k+1-1

D．2k-1+1

20、某棵二叉树按顺序方式存储在一维数组中，如下图

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D E F G H I J 则结点E在二叉树的第（C ）层。

A．1 C．3

B．2

D．4

21、含有n个结点的二叉链表中，空链域个数为（ B ）。 A．n C．2n

B．n+1 D．n

2

22、广义表A（a），则表尾为（ C）。 A．a C．空表

B．(()) D．（a）

23、向一个有127个元素的顺序表中插入一个新元素并保持元素原来的先后关系不变，在等

3

概率情况下平均要移动（ B ）个元素。 A、8

B、63.5

D、7

C、63

24、设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪个操作？（ B ） A．s->link=p->link;p->link=s; B．q->link= s ->link; q->link= s; C．p->link=s->link;s->link=p; D．p->link=s; s->link=q;

25、设单向循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单向循环链表的尾结点的指针。若想删除该链表的第一个结点，则应执行下列哪一个操作？（ D ）

A．s=rear; rear=rear->link; free(s); B．rear=rear->link; free(rear);

C．rear=rear->link ->link; free(rear);

D．s=rear->link->link; rear->link->link=s->link; free(s); 26、根据二叉树的定义，二叉树有（ B ）种形态。

A. 6 B. 5 C. 4 D. 3

27、一棵有100个结点的完全二叉树从根这一层开始，每一层中从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左子女编号为（ A ）。 A. 98 C. 50

B. 99 D. 48

28、如图所示的4棵树中，不是完全二叉树的为（ C ）。

A． B． C． D．

29、广义表A（a），则表尾为（ C ）。 A．a C．空表

B．(())

D．（a）

30、从顺序表{2，5，7，10，14，15，18，23，35，41，52}中用折半搜索法搜索出元素18需要做（ A ）次比较。 A．3 C．5

B．4

D．7

31、n 个顶点的连通图至少有（A）条弧。 A．n-1

B．n

4