2017年4月高等教育自学考试全国统一命题考试

数据结构导论

试卷及解析

(课程代码 02142)

一、单项选择题(本大题共15小题，每小题2分，共30分。在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。)

第1题 任意两个结点之间都没有邻接关系，组织形式松散，这种组织形式称为（ ）

A.集合

B.线性结构

C.树形结构

D.图结构

【正确答案】 A

【答案解析】(P25) 在四类基本的逻辑结构中，集合中任意两个结点之间都没有邻接关系，组织形式松散。线性结构中结点按逻辑关系依次排列形成一条“链”，结点之间一个一个依次相邻接。树形结构具有分支、层次特性，其形态像自然界中的树，上层的结点可以和下层多个结点相邻接，但下层结点只能和上层的一个结点相邻接。图结构最复杂，其中任何两个结点都可以相邻接。

第2题 表示数据元素之间的关联方式通常采用的存储方式是（ ）

A.顺序存储方式和索引存储方式

B.链式存储方式和散列存储方式

C.顺序存储方式和链式存储方式

D.链式存储方式和索引存储方式

【正确答案】 C

【答案解析】(P26) 表示数据元素之间的关联方式主要有顺序存储方式和链式存储方式。顺序存储方式是指所有存储结点存放在一个连续的存储区里。链式存储方式是指每个存储结点除了含有一个数据元素外，还包含指针，每个指针指向一个与本结点有逻辑关系的结点，用指针表示数据元素之间的逻辑关系。

第3题 下面几种算法时间复杂度阶数中，最小的是（ ）

A.O(log2n)

B.O(n)

C.O(n2)

D.O(2n)

【正确答案】 A

【答案解析】(P28~30) 在本题中，O(log2n)的时间复杂度最小，O(2n)的时间复杂度最大。

第4题 双向循环链表中，在指针p所指结点的后面插入一个新结点*t，正确的语句为（ ）

A.t->prior=p；

  t->next=p->next；

  p->next->prior=t；

  p->next=t；

B.t->prior=p；

  t->next=p->next；

  p->next=t；

C.t->prior=p；

  p->next->prior=t；

  t->next=p->next；

  p->next=t;

D.p->next->prior=t；

  p->next=t;

【正确答案】 A

【答案解析】(P53)

第5题 栈的修改原则是（ ）

A.先进先出

B.后进先出

C.栈空则进

D.栈满则出

【正确答案】 B

【答案解析】(P60) 栈又称为后进先出线性表，其修改原则是后进先出（Last In First Out）。

第6题 设有一顺序队列SQ，已知尾指针rear<队列的最大长度-1，则数据x进行入队列操作的语句为（ ）

A.SQ.front=SQ.front+1;

B.SQ.front=SQ.rear+1；

C.SQ.front=SQ.front+1；SQ.data［SQ.front］=x;

D.SQ.rear=SQ.rear+1；SQ.data［SQ.rear］=x；

【正确答案】 D

【答案解析】(P71)