数据结构应用题题库

数据结构应用题答案

第2章 线性表

1.设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。 答：操作序列如下：q->rlink = p->rlink ; p->rlink = q ; q->rlink->llink = q ; q->llink = p ; 注意答案不唯一

第3章 栈和队列

1.设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序。 答：共计14种，分别是：1234， 1243， 1324， 1342， 1432， 2134， 2143， 2341， 2314， 2431， 3214， 3241， 3421， 4321

2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。 答：（1）不能得到4，3，5，6，1，2 ；因为1，2，3，4入栈后；4，3出栈；得到序列4，3；栈中还有1，2；5入栈后即出栈，得到序列4，3，5；6入栈后即出栈，

计算机——《数据结构》

第1页 共13页

1．简述栈的基本操作

2．给定权值组W={1，3，78，14，20，28}，建立哈夫曼树。 3．试求下面的网络的最小生成树

10 1?C10

69 ?B15?E5 613 6?A?D

84.对一组关键字49，7，50，5，94，16，90，29，71，使用希尔排序，写出对d1?3时的一趟排序的结果。 1-4题答案：

1、栈的基本操作有：

栈的建立，判栈满，判栈空，压栈，退栈和取栈顶元素等。 2、

144

66

7838

28 1820 414

3 13、 41 96 536 625 84、

4950594169029717

1649295090947175

5．写出队列的基本操作。

a 6．对下面的二叉树

（１） 其中序遍历序列为

b

c （２）其后序遍历序列为 d e

5

g

h 7．给定一组关键字序列12，7，51，32，23，试构造一棵查找树。

8．对一组关键字49，7，50，5，94，16，90，29，71，使用快速排序，试给出第一次划分过程。

5-8题答案：

5．队列的基本操作有：

队列的建立，判队空，

第一章绪论（含算法的定义和度量）

1.从逻辑上可以把数据结构分为（C）。

A.动态结构、静态结构B.顺序结构、链式结构

C.线性结构、非线性结构D、初等结构、构造型结构

2.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单向循环

3. 衡量查找算法效率的主要标准是（B）。

A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易难度

4.程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A ）。 A O(n) B O(nlog2n) C O(n2) D O(n3/2) 5.下述哪一条是顺序存储方式的优点？（A ）

A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快

6.下列关于数据结构的叙述中，正确的是( D ). A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构

D.用一维数组存储一棵完全二叉树是有效的存储方法

7.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 8.

第一章绪论（含算法的定义和度量）

1.从逻辑上可以把数据结构分为（C）。

A.动态结构、静态结构B.顺序结构、链式结构

C.线性结构、非线性结构D、初等结构、构造型结构

2.若某线性表的常用操作是取第i个元素及其前趋元素，则采用( A )存储方式最节省时间 A.顺序表 B.单链表 C.双链表 D.单向循环

3. 衡量查找算法效率的主要标准是（B）。

A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易难度

4.程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A ）。 A O(n) B O(nlog2n) C O(n2) D O(n3/2) 5.下述哪一条是顺序存储方式的优点？（A ）

A．存储密度大 B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快

6.下列关于数据结构的叙述中，正确的是( D ). A.数组是不同类型值的集合

B.递归算法的程序结构比迭代算法的程序结构更为精炼 C.树是一种线性结构

D.用一维数组存储一棵完全二叉树是有效的存储方法

7.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 8.

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）

A．问题的规模 B. 待处理数据的初态 C. A和B 3. 计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性

4. 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述

C．数据结构+程序 D．以上都不对. 5. 下面关于算法说法错误的是（ ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ ）

(1）算法原地工作的

第1章 绪论

一、选择题

1. 算法的计算量的大小称为计算的（ ）。

A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（ ）

A．问题的规模 B. 待处理数据的初态 C. A和B 3. 计算机算法指的是（1），它必须具备（2） 这三个特性。

(1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法

(2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性

C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性

4. 一个算法应该是（ ）。

A．程序 B．问题求解步骤的描述

C．数据结构+程序 D．以上都不对. 5. 下面关于算法说法错误的是（ ）

A．算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（ ）

(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++;} //共同

数据结构试题库

一、 单项选择题

1．下列程序段所代表的算法的时间复杂度为（ D ）。

x=n; y=0;

while (x>=(y+1)*(y+1)) y++;

(A)O(n) (B)O(n2) (C)O(log2n) (D)O(n)

2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除

元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（ B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2

3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为

（ C ）。

(A)HS->next=s; (B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s; (D)s->next=HS;HS=HS>next;

4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设

队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（ A ）。

void AddQueue(struct link

1 绪论

沈阳理工大学应用技术学院

信息与控制学院 计算机科学与技术教研室

2011-5-8

- 1 -

数据结构复习题：绪论 单选题

1、在数据结构中，与所使用的计算机无关的数据叫____结构。 A存储|B物理|C逻辑|D物理和存储

2、在数据结构中，从逻辑上可以把数据结构分成______。

A动态结构和静态结构|B紧凑结构和非紧凑结构|C线性结构和非线性结构|D内部结构和外部结构图 3、数据结构在计算机内存中的表示是指_______。

数据的存储结构|数据结构|数据的逻辑结构|数据元素之间的关系 4、在数据结构中，与所使用的计算机无关的是数据的______结构。 逻辑|存储|逻辑和存储|物理

5、在以下的叙述中，正确的是_____。

线性表的线性存储结构优于链表存储结构|二维数组是其数据元素为线性表的线性表|栈的操作方式是先进先出|队列的操作方式是先进后出

6、在决定选取何种存储结构时，一般不考虑_______。

各结点的值如何|结束个数的多少|对数据有哪些运算|所用编程语言实现这种结构是否方便 7、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_______。 数据的处理方法|数据元素的类型|数据元素之间的关系|数据的存储方

数据结构试题库

一、 单项选择题

1．下列程序段所代表的算法的时间复杂度为（ D ）。

x=n; y=0;

while (x>=(y+1)*(y+1)) y++;

(A)O(n) (B)O(n2) (C)O(log2n) (D)O(n)

2．在一个长度为n的以顺序结构存储的线性表中，假设在线性表的任何位置删除

元素的概率相等，则删除一个元素时线性表所需移动元素的平均次数为（ B ）。 (A) n2 (B)(n-1)/2 (C)(n+1)/2 (D)n/2

3．在一个栈顶指针为HS的链栈中插入一个*s结点时，应执行执行操作为

（ C ）。

(A)HS->next=s; (B)s->next=HS->next;HS->next=s; (C)s->next=HS;HS=s; (D)s->next=HS;HS=HS>next;

4．假设以带头结点的循环链表表示队列Q，并且队列只设一个头指针front，不设

队列尾指针。若要进队一个元素*s，则在下列程序算法的空白处应添加的操作语句是（ A ）。

void AddQueue(struct link