2013年408数据结构

一、填空题

1.栈中元素的进出原则是 ，队列中元素的进出原则

是 。

2.设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前

面插入结点X时的操作序列为：

1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t；

3.假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素

占2个存储单元，基地址为10，则LOC[6,6]= 。 4.表达式a*(b+c)-d/e的后缀表达式为 。 5.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则

e=_______。

6.设一棵完全二叉树中有100个结点，则该二叉树的深度为__________；若用

二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。 7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素

个数之和等于顶点i的________。

8.利用逐点插入法建立序列（

数据结构课程设计题目（2013年）

一、必做题

1、图书管理系统（线性表） [问题描述]

设计一个程序，记录并统计图书使用情况。 [基本要求]

（1）图书信息包括图书ID号，图书名，出版社名，出版年月，馆藏册数。 （2）学生信息包括学号，姓名，班级，在借册数，已还册数，违约次数。

（3）借阅信息包括图书ID号，图书名，学号，姓名，借阅日期，应还日期，归还日期。

（4）采用顺序存储线性表表示图书信息。采用链式存储线性表表示学生信息。采用双向循环链表表示借阅信息 。其中一个双向循环链表表示在借的借阅信息，按照图书ID号非递减排序；另一个双向循环链表表示已还的借阅信息，按照图书ID号非递减排序。 （5）图书信息，学生信息、借阅信息采用文件方式输入。

图书信息示例如下，每条信息一行：

16000001 数据结构 清华大学出版社 2012.10 30 学生信息示例如下，每条信息一行： 161340106 张三 1613401 5 10 借阅信息示例如下，每条信息一行：

标志位1（1 表示借阅 2表示归还） 16000001 数据结构 161340106 张三 201

西安科技大学通信学院 数据结构与算法实验指导书

张小红 2013.1

I

目 录

实验一 线性表 ............................................................. 1 (一) 实验目的 ............................................................ 1 (二) 实验内容 ............................................................ 1 (三) 实验报告 ............................................................ 8 实验二 堆栈 ............................................................... 9 (一) 实验目的 ............................................................ 9 (二) 实验内容 ....................................

数据结构

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、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

（二）课程设计内容及安排

1、问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？

2、逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。

3、物理设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精

《数据结构与算法》课程设计大纲

（一）课程设计教学目的及基本要求

1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；

2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；

4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

（二）课程设计内容及安排

1、问题分析和任务定义。根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？

2、逻辑设计。对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图。

3、物理设计。定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精

院、系领导 审批并签名

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

北 京 交 通 大 学 考 试 试 题 （A卷）

课程名称:数据结构与算法 2012-2013学年第一学期 出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 题号 得分 阅卷人 一 二 三 四 五 六 总分 一、 填空题（每空2分，共20分）

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则

后序遍历该二叉树的序列为_____________。

3. 设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，

r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子c的运算

是 。

5. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为

____________。

6. 设二叉树中度数为0的结点数为50

数据结构习题

一、 单选题

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) 集

北 京 交 通 大 学 考 试 试 题 （A卷）

课程名称:数据结构与算法 2012-2013学年第一学期 出题教师:张勇 (请考生注意:（1）本试卷共有六道大题，（2）答案一律写在答题纸上，（3）试卷不得带出考场) 题号 得分 阅卷人 一 二 三 四 五 六 总分 一、 填空题（每空2分，共20分）

1. 数据的物理结构主要包括_____________和______________两种情况。

2. 设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则

后序遍历该二叉树的序列为_____________。

3. 设有向图G的二元组形式表示为G =（D，R），D={1，2，3，4，5}，R={r}，

r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。

4. 已知广义表Ls=(a, (b, c), (d, e)), 运用head和tail函数取出Ls中的原子c的运算

是 。

5. 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为

____________。

6. 设二叉树中度数为0的结点数为50