部分习题附标准答案

1、第一部分习题一、选择1、下列叙述中关于好的编程风格，正确的描述是：CA 、 程序中的注释是可有可无的 为了增强可读性我们要在必要语句之后加注释B、对递归定义的数据结构不要使用递归过程递归的可读性强C、递归应是封闭的，尽量少使用全局变量D、多采用一些技巧以提高程序运行效率2、通常从正确性、易读性、健壮性、高效性等四个方面评价算法（ 包括程序 ）的质量。以下解释错误的是 （ C ） 矚慫润厲钐 瘗睞枥庑赖。A、正确性算法应能正确地实现预定的功能（ 即处理要求 ）B、易读性算法应易于阅读和理解以便于调试修改和扩充C、健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需 要的运行结果

2、见课本 14 页D、高效性即达到所需要的时间性能3、以下说法正确的是（ D ）聞創沟燴鐺險爱氇谴净。A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合 D 、数据结构是带有结构的数据元素的集合4、对于顺序表，以下说法错误的是（ A）A 、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B 、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C 、顺序表的特点是 :逻辑结构中相邻的结点在存储结构中仍相邻D 、顺序表的特点是 : 逻辑上相邻的元素，存储在物理位置也相邻的单元中5、对顺序表上的插入、删除算法的时间复杂性分析来说

3、，通常以（B）为标准操作A 、条件判断 B、结点移动 C、算术表达式 D、赋值语句6、对于顺序表的优缺点，以下说法错误的是（C）A 、无需为表示结点间的逻辑关系而增加额外的存储空间B 、可以方便地随机存取表中的任一结点C 、插入和删除运算较方便D 、容易造成一部分空间长期闲置而得不到充分利用7、链表不具有的特点是： AA 、可随机访问任一个元素 B、插入删除不需要移动元素 C、不必事先估计存储空间D 、所需空间与线性表长度成正比8、若线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用（ D ）存储方式节省时间A 单链表 B、双向链表 C、单循环链表 D 、顺序表9、有时为了叙述方便，可

4、以对一些概念进行简称，以下说法错误的是（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对

5、单链表来说，只有从头结点开始才能扫描表中全部结点 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（

6、 1）便可实现，因此顺序表是一种随机存取结构C在链表上实现读表元运算的平均时间复杂性为O（ 1）D插入、删除操作在链表上的实现可在O（ n）时间内完成14循环链表主要优点是（ D）A不再需要头指针了B已知某个结点的位置后，能够容易找到它的直接前趋 C在进行插入、删除运算时，能更好地保证链表不断开 D从表中任一结点出发都能扫描到整个链表15以下说法错误的是（ B） A数据的物理结构是指数据在计算机内实际的存储形式 B算法和程序没有区别，所以在数据结构中二者是通用的 C对链表进行插人和删除操作时，不必移动结点 D双链表中至多只有一个结点的后继指针为空16以下说法正确的是 C A线性结构的基本特征是

7、：每个结点有且仅有一个直接前趋和一个直接后继 B 线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现 效率要低C在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素位置 有关D顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动17以下说法错误的是（ D） A求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B顺序存储的线性表可以随机存取 C由于顺序存储要求连续约存储区域所以在存储管理上不够灵活 D线形表的链式存储结构优于顺序存储结构18以下说法错误的是( B) A线性表的元素可以是各

8、种各样的，逻辑上相邻的元素在物理位置上不一定相邻 B在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 C在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 D线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 19以下说法正确的是( C) A在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点 进行查找任何一个元素B在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机 存取的存储结构C顺序存储方式只能用于存储线性结构 D顺序存储方式的优点是存储密度大、且插入、删除运算效率高20. 线性表 L=(a1,a2

9、,.,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;

10、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 每个结点所代表的数据元素包含的数据项的

11、个数要相等C 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致D 结点所代表的数据元素有同一特点 25带头结点的单链表 Head 为空的判定条件是 B庑。A 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 data RLink其中： LLink 是指向前驱结点的指针域： d

12、ata 是存放数据元素的数据域； 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;籟丛妈羥为贍偾蛏

13、练淨。错误原因 : 将新结点 *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.rea

14、r+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.front31 如果以链表作为栈的存储结构 ,则退栈

15、操作时( 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 6A a3,a1,a4,a2 贓熱俣阃歲匱阊邺镓騷。34. 向一个栈顶指针为Top 的链中插入一个 s 所指结点时，其操作步骤为(D)33设有一顺序栈已含 3 个元素，如下图所示，元素 a4正等待进栈。那么下列 4 个序列中不可能出现的出栈序列是( A

16、)0 1 2 3 maxsize-1a1a2a3B a3,a2,a4,a1 C a3,a4,a2,a1 D a4,a3,a2,a1（ 无头结点 ）A Top-next=s B s-next=Top-next;Top-next=s 坛摶乡囂忏蒌鍥铃氈淚。C s-next=Top;Top=s D s-next=Top;Top=Top-next 蜡變黲癟報伥铉锚鈰赘。 35.从栈顶指针为 Top的链栈中删除一个结点，并将被删结点的值保存到x 中，其操作步骤为（ A）Top=Top-next;x=Top-data 買鲷鴯譖昙膚A x=Top-data;Top=Top-next 遙闫撷凄。C x=Top

17、;Top=Top-next 踪韦辚糴。36. 在一个链队中，若 A f-next=c;f=s C s-next=r;r=s 37链栈与顺序栈相比， A插入操作更方便 C不会出现栈空的情况 D删除操作更方便38. 一个栈的入栈序列是 a,b,c,d,e, A e d c b aB d e c b a诛髅貺庑。39. 一个队列的入队列顺序是 1，2， A 4，3，2，1B 1，2，3，4，C1，4，3，240设计一个判别表达式中左、右括号是否配对的算法，采用（D x=Top-data綾镝鯛駕櫬鹕分别为队首、队尾指针，则插入 B r-next=s;r=sD s-next=f;f=s 有一个比较明显的

18、优点即（ B通常不会出现栈满的情况f,rB）s 所指结点的操作为（ B） 驅踬髏彦浃绥譎饴憂锦。则栈的不可能的输出序列是（C d c e a b D a b c d e3，4，则队列的输出系列是（D 3C）猫虿驢绘燈鮒B），2，4，1 B）数据结构最佳。A线性标的顺序存储结构 B 栈 C队列 D线性表的链式存储结构41 设循环队列中数组的下标范围是0 n-1，其头尾指针分别为 f 和 r，则其元素的个数为（D ）A 、r-f B、 r-f +1 C、 （r-f）%n+1D 、（r-f+n） %n42 若一个栈的输入序列是 1、2 N，输出序列的第一个元素是 N，则第 I 个输出元素为 （C ）

19、A 、N-IB、 IC、N-I+1D 、N-I-143 队列操作的原则是（ A）A 先进先出 B 、后进先出C、只能进行插入D 、只能进行删除44 线性表是 （ A ） 。A 一个有限序列，可以为空； B 一个有限序列，不能为空； C 一个无限序列，可以为空； D 一个无序序列，不能为空。 二填空题、1. 以下为求单链表表长的运算，分析算法，请在 int length_linklist（linklist head） /* 娅薔。处填上正确的语句。求表 head 的长度 */ 锹籁饗迳琐筆襖鸥_ _p=head;j=0; while(p-next)_ _p=p-next j+; return(j

20、);/*回传表长 */ 该算法也可以写成int length_linklist(linklist head) /*求表 head 的长度 */ 構氽頑黉碩饨荠龈话骛。p=head-next;j=0;while(p)p=p-next;j+;return(j); 比较一下 , 特别是初始化与循环条件 . 原题中是 while(p-next) 即若 p 有后继 , 则 j 加 1, 所以 p 的初始化为 p=head 輒峄陽檉簖疖網儂號泶。2. 以下为单链表按序号查找的运算，分析算法，请在 处填上正确的语句。linklist find_lklist(linklist head,int i)/查找第

21、i 个结点 p=head;j=0;while( _p&(jnext; j+; if(i=j) return(p);else return(NULL);因为返回 i 结点的地址 , 所以函数类型为 linklist, 如果找到就不需要访问链表了 , 所以应该是访问部分结点的这种情况 , 所以在循环条件中至少要有两个 . 尧侧閆繭絳闕绚勵蜆贅。3. 以下为单链表的定位运算，分析算法，请在 处填上正确的语句。int locate_lklist(lklist head,datatype x)/* 求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0*/ p=head;j=0;w

22、hile( p-next&p-next-data!=x )p=p-next;j+;if ( p-next ) return( j+1);else return(0);这题也要注意处始化 ,p 初值为 head,即指向头结点的 ,所以是让 *p 的后继结点的数据域 和 x 进行比较 . 若 p 的初值指向第一个结点 , 循环条件就发生了变化 , 具体算法为 : 识饒鎂錕缢灩 筧嚌俨淒。int locate_lklist(lklist head,datatype x)/* 求表 head 中第一个值等于 x 的结点的序号。不存在这种结点时结果为 0*/ p=head-next;j=1;while

23、(p &pdata!=x )p=p-next;j+;if ( p ) return( j );else return(0);这两个算法也要比较一下 . 在回顾一下我们上课所说采用链表编写算法的格式, 这个格式一定要放在脑子中 .4. 以下为单链表的删除运算，分析算法，请在 处填上正确的语句。void delete_lklist(linklist head,int i) p=find_lklist(head,i-1); / 调用第 2 题if(_ _p&p-next_ )/ 必须第 i-1 结点与第 i 结点存在 q=_ _p-next_ ; p-next=q-next; free(q);els

24、e error(“不存在第 i 个结点 ”)5. 以下为单链表的插入运算，分析算法，请在 处填上正确的语句。void insert_lklist(linklist head,datatype x,int i)/* 在表 head 的第 I 个位置上插入一个以 x 为值的新结点 */ p=find_lklist(head,i-1);if(p=NULL)error( “不存在第 i 个位置 ”) ；else s= (linklist)malloc(sizeof(lnode) ;s-data=x; s-next=_p-next;_ ;p-next=s;6. 以下为单链表的建表算法，分析算法，请在 处

25、填上正确的语句。Linklist create_lklist1()/* 通过调用 initiate_lklist 和 insert_lklist 算法实现的建表算法。假定 $ 是结束标志 */ 凍鈹鋨劳臘锴痫婦胫籴。 ininiate_lklist(head);i=1;scanf( “%f”,&x);while(x!= $) _ insert_lklist(head, x,int i)_;i+ ;scanf(“%f”,&x); return(head); 改建表算法的时间复杂性约等于 _O(N2) 。7. 以下为单链表的建表算法，分析算法，请在 处填上正确的语句。linklist create

26、_lklist2() /* 直接实现的建表算法。 */ 恥諤銪灭萦欢煬鞏鹜錦。 head=malloc(size);p=head;scanf( “%f”,&x); while(x!= $) q=(linklist)malloc(sizeof(lnode);q-data=x;p-next=q;p=q;scanf(“%f”,&x);p-next=null ; / 让最后一个结点的指针域为空return(head); 这题是从前往后建立单链表的与课本上算法 2.11 不一样 ,2.11 是逆序建立的 , 大家把这 两个算法对比一下 . 鯊腎鑰诎褳鉀沩懼統庫。 8循环链表与单链表的区别仅仅在于其尾结点

27、的链域值不是空指针 ，而是一个指向 _头结点_的指针。9在单链表中若在每个结点中增加一个指针域, 所含指针指向前驱结点， 这样构成的链表中有两个方向不同的链，称为 双向链表 。 硕癘鄴颃诌攆檸攜驤蔹。10 、一个好的算法应当具有下列好的特性：正确性、（ 可读性 ）、（健壮性 ）和效率和低存储需求。11、算法的五个重要特征为（ 确定性 ）、（ 有穷性 ）、（ 可行性 ）和输入、输出。12 、采用顺序存储结构的线性表，其每个元素占用个单元。第一个元素的地址为，则 第 i 个元素的存储位置为（ N+（i-1）*L）。 阌擻輳嬪諫迁择楨秘騖。13 、数据元素之间的关系在计算机中的表示有两种不同的表示方

28、法，即（ 顺序映像 ） 和（ 非顺序映像 ），从而得到两种不同的存储结构（ 顺序存储结构 ）和（ 链式存 储结构 ）。氬嚕躑竄贸恳彈瀘颔澩。14、已知栈的输入序列为 1、2、3n 输出序列为 a1,a2 ,an 符合 a2=n的输出序列 共有（ n-1 ）种。 釷鹆資贏車贖孙滅獅赘。15带头结点的单链表 H 为空的条件是 _H-nexy=NULL 。16 非空单循环链表 L 中 *p 是尾结点的条件是 _p-next=l_ 。 17在一个单链表中 p 所指结点之后插入一个由指针 s 所指结点，应执行 s-next=_ _p-next_ ; 和 p-next=_ _s_的操作。 怂阐譜鯪迳導嘯畫

29、長凉。18在一个单链表中 p 所指结点之前插入一个由指针 s所指结点，可执行以下操作： s-next= _p-next_ ;p-next=s; t=p-data; p-data=_s-data_; s-data=_t ;19在顺序表中做插入操作时首先检查 _是否溢出 _ 三判断题1 在顺序表中取出第 i 个元素所花费的时间与 i 成正比 不对 , 因为是可以随机存取 .2 线性表的长度是线性表所占用的存储空间的大小 不对3 在对链队列作出队列操作，不会改变 front 指针的值对4 双循环链表中，任一个结点的后继指针均指向其逻辑后继 不对 , 最后一个结点的后继指针不是指向其逻辑后继5 已知指

30、针 P 指向链表 L 中某结点，执行语句 P=P-next 不会删除该链表中结点 对6 在链队列中，即便不设置尾指针也能进行入队列操作对, 但花费的时间较多7 栈和队列都是运算受限的线性表对8 在带头结点的单循环链表中，任一结点的后继指针均不空对9 线性表采用链表方式和顺序表方式存储，执行插入和删除运算的时间复杂度都是O(N) ，因而两种存储方式的插入、删除运算所花费的时间相同谚辞調担鈧谄动禪泻類。不对四、算法设计(算法大多数是习题集上的 ,大家参考习题集答案 ,如果哪道题 ,有什么问题 ,我再给出具体 的分析和答案 )1设 A=( a1,a 2,a 3, an)和 B=(b 1,b 2,.

31、.,b m)是两个线性表(假定所含数据元素均为整数)。若 n=m且 ai =bi (i=1,. .,n),则称 A=B;若 ai=bi (i=1,. .,j)且 aj+1 bj+1 , 则称 AB。是编写一个比较 A 和 B 的算法，当 AB是分别输出 -1， 0 或者 1。嘰觐詿缧铴嗫偽純铪锩。2试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。3假设有两个按数据元素值递增有序排列的线性表A 和 B，均以单链表作存储结构。编写算法将 A 表和 B表归并成一个按元素值递减有序(即非递增有序，允许值相同)排列 的线性表 C，并要求利用原表 (即 A表和 B表的 )结点空间存放表 C。4设有线性表 A=(a 1,a 2,. .,a m)和B=(b1,b 2,. .,b n). 试写合并 A、B为线性表 C的算法， 使得： 熒绐譏钲鏌觶鷹緇機库。(a1,b1,.,am,bm,bm 1,bn)当mn;C=(a1,b1,.,an,bn,an 1,.,am)当m n;假设 A、 B均以单链表为存储结构 ( 并且 m、 n 显示保存 ) 。要求 C也以单链表为存储 结构并利用单链表 A、B 的结点空间。5已知单链表 L 中的结点是按值非递减有序排列的，试写一算法将值为 x 的结点插 大表 L 申，使得 L 仍然有序。6，试分别以顺序表和单链表作存储结构，各写一个实现线