第2章 线性表 一、单项选择题(每小题2分,共20分) ( )1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为: (A)存储结构 (B)逻辑结构 (C)顺序存储结构 (D)链式存储结构 ( )2. 一个向量第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是 (A)110 (B)108 (C)100 (D)120 ( )3. 在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是: (A) 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) (B) 在第i个结点后插入一个新结点(1≤i≤n) (C) 删除第i个结点(1≤i≤n) (D) 将n个结点从小到大排序 ( )4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动 个元素 (A)8 (B)63.5 (C)63 (D)7 ( )5. 链接存储的存储结构所占存储空间: (A) 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 (B) 只有一部分,存放结点值 (C) 只有一部分,存储表示结点间关系的指针 (D) 分两部分,一部分存放结点值,另一部分存放结点所占单元数 ( )6. 链表是一种采用 存储结构存储的线性表; (A)顺序 (B)链式 (C) (D)网状 ( )7. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址: (A)必须是连续的 (B)部分地址必须是连续的 (C)一定是不连续的 (D)连续或不连续都可以 ( )8. 线性表L在 情况下适用于使用链式结构实现。 (A)需经常修改L中的结点值 (B)需不断对L进行删除插入 (C)L中含有大量的结点 (D)L中结点结构复杂 ( )9. 单链表的存储密度 (A)大于1; (B)等于1; (C)小于1; (D)不能确定 ( )10. 设a1、a2、a3为3个结点,整数P0,3,4代表地址,则如下的链式存储结构称为 P0 3 4 P0  a1 3  a2 4  A3 0 (A)循环链表 (B)单链表 (C)双向循环链表 (D)双向链表 二、简答题(每小题10分,共20分) 1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好? 2 . 描述以下三个概念的区别:头指针、头结点、首元结点(第一个元素结点)。在单链表中设置头结点的作用是什么? 三、(15分)线性表具有两种存储方式,即顺序链接方式。现有一个具有五个元素的线性表L={23,17,47,05,31},若它以链接方式存储在下列100~119号地址空间中,每个结点由数据(占2个字节)和指针(占2个字节)组成,如下所示: 05 U 17 X 23 V 31 Y 47 Z ^ ^ 100 120 其中指针X,Y,Z的值分别为多少?该线性表的首结点起始地址为多少?末结点的起始地址为多少? 四、阅读分析题(15分) 指出以下算法中的错误和低效(即费时)之处,并将它改写为一个既正确又高效的算法。 Status DeleteK(SqList&a, int i, int k){ //本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素 if ( i<1 || k<0 || i+k> a.length ) return INFEASIBLE; //参数不合法 else{ for(count = 1; count =i+1; j--) a.elem[j-1] = a.elem[j]; a.length - -; } return OK; } // DeleteK 注:上题涉及的类型定义如下: # define LIST INIT SIZE 100 # define LISTINCREMENT 10 typedef struct { Elem Type *elem; //存储空间基址 Int length; //当前长度 Int listsize; //当前分配的存储容量 }SqList; 五、编程题(每题10分,共30分) 1. 写出在顺序存储结构下将线性表逆转的算法,要求使用最少的附加空间。 2. 已知L是无表头结点的单链表,且P结点既不是首元结点,也不是尾元结点,请写出在P结点后插入S结点的核心语句序列。 3. 编写程序,将若干整数从键盘输入,以单链表形式存储起来,然后计算单链表中结点的个数(其中指针P指向该链表的第一个结点)。