发布时间 : 星期四 文章数据结构c语言版试题大全（含答案）更新完毕开始阅读13adb34dc850ad02de804116
数据结构复习题答案：线性表 填空题
1、无|一|无|一 2、一半
3、O(n)|O(1)
4、相邻位置|链接指针 5、q->next?p->next->next
6、浪费|溢出|预先分配|动态存储区|溢出 7、变参或函数名|链接指针|前移|减1 8、n-i+1 9、n-i-1
10、简化插入、删除算法 11、前驱
12、指针链?next链 13、前驱结点|后续结点 14、循环双
15、p->next|s->data|t 16、p->next->next 17、p->next|s 18、O(0)|O(n)
19、物理存储位置|链域的指针值 20、n-i
21、L->length=0?L.length=0 22、最后一个 23、第一个 24、最后一个 25、第一个 26、O(n) 27、O(n) 28、O(1) 29、O(n)
30、q->next?p->next->next 31、p->next|s 32、O(1)|O(n) 33、O(1) 34、O(1) 35、双 36、4
37、p->prior->next=q;q->next=p;q->prior=p->prior;p->prior=q; 38、L->next==L
39、指向下一个结点的指针 40、O(n)| O(1) 41、O(1)|O(n)
- 29 -
42、i-1| i+1
43、p->next |a[p].next 44、表头
45、前驱|后继 46、表尾|表头
47、HL->next==NULL| HL->next==HL 50、a[j].next=a[i].next; | a[i].next=j;
数据结构复习题：线性表 问答题
1、线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?
(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?
(3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?
2、用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么? 3、在单链表和双向表中，能否从当前结点出发访问到任一结点? 4、编写下列算法
(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (2)从类型为list的线性表L中删除其值等于x的所有元素。
(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。
5、编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 (2)删除单链表中第i个（i≥1）结点。 (3)删除单链表中由指针p所指向的结点。
(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (6)从循环单链表中查找出最小值。
(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结 点的单链表。
6、对链表设置头结点的作用是什么?(至少说出两条好处)
7、在单链表、双链表和单循环表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去？若可以，其时间复杂度各为多少？ 8、简述顺序表和链表存储方式的特点。
9、有两个递增有序表，设计一个算法将它们归并成一个有序表(假设每个表中没有重复关键字的元素，归并时重复关键字的元素只归并一次)。
数据结构复习题答案：线性表 问答题
1、解答：(1)顺序存储是按索引（隐含的）直接存取数据元素，方便灵活，效率高，但插入、删除操作时将引起元素移动，因而降低效率；链接存储内存采用动态分配，利用率高，但需增设指示结点之间有序关系的
- 30 -
指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作十分简单。 (2)应选用链接表存储结构。其理由是，链式存储结构用一组任意的存储单元依次存储线性表里各元素，这里存储单元可以是连续的，也可以是不连续的。这种存储结构，在对元素作插入或删除运算时，不需要移动元素，仅修改指针即可。所以很容易实现表的容量扩充。
(3)应选用顺序存储结构。其理由是，每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。由此，只要确定了起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。而链表则是一种顺序存取的存储结构。
2、不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、 扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。
3、在单链表中只能由当前结点访问其后的任一结点，因为没有指向其前驱结点的指 针。而在双向链表中，既有指向后继结点的指针又有指向前驱结点的指针，故可由当前结点出发访问链表中任一结点。 4、 (1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。 (1) 解答: status insert(SqList L,int i,ElemType x){
// 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error('overflow');
(2) if (i<0) || (i>L.len) error ('out of range'); (3) for (j=L.len ;j>= i＋1;--j ) L.vec[j＋1]＝L.vec[j]; }
(4) L.vec[i＋1]＝x; (5) L.len＝len＋1; }
(2)从类型为list的线性表L中删除其值等于x的所有元素。 (2) 解答: status delete(L,x) {
// 从线性表L中删除其值等于x的所有元素 i＝1;
while (i<＝L.len ) if (L.vec[i]= =x ){
(Ⅰ) for( j＝i＋1 ;j<= L.len ;++j) L.vec[
5、解答：(1)将一个单链表中的所有结点按相反次序链接。 (1) 解答: status contrary(HL){
// 使HL单链表中的所有结点按相反次序链接
p＝HL ; //p指向未被逆序的第一个结点，初始指向原表头结点 HL＝nil; //HL指向逆序后的表头结点，初始值为空 while (p!=nil ){
(1) q＝p; //q指向将被逆序链接的结点 (2) p＝p＾.next; (3) q＾.next＝HL; (4) HL＝q; } }
- 31 -
(2)删除单链表中第i个（i≥1）结点。 (2) 解答:status delete(HL,i){
(1) if (i<＝0) or (HL＝nil) error('not h&&le'); (2) if (i＝1 )
{ HL＝HL->next; return ; }
(3) j＝1; p＝HL; //p指针所指向的结点，是单链表中第j
6、解答：(1) 对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一结点的指针域，因为任何元素结点都有前驱结点。若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点或删除该结点时操作会复杂些。
(2) 对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。
7、解答：1. 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2. 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。 3. 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
8、答：顺序表可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率；而链表内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序表方便，但结点的插入、删除操作较简单。 9、答：void Merge (LinkList &La, LinkList Lb) { pa=La->next; pb=Lb->next; p=La; while(pa && pb)
{ if (pa->data<=pb->data)
{p->next=pa; p=pa; pa=pa->next;} else
{p->next=pb; p=pb; pb=pb->next;} }
if(pa) p->next=pa; else p->next=pb; free(Lb); }
- 32 -