发布时间 : 星期一 文章数据结构作业（二）更新完毕开始阅读2c94d65548d7c1c709a14526
数据结构作业（二）
一、单选题
1．设用链表作为栈的存储结构则退栈操作（B ）。 (A) 必须判别栈是否为满 (C) 判别栈元素的类型 2．数据的最小单位是（A ）。 (A) 数据项
(B) 数据类型 (C) 数据元素 (D) 数据变量
(B) 必须判别栈是否为空 (D) 对栈不作任何判别
3．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ D ）。 (A) O(log2n)
(B) O(1)
(C) O(n2)
(D) O(n)
4．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（C ）。 (A) n-i
(B) n-1-i
(C) n+1-i
(D) 不能确定
5．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（A ）。 (A) head==0
(B) head->next==0 (D) head!=0
(C) head->next==head
6.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的
队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（ C ）。
(A) front->next=s；front=s； (B) s->next=rear；rear=s； (C) rear->next=s；rear=s； (D) s->next=front；front=s；
1
7．程序段s=i=0；do {i=i+1； s=s+i；}while(i<=n)；的时间复杂度为（ A）。 (A) O(n)
(B) O(nlog2n) (C) O(n2)
(D) O(n3/2)
8．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（ C ）。 (A) head==0
(B) head->next==0 (D) head!=0
(C) head->next==head
9.有一个链式栈S,设其栈顶指针变量为top，则删除栈顶元素的操作语句为（ D）。
(A) S.top=S.top+1; (C) S.top->next=S.top; 10.队列是一种（A ）的线性表。
(A) 先进先出 (B) 先进后出 (C) 只能插入 (D) 只能删除
(B) S.top=S.top-1; (D) S.top=S.top->next;
二、填空题
1．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__s->next=p->next,p->next=s______（设结点的指针域为next）。
2．设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___n-i+1____个数据元素；删除第i个位置上的数据元素需要移动表中____n-i___个元素。
3．设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_i(i+1)_/2+j-1_____个数据元素。
2
4．设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为__ p>llink->rlink=p->rlink;p->rlink->llink=p->rlink _______（设结点中的两个指针域分别为llink和rlink）。
5．设有一个顺序循环队列Q中有M个存储单元，则该循环队列中最多能够存储__M-1______个队列元素；当前实际存储___ (R-F+M)%M ______个队列元素，判断该循环队列为空的条件为____Q.front=q.rear_____，判断该循环队列为满的条件为_ Q.front ==(q.rear+1)%M________。（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。
三、应用题
1. 设指针变量p指向双向链表中结点A，请给出从该双向链表中删除结点A的
语句序列（设双向链表中结点的两个指针域分别为leftLink和rightLink）。 2. 画出广义表LS=(( ) , (e , f) , (a , (b , c , d ) , g))的两种存储结构。
四、编写算法
设计在单链表中删除值相同的多余结点(即：多个相同的结点只保留一个)的算法delSameNode(LNode *HL)。
3