数据结构-0章习题

【#文档大全网# 导语】以下是®文档大全网的小编为您整理的《数据结构-0章习题》，欢迎阅读！

***

第１章 绪论

1．简述以下概念：数据、数据元素、数据项、数据对象、数据构造、逻辑构造、存储构造、抽象数据类型。 2．试举一个数据构造的例子，表达其逻辑构造和存储构造两方面的含义和互相关系。 3．简述逻辑构造的四种根本关系并画出它们的关系图。 4．存储构造由哪两种根本的存储方法实现？ 5．选择题

〔1〕在数据构造中，从逻辑上可以把数据构造分成〔 〕。 A．动态构造和静态构造 B．紧凑构造和非紧凑构造 C．线性构造和非线性构造 D．内部构造和外部构造

〔2〕与数据元素本身的形式、内容、相对位置、个数无关的是数据的〔 〕 A．存储构造 B．存储实现 C．逻辑构造 D．运算实现 〔3〕通常要求同一逻辑构造中的所有数据元素具有一样的特性，这意味着〔 〕。 A．数据具有同一特点

B．不仅数据元素所包含的数据项的个数要一样，而且对应数据项的类型要一致 C．每个数据元素都一样

D．数据元素所包含的数据项的个数要相等 〔4〕以下说法正确的选项是〔 〕。 A．数据元素是数据的最小单位 B．数据项是数据的根本单位

C．数据构造是带有构造的各数据项的集合

D．一些外表上很不一样的数据可以有一样的逻辑构造 〔5〕以下与数据的存储构造无关的术语是〔 〕。

A．顺序队列 B. 链表 C. 有序表 D. 链栈 〔6〕以下数据构造中，〔 〕是非线性数据构造

A．树 B．字符串 C．队 D．栈 6．试分析下面各程序段的时间复杂度。 〔1〕x=90; y=100; while(y>0) if(x>100) {x=x-10;y--;} else x++; 〔2〕for (i=0; i for (j=0; j a[i][j]=0; 〔3〕s=0;

for i=0; i for(j=0; j s+=B[i][j]; sum=s; 〔4〕i=1; while(i<=n)

1


***

i=i*3; 〔5〕x=0;

for(i=1; i for (j=1; j<=n-i; j++) x++; 〔6〕x=n; //n>1 y=0;

while(x≥(y+1)* (y+1)) y++;

第2章 线性表

1．选择题

〔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〕链接存储的存储构造所占存储空间〔 〕。

A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针 B．只有一部分，存放结点值

C．只有一部分，存储表示结点间关系的指针

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

〔5〕线性表假设采用链式存储构造时，要求内存中可用存储单元的地址〔 〕。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以 〔6〕线性表Ｌ在〔 〕情况下适用于使用链式构造实现。 A．需经常修改Ｌ中的结点值 Ｂ．需不断对Ｌ进展删除插入 C．Ｌ中含有大量的结点 Ｄ．Ｌ中结点构造复杂 〔7〕单链表的存储密度〔 〕。

A．大于1 B．等于1 C．小于1 D．不能确定

〔8〕将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是〔 〕。 A．n B．2n-1 C．2n D．n-1

〔9〕在一个长度为n的顺序表中，在第i个元素〔1≤i≤n+1〕之前插入一个新元素时须向后挪动〔 〕个元素。

A．n-i B．n-i+1 C．n-i-1 D．i

(10) 线性表L=(a1，a2,……an)，以下说法正确的选项是〔 〕。

2


***

A．每个元素都有一个直接前驱和一个直接后继 B．线性表中至少有一个元素

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

D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 (11) 假设指定有n个元素的向量，那么建立一个有序单链表的时间复杂性的量级是〔 〕。 A．O(1) B．O(n) C．O(n2) D．O(nlog2n) (12) 以下说法错误的选项是〔 〕。

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

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

C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵敏 D．线性表的链式存储构造优于顺序存储构造

(13) 在单链表中，要将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;

(14) 在双向链表存储构造中，删除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;

(15) 在双向循环链表中，在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;

2．算法设计题

〔1〕将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。

〔4〕设计一个算法，通过一趟遍历在单链表中确定值最大的结点。

〔5〕设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。 〔7〕长度为n的线性表A采用顺序存储构造，请写一时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。



第3章 栈和队列

1．选择题

〔1〕假设让元素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

本文来源：https://www.wddqxz.cn/9a908fc99a8fcc22bcd126fff705cc1755275f84.html