第一节
线性表的顺序表示

考点1　线性表的定义和性质

例．以下（　　）属于线性结构。【模拟题】

① 数组　　② 双向队列　　③ 栈　　④ 二叉树

A．②③

B．①

C．①④

D．①②③

【答案】 D

【解析】 本题考查线性表的定义。数组可视为顺序表，即线性结构，而队列和栈属于功能受到限制的线性表，二叉树为树形结构，故只有①、②和③属于线性结构。

知识链接

线性结构是一种数据结构，它的数据元素之间呈线性关系，即一对一的关系，除了第一个和最后一个元素，每个元素都只有一个直接前驱和一个直接后继。常见的线性结构有顺序表、链表、数组、栈和队列等。

考点2　顺序表的性质和操作

例1．对于长度为n的顺序表，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（　　）。【2013年广东工业大学】

A．n

B．n/2

C．（n−1）/2

D．（n+1）/2

【答案】 C

【解析】 本题考查顺序表的性质与操作。顺序表的删除需要将待删除位置之后的元素依次向前移动，因此删除第1个元素需要移动n−1次，删除第2个元素需要移动n−2次……删除第n个元素需要移动0次。平均移动次数=总移动次数/总元素个数=（n−1+n−2 +…+ 0）/n=（（n−1）n/2）/n=（n−1）/2，故本题的答案为C选项。

例2．若6行5列的数组以行序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是（　　）。【2015年中国科学院大学】

A．1040

B．1042

C．1026

D．以上答案都不对

【答案】 C

【解析】 本题考查顺序表的地址计算。根据题意，一行有5列，第1行第1列的地址为1000，第2行第1列的地址为1010，第3行第1列的地址为1020，则第3行第4列的地址为1026。 ptJscKD+mn9Ls9+5CAis223WLtqAtGbln1w5GPKtth02xDV2Cc/QB08Lo8R+yWPG