2012数据结构-习题及程序设计整理

实用文档实用文档第二章1、首尾顺序逆置2、找出顺序表中最大值和最小值及位置3、头插法算法4、尾插法：5、带头结点的单链表，向表头插入一个结点：6、单链表中查找第i个结点：7、在单链表中查找值为K的结点8、单链表删除操作：9、重要习题，头结点与尾结点互换：10、重要习题，一个单链表拆为两个奇偶单链表：试写一个算法，将一个头结点为a的带头结点的单链表A分解成两个单链表A和B，其中头结点指针分别为a和b，使得A链表中含有原链表A中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，并保持原来的相对顺序。11、循环链表插入结点后仍然保持有序：12、重要习题(删除表中所有数值相同的多余元素)：13、双向链表的删除操作：14、双向链表的插入操作：在带头结点的双向循环链表中插入一个新结点，需要修改的指针数量是4个。包括新插入的新结点的指针，还有插入结点的前面结点的next域，和后面结点的prior域。第二章课后习题14、设计两个顺序表A和B，且都递增有序，试写一算法，从A中删除与B中相同的元素（也就是计算A-B）。15、已知head是指向一个带头结点的单链表的头指针，P指向该链表的任一结点，试写一算法，将P指向结点与其后继结点位置交换。（q为p的后继结点，s是首结点（头结点的下一个结点，r为首结点以后的结点）16、已知两个单链表A和B分别表示两个集合，其元素值递增有序，试写一算法，求A和B的交集C，要求C同样以元素递增的单链表形式存储。r=head;查找p的前趋结点17、设有一个头结点的双向循环链表，head为链表的头指针，试写一算法，实现在值为x的结点之前插入一个值为y的结点。第三章一、队列算法f31的功能是清空带头结点的链队列Q，请填空。Typestructnode{DataTypedata;Structnode*next;}QueueNode;{QueueNode*front;//队头指针二、填空题15、如果编号为1，2，3的3辆列车进入一个栈式结构的站台，那么可能得到的3辆车出站序列有哪些？不可能出现的序列是什么？16、简述下列程序算法的功能（假设元素为整数类型）（1）voidex31(SeqStack*S){intA[80],i,n;n=0;while(!empty(S)){A[n]=pop[S];n++;}for(i=0;i<n;i++)push(S,A[i]);}答案：此算法功能是通过一个数组将一个栈中的所有元素逆置存放。例如原来栈S中存放5个元素abcde，经过算法执行后，变为edcba。(2)voidex32(SeqStack*s,intc){SeqStackT;intd;while(!StackEmpty(S)){d=pop(S);if(d!=c)push(T,d);}while(!StackEmpty(T)){d=pop(T);if(d!=c)push(S,d);}}答案：通过一个中间栈T，达到删除栈S中所有与变量c相同的元素。17、写出下列程序的输出结果（栈结点数据域为字符型char）SeqStackS;Charx,y;X=`c`,y=`k`;Push(S,x);push(S,`a`);Push(S,y);x=pop(S);Push(S,`t`);push(S,x);X=pop(S);push(S,`s`);While(!StackEmpty(S)){Y=pop(S);Putchar(y);}Putchar(x);该程序段执行过程中，变量x,y和栈S中的顺序变化情况：x=`c`,y=`k`,S=”&”;x=`c`,y=`k`,S=”cak”;x=`k`,y=`k`,S=”cat”；x=`k`,y=`k`,S=”catk”;x=`k`,y=`k`,S=”cats”;最后输出结果为stack19、在循环队列的顺序存储结构下，分别写出入队（插入元素），出队（删除元素），时修改尾、队头指针的操作语句以及求队列长度的公式。入队操作指针移动语句为cq.rear=(cq.rear+1)%QueueSize;出队操作指针移动语句为cq.front=(cq.front+1)%QueueSize;队列长度(cq.rear+QueueSize-cq.front)%QueueSize;20、利用两个栈S1和S2模拟一个队列，如何用栈的运算来实现队列的插入和删除运算？试写出算法。21、试设计一个算法，实现输入一个字符串并检查字符串中是否含有圆括号，当圆括号匹配时输出括号内的字符串，否则给出出错信息（提示：利用栈记录在左括号出现后的字符）22、试利用循环队列（长度为K）存储，编写求斐波那契序列的前N（N>K）项（f0,f1,…fn-1）的算法，其函数定义如下：第四章22、1、2、3、4、6、已知A和B是两个NxN的对称矩阵，因为是对称矩阵，所以仅需要输入下三角元素存入一维数组。试写一算法，求对称矩阵A与B的乘积。7、三角矩阵与对对性的三角矩阵很相似。三角矩阵：对称矩阵:第五章1、求叶结点公式：2、3、4、5、若二叉树从0开始排序，则：若二叉树从1开始排序，则：第六章课后习题：22、对于图，试给出：（1）图的邻接矩阵；（2）邻接表和逆邻接表；(3)强连通分量。23、第七章23、对于给定的一组关键字（46，32，55，81，65，11，25，43），进行直接插入排序，写出其排序的每一趟结果。24、写出给定的一组关键字（26，18，60，14，7，45，13，32），写出直接选择排序，写出其排序的每一趟结果。25、对于给定的关键字（41，62，13，84，35，96，57，39，79，61，15，83）,分别写出执行以下排序算法的每一趟排序结果。（1）希尔排序（5，2，1）（2）快速排序(3)基数排序26、对于给定的关键字（26，18，60，14，7，45，13，32），写出执行堆排序算法的每一趟结果。27、对待排序记录关键字序列，在以下几种情况下，进行直接插入排序时（按升序）至多需要进行多少次关键字的比较？(1)关键字从小到大顺序有序（正序）（2）关键字从大到小顺序有序（反序）（3）前一半关键字序列从小到大顺序在序，后一半关键字序列是从大到小顺序有序28、判断下列序列是否为堆（小根堆或大根堆），如果不是，则将其调整为堆。（1）（17，18，60，70，7，32，73，65）（2）（96，83，72，45，28，54，60，23，38，15）（3）（25，48，16，35，79，82，23，40，36，72）（4）（12，24，18，65，33，56，33，92，86，70）29、算法设计已知一个按结点数值递增有序的单链表，试写一算法，插入一个新记录，使得链表仍然按关键字从小到大的次序排列。已知两个有序列A[0…n-1]和B[0…m-1]，试写一算法，将它们合并为一个有序表C【0…m+n-1】1、直接插入排序2、希尔排序3、冒泡排序（从后往前两两交换）第八章21、分别画出线性表（5，10，15，20，25，30，35，40）中用二分查找方法查找关键字等于10、30及39的查找过程。22、画出对长度为13的有序表进行二分查找的判定树，并求其等概率情况下查找成功的平均查找长度。23、已知关键字序列（Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec）,按元素的先后顺序依次插入到一棵初始为空的二叉排序树中，画出插入完成后的二叉排序树，并求等概率情况下查找成功的平均查找长度。24、已长如图的3阶B树，分别画出插入26后的B树和接着删除48后的B树。25、设散列函数f(k)=kmod13，散列表地址空间为0~12,对给定的关键字序列（19，14，23，01，68，20，84，27，55，11，10，79），分别以拉链法和线性探测法解决冲突构造散列表，画出所造的散列表，并指出这两个散列表中查找每一个关键字时进行比较的次数。26、用二分查找法对一个长度为12