数据结构--线性表必考重点题型(二)--（详解）--PTA

梦里梦外; 2022-02-13 00:39 235阅读 0赞

### 线性表 ###

*   *   *  选择题:
         *   *   *  1.设有一个 12×12 的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是（）
                 *   *  A.50 B.51 C.55 D.66
                 *  2.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间（）
                 *   *  A.单链表
                     *  B.仅有尾指针的单循环链表
                     *  C.仅有头指针的单循环链表
                     *  D.带头结点的双循环链表
                 *  3.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？（）
                 *   *  A.单链表
                     *  B.双链表
                     *  C.单循环链表
                     *  D.带头结点的双循环链表
                 *  4.将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？（）
                 *   *  A.单链表
                     *  B.单循环链表
                     *  C.带尾指针的单循环链表
                     *  D.带头结点的双循环链表
                 *  5.采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2，则实现两个多项式相加的时间复杂度是：（）
                 *   *  A.O(N1+N2)
                     *  B.O(M1+M2)
                     *  C.O(N1×N2)
                     *  D.O(M1×M2)
                 *  6.将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：（）
                 *   *  A.1 B.N C.2N D.NlogN
                 *  7.

### 选择题: ###

##### 1.设有一个 12×12 的对称矩阵M，将其上三角部分的元素mi,j（1≤i≤j≤12）按行优先存入C语言的一维数组N中，元素m6,6在N中的下标是（） #####

###### A.50 B.51 C.55 D.66 ######

答案：**A**  
解析“上三角矩阵从第一行开始元素数量依次是：**12，11，10，9，8，7，6，5，4，3，2，1**，m6,6表示上三角区域的第**6**行第**1**个，所以m6,6为第51个元素，占数组位置为a\[50\]。

##### 2.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间（） #####

###### A.单链表 ######

###### B.仅有尾指针的单循环链表 ######

###### C.仅有头指针的单循环链表 ######

###### D.带头结点的双循环链表 ######

答案：**B**  
解析：注意，该题指明插入和删除是在最后一个元素之后操作的，所以尾结点可以直接往后操作，更省时间。

##### 3.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？（） #####

###### A.单链表 ######

###### B.双链表 ######

###### C.单循环链表 ######

###### D.带头结点的双循环链表 ######

答案：**D**  
解析：结合第三题，在没有尾结点的情况下，双循环链表可以直接操作表尾，所以更节省时间。

##### 4.将线性表La和Lb头尾连接，要求时间复杂度为O(1)，且占用辅助空间尽量小。应该使用哪种结构？（） #####

###### A.单链表 ######

###### B.单循环链表 ######

###### C.带尾指针的单循环链表 ######

###### D.带头结点的双循环链表 ######

答案“**C**  
解析：（单链表各种操作的时间复杂度在题型(一)中通过例题已详细说明）选项C和D的时间复杂度都为 O(1)，但C的指针少，占用的辅助空间更小。

##### 5.采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2，则实现两个多项式相加的时间复杂度是：（） #####

###### A.O(N1+N2) ######

###### B.O(M1+M2) ######

###### C.O(N1×N2) ######

###### D.O(M1×M2) ######

答案：**A**  
解析：M1和M2为干扰选项，与本题无关。实现两个多项式相加，必须把每个多项式都遍历一遍。

##### 6.将两个结点数都为N且都从小到大有序的单向链表合并成一个从小到大有序的单向链表，那么可能的最少比较次数是：（） #####

###### A.1 B.N C.2N D.NlogN ######

答案：**B**  
解析：

##### 7. #####

如图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]: /images/20220213/97582bb31603496eb25241f27cca69d5.png