第一章 绪论
一、填空题
1． 数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。
_________是数据的基本单位；___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的，而是彼此之间存在着某种联系，将这种数据间的联系称为________。 2． 数据结构进行形式化定义时，可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集
合R所构成的二元组：DS=（D，R）。
3． 已知某数据结构的二元组形式表示为：A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，
r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}。则此数据结构属于_____________结构。
4． 一个算法的时间复杂度通常用问题规模大小的函数来表示，当一个算法的时间复杂度与问题规模n大小无
关时，则表示为__________；成正比关系时，则表示为___________；成对数关系时，则表示为___________；成平方关系时，则表示为__________。
5． 数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型，其中树型结构和图型结构合称
为_____________；数据结构的存储结构主要包括____________和____________两种类型。
6． 线性结构的特点是：第一个结点_______前驱结点，其余结点有且仅有_______个前驱结点；最后一个结点
_______后继结点，其余每个结点有且仅有_______个后继结点。
7． 树型结构的特点是：根结点没有________结点，其余每个结点有且仅有________个前驱结点；叶子结点
_________后继结点，其余结点可以有_________个后继结点。
8． 图型结构的特点是：每个结点可以有_________个前驱结点和后继结点。 9． 程序段for（i=1，s=0；s 10． 常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)、线性对数阶O(nlog2n)、 立方阶O(n3)、指数阶O(2n)等等，这些数量阶之间的大小关系为__________________________。 二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。 1. A=（K，R），其中：K={a，b，c，d，e，f，g，h}，R={r}，r={， 57>，<57，64>，<64，75>，<75，82>}；r2={<48，25>，<48，64>，<64，57>，<64，82>，<25，36>，<25，75>}。 5. E=（K，R），其中：K={1，2，3，4，5，6，7}，R={r}，r={<1，2>，<2，1>，<1，4>，<4，1>，<2， 3>，<3，2>，<3，4>，<4，3>，<1，3>，<3，1>}。 三、指出下列各函数的功能并求出其时间复杂度。 1. void prime(int n) { int i; for(i=2;i<=sqrt(n);i++) if (n %i==0) break; if (i>sqrt(n)) printf(“yes”); else printf(“no”); } 2. long sum1(int n) { 1 long sum,w,i; for(sum=0,i=1;i<=n;i++){ w=1; for(j=1;j<=i;j++) w=w×i; sum=sum+w; } return(sum); } 3. long sum2(int n) { long sum,w,i; for(sum=0, w=1,i=1;i<=n;i++){ w=w×i; sum=sum+w;} return(sum); } 4. void sort(int r[ ],int n) { int i,j; for(i=1; i if(r[j]>r[j+1]) {temp=r[j];r[j]=r[j+1];r[j+1]=temp;} } 2 第一章参考答案 一、填空题 1． 数据元素，数据项，结构 2． 数据，关系 3． 树型 4． O(1)，O(n)，O(log2n)，O(n2) 5． 线性结构，非线性结构，顺序结构，链式结构 6． 无，一，无，一 7． 前驱，一，无，任意 8． 任意 9． O(n1/2) 分析：设程序段中的循环体执行k次，则有不等式?i?n??i成立，解此不等式得到不等式 i?1i?1kk?12n?1/4?3/2?k?2n?1/4?1/2，因此f(n)?k?O(n)。 10． O(1) 二、分析下列用二元组形式表示的数据结构，指出他们分别属于何种类型的数据结构。 1． 线性结构 2． 树型结构 3． 图型结构 4． 图型结构 分析：数据结构D中的关系集合R有两个关系r1和r2。如果只考虑关系r1，则为线性结构；如果只考虑关系r2，则为树型结构；如果把关系r1和r2联合起来考虑，则为图型结构。 5． 图型结构 分析：若用图形来表示则可以看出r是E上的对称关系，为了简化起见，我们通常把 三、指出下列各函数的功能并求出其时间复杂度。 1． 函数的功能是判断n是否是一个素数，其时间复杂度为O(n1/2)。 分析：函数prime中出现的库函数sqrt为平方根函数，因此f(n)?n?1?O(n)。 2． 函数的计算?i!的值，其时间复杂度为O(n2)。 i?1nn3． 函数的计算?i!的值，其时间复杂度为O(n)。 i?14． 函数的功能是对数组r中的n个元素进行冒泡排序，其时间复杂度为O(n2)。 分析：f(n)??(n?i)?n(n?1)/2?O(n2)。 i?1n?13 第二章 线性表 一、填空题 1． 设长度为n的顺序线性表在任何位置上插入或删除操作都是等概率的，则插入一个元素时平均需要移动 _______个元素，删除一个元素时平均需要移动______个元素。 2． 在顺序线性表中插入一个元素时，插入位置开始后的所有元素均需要________移动一个位置。 3． 在顺序线性表中删除一个元素时，被删除元素后的所有元素均需要__________移动一个位置。 4． 线性表的链式存储结构中，元素之间的线性关系是通过结点中的________来实现的。 5． 线性表的顺序存储结构中逻辑上相邻的元素，物理位置__________相邻；线性表的链式存储结构中逻辑上 相邻的元素，物理位置____________相邻。 6． 已知单链表的长度为n，则在给定值为x的结点后插入一个新结点的时间复杂度为__________。 7． 已知单链表的长度为n，则删除给定值为x的结点的时间复杂度为__________。 8． 在单链表中设置头结点的作用是________________________________。 9． 双向链表中每个结点含有两个指针域，其中一个指针域指向_______结点，另一个指针域指向______结点。 10． 在长度为n的线性表中顺序查找某个结点值为X的时间复杂度为______________。 二、选择题 1．在长度为n的顺序线性表中删除第i个元素(1<=i<=n)，则需要向前移动的元素个数为（ ）。 ⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i 2．建立一个长度为n的单链表的时间复杂度为（ ）。 ⑴ O(n) ⑵ O(1) ⑶ O(n2) ⑷ ((log2n) 3．设指针p指向单链表中的结点A，结点A的后继结点是结点B，则删除结点B的操作为（ ）。 ⑴ p->next=p ⑵ p=p->next ⑶ p=p->next->next ⑷ p->next=p->next->next 4．设指针p指向单链表中结点A，指针q指向单链表中结点A的前驱结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作为（ ）。 ⑴ s->next=p->next； p->next=s； ⑵ q->next=s； s->next=p； ⑶ p->next=s->next； s->next=p； ⑷ p->next=s； s->next=q； 5．在长度为n的顺序线性表中的第i个元素(1<=i<=n+1)之前插入一个新元素时，则需要向后移动的元素个数为（ ）。 ⑴ n-i ⑵ n+1-i ⑶ n-1-i ⑷ i 6．在长度为n的有序线性表中插入一个元素后仍然保持有序的平均时间复杂度为（ ）。 ⑴ O(log2n) ⑵ O(1) ⑶ O(n2) ⑷ O(n) 7．设指针p指向双向链表中的结点A，指针s指向被插入的结点X，则在结点A之后插入结点X的操作为（ ）。 ⑴ p->rlink=s； s->llink=p； p->rlink->llink=s； s->rlink=p->rlink； ⑵ s->llink=p； s->rlink=p->rlink； p->rlink=s； p->rlink->llink=s； ⑶ p->rlink=s； p->rlink->llink=s； s->llink=p； s->rlink->p->rlink； ⑷ s->llink=p； s->rlink=p->rlink； p->rlink->llink=s； p->rlink=s； 8．指针p指向双向链表中的结点A，则删除结点A的操作是（ ）。 ⑴ p->llink->rlink=p->rlink； p->rlink->llink=p->llink； ⑵ p->rlink->llink=p->rlink； p->llink->llink=p->llink； ⑶ p->llink->rlink=p->llink； p->rlink->llink=p->rlink； ⑷ p->rlink->rlink=p->rlink； p->rlink->rlink=p->rlink； 9．线性表采用链式存储结构时，要求存储单元的地址（ ）。 ⑴ 必须是连续的 ⑵ 部分地址必须是连续的 ⑶ 一定是不连续的 ⑷ 连续不连续都可以 10．设head为单链表的头指针，则不带头结点的单链表为空的判定条件是（ ）。 4 ⑴ head==NULL ⑵ head->next==NULL ⑶ head->next==head ⑷ head!=NULL 11．设head为单链表的头指针，则带头结点的单链表为空的判定条件是（ ）。 ⑴ head==NULL ⑵ head->next==NULL ⑶ head->next==head ⑷ head!=NULL 12．设head和tail分别为单向循环链表的头指针和尾指针，则下列等式成立的是（ ）。 ⑴ head==tail ⑵ head->next==tail ⑶ tail->next==head ⑷ head->next==tail->next 三、算法设计题 顺序存储结构的类型定义：typedef struct {int a[m]; int n; } sqlist; 链式存储结构的类型定义：typedef struct node {int data; struct node *next;} lklist; 1. 建立一个有n个结点的单链表，要求从尾部进行插入。 2. 建立一个有n个结点的单链表，要求从头部进行插入。 3. 用顺序存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，??，an）逆置为(an， an-1，??，a1)。 4. 用链式存储结构实现线性表就地逆置算法，即在原表的存储空间内将线性表（a1，a2，??，an）逆置为(an， an-1，??，a1)。 5. 已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用顺序存储结构表示。 6. 已知集合A、B，求集合C=A∩B算法，要求集合A、B和C均用采用链式存储结构表示。 7. 设计在带有头结点的单向链表中删除值为X的结点算法。 5