数据结构基础知识考察

数据结构基础知识考察

一、填空题（每空1分，共4题，共10分）［填空题］

L数据的物理结构包括的表示和存储和的表示和存储。［填空题］*

空1答案：顺序结构

空2答案：链式结构

2.对于给定的n个元素，可以构造出的逻辑结构有___四

种。［填空题］*

空1答案：集合结构

空2答案：线性结构

空3答案：树形结构

空4答案：图状结构

3.一个算法具有5个特性:_________________有零个或多个输入、有一个或多个

输出。［填空题］*

空1答案：有穷性

空2答案：确定性

空3答案：可行性

4.抽象数据类型被形式地定义为其中D是___的有限集合，S是D上的

有限集合，P是对D的集合。［填空题］*

空1答案：D,S,P

空2答案：数据元素

空3答案：关系

空4答案：基本操作

5.数据结构主要包括数据的数据的和数据的这三个方面的内

容。［填空题］*

空1答案：逻辑结构

空2答案：存储结构

空3答案：操作

6.一个算法的效率可分为___效率和_____效率。［填空题］*

空1答案：时间

空2答案：空间

二、单项选择题（每题1.5分，共20题，共30分）［填空题］

L线性结构是数据元素之间存在一种（）。［单选题］*

A.一对多关系

B.多对多关系

C多对一关系

D.一对一关系，正确答案）

2.数据结构中，与所使用的计算机无关的是数据的（）结构。［单选题］*

A.存储

B.物理

C.逻辑

D.物理和存储

3.算法分析的目的是（）。［单选题］*

A.找出数据结构的合理性

B.分析算法的效率以求改进

C.研究算法中的输入和输出的关系

D.分析算法的易懂性和文档性

4.算法分析的两个主要方面是（）。［单选题］*

A.空间复杂性和时间复杂性

B.正确性和简明性

C,可读性和文档性

D.数据复杂性和程序复杂性

5.计算机算法指的是（）。［单选题］*

A.计算方法

B.排序方法

C.解决问题的有限运算序列

D.调度方法

6.从逻辑上可以把数据结构分为（）o［单选题］*

A,线性结构和非线性结构（正确答案）

B.紧凑结构和非紧凑结构

C.动态结构和静态结构

D.内部结构和外部结构

三、填空题（每空1分，共4题，共10分）［填空题］

1.线性表的两种存储结构分别为和o［填空题］*

空1答案：顺序存储

空2答案：链式存储

2.顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相

邻的元素，其物理位置相邻。［填空题］*

空1答案：必定

空2答案：不一定

3.若经常需要对线性表进行插入和删除操作，则最好采用存储结构，若线性

表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线

性表中的元素，则最好采用存储结构。［填空题］*

空1答案：链式

空2答案：顺序

4在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存

储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指

示。［填空题1*

空1答案：head头指针

空2答案:head.next

空3答案：其直接前驱

四、单项选择题（每题1.5分，共20题，共30分）［填空题］

1.线性表是（）。［单选题］*

A.一个有限序列，可以为空

B.一个有限序列，不能为空

C.一个无限序列，可以为空

D.一个无限序列，不能为空

2.带头结点的单链表L为空的判定条件是（）。［单选题］*

A.head==null

B.head.next==nullE确答案）

C.head.next==L

D.head!=null

3.在表长为n的单链表中，算法时间复杂度为O（n）的操作为（）o［单选题］*

A.删除p结点的直接后继结点

B.在p结点之后插入一^结点

C.删除表中第一个结点

D.查找单链表中第i个结点

4.在表长为n的顺序表中，算法时间复杂度为0(1)的操作为()o［单选题］**

A.在第i个元素前插入一个元素

B.删除第i个元素

C.在表尾插入一个元素

D.查找其值与给定值相等的一个元素

5.设单链表中指针p指向结点ai,若要删除ai结点，则需修改指针的操作为

()o［单选题］*

A.p=p.next

B.p.next=p.next.next〕二确答案)

C.p=p.next.next

D.next=p

五、单项选择题(每题1.5分，共20题，共30分)［填空题］

1.一个栈的入栈序列a,b,c,d,e,则栈的不可能的输出序列是()o［单选题］

*

A.edcba

B.decba

C.dceab(正确答案)

D.abcde

2.若栈采用顺序存储方式存储，现两栈共享空间top［i］代表第i个栈(i

=1,2)栈顶，栈1的底在v［l］,栈2的底在V［m］,则栈满的条件是()。［单选题］

A.top[2]-topfl]|=0

B.top[l]+1nop⑵（正确答案）

C.top[l]+top[2]=m

D.top[l]=top[2]

3.若已知一个栈的入栈序列是1,2,3，…，n,其输出序列为pl,p2,p3,

pn,若pl=n,则pi为（）o[单选题]*

A.i

B.n=i

C.n-i+1（正确答案）

D.不确定

4.栈结构通常采用的两种存储结构是（）。[单选题]*

A.顺序存储结构和链式存储结构

B.散列方式和索引方式

C.链表存储结构和数组

D.线性存储结构和非线性存储结构

5.判定一个栈ST（最多元素为mO）为空的条件是（）。[单选题]*

A.ST.top!=-1

B.ST.top==・l（正确答案）

C.ST.top!=mO-1

D.ST.top==m（）-l

6.判定一个栈ST（最多元素为mO）为栈满的条件是（）o

[单选题]*

A.ST.top!=-1

B.ST.top==-1

C.ST.top!=mO-1

D.ST.top==m0-1（正确答案）

7.栈的特点是（）,队列的特点是（A）。［单选题］*

A.先进先出

B.先进后出（正确答案）

8.一个队列的入列序列是1,2,3,4,则队列的输出序列是（）o［单选题］*

A.4,3,2,1

B.1,2,3,4（正确答案）

C.1,4,3,2

D.3,2,4,1

9.判定一个循环队列QU（最多元素为mO）为空的条件是（）。［单选题］*

A.front==rear

B.front!=rear

C.front==（rear+1）%m（）

D.front!=（rear+1）%m0

10.判定一个循环队列QU（最多元素为mO）为满队列的条件是（）o［单选题］*

A.front==rear

B.front!=rear

C.front==（rear+1）%m（）

D.front!=（rear+1）%m0

11.循环队列用数组A［0,m-l］存放其元素值，已知其头尾指针分别是front和

rear,则当前队列中的元素个数是（）。［单选题］*

A.(rear-front+m)%m

B.rear-front+1

C.rear-front-1

D.rear-front

12.栈和队列的共同点是（）。［单选题］*

A.都是先进后出

B.都是先进先出

C.只允许在端点处插入和删除元素（正确答案）

D.没有共同点

六、填空题（每空1分，共4题，共10分）［填空题］

1.在具有n个单元的循环队列中，队满时共有个元素。［填空题］*

空1答案：n-1

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

的结点数为2个，则度为0的结点数为（）个。［单选题］*

A.4

B.5

正确答案）

D.7

2.假设在一棵二叉树中，双分支结点数为15,单分支结点数为3（）个，则叶子结点

数为（）个。［单选题］*

A.15

B.16珞案）

C.17

D.47

3.假定一棵三叉树的结点数为50,则它的最小高度为（）o［单选题］*

A.3

B.4

C.5（正确答案）

D.6

4.在一棵二叉树上第4层的结点数最多为（）。［单选题］*