数据结构及应用算法教程修订版答案

习题一答案

1． 填空题

（1） 数据元素的有限集合，k上关系的有限集合 （2） 顺序存储（连续），链式存储（不连续） （3） 有穷性，确定性，可行性，输入，输出 （4） 时间复杂度，空间复杂度

2．简述下列术语

（1） 数据——是信息的载体，它是描述客观事物的数、字符以及所有能输入到计算

机中被计算机程序识别、加工处理的信息的集合。

（2） 数据元素——是数据的基本单位 ，是对一个客观实体的数据描述。一个数据元

素可以由一个或若干个数据项组成。数据元素也被称为结点或记录。

（3） 数据对象——具有相同性质的数据元素的集合就是一个数据对象，它是数据的

一个子集。 （4） 数据结构——数据结构就是数据之间的相互关系（即数据的组织形式）及在这

些数据上定义的数据运算方法的集合。 （5） 存储结构——数据的存储结构是数据的逻辑结构在计算机内部的表示或实现，

又称为数据的物理结构，它包括数据元素的表示和关系的表示。

（6） 数据类型——是具有相同性质的计算机数据的集合及定义在这个数据集合上的

一组操作的总称。

3.举例说明一下数据结构和算法的关系。

通过公式：程序

一、单项选择题

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．设线性表存放在向量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 !=

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

int i=0,j=L.length-1; int temp;

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同

一.选择题（共15题，每题3分）

（1）下面关于算法说法错误的是_______。 a. 算法最终必须由计算机程序实现

b. 为解决某问题的算法同为该问题编写的程序含义是相同的 c. 算法的可行性是指指令不能有二义性 d. 以上几个都是错误的 （2）下面说法错误的是______.

a. 算法原地工作的含义是指不需要任何额外的辅助空间

b. 在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 c. 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 d. 同一个算法，实现语言的级别越高，执行效率就越低 （3）在下面的程序段中，对x的赋值语句的频度为_____。 for (int i; i

a. 0(2n) b. 0(n) c. 0(n2) d. O(log2n) （4）下面说法正确的是______。 a. 数据元素是数据的最小单位； b. 数据元素是数据的最小单位；

c. 数据的物理结构是指数据在计算机内的实际存储形式 d. 数据结构的抽象操作的定义与具体实现有关 （5）下面说法正确的是_______。

a. 在顺序存储结构中，有时也存储数据结构中元素之间的关系 b. 顺序

第四章 栈和队列

一、选择题

1．对于栈操作数据的原则是（B ）。

A．先进先出 B．后进先出 C．后进后出 D．不分顺序 2．一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。

A．不确定 B．n-i+1 C．i D．n-i 3．有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）

A．5 4 3 6 1 2 B．4 5 3 1 2 6 C．3 4 6 5 2 1 D．2 3 4 1 5 6 4．设栈的输入序列是1，2，3，4,则（ ）不可能是其出栈序列。 A．1，2，4，3， B．2，1，3，4， C．1，4，3，2， D．4，3，1，2， E．3，2，1，4，

5．某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。

A．a，c，b，d B．b, c，d，a C．c, d，b, a D．d, c，a，b 6．设有三个元素X，Y，Z顺序进栈（进的过程中

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;