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

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

2、数据的（）。A.树B.图C.线性表 D.集合（5） 在存储数据时，通常不仅要存储各数据元素的值，还要存储（）。A.数据的处理方法B.数据元素的类型C.数据元素之间的关系D.数据的存储方法文案(6) 在存储结构中，要求( )。A.每个结点占用一片连续的存储区域C.结点的最后一个域是指针类型(7) 下列说法不正确的是()。A.数据元素是数据的基本单位C.数据可由若干个数据项构成B.所有结点占用一片连续的存储区域D .每个结点有多少个后继就设多少个指针B.数据项是数据中不可分割的最小单位D.数据元素可由若干个数据项构成(8) 以下与数据的存储结构无关的术语是()。A.循环队列B.链表C.散列表 D.

3、栈(9) 以下术语属于逻辑结构的是()。A.顺序表 B.哈希表C.有序表 D.单链表(10) 可以用()定义一个完整的数据结构。A.数据元素B.数据对象C.数据关系D.抽象数据类型(11) 对于数据结构的描述，下列说法中不正确的是()。A.相同的逻辑结构对应的存储结构也必相同B.数据结构由逻辑结构、存储结构和基本操作三方面组成C.数据结构基本操作的实现与存储结构有关D.数据的存储结构是数据的逻辑结构的机实现(12) 以下关于存储结构的叙述中，()是不正确的。A.结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不一定相邻C.可以通过计算得到第i个结点的存储地址

4、D.插入和删除操作方便，不必移动结点(13) 可以用()、数据关系和基本操作定义一个完整的抽象数据类型。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) 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区另I。(16) 说明数据的逻辑结构和存储结构之间的关系。(17) 抽象数据类型的主要特点是什么？数据类型和抽象

5、数据类型的关系如何？使用抽象数据类型的主要好处是什么?1算法和算法分析选择题(1) 算法指的是()。A.对特定问题求解步骤的一种描述，是指令的有限序列B.计算机程序C.解决问题的计算方法D.数据处理(2) 下面()不是算法所必须具备的特性。C.高效性 D.可行性)等特性。B.可行性、确定性和有穷性D.易读性、稳定性和健壮性A.有穷性 B.确切性(3) 算法必须具备输入、输出和(A.可行性、可移植性和可扩充性C.确定性、稳定性和有穷性(4) 算法应该具有确定性、可行性和有穷性，其中有穷性是指()。A.算法在有穷的时间终止B.输入是有穷的C.输出是有穷的D.描述步骤是有穷的(5) 当输入非法错误时

6、，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果，这称为算法的()。A.可读性 B.健壮性C.正确性 D.有穷性（6） 算法分析的目的是（A.找出数据结构的合理性C.分析算法的效率以求改进E.空间性能和时间性能G.可读性和文档性（7） 算法的时间复杂度与（A.问题规模C.编译程序的质量）,算法分析的两个主要方面是（）。B.研究算法中输入和输出的关系D.分析算法的易读性和文档性F.正确性和简明性H.数据复杂性和程序复杂性）有关。B.计算机硬件性能D.程序设计语言（8） 算法的时间复杂度与（）有关。A.问题规模B.待处理数据的初态C.算法的易读性D. A 和 B（9） 某算法的时间复

7、杂度是。（n2）,表明该算法（ ）。A.问题规模是n2C.执行时间与n2成正比B.执行时间等于n2D .问题规模与n2成正比(10) 下面说法错误的是（ ）。算法原地工作的含义是指示不需要如何额外的辅助空间在相同的规模n下，复杂度。(n)的算法在时间上总是优于复杂度。(2n)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低(11) 算法for (i=n-1; i>=1; i-)for (j=1; j<=i; j+)if (aj>aj+1) aj 与 aj+1交换；其中n为正整数，则最后一行语句的频度(执行次数)在最坏

8、情况下是()。A. O(n)B. Qnlog 2n)C. Qn3)D. Qn2)(12) 算法的时间复杂度属于一种()。A.事前统计的方法B.事先分析估算的方法C.事后统计的方法D.事后分析估算的方法(13) 设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlog 2n+200n+500,则该算法的时间复杂度是()。A. 0(1)B. C(n)C. Qnlog 2n)D. Qnlog 2n+n)(14) 假设时间复杂度为。(n2)的算法在有200个元素的数组上运行需要3.1ms ,则在有400个元素的数组上运行需要() ms。A. 3.1B. 6.2C. 12.4D. x (无法

9、确定)(15) 下列程序段加下划线的语句执行()次。for (m=0,i=1; i<=1; i+)for (j=1; j<=2*i; j+)m=m+1 ;A. n2B. 3nC. n(n+1)D, n3应用题(16) 将下列函数按它们的n-8时的无穷大阶数，从小到大排列。n , n-n 3-7n 5, nlog 2n , 2n/2 , n3, log 2n, n1/2 +log 2n , (3/2) n, n! , n2+log 2n(17) 分析以下程序段，并用大。记号表示其执行时间。 i=1;k=0;while (i<n-1)k=k+10*i;i+; i=1;j=0;wh

10、ile (i+j<=n)if (i>j) j+;else i+; for (i=1;i<=n;i+)for (j=1;j<=i;j+)for (k=1;k<=j;k+)x+; i=1;k=0;dok=k+10*i;i+; while (i<=n) y=0;while (y+1)*(y+1)<=n)y=y+1 for (i=0;i<n;i+)for (j=0；j<m；j+)a皿 j=0；(18) 有实现同一功能的两个算法A1和A2,其中A1的时间复杂度为 Ti=Q2n),A2的时间复杂度为T2=Qn2),仅就时间复杂度而言，请具体分析这两个算

11、法哪一 个好。综合应用题(19) 设n是偶数，且有程序段：for (i=1;i<=n;i+)if (2*i<=n)for (j=2*I;j<=n;j+)y=y+i*j;则语句y=y+i*j的执行次数是多少？要求列出计算公式。(20) 斐波那契数列Fn定义如下：Fo=0 , F1=1 ,，Fn=Fn-1 +F n-2n=2 , 3,请就此斐波那契数列，回答下列问题。 在递归计算Fn的时候，需要对较小的 Fn-1 , Fn-2,，F1 , Fo精确计算多少次？ 用大。表示法给出递归计算时递归函数的时间复杂度是多少？(21 ) 运算是数据结构的一个重要方面。举例说明两个数据结构的逻

12、辑结构和存储方式完全相同，只是对于运算的定义不同，因而具有不同的特性， 则这两个数据结构是不同的。(22) 针对给定的实际问题建立数据结构时，应从哪些方面考虑。2线性表的逻辑结构选择题(1) 线性表是具有 门个()的有限序列。A.数据B.字符C.数据元素D.数据项(2) 线性表是()。A. 一个有限序列，可以为空C. 一个无限序列，可以为空B. 一个有限序列，不能为空D. 一个无限序列，不能为空(3) 关于线性表，下列说法中正确的是()。A.线性表中每个元素都有一个直接前驱和一个直接后继B.线性表中的数据元素可以具有不同的数据类型C.线性表中数据元素的类型是确定的D.线性表中任意一对相邻的数据

13、元素之间存在序偶关系(4) ()是一个线性表。A.由n个实数组成的集合B.由所有实数组成的集合C.由所有整数组成的序列D.由n个字符组成的序列3顺序线性表选择题(1) 已知一维数组 A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144 ,则第一个元素的地址是()。A. 108B. 180C. 176D. 112(2) 在长度为n的线性表中查找值为 x的数据元素的时间复杂度为()。A. 0(0)B. 0(1)C. Qn)D. Qn2)(3) 在一个长度为n的线性表的第i (14Wn+1 )个元素之前插入一个元素， 需向后移动()个元素，删除第i (144)个元素时，需向前移动(

14、)个元素。A.n-iB.n-i+1C. n-iD. n-i+1(4) 线性表的顺序存储结构是一种()的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取(5) 顺序存储结构的优点是()。A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示(6) n个结点的线性表采用数组实现，算法的时间复杂度是。(1)的操作是( )。A.访问第i个结点(iwiwn)和求第i个结点的直接前驱(2VWn)B.在第i个结点后插入一个新结点(iwiwn)C.删除第i个结点(1 4知)D.以上都不对(7) 对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为()。A.O(

15、n)、Q(n)B.Q(n)、0(1)C.0(1)、O(n)D.0(1)、Qi)(8) 顺序表的插入算法中，当 n个空间已满时，可再申请增加分配 m个空间，若申请失败，则说明系统没有()可分配的存储空间。A. m个B. m个连续的 C. n+m 个 D. n+m 个连续的应用题(9) 设A是一个线性表(a1，a2,，an),采用顺序存储结构，则在等概论的前 提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间(14Wn)的概率为(n-i ) / (n (n-1 ) /2 ),则平均每插入一个元素所移动的元 素个数是多少？(10) 设n表示线性表中的元素个数，E表示存储数

16、据元素所需要的存储单元大小,D表示可以在数组中存储线性表的最大元素个数(D>n),则使用顺序存储方式存储线性表需要多少存储空间？(11) 在什么情况下线性表使用顺序存储比较好？算法设计题(12) 试以顺序表作存储结构，实现线性表就地逆置。(13) 设计算法判断给定字符串是否是回文。所谓回文是正读和反读均相同的字符 串，例如abcba或abba是回文，而 abcda不是回文。(14) 设计一个时间复杂度为。(n)的算法，实现将数组 An中所有元素循环左移k个位置。(15) 已知数组 An中的元素为整型，设计算法将其调整为左右两部分，左边所有 元素为奇数，右边所有元素为偶数，并要求算法的时间

17、复杂度为。(n)。(16) 假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。(17) 顺序存储的线性表 A,其数据元素为整型，设计算法将A拆成B和C两个表， 使A中值大于0的元素存入表B,值小于0的元素存入表 C,要求B和C不另外 设置存储空间而利用 A的空间。(18) 已知顺序表L中的元素递增有序排列，设计算法将元素x插入到表L中并保持表L仍递增有序。(19) 设计一个高效算法，在顺序表中删除所有元素值为x的元素，要求空间复杂度为 0(1)。(20) 设计算法实现从顺序表L中删除所有值在x和y之间的所有元素，要求时间性能复杂度为。，空间性能为。(1)。(21) )设计算法

18、删除顺序表中重复的元素，要求算法移动元素的次数较少并使剩余元素间的相对次序保持不变。(22) 给定n个记录的有序序列 An和m个记录的有序序列 Bm,将它们归并为 一个有序序列，存放在 Cn+m中，试写出这一算法(假设A、B和C均为升序序歹U)。4线性链表选择题(1) 线性表的存储结构是一种()的存储结构。A.随机存取B.顺序存取(2) 线性表采用存储时，其(A.地址必须是连续的C.地址一定是不连续的(3) 链表不具有的特点是(A.可随机访问任一元素C.不必事先估计存储空间C.索引存取D.散列存取B.部分地址必须是连续的D.地址连续与否均可以B.插入、删除不需要移动元素D.所需空间与线性表长度

19、成正比(4) 在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。A. 0(1)B. O(n)C. O(n2)D. Qnlog 2n1)(5) 对于n个元素组成的线性表，建立一个单链表的时间复杂度是()。A. 0(1)B. O(n)C. O(n2)D. Qnlog 2n1)(6) 对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是()。A. 0(1)B. O(n)C. O(n2)D. Qnlog 2n1)(7) 在单链表中删除指针p所指结点的后续结点，则执行()。A. p->next=p->next->nextB. p->next=p-&g

20、t;nextC. p=p->next->nextD.p=p->next;p->next=p->next->next(8) 在一个单链表中，已知 q所指结点是p所指结点的直接前驱，若在 q和p之间插入s所指结点，则执行()操作。A. s->next=p->next; p->next=s;B. q->next=s; s->next=p;C. p->next=s->next; s->next=p;D. p->next=s; s->next=q(9) 在一个长度为n (n>1 )的带头结点的单链表h上

21、，另设有尾指针r指向尾结点，执行( )操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表的最后一个元素后插入一个新元素(10) 在单链表中附加头结点的目的是为了()。A .保证单链表中至少有一个结点B.标识单链表中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储(11) 将长度为n个单链表在长度为m的单链表之后的算法，其时间复杂度是()。A. 0(1)B. Qn)C. O(m)D. O(n+m)(12) 循环单链表的主要优点是( )。A.不再需要头指针了B.从表中任一结点出发都能扫描到整个链表C.已知

22、某个结点的位置后，能够容易找到它的直接前驱D.在进行插入、删除操作时，能更好地保证链表不断开(13) 将线性表(a1，a2,，an)组织为一个带头结点的循环单链表，设 H为链表的头指针，则链表中最后一个结点的指针域中存放的是()。A.变量H的地址B.变量H的值C.元素a1的地址D.空指针(14) 非空的循环单链表 L的尾结点p满足()。A. p=NULL B. p->next=NULL C. p->next=LD. p=L(15) 若要在。(1)的时间实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分别指向()。A.各自的头结点B.各自的尾结点C.各自的第一个元素结点

23、D. 一个表的头结点，一个表的尾结点(16) 设线性表非空，（）可以在。（1）的时间在表尾插入一个新结点。A.带头结点的单链表，有一个链表指针指向头结点B.带头结点的循环单链表，有一个链表指针指向头结点C.不带头结点的单链表，有一个链表指针指向表的第一个结点D.不带头结点的循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）(17) 设指针rear指向带头结点的循环单链表的尾指针，若要删除链表的第一个元素结点，正确的操作是（ ）。A. s=rear; rear=rear->next;B. rear=rear->next;C. rear=rear->next->n

24、ext;D. s=rear->next->next; rear->next->next=s->next;(18) 设有两个长度为 n个单链表，以hl为头指针的链表是非循环的，以 h2为尾指针的链表是循环的，则（）。A.在两个链表上删除第一个结点的操作，其时间复杂度均为。（1）B.在两个链表的表尾插入一个结点的操作，其时间复杂度均为。（n）C.循环链表要比非循环链表占用更多的存储空间D.循环链表要比非循环链表占用更少的存储空间(19) 使用双链表存储线性表，其优点是可以（）。A.提高查找速度B.更方便数据的插入和删除C.节约存储空间D.很快回收存储空间(20) 与单

25、链表相比，双链表的优点之一是A .插入和删除操作更简单C.可以省略表头指针或表尾指针(21 )带头结点的循环双链表A. L->next->prior=NULLC. L->next=L)°B.可以进行随机访问D.访问其后相邻结点更灵活L为空表的条件是()。B. L->prior=LD. B和C者B对(22) 在循环双链表的p所指结点后插入 s所指结点的操作是( )。A. p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;B. p->next=s; p->

26、;next->prior=s; s->prior=p; s->next=p->next;C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;(23) 在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是()。 pb->next=pa->next; pb->prior=pa; pa-&g

27、t;next=pb; pa->next->prior=pb;A.B.C.D.(24) 在一个双链表中，删除结点p的操作是()。A. p->prior->next=p->next; p->next->prior=p->prior;B. p->prior=p->prior->prior; p->prior->prior=p;C. p->next->prior=p; p->next=p->next->next;D. p->next=p->prior->prior; p->

28、;prior=p->prior->prior;应用题(1) )单链表设置头结点的作用是什么？(2) )线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。 试问，线性表的存储结构是否能够克服上述三 个弱点？(3) )若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？(28) 设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间(不考虑头结点)？算法设计

29、题(29) 设计算法依次打印单链表中每个结点的数据信息。(30) 求单链表的长度。(31) ) 设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前,若找不到值为k的结点，则将x插入到链表的末尾。(32) ) 判断非空单链表是否递增有序。(33) 已知非空线性链表由list指出，结点结构为(data , link )。请编写算法，将 链表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。(34) 给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求：不允许使用数组作辅助空间)。(35) 已知非空

30、线性链表由list指出，设计算法交换p所指结点与其后续结点在链表 中的位置(设p所指结点不是链表的最后一个结点)。(36) 设计算法实现将单链表就地逆置。(37) 头插法建立单链表。(38) 尾插法建立单链表(39) 复制一个单链表。(40) ) 设计算法实现将单链表就地逆置。(41) 在一个有序单链表(假设从小到大排列)中插入一个元素值为 x的结点，使得插入后单链表仍然有序。(42) ) 设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结 点。(43) 已知单链表中各结点的元素值为整型且递增有序，设计算法删除表于 mink且小于maxk的所有元素，并释放被删结点的存储空间。(

31、44) 有两个整数序列 A=(a i, a2,，am)和B=(b 1, b2,，bn)已经存入两个单 链表中，设计算法判断序列B是否是序列A的子序列。(45) 设线性表 C=(ai, bi, a2, b2,，an, bn)采用带头结点的单链表存储，设计算法将表C拆分为两个线性表 A和B,使得A=(a i, a2,，an), B=(b i, b2,bn)。(46) 有两个递增有序的单链表la和lb ,设计算法将这两个单链表合并为一个有序链表。(47) 有两个有序的单链表， 一个表为升序，另一个表为降序，设计算法将这两个链 表合并为一个有序链表。(48) 已知单链表 A和B的数据(设为整型)递增有

32、序，设计算法利用原有结点，将表A中与表B具有相同值的结点删除，将表B中与原表A不同值的结点存入表A中，并保持表A的递增有序。(49) ) 设计算法将循环单链表就地逆置。(50) 已知L为单链表的头结点地址，表中共有 m (m>3)个结点，从表中第i个(1 vivm)结点起到第 m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。(51) 假设在长度大于1的循环单链表中，即无头结点也无头指针，s为指向链表中 某个结点的指针，试编写算法删除结点s的前驱结点。(52) 设循环单链表 L1 ,对其遍历的结果是：X1, X2, X3,，Xn-1 , Xn。请将该循环链表拆

33、成两个循环单链表L1和L2 ,使得L1中含有原L1表中序号为奇数的结点且遍历结果为：xi ,X3,;L2中含有原L1表中序号为偶数的结且遍历结果为：,X4 , X 2。(53) 已知一单链表中的数据元素含有三类字符：字母、数字和其他字符。 试编写算法，构造三个循环单链表，使每个循环链表中只含同一类字符。(54) 有两个循环链表taill和tail2 (taill和tail2分别指向循环链表的尾指针)，编写算法将循环链表tail2到循环链表taill之后，并使后的链表仍是循环链表。(55) 已知p指向循环单链表最后一个结点的指针，试编写只包含一个循环的算法，将线性表(ai, a2,，an-i ,

34、 an,)改造成(ai, a2,，an-i , an, an-i ,，a2, ai)。(56) 判断带头结点的循环双链表是否对称。(57) 设计算法实现双链表中第i个结点的前面插入一个值为x的结点。(58) 已知非空循环双链表head的存储结构为：Struct DNode TElem info;Struct DNode *left;Struct DNode *right;；设计算法实现从链表中删除指针p所指结点的前驱结点(假设该结点存在)。(59) 已知非空双链表由d指出，结点结构为(priordatanext ),请设计算法将链表中数据值最大(假定唯一)的那个结点移至链表的最前面。要求不得额

35、外申请新 的双链表结点。(60) 设计算法实现将双链表中结点p与其后继结点互换位置。(61) 设有一个双链表，每个结点中除了有prior、data和next三个域外，还有一个访问频度域freq ,在链表被起用之前，其值均初始化为零，每当在双链表上进 行一次LOCATE运算时，令元素值为 x的结点中freq域的值增1 ,并使此链表中 结点保持频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的 LOCATE算法。5静态链表选择题(1) 静态链表中指针表示的是( )。A.下一结点在存中的地址B.下一元素在数组中的下标C.左、右孩子的存储位置D.左、右孩子的地址(2) 以

36、下说法错误的是( )。i个元素的j指向链中某结静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第时间与i无关静态链表中能容纳的元素个数在定义表时必须是确定的静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动A.，B.C.， D.(3) 用数组r存储静态链表，结点的 next域指向后继，工作指针点，使j沿链移动的操作为()。A. j=rj.nextB. j=j+1C. j=j->nextD. j=rj->next(4) 线性表的静态链表存储与顺序存储相比，优点是()。A.所有基本操作的算法实现简单B.便于随机存取C.便于插入和删除D.便于利用零散的存储空间(5

37、) 下图所示数组中以静态链表形式存储了一个线性表，设头指针为a0.link ,则该线性表的元素依次为()。A.60, 63 , 40 ,74C. 74 , 25, 45, 60, 40 , 63D . 25 , 45, 60, 40 , 63 , 746线性表综合选择题(1)下面关于线性表的叙述中，错误的是()。A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用存储，不必占用一片连续的存储单元D.线性表采用存储，便于插入和删除操作(2) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用()存储方法最节约时间。A.顺序

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

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

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

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

42、问题：设有编号为1, 2,，n的n (n>0)个人围成一个圈，每个人持有一个密码 m (mwl),从第1个人开始报数，报到 m时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，,如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。(21) 编写算法，完成下述要求：建立一个链表用于存放输入的二进制数，链表中的每个结点的data域存放一个二进制位。在此链表上实现对二进制数加1的运算，并输出运算结果。(22) 有一个不带头结点的单链表h,通过遍历链表将链表中所有的方向逆转，算法如下，请在空格处填写正确的语句。void Inve

43、rse(&h) if ()return;p=h->next; pr=NULL;while ()h->next=pr;pr=h;h=p; (23) 设两个带头结点的单链表 A和B,表中结点的数据为整型， 下面算法产生表 A和表B的并集并以表 C存储，请填写算法中空白处的语句，完成其功能。7栈的基本概念选择题(1) 经过以下栈运算后，x的值是()。InitStack(s) , Push(s,a) , Push(s,b) , Pop(s,x) , GetTop(s,x)A. aB. bC. 1D. 0(2) 经过以下栈运算后，StackEmpty(s)的值是()。InitStac

44、k(s) , Push(s,a) , Push(s,b) , Pop(s,x) , Pop(s,y)A. aB. bC. 1D. 0(3) ()不是栈的基本运算。A.删除栈顶元素B.删除栈底元素C.判断栈是否为空D.将栈置为空栈(4) 设有一个空栈，栈顶指针为 1000H (十六进制，下同)，每个元素需要1个单位的存储空间， 则执行 PUSH , PUSH , POP, PUSH , POP, PUSH , POP, PUSH 操作后，栈顶指针值为()。A. 1002H B. 1003HC. 1004HD. 1005H(5) 一个栈的入栈序列是1, 2, 3, 4, 5,则栈的不可能的输出序列

45、是()。A. 5, 4, 3, 2, 1B. 4, 5, 3, 2 , 1C. 4 , 3, 5, 1 , 2D. 1, 2, 3, 4, 5(6)若一个栈的输入序列是 1, 2, 3,，n,输出序列的第一个元素是 n,则第i个输出元素是()。A.不确定 B. n-iC. n-i-1D . n-i+1若一个栈的输入序列是 1, 2, 3,，n,其输出序列是pi, p2,，pn,若pi=3 ,贝U P2 的值()A. 一定是2 B. 一定是1C.不可能是1 D.以上都不对(8)若一个栈的输入序列是 P1, P2,，pn,其输出序列是1, 2, 3,，n,若P 3=1 ,贝U p 1 的值()。C

46、.不可能是2 D.不可能是3A.可能是2 B, 一定是2(9) 当字符序列t3_依次通过栈，车出长度为 3且可用作C语言标识符的序列有()。A. 4个B. 5个C. 3个D.6个应用题(10) 设有一个栈，元素进栈的次序为A, B, C, D, E,能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。C, E, A, B, DC, B, A, D, E(11) 在操作序列 push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？ ( push(k)表示整数k入栈，pop表示栈 顶元素出栈。)(12) 设元素1

47、、2、3、P、A依次经过一个栈，进栈次序为123PA ,在栈的输出序列中，有哪些序列可作为C+程序设计语言的变量名。(13) 如果进栈序列为 A、B、C、D,则可能的出栈序列是什么？算法设计题(14) 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出 栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIO D. IIIOOIOO通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ,否则返回false (假定被判定的操作序

48、列已存入一维数组中)。8顺序栈选择题（1） 在一个具有n个单元的顺序栈中，假定以地址低端（即下标为 0的单元）作为栈底，以top作为栈顶指针，当出栈时，top的变化为（）。A.不变B. top=0C. top-1D. top=top+1（2） 设数组Sn作为两个栈S1和S2的存储空间，对任何一个栈只有当 Sn全满 时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。A. S1的栈底位置为0, S2的栈底位置为n-1B. S1的栈底位置为0, S2的栈底位置为n/2C. S1的栈底位置为0, S2的栈底位置为nD. S1的栈底位置为0, S2的栈底位置为1（3） 为了增加存空间的利用率和减

49、少溢出的可能性，两个栈共享一片连续的存空间时，应将两栈的栈底分别设在这片存空间的两端，这样，当（）时才产生上溢。A.两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇D.两个栈均不空，且一个栈的栈顶到达另一个栈的栈底（4） 两个栈共享一个数组空间的好处是（）。A.减少存取时间，降低发生上溢的可能性B.节省存储空间，降低发生上溢的可能性C.减少存取时间，降低发生下溢的可能性D.节省存储空间，降低发生下溢的可能性算法设计题（5） 假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出 栈的操作序列可表示为仅有I和O组成的序列，

50、称可以操作的序列为合法序列，否则称为非合法序列。下面所示的序列中哪些是合法的？通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true ,否则返回false (假定被判定的操作序列已存入一维数组中)。（6） 下面的算法将一个整数e压入到堆栈S,请在空格处填上适当的语句实现该操作。Typedef struct int *base;int top;int stacksize;SqStack;int Push(SqStack S,int e) if () S.base=(int *)realloc(S.base,(S.stacksize+1)*sizeof(int);if ()

51、printf ( "Not Enough Memory!n ");retuan 0;S.top= ®S.stacksize= ®®retuan 1;选择题9链栈(1)向一个栈顶指针为A. h->next=s;B. s->next=h;h的带头结点的链栈中插入指针s所指的结点时，应执行C. s->next=h; h->next=s;D. s->next=h->next; h->next=s;(2)从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行()。A.x=top; top=top-

52、>next;B. x=top->data;C.top=top->next; x=top->data;D. x=top->data; top=top->next;10队列的基本概念选择题(1) 队列的“先进先出”特性是指()。A.最后插入队列中的元素总是最后被删除B.当同时进行插入、删除操作时，总是插入操作优先C.每当有删除操作时，总要先做一次插入操作D.每次从队列中删除的总是最早插入的元素(2) 允许对队列进行的操作有()。A.对队列中的元素排序B.取出最近入队的元素C.在队头元素之前插入元素D.删除队头元素(3) 一个队列的入队顺序是 1、2、3、4,则队

53、列的输出顺序是( )。A. 4321B. 1234C. 1432D, 3241选择题11顺序队列(1)循环队列存储在数组 A。m中，则入队时的操作为(A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD . rear=(rear+1) mod (m+1)(2) 若用一个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3,则从队列中删除一个元素，再增加两个元素后，rear和front的值分别为()。A. 1 和 5 B. 2 和 4C. 4 和 2D . 5 和 1(3) 已知循环队列的存储空间为数组 A21 , front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和rear的值分别是8和3,则该队列的长度为()。A. 5B. 6C. 16D. 17(4)如图所示为一个元素类型为字符型的环形队列,如果front指向队头元素的前012345678911111111112220123456789012ThefloweRIsbeauTiful一个位置，rear指向队尾元