编程考试试卷

最新题目 更多

•    算法21可直接使用Python的列表设计算法。21·假设用一个线性表记录某地区每年的平均气温，以研究全球气候变暖的趋势。研究者发现，气温的变化是有一定的规律的。如：线性表L=(3, 4, 6, 4, 5, 7, 5)记录了连续7年的平均气温，从第一年开始，按照＋1,+2,-2的规律变化，然后又按照＋1,+2,-2这样的规律变化，我们称这个表中存在一个长度为3的温度变化环。又如：（1, 10, 13, 45, 48, 57, 60, 92,95, 104, 107)存在一个长度为4的环＋9,+3,+32,+3.设计算法求解线性表中这个环的长度。
•    算法20中，la为双向链表的头指针，直接用头指针表示和操作双向链表。20·设有一个双向链表la,每个结点中除有prior、data和next域外，还有一个访问频度freq域，在链表被使用之前，freq域初始化为零。每当在链表进行一次locate(x)运算后，令值为X的结点中的freq域增1,并调整表中结点的次序，使其按访问频度的递减序列排列，以便使频繁访问的结点总是靠近表头。设计满足上述要求的locate(x)算法。
•    算法14~19中，la、lb、Ic为各个单链表的头指针，直接用头指针表示和操作单链表。19·设计算法，求两个有序单链表la和lb表示的集合的交集lc,Ic也为有序单链表。
•    算法14~19中，la、lb、lc为各个单链表的头指针，直接用头指针表示和操作单链表。18.设计算法，求两个有序单链表la和lb表示的集合的差集Ic,Ic也为有序单链表。
•    算法14~19中，la、lb、Ic为各个单链表的头指针，直接用头指针表示和操作单链表。17·设计算法，将两个递增有序单链表la和lb合并成一个递减有序表。
•    算法14~19中，la、lb、lc为各个单链表的头指针，直接用头指针表示和操作单链表。16.设计算法，将一个单链表la分裂成奇偶两个单链表，偶数位序的结点留在原表，奇数位序的形成一个新表lb
•    算法14~19中，la、lb、lc为各个单链表的头指针，直接用头指针表示和操作单链表。15.la和lb分别为两个不带头结点的单链表，设计算法，从la中删除自i号元素起共len个结点，并将这len个结点插入到Ib中的i号结点之前。
•    算法14~19中、la、lb、Ic为各个单链表的头指针，直接用头指针表示和操作单链表。14·假设链表la有两种可能的状态：它或者有尾部（蛇），或者它的最后一个结点的指针域指向链表前面的某个结点（蜗牛）。给出一个算法判断给定的链表la是蛇还是蜗牛。
•    要求将算法7~13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。13·设计算法，在有序单链表中插入值为x的元素，并保持表的有序性。
•    要求将算法7-13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。12.设计算法，将一个整数的质因数进行分解并按递减顺序生成一个有序单链表。如输入2100,则生成的单链表中的元素从头开始依次为（7, 5, 5, 3, 2, 2)
•    要求将算法7~13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。11.设计算法，将给定的单链表中所有值为偶数的结点放在值为奇数的结点前面。
•    要求将算法7~13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。10.设计算法找出单链表中最后一个满足n%k=0的结点，n表示从首结点开始的结点个数（未知），k是给定的整型常数。
•    要求将算法7-13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。9.设计算法，删除单链表中的所有冗余元素，并返回删除的元素个数。例如，原线性表为：（7. 2, 1, 7, 2, 3, 6. 3. 5),去除冗余之后的表为：（7, 2. 1, 3, 6, 5)
•    要求将算法7-13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。8.设计算法，判断单链表中的元素是否中心对称。例如，线性表（1, 2, 3, 2, 1)及（1.2. 2. 1)是中心对称的。
•    要求将算法7~13设计为3. 4. 1节定义的带头结点单链表LinkedList类的方法。7.设计算法，定位单链表中间位置的结点。如线性表为（1, 2, 3. 4. 5),则中间位置元素为3;如线性表为（1, 2, 3, 4),则中间位置元素为2
•    要求将算法1-6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。6.设计算法，将有序顺序表中position位置的元素值替换为item,要求替换后的表仍保持有序。
•    要求将算法1~6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。5.设在某顺序表中，有一个整数在该表中的出现次数为奇数，其余整数的出现次数均为偶数。设计尽可能高效的算法，寻找出现次数为奇数的整数。例如：（1, 2. 5, 2,5. 1. 5)中，出现次数为奇数的整数为5
•    要求将算法1~6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。4.设计尽可能高效的算法，删除顺序表中所有值为x的元素。
•    要求将算法1-6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。3.设计算法，将整数顺序表所有元素划分为两部分，其中前面部分的元素都小于等于x,后面部分的元素都大于x.
•    要求将算法1~6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。2.设计算法，将顺序表中存放的元素循环左移p位。即L（a_o,a_1,a_2···.a_p···..a_n-1变为L= (a_p·a_p+1····.a_n-1.a_o····a_p-1)。
•    要求将算法1~6设计为3. 3. 4节定义的顺序表DynamicArrayList类的方法。1.设计算法，在顺序表中删除所有奇数位序的元素。
•    在线性表的以下链式存储中，若链表头结点的地址未知，仅已知p指针指向的结点，能否从中删除该结点？为什么？（1)单链表；（2)双链表；
•    线性表有两类存储结构，一是顺序表，二是链表。如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，同时线性表的总数也会不断改变。在此情况下，应选用哪种存储结构？为什么？
•    线性表的顺序存储结构具有三个弱点：其一，在进行插入或删除操作时，需移动元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量较难扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨论之。
•    说明顺序表和链表的优缺点和适用场合
•    以下算法的时间复杂度分别是多少？请用大O记号表示（1）将长度为n的顺序表置成空表。______；（2）将长度分别为m和n的递增有序单链表A和B合并成递减有序单链表C。（假设可以通过头指针直接访问链表的结点）______
•    给定两个有序顺序表A和B，设A表的长度为m，B表的长度为n，将两个有序表合并成有序表C，最坏情况下需进行______次比较
•    当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度按序号存取线性表的元素时，应采用______存储结构
•    在n个结点的双向循环链表中，若仅设尾指针，则访问首结点和尾结点的时间复杂度分别为______、______
•    在n个结点的单循环链表中，若仅设头指针，则访问首结点和尾结点的时间复杂度分别为______、______；若仅设尾指针，则访问首结点和尾结点的时间复杂度分别为______、______