数据结构考题与答案

常见的算法习题,填空题,基础知识汇总

二、填空题：

1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和___运算___________。

2、数据结构算法中，通常用时间复杂度和____空间复杂度______________两种方法衡量其效率。

3、一个算法一该具有__有穷性____,__确定性____,__可行性__,___输入___和_输出___这五种特性。

4、若频繁地对线性表进行插入与删除操作，该线性表应采用_链式___________存储结构。

5、在非空线性表中除第一个元素外，集合中每个数据元素只有一个_直接前驱______；除最后一个元素之外，集合中每个数据元素均只有一个___直接_后继_____。

6、线性表中的每个结点最多有__一个_直接___前驱和______一个直接___后继。

7、____循环__链表从任何一个结点出发，都能访问到所有结点。

8、链式存储结构中的结点包含__指针__________域，________数据_______域。

9、在双向链表中，每个结点含有两个指针域，一个指向___前驱__结点，另一个指向__后继______结点。

10、某带头结点的单链表的头指针head，判定该单链表非空的条件__head->nex

思凯学习俱乐部

第九章 集合

一、 选择题

1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。【北京航空航天大学 2000 一、8 （2分）】

A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) 【南京理工大学1998一、7（2分）】 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3．顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（（1））,二分法查找只适用于查找顺序存储的有序表，平均比较次数为（（2））。 在此假定N为线性表中结点数，且每次查找都是成功的。【长沙铁道学院 1997 四、3 (4分)】

A.N+1 B.2log2N C.logN D.N/2 E.Nlog2N F.N2

4. 下面关于二分查找的叙述正确的是 ( ) 【南京理工大学

2.3 课后习题解答 2.3.2 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√）

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×）

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√）

7．线性表的链式存储结构优于顺序存储结构。（×）

8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√）

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×）

11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）

12．线性表的特点是每个元素都有一个前驱和一个后继。（×）

2.3.3 算法设计题

1．设线性表存放在向量A[arrsize]的前

1. Fill the blank with correct C++ codes:

(1) Given an array storing integers ordered by distinct value without duplicate, modify the binary

search routines to return the position of the integer with the smallest value greater than K when K itself does not appear in the array. Return ERROR if the greatest value in the array is less than K: (12 scores)

// Return position of smallest element >= K int newbinary(int array[], int n, int K) { int l = -1;

int r = n; // l and r beyond array bounds while (l+1 !=

A 装箱问题模拟（20）

源码：

#include #include using namespace std;

char box[1010];

int main() {

memset(box,100,sizeof(box)); int N; int t;

int num=0; cin>>N;

int temp = N; while(temp--) {

cin>>t;

for (int i=0;i

int a = box[i]; if (a>=t) {

if (a==100) num++;

box[i] -=t;

cout<

cout<

//system(\ return 0; }

B 表达式转换（25）

源码：

#include #include #include using namespace std;

stack sta;

int main() {

string s;

string anwser; cin>>s;

int i;

bool n

西安科技大学

2013年硕士研究生入学考试试题答案A

─────────────────────────────────

科目编号：824 科目名称：数据结构与算法设计

答案A： 一、 二、

单选题（2×15=30分） BDDAC BBCDC ABABC 填空题（2×10=20分）

（1） 运算/操作 （2） 4 （3） 90 （4） h （5） 2m-1 （6）top=p （7）队尾 （8）5 （9）n-1 （10）直接插入排序

三、

简答题（任选5道题，每小题8分，共40分）（只要答出要点即可） 顺序表：空间利用率高，插入、删除运算效率低；

链表：插入、删除运算效率高，不必事先估计“容量”， 空间利用率低。 （2）“假溢出”现象是

处理方式有 判断队满和队空

（3）二叉树的顺序存储方式是一维数组存储二叉树，且能反映各节点之间的逻辑关系； 优点是可方便实现二叉树的基本操作，缺点是，除非是完全二叉树，否则空间浪费很大。

（4）邻接矩阵：

邻接表、逆邻接表：不方便判断某两个顶点是否有边； 两种方式各有利弊。 （5）顺序查找，（n+1）/2;

一、单项选择题

2

1某算法的时间复杂度是O(n)，表明该算法（ ）。

22

A 问题规模是n B 问题规模与n成正比

2 2

C 执行时间等于n D 执行时间与n成正比 2、关于数据结构的描述，不正确的是（ ）。 A 数据结构相同，对应的存储结构也相同。

B 数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C 数据结构操作的实现与存储结构有关。 D 定义逻辑结构时可不考虑存储结构。

3、按排序策略分来，起泡排序属于（ ）。

A 插入排序 B 选择排序 C 交换排序 D 归并排序 4、利用双向链表作线性表的存储结构的优点是（ ）。

A 便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C 节省空间 D 便于销毁结构释放空间

5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（ ）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、Dijkstra算法是按（ ）方法求出图中从某顶点到其余顶点最短路径的。 A 按长度递减的顺序求出图的某顶点到其余顶点的最短路径

B 按长度递增

第1章 绪论

习题

1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。

2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现？ 5．选择题

（1）在数据结构中，从逻辑上可以把数据结构分成（ ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构

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

（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（ ）。 A．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致 C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等 （4）以下说法正确的是（ ）。 A．数据元素是数据的最小单位 B．数据项是数据的基本单位

C．数据结构是带有结构的各数据项的集合

D．一些表面上很

数据结构

2.3 课后习题解答

2.3.2 判断题

1．线性表的逻辑顺序与存储顺序总是一致的。（×） 2．顺序存储的线性表可以按序号随机存取。（√）

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。（×）

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。（√）

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（×）

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。（√） 7．线性表的链式存储结构优于顺序存储结构。（×）

8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。（√）

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。（√） 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。（×）

11．静态链表既有顺序存储的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×）

12．线性表的特点是每个元素都有一个前驱和一个后继。（×）

2.3.3 算

数据结构上机答案

1.1顺序线性表的基本操作 #include #include #define OK 1 #define ERROR 0

#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 #define ElemType int

typedef struct { int *elem,length,listsize; }SqList;

int InitList_Sq(SqList &L) { L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)); L.length=0; L.listsize=LIST_INIT_SIZE; return OK; }

int Load_Sq(SqList &L) { int i; if(L.length==0) printf(\ else { printf(\ for(i=0;i

int ListInsert_Sq(SqList &L,int i,int e) { if(i<1||i>L.length+1) return ERROR; ElemType *newbase,