1 第1章 选择题： 1.1 数据结构在计算机内存中的表示是指： A．数据的存储结构 B.数据结构 C．数据的逻辑结构 D.数据元素之间的关系 1.2 数据的逻辑结构是指： A. 数据所占的存储空间量 B．各数据元素之间的逻辑关系 C. 数据在计算机中顺序或链接的存储方式 D. 存储在内存或外存中的数据 1.3 在下列的叙述中，正确的是： A．数据的逻辑结构是指数据的各数据项之间的逻辑关系。 B．数据的物理结构是指数据在计算机内的实际存储形式。 C．在顺序存储结构中，数据元素之间的关系是显示体现的。 D．链接存储结构是通过结点的存储位置相邻来体现数据元素之间的关系。 填空题： 1.4 数据结构主要研究 数据的逻辑结构 ， 数据的存储结构 ， 数据的运算 三个方面的内容。 1.5 链接存储的特点是通过附加 指针域 来表示数据元素之间的逻辑关系。 1.6 数据结构中讨论的三种经典结构包括： 线性表 ， 树 ， 图 。 1.7 数据结构中常用的存储方法有： 顺序 ， 链接 ， 索引 ， 散列 。 1.8 顺序存储结构可以通过位置 隐含 表示关系，链接存储结构通过附加指针来 显示 表示关系。 1.9 算法的特性包括 有穷性 ， 确定性 ， 可行性 ，输入和输出。 1.10 算法性能分析的两个主要定量评价指标是 时间复杂度 和 空间复杂度 。 简答题： 1.11 数据结构研究的三方面内容之间有什么联系和区别？ 数据结构研究的三方面内容包括: 数据的逻辑结构、存储结构和运算。数据的逻辑结构是数学模型，存储结构是指逻辑结构到存储区域的映射，运算是定义在逻辑结构上，实现在存储结构上。 1.12 简述数据结构中讨论的三种经典结构的逻辑特征是什么？ 三种经典结构：线性表、树和图。逻辑特征分别为： （1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。 （2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。 （3）图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。 1.13 简述各种常用存储方法的基本思想。 各种方法的基本思想： 顺序存储：逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里。 链接存储：通过附加指针域表示数据元素之间的关系。 索引存储：除了存储数据元素，还要建立附加的索引表来标识数据元素的地址。 散列存储：根据关键字直接计算出该结点的存储地址，通常称为关键字－地址转换法。 2

第2章 选择题： 2.1 线性表L=（a1，a2，…，an），下列说法正确的是： A. 每个元素都有一个直接前驱和一个直接后继。 B. 线性表中至少有一个元素。 C. 表中元素的排列顺序必须是由小到大或由大到小。 D. 除第一个和最后一个元素外，其余每个元素都有且仅有一个直接前驱和一个直接后继。 2.2 下面关于线性表的叙述中，错误的是： A．线性表若采用顺序存储，必须占用一片连续的存储单元 B．线性表若采用顺序存储，便于进行插入和删除操作 C．线性表若采用链接存储，不必占用一片连续的存储单元 D．线性表若采用链接存储，便于插入和删除操作 2.3 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为： A .n-i+1 B .n-i C .i D .i-1 2.4 删除长度为n的顺序表中的第i(1≤i≤n)个位置上的元素，元素的移动次数为： A. n-i+1 B. n-i C. i D. i-1 2.5 已知一个带头结点单链表L，在表头元素前插入新结点 *s的语句为： A. L=s; s->next=L; B. s->next=L->next; L->next=s; C. s=L; s->next=L; D. s->next=L; s=L; 2.6 已知一个不带头结点单链表的头指针为L，则在表头元素之前插入一个新结点*s的语句为： A. L=s; s->next=L; B. s->next=L; L=s; C. s=L; s->next=L; D. s->next=L; s=L; 2.7 已知单链表上一结点的指针为p，则在该结点之后插入新结点*s的正确操作语句为： A． p->next=s; s->next=p->next; B． s->next=p->next; p->next=s; C． p->next=s; p->next=s->next; D． p->next=s->next; p->next=s; 2.8 已知单链表上一结点的指针为p，则删除该结点后继的正确操作语句是： A． s= p->next; p=p->next; free(s); B． p=p->next; free(p); C． s= p->next; p->next=s->next; free(s); D． p=p->next; free(p->next); 2.9 设一个链表最常用的操作是在表尾插入结点和在表头删除结点，则选用下列哪种存储结构效率最高？ A. 单链表 B. 双链表 C. 单循环链表 D. 带尾指针的单循环链表 2.10 线性表的链接存储结构是一种（ ）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 2.11 链表不具备的特点是： A. 插入删除不需要移动元素 B. 不必事先估计存储空间 C. 可随机访问任一结点 D. 所需空间与其长度成正比 填空题： 2.1 在单链表L中，指针p所指结点有后继结点的条件是 p->next!=NULL 。 2.2 判断带头结点的单链表L为空的条件 L->next==NULL。 2.12 顺序表和链表中能实现随机存取的是 顺序表 ，插入、删除操作效率高的是 链表 。 2.13 对于一个具有n个结点的单链表，已知一个结点的指针p，在其后插入一个新结点的时间复杂度为 O（1） ；若已知一个结点的值为x，在其后插入一个新结点的时间复杂度为 O（n） 。

2.14 顺序表的存储密度 大 ，链表的存储密度 小 。 3

简答题： 2.15 比较顺序表和链表这两种线性表不同存储结构的特点。

2.16 简述头结点的作用。 头结点的作用是使得单链表在表头位置的插、删操作同中间位置的插、删操作完全相同。即使“空表”与“非空表”的操作统一，也使“表头结点”与其他位置结点的操作完全一致，无须特殊处理。 2.17 写出单链表存储结构的C语言描述。 typedef int DataType; typedef struct Node { DataType data; struct Node *next; }LinkList;

完善程序题： 2.18 设计一个算法，其功能为：向一个带头结点的有序单链表（从小到大有序）中插入一个元素x，使插入后链表仍然有序。请将代码补充完整。 typedef int DataType; typedef struct Node { DataType data; ; /*定义指向该结构类型的指针变量next*/ }Linklist; void insert(Linklist *L,DataType x) { Linklist *s,*p=L; while(p->next && p->next->data; /*p指针后移一步*/ ; /*申请一个新结点空间，将其地址赋给变量s*/ s->data=x; ; ; /*将*s结点插入到*p结点的后面*/ } struct Node * next; p=p->next; s=(LinkList *)malloc(sizeof(LinkList)); s->next=p->next; p->next=s;

2.19 设计一个函数功能为：在带头结点的单链表中删除值最小的元素。请将代码补充完整。 typedef int DataType; typedef Node /*定义结构体类型*/ { DataType data; struct Node * next; }LinkList;

顺序表 存储密度大 存储空间连续 静态分配 随机存取 插、删效率低

链表 存储密度大 存储空间可不连续 动态分配 顺序存取 插、删效率高 4 void deleteMin(LinkList *L) { LinkList *p=L->next,*q; /*首先查找值最小的元素，指针q指向最小元素结点*/ q=p; while(p) { if( p->data < q->data) q=p; ; /* p指针后移一步，比较单链表中的每一个结点*/ } if(!q) return; /*不存在最小结点（空表）时，直接退出*/ p=L; /*若存在最小结点，则先找到最小结点的前驱，即*q的前驱*/ while( ) p=p->next; ; /*从单链表中删除最小元素结点（指针q所指结点）*/ ; /* 释放指针q所指结点的空间*/ }

struct p=p->next; p->next!=q p->next=q->next; free(q); 算法设计题： 2.20 已知长度为n的线性表A中的元素是整数，写算法求线性表中值大于item的元素个数。分两种情况编写函数：（1）线性表采用顺序存储；（2）线性表采用单链表存储。 （1）线性表采用顺序存储 #define MAX 1024 typedef int DataType; typedef struct { DataType data[MAX]; int last; } SeqList; int LocateElem (SeqList *L, DataType item) { int i,j=0; for(i=0;i<=L->last ;i++) if( L->data[i] >item ) j++; return j; } （2）线性表采用单链表存储 typedef int DataType; typedef struct Node { DataType data; struct Node *next; }LinkList; int locateElem(LinkList *L, DataType item )