数据结构习题(二)
数据结构习题（二）
一、填空题
1. 队列的插入操作在 进行，删除操作在 进行。
2. 在栈结构中，允许插入、删除的一端称为 , 另一端称为 。
3. 假设以S 和X 分别表示进栈和退栈操作，则对输入序列a,b,c,d,e 进行一系列栈操作SSXSXSSXXX 之后，得到的输出序列为 。
4. 一个不带表头结点且不空链栈的栈顶指针是top ，栈中元素的值域为data ，则栈顶元素即为__ ____ _。
5. 一个带表头结点链栈的栈顶指针是top ，每个结点包含值域data 和指针域next ，当进行出栈操作时，则需要修改指针域的操作为 。
6.设数组S[M]存储一个顺序栈的元素，变量top 指示下一个入栈元素在数组中的下标位置，栈为空的条件是___ _____，栈为满的条件是___ _____。
7. 在一个用一维数组a[N]存储的顺序循环队列中，该队列中的元素最少为 个，最多为 个。
8. 在具有SIZE 个数据元素的顺序存储的循环队列中，假定front 和rear 分别指示队列里第一个元素的前一位置和最后一个元素的位置，则判断队空的条件是________ ；队满的条件是 ；队中元素个数为 。
9. 空串是 ；空格串是 。
10. 设两个串S1和S2，求S1在S2中首次出现的运算称为_______ _。
11.串中任意个连续的字符组成的子序列称为该串的 。
12. 假设一个10阶的下三角矩阵A 按列优顺序压缩存储在一维数组C 中，则C 数组的体积最小应为
13. 在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的_____________、___________和___________三项。
14. 广义表A=(a,(b),(),(c,d,e))的长度为 ；已知广义表的表头为a ，表尾为(b,c)，则此广义表为 。
15. 如图所示，用一个
体积为MAX 的数组
同时构造两个栈S1和
S2，栈S1的栈底是下
标为0的这一端，栈S2的栈底是下标为MAX-1的这一端，整型变量top1标记栈S1的栈顶位置，整型变量top2
标记栈S2的栈顶位置。两个栈的初始状态为：top1=0，top2=MAX-1。则栈满的条件
为 。
012MAX-1
二、选择题
1．在栈中存取数据的原则是；在队列中存取数据的原则是。
A. 先进先出
B. 后进先出
C. 后进后出
D. 随意进出
2．一个栈的输入序列为A B C D E，则下列序列中不可能是栈的输出序列的是_______。
A. BCDAE
B. DCABE
C. BCADE
D. AEDCB
3．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为。
A. 4
B. 5
C. 6
D. 7
4．假定利用数组a[N]顺序存储一个栈，用top表示下一个入栈元素的下标位置，top==0表示栈空，并已知栈未满，当元素x进栈时所执行的操作为。
A. a[--top]=x;
B. a[++top]=x;
C. a[top++]=x;
D. a[top--]=x;
5．向一个不带表头结点栈顶指针为top的链栈中插入一个s所指结点时，执行________。
A. top->next=s；
B. s->next=top->next；top->next=s；
C. s->next=top;top=s；
D. s->next=top;top=top->next；
6．已知循环队列的存储空间为数组data[21]，假定front和rear分别指示队列里第一个元素的前一位置和最后一个元素的位置，且front的值为8，rear的值为3，则该队列的当前长度为。
A. 5
B. 6
C. 16
D. 17
7．在栈中出栈操作的时间复杂度为。
A. O(1)
B. O(log2n)
C. O(n)
D. O(n2)
8．串的长度是。
A. 串中不同字符的个数
B. 串中不同字母的个数
C. 串中所含字符的个数且字符个数大于零
D. 串中所含字符的个数
9．设有说明char S2[]= “A _TEACHER”；则strlen(S2)的返回值为________。
A. 1
B. 8
C. 9
D. 11
10．在C语言中，定义二维数组数组A[5][6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[4][4]的地址为。
A. 1140
B. 1145
C. 1120
D. 1125
11．在c语言中，已知字符数组A[8][10]中元素A[2][1]的地址为1000，则元素A[0][0]的地址为______。
A. 972;
B. 979
C. 980
D. 982
12．对广义表L=((a,b),c,d)进行操作tail(head(L))的结果是。
A. (c,d)
B. (d)
C. b
D. (b)
13．从广义表LS=((p,q),r,s)中分解出原子q的运算是。
A. tail(head(LS))
B. head(tail(head(LS)))
C. head(tail(LS))
D. tail(tail(head(LS)))
三、阅读程序
1、设在头文件stack.h中已定义如下函数，原型为：
初始化栈：void InitStack(SeqStack *s)
入栈：void Push(SeqStack *s, datatype e)
出栈：datatype Pop(SeqStack *s)
判栈空：int EmptyStack(SeqStack *s)
运行下面程序，当输入值为：493 13 ，给出输出结果：
#include
typedef char datatype;
#include “stack.h”
void Trans(int m, int k, char s[])
{ int i,d;
SeqStack st;
InitStack(&st);
do{
d=m%k;
if(d<10) Push(&st, d+’0’);
else Push(&st, d-10+’a’);
}while(m/=k);
i=0;
while(!EmptyStack(&st))
s[i++]=Pop(&st);
s[i]=’\0’;
}
main()
{ int m, k;
char s[10];
scanf(“%d %d”, &m, &k);
Trans(m, k, s);
printf(“\ns=%s”, s);
}
2、程序填空：设有一个带头结点的单链表来构造一个队列，其数据结构类型定义为：
typedef struct node{
datatype data;
struct node *next;
}LQNode, *LinkQueue;
typedef struct{
LinkQueue front, rear; /*front：队头指针，rear：队尾指针*/
}Queue;
如下定义的函数是一个入队函数，请在空格中填写合适内容以完善该函数。
void EnQueue(Queue *q, datatype x)
{ LinkQueue p;
p= ; /*向系统申请一个结点*/
=x; /*向结点赋值*/
p->next=q->rear->next;
; /*把p结点链到队尾*/
q->rear=p;
}
四、算法设计题
1、假设有一个循环队列，数据类型定义如下，其中f表示队头元素的前一个位置，r表示队尾元素位置：
typedef struct {
datatype data[MAX];
int f, r;
}SeqQueue;
（1）设计一个入队函数：EnQueue(SeqQueue *q, datatype x)
（2）设计一个出队函数datatype DeleteQueue(SeqQueue *q)
2、假设采用C语言的格式表示一个串。请编写一个朴素模式匹配函数int index (char *s, char *t)，其中形参s表示原串，t表示模式串，功能是求t在s中首次出现的位置。若出现，函数返回在s串中出现的起始下标值；若不出现，则返回-1。
《数据结构》第二章习题参考答案 殷人昆版
《数据结构》第二章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题 （1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题
经典数据结构面试题(含答案)
栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 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．数据的基本单位是( B ) A．数据B．数据元素C．数据项D．数据结构 2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素 D．数据项 3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型 C．逻辑结构D．物理结构 4．数据的逻辑结构可分为（C） A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B ) A．LOC(1)+i*m B．LOC(1)+(i-1)*m C．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D） A．所有结点的地址必须是连续的 B．部分结点的地址必须是连续的 C．所有结点的地址一定不连续 D．所有结点的地址连续、不连续都可以 7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的 C．连续不连续都可以D．部分是连续的
8．下列不属于线性结构的是( C )。 A．单链表B．队列 C．二叉树D．数组 9．链表不具有的特点是( A) A．可随机访问任一元素B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与线性表的长度成正比 10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。 A．顺序存储线性表B．非顺序存储非线性表 C．顺序存储非线性表D．非顺序存储线性表 11．在单链表表示的线性表中，可以从( A )。 A．第一个结点访问到所有结点 B．某个结点访问到所有结点 C．某个结点访问到该结点的所有前趋结点 D．最后一个结点访问到所有结点 12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。 A．s->link=p->link; p->link=s; B．p->link=s->link; s->link=p; C．q->link=s; s->link=p; D．p->link=s; s->link=q; 13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素
数据结构复习题答案 2
一、填空。 1．顺序存储结构的特点是（静态存储的物理次序和逻辑次序一致），链式存储结构的特点式（动态存储的物理次序和逻辑次序不一定一致）。 2．算法在遇到非法操作时可以作出合理处理的特性为（健壮性）。 3．常见的算法时间复杂度用大O记号表示为：常数阶（ O(1) ），对数阶（ O(log2n ) ），线性阶（O(n) ），平方阶( O(n2) )和指数阶（ O(2n) ）。 4．在单链表中，除了头结点以外，任一结点的存储位置由（其直接前驱的指针域）指示。 5．当线性表采用顺序存储结构时，其主要特点是（静态存储物理次序和逻辑次序一致）。6．在双链表中，每个结点设置了两个指针域，其中一个指向（直接前驱）结点，另一个指向（直接后继）结点。 7．设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（ 2,3 ），栈顶指针是（ 1003 H ）。8．栈S通常采用的两种存储结构是（顺序存储和链序存储）；其判定栈空的条件分别是（ s->top==-1 top->next==NULL ）, 判定栈满的条件分别是（ s->top==stack_size-1 ）。 9．（栈）可作为实现递归函数调用的一种数据结构。 10．栈和队列是两种特殊的线性表，栈的操作特性是（先进后出），队列的操作特性是（先进先出），栈和队列的主要区别是（栈是在表的一端进行操作，队列是在表的两端进行操作）。 11．循环队列的引入是为了克服（假溢出）。 12．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为 ( (front-rear+n）mod n ）。 13．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（ O(1) ）和（ O(n) ）。 14．串是一种特殊的线性表，其特殊性体现在（串的数据限定为字符集）。 15．两个串相等的充分必要条件是（两个串的长度相等并且每个对应位置的字符都相等）。 16．（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。17．从逻辑关系上讲，数据结构主要分为（集合结构）、（线性结构）、（树形结构）、（图状结构或网状结构）。 18．数据的存储结构主要有（顺序）和（非顺序）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据的表示）和（关系的表示）。 19．算法具有5个特性，分别是（可行性，有限性，确定性，输入和输出） 20．顺序表中第一个元素的地址是100，每个元素的长度为2，则第五个元素的存储地址是（ 108 ）。 21．单链表中设置头指针的作用是（标识链表在内存中的位置）。 22、设单链表中指针P指向结点A，若要删除A的后继结点（假设A存在后继结点），则修改指针的操作为（ p->next=p->next->next; ）。 23．设S=”I AM A TEACHER”,其长度为（ 14 ）。 24．对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是（ O(1) ）。 25．数组通常有两种运算：（获得特定位置的元素值）和（修改特定元素的值），这决定了数组通常采用（顺序）结构来存储。
(完整版)数据结构课后习题及解析第二章
第二章习题 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
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )
数据结构课后习题及解析第二章
第二章习题 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。
地理信息系统空间数据结构
第二章地理信息系统空间数据结构 2.1 地理空间数据及其特征 【学时安排】 1 学时 【目的要求】 1、掌握地理信息系统的数据类型； 2、理解地理信息系统的数据来源； 3、掌握空间数据的特点。 【重点难点】 地理信息系统的数据类型与特征。 【教学方法与手段】 示例式教学方法，多媒体教学手段。 一、GIS空间数据的来源与类型 空间数据是GIS的核心，也有人称它是GIS的血液，因为GIS的操作对象是空间数据，因此设计和使用GIS 的第一步工作就是根据系统的功能，获取所需要的空间数据，并创建空间数据库。 1、地理数据的来源 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种来源： ⑴地图数据。来源于各种类型的普通地图和专题地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度，是地理信息的主要载体，同时也是地理信息系统最重要的信息源。 ⑵影像数据。主要来源于卫星遥感和航空遥感，包括多平台、多层面、多种传感器、多时相、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，也是GIS的最有效的数据源之一。 ⑶地形数据。来源于地形等高线图的数字化，已建立的数字高程模型( DEM和其他实 测的地形数据等。 ⑷属性数据。来源于各类调查报告、实测数据、文献资料、解译信息等。 ⑸元数据。来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、源数据比例尺、数据转换方法等。 2、空间数据的类型 空间数据根据表示对象的不同，又具体分为七种类型(图2-1) ，它们各表示的具体内容 如下： (1) 类型数据。例如考古地点、道路线、土壤类型的分布等。 (2) 面域数据。例如随机多边形的中心点，行政区域界线、行政单元等。 (3) 网络数据。例如道路交点、街道、街区等。 (4) 样本数据。例如气象站、航线、野外样方分布区等。 (5) 曲面数据。例如高程点、等高线、等值区域等。 (6) 文本数据。例如地名、河流名称、区域名称等。 (7) 符号数据。例如点状符号、线状符号、面状符号(晕线) 等。
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 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. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2. 算法就是程序。（） 3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 第二章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元 素个数与＿＿插入或删除的位置＿＿有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。 2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。
数据结构(第二版)课后习题答案(王红梅主编)
课后习题讲解 1. 填空 (1)()是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素 3()是数据的最小单位，()是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为( )、( )、( )和( )。【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有( )和( )两种基本方法，不论哪种存储结构，都要存储两方面的内容： ( ) 和( )。 解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的 关系
⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模 ⑻ 设待处理问题的规模为n若一个算法的时间复杂度为一个常数， 则表示成数量级的形式为（），若 为n*log25n，则表示成数量级的形式为（）。 【解答】0（1）, Ο（nlog2n） 【分析】用大0记号表示算法的时间复杂度，需要将低次幕去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关
系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数 组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个 结点，元素之间的逻辑关系由结点中 的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（） A 树 B 图 C 线性表 D 集合
【免费下载】数据结构习题及答案
第一章 1．在数据结构中，从逻辑上可以把数据结构分为（C ） A．动态结构和静态结构 B. 紧凑结构和非紧凑结构 C．线性结构和非线性结构 D. 内部结构和外部结构 ● 2.在数据结构中,与所使用的计算机无关的是( A ) A. 逻辑结构 B. 存储结构 C. 逻辑和存储结构 D. 物理结构 3.下面程序的时间复杂度为____O（mn）_______。 for (int i=1; i<=m; i++) for (int j=1; j<=n; j++ ) S+=i 第二章线性表 ●链表不具备的特点是（A） A 可以随机访问任一结点（顺序） B 插入删除不需要移动元素 C 不必事先估计空间 D 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件为（A ），带头结点的单链表head为空的判定条件为（B ） A head==null B head->next==null C head->next==head D head!=null ●3.在线性表的下列存储结构中，读取元素花费时间最少的是（D） A 单链表 B 双链表 C 循环链表 D 顺序表 ● 4.对于只在表的首、尾两端进行手稿操作的线性表，宜采用的存储结构为(C) A 顺序表 B 用头指针表示的单循环链表 C 用尾指针表示的单循环链表 D 单链表 ● 5.在一个具有n 个结点的有序单链表中插入一个新的结点，并保持链表元素仍然有序， 则操作的时间复杂度为( D ) A O(1) B O(log2n) C O(n2) D O(n) ● 6.在一个长度为n (n>1)的单链表上，设有头和尾两个指针，执行(B)操作与链表的长 度有关 A 删除单链表中第一个元素 B 删除单链表中最后一个元素 C 在第一个元素之前插入一个新元素 D 在最后一个元素之后插入一个新元素 ●7.与单链表相比，双向链表的优点之一是(D) A 插入删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 顺序访问相邻结点更容易 ●8.若list是某带头结点的循环链表的头结点指针，则该链表最后那个链结点的指针域 (头结点的地址)中存放的是( B ) A list的地址 B list的内容 C list指的链结点的值 D 链表第一个链结点的地址 ●9.若list1和list2分别为一个单链表与一个双向链表的第一个结点的指针，则( B ) A list2比list1占用更多的存储单元 B list1与list2占用相同的存储单元 C list1和list2应该是相同类型的指针变量 D 双向链表比单链表占用更多的存储单元 10.链表中的每个链结点占用的存储空间不必连续，这句话正确吗？ (不正确) 11. 某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。V 100+4*12=148 11.在顺序表的（最后一个结点之后）插入一个新的数据元素不必移动任何元素。 12.若对线性表进行的操作主要不是插入删除，则该线性表宜采用（顺序）存储结构，若频繁地对线性表进行插入和删除操作，则该线性表宜采用( 链 )存储结构。
经典数据结构上机题_答案解析
数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 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 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R 是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5.有n个球队参加的足球联赛按主客场制进行比赛，共需进行n(n-1)场比赛。参考答案： n(n-1) 6.一棵树的前根遍历序列为EFHIGJK，后根遍历序列为HFIEJKG，将树转换成二叉树形式后，该二叉树的后序遍历序列为HIFKJGE。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11.在一棵m阶B树上，每个内部结点的关键字数目最少为?m/2?-1个，最多为 m-1个，其子树数目最少为?m/2?，最多为m。 12. 后缀算式9 2 3 +- 10 2 / -的值为 -1； 中缀算式8-(3+5)*(5-6/2)对应的后缀算式为8 3 5 + 5 6 2 / - * -。 13. 在一段文字中，5个常用汉字及出现频度如下：于个和是有 18 17 14 10 1 2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i 2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队； 《数据结构》课程设计题目 (程序实现采用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; 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 2015.3 目录 第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (42) 第7章查找 (54) 第8章排序 (65) 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 1 填空题 （1）数据元素（2）数据项数据元素（3）集合线性结构树结构图结构（4）顺序存储链接存储数据元素数据元素之间的关系 （5）零或多个输入一个或多个输出有穷性确定性可行性 （6）自然语言程序设计语言流程图伪代码，伪代码 （7）问题规模（8）O(1) O(nlog2n) 2 选择题 （1）C D (2)B (3) B (4) A (5) D (6)A (7) C (8) C E 3 判断题 ×××√× 第二章 1 填空题 （1）表长一半表长位置 （2）108 （3）p->next=(p->next)->next; （4）运算方便 （5）p->next=head; （6）s->next=rear->next rear->next=s; rear=s; q=rear->next->next; rear->next->next=q->next; delete q; （7）O(1) O(n) （8）循环单链表循环双链表双链表 2 选择题 （1） A B （2） D （3） B （4） A （5） A （6） D （7） B （8） B （9） C （10）B （11）B （12）D （13）A （14）A 3 判断题××××× 1 填空题 （1）1003H （2）顺序栈和链栈top=-1或top==NULL top==数组长度或内存无可用空间（3）栈 （4）abc+*d- （5）后进先出先进先出操作位置受限 （6）假溢出 （7）（rear-front+n）% n （8）O(1) O(n) 2 选择题 （1） C （2） D （3） C （4） B （5） B （6） B （7） D （8） A （9） C 3 判断题×√√××第四章 1 填空题 （1）数据元素的类型是字符 （2）长度相等且对应位置字符相等（3）存取修改顺序存储（4）1140 （5）d+41 （6）三元组顺序表十字链表 2 选择题 （1） B （2） D E K （3） B （4） C （5） D （6） C （7） D 3 判断题×√√×× （按照自己的情况选作部分习题，不要抄袭） 第二章习题 顺序存储线性表 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。√ 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。√ 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。×6．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。√ 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( A ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。插入一个元素时平均要移动表中的（A）个元素。 (A) n/2 (B) n+1/2 (C) n -1/2 (D) n 三填空题 1．在顺序表中做插入操作时首先检查___表是否满了______________。 四算法设计题 1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性。并且分析算法的时间复杂度。2．已知一顺序表A，其元素值非递减有序排列，编写一个函数删除顺序表中多余的值相同的元素。 3．编写一个函数，从一给定的顺序表A中删除值在x~y(x<=y)之间的所有元素，要求以较高的效率来实现。 提示：可以先将顺序表中所有值在x~y之间的元素置成一个特殊的值，并不立即删除它们，然后从最后向前依次扫描，发现具有特殊值的元素后，移动其后面的元素将其删除掉。 4．线性表中有n个元素，每个元素是一个字符，现存于向量R[n]中，试写一算法，使R 中的字符按字母字符、数字字符和其它字符的顺序排列。要求利用原来的存储空间，元素移动次数最小。（研54） 5．线性表用顺序存储，设计一个算法，用尽可能少的辅助存储空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表 （a1, a2, … , a m, b1, b2, … , b n）改变为： （b1, b2, … , b n , a1, a2, … , a m）。 五上机实习题目 约瑟夫环问题 约瑟夫环问题：设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，计算机数据结构习题答案2
第二章数据结构习题作业
数据结构经典题目c语言代码
数据结构(C语言版)(第2版)课后习题答案
《数据结构》课后习题答案(第2版)
数据结构Java版第二章习题