第一部分习题一、 选择1、 下列叙述中关于好的编程风格，正确的描述是：CA、 程序中的注释是可有可无的为了增强可读性我们要在必要语句之后加注释B、 对递归定义的数据结构不要使用递归过程递归的可读性强C、 递归应是封闭的，尽量少使用全局变量D、 多采用一些技巧以提高程序运行效率2、通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是 ( C )矚慫润厲钐瘗睞枥庑赖。A、正确性算法应能正确地实现预定的功能(即处理要求)B、易读性算法应易于阅读和理解以便于调试修改和扩充C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果 见课本14页D、高效性即达到所需要的时间性能3、以下说法正确的是 ( D )聞創沟燴鐺險爱氇谴净。A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合4、对于顺序表，以下说法错误的是（A） A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中5、对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（B）为标准操作 A、条件判断B、结点移动C、算术表达式D、赋值语句6、对于顺序表的优缺点，以下说法错误的是（C） A、无需为表示结点间的逻辑关系而增加额外的存储空间 B、可以方便地随机存取表中的任一结点 C、插入和删除运算较方便 D、容易造成一部分空间长期闲置而得不到充分利用7、链表不具有的特点是：AA、可随机访问任一个元素 B、插入删除不需要移动元素C、不必事先估计存储空间 D、所需空间与线性表长度成正比8、 若线性表最常用的操作是存取第i个元素及其前驱的值，则采用（D ）存储方式节省时间A单链表B、双向链表 C、单循环链表D、顺序表9、有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是（D）A将“指针型变量”简称为“指针”B将“头指针变量”称为“头指针”C将“修改某指针型变量的值”称为“修改某指针”D将“p中指针所指结点”称为“P值”10设指针P指向双链表的某一结点，则双链表结构的对称性可用（C）式来刻画A p-prior-next-=p-next-nextB p-prior-prior-=p-next-priorC p-prior-next-=p-next-priorD p-next-next=p-prior-prior11.以下说错误的是（A）A对循环来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表B对单链表来说，只有从头结点开始才能扫描表中全部结点C双链表的特点是找结点的前趋和后继都很容易D对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中。12在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别是（B）A rear和rear-next-nextB rear-next 和rearC rear-next-next和rearD rear和rear-next13.以下说错误的是 ( C) A 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）B读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构C在链表上实现读表元运算的平均时间复杂性为O（1）D插入、删除操作在链表上的实现可在O（n）时间内完成14循环链表主要优点是（D）A不再需要头指针了B已知某个结点的位置后，能够容易找到它的直接前趋C在进行插入、删除运算时，能更好地保证链表不断开D从表中任一结点出发都能扫描到整个链表15以下说法错误的是（B）A数据的物理结构是指数据在计算机内实际的存储形式B算法和程序没有区别，所以在数据结构中二者是通用的C对链表进行插人和删除操作时，不必移动结点D双链表中至多只有一个结点的后继指针为空16以下说法正确的是CA线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继B线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低C在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置有关D顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动17以下说法错误的是（D）A求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取C由于顺序存储要求连续约存储区域所以在存储管理上不够灵活D线形表的链式存储结构优于顺序存储结构18以下说法错误的是（B）A线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻B在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻C在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻D线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素19以下说法正确的是（C）A在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素B在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构C顺序存储方式只能用于存储线性结构D顺序存储方式的优点是存储密度大、且插入、删除运算效率高20.线性表L=(a1,a2,.,ai,.,an),下列说法正确的是( D )A每个元素都有一个直接前驱和直接后继B线性表中至少要有一个元素C表中诸元素的排列顺序必须是由小到大或由大到小的D除第一个元素和最后一个元素外其余每个元素都有一个数且仅有一个直接前驱和直接后继21.线性表若采用链表存储结构时，要求内存中可用存储单元的地址(D )A必需是联系的B部分地址必须是连续的C一定是不连续的D连续不连续都可以22.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为( D)A p=rear;rear=rear-next; free(p)B rear=rear-next;free(rear);C rear=rear-next-next; free(rear); D p=rear-next-next; rear-next-next=p-next; free(p);残骛楼諍锩瀨濟溆塹籟。23. 单链表中，增加头结点的目的是为了 ( C )A使单链表至少有一个结点B标示表结点中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储实现24线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着C酽锕极額閉镇桧猪訣锥。A 每个结点所代表的数据元素都一样。B 每个结点所代表的数据元素包含的数据项的个数要相等C 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致D 结点所代表的数据元素有同一特点25带头结点的单链表Head为空的判定条件是 BA Head=Null B Head-next=NULL C Head-next=Head彈贸摄尔霁毙攬砖卤庑。26空的单循环链表L的尾结点*P,满足D ( 虽然C的条件也成立,但不空的单循环链表也满足C)A P-next=NULL B P=NULL C P-next=L D P=L謀荞抟箧飆鐸怼类蒋薔。27.双向链表结点结构如下：LLink dataRLink其中：LLink是指向前驱结点的指针域：data是存放数据元素的数据域；Rlink是指向后继结点的指针域。厦礴恳蹒骈時盡继價骚。下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双向链表中。能正确完成要求的算法段是C茕桢广鳓鯡选块网羈泪。A Q-LLink=P-LLink;Q-Rlink=P;P-LLink=Q; P-LLink-Rlink=Q; 鹅娅尽損鹌惨歷茏鴛賴。错误原因为: P-LLink-Rlink=Q; P-LLink已在第三个赋值语句中修改了.B P-LLink=Q;Q-Rlink=P;P-LLink-Rlink=Q;Q-LLink=P-LLink;籟丛妈羥为贍偾蛏练淨。 错误原因:将新结点*Q作为非空双向链表中的结点*p的前驱,应先修改插入结点的前驱指针域,后修改结点*p的前驱指针域預頌圣鉉儐歲龈讶骅籴。C Q-LLink=P-LLink;Q-Rlink=P;P-LLink-Rlink=Q;P-LLink=Q;渗釤呛俨匀谔鱉调硯錦。28.循环队列的出队操作为 ( A )A sq.front=(sq.front+1)% maxsizeBsq.front=sq.front+1C sq.rear=(sq.rear+1)% maxsizeD sq.rear=sq.rear+129.循环队列的队满条件为 (C )A (sq.rear+1) % mazsize =(sq.front+1) % maxsize;B (sq.rear+1) % maxsize =sq.front+1C (sq.rear+1) % maxsize =sq.frontD sq.rear =sq.front30.循环队列的队空条件为 ( D)A (sq.rear+1) % maxsize =(sq.front+1) % maxsizeB (sq.rear+) % maxsize =sq.front+1C (sp.rear+1) % maxsize =sq.frontD sq.rear = sq.front 31如果以链表作为栈的存储结构,则退栈操作时 ( C )铙誅卧泻噦圣骋贶頂廡。A必须判别栈是否满B判别栈元素的类型C必须判别栈是否空D队栈不做任何判别32.设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出线的顺序是s2,s3,s4, s6 , s5,s1,则栈的容量至少应该是（B）擁締凤袜备訊顎轮烂蔷。A 2 B3 C 5 D 633设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是（A） 0 1 2 3 maxsize-1a1a2