云南专升本数据结构真题答案及解析

第2部分 习题解析

第1章 绪论

1.1 选择题

1. 算法的时间复杂度取决于（ C ）

A）问题的规模 B） 待处理数据的初态 C） A和B

【答案】C

2.计算机算法指的是解决问题的步骤序列，它必须具备（B ） 这三个特性。

A）可执行性、可移植性、可扩充性 B） 可执行性、确定性、有穷性

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

【答案】B

5．从逻辑上可以把数据结构分为（ C ）两大类。

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

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

【答案】C

6．在下面的程序段中，对x的赋值的语句频度为（ C ）

for(i=0;i<n;i++)

for(j=0;j<n;j++) x=x+1;

A） O(2n) B）O(n) C．O(n2) D．O(log2n)

【答案】C

7．下面的程序段中， n为正整数，则最后一行的语句频度在最坏情况下是（D ）

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if (A[j]>A[j+1])

A[j]与A[j+1]对换；

A. O（n） B） O(nlog2n) C） O(

第2部分 习题解析

第1章 绪论

1.1 选择题

1. 算法的时间复杂度取决于（ C ）

A）问题的规模 B） 待处理数据的初态 C） A和B

【答案】C

2.计算机算法指的是解决问题的步骤序列，它必须具备（B ） 这三个特性。

A）可执行性、可移植性、可扩充性 B） 可执行性、确定性、有穷性

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

【答案】B

5．从逻辑上可以把数据结构分为（ C ）两大类。

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

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

【答案】C

6．在下面的程序段中，对x的赋值的语句频度为（ C ）

for(i=0;i<n;i++)

for(j=0;j<n;j++) x=x+1;

A） O(2n) B）O(n) C．O(n2) D．O(log2n)

【答案】C

7．下面的程序段中， n为正整数，则最后一行的语句频度在最坏情况下是（D ）

for(i=n-1;i>=1;i--)

for(j=1;j<=i;j++)

if (A[j]>A[j+1])

A[j]与A[j+1]对换；

A. O（n） B） O(nlog2n) C） O(

专升本数据结构试题(一)

专业 班级 姓名 学号

一、

填空题(每空2分，共32分)

1．数据结构研究数据的___________、存储结构及数据的运算与实现。

2．在双向循环链表中，在P所指结点之后插入指针f所指结点，其操作为_________________；f->next=P->next；________________________；P->next=f 。

3．在一个长度为n的顺序表中向第i个元素（0＜i≤n+1＝之前插入一个新元素时，需向后移动_______个元素。

4．在等概率情况下，在顺序表中删除一个元素的平均移动次数为___________。 5．栈的特点是__________，栈和队列都是操作受限的线性表。

6．循环队列中队列最大长度为m，front和rear分别为头尾指针，则队列满的条件为__________ ____________________。

7．将中缀表达式A＋（B－C/D）＊E变为后缀表达式为_________________________。 8．空串指_________________________。

9．串A=“date”

专升本数据结构试题(二)

专业 班级 姓名 学号

一、

填空题(每空2分，共32分)

1．_______________是数据的不可分割的最小单位。 2． X=9；Y=100； WHILE(Y>0) IF(X>100) {X=X-10；Y- -} ELSE X++；

该程序的时间复杂度为________________。

3．队列的特点是__________，栈和队列都是操作受限的线性表。

4．两栈共享空间时，设向量S的空间长度为m，top1和top2分别是两栈的栈顶指针，则栈2为空的条件为______________________，两栈满的条件是_____________________ 5．储稀疏矩阵的方法有___________ 和十字链表法。

6．对于二维数组Amⅹn，若按行优先原则存储，设每一个元素占c个存储单元，则Loc(aij)＝Loc(a00)+________________________。

7．Head(tail(((a , b) , (c , d))))

这是我自己整理的福建省专升本数据结构历年真题的详细答案,希望对学弟学妹们有所帮助,那些去补习的都是没什么用的!

06年转升本数据结构考题

一、 单项选择题（共12 小题，每小题2分,共24分） 1、已知单链表结构为 struct node{ int data;

struct node *next; }*p,*q,*r ;

删除单链表中结点p(由p指向的结点)后面的结点的操作不正确的是__C__ A、

q=p->next; p->next=q->next;

B、p->next=p->next->next;

C、r=p->next; p->next=q->next;

D、

q=p->next; r=q->next; p->next=r;

2、若待排序对象序列在排序前已经按照关键字递增排列，则采用__A__比较次数最少。

A、直接插入排序 O(n) B、快速排序 O(n2) C、合并排序

D、简单选择排序 O(n2)

3、图的深度优先遍历类似于树的__C__ A、后序遍历 B、层次遍历 C、前序遍历 D、中序遍历

4、求赋权有向图的最短路径常用的算法有___D___

这是我自己整理的福建省专升本

专升本《数据结构》

一、 （共75题,共150分）

1. 数据的逻辑结构是由（）部分组成的。 （2分） A.2 B.3 C.4 D.5

标准答案：A

2. 算法是对某一类问题求解步骤的有限序列，并具有（）个特性。 （2分） A.3 B.4 C.5 D.6

标准答案：C

3. 队列的入队操作是在（）进行的。 （2分） A.队头 B.队尾 C.任意位置 D.指定位置

标准答案：B

4. 队列的出队操作是在（）进行的。 （2分） A.队头 B.队尾 C.任意位置 D.指定位置

标准答案：A

5. 数组通常采用顺序存储的优点是（）。 （2分） A.便于增加存储空间 B.便于依据下标进行随机存取 C.避免数据元素的移动 D.防止下标溢出

标准答案：B

6. 下列给

06数据结构（50分）

一、单选题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填写在题干后面的括号内。每小题1分，共10分）

1.数据的基本单位是（ ）

A.数据项 B.数据类型 C.数据对象 D.数据元素

2.若频繁的对线性表进行插入和删除操作，则该线性表应该采用_______存储结构。（ ） A.顺序 B.链式 C.散列 D.任意

3.若进栈序列为3，5，7，9，进栈过程中可以出栈，则不可能的出栈次序是（ ） A.7，5，3，9 B.9，7，5，3 C.7，5，9，3 D.9，5，7，3 4.下面的说法中，正确的是（ ）

A.字符串的长度指串中包含的字母的个数 B.字符串的长度指串中包含的不同字符的个数 C.一个字符串不能说是其自身的一个子串 D.若T包含在S中，则T一定是S的一个子串 5.广义表（（a，b），（c，d））的表尾是（ ）

A.d B.c，d C.（c，d）

第一章 绪论

一、选择题

1、( )是数据的基本单位。

A) 数据结构 B)数据元素 C)数据项 D)数据类型 2、以下说法不正确的是( )。

Ａ)数据结构就是数据之间的逻辑结构。

Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。 Ｃ)数据项是组成数据元素的最小标识单位。 Ｄ)数据的抽象运算不依赖具体的存储结构。

3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（ ）等5个特性。 A)可执行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 4、一般而言，最适合描述算法的语言是( )。

A)自然语言 B)计算机程序语言 C)介于自然语言和程序设计语言之间的伪语言 D)数学公式 5、通常所说的时间复杂度指( )。

A)语句的频度 B)算法的时间消耗 C)渐近时间复杂度 D)最坏时间复杂度

6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明( )

第一章 绪论

一、选择题

1、( )是数据的基本单位。

A) 数据结构 B)数据元素 C)数据项 D)数据类型 2、以下说法不正确的是( )。

Ａ)数据结构就是数据之间的逻辑结构。

Ｂ)数据类型可看成是程序设计语言中已实现的数据结构。 Ｃ)数据项是组成数据元素的最小标识单位。 Ｄ)数据的抽象运算不依赖具体的存储结构。

3、计算机算法是解决问题的有限运算序列,它具备输入、输出和（ ）等5个特性。 A)可执行性、可移植性和可扩充性 B)可行性、确定性和有穷性 C)确定性、有穷性和稳定性 D)易读性、稳定性和安全性 4、一般而言，最适合描述算法的语言是( )。

A)自然语言 B)计算机程序语言 C)介于自然语言和程序设计语言之间的伪语言 D)数学公式 5、通常所说的时间复杂度指( )。

A)语句的频度 B)算法的时间消耗 C)渐近时间复杂度 D)最坏时间复杂度

6、A算法的时间复杂度为O(n3)，B算法的时间复杂度为O(2n)，则说明( )

北京师范大学08年考研程序设计与数据结构试题

考研_考试大 [ 2008/11/17 ] 来源：北京师范大学

一、简答题（20分）

1.数据类型和抽象数据类型的含义 2.算法的特性与算法的时间复杂度

3.快速排序方法最好和最坏的情况是什么？简要分析说明 4.栈、队列的共同点与不同点，说明其属于线形表的原因 二、方法选择（20分）

1.一棵二叉排序树中各结点不相同，欲得到一个由大到小的结点值递减序列，你认为采用什么方法能得到要求的结果？

2.设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序，基数排序，快速排序，堆排序，插入排序），那种方法最好，为什么？

三、（40分，每题8分）

1.已知一个循环单链表la，av是可利用栈的头指针，请用３个赋值语句，完成将整个循环链表释放的功能。（即将表整个归还到可用的栈空间） 2.给出求N阶hanoi塔的函数定义如下：Hanoi （ int n，char x，char y ，char z ）

{ if （ n= =1） move （ x ，1，z） Else{ hanoi（ n-1， x，z，