数据结构期末考试(题集)

1、WORD格式数据构造的根本概念选择题 1顺序存储构造中数据元素之间的逻辑关系是由表示的， 存储构造中的数据元素之间的逻辑关系是由表示的。A 线性构造B 非线性构造C存储位置D指针 2假设有如下遗产继承规那么： 丈夫和妻子可以相互继承遗产， 子女可以继承父亲或母亲的遗产； 子女间不能相互继承， 那么表示该遗产继承关系的最适宜的数据构造应该是。A 树B 图C线性表D集合 3计算机所处理的数据一般具有某种内在联系，这是指。A 数据和数据之间存在某种关系B元素和元素之间存在某种关系C元素内部具有某种构造D数据项和数据项之间存在某种关系 4在数据构造中，与所使用的计算机无关的是数据的。A 树B 图C线性

2、表D集合 5在存储数据时，通常不仅要存储各数据元素的值，还要存储。A 数据的处理方法B数据元素的类型C数据元素之间的关系D数据的存储方法 6在存储构造中，要求。A 每个结点占用一片连续的存储区域B所有结点占用一片连续的存储区域C结点的最后一个域是指针类型D每个结点有多少个后继就设多少个指针 7以下说法不正确的选项是。A 数据元素是数据的根本单位B数据项是数据中不可分割的最小单位C数据可由假设干个数据项构成D数据元素可由假设干个数据项构成 8以下与数据的存储构造无关的术语是。A 循环队列B 链表C散列表D栈 9以下术语属于逻辑构造的是。A 顺序表B 哈希表C有序表D单链表 10可以用定义一个完整

3、的数据构造。A 数据元素B 数据对象C数据关系D抽象数据类型 11对于数据构造的描述，以下说法中不正确的选项是。A 一样的逻辑构造对应的存储构造也必一样B数据构造由逻辑构造、存储构造和根本操作三方面组成专业资料整理WORD格式1专业资料整理WORD格式C数据构造根本操作的实现与存储构造有关D数据的存储构造是数据的逻辑构造的机内实现 12以下关于存储构造的表达中，是不正确的。A 结点除数据信息外还包括指针域，因此存储密度小于顺序存储构造B逻辑上相邻的结点物理上不一定相邻C可以通过计算得到第i 个结点的存储地址D插入和删除操作方便，不必移动结点 13可以用、数据关系和根本操作定义一个完整的抽象数据

4、类型。A 数据元素B 数据对象C原子类型D存储构造应用题 14设有数据构造D ， R，其中 D=1 ， 2， 3， 4，5， 6 ，R=(1 ， 2)， (2， 3)，(2， 4)，(3 ， 4)，(3 ，5) ， (3， 6)， (4， 5)， (4， 6) 。试画出其逻辑构造图并指出属于何种构造。（ 15 试描述数据构造和抽象数据类型的概念与程序设计语言中数据类型概念的区别。（ 16 说明数据的逻辑构造和存储构造之间的关系。（ 17 抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？专业资料整理WORD格式2专业资料整理WORD格式1 算法和

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

6、算法分析的目的是，算法分析的两个主要方面是。A 找出数据构造的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性 7算法的时间复杂度与有关。A 问题规模B计算机硬件性能C编译程序的质量D程序设计语言 8算法的时间复杂度与有关。A 问题规模B待处理数据的初态C算法的易读性DA和B 9某算法的时间复杂度是(n2)，说明该算法。A 问题规模是 n2B执行时间等于n2C执行时间与 n2成正比D问题规模与 n2成正比 10下面说法错误的选项是。专业资料整理WORD格式3专业资料整理WORD格式算

7、法原地工作的含义是指示不需要如何额外的辅助空间在一样的规模 n 下，复杂度 (n)的算法在时间上总是优于复杂度 (2 n)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低 11算法for (i=n-1; i>=1; i-)for (j=1; j<=i; j+)if (aj>aj+1) aj 与 aj+1 交换；其中 n 为正整数，那么最后一行语句的频度执行次数在最坏情况下是。A (n)B (nlog 2 n)32C (n )D (n ) 12算法的时间复杂度属于一种。A 事前统计的方法B事先分析估算的方法C事后统计的

8、方法D事后分析估算的方法 13设某算法完成对 n 个元素进展处理， 所需的时间是T(n)=100 nlog 2n+200n+500 ，那么该算法的时间复杂度是。A (1)B (n)C (nlog 2n)D (nlog 2n+n) 14假设时间复杂度为(n2)的算法在有 200 个元素的数组上运行需要3.1ms，那么在有 400 个元素的数组上运行需要 ms。A3.1B6.2C 12.4D x无法确定 15以下程序段加下划线的语句执行次。for (m=0,i=1; i<=1; i+)for (j=1; j<=2*i; j+)A n2m=m+1 ；D n3B 3nC n(n+1)应用题

9、 16将以下函数按它们的n时的无穷大阶数，从小到大排列。n， n-n3-7n5， nlog 2n， 2n/2， n3， log 2n， n1/2+log 2 n， (3/2) n，n! ，n2+log 2n 17分析以下程序段，并用大记号表示其执行时间。i=1;k=0;else i+;while (i<n-1)for (i=1;i<=n;i+)for (j=1;j<=i;j+)k=k+10*i;for (k=1;k<=j;k+)i+;x+;i=1;k=0;i=1;j=0;dowhile (i+j<=n)if (i>j) j+;k=k+10*i;专业资料整理W

10、ORD格式4专业资料整理WORD格式i+; while (i<=n) for (i=0;i<n;i+) y=0;for (j=0;j<m;j+)while (y+1)*(y+1)<=n)aij=0;y=y+1 18有实现同一功能的两个算法A1 和 A2 ，其中 A1 的时间复杂度为T 1= (2n)，2A2 的时间复杂度为 T 2= (n )，仅就时间复杂度而言，请具体分析这两个算法哪一个好。综合应用题 19设 n 是偶数，且有程序段：for (i=1;i<=n;i+)if (2*i<=n)for (j=2*I;j<=n;j+)y=y+i*j;那么语句

11、 y=y+i*j的执行次数是多少？要求列出计算公式。 20 斐波那契数列 Fn定义如下：F0=0， F1=1 ， , ， Fn=Fn-1+Fn-2n=2， 3，,请就此斐波那契数列，答复以下问题。在递归计算Fn的时候，需要对较小的Fn-1， Fn-2，, ，F1， F0准确计算多少次？用大表示法给出递归计算时递归函数的时间复杂度是多少？（ 21 运算是数据构造的一个重要方面。 举例说明两个数据构造的逻辑构造和存储方式完全一样， 只是对于运算的定义不同， 因而具有不同的特性， 那么这两个数据构造是不同的。（ 22 针对给定的实际问题建立数据构造时，应从哪些方面考虑。专业资料整理WORD格式5专业

12、资料整理WORD格式2 线性表的逻辑构造选择题 1线性表是具有n 个的有限序列。A 数据B 字符C数据元素D数据项 2线性表是。A 一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空 3关于线性表，以下说法中正确的选项是。A 线性表中每个元素都有一个直接前驱和一个直接后继B线性表中的数据元素可以具有不同的数据类型C线性表中数据元素的类型是确定的D线性表中任意一对相邻的数据元素之间存在序偶关系 4是一个线性表。A 由 n 个实数组成的集合B由所有实数组成的集合C由所有整数组成的序列D由 n 个字符组成的序列专业资料整理WORD格式6专业资料整理WORD

13、格式3顺序线性表选择题 1一维数组 A 采用顺序存储构造，每个元素占用4 个存储单元，第9 个元素的地址为144，那么第一个元素的地址是。A108B180C 176D 112 2在长度为 n 的线性表中查找值为x 的数据元素的时间复杂度为。A (0)B (1)C (n)D (n2) 3在一个长度为 n 的线性表的第i 1 i n+1 个元素之前插入一个元素，需向后移动个元素，删除第i 1 i n个元素时，需向前移动个元素。A n-iB n-i+1C n-iD n-i+1 4线性表的顺序存储构造是一种的存储构造。A 随机存取B 顺序存取C索引存取D散列存取 5顺序存储构造的优点是。A 存储密度大

14、B插入运算方便C删除运算方便D可方便地用于各种逻辑构造的存储表示 6n 个结点的线性表采用数组实现，算法的时间复杂度是 (1) 的操作是 。A 访问第 i 个结点 1i n和求第 i 个结点的直接前驱2 i nB在第 i 个结点后插入一个新结点 1 i nC删除第i 个结点 1 i nD以上都不对 7对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为。A (n)、 (n)B (n) 、 (1)C (1) 、 (n)D (1)、 (1) 8顺序表的插入算法中，当n 个空间已满时，可再申请增加分配m 个空间，假设申请失败，那么说明系统没有可分配的存储空间。A m 个B m 个连续的C

15、n+m 个D n+m 个连续的应用题 9设 A 是一个线性表a1， a2，, ，an，采用顺序存储构造，那么在等概论的前提下，平均每插入一个元素需要移动的元素个数为多少？假设元素插在ai与 ai+1之间(1 i n)的概率为 n-i / n n-1 /2，那么平均每插入一个元素所移动的元素个数是多少？ 10设 n 表示线性表中的元素个数，E 表示存储数据元素所需要的存储单元大小，专业资料整理WORD格式7专业资料整理WORD格式D 表示可以在数组中存储线性表的最大元素个数D n，那么使用顺序存储方式存储线性表需要多少存储空间？ 11在什么情况下线性表使用顺序存储比较好？算法设计题（ 12 试以

16、顺序表作存储构造，实现线性表就地逆置。（ 13 设计算法判断给定字符串是否是回文。所谓回文是正读和反读均一样的字符串，例如 abcba 或 abba 是回文，而 abcda 不是回文。 14设计一个时间复杂度为(n)的算法，实现将数组An 中所有元素循环左移k个位置。 15数组An 中的元素为整型，设计算法将其调整为左右两局部，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为(n)。 16假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。 17顺序存储的线性表A ，其数据元素为整型，设计算法将A 拆成 B 和 C 两个表，使 A 中值大于0 的元素存入表B，值

17、小于0 的元素存入表C，要求 B 和 C 不另外设置存储空间而利用A 的空间。 18顺序表L 中的元素递增有序排列，设计算法将元素x 插入到表L 中并保持表 L 仍递增有序。 19设计一个高效算法，在顺序表中删除所有元素值为x 的元素， 要求空间复杂度为 (1) 。 20设计算法实现从顺序表L 中删除所有值在x 和 y 之间的所有元素，要求时间性能复杂度为(n)，空间性能为(1) 。（ 21 设计算法删除顺序表中重复的元素， 要求算法移动元素的次数较少并使剩余元素间的相对次序保持不变。 22给定 n 个记录的有序序列An 和 m 个记录的有序序列Bm ，将它们归并为一个有序序列， 存放在 Cn

18、+m 中，试写出这一算法 假设 A 、B 和 C 均为升序序列。专业资料整理WORD格式8专业资料整理WORD格式4线性链表选择题 1线性表的存储构造是一种的存储构造。A 随机存取B 顺序存取C索引存取D散列存取 2线性表采用存储时，其。A 地址必须是连续的B局部地址必须是连续的C地址一定是不连续的D地址连续与否均可以 3链表不具有的特点是。A 可随机访问任一元素B插入、删除不需要移动元素C不必事先估计存储空间D所需空间与线性表长度成正比（ 4在具有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ 。A (1)B (n)C (n2)D (nlog 2n1) 5对于 n 个元素

19、组成的线性表，建立一个单链表的时间复杂度是。A (1)B (n)C (n2)D (nlog 2n1) 6对于 n 个元素组成的线性表，建立一个有序单链表的时间复杂度是。A (1)B (n)C (n2)D (nlog 2n1) 7在单链表中删除指针p 所指结点的后续结点，那么执行。A p->next=p->next->nextB p->next=p->nextCp=p->next->nextD p=p->next; p->next=p->next->next 8在一个单链表中， q 所指结点是 p 所指结点的直接前驱，假设在 q

20、和 p 之间插入 s 所指结点，那么执行操作。A s->next=p->next; p->next=s;B q->next=s; s->next=p;Cp->next=s->next; s->next=p;D p->next=s; s->next=q 9在一个长度为 n n>1的带头结点的单链表h 上，另设有尾指针r 指向尾结点，执行操作与链表的长度有关。A 删除单链表中的第一个元素B删除单链表中的最后一个元素C在单链表第一个元素前插入一个新元素D在单链表的最后一个元素后插入一个新元素 10在单链表中附加头结点的目的是为了。A

21、保证单链表中至少有一个结点B标识单链表中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储专业资料整理WORD格式9专业资料整理WORD格式 11将长度为n 个单链表在长度为m 的单链表之后的算法，其时间复杂度是。A (1)B (n)C (m)D (n+m) 12循环单链表的主要优点是。A 不再需要头指针了B从表中任一结点出发都能扫描到整个链表C某个结点的位置后，能够容易找到它的直接前驱D在进展插入、删除操作时，能更好地保证链表不断开 13 将线性表 a1， a2，, ， an组织为一个带头结点的循环单链表，设H 为链表的头指针，那么链表中最后一个结点的指针域中存放的是。A 变量 H

22、的地址B变量 H 的值C元素 a1的地址D空指针 14 非空的循环单链表 L 的尾结点p 满足。A p=NULLB p->next=NULLC p->next=LD p=L 15假设要在 (1) 的时间内实现两个循环单链表的首尾相接，那么两个循环单链表应各设一个指针，分别指向。A 各自的头结点B各自的尾结点C各自的第一个元素结点D一个表的头结点，一个表的尾结点 16设线性表非空， 可以在 (1)的时间内在表尾插入一个新结点。A 带头结点的单链表，有一个链表指针指向头结点B带头结点的循环单链表，有一个链表指针指向头结点C不带头结点的单链表，有一个链表指针指向表的第一个结点D不带头结点

23、的循环单链表，有一个链表指针指向表中某个结点除第一个结点外 17设指针rear 指向带头结点的循环单链表的尾指针，假设要删除链表的第一个元素结点，正确的操作是。A s=rear; rear=rear->next;Brear=rear->next;Crear=rear->next->next;D s=rear->next->next; rear->next->next=s->next; 18设有两个长度为n 个单链表， 以 h1 为头指针的链表是非循环的，以 h2 为尾指针的链表是循环的，那么。A 在两个链表上删除第一个结点的操作，其时间复杂

24、度均为(1)B在两个链表的表尾插入一个结点的操作，其时间复杂度均为(n)C循环链表要比非循环链表占用更多的存储空间D循环链表要比非循环链表占用更少的存储空间 19使用双链表存储线性表，其优点是可以。专业资料整理WORD格式10专业资料整理WORD格式A 提高查找速度B更方便数据的插入和删除C节约存储空间D很快回收存储空间 20 与单链表相比，双链表的优点之一是。A 插入和删除操作更简单B可以进展随机访问C可以省略表头指针或表尾指针D访问其后相邻结点更灵活 21 带头结点的循环双链表L 为空表的条件是。A L->next->prior=NULLB L->prior=LCL-&g

25、t;next=LDB和 C都对 22 在循环双链表的p 所指结点后插入 s所指结点的操作是。A p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;Bp->next=s; p->next->prior=s; s->prior=p; s->next=p->next;Cs->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D s->prior=p; s->ne

26、xt=p->next; p->next->prior=s; p->next=s; 23 在双链表中指针pa 所指结点后面插入 pb 所指结点，执行的语句序列是 。 pb->next=pa->next;pb->prior=pa; pa->next=pb;pa->next->prior=pb;A B CD 24在一个双链表中，删除结点p 的操作是。A p->prior->next=p->next; p->next->prior=p->prior;Bp->prior=p->prior->

27、prior; p->prior->prior=p;Cp->next->prior=p; p->next=p->next->next;D p->next=p->prior->prior; p->prior=p->prior->prior;应用题（ 25 单链表设置头结点的作用是什么？（ 26 线性表的顺序存储构造具有三个弱点：其一，插入或删除操作需要移动大量元素；其二， 由于难以估计， 必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三， 表的容量难以扩大。 试问，线性表的存储构造是否能够抑制上述三个弱点？（

28、 27假设频繁地对一个线性表进展插入和删除操作，该线性表采用什么存储构造比较好？ 28设 n 表示线性表中的元素个数，P 表示指针所需的存储单元大小，E 表示存储数据元素所需的存储单元大小，那么使用单链表存储方式存储该线性表需要多少存储空间不考虑头结点？算法设计题专业资料整理WORD格式11专业资料整理WORD格式（ 29 设计算法依次打印单链表中每个结点的数据信息。（ 30 求单链表的长度。 31设计算法将值为x 的结点插入到不带头结点的单链表L 中值为 k 的结点之前，假设找不到值为k 的结点，那么将x 插入到链表的末尾。 32判断非空单链表是否递增有序。 33非空线性链表由list 指出

29、，结点构造为data， link 。请编写算法，将链表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。 34给定一个带头结点的单链表，设head 为头指针，设计算法按递增次序输出单链表中各结点的数据元素， 并释放结点所占的存储空间 要求： 不允许使用数组作辅助空间。 35非空线性链表由list 指出， 设计算法交换p 所指结点与其后续结点在链表中的位置设p 所指结点不是链表的最后一个结点。（ 36 设计算法实现将单链表就地逆置。（ 37 头插法建立单链表。（ 38 尾插法建立单链表（ 39 复制一个单链表。（ 40 设计算法实现将单链表就地逆置。 41在一个有序单链表假设从小到

30、大排列中插入一个元素值为x 的结点， 使得插入后单链表仍然有序。（ 42 设单链表以非递减有序排列，设计算法实现在单链表中删去值一样的多余结点。（ 43单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于 mink 且小于 maxk 的所有元素，并释放被删结点的存储空间。 44有两个整数序列 A=(a1，a2，, ， am)和 B=(b1， b2，, ， bn) 已经存入两个单链表中，设计算法判断序列 B 是否是序列 A 的子序列。（ 45 设线性表 C=(a1，b1，a2，b2，, ， an，bn)采用带头结点的单链表存储，设计算法将表 C 拆分为两个线性表 A 和 B ，使得 A=

31、(a 1， a2，, ， an)， B=(b 1，b2，, ，bn)。专业资料整理WORD格式12专业资料整理WORD格式（ 46 有两个递增有序的单链表la 和 lb，设计算法将这两个单链表合并为一个有序链表。（ 47 有两个有序的单链表， 一个表为升序， 另一个表为降序， 设计算法将这两个链表合并为一个有序链表。（ 48单链表 A 和 B 的数据设为整型递增有序，设计算法利用原有结点，将表 A 中与表 B 具有一样值的结点删除， 将表 B 中与原表 A 不同值的结点存入表 A 中，并保持表 A 的递增有序。（ 49 设计算法将循环单链表就地逆置。（ 50 L 为单链表的头结点地址， 表中共

32、有 m m 3个结点， 从表中第 i 个 1 i m结点起到第 m 个结点构成一个局部循环链表。设计算法将这局部循环链表中所有结点顺序完全倒置。 51假设在长度大于1 的循环单链表中，即无头结点也无头指针，s 为指向链表中某个结点的指针，试编写算法删除结点s的前驱结点。（ 52 设循环单链表 L1 ，对其遍历的结果是： x1， x2， x3，, ， xn-1， xn。请将该循环链表拆成两个循环单链表 L1 和 L2 ，使得 L1 中含有原 L1 表中序号为奇数的结点且遍历结果为： x1，x3，, ；L2 中含有原L1 表中序号为偶数的结且遍历结果为：, ，x4， x2。（ 53一单链表中的数据

33、元素含有三类字符：字母、数字和其他字符。 试编写算法，构造三个循环单链表，使每个循环链表中只含同一类字符。 54有两个循环链表tail1 和 tail2 tail1 和 tail2 分别指向循环链表的尾指针，编写算法将循环链表tail2 到循环链表tail1 之后，并使后的链表仍是循环链表。（ 55 p 指向循环单链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表 a1，a2，, ， an-1，an，改造成 a1，a2，, ， an-1，an，an-1，, ， a2，a1。（ 56 判断带头结点的循环双链表是否对称。 57设计算法实现双链表中第i 个结点的前面插入一个值为x 的结点。

34、 58非空循环双链表 head 的存储构造为：Struct DNode TElem info;Struct DNode *left;Struct DNode *right;专业资料整理WORD格式13专业资料整理WORD格式;设计算法实现从链表中删除指针p 所指结点的前驱结点假设该结点存在。 59非空双链表由d 指出，结点构造为priordatanext ，请设计算法将链表中数据值最大 假定唯一 的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。 60设计算法实现将双链表中结点p 与其后继结点互换位置。 61设有一个双链表，每个结点中除了有prior 、 data 和 next 三个

35、域外，还有一个访问频度域freq ，在链表被起用之前，其值均初始化为零，每当在双链表上进展一次 LOCATE 运算时，令元素值为 x 的结点中 freq 域的值增 1，并使此链表中结点保持频度递减的顺序排列， 以便使频繁访问的结点总是靠近表头。 编写算法实现符合上述要求的 LOCATE 算法。专业资料整理WORD格式14专业资料整理WORD格式5 静态链表选择题 1静态链表中指针表示的是。A 下一结点在内存中的地址B下一元素在数组中的下标C左、右孩子的存储位置D左、右孩子的地址 2以下说法错误的选项是。静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第i 个元素的时间与 i 无关

36、静态链表中能容纳的元素个数在定义表时必须是确定的静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动A ，B C，D 3用数组 r 存储静态链表， 结点的 next 域指向后继， 工作指针 j 指向链中某结点，使 j 沿链移动的操作为。A j=rj.nextB j=j+1Cj=j->nextD j=rj->next 4线性表的静态链表存储与顺序存储相比，优点是。A 所有根本操作的算法实现简单B便于随机存取C便于插入和删除D便于利用零散的存储空间 5以下列图所示数组中以静态链表形式存储了一个线性表，设头指针为a0.link ，那么该线性表的元素依次为。下标012345678d

37、ata606340457425link4376201A 60， 63，40， 45，74， 25B 45， 63， 25， 60， 40， 74C74， 25，45， 60， 40， 63D 25，45， 60，40， 63， 74专业资料整理WORD格式15专业资料整理WORD格式6 线性表综合选择题 1下面关于线性表的表达中，错误的选项是。A 线性表采用顺序存储，必须占用一片连续的存储单元B线性表采用顺序存储，便于进展插入和删除操作C线性表采用存储，不必占用一片连续的存储单元D线性表采用存储，便于插入和删除操作 2假设某线性表中最常用的操作是取第i 个元素和找第i 个元素的前驱，那么采用存

38、储方法最节约时间。A 顺序表B 单链表C双链表D循环单链表 3假设链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，那么采用存储方法最节约时间。A 单链表B循环双链表C循环单链表D带尾指针的循环单链表 4设线性表有n 个元素，以下操作中， 在顺序表上实现比在链表上实现的效率更高。A 输出第i 1 i n个元素值B交换第1 个和第 2 个元素的值C顺序输出所有n 个元素D查找与给定值x 相等的元素在线性表中的序号 5如果对于具有n n 1个元素的线性表的根本操作有4 种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素的后面插入新元素。那么最好使用。A

39、 只设尾指针的循环单链表B只设尾指针的非循环单链表C只设头指针的循环双链表D同时设置头指针和尾指针的循环单链表应用题 6请比较线性表的两种根本的存储构造顺序表和单链表。 7举例说明对一样的逻辑构造， 同一种运算在不同的存储方式下实现，算法的效率不同。 8如果某线性表中数据元素的类型不一致，但是希望能根据下标随机存取每个元素，请为这个线性表设计一个适宜的存储构造。 9线性链表有哪几种常见的变形？各有何特点？专业资料整理WORD格式16专业资料整理WORD格式kk n个单词。算法设计题（ 10 用顺序表表示集合，设计算法实现集合的求交集运算。（ 11 用顺序表表示集合，设计算法实现集合的求并集运算

40、。（ 12 用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。（ 13 假定以有序表表示集合，设计算法判断两个给定集合是否相等。 14设两个单链表L1 和 L2 分别表示两个集合，设计算法判断L1 是否是 L2 的子集。（ 15两个不带头结点的单链表A 和 B 分别表示两个集合，并且其元素值递增有序，求 A 、 B 的交集 C，并以同样的递增形式存储，要求尽可能节省时间。（ 16 在某商店的仓库中， 对电视机按其价格从低到高建立一个单链表，链表的每个结点指出同样价格的电视机的台数。现有m 台价格为n 元的电视机入库，请编写算法完成仓库的进货管理。 17从键盘输入n 个英语单词

41、，输入格式为n， w1，w 2，, ， w n，其中 n 表示随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，那么只在链表上只保存一个；统计单词重复出现的次数，然后输出次数最多的前 18一元稀疏多项式可以采用单链表形式存储，设计算法完成A(x)+B(x) ，其中 A(x)和 B(x) 均为稀疏的一元多项式，要求利用原表的存储空间。 19假设用不带头结点的单链表表示八进制数，例如，八进制数536 可以表示成三个结点的链表。 要求写一个函数Add ，该函数有两个参数P 和 Q，分别指向表示八进制数的链表，执行函数调用Add(P,Q) 后，将返回表示八进制数P 加八进制数Q所

42、得结果数的链表。 20约瑟夫环问题：设有编号为1， 2，, ， n 的 n n 0个人围成一个圈，每个人持有一个密码m m 1，从第1 个人开场报数，报到m 时停顿报数，报m 的人出圈，再从他的下一个人起重新报数，报到m 时停顿报数，报m 的出圈， , ，如此下去，直到所有人全部出圈为止。当任意给定n 和 m 后，设计算法求n 个人出圈的次序。 21编写算法，完成下述要求：建立一个链表用于存放输入的二进制数，链表中的每个结点的data 域存放一个二进制位。在此链表上实现对二进制数加1 的运算，并输出运算结果。 22有一个不带头结点的单链表h，通过遍历链表将链表中所有的方向逆转，专业资料整理WORD格式17