数据结构期中考试试卷答案.doc

《数据结构期中考试试卷答案.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2014－2015学年度第一学期《数据结构》期中考试试卷一、选择题（每题2分，共20分）1.计算机内部数据处理的基本单位是（B）。A.数据B.数据元素C.数据项D.数据库2.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O()C.O(n)D.O()3.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素。A．n-iB．n-i+lC．n-i-1D．i4.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s

2、结点，则须执行（B）。A．s->next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q5.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。CA．top不变B．top=0C．top--D．top++6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。DA．rear％n==f

3、rontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front7.两个字符串相等的条件是（D）。A.两串的长度相等B.两串的长度相等，并且两串包含的字符相同C.两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同8.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）。A.SA+141B.SA+144C.SA+222D.SA+2259.设有广义表D=(a,b,D)，其长度为（B

4、），深度为（A）。A.无穷大B.3C.2D.510.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。A.15B.16C.17D.47二、填空题（每空1分，共20分）1.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图2.一个算法的效率可分为__________________效率和__________________效率。4.时间，空间3.当对一个线性表经常进

5、行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。7（第3页，共3页）．顺序，链接4.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。12．O(1)，O(n)5.可以在线性表的______位置插入和删除元素；对于栈只能在_______位置删除元素；对于队列只能在_______位置插入元素。9任何，栈顶，队尾6.设字符串S1=“ABCDEF”，S2=“PQR

6、S”，则运算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值为___________________。3.“BCDEDE”7.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。1.线性结构，顺序结构，以行为主序，以列为主序8.三维数组R[c1…d1,c2…d2,c3…d3]共含有______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（

7、d-c+1）×（d-c+1）×（d-c+1）9.数组A[1…10，-2…6，2…8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。10.913三、简答题（每题6分，共18分）1.已知L是无表头结点的单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)在P结点后插入S结点。(2)在表首插入S结点。(3)在表尾插入S结点。2已知L是带表头结点的非空单链表，且P结点既不是首元结点也不是尾元结点，试写出合适的语句序列。(1)删除P结点的直

8、接后继结点。(2)删除P结点。（3）删除尾元结点。3．LinkListmynote(LinkL