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

数据结构得基本概念选择题（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每个结点有多少个后继就设多少个指针（7） 下列说法不正确得就是（ ）。A数据元素就是数据得基本单位B数据项就是数据中不可分割得最小单位C数据可由若干个数据项构成D数据元素可由若干个数据项构成（8） 以下与数据得存储结构无关得术语就是（ ）。A循环队列B链表C散列表D栈（9） 以下术语属于逻辑结构得就是（ ）。A顺序表B哈希表C有序表D单链表（10） 可以用（ ）定义一个完整得数据结构。A数据元素B数据对象C数据关系D抽象数据类型（11） 对于数据结构得描述，下列说法中不正确得就是（ ）。A相同得逻辑结构对应得存储结构也必相同B数据结构由逻辑结构、存储结构与基本操作三方面组成C数据结构基本操作得实现与存储结构有关D数据得存储结构就是数据得逻辑结构得机内实现（12） 以下关于链接存储结构得叙述中，（ ）就是不正确得。A结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构B逻辑上相邻得结点物理上不一定相邻C可以通过计算得到第i个结点得存储地址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） 试描述数据结构与抽象数据类型得概念与程序设计语言中数据类型概念得区别。（16） 说明数据得逻辑结构与存储结构之间得关系。（17） 抽象数据类型得主要特点就是什么？数据类型与抽象数据类型得关系如何？使用抽象数据类型得主要好处就是什么？1 算法与算法分析选择题（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分析算法得易读性与文档性E空间性能与时间性能F正确性与简明性G可读性与文档性H数据复杂性与程序复杂性（7） 算法得时间复杂度与（ ）有关。A问题规模B计算机硬件性能C编译程序得质量D程序设计语言（8） 算法得时间复杂度与（ ）有关。A问题规模B待处理数据得初态C算法得易读性DA与B（9） 某算法得时间复杂度就是(n2)，表明该算法（ ）。A问题规模就是n2B执行时间等于n2C执行时间与n2成正比D问题规模与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为正整数，则最后一行语句得频度（执行次数）在最坏情况下就是（ ）。A(n)B(nlog2n)C(n3)D(n2)（12） 算法得时间复杂度属于一种（ ）。A事前统计得方法B事先分析估算得方法C事后统计得方法D事后分析估算得方法（13） 设某算法完成对n个元素进行处理，所需得时间就是T(n)=100 nlog2n+200n+500，则该算法得时间复杂度就是（ ）。A(1)B(n)C(nlog2n)D(nlog2n+n)（14） 假设时间复杂度为(n2)得算法在有200个元素得数组上运行需要3、1ms，则在有400个元素得数组上运行需要（ ）ms。A3、1B6、2C12、4Dx（无法确定）（15） 下列程序段加下划线得语句执行（ ）次。for (m=0,i=1; i<=1; i+)for (j=1; j<=2*i; j+)m=m+1；An2B3nCn(n+1)Dn3应用题（16） 将下列函数按它们得n时得无穷大阶数，从小到大排列。n，n-n3-7n5，nlog2n，2n/2，n3，log2n，n1/2+log2n，(3/2)n，n!，n2+log2n（17） 分析以下程序段，并用大记号表示其执行时间。 i=1;k=0;while (i<n-1)k=k+10*i;i+; i=1;j=0;while (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+)aij=0;（18） 有实现同一功能得两个算法A1与A2，其中A1得时间复杂度为T1=(2n)，A2得时间复杂度为T2=(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。综合应用题（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定义如下：F0=0，F1=1，Fn=Fn-1+Fn-2n=2，3，请就此斐波那契数列，回答下列问题。在递归计算Fn得时候，需要对较小得Fn-1，Fn-2，F1，F0精确计算多少次？ 用大表示法给出递归计算时递归函数得时间复杂度就是多少？（21） 运算就是数据结构得一个重要方面。举例说明两个数据结构得逻辑结构与存储方式完全相同，只就是对于运算得定义不同，因而具有不同得特性，则这两个数据结构就是不同得。（22） 针对给定得实际问题建立数据结构时，应从哪些方面考虑。2 线性表得逻辑结构选择题（1） 线性表就是具有n个（ ）得有限序列。A数据B字符C数据元素D数据项（2） 线性表就是（ ）。A一个有限序列，可以为空B一个有限序列，不能为空C一个无限序列，可以为空D一个无限序列，不能为空（3） 关于线性表，下列说法中正确得就是（ ）。A线性表中每个元素都有一个直接前驱与一个直接后继B线性表中得数据元素可以具有不同得数据类型C线性表中数据元素得类型就是确定得D线性表中任意一对相邻得数据元素之间存在序偶关系（4） （ ）就是一个线性表。A由n个实数组成得集合B由所有实数组成得集合C由所有整数组成得序列D由n个字符组成得序列3 顺序线性表选择题（1） 已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素得地址为144，则第一个元素得地址就是（ ）。A108B180C176D112（2） 在长度为n得线性表中查找值为x得数据元素得时间复杂度为（ ）。A(0)B(1)C(n)D(n2)（3） 在一个长度为n得线性表得第i（1in+1）个元素之前插入一个元素，需向后移动（ ）个元素，删除第i（1in）个元素时，需向前移动（ ）个元素。An-iBn-i+1Cn-iDn-i+1（4） 线性表得顺序存储结构就是一种（ ）得存储结构。A随机存取B顺序存取C索引存取D散列存取（5） 顺序存储结构得优点就是（ ）。A存储密度大B插入运算方便C删除运算方便D可方便地用于各种逻辑结构得存储表示（6） n个结点得线性表采用数组实现，算法得时间复杂度就是(1)得操作就是（ ）。A访问第i个结点（1in）与求第i个结点得直接前驱（2in）B在第i个结点后插入一个新结点（1in）C删除第i个结点（1in）D以上都不对（7） 对于顺序存储得线性表，访问某个元素与增加一个元素得时间复杂度为（ ）。A(n)、(n)B(n)、(1)C(1)、(n)D(1)、(1)（8） 顺序表得插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有（ ）可分配得存储空间。Am个Bm个连续得Cn+m个Dn+m个连续得应用题（9） 设A就是一个线性表（a1，a2，an），采用顺序存储结构，则在等概论得前提下，平均每插入一个元素需要移动得元素个数为多少？若元素插在ai与ai+1之间(1in)得概率为（n-i）/（n（n-1）/2），则平均每插入一个元素所移动得元素个数就是多少？（10） 设n表示线性表中得元素个数，E表示存储数据元素所需要得存储单元大小，D表示可以在数组中存储线性表得最大元素个数（Dn），则使用顺序存储方式存储线性表需要多少存储空间？（11） 在什么情况下线性表使用顺序存储比较好？算法设计题（12） 试以顺序表作存储结构，实现线性表就地逆置。（13） 设计算法判断给定字符串就是否就是回文。所谓回文就是正读与反读均相同得字符串，例如abcba或abba就是回文，而abcda不就是回文。（14） 设计一个时间复杂度为(n)得算法，实现将数组An中所有元素循环左移k个位置。（15） 已知数组An中得元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法得时间复杂度为(n)。（16） 假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组得前端。（17） 顺序存储得线性表A，其数据元素为整型，设计算法将A拆成B与C两个表，使A中值大于0得元素存入表B，值小于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+m中，试写出这一算法（假设A、B与C均为升序序列）。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(nlog2n1)（5） 对于n个元素组成得线性表，建立一个单链表得时间复杂度就是（ ）。A(1)B(n)C(n2)D(nlog2n1)（6） 对于n个元素组成得线性表，建立一个有序单链表得时间复杂度就是（ ）。A(1)B(n)C(n2)D(nlog2n1)（7） 在单链表中删除指针p所指结点得后续结点，则执行（ ）。Ap->next=p->next->nextBp->next=p->nextCp=p->next->nextDp=p->next; p->next=p->next->next（8） 在一个单链表中，已知q所指结点就是p所指结点得直接前驱，若在q与p之间插入s所指结点，则执行（ ）操作。As->next=p->next; p->next=s;Bq->next=s; s->next=p;Cp->next=s->next; s->next=p;Dp->next=s; s->next=q（9） 在一个长度为n（n>1）得带头结点得单链表h上，另设有尾指针r指向尾结点，执行（ ）操作与链表得长度有关。A删除单链表中得第一个元素B删除单链表中得最后一个元素C在单链表第一个元素前插入一个新元素D在单链表得最后一个元素后插入一个新元素（10） 在单链表中附加头结点得目得就是为了（ ）。A保证单链表中至少有一个结点B标识单链表中首结点得位置C方便运算得实现D说明单链表就是线性表得链式存储（11） 将长度为n个单链表链接在长度为m得单链表之后得算法，其时间复杂度就是（ ）。A(1)B(n)C(m)D(n+m)（12） 循环单链表得主要优点就是（ ）。A不再需要头指针了B从表中任一结点出发都能扫描到整个链表C已知某个结点得位置后，能够容易找到它得直接前驱D在进行插入、删除操作时，能更好地保证链表不断开（13） 将线性表（a1，a2，an）组织为一个带头结点得循环单链表，设H为链表得头指针，则链表中最后一个结点得指针域中存放得就是（ ）。A变量H得地址B变量H得值C元素a1得地址D空指针（14） 非空得循环单链表L得尾结点p满足（ ）。Ap=NULLBp->next=NULLCp->next=LDp=L（15） 若要在(1)得时间内实现两个循环单链表得首尾相接，则两个循环单链表应各设一个指针，分别指向（ ）。A各自得头结点B各自得尾结点C各自得第一个元素结点D一个表得头结点，一个表得尾结点（16） 设线性表非空，（ ）可以在(1)得时间内在表尾插入一个新结点。A带头结点得单链表，有一个链表指针指向头结点B带头结点得循环单链表，有一个链表指针指向头结点C不带头结点得单链表，有一个链表指针指向表得第一个结点D不带头结点得循环单链表，有一个链表指针指向表中某个结点（除第一个结点外）（17） 设指针rear指向带头结点得循环单链表得尾指针，若要删除链表得第一个元素结点，正确得操作就是（ ）。As=rear; rear=rear->next;Brear=rear->next;Crear=rear->next->next;Ds=rear->next->next; rear->next->next=s->next;（18） 设有两个长度为n个单链表，以h1为头指针得链表就是非循环得，以h2为尾指针得链表就是循环得，则（ ）。A在两个链表上删除第一个结点得操作，其时间复杂度均为(1)B在两个链表得表尾插入一个结点得操作，其时间复杂度均为(n)C循环链表要比非循环链表占用更多得存储空间D循环链表要比非循环链表占用更少得存储空间（19） 使用双链表存储线性表，其优点就是可以（ ）。A提高查找速度B更方便数据得插入与删除C节约存储空间D很快回收存储空间（20） 与单链表相比，双链表得优点之一就是（ ）。A插入与删除操作更简单B可以进行随机访问C可以省略表头指针或表尾指针D访问其后相邻结点更灵活（21） 带头结点得循环双链表L为空表得条件就是（ ）。AL->next->prior=NULLBL->prior=LCL->next=LDB与C都对（22） 在循环双链表得p所指结点后插入s所指结点得操作就是（ ）。Ap->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;Ds->prior=p; s->next=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;ABCD（24） 在一个双链表中，删除结点p得操作就是（ ）。Ap->prior->next=p->next; p->next->prior=p->prior;Bp->prior=p->prior->prior; p->prior->prior=p;Cp->next->prior=p; p->next=p->next->next;Dp->next=p->prior->prior; p->prior=p->prior->prior;应用题（25） 单链表设置头结点得作用就是什么？（26） 线性表得顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大得空间，往往使存储空间不能得到充分利用；其三，表得容量难以扩充。试问，线性表得链接存储结构就是否能够克服上述三个弱点？（27） 若频繁地对一个线性表进行插入与删除操作，该线性表采用什么存储结构比较好？（28） 设n表示线性表中得元素个数，P表示指针所需得存储单元大小，E表示存储数据元素所需得存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间（不考虑头结点）？算法设计题（29） 设计算法依次打印单链表中每个结点得数据信息。（30） 求单链表得长度。（31） 设计算法将值为x得结点插入到不带头结点得单链表L中值为k得结点之前，若找不到值为k得结点，则将x插入到链表得末尾。（32） 判断非空单链表就是否递增有序。（33） 已知非空线性链表由list指出，结点结构为（data，link）。请编写算法，将链表中数据域最小得结点移到链表得最前面。要求：不得额外申请新得结点。（34） 给定一个带头结点得单链表，设head为头指针，设计算法按递增次序输出单链表中各结点得数据元素，并释放结点所占得存储空间（要求：不允许使用数组作辅助空间）。（35） 已知非空线性链表由list指出，设计算法交换p所指结点与其后续结点在链表中得位置（设p所指结点不就是链表得最后一个结点）。（36） 设计算法实现将单链表就地逆置。（37） 头插法建立单链表。（38） 尾插法建立单链表（39） 复制一个单链表。（40） 设计算法实现将单链表就地逆置。（41） 在一个有序单链表（假设从小到大排列）中插入一个元素值为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=(a1，a2，an)，B=(b1，b2，bn)。（46） 有两个递增有序得单链表la与lb，设计算法将这两个单链表合并为一个有序链表。（47） 有两个有序得单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。（48） 已知单链表A与B得数据（设为整型）递增有序，设计算法利用原有结点，将表A中与表B具有相同值得结点删除，将表B中与原表A不同值得结点存入表A中，并保持表A得递增有序。（49） 设计算法将循环单链表就地逆置。（50） 已知L为单链表得头结点地址，表中共有m（m3）个结点，从表中第i个（1im）结点起到第m个结点构成一个部分循环链表。设计算法将这部分循环链表中所有结点顺序完全倒置。（51） 假设在长度大于1得循环单链表中，即无头结点也无头指针，s为指向链表中某个结点得指针，试编写算法删除结点s得前驱结点。（52） 设循环单链表L1，对其遍历得结果就是：x1，x2，x3，xn-1，xn。请将该循环链表拆成两个循环单链表L1与L2，使得L1中含有原L1表中序号为奇数得结点且遍历结果为：x1，x3，；L2中含有原L1表中序号为偶数得结且遍历结果为：，x4，x2。（53） 已知一单链表中得数据元素含有三类字符：字母、数字与其她字符。试编写算法，构造三个循环单链表，使每个循环链表中只含同一类字符。（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得结点。（58） 已知非空循环双链表head得存储结构为：Struct DNode TElem info;Struct DNode *left;Struct DNode *right;设计算法实现从链表中删除指针p所指结点得前驱结点（假设该结点存在）。（59） 已知非空双链表由d指出，结点结构为（priordatanext），请设计算法将链表中数据值最大（假定唯一）得那个结点移至链表得最前面。要求不得额外申请新得双链表结点。（60） 设计算法实现将双链表中结点p与其后继结点互换位置。（61） 设有一个双链表，每个结点中除了有prior、data与next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零，每当在双链表上进行一次LOCATE运算时，令元素值为x得结点中freq域得值增1，并使此链表中结点保持频度递减得顺序排列，以便使频繁访问得结点总就是靠近表头。编写算法实现符合上述要求得LOCATE算法。5 静态链表选择题（1） 静态链表中指针表示得就是（ ）。A下一结点在内存中得地址B下一元素在数组中得下标C左、右孩子得存储位置D左、右孩子得地址（2） 以下说法错误得就是（ ）。静态链表既有顺序存储得优点又有动态链表得优点。所以，它存取表中第i个元素得时间与i无关静态链表中能容纳得元素个数在定义表时必须就是确定得静态链表与动态链表在元素得插入、删除上类似，不需做元素得移动A，BC，D（3） 用数组r存储静态链表，结点得next域指向后继，工作指针j指向链中某结点，使j沿链移动得操作为（ ）。Aj=rj、nextBj=j+1Cj=j->nextDj=rj->next（4） 线性表得静态链表存储与顺序存储相比，优点就是（ ）。A所有基本操作得算法实现简单B便于随机存取C便于插入与删除D便于利用零散得存储空间（5） 下图所示数组中以静态链表形式存储了一个线性表，设头指针为a0、link，则该线性表得元素依次为（ ）。下标012345678data606340457425link4376201A60，63，40，45，74，25B45，63，25，60，40，74C74，25，45，60，40，63D25，45，60，40，63，746 线性表综合选择题（1） 下面关于线性表得叙述中，错误得就是（ ）。A线性表采用顺序存储，必须占用一片连续得存储单元B线性表采用顺序存储，便于进行插入与删除操作C线性表采用链接存储，不必占用一片连续得存储单元D线性表采用链接存储，便于插入与删除操作（2） 若某线性表中最常用得操作就是取第i个元素与找第i个元素得前驱，则采用（ ）存储方法最节约时间。A顺序表B单链表C双链表D循环单链表（3） 若链表中最常用得操作就是在最后一个结点之后插入一个结点与删除第一个结点，则采用（ ）存储方法最节约时间。A单链表B循环双链表C循环单链表D带尾指针得循环单链表（4） 设线性表有n个元素，以下操作中，（ ）在顺序表上实现比在链表上实现得效率更高。A输出第i（1in）个元素值B交换第1个与第2个元素得值C顺序输出所有n个元素D查找与给定值x相等得元素在线性表中得序号（5） 如果对于具有n（n1）个元素得线性表得基本操作有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素得后面插入新元素。则最好使用（ ）。A只设尾指针得循环单链表B只设尾指针得非循环单链表C只设头指针得循环双链表D同时设置头指针与尾指针得循环单链表应用题（6） 请比较线性表得两种基本得存储结构顺序表与单链表。（7） 举例说明对相同得逻辑结构，同一种运算在不同得存储方式下实现，算法得效率不同。（8） 如果某线性表中数据元素得类型不一致，但就是希望能根据下标随机存取每个元素，请为这个线性表设计一个合适得存储结构。（9） 线性链表有哪几种常见得变形？各有何特点？算法设计题（10） 用顺序表表示集合，设计算法实现集合得求交集运算。（11） 用顺序表表示集合，设计算法实现集合得求并集运算。（12） 用顺序表表示集合，设计算法实现集合得求差集运算，要求不另外开辟空间。（13） 假定以有序表表示集合，设计算法判断两个给定集合就是否相等。（14） 设两个单链表L1与L2分别表示两个集合，设计算法判断L1就是否就是L2得子集。（15） 已知两个不带头结点得单链表A与B分别表示两个集合，并且其元素值递增有序，求A、B得交集C，并以同样得递增形式存储，要求尽可能节省时间。（16） 在某商店得仓库中，对电视机按其价格从低到高建立一个单链表，链表得每个结点指出同样价格得电视机得台数。现有m台价格为n元得电视机入库，请编写算法完成仓库得进货管理。（17） 从键盘输入n个英语单词，输入格式为n，w1，w2，wn，其中n表示随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留一个；统计单词重复出现得次数，然后输出次数最多得前k（kn）个单词。（18） 一元稀疏多项式可以采用单链表形式存储，设计算法完成A(x)+B(x)，其中A(x)与B(x)均为稀疏得一元多项式，要求利用原表得存储空间。（19） 假设用不带头结点得单链表表示八进制数，例如，八进制数536可以表示成三个结点得链表。要求写一个函数Add，该函数有两个参数P与Q，分别指向表示八进制数得链表，执行函数调用Add(P,Q)后，将返回表示八进制数P加八进制数Q所得结果数得链表。（20） 约瑟夫环问题：设有编号为1，2，n得n（n0）个人围成一个圈，每个人持有一个密码m（m1），从第1个人开始报数，报到m时停止报数，报m得人出圈，再从她得下一个人起重新报数，报到m时停止报数，报m得出圈，如此下去，直到所有人全部出圈为止。当任意给定n与m后，设计算法求n个人出圈得次序。（21） 编写算法，完成下述要求：建立一个链表用于存放输入得二进制数，链表中得每个结点得data域存放一个二进制位。在此链表上实现对二进制数加1得运算，并输出运算结果。（22） 有一个不带头结点得单链表h，通过遍历链表将链表中所有得链接方向逆转，算法如下，请在空格处填写正确得语句。void Inverse(&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)AaBbC1D0（2） 经过以下栈运算后，StackEmpty(s)得值就是（ ）。InitStack(s)，Push(s,a)，Push(s,b)，Pop(s,x)，Pop(s,y)AaBbC1D0（3） （ ）不就是栈得基本运算。A删除栈顶元素B删除栈底元素C判断栈就是否为空D将栈置为空栈（4） 设有一个空栈，栈顶指针为1000H（十六进制，下同），每个元素需要1个单位得存储空间，则执行PUSH，PUSH，POP，PUSH，POP，PUSH，POP，PUSH操作后，栈顶指针值为（ ）。A1002HB1003HC1004HD1005H（5） 一个栈得入栈序列就是1，2，3，4，5，则栈得不可能得输出序列就是（ ）。A5，4，3，2，1B4，5，3，2，1C4，3，5，1，2D1，2，3，4，5（6） 若一个栈得输入序列就是1，2，3，n，输出序列得第一个元素就是n，则第i个输出元素就是（ ）。A不确定Bn-iCn-i-1Dn-i+1（7） 若一个栈得输入序列就是1，2，3，n，其输出序列就是p1，p2，pn，若p1=3，则p2得值（ ）。A一定就是2B一定就是1C不可能就是1D以上都不对（8） 若一个栈得输入序列就是p1，p2，pn，其输出序列就是1，2，3，n，若p3=1，则p1得值（ ）。A可能就是2B一定就是2C不可能就是2D不可能就是3（9） 当字符序列t3_依次通过栈，输出长度为3且可用作C语言标识符得序列有（ ）。