数据结构习题解析与实训 第四章
第4章栈和队列
栈和队列是两种操作受到限制的特殊类型的线性表。
对栈中数据元素的操作要遵循元素后进先出的原则。栈可以分为顺序存储和链式存储两种实现方法。对栈中数据元素的操作要特别注意栈空条件、栈满条件和对栈顶指针操作的正确性。
队列的特点是对数据元素的操作要遵循元素先进先出的原则。队列的实现方法分为顺序存储和链式存储两种。改进后的顺序存储队列又称循环队列。对队列中数据元素的操作要特别注意队空条件、队满条件和对队头指针、队尾指针操作的正确性。
本章给出不同存储结构上的栈和队列的应用例举程序。
4.1习题解析
【习题1】数制转换(非负十进制整数转换为八进制数)
题目要求:将输入的非负十进制整数转换为八进制数输出,用栈结构实现,也可以用
递归算法实现。
结构说明:栈结构用顺序存储方式实现,结构设定如下所示。
#defineDATATYPE1int
#defineMAXSIZE100
typedefstruct
{DATATYPE1data[MAXSIZE];
inttop;
}SEQSTACK;
【解答1】
#include″datastru.h″
#include
voidinitstack(SEQSTACK＊s)
/＊顺序栈初始化＊/
{s->top=0;}
DATATYPE1gettop(SEQSTACK＊s)
/＊返回栈顶元素＊/
{ATATYPE1x;
if(s->top==0)
{printf(″栈空\n″);x=0;}
elsex=(s->data)[s->top];
returnx;
}
intpush(SEQSTACK＊s,DATATYPE1x)
/＊元素x入栈＊/
{f(s->top==MAXSIZE-1)
{printf(″栈满\n″);return0;}
else
{s->top++;(s->data)[s->top]=x;return1;}
}
DATATYPE1pop(SEQSTACK＊s)
/＊返回栈顶元素并删除栈顶元素＊/
{ATATYPE1x;
if(s->top==0){printf(″栈空\n″);x=0;}
else{x=(s->data)[s->top];s->top--;}
returnx;
}
main()
{EQSTACKstack,＊s;
intn;
s=&stack;initstack(s);n=0;
printf(″输入一非负整数(十进制):″);
scanf(″%d″,&n);push(s,′#′);
while(n!=0)
{push(s,n%8);/＊%为求余数运算符,余数入栈＊/
n=n/8;}/＊/为求整数商运算符,商不为零,继续运行＊/
printf(″\n\n对应的八进制数为:″);
while(gettop(s)!=′#′)printf(″%d″,pop(s));
第4章栈和队列l47
printf(″\n″);
}
【解答2】
这是一个用递归算法实现非负十进制整数转换为八进制数的程序,递归算法中用到
的栈由系统提供。一般将递归算法改写成非递归算法的时候要用到栈结构。
#include
voidd_to_or(intx)
/＊非负十进制整数转换为八进制数的递归算法＊/
{f(x/8!=0)d_to_or(x/8);
printf(″%d″,x%8);
}
main()
{intx;
printf(″输入一非负整数(十进制):″);
scanf(″%d″,&x);
printf(″\n\n对应的八进制数为:″);
d_to_or(x);
printf(″\n\n″);
}
【习题2】括号配对检查
题目要求:输入一个只有左括号“(”和右括号“)”的序列,程序对括号配对的正确性
检查并给出结果,配对检查的算法中用到栈结构。例如括号序列“(()())”、“()()(())”为
正确配对,括号序列“()())”、“()(()”、“)()(”为不正确配对等。注意:输入序列中只能出
现左括号“(”和右括号“)”,序列的语法正确性由用户保证。
结构说明:同上题。
【解答】
#include″datastru.h″
#include
voidinitstack(SEQSTACK＊s)
/＊顺序栈初始化＊/
{s->top=0;}
intpush(SEQSTACK＊s,DATATYPE1x)
/＊元素x入栈＊/
l48数据结构习题解析与实训
{f(s->top==MAXSIZE-1){printf(″栈满\n″);return0;}
else{s->top++;(s->data)[s->top]=x;return1;}
}
DATATYPE1pop(SEQSTACK＊s)
/＊返回栈顶元素并删除栈顶元素＊/
{ATATYPE1x;
if(s->top==0){printf(″栈空\n″);x=0;}
else{x=(s->data)[s->top];s->top--;}
returnx;
}
DATATYPE1gettop(SEQSTACK＊s)
/＊返回栈顶元素＊/
{ATATYPE1x;
if(s->top==0){printf(″栈空\n″);x=0;}
elsex=(s->data)[s->top];
returnx;
}
check(SEQSTACK＊s)
{
intbool;
charch;
push(s,′#′);printf(″\n请输入一串括号,回车键结束:″);
ch=getchar();bool=1;
while(ch!=′\n′&&bool)
{f(ch==′(′)push(s,ch);/＊遇到左括号,左括号入栈＊/
if(ch==′)′)/＊遇到右括号:＊/
if(gettop(s)==′#′)bool=0;/＊栈顶元素为#号,配对错误＊/
elsepop(s);/＊栈顶元素为左括号,消括号＊/
ch=getchar();}/＊继续处理＊/
if(gettop(s)!=′#′)bool=0;
if(bool)printf(″\n括号配对正确\n″);
elseprintf(″\n括号配对错误\n″);
}
main()
{
第4章栈和队列l49
SEQSTACKst,＊s;
s=&st;
initstack(s);
check(s);
}
【习题3】链队列管理
题目要求:这是一个加深理解在链队列结构上插入和删除元素的程序。
首先建立带头结点的空链队列,接下来如果输入奇数,则奇数入队列;如果输入偶数,
则队列中的第一个元素出队列;如果输入0,则退出程序。程序中可反复输入奇数和偶
数,直至输入0退出程序。
结构说明:队列用链表结构实现,结构如下所示。
#defineDATATYPE1int
typedeftructqnode
{ATATYPE1data;
structqnode＊next;
}LINKQLIST;
typedefstruct
{LINKQLIST＊front,＊rear;
}LINKQUEUE;
【解答】
#include″datastru.h″
#include
#include
DATATYPE1dellinkqueue(LINKQUEUE＊q)
/＊删除队头元素并返回＊/
{INKQLIST＊p;
DATATYPE1v;
if(q->front==q->rear){printf(″队列空\n″);v=0;}
else{p=(q->front)->next;
(q->front)->next=p->next;
if(p->next==NULL)q->rear=q->front;
v=p->data;
free(p);}
returnv;
}
l50数据结构习题解析与实训
voidenlinkqueue(LINKQUEUE＊q,DATATYPE1x)
/＊元素x入队列＊/
{q->rear)->next=(LINKQLIST＊)malloc(sizeof(LINKQLIST));
q->rear=(q->rear)->next;(q->rear)->data=x;
(q->rear)->next=NULL;
}
voidinitlinkqueue(LINKQUEUE＊q)
/＊链队列初始化＊/
{q->front=(LINKQLIST＊)malloc(sizeof(LINKQLIST));
(q->front)->next=NULL;q->rear=q->front;
}
voidoutlinkqueue(LINKQUEUE＊q)
/＊链队列元素依次显示＊/
{INKQLIST＊p;
p=q->front;printf(″队列元素显示:″);
while(p!=q->rear)
{p=p->next;printf(″%d″,p->data);}
printf(″\n″);
}
main()
{
LINKQUEUElq,＊p;
DATATYPE1j;
p=&lq;
initlinkqueue(p);
printf(″输入一整数(奇数———入队列、偶数———删除队头元素、0———退出):″);
scanf(″%d″,&j);
while(j!=0)/＊输入0———退出＊/
{f(j%2==1)enlinkqueue(p,j);/＊输入奇数———入队列＊/
elsej=dellinkqueue(p);/＊输入偶数———删除队头元素＊/
outlinkqueue(p);
printf(″\n输入一整数(奇数———入队列、偶数———删除队头元素、0———退出):″);
scanf(″%d″,&j);}/＊继续输入＊/
}
【习题4】打印杨辉三角系数
题目要求:将二项式(a+b)i展开,其系数构成杨辉三角形,按行将展开式系数的前n
第4章栈和队列l51
l52
数据结构习题解析与实训 行显示出来。杨辉三角系数如下所示。
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
从三角形的结构可知,除第一行以外,在显示第i 行时,可利用上一行(第i-1行)的
数据。在显示第i+1行时,又可用到第i 行的数据。若在每行的两边各加上一个0,如 图4．1所示 。
图4.1 第i 行元素与第i+1行元素的关系
可以很清楚地看到下一行的系数可在上一行显示的同时计算出来。在程序中设置一 个队列,在输出上一行系数时,同时计算下一行的系数并预先存入队列中。在各行系数之 间插入一个0,为计算方便用。
结构说明:同上题。
【解答】
#include ″datastru.h″
#include
#include
DATATYPE1dellinkqueue(LINKQUEUE ＊q)
/＊删除队头元素并返回＊/
{INKQLIST ＊p;
DATATYPE1v;
if(q->front==q->rear)
{printf(″队列空\n″);v=0;}
else
{p=(q->front)->next;
(q->front)->next=p->next;
if(p->next==NULL)
q->rear=q->front;
v=p->data;
free(p);}
returnv;
}
DATATYPE1getlinkqueue(LINKQUEUE＊q)
{/＊返回队头元素＊/
DATATYPE1v;
if(q->front==q->rear){printf(″队列空\n″);v=0;}
elsev=(q->front)->next->data;
returnv;
}
voidenlinkqueue(LINKQUEUE＊q,DATATYPE1x)
{/＊元素x入队列＊/
(q->rear)->next=(LINKQLIST＊)malloc(sizeof(LINKQLIST));
q->rear=(q->rear)->next;
(q->rear)->data=x;
(q->rear)->next=NULL;
}
voidinitlinkqueue(LINKQUEUE＊q)
{/＊链队列初始化＊/
q->front=(LINKQLIST＊)malloc(sizeof(LINKQLIST));
(q->front)->next=NULL;
q->rear=q->front;
}
voidmain(){
LINKQUEUE lq,＊q;
intn,s,t,k,i,m,j;
printf(″打印杨辉三角形,输入行数:″);
scanf(″%d″,&n);q=&lq;
initlinkqueue(q);/＊链队列初始化＊/
enlinkqueue(q,1);enlinkqueue(q,1);/＊预先放入第一行的两个系数1＊/
s=0;/＊计算下一行系数时用到的工作单元＊/
for(i=1;i<=n;i++){/＊逐行处理＊/
printf(″\n″);/＊换行＊/
for(m=i;m<=n;m++)p rintf(″″);
enlinkqueue(q,0);/＊各行之间插入一个0＊/
for(j=1;j<=i+2;j++){/＊处理第i行的i+2个系数(包括一个0)＊/
第4章栈和队列l53
t=getlinkqueue(q);/＊取队头元素＊/
k=dellinkqueue(q);/＊删除队头元素＊/
enlinkqueue(q,s+t);/＊计算下一行的系数,入队列＊/
s=t;
if(j!=(i+2))pr intf(″%d″,s);/＊打印一个系数,第i+2个是0,不显示＊/
}
printf(″\n″);
}
printf(″\n\n″);
}
4.2实训练习題
【习题5】数制转换(非负十进制整数转换为二进制数)
题目要求:编两个程序将输入的非负十进制整数转换为二进制数并输出显示。一个
程序用栈结构实现;一个程序用递归算法实现。算法的思路可参考本章【习题1】数制转
换(非负十进制整数转换为八进制数)程序。
【习题6】非负十进制整数逆向显示
题目要求:将输入的非负十进制整数逆向显示,如输入1234,输出显示4321。用递
归算法实现。
【习题7】打印下列图案
题目要求:用递归算法打印下列图案,图案的行数作为参数由用户输入。
1
22
333
4444
…
l54数据结构习题解析与实训
经典数据结构面试题(含答案)
栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________
数据结构习题(,,章)
数据结构习题(,,章)
————————————————————————————————作者：————————————————————————————————日期：
第四章串 一．选择题 1．若串S='software',其子串的数目是（） A．8 B．37 C．36 D．9 2．设有两个串p和q,求q在p中首次出现的位置的运算称作（） A．连接B．模式匹配C．求串长D．求子串 3．设字符串S1=“ABCDEFG”，S2=“PQRST”，则运算： S=CONCAT（SUBSTR（S1，2，LEN（S2））；SUBSTR（S1，LEN（S2），2））；后的串值为（） A．A BCDEF B．BCDEFG C．BCDPQRST D． BCDEFEF 4．下面的说法中，只有（）是正确的 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母D．空串就是空白串 5．两个字符串相等的条件是（） A．两串的长度相等 B．两串包含的字符相同 C．两串的长度相等，并且两串包含的字符相同 D．两串的长度相等，并且对应位置上的字符相同 二．填空题 1．串“ababcbaababd”的next函数值为，nextval函数值为。2．子串的长度为。 第五章数组和广义表 一．选择题 1．设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( ) A. BA+141 B. BA+180 C. BA+222 D. BA+225 2．假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（） A. 808 B. 818 C. 1010 D. 1020 3．对稀疏矩阵进行压缩存储目的是（） A．便于进行矩阵运算B．便于输入和输出C．节省存储空间D．降低运算的时间复杂度 4．假设以三元组表表示稀疏矩阵，则与如图所示三元组表对应的4×5的稀疏矩阵是（注：矩阵的行列下标均从1开始）（）
数据结构模拟卷(含答案)经典习题培训讲学
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )
数据结构课后习题答案第四章
第四章 一、简述下列每对术语的区别： 空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答： ●空串是指不包含任何字符的串，它的长度为零。 空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。 ●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。 ●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。 动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。 ●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。 二、假设有如下的串说明： char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p; (1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,","); strcat(s3,s2); (3)调用函数strcmp(s1,s2)的返回值是什么?
数据结构课后习题及解析第二章
第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2
数据结构复习题三
数据结构练习题 第一章绪论 一．选择题 1、在数据结构的讨论中把数据结构从逻辑上分为（）。 A.内部结构与外部结构 B.静态结构与动态结构 C.线性结构与非线性结构 D.紧凑结构与非紧凑结构 2、采用线性链表表示一个向量时，要求占用的存储空间地址（）。A: 必须是连续的 B 部分地址必须是连续的 C: 一定是不连续的C: 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。 A: n B: n/2 C: (n-1)/2 D: (n+1)/2 4、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。 A: s→next = p→next;p→next = s; B: p→next= s; s→next = q; C: p→next = s→next;s→next = p;D: q→next= s;s→next= p; 8.下面程序段的时间复杂度为____________。 for(int i=0; i 二．填空题 1.通常，评价一个算法有正确性、健壮性、_________、时间复杂度、空间复杂度五个方面。 2.在数据结构中，数据的逻辑结构有线性结构、图结构、________________、_______________四种，物理实现上有顺序结构、索引结构、___________、_____________四种。 第三章线性表 一．选择题 1.在一个单链表HL中,若要向q所指结点之后插入一个指针p指向的结点,则执行. A. HL=p; p->next=HL B. P->next=HL; HL=p C. P->next=q->next; q->next=p D. P->next=q->next; q=p->next 2.在一个长度为n的顺序存储线性表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需要从后向前依次后移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3.在一个长度为n的顺序存储线性表中，删除第i个元素(1≤i≤n+1)时，需要从前向后依次前移个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 4.在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为。 A、n B、n/2 C、(n+1)/2 D、(n-1)/2 5.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next = HL; p = HL; D、p->next = HL->next; HL->next = p; 6.在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; 数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include #define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 江南大学现代远程教育第一阶段练习题及答案 考试科目:《数据结构》第一章至第四章（总分100分） ______________学习中心（教学点）批次：层次： 专业：学号：身份证号： 姓名：得分： 一、选择题（每题3分，共30分） 1、在树形结构中，数据元素间存在（）的关系。 Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系 2、下列说法中错误的是（）。 Ａ、数据对象是数据的子集 Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构 Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系 Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 3、下列不属算法特性的是（）。 Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性 4、在长为n的顺序表中删除一个数据元素，平均需移动（）个数据元素。 Ａ、n Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2 5、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 Ａ、顺序表Ｂ、双链表Ｃ、带头结点的双向循环链表Ｄ、单循环链表 6、在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（）。 Ａ、不变Ｂ、top=n Ｃ、top++ Ｄ、top-- 7、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（）。 Ａ、rear=front->next Ｂ、rear=rear->next Ｃ、front=front->next Ｄ、front=rear->next 8、判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（）。 Ａ、S Ｂ、S->next Ｃ、S->next==NULL Ｄ、!S 9、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。 Ａ、front->next Ｂ、rear->next Ｃ、front==rear Ｄ、front!=rear 10、串的长度是指（）。 .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ I Single Choice(10 points) 1. ( a )For the following program fragment the running time(Big-Oh) is . i = 0; s = 0; while(s <( 5*n*n + 2)) { i++; s = s + i; } a. O(n) b. O(n2) c. O(n1/2) d. O(n3) 2. ( c )Which is non-linear data structure_____. a. queue c. tree d. sequence list 3.( b )The worst-time for removing an element from a sequence list (Big-Oh) is . a. O(1) b. O(n) c. O(n2) d. O(n3) 4.( d )In a circular queue we can distinguish(区分) empty queues from full queues by . a. using a gap in the array b. incrementing queue positions by 2 instead of 1 a count of the number of elements d. a and c 5.( b )A recursive function can cause an infinite sequence of function calls if . a.the problem size is halved at each step b.the termination condition is missing c.no useful incremental computation is done in each step d.the problem size is positive 6．( c )The full binary tree with height 4 has nodes. a. 15 b. 16 7. ( b )Searching in an unsorted list can be made faster by using . a.binary search 《数据结构》课程设计题目 (程序实现采用C语言) 题目1：猴子选王（学时：3） 一堆猴子都有编号，编号是1，2，3 ...m，这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。 要求：m及n要求从键盘输入，存储方式采用向量及链表两种方式实现该问题求解。 //链表 #include { pCurr = (RingNodePtr)malloc(sizeof(RingNode)); i++; pCurr->pos = i; pPrev->next = pCurr; pPrev = pCurr; } pCurr->next = pHead; // 构成环状链表 } void KickFromRing(RingNodePtr pHead, int n) { RingNodePtr pCurr, pPrev; int i = 1; // 计数 pCurr = pPrev = pHead; while(pCurr != NULL) { if (i == n) { // 踢出环 printf("\n%d", pCurr->pos); // 显示出圈循序 pPrev->next = pCurr->next; free(pCurr); pCurr = pPrev->next; i = 1; } pPrev = pCurr; 绪论和线性表习题 一、选择题 1.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s->next=p；p->next=s; B、s->next=p->next; p->next=s； C. s->next=p->next;p=s; D. p->next=s;s->next=p; 2.与单链表相比,双链表优点之一( ). A.插入删除操作更简单. B.可随机访问 C.可省略表头指针和表尾指针 D、顺序访问相临结点更灵活 3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为( ) A、 n-i+1 B.n-i C.i D.i-1 4.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A.顺序表 B.用头指针表示的单循环链表 C、用尾指针表示的单循环链表 D.单链表 5.在需要经常查找结点的前驱与后继的场合中，使用( )比较合适。 A.单链表B、双链表 C.顺序表 D.循环链 表 6.下面关于线性表的叙述中，错误的为( ) A.顺序表使用一维数组实现的线性表 B.顺序表必须占用一片连续的存储单元 C.顺序表的空间利用率高于链表 D、在链表中，每个结点只有一个链域 7.带头结点head的单链表为空的判断条件是( ) A. head=NUIL B、head->next=NUIL C. head->next=head D. head!=NUIL 8.线性表通常采用两种存储结构是( ) A、顺序存储结构和链式存储结构 B.散列方式和索引方式 C.链表存储结构和数组 D.线性存储结构和非线性存储结构 9．线性表采用链式存储时，结点的存储地址（） A．必须是不连续的 B、连续与否均可 C．必须是连续的 D．和头结点的存储地址相连续 10．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（） A．O（1） B．O（n） C、 O（m） D．O（m+n） 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 数据结构经典例题 1.设计一个算法将L拆分成两个带头节点的单链表L1和L2。 void split(LinkList *&L,LinkList *&L1,LinkList *&L2) { LinkList *p=L->next,*q,*r1; //p指向第1个数据节点 L1=L; //L1利用原来L的头节点 r1=L1; //r1始终指向L1的尾节点 L2=(LinkList *)malloc(sizeof(LinkList));//创建L2的头节点 L2->next=NULL; //置L2的指针域为NULL while (p!=NULL) { r1->next=p; //采用尾插法将*p(data值为ai)插入L1中 r1=p; p=p->next; //p移向下一个节点(data值为bi) q=p->next; //由于头插法修改p的next域,故用q保存*p的后继节点 p->next=L2->next; //采用头插法将*p插入L2中 L2->next=p; p=q; //p重新指向ai+1的节点 } r1->next=NULL; //尾节点next置空 } 2.查找链表中倒数第k个位置上的节点（k为正整数）。若查找成功，算法输出该节点的data域的值，并返回1；否则，只返回0。 typedef struct LNode {int data; struct LNode *link; } *LinkList; int Searchk(LinkList list,int k) { LinkList p,q; int count=0; p=q=list->link; while (p!=NULL) { if (count 第四章串 习题4 一、选择题 1.串是一种分外的线性表，其分外性体现在（）。 A.可以顺序存储 B.数据元素是一个字符 C.可以连接存储 D.数据元素可以是多个字符 2.有两个串P和Q，求P在Q中首次出现的位置的运算称为（）。 A.模式匹配 B.联接 C.求子串 D.求串长 3.设S为一个长度为n的字符串，其中的字符各不相同，则S中的互异的非通俗子串（非空且例外于S本身）的个数为（）。 A.n2 B.（n2/2）+（n/2） C.（n2/2）+（n/2）-1 D.（n2/2）-（n/2）-1 4.设串s1=“ABCDEFG”,s2=“PQRST”，函数concat（x，y）返回x和y串的连接串，subString（s，i，j）返回串s的从序号i的字符开始的j个字符组成的子串，Strlength（s）返回串s的长度，则concat（subString（s1，2，Strlength （s2）），subString(s1，Strlength（s2），2)））的结果串是（）。 A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 5.顺序串中，根据空间分配方式的例外，可分为（）。 A.直接分配和间接分配 B.静态分配和动态分配 C.顺序分配和链式分配 D.随机分配和不变分配 6.设串S=“abcdefgh”，则S的所有非通俗子串（除空串和S自身的串）的个数是（）。 A.8 B.37 C.36 D.35 7.设主串的长度为n，模式串的长度为m，则串匹配的KMP算法时间复杂度是（）。 A.O(m) B.O（n） C.O（m+n） D.O（n*m） 8.已知串S=“aaab”，其next数组值为（）。 A.0123 B.1123 C.1231 D.1211 二丶填空题 1.在空串和空格串中，长度不为0的是（）。 2.空格串是指（），其长度等于（）。 3.按存储结构的例外，串可分为（）、（）和（）。 4.C语言中，以字符（）表示串值的终结。 5.在块链串中，为了提高存储密度，应该增大（）。 6.假设每个字符占1个字节，若结点大小为4个字节的链串的存储密度为50％，则其每个指针占（）个字节。 7.串操作虽然较多，但都可以通过五中基本操作（）、（）、（）、（）和（）构成的最小子集中的操作来实现。 8.设串S=“Ilikecomputer.”，T=“com”，则Length（S）=（），Index（S,T,1）=（）。 9.在KMP算法中，next[j]只与（）串有关，而与（）串无关。 10.字符串“ababaaab”的nextval函数值为（）。 11.两个字符串相等的充分必要条件是（）。 12.实现字符串复制的函数strcpy为： 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 基本概念典型例题 一、单项选择题 [例6-1]数据结构用集合的观点可以表示为一个二元组DS＝(D，R)。其中，D是( ①)的有穷集合，R是D上( ②)的有限集合。 ①A.算法B. 数据元素C. 数据操作D. 逻辑结构 ②A. 操作B. 映像C. 存储D．关系 解析：由数据结构的集合形式化定义可知，本题答案为：①B；②D。 [例6-2]数据的常用存储结构中不包括( )。 A．顺序存储结构B．线性结构C．索引存储结构D．散列存储结构 解析：数据通常有四种基本的存储方法，即顺序存储方法、链式存储方法、索引存储 方法和散列存储方法。由此可知，本题答案为：B。 [例6-3] 算法指的是( ①)，它必须具备( ②)这三个特性。 ①A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法 ②A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性 C．确定性、有穷性、稳定性D．易读性、稳定性、安全性 解析：算法是对特定问题求解步骤的一种描述，是由若于条指令组成的有限序列。它 必须满足以下性质：输人性、输出性、有穷性、确定性、无二义性和可行性。由此可知，本 题答案为：①㈠②B。 [例6-4] 在下面的程序段中，对x的赋值语句的执行频度为( )。 for(i=0；i 第四章习题（P111-113） 一、复习题 1、试述数据和数据结构的概念及其区别。 数据是对客观事物的符号表示，是信息的载体；数据结构则是指互相之间存在着一种或多种关系的数据元素的集合。（P93） 2、列出算法的五个重要特征并对其进行说明。 算法具有以下五个重要的特征：有穷性：一个算法必须保证执行有限步之后结束。确切性：算法的每一步骤必须有确切的定义。输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件。输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法没有实际意义。可行性：算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。（P95） 3、算法的优劣用什么来衡量试述如何设计出优秀的算法。 时间复杂度空间复杂度（P97-98） 4、线性和非线性结构各包含哪些种类的数据结构线性结构和非线性结构各有什么特点 线性结构用于描述一对一的相互关系，即结构中元素之间只有最基本的联系，线性结构的特点是逻辑结构简单。所谓非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型和图型结构就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。（P99-105） 5、简述树与二叉树的区别；简述树与图的区别。 树用来描述层次结构，是一对多或多对一的关系；二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。二叉树是有序的，即若将其左、右子树颠倒，就成为另一棵不同的二叉树。图也称做网，是一种比树形结构更复杂的非线性结构。在图中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的，图表示的多对多的关系。（P102-P104） 6、请举出遍历算法在实际中使用的例子。 提示：根据实际生活中需要逐个访问处理的情况举例。 7、编写一个算法，统计在一个输入字符串中各个不同字符出现的频度。用适当的测试数据来验证这个算法。 提示：根据查找算法和串中求子串的算法，查找输入串中以单个字符形式的子串。 8、若对有n个元素的有序顺序表和无序顺序表进行顺序搜索，试就下列三种情况分别讨论两者在等搜索概率时的平均搜索长度是否相同 (1) 搜索失败； (2) 搜索成功，且表中只有一个关键码等于给定值k的对象； (3) 搜索成功，且表中有若干个关键码等于给定值k的对象，要求一次搜索找出所有对象。经典数据结构上机题_答案解析
数据结构第1阶段练习题
经典数据结构面试题(含答案)
数据结构例题解析(1)
数据结构经典题目c语言代码
数据结构 习题
数据结构第一章课后习题与答案
数据结构经典例题
数据结构课后习题第四章
数据结构上机例题及答案
数据结构典型例题
第4章数据结构与算法习题与答案
- 数据结构习题参考答案与解析
- 严蔚敏版数据结构课后习题集答案解析完整版
- 《数据结构》练习题库及答案解析
- 严蔚敏数据结构课后习题及答案解析
- 数据结构课后习题详解(超完整超经典)
- 数据结构习题和答案及解析
- 数据结构习题和答案及解析
- 数据结构习题集及答案
- 数据结构（递归、数组、矩阵）练习题与答案
- 数据结构各章习题及答案!
- 数据结构1800题含答案详解
- (完整版)数据结构课后习题答案
- 数据结构习题与答案
- 数据结构课后习题详解(超完整,超经典)
- 数据结构课后习题答案详解(C语言版_严蔚敏)
- 数据结构习题及答案
- 数据结构课后习题答案
- 严蔚敏版数据结构课后习题答案-完整版
- 数据结构课后习题答案
- 数据结构习题集答案解析_清华大学版