《数据结构》习题集：第2章_线性表
第2章线性表
一、选择题
1.表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均
次数为（E ），删除一个元素需要移动的元素个数为（A ）。
A. (N-1)/2
B. N
C. N+1
D. N-1
E. N/2
F. (N+1)/2
G. (N-2)/2
2.线性表是具有N 个（C ）的有限序列。
A、表元素
B、字符
C、数据元素
D、数据项
E、信息
3.“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（B ）。
A、正确的
B、错误的
C、不一定，与具体结构有关。
4.线性表采用链式存储结构时，要求内存中可用存储单元的地址（D ）。
A、必须是连续的
B、部分地址必须是连续的
C、一定是不连续的
D、连续或不连续都可以。
5.带头结点的单链表为空的判定条件是（B ）。
A、head==NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
6.不带头结点的单链表head 为空的判定条件是（A ）。
A、head==NULL
B、head->next==NULL
C、head->next==head
D、head!=NULL
7.非空的循环单链表head 的尾结点P 满足（ C ）。
A、P->NEXT=NULL
B、p=NULL
C、p->next==head
D、p==head
8.在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（B ）。
A、O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
9.在一个单链表中，若删除P 所指结点的后继结点，则执行（ A ）。
A、p->next=p->next->next
B、p=p->next;p->next=p->next->next
C、p->next=p->next;
D、p=p->next->next;
10.在一个单链表中，若在Ｐ所指结点之后插入Ｓ所指结点，则执行（B ）。
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;
11.在一个单链表中，已知q 是p 的前趋结点，若q 和p 之间插入结点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;
12.假设双链表结点的类型如下：
typedef struct linknode{
int data; ／／数据域
struct linknode *llink; ／／指向前趋结点的指针域
struct linknode *rlink; ／／指向后继结点的指针域
}bnode
现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（D ）。
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->llink->rlink=q;p->llink=q;
D、以上都不对
13.如上题结点结构，如在此非空循环双向链表的结点p 之后插入结点s 的操作序列是（D ）。
A、p->rlink=s;s->llink=p;p->rlink->llink=s;s->rlink=p->rlink;
B、p->rlink->s;p->rlink->llink=s;s->llink=p;s->rlink=p->rlink;
C、s->llink=p;s->rlink=p->rlink;p->rlink=s;p->rlink->llink=s;
D、s->llink=p;s->rlink=p->rlink;p->rlink->llink=s;p->rlink=s;
14.在一个长度为n 的单链表上，设有头和尾两个指针，执行（B ）操作与链表的长度有关。
A、删除单链表中的第一个元素
B、删除单链表中最后一个元素
C、在单链表第一个元素前插入一个新元素
D、在单链表最后一个元素后插入一个新元素
15.线性结构中的一个结点代表一个（A ）
A、数据元素
B、数据项
C、数据
D、数据结构
16.非空线性表L=(a1,a2,…,ai,…,an)，下列说法正确的是（D ）
A、每个元素都有一个直接前驱和直接后继
B、线性表中至少要有一个元素
C、表中诸元素的排列顺序必须是由小到大或由大到小的
D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继
17.顺序表是线性表的（B ）
A、链式存储结构
B、顺序存储结构
C、索引存储结构
D、散列存储结构
18.对于顺序表，以下说法错误的是（A ）
A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
19.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B ）为标准操作。
A、插入操作
B、结点移动
C、算术表达式
D、删除操作
20.对于顺序表的优缺点，以下说法错误的是（ C ）
A、无需为表示结点间的逻辑关系而增加额外的存储空间
B、可以方便地随机存取表中的任一结点
C、插入和删除运算较方便
D、由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
21.若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（A ）存储方式最节省时间。
A、顺序表
B、单链表
C、双链表
D、单循环链表
22.循环链表主要优点是（D ）
A、不再需要头指针了
B、已知某个结点的位置后，能够容易找到它的直接前趋
C、在进行插入、删除运算时，能更好地保证链表不断开
D、从表中任一结点出发都能扫描到整个链表
23.在线性表的下列存储结构中，读取元素花费时间最少的是（D ）
A、单链表
B、双链表
C、循环链表
D、顺序表
二、填空题
1.在线性结构中，第一个结点（没有）前趋结点，其余每个结点有且只有（ 1 ）个前趋结点。
2.在顺序表中插入或删除一个元素，需要平均移动（表中一半）元素，具体移动的元素个数与（该元素的位置）
有关。
3.已知Ｌ是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：
（１）表首插入Ｓ结点的语句序列是（FC ）。
（２）表尾插入Ｓ结点的语句序列是（ BIAG ）。
Ａ、Ｐ->next=S;
Ｂ、P=L;
Ｃ、L=S;
Ｄ、P->next=S->next;
Ｅ、S->next=P->next;
Ｆ、S->next=L;
Ｇ、S->next=NULL;
Ｈ、while(P->next!=Q)p=p->next;
Ｉ、while(P->next!=NULL)P=P->next;
4.已知L 是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。
（1）删除首元结点的语句序列是（ HGBJ ）,
（2）删除尾元结点的语句序列是（HFDBJ ）
A、P=P->next;
B、P->next=P->next->next;
C、while(P!=NULL)p=p->next;
D、while(Q->next!=NULL){P=Q;Q=Q->next;}
E、while(P->next!=Q)P=P->next;
F、Q=P;
G、Q=P->next;
H、P=L;
I、L=L->next;
J、free(Q);
5.已知L 是带表头结点的非空链表，且P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合
适的语句序列。
（1）删除P 结点的直接后继结点的语句序列是（FAI ）,
（2）删除P 结点的直接前趋结点的语句序列是（ EGDFAI ）
A、P->next=P->next->next;
B、P=P->Pnext->next;
C、while(P->next!=Q)P=P->next;
D、while(P->next->next!=Q)P=P->next;
E、Q=P;
F、Q=P->next;
G、P=L;
H、L=L->next; I、free(Q);
6.已知结点编号，在各结点查找概率相等的情况下，从n 个结点的单链表中查找一个结点，平均要访问（ n/2 ）
个结点，从n 个结点的双链表中查找一个结点，平均要访问（n/4 ）个结点。
7.对于一个具有n 个结点的单链表，在已知p 所指结点后插入一个新结点的时间复杂度是（O(1) ）；在值域
为给定值的结点后插入一个新结点的时间复杂度是（ O（n））。
8.单链表是（线性表）的链接存储表示。
9.单链表中设置头结点的作用是（插入和删除首元素时不必进行特殊处理）。
10.在单链表中，除首元结点外，任一结点的存储位置由（其直接前趋结点的链域）指示。
11.在非空双向循环链表中，在结点q 的前面插入结点p 的过程如下：
p->prior=q->prior;
q->prior->next=p;
p->next=q;
( q->prior=p;);
12.在双向链表中，每个结点有两个指针域，一个指向（前趋结点），另一个指向（后继结点）。
13.顺序表中逻辑上相邻的元素的物理位置（必定）相邻。单链表中逻辑上相邻的元素的物理位置（不定）
相邻。
14.为了便于讨论，有时将含n(n≥0)个结点的线性结构表示成(a1，a2,…,a n)，其中每个a i 代表一个_结点_____。a1 称
为_第一个_____结点，a n 称为__最后一个____结点，i 称为a i 在线性表中的_位置_______。对任意一对相邻结点a i、a i┼1(1≤i 15.线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接__前驱____外，其他结点有且仅有一个 直接_前驱_____；除终端结点没有直接__后继____外，其它结点有且仅有一个直接_后继_____. 16.所有结点按1 对1 的邻接关系构成的整体就是_线性_____结构。 17.线性表的逻辑结构是_线性_____结构。其所含结点的个数称为线性表的__长度________。 18.在单链表中，指针p 所指结点为最后一个结点的条件是_p->next=NULL__________。 三、判断题 1. 顺序存储的线性表可以随机存取。V 2. 顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。X 3. 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。V 4. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。X 5. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。V 6. 在单链表中，可以从头结点进行查找任何一个元素。V 7. 线性表的链式存储结构优于顺序存储结构。X 8. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。V 9. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。X 10. 顺序存储方式只能用于存储线性结构。X 四、简答题 1.若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？ 宜采用链式存储结构，因为它使线性表的插入和删除操作的时间复杂度为O（1），而顺序存储结构的为O（n）2.描述概念：头指针、头结点、首元结点的区别？ 首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存线性表的数据元素，其作用是为了对链表进行操作时，可以对空表非空表的情况以及对首元结点进行统一的处理。头指针是指向链表第一个结点（头结点或首元结点）的指针。 若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用 3.设A 是一个线性表（a1a2…an），采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的 元素个数为多少？若元素插在ai 与ai+1 之间（0<=I<=n-1）的概率为2(n-i)/(n(n+1))，则平均每插入一个元素所要移动的元素个数又是多少？ 4.为什么在单循环链表中设置尾指针比设置头指针更好？ 解答：单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点，但设置尾指针时，若在表尾进行插入或删除操作时可在O(1)时间内完成，同样在表头进行插入或删除操作时也可在O(1)时间内完成。 但设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为O(n) 5.双链表和单循环链表中，若仅知道指针p 指向某个结点，不知道头指针，能否将结点*p 从相应的链表中删除？ 若可以，其时间复杂度各为多少？ 解答：能删除。双链表上删除p 所指向的结点的时间复杂度为O(1)，单循环链表上删除p 所指向的结点的时间复杂度为O(n)。 6.下列算法的功能是什么？ LinkedList test1(LinkedList L) { //L 是无头结点的单链表 ListNode *q,*p; if(L&&L->next) { q=L ; L=L->next; p=L; while(p->next) p=p->next; p->next=q; q->next=NULL; } return L; } 解答：如果长度大于1，则将首元结点删除并插入到表尾 7.如果有n 个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。 在此情况下，应选择哪一种存储结构。为什么？ 解答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配存储单元，不能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间，因此适用于动态变化表长的线性表。 8.若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存 储结构。为什么？ 解答：应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为O(1) 9.设有多项式a(x)=9+8x+9x4+5x10 b(x)=-2x+22x7-5x10 （1）用单链表给出a(x)、b(x)的存储表示； （2）设c (x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。 五、设计题 1.将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占 用其它的存储空间。表中不允许有重复的数据。 2.将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另 外占用其它的存储空间。表中允许有重复的数据。 3.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A链表中。 4.已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在 A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 5.设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零 的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。 6.设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 7.设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。 8.设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数， 其值可以和表中的元素相同，也可以不同）。 9.已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换 p所指向的结点和它的前缀结点的顺序。 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。 10.已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法 删除线性表中所有值为item的数据元素。 [算法讨论] 因元素只扫描一趟，算法时间复杂度为O（n）。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。 （1）将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb){ if(pa->data else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素，删除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q;} } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点} （2）将两个非递减的有序链表合并为一个非递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。 void union(LinkList& La, LinkList& Lb, LinkList& Lc, ) { pa = La->next; pb = Lb->next; // 初始化 Lc=pc=La; //用La的头结点作为Lc的头结点 Lc->next = NULL; while ( pa || pb ) { if ( !pa ) { q = pb; pb = pb->next; } else if ( !pb ) { q = pa; pa = pa->next; } else if (pa->data <= pb->data ) { q = pa; pa = pa->next; } else { q = pb; pb = pb->next; } q->next = Lc->next; Lc->next = q; // 插入 } delete Lb; //释放Lb的头结点} （3）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出A与B的交集，并存放于A 链表中。 void Mix(LinkList& La, LinkList& Lb, LinkList& Lc, ) { pa=la->next;pb=lb->next;∥设工作指针pa和pb； Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa&&pb) if(pa->data==pb->data)∥交集并入结果表中。 { pc->next=pa;pc=pa;pa=pa->next; u=pb;pb=pb->next; delete u;} else if(pa->data else {u=pb; pb=pb->next; delete u;} while(pa){ u=pa; pa=pa->next; delete u;}∥ 释放结点空间 while(pb) {u=pb; pb=pb->next; delete u;}∥释放结点空间 pc->next=null;∥置链表尾标记。 delete Lb; ∥注：本算法中也可对B表不作释放空间的处理 （4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即 仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 void Difference（LinkedList A，B，*n） ∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0 {p=A->next；∥p和q分别是链表A和B的工作指针。 q=B->next； pre=A；∥pre为A中p所指结点的前驱结点的指针。 while（p!=null && q!=null） if（p->data else if（p->data>q->data）q=q->next；∥B链表中当前结点指针后移。 else {pre->next=p->next；∥处理A，B中元素值相同的结点，应删除。 u=p； p=p->next； delete u；} ∥删除结点 （5）设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点（链表A的元素类型为整型，要求B、C表利用A表的结点）。 （6）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一个结点中数据具有最大值 p=L->next->next; while(p != NULL ){//如果下一个结点存在 if(p->data > pmax->data) pmax=p; p=p->next; } return pmax->data; （7）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。 void inverse(LinkList &L) { // 逆置带头结点的单链表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后继 p->next=L->next; L->next=p; // *p插入在头结点之后 p = q; } } （8）设计一个算法，删除递增有序链表中值大于mink且小于maxk的所有元素（mink和maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同）。 void delete(LinkList &L, int mink, int maxk) { p=L->next; //首元结点 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一个值>mink的结点 if (p) { while (p && p->data // 查找第一个值≥maxk 的结点 q=pre->next; pre->next=p; // 修改指针 while (q!=p) { s=q->next; delete q; q=s; } // 释放结点空间 }//if } （9）已知p指向双向循环链表中的一个结点，其结点结构为data、prior、next三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。 知道双向循环链表中的一个结点，与前驱交换涉及到四个结点（p结点，前驱结点，前驱的前驱结点，后继结点）六条链。 void Exchange（LinkedList p） ∥p是双向循环链表中的一个结点，本算法将p所指结点与其前驱结点交换。 {q=p->llink； q->llink->rlink=p；∥p的前驱的前驱之后继为p p->llink=q->llink；∥p的前驱指向其前驱的前驱。 q->rlink=p->rlink；∥p的前驱的后继为p的后继。 q->llink=p；∥p与其前驱交换 p->rlink->llink=q；∥p的后继的前驱指向原p的前驱 p->rlink=q；∥p的后继指向其原来的前驱 }∥算法exchange结束。 （10）已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。 [题目分析] 在顺序存储的线性表上删除元素，通常要涉及到一系列元素的移动（删第i个元素，第i+1至第n 个元素要依次前移）。本题要求删除线性表中所有值为item的数据元素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n），从两端向中间移动，凡遇到值item的数据元素时，直接将右端元素左移至值为item的数据元素位置。 void Delete（ElemType A[ ]，int n） ∥A是有n个元素的一维数组，本算法删除A中所有值为item的元素。 {i=1；j=n；∥设置数组低、高端指针（下标）。 while（i {while（i if（i if（i } [算法讨论] 因元素只扫描一趟，算法时间复杂度为O（n）。删除元素未使用其它辅助空间，最后线性表中的元素个数是j。 数据结构试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为（C ） A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时，要求占用的存储空间地址（D ） A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ D ）。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（ D ）。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个，采用（ C ）方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（ B ）。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放 该数组至少需要的存储字数是（ C ）。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时，通常需要使用（ A ）。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（ C ）。 10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ D ）。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与（ A ）的表示等价。 A *（a+i） B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参，则应把形参变量说明为（ B ）参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为（ C ） for (int i=0;i 《数据结构》第二章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题 （1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题 第一章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？ 解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。 2.4 对以下单链表分别执行下列各程序段，并画出结果示意图。 解： 2.5 画出执行下列各行语句后各指针及链表的示意图。 L=(LinkList)malloc(sizeof(LNode)); P=L; for(i=1;i<=4;i++){ P->next=(LinkList)malloc(sizeof(LNode)); P=P->next; P->data=i*2-1; } P->next=NULL; for(i=4;i>=1;i--) Ins_LinkList(L,i+1,i*2); for(i=1;i<=3;i++) Del_LinkList(L,i); 解： 2.6 已知L是无表头结点的单链表，且P结点既不是 习题二 一、选择题 1．在一个长度为n的顺序表中删除第i个元素（0＜i 序号 数据结构实验报告 班级姓名同组者/ 成绩 日期 3.9指导教师 实验名称实验一线性表及其应用 一、实验目的 1、深刻理解线性表的逻辑特性及其顺序、链式存储方式的特点。 2、熟练掌握线性表的常用操作（建立、插入、删除、遍历等）在顺序、链式存储上的实现。 3、加深对C/C++等编程语言的相关知识点的理解（如结构体、指针、函数、引用参数等）。 二、实验内容 1、根据给定的整型数组，以尾插法建立一个单链表，并实现以下操作： ①查找：输入一个欲查找的整数，找到则显示第一个相匹配的整数在单链表中所处的位置，若不存在，则显示提示信息。 ②删除：输入一个欲删除的整数e ，若存在则在单链表中删除第一个值为 e 的元素。 ③插入：输入一个欲插入位置i 和欲插入元素e，将e 插入到第i 个整数之前（注意i 的合法性）。 A、算法思想 ①创建 head 为头结点指针，初始时head->next 为NULL ；tail 始终指向当前链表的最后一个元素，其初始时指向头结点；p 始终指向每次申请的新结点，修改p->data 为当前读入的整数；修改tail->next 为p ，修改tail 为p ；最后修改tail->next 为NULL ，。 ②插入 找到插入点的前驱（即第i-1 个结点）的指针p ；s 指向新申请的结点；修改s->data 为参数e，修改s->next 为p->next ，修改p->next 为s 。 ③查找 ……利用p进行遍历，直到节点的数据和所给的数据相同，输出节点的位置 ④删除 ……利用p进行遍历，并总是将p的前一节点的指针赋给pre，一旦找到，则删除节点并 退出循环，没有到话，反馈相关信息 B、算法源码 /* *线性表及其应用 */ #include 2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i] } } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 填空题（10 * 1’ = 10’） 一、概念题 .当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。 .带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 .循环队列的引入，目的是为了克服假溢出。 .长度为0的字符串称为空串。 .组成串的数据元素只能是字符。 .设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。 .为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。 .广义表的深度是广义表中括号的重数 .有向图G可拓扑排序的判别条件是有无回路。 .若要求一个稠密图的最小生成树，最好用Prim算法求解。 . 直接定址法法构造的哈希函数肯定不会发生冲突。 .排序算法所花费的时间，通常用在数据的比较和交换两大操作。 .通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。 .对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。 .存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。 .抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。 .一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。 .在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior= p->prior; s->next= p; p->prior- next= s; p->prior= s;。 .在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。 .队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。 .栈是限定尽在表位进行插入或删除操作的线性表。 .在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。 .已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x; p->next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 .循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。 .串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。 .字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。 .所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。 .一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。 .在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。 网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。 .按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。 .直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。 .设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。 .下列程序判断字符串s是否对称，对称则返回1，否则返回0；如?(“abba”)返回1，?（”abab”）返回0. Int f (char*s) { Int i=0,j=0; 求串长*/ 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 数据结构顺序表的主要代码（LIZHULIN） 1．/***有头结点的单链表的初始化、建立（表头插入、表尾插入）、求长度、插入、删除、输出***/ /***********单链表的初始化、建立、输出*****************/ #include 第一章概论 一、选择题 1、研究数据结构就是研究（D ）。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作（研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作） 2、算法分析的两个主要方面是（ A ）。 A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。（线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素，有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继）（链表、栈、队列、数组、串） A. 图 B. 树 C. 广义表（线性表的推广） D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（B ）等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是（ C ）。 for(i=0;i 6、算法是（D ）。为了解决某一问题而规定的一个有限长的操作序列 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（C ）。 A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n) 8、下面程序段的时间复杂度为（ C ）。 i=1; while(i<=n) i=i*3; A. O(n) B. O(3n) C. O(log3n) D. O(n3) 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（B ）和运算等的学科。（关系和操作） A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是（ A ）。 i=s=0; while(s 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 第2章线性表 1．选择题 （1）顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 A．110 B．108 C．100 D．120 答案：B 解释：顺序表中的数据连续存储，所以第5个元素的地址为：100+2*4=108。 （2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。 A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B．在第i个结点后插入一个新结点（1≤i≤n） C．删除第i个结点（1≤i≤n） D．将n个结点从小到大排序 答案：A 解释：在顺序表中插入一个结点的时间复杂度都是O(n2)，排序的时间复杂度为O(n2)或O(nlog2n)。顺序表是一种随机存取结构，访问第i个结点和求第i个结点的直接前驱都可以直接通过数组的下标直接定位，时间复杂度是O(1)。 （3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。 A．8 B．63.5 C．63 D．7 答案：B 解释：平均要移动的元素个数为：n/2。 （4）链接存储的存储结构所占存储空间（）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值 C．只有一部分，存储表示结点间关系的指针 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数 答案：A （5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 答案：D （6）线性表Ｌ在（）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂 答案：B 第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node （A ）需经常修改L 中的结点值 （E ）需不断对L 进行删除插入 第二部分线性表 、选择题 1 ?关于顺序存储的叙述中，哪一条是不正确的 （B ） A. 存储密度大 B. 逻辑上相邻的结点物理上不必邻接 C. 可以通过计算直接确定第 i 个结点的位置 D. 插入、删除操作不方便 2.长度为n 的单链表连接在长度为 m 的单链表后的算法的时间复杂度为 （C ） A 0（ n ） B 0（1） C 0（m ） D 0（m+n ） 3 .在n 个结点的顺序表中，算法的时间复杂度是 0（1）的操作是：（A ） A 访问第i 个结点（1<=i<=n ）和求第i 个结点的直接前趋（2<=i<=n ) B 在第i 个结点（1<=i<=n ）后插入一个新结点 C 删除第i 个结点（1<=i<=n ) D 将n 个结点从小到大排序 4.一个向量第一个兀素的存储地址是 100 ,每个兀素的长度为 2 ,则第5 个兀素的地址是 (B ) ( A ) 110 ( B ) 108 (C ) 100 ( D ) 120 5 .已知一个顺序存储的线性表， 设每个结点需要占 m 个存储单元，若第一个结点的地址为 da , 则第i 个结点的地址为：（A ） 7 .链表是一种采用（ B ）存储结构存储的线性表。 （A ）顺序 （B ）链式 （C ）星式 （D ）网状 8 .线性表若采用链式存储结构时，要求内存中可用存储单兀的地址： （D ） （A ）必须是连续的 （B ）部分地址必须是连续的 （C ）一定是不连续的 （D ）连续或不连续都可以 9 .线性表L 在_ （ B ）情况下适用于使用链式结构实现。 A ） da+（i-1）*m B ） da+i*m 6.在具有n 个结点的单链表中，实现（ A ）遍历链表和求链表的第 i 个结点 C ）删除开始结点 C ） da-i*m D ） da+（i+1）*m A ）的操作，其算法的时间复杂度为 0（n ）。 B ）在地址为p 的结点之后插入一个结点 D ） 删除地址为p 的结点的后继结点 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;数据结构试题及答案
《数据结构》第二章习题参考答案 殷人昆版
数据结构线性表答案
数据结构线性表2答案
数据结构线性表实验报告
数据结构第二章课后习题题解
数据结构课后习题及答案
数据结构_实验1_线性表的基本操作
(完整版)数据结构课后习题及解析第二章
数据结构线性表的主要程序代码
数据结构试题答案
数据结构实验一题目一线性表实验报告
数据结构 线性表 课后答案
数据结构习题与答案
《数据结构》实验一 线性表及其应用
(完整版)数据结构第二章线性表1答案
数据结构作业及答案