1.文件可按其记录的类型不同而分成两类，操作系统文件和数据库文件。
2.数据库文件按记录中关键字的多少可分成( 单关键字文件 )和( 多关键字文件 )两种文件。
3.文件由( 记录 )组成，记录由( 数据项 )组成。
4.从用户观点看，文件的逻辑结构通常可以区分为两类：一类是如DBASE中数据库文件那样的文件组织结构，称为( 数据库 )文件；另一种是诸如用各种文字处理软件编辑成的文本文件，称为( 文本 )文件。
从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即( 顺序组织 )、 ( 随机组织)、( 链组织 )。
B+树适用于组织( 随机组织 )的索引结构，
m阶B+树每个结点至多有( m )
除根结点外每个结点至少有( (m/2)向上取整 )个儿子，根结点至少有( 2 )个儿子，有k个儿子的结点必有( k )个关键码。
5.物理记录之间的次序由指针相链表示的顺序文件称为( 串联文件)
6.顺序文件中，要存取第I个记录，必须先存取( 第I-1 )个记录。
7.索引顺序文件既可以顺序存取，也可以( 随机 )存取。
8.建立索引文件的目的的( 提高查找速度 )。
9.索引顺序文件是最常用的文件组织之一，通常用( 树 )结构来组织索引。
10.倒排文件的主在优点在于( 检索记录快)。
11.检索是为了在文件中满足一定条件的记录而设置的操作。检索可以按( 关键字 )检索，也可以按( 记录号 ) 检索；
按(记录号 ) 检索又可以有( 顺序 ) 检索和( 直接 ) 检索。
12.哈希检索的技术的关键是( 构造哈希函数 )和( 解决冲突的方法 )。结构来组
13.VSAM系统是由( 索引集 )、( 顺序集 ) 、( 数据集 )构成的。
14.VSAM( 虚拟存储存取方法 )文件的优点是：动态地( 分配和释放存储空间 ) ，不需要文件进行( 重组 ) ，并能较快地( 对插入的记录 ) 进行查找。
一～五章选择题
一
1.学习数据结构的主要目的是( C )。
A．处理数据计算问题 B．研究程序设计技巧
C．选取合适数据结构，写出更有效的算法 D．是计算机硬件课程的基础
2.数据结构是一门研究非数值计算的程序设计问题中计算机的逻辑存储以及它们之
间的( B )和运算的科学。
A．结构 B．关系 C．运算 D．算法
3.在计算机中存储一个数据元素的位串称为 ( A ) 。
A. 结点
B. 数据项
C. 数据字段
D. 字符串
4.算法指的是( C )
A.计算机程序
B.排序算法
C.解决问题的有限运算序列
D.解决问题的计算方法
5.( D )是数据不可分割的最小单位。
A．数据结构 B．数据对象 C．数据元素 D．数据项
6.数据结构有 ( D ) 种基本逻辑结构。
A. 1
B. 2
C. 3
D. 4
7.在数据结构中，从逻辑上可以把数据结构分成( C )。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构
C．线性结构和非线性结构 D．内部结构和外部结构
8.通常所说的时间复杂度是指( B )。
A．语句的频度和 B．算法的时间消耗 C．渐近时间复杂度 D．最坏时间复杂度9.( C )是数据的基本单位。
A．数据结构 B．数据项 C．数据元素 D．数据类型
10.数据元素是数据的基本单位，其内 ( C ) 数据项。
A. 只能包括一个
B. 不包含
C. 可以包含多个
D. 必须包含多个
11.计算机算法必须具有输入、输出和( A )等五个特性。
A．可执行性、确定性、有穷性B可执行性、可移植性、可扩充性
C．确定性、有穷性和稳定性D．易读性、稳定性和安全性
12.下列时间复杂度中最好的是 ( A ) 。
A. O(1)
B. O(n)
C. O(log2n)
D. O(n^2)
13.对于反复多次使用的程序，应尽是选用( B )算法。
A．节约空间 B．节约时间 C．简明易懂 D．容易调试
14.下列说法不正确的是( D )。
A．数据元素是数据的基本单位
B．数据项是数据中不可分割的最小可标识单位
C．数据可由若干个数据元素构成
D．数据项可由若干个数据元素构成
15.计算机算法指的是( C )。
A．计算方法和运算结果 B．排序方法 C．解决某一问题的有限序列 D．调度方法
16.下列时间复杂度中最坏的是 ( D ) 。
A. O(1)
B. O(n)
C. O(log2n)
D. O(n^2)
17.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数
据组织形式，其中解释错误的是( A )。
A．集合中任何两个结点之间都有逻辑关系但组织形式松散
B．线性结构中结点按逻辑关系依次排列形成一条“锁链”
C．树形结构具有分支、层次特性，其形态有点像自然界中的树
D．图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
18.某算法的时间耗费为T(n)=100n+10log2n+n2+10，该算法的时间复杂度为( A )：
A．O(n2) B．O(n3) C．O(n) D．O(1)
19.一般而言，最适合描述算法的语言是( C )。
A．自然语言 B．计算机程序语言
C．介于自然语言和程序设计语言之间的语言 D．数学公式
20.下列四种基本的逻辑结构中，数据元素之间关系最弱的是 ( A ) 。
A. 集合
B. 线性结构
C. 树形结构
D. 图状结构
21.评价一个算法时间性能的主要标准是( D )。
22.D．算法的时间复杂度
23.一个算法必须保证执行有限步之后结束，这是算法的( A )特性。
A．有穷性 B．确定性 C．可行性 D．输出
24.逻辑关系是指数据元素间的 ( C ) 。
A. 类型
B. 存储方式
C. 结构
D. 数据项
25.研究数据结构就是研究( D )。
A．数据的逻辑结构及其数据在运算上的实现
B．数据的存储结构
C．数据的逻辑和存储结构
D．数据的逻辑和存储结构及其数据在运算上的实现
26.算法分析的两个主要方面是( A )。
A．空间复杂性和时间复杂性 B．正确性和简明性
C．可读性和文档性 D．数据复杂性和程序复杂性
27.用类 C 语言描写的算法 ( B ) 。
A. 可以直接在计算机上运行
B. 可以描述解题思想和基本框架
C. 不能改写成 C 语言程序
D. 与 C 语言无关
28.逻辑结构是 ( A ) 关系的整体。
A. 数据元素之间逻辑
B. 数据项之间逻辑
C.
C.数据类型之间
D. 存储结构之间
29.要求同一逻辑结构的所有数据元素具有相同特性，这意味着( B )。
A.数据元素具有同一的特点
B.不仅数据元素包含的数据项的个数要相同,而且对应数据项的类型要一致
C.每个数据元素都一样式
D.数据元素所包含的数据项的个数要相等
30.算法分析的目的是( C )。
A.找出数据结构的合理性
B.研究算法中的输入与输出的关系
C.分析算法的效率以求改进
D.分析算法的易懂性和文档性
31.数据结构被形式化地定义为(K，R)，其中，R是K上( D )的有限集合。
A．操作 B．映象 C．存储 D．关系
32.一个存储结点存放一个 ( B ) 。
A. 数据项
B. 数据元素
C. 数据结构
D. 数据类型
33.算法能正确地实现预定功能的特性称为 ( A ) 。
A. 正确性
B. 易读性
C. 健壮
D. 高效率
34.数据结构被形式化地定义为(K，R)，其中K是( B )的有限集合。
A．算法 B．数据元素 C．数据操作 D．逻辑结构
35.以下说法不正确的是( A )。
A．数据结构就是数据之间的逻辑结构
B．数据类型可看成是程序设计语言中已实现的数据结构
C．数据项是组成数据元素的最小标识单位
D．数据的抽象运算不依赖具体的存储结构
36.算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成，这是算
法的( C )。
A．有穷性 B．确定性 C．可行性 D．输出
二
1.线性表L=(a1,a2,…ai,…,an ),下列说法正确的是( D )。
A.每个元素都有一个直接前驱和直接后继
B.线性表中至少要有一个元素
C.表中诸元素的排列顺序必须是由小到大或由大到小的
D.除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和
直接后继
2.对线性表进行二分法查找，其前提条件是( A )。
A．线性表以顺序方式存储，并且按关键码值排好序
B．线性表以顺序方式存储，并且按关键码值的检索频率排好序
C．线性表以链接方式存储，并且按关键码值排好序
D．线性表以链接方式存储，并且按关键码值的检索频率排好序
3.对于只在表的首尾两端进行插入操作的线性表，宜采用的存储结构为( C )。
A.顺序表
B.用头指针表示的单循环链表
C.用尾指针表示的单循环链表
D.单链表
4.线性表的顺序存储结构是一种( A )的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取
5.用数组表示线性表的优点是( B )。
A.便于插入和删除操作
B.便于随机存取
C.可以动态地分配存储空间
D.不需要占用一片相邻的存储空间
6.在线性表的下列存储结构中,读取元素花费时间最少的是( D )。
A.单链表
B.双链表
C.循环链表
D.顺序表
7.线性结构中的一个结点代表一个( A )。
A.数据元素
B.数据项
C.数据
D.数据结构
8.对于顺序表,以下说法错误的是( A )。
A.顺序表是用一维数组实现的线性表,数组的下标可以看成是元素的绝对地址
B.顺序表的所有存储结点按相应数据元素元素间的逻辑关系决定的次序依次排列
C.顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D.顺序表的特点是:逻辑上相邻的元素,存储在物理位置也相邻的单元中
9.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用
( A )存储方式最节省时间。
A．单链表 B．双链表 C．单向循环 D．顺序表
10.线性表是( A )。
A.一个有限序列，可以为空
B.一个有限序列，不可以为空
C.一个无限序列，可以为空
D.一个无限序列，不可以为空
11.在( C )运算中，使用顺序表比链表好。
A．插入 B．删除 C．根据序号查找 D．根据元素值查找
12.在循环双向链表的p所指的结点之后插入s所指结点的操作是( D )。
A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;
B．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;
C．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;
D.s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;
13. ( D )适合作为经常在首尾两端操作线性表的存储结构。
A.顺序表
B.单链表
C.循环链表
D.双向链表
14.对于顺序表的优缺点,以下说法错误的是( C )。
A.无需为表示结点间的逻辑关系而增加额外的存储空间
B.可以方便地随机存取表中的任何一结点
C.插入和删除操作较方便
D.由于顺序表要求占用连续的空间,存储分配只能预先进行(静态分配)
15.设非空单链表的数据字段为data，指针字段为next，指针p指向单链表中第i个
结点，s指向已生成的新结点，现将s结点插入到单链表中，使其成为第i+1个结点，下列算法段能正确完成上述要求的是( C )。
A.s->next=p->next=s；
B.p->next=s；s->next=p->next；
C.s->next=p->next；p->next=s；交换p->data和s->data；
D.p=s；s->next=p
16.线性表中各元素之间的关系是( C )关系。
A.层次
B.网状
C.有序
D.集合
17.在长度为n的顺序表的第i（1≤i≤n+1）各位置上插入一个元素，元素的移动次
数为( D )。
A.n-(i-1)
B.n-i
C.i
D.i-1
18.在一个单链表HL中,若要在指针q所指结点的后面插入一个由指针p所指向的结
点，则执行( D )。
A．q->next=p->next;p->next=q;
B．p->next=q->next;q=p;
C．q->next=p->next;p->next=p;
D．p->next=q->next;q->next=p;
19.不带头结点的单链表head为空的判定条件是( A )
A．head==NULL B．head->next==NULL
C．head->next==head D．head!=NULL
20.非空的循环单链表head的尾结点(由p所指向)满足( C )。
A．p->next=NULL B．p=NULL C．p->next=head D．p=head
21.顺序表是线性表的( B )。
A.链式存储结构
B.顺序存储结构
C.索引存储结构
D.散列存储结构
22.线性表中哪些元素只有一个直接前驱和一个直接后继( C )。
A.首元素
B.尾元素
C.中间元素
D.所有的元素
23.在长度为n的顺序存储的线性表中，删除第i个元素(1≤i≤n)时，需要从前向后
依次前移( A )个元素。
A．n-I B．n-i+1 C．n-i-1 D．i
24.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执
行( D )。
A．s->next=p;p->next=s; B．s->next=p->next;p->next=s;
C．s->next=p->next;p=s; D．p->next=s;s->next=p;
25.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，
需平均比较( B )个结点。
A．n B．n/2 C．(n-1)/2 D．(n+1)/2
26.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针字段，
现要把一个指针s所指的新结点作为非空双链表中q所指结点（中间结点）的直接后继结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( C )。
A. q->right=s；s->left=q；q->right->left=s； s->right=q->right；
B. s->left=q；q->right=s；q->right->left=s； s->right=q->right；
C. s->left=q;s-right=q->right;q->right-left=s;q->right=s;
D.以上都不对
27.下面给出的算法段是把一个q所指新结点作为非空双向链表中的p所指结点的前
驱结点插入到该双链表中，能正确完成要求的算法段是( A )。
A．q->rlink=p;q->llink=p->llink;p->llink=q;p->llink->rlink=q;
B．p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink;
C．q->llink=p->llink;q->rlink=p;p->llink->rlink=q;p->llink=q;
D．以上都不对
28.循环链表的主要优点是( D )。
A.不再需要头指针了
B.已知某个结点的位置后,容易找到它的直接前驱
C.在进行插入、删除操作时,能更好地保证链表不断开
D.从表中任一结点出发都能扫描到整个链表
29.在单链表的一个结点中有( A )个指针。
A.1
B.2
C.0
D.3
30.在一个单链表中，删除p所指的直接后继的操作是( A )。
A．p->next=p->next->next; B．p=p->next->next;
C．p=p->next; D．p->next->next=p->next;
31.带有头结点的单链表head为空的判定条件是( B )。
A．head==NULL B．head->next==NULL
C．head->next==head D．head!=NULL
32.将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为( C )。
A．O(1) B．O(n) C．O(m) D．O(m+n)
33.下面关于线性表的叙述中，错误的是( B )。
A.线性表采用顺序存储，必须占用一片连续的存储单元
B.线性表采用顺序存储，便于进行插入和删除操作
C.线性表采用链接存储，不必占用一片连续的存储单元
D.线性表采用链接存储，便于插入和删除操作
34.在单循环链表中，用尾指针取代头指针的作用是( D )。
A．方便查找中间结点 B．方便查找终端结点
C．方便查找开始结点 D．查找开始结点和终端结点同样方便
35.在一个单链表中，已知q所指结点是p所指结点的前趋结点，若在p和q之间插
入s结点，则执行的操作序列是。( C )。
A.s->next=p->next;p->next=s;
B.p->next=s->next;s->next=p;
C.q->next=s;s->next=p;
D.p->next=s;s->next=q;
36.带有头结点的单循环链表head为空的判定条件是( C )。
A．head==NULL B．head->next==NULL C．head->next==head D．head!=NULL
37.链式存储的存储结构所占存储空间( A )。
A.分两部分，一部分存放结点值，另一部分存放表示结点关系的指针
B.只有一部分，存放结点值
C.只有一部分，存放表示结点关系的指针
D.分两部分，一部分存放结点值，另一部分存放结点所占单元数
38.线性表（L）经运算InitList（L）后，函数IEmpty（L）的值是( C )。
A.0
B.false
C.1
D.Null
39.以下关于链式存储结构的叙述中，( C )是不正确的。
A.结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构
B.逻辑上相邻的结点物理上不必邻接
C.可以通过计算直接确定第i个结点的存储地址
D.插入、删除运算操作方便，不必移动结点
40.在等概率情况下，顺序表的插入操作要移动( B )结点。
A．全部 B．一半 C．三分之一 D．四分之一
41.在一个具有n个结点的有序单链表中插入一个新的结点并仍然有序的时间复杂度
是( B )。
A．O(1) B．O(n) C．O(n^2) D．O(log2n)
42.单链表中，增加头结点的作用是( A )。
A.方便运算的实现
B.用于标志单链表
C.使单链表中至少有一个结点
D.用于标志起始结点
43.两指针p和q，分别指向单链表的两个元素，p所指元素是q所指元素的前驱的条
件是( A )。
A.p->next==q
B.q->next==p
C.p==q
D.p->next==null
44.线性表采用链式存储时，其地址( D )。
A.必须是连续的
B.一定是不连续的
C.部分地址必须是连续的
D.连续与否均可以
45.以下关于线性表的说法不正确的是( C )。
A.线性表中的数据元素可以是数字、字符、记录等不同类型
B.线性表中包含的数据元素个数不是任意的
C.线性表中的每个结点都有且只有一个直接前驱和直接后继
D.存在这样的线性表：表中各结点都没有直接前驱和直接后继
46.在具有n个结点的单链表中，实现( A )的操作，其算法的时间复杂度都是O(n)。
A．遍历链表和求链表的第I个结点 B．在地址为p的结点之后插入一个结点 C．删除开始结点
D．删除地址为p的结点的后继结点
47.指针P所指的元素是双向循环链表L的尾元素的条件是( D )。
A.P==L
B.p==null
C.p->prior==L
D.p->next==L
48.对顺序表上的插入、删除算法的时间复杂度分析来说，通常以( B )为标准操作。
A．条件判断 B.结点移动 C.算术表达式 D.赋值语句
49.两个指针p和q分别指向双向循环链表L两个元素，p所指元素是q所指元素的
后继的条件是( B )。
A.p==q
B.q->next==p
C.p->next==q
D.q->next==p->next
50.线性表的链接实现有利于( A )运算。
A.插入
B.读表元
C.查找
D.定位
51.用单链表的方式存储的线性表，存储每一个结点需要两个域，一个是数据域，另
一个是( B )。
A.当前结点所在地址域
B.指针域
C.空指针域
D.空闲域
52.在双向链表的一个结点中有( B )个指针。
A.1
B.2
C.0
D.3
53.指针p指向线性链表L首元素的条件是( A )。
A.p=L
B.L->next=p
C.p->next=L
D.p->next=null
54.对线性表，在( B )情况下应当采用链表表示。
A．经常需要随机在存取元素 B．经常需要进行插入和删除
C．表中元素需要占据一片连续的存储空间 D．表中元素的个数不变
55.若某线性表中，最常用的操作是在最后一个元素之后插入一个元素和删除第一个
元素，则采用( C )存储方式最省时。
A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表
56.线性表的链式存储结构是一种( B )的存储结构。
A．随机存取 B．顺序存取 C．索引存取 D．散列存取
57.用链接方式存储的队列，在进行删除运算时( D )。
A．仅修改头指针 B．仅修改尾指针
C．头、尾指针都要修改 D．头、尾指针可能都要修改
58.在顺序表中，只要知道( D )，就可在相同时间内求出任一结点的存储地址。
A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小
三
1.4个元素进S栈的顺序是A、B、C、D，进行两次Pop（S，x）操作后，栈顶元素的
值是( B )。
A．A B．B C．C D．D
2.表达式a*(b+c)-d的后缀表达式是( B )。
A.abcdd+-
B.abc+*d-
C.abc*+d-
D.-+*abcd
3.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行
( D )。
A.x=HS;HS=HS->next;
B.x=HS->data;
C.HS=HS->next;x=HS->data;
D.x=HS->data;HS=HS->next;
4.当循环队列Sq是满队列时，存放队列元素的数组data有n个元素，则data中存
放个队列元素( A )。
A．n B．n-1 C．n-2 D．0
5.队列操作的原则是( B )。
A．先进先出 B．先进后出 C．只能进行插入 D．只能进行删除
6.队列的特点是( A )。
A．先进先出 B．后进先出 C.先进后出 D．不进不出
7.队列是限定在( C )处进行插入操作的线性表。
A．端点 B．队头 C．队尾 D．中间
8.和顺序栈相比，链栈有一个比较明显的优势是( A )。
A.通常不会出现栈满的情况
B.通常不会出现栈空的情况
C.插入操作更容易实现
D.删除操作更容易实现
9.经过下列运算后GetHead（Q）的值是( B )。
InitQueue（Q）；EnQueue（Q，a）；EnQueue(Q,b）；OutQueue（Q，x）；
A．a B．b C．1 D．2
10.链栈ls是空栈的条件是( A )。
A．ls==null B．ls->next==null C．Ls==0 D．ls->next==ls
11.判定一个顺序栈ST（最多元素为m0）为空的条件是( B )。
A．ST.top<>ST.base B．ST.top==ST.base
C．ST.top<>m0 D．ST.top==m0
12.判定一个循环队列QU(最多元素为m0)为空的条件是( C )。
A．QU.front==（QU.rear+1）%m0 B．QU.front！=（QU.rear+1）%m0
C．QU.front==QU.rear D．QU.front！=QU.rear
13.判定一个循环队列QU(最多元素为m0)为满的条件是( A )。
A．QU.front==（QU.rear+1）%m0 B．QU.front！=（QU.rear+1）%m0
C．QU.front==QU.rear D．QU.front！=QU.rear
14.如果以链表作为栈的存储结构,则出栈操作时( C )
A.必须判别栈是否满
B.判别栈元素的类型
C.必须判别栈是否空
D.对栈不做任何判别
15.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pn,若p1=n,
则pi为( C )。
A.I
B.n=I
C.n-I+1
D.不确定
16.设计一个判别表达式中左、右括号是否配对出现的算法,采用( )数据结构最佳
( B )。
A.线性表的顺序存储结构
B.栈
C.队列
D.线性表的链式存储结构
17.顺序栈存储空间的实现使用( B )。
A．链表 B．数组 C．循环链表 D．变量
18.顺序栈是空栈的条件是( A )。
A．top==0 B．top==1 C．top==-1 D．top==m
19.同一个栈内各元素的类型( A )。
A．必须一致 B．可以不一致 C．不能一致 D．不必不一致
20.向一个栈顶指针为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;
21.循环队列Sq是空队列的条件是( A )。
A．Sq->rear= =Sq->front
B．(Sq->rear+1）％maxsize= =Sq->front
C．Sq->rear= =0 D．Sq->front= =0 22.循环队列Sq是满队列的条件是( B )。
A．Sq->rear= =Sq->front
B．（Sq->rear+1）％maxsize= =Sq->front
C．Sq->rear= =0
D．Sq->front= =0
23.一个队列的入对序列是1,2,3,4,则队列的输出序列是( B )。
A.4,3,2,1
B.1,2,3,4
C.1,4,3,2
D.3,2,4,1
24.一个顺序栈一旦说明，其占用空间的大小( A )。
A．已固定 B．可以改变 C．不能固定 D．动态变化
25.一个栈的入栈序列(顺序)是a,b,c,d,e,则栈不可能的输出序列是( C )。
A.edcba
B.decba
C.dceab
D.abcde
26.一个栈的入栈序列是1,2,3,4,则栈的可能的输出序列是( B )。
A.1,4,2,3
B.2,1,4,3
C.4,2,1,3
D.4,2,3,1
27.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是( C )。
A.edcba
B.decba
C.dceab
D.abcde
28.以下说法正确的是( A )。
A.因链栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
B.因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况
C.对于链栈而言，在栈满状态下，如果再进行入栈操作，则会发生“上溢”
D.对于顺序栈而言，在栈满状态下，如果再进行入栈操作，则会发生“下溢”
29.元素A、B、C、D依次进顺序栈后，栈顶元素是( D )。
A．A B．B C．C D．D
30.在计算递归函数时,如不使用递归过程，则一般情况下必须借助( A )数据结构
A.栈
B.树
C.双向队列
D.顺序表
31.在栈顶一端可进行的全部操作是( C )。
A．插入 B．删除 C．插入和删除 D．进栈
32.栈操作的原则是( B )。
A．先进先出 B．先进后出 C．只能进行插入 D．只能进行删除
33.栈的特点是( B )。
A．先进先出 B．后进先出 C．后进后出 D．不进不出
34.栈和队列的共同点是( C )。
A.都是先进后出发
B.都是先进先出
C.只允许在端点处插入和删除元素
D.没有共同点
35.栈是限定在( C )处进行插入或删除操作的线性表。
A．端点 B．栈底 C．栈顶 D．中间
36.栈是一个( B )线性表结构。
A．不加限制的 B．加了限制的 C．推广了的 D．非
37.栈与一般线性表区别主要在方面( D )。
A．元素个数 B．元素类型 C．逻辑结构D．插入、删除元素的位置
四
1.设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j)
返回串s的从序号i的字符开始的j个实际字符组成的子串,len(s)返回串s的长度,则con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的结果是( D )。
A.BCDEF
B.BCDEFG
C.BCPQRST
D.BCDEFEF
2.串是任意有限个（ C ）
A符号构成的序列 B符号构成的集合
C字符构成的序列 D字符构成的集合
3.设有两个串p和q,求q 在p中首次出现的位置的运算称作( B )
A.连接
B.模式匹配
C.求子串
D.求串长
4.说串是一种特殊的线性表，则其特殊性表现在( C )。
A.串是可以顺序存储的
B.串是可以链接存储的
C.串中的每一个结点由一个字符组成
D.串中的结点是多个字符组成的
五
1.常对数组进行的两种基本操作是( C )。
A.建立与删除
B.索引和修改
C.查找和修改
D.查找和索引
2.对矩阵压缩存储是为了（ B ）。
A.方便运算
B.节省时间
C.方便存储
D.提高运算速度
3.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标I
的范围从0到8，列下标j的范围从1到10，如M按行优先方式存储，元素M[8][5]的起始位置与当M按列优先方式存储时的( B )元素的起始地址一致。
A.M[8][5]
B.M[3][10]
C.M[5][8]
D.M[0][9]
4.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标I
的范围从0到8，列下标j的范围从1到10，则M的第8列和第5行共占( A )个字节。
A.108
B.114
C.54
D.60
5.二维数组M的成员是6个字符（每个字符占一个存储单元）组成的串，行下标I
的范围从0到8，列下标j的范围从1到10，则存在M至少需要( D )个字节。
A.90
B.180
C.240
D.540
6.二维数组M的元素是4个字符（每个字符占一个存储单元）组成的串，行下标I
的范围从0到4，列下标j的范围从0到5，M按行存储时元素M[3][5]的起始地址与M按列存储时元素( B )的起始地址相同。
A.M[2][4]
B.M[3][4]
C.M[3][5]
D.M[4][4]
7.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，
就完成了对该矩阵的转置运算，这种观点( B )。
A.正确
B.错误
8.设矩阵 A是一个对称矩阵，为了节省空间，将其下三角矩阵按行序存放在一维数
组 B[1，n（n+1）/2]中，对下三角部分中任一元素a ij （i≥j），在一维数B中下标k的值是( B )。
A．i（i-1）/2+j-1 B．i（i-1/2+j C．i （i+1）/2+j-1 D．i（i+1）/2+j
9.数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到
10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是( C )。
A.50
B.100
C.240
D.270
10.数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到
10，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[5][8]的起始地址为_ _B_ _。
A.SA+141
B.SA+180
C.SA+141
D.SA+141
11.数组A中，每个元素A的长度为3个字节，行下标I从1到8，列下标j从1到
10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( C )。
A.SA+141
B.SA+144
C.SA+222
D.SA+225
12.数组的基本操作主要包括( C )。
A．建立与删除 B．索引与修改 C．访问与修改 D．访问与索引
13.稀疏矩阵一般的压缩存储方法有两种，即( C )。
A. 二维数组和三维数组
B. 三元组和散列
C. 三
元组和十字链 D. 散列和十字链表
判断题
1．线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。( × )
2．采用线性探测法处理冲突的散列表中，所有同义词（其冲突的元素）在表中相邻。
( × )
3．调用一次深度优先遍历可以访问到图中的所有顶点。( × )
4．调用一次广度优先遍历可以访问到图中的所有顶点。( √ )
5．堆是完全二叉树，完全二叉树不一定是堆。( × )
6．对链表进行插入和删除操作时不必移动链表中结点。( √ )
7．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。
( √ )
8．快速排序是排序算法中平均性能最好的一种排序。 ( √ )
9．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
( √ )
10．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。
( √ )
11．任何有向网拓扑排序的结果是唯一的。( × )
12．入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。
( × )
13．若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。 ( √ )
14．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。
( × )
15．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。
( 对 )
16．顺序表查找指的是在顺序存储结构上进行查找。 ( × )
17．算法的效率越高越好。 ( × )
18．外部排序过程主要部分分为两个阶段：生成初始归并段和对归并段进行逐趟归并。
( 对 )
19．希尔排序算法的时间复杂度为O(n^2)。( × ) 20．线性表的顺序存储结构比链式存储结构更好。( × ) 21．用邻接矩阵法存储图时，所占用的空间大小仅与图中结点个数有关。
( 对 )
22．用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。 ( × )
23．有向图的邻接表和逆邻接表中表结点的个数不一定相等。 ( × ) 24．栈和队列的存储方式既可是顺序方式，也可是链接方式。 ( 对 )
25．中序遍历二叉排序树可以得到一个有序的序列。 ( 对 )
26．子串“ABC”在主串“AABCABCD”中的位置为2。(对 )
完成以下操作(二)
15．设无向图G如下图所示，给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。
16．设有无向图G，要求给出用普里姆算法(克鲁斯卡尔算法，两个算法都做)构造最小生成树所走过的边的集合。
三、思考以下算法设计
1.设计一个算法，功能是在带头结点的单链表head中删除数据域值最小的结点。struct Node
{
int Data ;
Node *next ;
};
void deleteNode( Node *head , int KeyData ) // KeyData 需要删除的结点的值
{
Node *p = head ;
while( p ->next != NULL )
{
if( p -> next -> Data == KeyData )
p ->next = p ->next -> next ; p = p -> next ;
}}
2.有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待
排序的表（用数组表示，表中所有待排序的关键字互不相同）进行排序，并将排序结构存放到另一个新的表中。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出计数值为C，那么，这个记录在新的有序表中的合适的存放位置即为C。实现计数排序的算法。
3.试以单链表为存储结构实现简单选择排序的算法。
void LinkList_Select_Sort(LinkList &L) //单链表上的简单选择排序算法
{ for (p=L;p->next->next;p=p->next)
{ q=p->next; x=q->data;
for (r=q,s=q;r->next;r=r->next) //在q后面寻找元素值最小的结点
if (r->next->data { x=r->next->data; s=r; } if (s!=q) //找到了值比q->data更小的最小结点s->next { p->next=s->next; s->next=q; t=q->next; q->next=p->next->next; p->next->next=t; } //交换q和s->next两个结点 }//for }//LinkList_Select_Sort 4.编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。 void Bubble_Sort2(int a[ ],int n) //相邻两趟是反方向起泡的冒泡排序算法 { low=0;high=n-1; //冒泡的上下界 change=1; while (low { change=0; for(i=low;i if (a[i]>a[i+1]) { a[i]<->a[i+1]; change=1; } high--; //修改上界 for (i=high;i>low;i--) //从下向上起泡 if (a[i] { a[i]<->a[i-1]; change=1; } low++; //修改下界 }//while }//Bubble_Sort2 5.写出从图的邻接表转换成邻接矩阵表示的算法。 6.编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 int degreel(Graph &ga,int numb) int degree1(Graph & ga, int numb) { //根据无向图的邻接矩阵求出序号为numb的顶点的度数 int j,d=0; for(j=0; j if (ga.cost[numb][j]!=0 && ga.cost[numb][j]!=MAXINT) d++; return (d); } 7.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除 表中所有值小于max但大于min的元素的算法。 delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head; p=head->next; while (p!=NULL) if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; } else { q->next=p->next; free(p); p=q->next; } } 8.已知线性表的元素按递增顺序排列，并以带头结点的单链表作为存储结构。试编写 一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。delete(LinkList *head, int max, int min) { linklist *p, *q; if (head!=NULL) { q=head; p=head->next; while((p!=NULL) && (p->data<=min)) { q=p; p=p->next; } while((p!=NULL) && (p->data p=p->next; q->next=p; } } 9.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data，next 和prior，结点LinkList类型定义如下： 现在所有结点已经由next域连接起来，试编一个算法，利用prior域(此域初值为NULL)把所有结点按照其值从小到大的顺序链接起来。 《数据结构课程实验》大纲 一、《数据结构课程实验》的地位与作用 “数据结构”是计算机专业一门重要的专业技术基础课程，是计算机专业的一门核心的关键性课程。本课程较系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了常用的多种查找和排序技术，并做了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： （1）内容丰富，学习量大，给学习带来困难； （2）贯穿全书的动态链表存储结构和递归技术是学习中的重点也是难点； （3）所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度； （4）隐含在各部分的技术和方法丰富，也是学习的重点和难点。 根据《数据结构课程》课程本身的技术特性，设置《数据结构课程实验》实践环节十分重要。通过实验实践内容的训练，突出构造性思维训练的特征, 目的是提高学生组织数据及编写大型程序的能力。实验学时为18。 二、《数据结构课程实验》的目的和要求 不少学生在解答习题尤其是算法设计题时，觉得无从下手，做起来特别费劲。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。数据结构中稍微复杂一些的算法设计中可能同时要用到多种技术和方法，如算法设计的构思方法，动态链表，算法的编码，递归技术，与特定问题相关的技术等，要求重点掌握线性链表、二叉树和树、图结构、数组结构相关算法的设计。在掌握基本算法的基础上，掌握分析、解决实际问题的能力。 三、《数据结构课程实验》内容 课程实验共18学时，要求完成以下六个题目： 实习一约瑟夫环问题（2学时） 数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 《数据结构与算法设计》实验大纲及实验内 容详细要求 一、课程编号： 二、课程类型：必修 适用专业：通信工程 实验学时：32学时 三、本课程的地位、作用与任务 数据结构课程的目标是使学生掌握数据的基本的逻辑结构和存储结构、一些典型的数据结构算法及程序设计方法，要求学会分析数据对象特征，掌握数据组织方法和计算机的表示方法，为数据选择适当的逻辑结构、存储结构以及相应的处理算法，要求具备算法分析的基本技术和能力，并培养良好的程序设计风格，掌握开发复杂、高效程序的技能。 在实验前要预习或者自行补充部分学时，同时进行部分代码准备，实验后要认真完成实验报告。 四、课程基本要求 1.学生应根据每个实验的任务和教师所提的要求，带C语言教材和课程教材。 2.完成指定的实验任务，保存源代码并输出、记录实验结果。 3.实验结束后按时提交实验报告，对于未完成部分，应该利用课余时间补充完成。 五、实验安排 本实验课程共32学时，五个实验(单元)，分16次实验，每次2学时。 实验一：C程序编程、调试实验 1、实验学时：4学时（学生堂下自行加4学时） 2、实验目的： 1)巩固复习前期所学C语言的基本数据类型和自定义数据类型等知识点，强化 学习数据结构语言和编程基础。 2)巩固复习前期所学C语言的函数参数传递、指针和结构体等知识点，加强学 习数据结构语言基础。 3)能够较熟练调试程序 3、实验内容： 1)学生信息的显示。具体要求如下： ●定义一个结构体描述学生信息(学号，姓名，性别，年龄，住址)； ●设计一个函数，用于显示单个学生信息，函数的参数为前面定义的结构 体类型； ●设计一个主函数，在主函数中输入学生的信息，并调用前面定义的函数 进行显示（学生人数不少于5人）。 2)输入若干个整数存储到数组元素值，然后按输入顺序进行逆置存储，最后打 印出逆置后的元素值。要求用指针和动态内存分配方法实现。例如输入：1023045，逆置后显示为：5430210。 3)编写扑克牌发牌程序。在VC++的调试环境下观察数据存储位置、存储数据的 变化、数据之间的逻辑次序、物理存储位置次序。 4)对上述C程序进行调试，运行，从中理解数据和算法的概念，总结调试方法。 实验二：线性表的存储及基本操作、综合应用 1、实验学时：6学时 2、实验目的： 1)掌握线性表的逻辑特征 2)熟练掌握线性表的链式存储结构定义及基本操作 3)理解循环链表和双链表的特点和基本运算 4)加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实 际问题的编程能力。 5)掌握顺序表和链表的概念，学会对问题进行分析，选择恰当的逻辑结构和物理 结构 6)和实验一一起撰写一份实验报告，总结学习效果 3、实验内容： 使用顺序表和链表两种存储结构（linked list），存储输入的一组数据整数，能够进 数据结构实验总结报告 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件， 会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 （3）程序界面更加人性化。 Huffman Tree Demo (C) 2011-12-16 boj Usage: huffman [-c file] [-u file] output_file -c Compress file. e.g. huffman -c test.txt test.huff -u Uncompress file. e.g. huffman -u test.huff test.txt 目前的程序提示如上所示。如果要求实用性，可以考虑加入其他人性化的功能。 三、调研常用的压缩算法，对这些算法进行比较分析 （一）无损压缩算法 ①RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。 变体1：重复次数+字符 文本字符串：A A A B B B C C C C D D D D，编码后得到：3 A 3 B 4 C 4 D。 禁止抄袭，否则一律不及格。机会仅有一次！！！！！ 《数据结构课程设计》 一、基本要求 （1）选择一个与线性表、堆栈和队列、数组、树、图、排序、查找等相关的专题，利用C语言或java来实现，解决具有一定规模的、具有实际意义的应用题目。 （2）论文内容主要包括封面、正文、参考文献等，其中正文内容主要引言、系统分析设计、系统实现和小结几部分组成。 （3）论文格式参考下面文档《模板》撰写课程报告。 （4）特别要求自己独立完成。 （5）第15周周一提交课程设计论文、电子版、源代码。 二、创新要求 在基本要求达到后，可进行创新设计，如改善算法性能、友好的人机界面。 可选题目列表： 1.运动会分数统计 任务：参加运动会有n个学校，学校编号为1……n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1……m，女子m+1……m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20） 功能要求： 1)可以输入各个项目的前三名或前五名的成绩； 2)能统计各学校总分， 3)可以按学校编号或名称、学校总分、男女团体总分排序输出； 4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。 5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有合理的提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指 数据结构实验报告全集 实验一线性表基本操作和简单程序 1．实验目的 （1）掌握使用Visual C++ 6.0上机调试程序的基本方法； （2）掌握线性表的基本操作：初始化、插入、删除、取数据元素等运算在顺序存储结构和链表存储结构上的程序设计方法。 2．实验要求 （1）认真阅读和掌握和本实验相关的教材内容。 （2）认真阅读和掌握本章相关内容的程序。 （3）上机运行程序。 （4）保存和打印出程序的运行结果，并结合程序进行分析。 （5）按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果 实验代码： 1）头文件模块 #include iostream.h>//头文件 #include nodetype *create()//建立单链表，由用户输入各结点data域之值，//以0表示输入结束 { elemtype d;//定义数据元素d nodetype *h=NULL,*s,*t;//定义结点指针 int i=1; cout<<"建立一个单链表"< 数据结构实验总结报告 李博杰PB10000603 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。 ①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 实验一~实验四任选一题；实验五~实验九任选一题。 实验一运动会分数统计 一、实验目的： （1）熟练掌握线性表的两种存储方式 （2）掌握链表的操作和应用。 （3）掌握指针、结构体的应用 （4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。 二、实验内容： 【问题描述】 参加运动会的n个学校编号为1~n。比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m＋1~m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。 【基本要求】 产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。 【测试数据】 对于n＝4，m＝3，w＝2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。 【实现提示】 可以假设m≤20，m≤30，w≤20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。 【选作内容】 允许用户指定某些项目可采取其他名次取法。 实验二停车场管理 一、实验目的： （1）熟练掌握栈顺存和链存两种存储方式。 （2）掌握栈的基本操作及应用。 （3）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 二、实验内容： 【问题描述】 设停车场是一个可停放n辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。 【基本要求】 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。 【测试数据】 设n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D，2，35），（D，4，40），（E，0，0）。其中：A表示到达（Arrival）；D表示离去（Departure）；E表示输入结束（End）。 【实现提示】 需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。 【选作内容】 （1）两个栈共享空间，思考应开辟数组的空间是多少？ （2）汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。 （4）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。 2009级数据结构实验报告 实验名称：约瑟夫问题 学生姓名：李凯 班级：21班 班内序号：06 学号：09210609 日期：2010年11月5日 1．实验要求 1）功能描述：有n个人围城一个圆圈，给任意一个正整数m，从第一个人开始依次报数，数到m时则第m个人出列，重复进行，直到所有人均出列为止。请输出n个人的出列顺序。 2）输入描述：从源文件中读取。 输出描述：依次从显示屏上输出出列顺序。 2. 程序分析 1）存储结构的选择 单循环链表 2）链表的ADT定义 ADT List{ 数据对象：D={a i|a i∈ElemSet,i=1,2,3,…n,n≧0} 数据关系：R={< a i-1, a i>| a i-1 ,a i∈D,i=1,2,3,4….,n} 基本操作： ListInit(&L)；//构造一个空的单链表表L ListEmpty(L); //判断单链表L是否是空表，若是，则返回1，否则返回0. ListLength(L); //求单链表L的长度 GetElem（L，i）；//返回链表L中第i个数据元素的值； ListSort(LinkList [内容要求] 1、存储结构：顺序表、单链表或其他存储结构，需要画示意图，可参考书上P59 页图2-9 2.2 关键算法分析 结点类： template 数据结构实验报告 第次实验 学号： 20141060106 姓名：叶佳伟 一、实验目的 1、复习二叉树的逻辑结构、存储结构及基本操作； 2、掌握二叉链表及二叉树的创建、遍历； 3、了解二叉树的应用。 二、实验内容 1、（必做题）假设二叉树中数据元素类型是字符型，请采用二叉链表实现二叉树的以下基本操作： （1）根据二叉树的先序序列和中序序列构造二叉树； （2）根据先序遍历二叉树； （3）根据中序遍历二叉树； （4）根据后序遍历二叉树。 测试数据包括如下错误数据： 先序：1234；中序：12345 先序：1234；中序：1245 先序：1234；中序：4231 2、（必做题）对于一棵二叉树，请实现： （1）计算二叉树的叶子数目； （2）计算二叉树的深度。 三、算法描述 （采用自然语言描述） 1、先构造一个二叉树的结构体，再构造createtree的函数实现数据的输入。在键盘上输入先序和中序序列。先判断先序和后序序列是否符合逻辑。若符合逻辑，则在先序、中序、后序函数将二叉树输出。 四、详细设计 （画出程序流程图） 五、程序代码 （给出必要注释） #define max 5 #define TEL 2*max+1 #include "stdio.h" #include "stdlib.h" #include "string.h" typedef char TElemType; typedef struct BiTNode{ TElemType data; //数据域 struct BiTNode *lchild, *rchild; //左右孩子指针域 } BiTNode, *BiTree; BiTNode root; BiTree rt=&root; int calculate(char c,char s[],int st) {char *p; p=s+st; while(*p!=c && *p!='\0') p++; return p-s; } void createtree(BiTree *t,int i1,int i2,int len,char preorder[],char pinorder[]) {int r,llen,rlen; if(len<=0) *t=NULL; else {*t=(BiTree)malloc(sizeof(BiTNode)); (*t)->data=preorder[i1]; r=calculate(preorder[i1],pinorder,i2); llen=r-i2; rlen=len-(llen+1); createtree(&(*t)->lchild,i1+1,i2,llen,preorder,pinorder); createtree(&(*t)->rchild,i1+llen+1,r+1,rlen,preorder,pinorder); } } void PostOrderTraverse(BiTree t) {if(t) {PostOrderTraverse(t->lchild); PostOrderTraverse(t->rchild); putchar(t->data); } } void PreOrderTraverse(BiTree t) {if(t) {putchar(t->data); 《用哈夫曼编码实现文件压缩》 实验报告 课程名称数据结构 实验学期2015至2016学年第一学期 学生所在系部计算机学院 年级2014专业班级物联B142班 学生姓名杨文铎学号201407054201 任课教师白磊 实验成绩 用哈夫曼编码实现文件压缩 1、了解文件的概念。 2、掌握线性表的插入、删除的算法。 3、掌握Huffman树的概念及构造方法。 4、掌握二叉树的存储结构及遍历算法。 5、利用Haffman树及Haffman编码，掌握实现文件压缩的一般原理。 微型计算机、Windows系列操作系统、Visual C++6.0软件 根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。 本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用S为的ascii码进行存储，根据他们在文件中出现的频率不同，我们利用Haffman算法使每个字符能以最短的二进制数字符进行存储，已达到节省存储空间，压缩文件的目的，解决了压缩需要采用的算法，程序的思路已然清晰: 1、统计需压缩文件中的每个字符出现的频率 2、将每个字符的出现频率作为叶子节点构建Haffman树，然后将树中结点引向 其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码 即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Haffman 编码，将每个字符用最短的二进制字符表示。 3、打开需压缩文件，再将需压缩文件中的每个ascii码对应的haffman编码按bit 单位输出。 4、文件压缩结束。 （1）构造haffman树的方法一haffman算法 构造haffman树步骤： I.根据给定的n个权值{w1，w2，w3…….wn}，构造n棵只有根结点的二叉 树，令起权值为wj。 II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。 III.在森林中删除这两棵树，同时将得到的二叉树加入森林中。 IV.重复上述两步，知道只含一棵树为止，这棵树即哈夫曼树。 对于haffman的创建算法，有以下几点说明： a）这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为 数据结构实验课程大纲 本大纲是针对计算机科学与技术专业本科对数据结构的基本要求而编写的。 一、目的与任务 数据结构是一门实践性很强的课程，每个学生必须完成一定数量的上机作业。通过上机作业，要求在数据结构的逻辑特性和存贮表示、基本数据结构的选择和应用、算法设计及其实现等方面加深对课程基本内容的理解。同时，在程序设计方法、程序设计风格及上机操作等基本技能和科学作风方面受到比较系统的、严格的训练。提高分析问题和用计算机解决实际问题的能力。为后续课程的学习以及为应用软件特别是非数值软件的开发打下良好的理论基础和实践基础。 二、课程内容 1.顺序表的表示和运算（0-2学时） 2.链表的表示和运算（2学时） 3.栈的应用（2-3学时） 4.队列的应用（2-3学时） 5.二叉树的基本操作和应用（2-6学时） 6.图及其应用（2-6学时） 7.排序（4-6学时） 8.查找（2-4学时） 三、基本要求 1.逐步理解和掌握程序设计和上机操作的基本方法和技能。 2.理解并实现各种基本数据结构的存贮表示、运算方法及其典型应用；学会根据实际问题的要求设计算法的 数据结构，并具有一定的比较和选用数据结构及算法的能力。 3.理解并实现常用的查找和排序的基本方法。 四、学时分配 五、实验内容 注：带*的内容以及练习与思考题，可根据实际学时、专业方向特点等具体要求，做相应调整或从略。 实验一、顺序表 实验目的： 熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作。 实验要求： 了解并熟悉顺序表的逻辑特性、存储表示方法和顺序表的基本操作的实现和应用。 实验内容： 编写程序实现下列的要求： (1) 设数据元素为整数，实现这样的线性表的顺序存储表示。 (2) 键盘输入10个数据元素，利用顺序表的基本操作，建立该表。 (3) 利用顺序表的基本操作，找出表中的最大的和最小的数据元素（用于比较的数据元素为整数）。 (4) * 若数据元素为学生成绩（含姓名、成绩等字段），重新编程，实现上面的要求。要求尽可能少地修改前面的程序来得到新程序。（这里用于比较的字段为分数） 练习及思考题： （1）不同类型的数据元素所对应的顺序表在类型定义和操作实现上有什么异同？ （2）顺序表的操作上有什么特点？ （3）不固定数据元素的个数，而通过特殊数据来标记输入数据的结束，实现这样的输入操作。 实验二、链表 实验目的： 熟悉链式表的逻辑特性、存储表示方法的特点和链式表的基本操作。 实验要求： 了解并熟悉链式表的逻辑特性、存储表示方法和链式表的基本操作的实现和应用。 实验内容： 编写程序实现下列的要求： (1) 设学生成绩表中的数据元素为学生成绩（含姓名、成绩字段），实现这样的线性表的链式存储表示。 (2) 键盘输入若干个数据元素（用特殊数据来标记输入数据的结束），利用链表的基本操作（前插或后插算法），建立学生成绩单链表。 (3) 键盘输入关键字值x，打印出表中所有关键字值<=x的结点数据。（用于比较的关键字字段为分数）。 (4) 输入关键字值x，删除表中所有关键字值<=x的结点。（用于比较的关键字字段为分数）。 (5) * 释放该链表（删除所有结点）。 (6) * 若要求建立的学生成绩单链表为有序表，重新编写算法和程序实现前面的要求（3）。（用于比较的字段为分数）。 练习及思考题： （1）不同类型的数据元素所对应的链式表在类型定义和操作实现上有什么异同？ （2）有头结点的链式表，有什么特点？ 2011~2012第一学期数据结构实验报告 班级：信管一班 学号：201051018 姓名：史孟晨 实验报告题目及要求 一、实验题目 设某班级有M（6）名学生，本学期共开设N（3）门课程，要求实现并修改如下程序（算法）。 1. 输入学生的学号、姓名和 N 门课程的成绩（输入提示和输出显示使用汉字系统）， 输出实验结果。（15分） 2. 计算每个学生本学期 N 门课程的总分，输出总分和N门课程成绩排在前 3 名学 生的学号、姓名和成绩。 3. 按学生总分和 N 门课程成绩关键字升序排列名次，总分相同者同名次。 二、实验要求 1．修改算法。将奇偶排序算法升序改为降序。（15分） 2．用选择排序、冒泡排序、插入排序分别替换奇偶排序算法,并将升序算法修改为降序算法；。（45分）） 3．编译、链接以上算法，按要求写出实验报告（25）。 4. 修改后算法的所有语句必须加下划线，没做修改语句保持按原样不动。 5．用A4纸打印输出实验报告。 三、实验报告说明 实验数据可自定义，每种排序算法数据要求均不重复。 (1) 实验题目：《N门课程学生成绩名次排序算法实现》； (2) 实验目的：掌握各种排序算法的基本思想、实验方法和验证算法的准确性； (3) 实验要求：对算法进行上机编译、链接、运行； (4) 实验环境（Windows XP-sp3,Visual c++)； (5) 实验算法（给出四种排序算法修改后的全部清单）； (6) 实验结果（四种排序算法模拟运行后的实验结果）； (7) 实验体会（文字说明本实验成功或不足之处）。 三、实验源程序（算法） Score.c #include "stdio.h" #include "string.h" #define M 6 #define N 3 struct student { char name[10]; int number; int score[N+1]; /*score[N]为总分,score[0]-score[2]为学科成绩*/ }stu[M]; void changesort(struct student a[],int n,int j) {int flag=1,i; struct student temp; while(flag) { flag=0; for(i=1;i 《数据结构与算法》课程实验内容与要求 一、课程简介 本课程着重讲述①线性结构、树型结构、图等典型数据结构的逻辑特点、存储结构及其相应的基本算法。②各种查找算法③典型内部排序算法。 二、实验的作用、地位和目的 数据结构是一门技术基础课，通过实验深刻理解各种逻辑结构、存储结构的特性，培养为实际问题分析其数据对象、基本操作，选择逻辑结构、存储结构灵活应用基本算法，设计出具有专业水准的应用程序的能力。 三、实验方式与要求 ①首先要求学生在课下完成问题分析、算法设计，基本完成程序设计。 ②实验时，每位学生使用一台微机，独立调试，完成程序。 ③程序调试好后，由指导教师检测运行结果，并要求学生回答相关的问题。教师评出检查成绩。 ④学生记录程序的输入数据，运行结果及源程序。 ⑤在一周内完成实验报告。 四、考核方式与实验报告要求 实验成绩由指导教师根据学生的实验完成情况、源程序质量、回答问题情况、实验报告质量、实验纪律等方面给分。 学生在实验后的一周内提交实验报告。实验报告按照首页附件中实验报告模版书写。实验报告中应包括如下内容： ?实验内容按任课教师下达的实验任务填写（具体实验题目和要求）； ?实验过程与实验结果应包括如下主要内容： 算法设计思路简介 算法描述：可以用自然语言、伪代码或流程图等方式 算法的实现和测试结果：包括算法运行时的输入、输出，实验中出现的问题及解决办法等 ?源程序清单与实验结果或其它说明可打印，并装订在实验报告首页之后。 ?实验报告雷同者，本次实验成绩为0分或雷同实验报告平分得分 五、实验的软硬件环境 硬件环境：PⅡ以上微型计算机 软件环境：Windows98/2000, VC++6.0或turbo C 六、实验内容安排 实验一线性表应用 实验时间：2016年3月14日1-4节（地点：7-215） 实验目的：理解线性表的逻辑特点；掌握顺序表、链表存储结构，以及线性表的基本操作，如插入、删除、查找，以及线性表合并等操作在顺序存储结构和链式存储结构上的实现算法，并能够在实际问题背景下的灵活运用线性表来解决问题，实现相应算法。 具体实验题目与要求：（任课教师根据实验大纲自己指定） 每位同学可从下面题目中选择1-2题实现： 1．一元稀疏多项式简单的计算器 1）问题描述：用线性表表示一元稀疏多项式，设计一个一元多项式运算器 2）要求: （1）采用单链表存储结构一元稀疏多项式 （2）输入并建立多项式 （3）输出多项式 （4）实现多项式加、减运算 2．单链表基本操作练习 1）问题描述：在主程序中提供下列菜单： 1…建立链表 2…连接链表 3…输出链表 0…结束 2）实验要求：算法中包含下列过程，分别完成相应的功能： CreateLinklist(): 从键盘输入数据，创建单链表 ContLinklist()：将前面建立的两个单链表首尾相连 OutputLinklist()：输出显示单链表 3．约瑟夫环问题 1）问题描述：有编号为1, 2…n 的n 个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始给定一个正整数m，从第一个人按顺时针方向自1开始报数，报到m者出列，不再参加报数，这时将出列者的密码作为m，从出列者顺时针方向的下一人开始重新自1开始报数。如此下去，直到所有人都出列。试设计算法，输出出列者的序列。 2）要求: 采用顺序和链式两种存储结构实现 实验报告格式及要求：按附件中实验报告模版书写。（具体要求见四） 精品文档 这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独立思考，深入研究，分析问题、解决问题的能力。3、通过实际编译系统的分析设计、编程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在，才发现只要认真做，没有什么不可能。 编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候完全以一个用户的身份来用对你的用户界面做一些建议，正所谓当局者迷旁观者清，把各个注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意指针的初始化不管它怎么用以免不必要麻烦。 通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不清楚的东西也做了一定的了解，也形成了一定的个人做事风格。 通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过用for的多重循环，舍弃多余的循环，提高了程序的运行效率。在编写这个程序的过程中，我复习了之前学的基本语法，哈弗曼树最小路径的求取，哈弗曼编码及译码的应用范围，程序结构算法等一系列的问题它使我对数据结构改变了看法。在这次设计过程中，体现出自己单独设计模具的能力以及综合运用知识的能力，体会了学以致用、突出自己劳动成果的喜悦心情，也从中发现自己平时学习的不足和薄弱环节，从而加以弥补。 精品文档 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template数据结构实验报告格式
数据结构实验报告
《数据结构与算法设计》实验大纲及实验内容详细要求
数据结构实验总结报告
《数据结构设计》内容要求要点
数据结构实验报告全集
数据结构实验总结报告
数据结构课程设计题目及要求
数据结构实验报告模板
数据结构实验报告
数据结构实验报告
《数据结构》实验指导书
数据结构实验报告及心得体会
《数据结构与算法》上机实验要求
最新数据结构实训总结
数据结构实验报告图实验
相关主题
文本预览