1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 2 及答案与解析一、单项选择题1 线性表是一个( ) 。 【电子科技大学 2010 一、1(2 分)】【江苏大学 2005 一、1(2 分)】（A）有限序列，可以为空（B）有限序列，不能为空（C）无限序列，可以为空（D）无限序列，不能为空2 线性表的顺序存储结构是一种( )。 【北京理工大学 2006 五、3(1 分)】（A）随机存取的存储结构（B）顺序存取的存储结构（C）索引存取的存储结构（D）Hash 存取的存储结构3 (多选 )在下列叙述中， ( )是错误的。【华中科技大学 2006 一、1(2 分)】（A）线性表的逻辑顺序与物理顺序
2、总是一致的（B）二叉树的顺序存储结构比链式存储结构节省存储空间（C）二叉树的度小于等于 2（D）每种数据结构都具有两种基本运算(操作)：插入、删除元素 (结点)4 能在 O(1)时间内访问线性表的第 i 个元素的结构是( )。【电子科技大学 2011一、2(2 分) 】（A）顺序表（B）单链表（C）单向循环链表（D）双向链表5 下面关于线性表的叙述中，错误的是哪一个?( )【北方交通大学 2001 一、14(2分)】（A）线性表采用顺序存储，必须占用一片连续的存储单元（B）线性表采用顺序存储，便于进行插入和删除操作（C）线性表采用链接存储，不必占用一片连续的存储单元（D）线性表采用链接存储，便
3、于插入和删除操作6 线性表是具有 n 个( ) 的有限序列(n0)。【清华大学 1998 一、4(2 分)】（A）表元素（B）字符（C）数据元素（D）数据项（E）信息项7 单链表中，增加一个头结点的目的是( )。 【厦门大学 2003 一、1(2 分)】（A）使单链表至少有一个结点（B）标识表结点中首结点的位置（C）方便运算的实现（D）说明单链表是线性表的链式存储8 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( ) 存储方式最节省时间。【哈尔滨工业大学 2001 二、1(2 分)】【烟台大学 2007 一、3(2 分) 】（A）顺序表（B）双链表（C）带头
4、结点的双循环链表（D）单循环链表9 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用 ( ) 存储方式最节省运算时间。【南开大学 2000 一、3】【华中科技大学2007 一、6(2 分) 】（A）单链表（B）仅有头指针的单循环链表（C）双链表（D）仅有尾指针的单循环链表10 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。【电子科技大学 2013 一、3(2 分)】【江苏大学 2006 一、3(2 分)】（A）单链表（B）单循环链表（C）带尾指针的单循环链表（D）带头结点的双循环链表11 若某线性表最常用的操作是在最后一个结点之后插入
5、一个结点或删除最后一个结点，则采用存储结构算法的时间效率最高的是( )。 【北京理工大学 2006 五、5(1 分)】（A）单链表（B）给出表尾指针的单循环链表（C）双向链表（D）给出表尾指针的双向循环链表12 对于一个线性表既要求能够进行较快速的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用( )。 【哈尔滨工业大学 2005 二、2(1 分)】（A）顺序存储方式（B）链式存储方式（C）散列存储方式（D）以上均可以13 在线性表的下列存储结构中，读取元素花费时间最少的是( )。【电子科技大学 2005 一、10(1 分) 】【北京理工大学 2006 五、6(1 分)】（A）顺序
6、表（B）单链表（C）双向链表（D）循环链表14 若线性表最常用的操作是存取第 I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式( ) 。【北京理工大学 2004 一、3(1 分)】（A）单链表（B）双向链表（C）单循环链表（D）顺序表15 在链式存储结构中，数据之间的关系是通过( )体现的。【北京理工大学 2005一、3 (1 分) 】（A）数据在内存的相对位（B）指示数据元素的指针（C）数据的存储地址（D）指针二、填空题16 删除长度为 n 的顺序表的第 l 个数据元之前需要移动表中 _个数据元素。(1in)【北京航空航天大学 2006 一、1(1 分)】17 对长度为 n 的线
7、性表采用顺序查找，在等概率的条件下，查找成功的平均检索长度为_。在长度为 n 的顺序表中删除第 i(1in)个数据元素需要移动_个数据元素。在长度为 n 的顺序表中的第 i(1in)个数据元素之前插入一个新元素，需要移动_个数据元素。【大连理工大学 2005 一、1(3 分)】18 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【北方交通大学 2001二、4】19 线性表 L=(a1，a 2，a n)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【北方交通大学 2001 二、9】20 在长
8、度为 n 线性表中插入一个元素，采用顺序存储结构的复杂度为_；采用链式存储结构的复杂度为_ 。【北京理工大学 2006 十、2(1 分)】三、判断题21 线性表的逻辑顺序与物理顺序总是一致的。 ( )【吉林大学 2006 一、1(1 分)】（A）正确（B）错误22 线性表中每个元素都有一个直接前驱和一个直接后继。( )【北京交通大学2005 三、1(2 分) 】（A）正确（B）错误23 线性表的插入、删除总是伴随着大量数据的移动。( )【北京邮电大学2006、2(1 分) 】（A）正确（B）错误24 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。( ) 【中国海
9、洋大学 2006 二、2(1 分) 】（A）正确（B）错误25 顺序存储方式只能用于存储线性结构。( )【哈尔滨工业大学 2005 三、5(1 分)】（A）正确（B）错误26 线性表中的所有数据元素的数据类型必须相同。( )【清华大学 2004】（A）正确（B）错误27 在顺序表中取出第 i 个元素所花费的时间与 f 成正比。 ( )【北京邮电大学2006 二、1(1 分) 】（A）正确（B）错误28 顺序存储的线性表可以随机存取。( )【中国海洋大学 2006 二、3(1 分)】（A）正确（B）错误29 顺序存储结构的主要缺点是不利于插入或删除操作。( )【南京航空航天大学1997 一、2(
10、1 分) 】（A）正确（B）错误30 取线性表的第 i 个元素的时间同 f 的大小有关。 ( )【南京理工大学 1997 二、9(2 分)】（A）正确（B）错误四、综合题31 简述单链表中设置头结点的作用。【电子科技大学 2008 三、1(6 分)】32 在单链表、双向链表和单向循环链表中，若仅知道指针 p 指向某结点，不知道头指针，能否将结点 p 从相应的链表中删去?若可以，其时间复杂度各为多少? 【吉林大学 2007 二、1(3 分)】计算机专业基础综合数据结构（线性表）历年真题试卷汇编 2 答案与解析一、单项选择题1 【正确答案】 A2 【正确答案】 A3 【正确答案】 A,B,D4 【
11、正确答案】 A5 【正确答案】 B6 【正确答案】 C7 【正确答案】 C8 【正确答案】 A【试题解析】 顺序表的优点之一是随机存取，即时间复杂度为 O(1)，而插入和删除的时间复杂度都是 O(n)。但是对于在最后插入结点和删除结点的时间复杂度都是 O(1)。9 【正确答案】 D【试题解析】 带有尾指针的单循环链表在最后插入结点和删除第一个元素的时间复杂度是 O(1)。带有头指针的单循环链表要在最后插入结点必须遍历整个链表。10 【正确答案】 D【试题解析】 带有尾指针的单循环链表删除尾结点时要遍历整个链表，时间复杂度是 O(n)。只有用带头结点的双循环链表完成要求的操作最节省时间，时间复杂
12、度是 O(1)。11 【正确答案】 D12 【正确答案】 B【试题解析】 散列存储方式是集合的一种表示方法，元素之间没有“逻辑关系”。B 是正确选择。13 【正确答案】 A14 【正确答案】 D15 【正确答案】 D二、填空题16 【正确答案】 ni17 【正确答案】 (n+1) 2 ，ni n 一 i+118 【正确答案】 顺序19 【正确答案】 (n 一 1)220 【正确答案】 O(n) O(1)三、判断题21 【正确答案】 B22 【正确答案】 B【试题解析】 非空线性表第一个元素无前驱，最后一个元素无后继。23 【正确答案】 B【试题解析】 叙述不严格，在最后插入元素和删除最后一个元
13、素，都不需要移动元素。24 【正确答案】 A25 【正确答案】 B26 【正确答案】 A27 【正确答案】 B28 【正确答案】 A29 【正确答案】 A30 【正确答案】 B四、综合题31 【正确答案】 在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义(当然有些情况下也可存放链表的长度、用做监视哨等)。有头结点后，链表指针(即头指针) 值是确定的，无论链表是否为空，头指针均不为空；对于链表操作，特别是插入或删除结点是第一元素结点的操作，就不用再作判断，与对其他结点的操作就统一了。32 【正确答案】 仅知道指针 p 指向某结点， (1)在单链表中不能将其删除，不知道头指针，无法查询到其前驱的指针。(2)在双向链表可以将其删除，时间复杂度是 O(1)。 (3)在单向循环链表中，可以将其删除，可以查询到其前驱的指针，时间复杂度是 O(n)。
