第 1 章 绪论
一、单选题
1、在数据结构中，从逻辑上可以把数据结构分成
A、动态结构和静态结构
B、紧凑结构和非紧凑结构 D、内部结构和外部结构
C、线性结构和非线性结构 2、算法分析的两个主要方面是
A、空间复杂性和时间复杂性 C、可读性和文档性
B、正确性和简明性
D、数据复杂性和程序复杂性
3、数据的不可分割的最小单位是
A、结点
B、数据元素
C、数据项
D、数据对象
4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为
A、规则
B、集合
C、结构
D、运算
5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是
A、问题的规模
B、机器代码质量的优劣 D、语句的执行次数
C、机器执行速度 二、判断题
1、数据结构是带有结构的数据元素的集合。 2、程序越短，运行的时间就越少。 3、处理同一问题的算法是唯一的。
4、一个完整算法可以没有输入，但必须有输出。 三、填空题
1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 2、______________结构的数据元素之间存在一对多的关系。
3、数据结构的形式化定义为 (D，S)，其中 D 是______________的有限集，S 是 D 上关系的有限集。
4、数据结构在计算机中的______________称为存储结构。
5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此
- 6 -
得到两种不同的存储结构是______________存储结构和______________存储结构。 6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。
7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。 四、解答题
1、设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： ⑴ i=1；
k=0； while (i<=n-1) {
@ k+=10*i； i++； } ⑵ i=1；
k=0； do {
@ k+=10*i； i++； } while (i<=n-1)； ⑶ i=1；
k=0； while (i<=n-1) { i++； @ k+=10*i； } ⑷ k=0；
for (i=1；i<=n；i++) {
for (j=i；j<=n；j++) @ k++；
- 7 -
}
2、阅读以下算法： void fun(int n) {
int i，j，k，s，x； for (s=0，i=0；i j=n； x=0； while (i printf(\，x=%d\\n\，s，x)； } ⑴分析算法中语句“s++；”的执行次数； ⑵分析算法中语句“x+=2；”的执行次数； ⑶分析算法的时间复杂度。 五、算法设计题 编程实现课本例1-7所描述的抽象数据类型Triplet，并完成以下功能，要求有菜单提示： ⑴初始化三元组为 (100，200，300)； ⑵获取第二个元素值并输出； ⑶置第三个元素值为 150； ⑷获取第三个元素值并输出； ⑸获取最大元素值并输出； ⑹获取最小元素值并输出； ⑺撤销三元组。 - 8 - 第2章 线性表 一、单选题 1．线性表是( ) 。 (A) 一个有限序列，可以为空 (B) 一个有限序列，不能为空 (C) 一个无限序列，可以为空 (D) 一个无序序列，不能为空 2．线性表采用链式存储时，其地址( ) 。 (A) 必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 3．与顺序表相比，用链表实现线性表的优点是（ ）。 (A)便于随机存取 (B)花费的存储空间较顺序存储少 (C)便于插入和删除 (D)数据元素的物理顺序与逻辑顺序相同 4．线性表的静态链表结构与顺序存储结构相比优点是( )。 (A)所有的操作算法实现简单 (B)便于随机存取 (C)便于插入和删除 (D)便于利用零散的存储器空间 5．循环链表的主要优点是( ) 。 (A)不在需要头指针了 (B)已知某个结点的位置后，能够容易找到他的直接前趋 (C)在进行插入、删除运算时，能更好的保证链表不断开 (D)从表中的任意结点出发都能扫描到整个链表 6．下面关于线性表的叙述错误的是( )。 (A) 线性表采用顺序存储，必须占用一片地址连续的单元 (B) 线性表采用顺序存储，便于进行插入和删除操作 (C) 线性表采用链式存储，不必占用一片地址连续的单元 (D) 线性表采用链式存储，不便于进行插入和删除操作； 7．假设双链表结点的类型如下： typedef struct linknode { int data ; //数据域 struct linknode *llink;//指向前趋结点的指针域 struct linknode *rlink;//指向后继结点的指针域 - 9 - } bnode 现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是( )。 (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->rlink;q->rlink=p;p->link->rlink=q;p->llink=q (D) 以上都不对 8. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是： （A）110 （B）108 （C）100 （D）120 9. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是( ) （A） 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B） 在第i个结点后插入一个新结点（1≤i≤n） （C） 删除第i个结点（1≤i≤n） （D） 将n个结点从小到大排序 10. 链式存储结构所占存储空间（ ） （A） 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 （B） 只有一部分，存放结点值 （C） 只有一部分，存储表示结点间关系的指针 （D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数 11. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 (A) 单链表 (B) 仅有头指针的单循环链表 (C) 双链表 (D) 仅有尾指针的单循环链表 12. 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ） （A）n （B）2n-1 （C）2n （D）n-1 13． 线性表L在以下哪种情况下适用于使用链式结构实现（ ） （A）需经常修改L中的结点值 （B）需不断对L进行删除插入 （C）L中含有大量的结点 （D）L中结点结构复杂 14．在一个单链表L中，若要删除由指针q所指向结点的后继结点，则执行（ ）。 - 10 -