算法与数据结构答案2023秋

第二章测试

1.下面关于线性表的叙述中，错误的是哪一个（ ）
A:线性表采用顺序存储，必须占用一片连续的存储单元。 B:线性表采用链接存储，不必占用一片连续的存储单元。 C:线性表采用链接存储，便于插入和删除操作。 D:线性表采用顺序存储，便于进行插入和删除操作。
答案:D
2.设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。
A:O(n) B:O(1) C:O(n2) D:O(log2n) 3.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（ ）
A:对 B:错 4.单循环链表H的尾结点p的特点是（ ）。
A:p->next== H->next  B:p==H ->next  C:p==H  D:p->next==H  5.在顺序表中插入和删除一个结点需平均移动多少个结点?
A:(n-1)/2
B:(n+1)/2 C:(2n-1)/2 D:n/2
1.带头结点的单链表head为空的判定条件是（）
A:head->next= =NULL B:head->next= =head C:head!=NULL D:head= =NULL 2.循环链表的主要优点是（ ）。
A:在表中任一结点出发都能扫描整个链表 B:不再需要头指针 C:在进行插入、删除运算时能保证链表不断开 D:已知某结点位置后能容易找到其直接前驱 3.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）
A:必须是连续的 B:部分地址必须是连续的 C:连续或不连续都可以 D:一定是不连续的 4.若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
A:循环单链表 B:单链表 C:双链表 D:顺序表 5.在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（ ）个元素
A:n-i+1 B:n-i C:n-i-1 D:i 6.线性表的顺序存储结构是一种（ ）存储结构。
A:索引存取 B:顺序存取 C:散列存取 D:随机存取 7.在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（ ）。
A:q->next=p->next;q->prior=p;p->next=q;p->next=q; B:p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C:p->next=q;q->prior=p;p->next->prior=q;q->next=q; D:q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; 8.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（ ）。（答案中的i均为合法输入）
A:对顺序表中元素进行排序 B:删除第i个元素 C:在第i个元素之后插入一个新元素 D:访问第i个元素的前驱 9.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为（ ）。
A:p->next=s->next；s->next=q； B:q->next=s->next；s->next=p； C:s->next=q；p->next=s->next； D:s->next=p；q->next=s->next； 10.在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（ ）。
A:n B:n/2 C:(n-1)/2 D:(n+1)/2