数据结构(华中农业大学) 中国大学MOOC答案2024版100分完整版

B:head->next = = NULL;
C:head->next = = head;
D:head! = NULL;
答案: head->next = = NULL;

14、 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行____。

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;
答案: s->next=p->next;  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;
答案: q->next=s; s->next=p; 

16、 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较_____个结点。

A:n
B:n/2
C:(n-1)/2
D:(n+1)/2
答案: (n+1)/2

17、 给定有n个结点的向量，建立一个有序单链表的时间复杂度_。

A:O(1)
B:O(n)
C:O(n^2)
D:O(nlogn)
答案: O(n^2)

18、 顺序存储结构是一种___的存储结构。

A:随机存取
B:索引存取
C:顺序存取
D:散列存取
答案: 随机存取

19、 在以下的叙述中，正确的是___。

A:线性表的顺序存储结构优于链表存储结构
B:线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C:线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D:线性表的链表存储结构优于顺序存储结构
答案: 线性表的链表存储结构适用于频繁插入/删除数据元素的情况

20、 非空的循环单链表head的尾结点（由p所指向）满足____。

A:p->next= =NULL
B: p= =NULL
C: p->next= =head
D:p= =head
答案:  p->next= =head

21、 在一个单链表中，若删除p所指结点的后续结点，则执行____。

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；
答案: p->next= p->next->next；

22、 在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移____个元素。

A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i+1

23、 在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移____个元素。

A:n-i
B:n-i+1
C:n-i-1
D:i
答案: n-i

24、 在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为____。

A:n
B:n/2
C:(n+1)/2
D:(n-1)/2
答案: (n+1)/2

25、 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行____。

A:HL = p;  p->next = HL; 
B:p->next = HL;  HL = p;
C:p->next = HL;   p = HL;
D:p->next = HL->next;  HL->next = p;
答案: p->next = HL;  HL = p;

26、 一个带头结点head的循环单链表为空的判断条件是____。

A:head==NULL 
B:head->next==NULL
C:head->next==head
D:head!=NULL
答案: head->next==head

27、 在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行____。

A:p = q->next ;  p->next = q->next;
B:p = q->next ;  q->next = p;
C:p = q->next ;  q->next = p->next;
D:q->next = q->next->next;  q->next = q;
答案: p = q->next ;  q->next = p->next;

28、 将两个各有n个元素的有序表归并成一个有序表，在最坏的情况下，其比较次数是____。

A:2n-1
B:n
C:n+1
D:n-1
答案: 2n-1

29、 线性表的逻辑顺序与存储顺序总是一致的。

A:正确
B:错误
答案: 错误

30、 顺序存储的线性表可以按序号随机存取。

A:正确
B:错误
答案: 正确

31、 顺序表的插入和删除一个数据元素，每次操作平均只有近一半的元素需要移动。

A:正确
B:错误
答案: 正确

32、 线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

A:正确
B:错误
答案: 正确

33、 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

A:正确
B:错误
答案: 错误

34、 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

A:正确
B:错误
答案: 正确

35、 线性表的链式存储结构优于顺序存储结构。

A:正确
B:错误
答案: 错误

36、 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

A:正确
B:错误
答案: 正确

37、 线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

A:正确
B:错误
答案: 正确

38、 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

A:正确
B:错误
答案: 错误

39、 线性表中，每一个元素均存在前驱。

A:正确
B:错误
答案: 错误

40、 线性表中，每一个元素均存在后继。

A:正确
B:错误
答案: 错误

41、 线性表中，存在唯一一个被称为第一元素的元素。

A:正确
B:错误
答案: 正确

42、 线性表中，存在唯一一个被称为最后一个元素的元素。

A:正确
B:错误
答案: 正确

43、 线性结构是一种一对一的结构。

A:正确
B:错误
答案: 正确

第3章 栈和队列 栈和队列

1、 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。

A:edcba 
B:decba 
C:dceab 
D: abcde
答案: dceab 

2、 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为____。

A:i
B:n=i
C:n-i+1
D:不确定
答案: n-i+1

3、 栈结构通常采用的两种存储结构是____。

A:顺序存储结构和链式存储结构
B:散列方式和索引方式
C:链表存储结构和数组
D:线性存储结构和非线性存储结构
答案: 顺序存储结构和链式存储结构

4、 判定一个顺序栈ST（最多元素为m0）为空的条件是____。

A:top !=0
B:top= =0
C:top !=m0
D:top= =m0-1
答案: top= =0

5、 判定一个顺序栈ST（最多元素为m0）为栈满的条件是____。

A:top！=0 
B:top= =0
C:top！=m0
D:top= =m0-1
答案: top= =m0-1

6、 队列操作的原则是____。

A:先进先出
B:后进先出
C:只能进行插入
D:只能进行删除
答案: 先进先出

7、 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ __。(不带空的头结点)

A:HS—＞next=s;
B:s—＞next= HS—＞next;  HS—＞next=s;
C:s—＞next= HS;  HS=s;
D:s—＞next= HS;  HS= HS—＞next;
答案: s—＞next= HS;  HS=s;

8、 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__  __。(不带空的头结点)

A:x=HS;  HS= HS—＞next; 
B:x=HS—＞data;
C:HS= HS—＞next; x=HS—＞data; 
D:x=HS—＞data; HS= HS—＞next;
答案: x=HS—＞data;

9、 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。

A:4，3，2，1 
B:1，2，3，4
C:1，4，3，2 
D:3，2，4，1
答案: 1，2，3，4

10、 判定一个循环队列QU（最多元素为m）为空的条件是____。

A:rear – front= =m
B:rear-front-1= =m
C:front= = rear
D:front= = rear+1
答案: front= = rear

11、 判定一个循环队列QU（最多元素为m, m= =Maxsize-1）为满队列的条件是____。

A:((rear- front)+ Maxsize)% Maxsize = =m
B:rear-front-1= =m
C:front= =rear
D:front= = rear+1
答案: ((rear- front)+ Maxsize)% Maxsize = =m

12、 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。

A: (rear-front+m)%m
B:rear-front+1
C:rear-front-1
D: rear-front
答案:  (rear-front+m)%m

13、 栈和队列的共同点是____。

A:都是先进后出
B:都是先进先出
C:只允许在端点处插入和删除元素 
D:没有共同点
答案: 只允许在端点处插入和删除元素 

14、 栈操作的原则是____。

A:先进先出
B:后进先出
C:只能进行插入
D:只能进行删除
答案: 后进先出

15、 在顺序栈中，判断栈s为空的条件是____。

A:t.base == NULL
B:st.top == st.stacksize
C:st.top-st.base>=st.stacksize
D:st.top == st.base
答案: st.top == st.base

16、 在顺序栈中，判断栈s满的条件是____。

A:st.base == NULL
B:st.top == st.stacksize
C:st.top-st.base>=st.stacksize
D:st.top == st.base
答案: st.top-st.base>=st.stacksize

17、 当利用大小为N的一维数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行语句修改top指针____。

A:top++
B:top– 
C:top=0
D:top
答案: top– 

18、 当利用大小为N的一维数组顺序存储一个循环队列时，该队列的最大长度为____。

A:N-2
B:N-1
C:N
D:N+1
答案: N-1

19、 从一个循环顺序队列删除元素时，首先需要____。

A:前移一位队首指针
B:后移一位队首指针
C:取出队首指针所指位置上的元素
D:取出队尾指针所指位置上
答案: 后移一位队首指针

20、 假定一个循环顺序队列的队首和队尾指针分别为f和r，则判断队空的条件是____。

A:f+1==r 
B:r+1==f 
C:f==0
D:f==r
答案: f==r

21、 假定一个链队的队首和队尾指针分别为front和rear，则判断队空的条件是____。

A:front==rear 
B:front!=NULL
C:rear!=NULL
D:front==NULL
答案: front==NULL