计算机专业基础综合数据结构(线性表)历年真题试卷汇编5

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