专升本数据结构考什么

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

专业 班级 姓名 学号

一、

填空题(每空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))))

第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(

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

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. 下列给

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

作业题（一）

一、单项选择题

1. 从逻辑上可以把数据结构分为（ ）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 2. 链表不具有的特点是（ ）

A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 3.下面程序段的时间复杂度的量级为（ ）。 For(i=1;i<=n;i++) For(j=1;j<=I;j++) For(k=1;k<=j;k++) X=x+1;

A．O(1) B．O(n) C．O(n2) D．O(n3)

4.在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（ ）个指针域的值。

A．2 B．3 C．4 D．6

5、一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（ ）。

A．98

一．关系代数运算

1.选择 σ

（1）查询年龄小于20岁的学生 σsage<20(student)

（2）查询学号为201215122的学生 σsno=201215122(student) 2.投影

（1）查询学生姓名，和所在系 same,sdept(student)

（2）查询选修了2号课程的学生学号

sno（σcno=‘2’2(student)）

SQL语句

学生-课程数据库

学生表：学生（学号，姓名，性别，年龄，所在系） 课程表：课程（课程号，课程名，先行课，学分） 学生选课表：选课（学号，课程号，成绩）

二．创建数据库SQL

1. 创建数据库

Create database 数据库名 On

( name =逻辑文件名，

Filename=’物理文件名’， Size=初始文件大小， Maxsize=最大文件大小， Filegrowth=文件自动增量 ) Log on

( name =逻辑文件名，

Filename=‘物理文件名’， Size=初始文件大小， Maxsize=最大文件大小， Filegrowth=文件自动增量 )

例 创建‘教务管理数据库’

Create databas

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

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

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集