数据结构2004年解析

第1-3章习题

一、选择题

1.若进栈序列为a，b，c，d，进栈过程中可以出栈，则 不可能是一个出栈序列。 A) a,d,c,b

B) b,c,d,a C) c,a,d,b D) c,d,b,a

6.设用一维数组A[1,…,n]来存储一个栈，令A[n]为栈底，用整型变量T指示当前栈顶位置，A[T]为栈顶元素。当从栈中弹出一个元素时，变量T将变化为 。 A) T=T + 1 B) T=T – 1 C) T不变 D) T= n 7. 一个栈的入栈序列为a，b，c，d，e,则栈不可能的出栈序列是 。 A) e d c b a B) d e c b a C) d c e a b D) a b c d e 8.若语句S的执行时间为O(1),那么下列程序段的时间复杂度为 。

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

For(j = 0; j <=n ;j++) s

A) O(n) B) O(n*n) C) O(n*log2n) D) O(n*i) 18

更多优质免费自考资料尽在豆瓣小组-自考乐园俱乐部

（http://www.douban.com/group/zikao/）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........

全国2004年10月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题(本大题共15小题，每小题2分，共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题干的括号内。错选、多选或未选均无分。

1．下列各式中，按增长率由小至大的顺序正确排列的是( ) A．n，n！，2，n C．2n，log n，nlogn，n3/2

n

3/2

B．n，2，n

3/2nlogn

，2

100

D．2100，logn, 2n, nn

2．若要在单链表中的结点*p之后插入一个结点*s，则应执行的语句是( ) A．s->next=p->next; p->next=s; C．p->next=s->next; s->next=p;

B．p->next=s; s->next=p->next; D．s->next=p; p->next=s->next;

3．若要在O（1）的时间复杂度上实现两个循环链表头尾相接，则应对两

www.pass60.com祝考生Pass60

超越60自考网

全国2004年1月高等教育自学考试

数据结构试题

课程代码：02331

一、单项选择题（本大题共15小题，每小题2分，共30分）

在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1．在数据结构中，数据的逻辑结构可以分成（ ） A．内部结构和外部结构

B．线性结构和非线性结构 D．动态结构和静态结构 B．数据元素在表中的序号表示 D．数据元素的值表示

C．紧凑结构和非紧揍结构 A．数据元素的相邻地址表示 C．指向后继元素的指针表示

2．在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用（ ）

3．设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是（ ） s -> next = p -> next; p -> next = s;

t = p -> data; p -> data = s -> data; s ->data = t; A．结点*p与结点*s的数据域互换 B．在p所指结点的元素之前插入元素 C．在p所指结点的元素之后插入元素

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

数据结构

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依次进入初

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

院、系领导 审批并签名

A / B卷 广州大学 2009-2010 学年第 二 学期考试卷

课程 数据结构 考试形式（开卷/闭卷，考试/考查）学院

系 专业 班级 学号 姓名_ 题次 分数 评分 一 10 二 20 三 10 四 30 五 30 六 七 八 九 十 总分 评卷人 100 一、单项选择题（10分，每小题1分）

1、 输出一个二维数组b[m][n]中所有元素值的时间复杂度为（ ）。

A. O(n) B. O(m+n) C. O(n2) D. O(m*n)

2、在一个长度为n的顺序表中删除一个值为x的元素时，需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2

B. n/2

C. n

D. n+1

3、 设双向循环链表中结点的结构为（data, lLink, rLink），且不带表头结点。若想在指针p

所指结点之后插入指针s所指结点，则应执行下列哪一个操作？

A. p->rLink = s; s->lLink = p

第0章 数据结构导论

0.1 数据结构学习指导

0.1.1 课程地位

《数据结构》是计算机科学与技术专业本科生的专业基础课程之一。用计算机解决任何实际问题都离不开数据表示和数据处理，而数据表示和处理的核心问题之一是数据结构及其实现——这正是数据结构课程的基本内容。从这个意义上来说，数据结构课程在知识学习和技能培养两个方面都处于关键性地位，是理论和实践要求都相当高的课程。本课程不仅为操作系统、数据库系统、编译方法、计算机网络等后续课程提供了必要的知识基础，而且也为计算机及其专业人员提供了必要的技能训练。 在对清华大学计算机系历届毕业生和部分研究生追踪调查显示，几乎所有的同学都认为《数据结构》是他们在学校里学过的最有用的课程之一，也是国内外许多软件开发机构要求考核的基本课程之一。由此可见《数据结构》这门课程的重要性。

0.1.2 课程要求

根据课程的教学大纲要求，《数据结构》主要讨论在软件开发中如何进行数据结构和算法的设计。因此，用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程的重点，也是学生需要掌握的重点。面向对象方法以及结构化技术都是建立高质量软件的技术，通过《数据结构》课程的学习和实践，可以加深对这些先进软件开发方法

第10章 索引与散列

一、复习要点

索引结构和散列结构是用于外部搜索的搜索结构。数据在外存的组织即文件结构，主要分顺序、直接存取（散列）和索引文件。在这些文件组织中使用的主要是索引和散列方法。

1、基本知识点

要求掌握静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。掌握动态索引结构，包括B树的搜索、插入、删除，通过关键码个数估算B树的高度的方法；B+树的搜索、插入与删除。掌握散列法，包括散列函数的构造、处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。

二、难点与重点

1、线性索引

? 密集索引、稀疏索引、索引表计算

? 基于属性查找建立倒排索引、单元式倒排表 2、动态搜索树

? 平衡的m路搜索树的定义、搜索算法

? B树的定义、B树与平衡的m路搜索树的关系

? B树的插入(包括结点分裂)、删除(包括结点调整与合并)方法 ? B树中结点个数与高度的关系

? B+树的定义、搜索、插入与删除的方法 3、散列表

? 散列函数的比较

? 装载因子 ? 与平均搜索长度的关系，平均搜索长度的关系 ? 表长m、表中已有数据对象个数n和装载因子的关系

? 解决冲突的(闭散列)线性探查法的运用，平均探查次数的计算

? 线性探查

第0章 数据结构导论

0.1 数据结构学习指导

0.1.1 课程地位

《数据结构》是计算机科学与技术专业本科生的专业基础课程之一。用计算机解决任何实际问题都离不开数据表示和数据处理，而数据表示和处理的核心问题之一是数据结构及其实现——这正是数据结构课程的基本内容。从这个意义上来说，数据结构课程在知识学习和技能培养两个方面都处于关键性地位，是理论和实践要求都相当高的课程。本课程不仅为操作系统、数据库系统、编译方法、计算机网络等后续课程提供了必要的知识基础，而且也为计算机及其专业人员提供了必要的技能训练。 在对清华大学计算机系历届毕业生和部分研究生追踪调查显示，几乎所有的同学都认为《数据结构》是他们在学校里学过的最有用的课程之一，也是国内外许多软件开发机构要求考核的基本课程之一。由此可见《数据结构》这门课程的重要性。

0.1.2 课程要求

根据课程的教学大纲要求，《数据结构》主要讨论在软件开发中如何进行数据结构和算法的设计。因此，用抽象数据类型以及面向对象的方法组织、存储各种类型的数据是本课程的重点，也是学生需要掌握的重点。面向对象方法以及结构化技术都是建立高质量软件的技术，通过《数据结构》课程的学习和实践，可以加深对这些先进软件开发方法