数据结构期中考试试卷答案（最终定稿）
第一篇：数据结构期中考试试卷答案
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(n)C.O(n)
D.O(n)
33.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动（A）个元素。
A．n-i B．n-i+l C．n-i-1 D．i 4.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（B）。
A．s->next=p->next;p->next=s B．q->next=s;s->next=p C．p->next=s->next;s->next=p D．p->next=s;s->next=q 5.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。C A．top不变
B．top=0 C．top--D．top++ 6.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。D A．rear％n= = front B．（front+l）％n= = rear C．rear％n-1= = front D．(rear+l)％n= = front 7.两个字符串相等的条件是（D）。
A.两串的长度相等 B.两串的长度相等，并且两串包含的字符相同 C.两串包含的字符相同 D.两串的长度相等，并且对应位置上的字符相同
8.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开
始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（C）。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9.设有广义表D=(a,b,D)，其长度为（B），深度为（A）。A.无穷大 B.3
C.2 D.5 10.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（B）个。
A.15
B.16
C.17
D.47
二、填空题（每空1分，共20分）
1.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。2.集合，线性，树，图
2.一个算法的效率可分为__________________效率和__________________效率。4.时间，空间
3.当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。7．顺
（第1页，共3页）
序，链接
4.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。12．O(1)，O(n)5.可以在线性表的______位置插入和删除元素；对于栈只能在_______位置删除元素；对于队列只能在_______位置插入元素。9任何，栈顶，队尾 6.设字符串S1= “ABCDEF”，S2= “PQRS”，则运算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.（d1-c1+1）×（d2-c2+1）×（d3-c3+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结点的直接后继结点。(2)删除P结点。（3）删除尾元结点。3． LinkList mynote(LinkList L){//L是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L；
S1： while(p－>next)p=p－>next； S2： p－>next=q；q－>next=NULL；
} return L； } 请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2, „,an）,写出算法执行后的返回值所表示的线性表。
该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
四、算法设计题（每题14分，共42分）1.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针，已知p为指向链表中某结点的指针，设计在链表中删除p所指结点的前趋结点的算法。
数据结构与算法分析答案
解：可引入一个指针q，当q->next=p时，说明此时q所指的结点为p所指结点的前趋结点，从而可得算法如下：
void delete(LinkList *p){ //在链表中删除p所指结点的前趋结点 LinkList *q,*t;
q=p;
while(q->next->next!=p)//q->next不是p的前趋结点
（第2页，共3页）
q=q->next;
t=q->next;//t指向要删除结点
q->next=p;//删除t结点
free(t);｝
2.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。
2．算法描述如下：
delete(LinkList *head, int max, int min){ LinkList *p,*q;
q=head;
p=head->next;
while(p!=NULL)
if((p->data<=min)||(p->data>=max))
{ q=p;
p=p->next;
} else { q->next=p->next;free(p);p=q->next;} }
3.假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。
（第3页，共3页）
第二篇：数据结构期中试卷及答案
一、选择题（每小题2分，共30分）1.数据结构是（D）。
A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合
D．相互之间存在一种或多种特定关系的数据元素的集合
2．以下与数据的存储结构无关的术语是（D）。
A．链队列 B.链表 C.顺序表 D.栈
3．以下数据结构中，（A）是非线性数据结构
A．树 B．字符串 C．队 D．栈
4．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（B）。
A．98 B．100 C．102 D．106
5．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。A．插入 B．删除 C．排序 D．查
6．线性表采用链式存储时，其地址(D)。
A．必须是连续的 B．一定是不连续的 C．部分地址必须连续 D．连续与否均可以
7．线性表是(A)。
A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。