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++;3. 在一个长度为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=0c．topd．top++
6. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为___d
a．rear％n= =frontb．（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 ）。
9. 设有广义表d=(a,b,d)，其长度为（b ），深度为（a ）。
a.无穷大b.3c.2d.5
10. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（b ）个。
a. 15b. 16c. 17d. 47
二、填空题（每空1分，共20分）
1. 数据的逻辑结构有四种基本形态，分别是和2. 集合，线性，树，图。
2. 一个算法的效率可分为效率和效率。4. 时间，空间。
3. 当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用___存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用___存储结构为宜。7．顺序，链接。
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.（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结点的直接后继结点。(2) 删除p结点。（3）删除尾元结点。
3． linklist mynote(linklist l)
//l是不带头结点的单链表的头指针。
if(l&&l->next)
请回答下列问题：（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的前趋结点。
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))
else q->next=p->next;
free(p);
p=q->next;
3. 假设表达式有单字母变量和双目四则运算符构成。试写一个算法，对一个通常书写形式且书写正确的表达式求值。
数据结构期中考试试卷答案
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 3...
期中考试试卷答案
群星学校高二年级地理学科期中考试试卷。命题人 陈克斌 2011年4月。分值 100分时间 90分钟。第 卷 选择题，共50分 一 单项选择题 每题1分，共计50分。1 在下图中画斜线的四块假想陆地中面积最大的是。ab cd 2 在 的方位是。a 东南 b 西南。c 西北 d 东北 3 下图中a在b的...
答案期中考试试卷
赤峰学院2009 2010学年第一学期本科班。单片机原理及应用 考试试题。一 填空 每空1分，共20分 1 计算机三大总线分别为数据总线 地址总线和控制总线。2 mcs 51单片机51子系列有一个 8 位cpu 4 个通用并行口 全双工串行口 1 个 定时 计数器 2 个 中断源有 5 个，分为 2...