题库试卷

【百年教育职业培训中心】数据结构-章节资料考试资料-青岛大学

来源：百年教育职业培训中心　更新时间：2022-06-11 21:06:59

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！答案：微信搜索【渝粤教育】公众号【Test】单元测试-绪论1、【单选题】在Data_Structu

报名本机构合作学校，赠送复习资料，复习课程，确保录取。并且可以申请学校奖学金500元～1500元不等！

答案：微信搜索【渝粤教育】公众号

【Test】单元测试 - 绪论

1、【单选题】在Data_Structure=(D，S)中，D是（）的有限集合。

A、数据元素

B、算法

C、数据操作

D、数据对象

2、【单选题】被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的这种关系称为（）。

A、规则

B、结构

C、集合

D、运算

3、【单选题】以下关于数据结构的说法正确的是（）。

A、数据结构的逻辑结构独立于其存储结构

B、数据结构的存储结构独立于该数据结构的逻辑结构

C、数据结构的逻辑结构唯一地决定了该数据结构的存储结构

D、数据结构仅由其逻辑结构和存储结构决定

4、【单选题】在数据结构中，从逻辑上可以把数据结构分成（）。

A、动态结构和静态结构

B、紧凑结构和非紧凑结构

C、线性结构和非线性结构

D、内部结构和外部结构

5、【单选题】以下关于数据结构的说法中错误的是（）。

A、数据结构相同，对应的存储结构也相同

B、数据结构涉及数据的逻辑结构、存储结构和施加其上的操作3个方面

C、数据结构操作的实现与存储结构有关

D、定义逻辑结构时可不考虑存储结构

6、【单选题】算法指的是（）。

A、计算机程序

B、解决问题的计算方法

C、搜索和排序方法

D、解决问题的有限运算序列

7、【单选题】算法的时间复杂度与（）有关。

A、问题规模

B、计算机硬件的运行速度

C、源程序的长度

D、编译后执行程序的质量

8、【单选题】某算法的时间复杂度是O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_e05d4a63-e7a8-473d-b64a-0ed7c30d7d04.png" />)，表明该算法（）。

A、问题规模是<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0fbdf15a-cbe3-4e94-a70a-a63931cb214d.png" />

B、问题规模与<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d72c0fc4-5335-46f9-86c0-35f3213c6d3a.png" />成正比

C、执行时间等于<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d72c0fc4-5335-46f9-86c0-35f3213c6d3a.png" />

D、执行时间与<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d72c0fc4-5335-46f9-86c0-35f3213c6d3a.png" />成正比

9、【单选题】以下函数中时间复杂度最小的是（）。

A、T(n)=<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_35647859-142b-45eb-b7a6-0a34a91087a8.png" />+5000n

B、T(n)=<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d72c0fc4-5335-46f9-86c0-35f3213c6d3a.png" />-10000n

C、T(n)=<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_1b6136de-9471-405b-999b-b0add403e80e.png" />-6000n

D、T(n)=20000<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_51a18069-cbdf-43bf-ba45-3875727010dd.png" />

10、【单选题】下面程序段的时间复杂度为（）。x = 90;y = 100;while(y 0) if(x 100) { x = x - 10; y--; } else x++;

A、O(1)

B、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_259b04ee-32d7-475f-8db6-94345ea68885.png" />)

C、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0bcea957-7e78-4b36-bedb-854cb36e77f6.png" />)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d72c0fc4-5335-46f9-86c0-35f3213c6d3a.png" />)

11、【单选题】下面程序段的时间复杂度为（）。i = 1;while(i = n) i = i * 3;

A、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_2581cee4-3242-41be-9bc8-82d86d07a8db.png" />)

B、O(3n)

C、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_26d2dce4-42fe-4e56-99ab-5c2f31659935.png" />)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_c9c1a63d-592f-4c0c-a69f-bfbce6a92797.png" />)

12、【单选题】下面程序段的时间复杂度为（）。x = 0;for(i = 1; i n; i++) for (j = 1; j = n - i; j++) x++;

A、O(n)

B、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d3b68bbe-ef2f-4337-aa9f-739efefa5a7c.png" />)

C、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_0bcea957-7e78-4b36-bedb-854cb36e77f6.png" />)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_d72c0fc4-5335-46f9-86c0-35f3213c6d3a.png" />)

13、【判断题】数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。

A、正确

B、错误

14、【判断题】数据的物理结构是指数据结构在计算机内的实际存储形式。

A、正确

B、错误

15、【判断题】数据的逻辑结构与各数据元素在计算机中如何存储有关。

A、正确

B、错误

16、【判断题】算法的时间效率和空间效率往往相互冲突，有时很难两全其美。

A、正确

B、错误

【Test】单元测试 - 顺序存储结构

1、【单选题】顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A、110

B、108

C、100

D、120

2、【单选题】在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。

A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

B、在第i个结点后插入一个新结点（1≤i≤n）

C、删除第i个结点（1≤i≤n）

D、将n个结点从小到大排序

3、【单选题】向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。

A、8

B、63.5

C、63

D、7

4、【单选题】将两个各有n个元素的有序顺序表归并成一个有序表，其最少的比较次数是（）。

A、n

B、2n-1

C、2n

D、n-1

5、【单选题】在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。

A、n-i

B、n-i+1

C、n-i-1

D、i

6、【单选题】线性表L=(a1，a2,……an)，下列说法正确的是（）。

A、每个元素都有一个直接前驱和一个直接后继

B、线性表中至少有一个元素

C、表中诸元素的排列必须是由小到大或由大到小

D、除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继

7、【单选题】在长度为n的顺序表中插入一个元素的时间复杂度为（）。

A、O(1)

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_04eb42e5-d93a-4f42-bd2d-576aa5451c4b.png" />

C、O(n)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_a93f63c9-f380-4b81-87a3-9cd5f67e2f5f.png" />)

8、【单选题】在长度为n的顺序表中删除一个元素的时间复杂度为（）。

A、O(1)

B、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8d96336e-534c-475c-abf3-7856df51376a.png" />

C、O(n)

D、<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_02633370-d156-4030-b1d1-c5db625cefa5.png" />

9、【单选题】将两个长度分别为n、m的递增有序顺序表归并成一个有序顺序表，其最少的比较次数是（）(MIN表示取最小值）。

A、n

B、m

C、MIN(m,n)

D、m+n

10、【单选题】下述（）是顺序存储结构的优点。

A、存储密度大

B、插入运算方便

C、删除运算方使

D、方便地运用于各种逻辑结构的存储表示

11、【单选题】线性表的顺序存储结构是一种（）。

A、随机存取的存储结构

B、顺序存取的存储结构

C、索引存取的存储结构

D、散列存取的存储结构

12、【单选题】一个顺序表所占用的存储空间大小与（）无关。

A、表的长度

B、元素的存放顺序

C、元素的类型

D、元素中各数据项的类型

13、【单选题】若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为了提高效率，应采用（）的存储方式。

A、顺序表

B、单链表

C、单循环链表

D、双向链表

14、【单选题】一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入删除操作，则利用（）存储方式可以节省时间。

A、顺序表

B、单链表

C、带头结点的双循坏链表

D、单循环链表

15、【单选题】在n个元素的线性表的顺序存储表示中，时间复杂度为O(1)的操作是（）。I.访问第i(1≤i≤n)个结点和求第i(2≤i≤n)个结点的直接前驱II.在最后一个结点后插入一个新的结点III.删除第1个结点IV.在第i(1≤i≤n)个结点后插入一个结点

A、I

B、II,III

C、I,II

D、I,II,III

16、【单选题】若长度为n的非空线性表采用顺序存储结构，在表的第i个位置插入一个数据元素，i的合法值应该是（）。

A、1≤i≤n

B、1≤i≤n+1

C、0≤i≤n

D、0≤i≤n-1

17、【单选题】下列算法的功能是：从一给定的顺序表L中删除元素值在x到y (x=y)之间的所有元素。请在空白处选择正确的语句。void DelAllXY(SqList L, ElemType x, ElemType y)
{
int i, k = 0;
for (i = 0; j L.length; i++)
if (_____________________________) {
L.elem[k] = L.elem[i];
k++;
}
L.length = k;
}

A、L.elem[i] >= x && L.elem[i] <= y

B、L.elem[i] >= y && L.elem[i] <= x

C、!(L.elem[i] >= x && L.elem[i] <= y)

D、!(L.elem[i] >= y && L.elem[i] <= x)

18、【单选题】下列算法的功能是：删除顺序表中值重复的元素（值相同的元素仅保留第一个），使得表中所有元素的值均不相同。请在空白处选择正确的语句。//测试数据：{1, 2, 3, 3, 5, 3, 2, 2}、{2, 2, 3, 3, 5, 3, 2, 2}
Status deleteSame (SqList L)
{
if (L.length == 0) {
printf (表空，不能删除！\n);
return ERROR;
};
int i, j, k = 0;
for (i = 1; i L.length; i++) {
for (j = 0; j = k; j++)
if (L.elem[i] == L.elem[j])
break;
if (_______________________)
L.elem[k] = L.elem[i];
}
L.length = k + 1;
return OK;
}

A、j > i && k++ != i

B、j < k && k++ != i

C、j < i && ++k != i

D、j > k && ++k != i

19、【判断题】顺序表的元素序号从1开始，但存储位置从0开始，元素序号与其在存储中的下标值差1。

A、正确

B、错误

20、【判断题】顺序表中元素的逻辑顺序和物理顺序总是一致的。

A、正确

B、错误

21、【判断题】顺序表的主要缺点是实现线性表的插入或删除可能移动大量元素。

A、正确

B、错误

22、【判断题】在顺序表中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

A、正确

B、错误

23、【判断题】在顺序表中可以随机存取，因此存取第i个元素的时间与i 的大小有关。

A、正确

B、错误

24、【判断题】在顺序表中插入或删除一个元素x时，需要移动元素的个数与x的存储位置有关。

A、正确

B、错误

25、【判断题】设顺序表中已有n个元素，则合理的插入位置与删除位置应有n个。

A、正确

B、错误

【Test】单元测试 - 链式存储结构

1、【单选题】单链表的结点所占存储空间（）。

A、分两部分，一部分存放数据值，另一部分存放表示逻辑关系的指针

B、只有一部分，存放结点值

C、只有一部分，存储逻辑关系的指针

D、分两部分，一部分存放结点值，另一部分存放结点所占单元数

2、【单选题】线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。

A、必须是连续的

B、部分地址必须是连续的

C、一定是不连续的

D、连续或不连续都可以

3、【单选题】线性表L在（）情况下适用于使用链式结构实现。

A、需经常修改L中的结点值

B、需不断对L进行删除插入

C、L中含有大量的结点

D、L中结点结构复杂

4、【单选题】单链表的存储密度（）。

A、大于1

B、等于1

C、小于1

D、不能确定

5、【单选题】创建一个包括n个结点的有序单链表的时间复杂度是（）。

A、O(1)

B、O(n)

C、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_3f995efd-732b-41c2-b05b-d747d3596d5d.png" />)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_9323632b-2c7f-4faa-bae9-888bf5ec7c99.png" />)

6、【单选题】以下说法错误的是（）。

A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低

B、顺序存储的线性表可以随机存取

C、由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活

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

7、【单选题】在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。

A、s->next=p+1; p->next=s;

B、(*p).next=s; (*s).next=(*p).next;

C、s->next=p->next; p->next=s->next;

D、s->next=p->next; p->next=s;

8、【单选题】在双向链表存储结构中，删除p所指的结点时须修改指针（）。

A、p->next->prior=p->prior; p->prior->next=p->next;

B、p->next=p->next->next; p->next->prior=p;

C、p->prior->next=p; p->prior=p->prior->prior;

D、p->prior=p->next->next; p->next=p->prior->prior;

9、【单选题】在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。

A、p->next=q; q->prior=p; p->next->prior=q; q->next=q;

B、p->next=q; p->next->prior=q; q->prior=p; q->next=p->next;

C、q->prior=p; q->next=p->next; p->next->prior=q; p->next=q;

D、q->prior=p; q->next=p->next; p->next=q; p->next->prior=q;

10、【单选题】在单链表中查找指定值的结点的时间复杂度是（）。

A、O(1)

B、O(n)

C、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_51bb779c-6d3c-41ad-bafb-d411fb728ad5.png" />)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_b7a7b42f-df55-4f07-9a5d-16b67ac220d1.png" />)

11、【单选题】以下关于单链表的叙述中，不正确的是（）。

A、结点除自身信息外还包括指针域，因此存储密度小于顺序存储结构

B、逻辑上相邻的元素物理上不必相邻

C、可以通过头结点直接计算第i个结点的存储地址

D、插入、删除运算操作方便，不必移动结点

12、【单选题】在单链表中，增加一个头结点的目的是为了（）。

A、使单链表至少有一个结点

B、方便运算的实现

C、标识链表中重要结点的位置

D、说明单链表是线性表的链式存储结构

13、【单选题】在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。

A、O(1)

B、O(n)

C、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_8873af44-53a3-4172-8a7b-43ba2e9a9810.png" />)

D、O(<img src="http://edu-image.nosdn.127.net/_PhotoUploadUtils_657c232b-fce6-4486-845d-662f35544395.png" />)

14、【单选题】将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度是（）。

A、O(1)

B、O(m)

C、O(n)

D、O(m+n)

15、【单选题】已知一个长度为n的单链表中所有结点是递增有序的，以下叙述中正确的是（）。

A、插入一个结点使之有序的算法的时间复杂度为O(1)

B、删除最大值结点使之有序的算法的时间复杂度为O(1)

C、找最小值结点的算法的时间复杂度为O(1)

D、以上都不对

16、【单选题】在一个长度为n(nl)的带头结点的单链表L上，另设有尾指针r(指向尾结点)，执行( )操作与链表的长度有关。

A、删除单链表中的第一个元素

B、删除单链表中的尾结点

C、在单链表第一个元素前插入一个新结点

D、在单链表最后一个元素后插入一个新结点

17、【单选题】下列算法的功能是：删除单链表L（含两个或两个以上的数据结点）中第一个值为x的结点的前驱结点。请在空白处选择正确的语句。
int deleteFirstX(LinkList L, ElemType x)
{
LinkList prepre = L, pre = prepre-next, p;
if (pre-data == x) return 0;
p = pre-next;
while (p != NULL p-data != x) {
prepre = pre;
____________________;
p = p-next;
}
if (p != NULL) {
prepre-next = p;
free(pre);
return 1;
}
else return 0;
}

A、pre = p

B、prepre->next = p

C、p = pre->next

D、p = prepre->next

18、【单选题】下列算法的功能是：设List={a1,b1,a2,b2，......，an,bn}为一线性表，采用带头结点的单链表head存放，设计一个就地算法，将其拆分为两个线性表，每个线性表均采用带头结点的单链表存储，使得：A={a1,a2,......,an}，B={bn,bn-1,......，b2,b1}。
请在空白处选择正确的语句。
void splitList(LinkList head, LinkList headA, LinkList headB)
{
LinkList p = head-next, q, r;
headA = head;
r = headA;
headB = (LNode *)malloc(sizeof(LNode));
headB-next = NULL;
while (p != NULL) {
r-next = p;
r = p;
p = p-next;
q = p-next;
________________________;
headB-next = p;
p = q;
}
r-next = NULL;
}

A、headB->next = p->next

B、p = headA->next

C、p->next = headA->next

D、p->next = headB->next

19、【判断题】链式存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。

A、正确

B、错误

20、【判断题】链式存储在插入和删除时需要保持数据元素原来的物理顺序，不需要保持原来的逻辑顺序。

A、正确

B、错误

21、【判断题】在链式存储中存取数据元素时，不一定要按顺序访问。

A、正确

B、错误

22、【判断题】在单链表中，头结点就是首结点。

A、正确

B、错误

23、【判断题】在单链表中，要取得某个元素，只要知道指示该元素所在结点地址的指针即可，因此，单链表是随机存取的存储结构。

A、正确

B、错误

24、【判断题】循环单链表可以仅在链表尾部设置链尾指针。

A、正确

B、错误

25、【判断题】静态链表中地址相邻的元素具有前趋、后继关系。

A、正确

B、错误

【Test】单元测试 - 栈和队列

1、【单选题】经过以下栈运算后，x的值是（）。InitStack(s); Push(s,a); Push(s,b); Pop(s,x); GetTop(s,x);

A、a

B、b

C、1

D、0

2、【单选题】若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（）种情况。

A、5，4，3，2，1

B、2，1，5，4，3

C、4，3，1，2，5

D、2，3，5，4，1

3、【单选题】若链栈采用无头结点的单链表存储，top指向栈顶。若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。

A、x=top->data;top=top->next；

B、top=top->link;x=top-> next；

C、x=top;top=top-> next；

D、x=top-> next；

4、【单选题】数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。

A、r-f

B、(n+f-r)%n

C、n+r-f

D、n+r-f)%n

5、【单选题】设有一个递归算法如下 int fact(int n) { //n大于等于0
if(n=0)
return 1;
else
return n*fact(n-1);
}则计算fact(n)需要调用该函数的次数为（）。

A、n-1

B、n

C、n+1

D、n+2

6、【单选题】栈在（）中有所应用。

A、递归调用

B、函数调用

C、表达式求值

D、其他三个选项

7、【单选题】为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。

A、栈

B、队列

C、线性表

D、有序表

8、【单选题】设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。

A、2

B、3

C、4

D、6

9、【单选题】若一个栈以一维数组V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。

A、top--; V[top]=x;

B、top++; V[top]=x;

C、V[top]=x; top++;

D、V[top]=x; top--;

10、【单选题】设计一个判别表达式中左，右括号是否配对出现的算法，采用（　）数据结构最佳。

A、线性表的顺序存储结构

B、线性表的链式存储结构

C、栈

D、队列

11、【单选题】用链式方式存储的队列，在进行删除运算时（　）。

A、仅修改头指针

B、仅修改尾指针

C、头、尾指针都要修改

D、头、尾指针可能都要修改

12、【单选题】循环队列存储在数组A[0..m]中，则入队时的操作为（　）。

A、rear=(rear+1)%(m+1)

B、rear=(rear+1)%(m-1)

C、rear=rear+1

D、rear=(rear+1)%m

13、【单选题】最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（　）。

A、(rear+1)%n==front

B、rear==front

C、rear+1==front

D、(rear-l)%n==front

14、【单选题】栈和队列的共同点是（　）。

A、都是先进先出

B、都是先进后出

C、只允许在端点处插入和删除元素

D、没有共同点

15、【单选题】将递归算法转换成非递归算法时，通常要借助的数据结构是（）。

A、线性表

B、栈

C、队列

D、树

16、【单选题】一个递归算法必须包括（　）。

A、递归部分

B、终止条件和递归部分

C、迭代部分

D、终止条件和迭代部分

17、【单选题】执行完下列程序后，i的值为（）。int f (int x)
{
if (x 0)
return x * f (x - 1);
else
return 2;
}
int i = f(f(1));

A、2

B、4

C、8

D、无限递归

18、【单选题】下列算法的功能是：已知有n个自然数1，2，...，n存放在一维数组A[n]中，该递归算法输出这n个自然数的全排列。请在空白处选择正确的语句。#include bits/stdc++.h
using namespace std;
void perm(int A[], int i, int n)
{
int j;
int temp;
if(i == 0) {
for (j = 0; j n; j++)
printf (%d, A[j]);
printf (\n);
}
else {
for(j = 0; j = i; j++) {
temp = A[i];
A[i] = A[j];
A[j] = temp;
______________;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
}
}
/*
例如，当a[] = {1, 2, 3, 4, 5}, i = 2, n = 5时，输出结果为：
23145
32145
31245
13245
21345
12345
*/