发布时间 : 星期日 文章数据结构作业2更新完毕开始阅读8818131ac281e53a5802ff54
一、判断题。
? 1、通常数组采用静态内存分配进行存储，链表采用动态内存分配进行存
储。（ V ）
? 2、链表在进行插入与删除操作时，根本就不需要移动数据元素。（ X ） ? 3、在查找结点时，双向链表比单链表较为迅速；在插入或删除一个具体
结点时，双向链表比单链表较为费时。（ V ） ? 4、顺序存储的线性表可以按序号随机存取。（ V ）
二、选择题。（选择题答案填入下列表格中） 题号 答案 题号 答案 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8
? 1、在有n个数据元素的链表中进行插入操作，在最坏情况下需要读取多少个元素？
(A). 1 (B). n/2 (C). n (D). n/3
? 2、如下链表中，f为头指针，请问结点d的数据域如何表示？
f b e d w ^ (A). ((f→next)→next)→data (B). ((f→next)→next)→next
(C). (((f→next)→next)→next) →data (D). 以上都不是
? 3、在双向链表中，插入一个newnode在某node的右边，请在空格内选择正确的操作。 ? Void dinsert (node_pointer node, node_pointer newnode) ? { newnode→Llink=node; ? newnode→Rlink=node→Rlink; ? ( )=newnode; ? node→Rlink=newnode; } (A). node→Rlink→Llink (B). node→Llink→Rlink (C). node→Llink
(D). node→Llink→Llink ? 4、链表不具有的特点是什么？ A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间
D. 所需空间与线性表的长度成正比
? 5、线性链表（动态）是通过什么方式表示元素之间的关系的？ A. 保存后继元素地址 B. 元素的存储顺序
C. 保存左、右孩子地址 D. 保存后继元素的数组下标
? 6、设顺序表的每个元素占8个存储单元，第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址是什么？ A. 139 B. 140 C. 147 D. 148
? 7、设顺序表的长度为n，并设从表中删除元素的概率相等，则在平均情况下，从表中删除一个元素需移动的元素个数是什么？ A. (n-1)/2 B. n/2 C. n(n-1)/2 D. n(n+1)/2
? 8、在线性链表存储结构下，插入操作算法的操作如何？ A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满
D. 需要判断是否表空和表满
? 9、带头结点的单链表head为空的判断条件是（ ）。
A. head==NULL B. head->next==NULL C. head->next=head D. head!=NULL ? 10、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。 A. 单链表
B. 仅有头指针的单循环链表 C. 双链表
D. 仅有尾指针的单循环链表
? 11、线性表的静态链表存储结构与顺序存储结构相比优点是（ ）。 A. 所有的操作算法简单 B. 便于插入和删除
C. 便于利用零散的存储器空间 D. 便于随机存取
? 12、长为n的线性表采用顺序存储结构，在第i个位置插入一个新元素的算法时间复杂度为（ ）。
A. O(logn) B. O(1) C. O(n) D. O(n2)
? 13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数为（ ）。
A. n B. 2n-1 C. 2n D. n-1
? 14、在双循环链表p所指结点之后插入s所指结点的操作是（ ）。 A. p->next=s; s->prior=p; p->next->prior=s; s->prior=p->next; B. p->next=s; p->next->prior=s; s->prior=p; s->next=p->next; C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s; D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;
? 15、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q结点和p结点之间插入s结点，则执行（ ）。 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;
三、算法编程题。
3.1 将一顺序表A中的元素逆置。如原来顺序表A中元素是
100,90,80,70,60,50,40
逆置以后为
40,50,60,70,80,90,100
要求算法所用的辅助空间要尽可能地少。并编写C语言程序实现。
3.2 写一算法求已知顺序表A中元素的最大值和次最大值。并编写C语言程序实现。
3.3 设一顺序表中元素值递增有序。写一算法并用C程序实现，将元素x插到表中适当的位置，并保持顺序表的有序性，且分析算法中找出适当位置的时间复杂度。
3.4 按下面两种情况分别编写算法并用C程序实现删除顺序表中值相同的多余元素：
(1)表元素值递增有序； (2)表元素值无序。
3.5 设有两个线性表A和B皆是单链表存储结构。同一个表中的元素各不相同，且递增有序。写一算法，构成一个新的线性表C，使C为A和B的交集，且C中元素也递增有序。
3.6 设L为带头结点的单链表，按下面两种情况分别编写算法，删除表中值相同的多余元素。
(1)表元素值递增有序； (2)表元素值无序。
四、已知线性表非递减有序，存储于一个一维数组A[0,1,…,n-1]中，表长为n且为全局变量，下面算法的功能是什么？ ? Void del( DataType A[] ) ? { int i, j; i=1; ? while ( i<=n-1)
? if ( A[i] != A[i+1] ) ? i++; ? else
? { for ( j=(i+2); j 五、下述算法的功能是什么？ ? LinkList Demo ( LinkList L) ? { // L是无头结点的单链表 ? LNode *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; ? }