西华大学《数据结构》中期试卷答案

《数据结构》期中考试题答案一、填空题（20分，每题2分）1.逻辑结构、存储结构2.便于插入和删除操作3.方便运算的实现4.算法执行过程中所需要的基本运算次数5.存储结构6.q.next=p.next ； p.next=q7．递归算法8.抽象类或接口二、选择题（30分，每题2分）AACBB BDDCB AACAC三、问答题（50分，每题10分）1.什么是栈和队列？两者有何异同？答：栈和队列都属于线性表结构，它们是两种特殊的线性表，栈的插入和删除操作都在线性表的一端进行，所以栈的特点是“后进先出”；而队列的插入和删除操作分别在线性表的两端进行，所以队列的特点是“先进先出”。

2.采用顺序存储结构的栈和队列，在进行插入、删除操作时需要移动数据元素吗？为什么？答：采用顺序存储结构的栈和队列，在进行插入、删除操作时不需要移动数据元素，因为栈和队列均不能进行中间插入、删除操作。

3.什么是队列的假溢出？为什么顺序存储结构队列会出现假溢出？怎样解决队列的假溢出问题？链式存储结构队列会出现假溢出吗？答：顺序队列，当入队的元素个数（包括已出队元素）超过数组容量时，队列尾下标越界，数据溢出。

此时，由于之前已有若干元素出队，数组前部已空出许多存储单元，所以，这种溢出并不是因存储空间不够而产生的，称之为假溢出。

顺序队列之所以会产生假溢出现象，是因为顺序队列的存储单元没有重复使用机制。

解决的办法是将顺序队列设计成循环结构。

链式存储结构队列不会出现假溢出。

因为每次元素入队，都要申请新结点，数据不会溢出。

4.答案：(1) (a2, a4, …, ) (2)将单链表中偶数结点位置的元素值写入顺序表list5.数据的存储结构有哪两种，各有什么特点？答：数据存储结构的基本形式有两种：顺序存储结构和链式存储结构。

顺序存储结构使用一组连续的内存单元依次存放数据元素，元素在内存中的物理存储次序与它们的逻辑次序相同。

链式存储结构使用若干地址分散的存储单元存储数据元素，逻辑上相邻的数据元素在物理位置上不一定相邻，数据元素间的关系需要采用附加信息特别指定。

数据构造习题集含答案目录目录 (1)选择题 (2)第一章绪论 (2)第二章线性表 (4)第三章栈和队列 (6)第四章串 (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图 (11)第八章查找 (13)第九章排序 (14)简答题 (19)第一章绪论 (19)第二章线性表 (24)第三章栈和队列 (26)第四章串 (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图 (36)第八章查找 (38)第九章排序 (39)编程题 (41)第一章绪论 (41)第二章线性表 (41)第三章栈和队列 (52)第四章串 (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图 (52)第八章查找 (52)第九章排序 (57)选择题第一章绪论1.数据构造这门学科是针对什么问题而产生的？〔A〕A、针对非数值计算的程序设计问题B、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2.数据构造这门学科的研究内容下面选项最准确的是〔D〕A、研究数据对象和数据之间的关系B、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3.某班级的学生成绩表中查得X三同学的各科成绩记录，其中数据构造考了90分，那么下面关于数据对象、数据元素、数据项描述正确的选项是〔C〕A、某班级的学生成绩表是数据元素，90分是数据项B、某班级的学生成绩表是数据对象，90分是数据元素C、某班级的学生成绩表是数据对象，90分是数据项D、某班级的学生成绩表是数据元素，90分是数据元素4.*数据构造是指〔A〕。

A、数据元素的组织形式B、数据类型C、数据存储构造D、数据定义5.数据在计算机存储器内表示时，物理地址与逻辑地址不一样，称之为〔C〕。

A、存储构造B、逻辑构造C、链式存储构造D、顺序存储构造6.算法分析的目的是〔C〕A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改良D、分析算法的易懂性和文档型性7.算法分析的主要方法〔A〕。

西华大学课程考试试题卷（A 卷）试卷编号：（2008至2009学年第2学期）课程名称：数据结构考试时间：110分钟课程代码：8401801试卷总分：100分考试形式：闭卷学生自带普通计算器:否一、单项选择题（本大题共20个小题，每小题2分，共40分）1.如果在数据结构中每个数据元素只可能有一个直接前驱，但可有多个直接后继，则该结构是（c ）A.栈 B.队列 C.树 D.图2.在数据结构中，从逻辑上可以把数据结构分成（b ）。

A．动态结构和静态结构Ｂ.线性结构和非线性结构C．紧凑结构和非紧凑结构Ｄ．内部结构和外部结构3.算法分析的两个主要方面是（a ）。

A.空间复杂性和时间复杂性 B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性4.在以下的叙述中，正确的是（c ）。

A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构5.非空的循环单链表head 的尾结点（由p 所指向）满足（c ）。

A.p->next==NULL B.p==NULL C.p->next==head D.p==head 6.栈和队列的共同点是（c ）。

A.都是先进先出 B.都是先进后出C.只允许在端点处插入和删除元素 D.没有共同点7.设若入栈序列的元素顺序为X，Y，Z，判断下列哪一个出栈序列是不可能的。

（c ）。

A．XYZ B.YZX C.ZXY D.ZYX 8.设数组Data[0..m-1]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为（b ）。

A.front=front+1 B.front=(front+1)%m C.rear=rear+1 D.rear=(rear+1)%m 9.深度为5的二叉树至多有（d ）个结点。

数据结试题及答案数据结构试题及答案1. 单项选择题(1) 在数据结构中，线性表的顺序存储结构通常使用（）。

A. 链表B. 栈C. 队列D. 数组答案：D(2) 下列关于二叉树的描述中，不正确的是（）。

A. 二叉树是有序树B. 二叉树的第i层至多有2^(i-1)个节点C. 任意非空二叉树的第i层至多有2^(i-1)个节点D. 任意非空二叉树的第i层至少有2^(i-1)个节点答案：D2. 多项选择题(1) 下列关于图的描述中，正确的是（）。

A. 图的边有方向B. 图的边没有方向C. 图的顶点之间可以有零条或多条边D. 图的顶点之间至多有一条边答案：B, C(2) 在排序算法中，时间复杂度为O(nlogn)的算法包括（）。

A. 快速排序B. 归并排序C. 冒泡排序D. 堆排序答案：A, B, D3. 简答题(1) 请简述栈和队列的区别。

答案：栈是一种后进先出（LIFO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。

(2) 什么是递归？请举例说明。

答案：递归是一种方法，它允许函数调用自身来解决问题。

例如，计算阶乘函数n!时，可以定义为n! = n * (n-1)!，当n=1时，1!=1。

4. 计算题(1) 给定一个链表，其节点定义如下：struct ListNode {int val;ListNode *next;};请写出一个函数，反转链表，并返回新的链表头节点。

答案：ListNode* reverseList(ListNode* head) {ListNode* prev = NULL;ListNode* curr = head;ListNode* next = NULL;while (curr != NULL) {next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}(2) 给定一个二叉树，请计算其深度。

试卷编号：数据结构期末试卷一、选择题（在每个小题四个备选答案中选出一个正确答案）（本大题共20小题，每小题1.5分，总计30分）1、数据的基本单位是（ B ）。

A.数组元素B.数据元素C.数据项D.数据对象1、性质相同的数据元素的集合是（D ）。

A.数组元素B.数据元素C.数据项D.数据对象2、下列选项中哪个不属于算法重要特性？（D ）A.有穷性和确定性B.可行性C.输入和输出D.可视化和模块化2、算法的效率一般是指（A ）。

A.算法的执行时间B.算法所需要存储空间C.算法的可读性D.算法处理的数据量3、如一个线性表中的数据元素是由若干个数据项组成，人们通常把这样的数据元素又称为（A）。

A.记录B.字段C.属性D.数据项集合3、在线性表的抽象数据类型定义中，下列哪个是其数据关系的描述？其中ai指数据元素，D指数据对象。

（ B ）A. R={<a i,a n> |a i,a n∈D,i=1,2…,n}B. R={<a i,a i+1> |a i,a n∈D,i=1,2…,n-1}C. R={<a i,a i+1> |a i,a n∈D,i=1,2…,n}D. R={<a i-1,a i> |a i,a n∈D,i=2,3…,n-1}4、与数组相比，用链表表示线性表的主要优点是( C )。

A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序相同4、与链表相比，采用数组表示性线表的主要优点是（ A ）。

A.便于随机存取B.花费的存储空间比顺序表少C.便于插入与删除D.数据元素的物理顺序与逻辑顺序不一定相同5、下列关于栈说法正确的是（A ）。

A. 栈是限定在表尾部进行插入和删除操作的线性表 B . 一般使用链作栈存储结构，不可使用数组 C. 栈是先进先出的一种结构 D. 栈有栈顶和栈底，可从栈顶或栈底开始取元素5、下列关于栈的说法正确的是（C）A.在顺序栈中，栈底指针是可随意移动的 B . 空栈时，栈顶和栈底指针只相差1 . C。

1、已知A、B、C、D、E、F六个点的权重分别为49、3、17、22 、5 、6，画出赫夫曼树设计出赫夫曼编码。

解：A=49 B=3 C=17 D=22 E=5 F=6画出赫夫曼树如下：赫夫曼编码//------无栈非递归遍历哈夫曼树，求哈夫曼编码HC = (HUffmanCode)malloc((n+1)*sizeof(char *)); // 分配求编码的工作空间p = m; // 赫夫曼树的接点复制给p ，保证从使HT[p]从尾部开始cdlen = 0; // cdlen的初值为0for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志HT[i].weight = 0; //权重赋值为0while (p)//p不为空{if (HT[p].weight==0){ // 向左HT[p].weight = 1;//将p点的权重赋值为1if (HT[p].lchild != 0) //p点的左孩子不为0{p = HT[p].lchild; //p赋值为p的左孩子cd[cdlen++] ='0'; //录入0}else if (HT[p].rchild == 0) //p的右儿子=0{HC[p] = (char *)malloc((cdlen+1) * sizeof(char)); // 登记叶子结点的字符的编码cd[cdlen] ='\0'; //编码结束符strcpy(HC[p], cd); // 复制编码(串)}}else if (HT[p].weight==1) // p点权重为1时，向右{HT[p].weight = 2;//将p点权重赋值为2if (HT[p].rchild != 0) //p点的右孩子不为0{p = HT[p].rchild; //p点赋值为p点的右儿子cd[cdlen++] ='1'; //录入1}}else{//HT[p].weight==2，退回HT[p].weight = 0;//p点权重赋值为0p = HT[p].parent;//退到父结点--cdlen; //编码长度减1}}} // HuffmanCoding3、先序后序非递归遍历二叉树的算法源代码：#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<queue>#include<stack>#include<iostream>using namespace std;typedef struct BiTNode{char data;BiTNode *lchild, *rchild;}BiTNode,*BiTree;void CreateBiTree(BiTree &T)//建树，按先序顺序输入节点{char ch;scanf("%c",&ch);if(ch==' '){T=NULL;return;}else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(1);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}void InOrderTraverse(BiTree T)//非递归中序遍历{stack<BiTree> Stack;if(!T){printf("空树！\n");return;}while(T || !Stack.empty()){while(T){Stack.push(T);T=T->lchild;}T=Stack.top();Stack.pop();printf("%c",T->data);T=T->rchild;}}void PreOrderTraverse(BiTree T)//非递归先序遍历{stack<BiTree> Stack;if(!T){printf("空树！\n");return;}while(T || !Stack.empty()){while(T){Stack.push(T);printf("%c",T->data);T=T->lchild;}T=Stack.top();Stack.pop();T=T->rchild;}}void PostOrderTraverse(BiTree T)//非递归后序遍历,用一个标记标记右子树是否访问过int flag[20];stack<BiTree> Stack;if(!T){printf("空树！\n");return;}while(T){Stack.push(T);flag[Stack.size()]=0;T=T->lchild;}while(!Stack.empty()){T=Stack.top();while(T->rchild && flag[Stack.size()]==0){flag[Stack.size()]=1;T=T->rchild;while(T){Stack.push(T);flag[Stack.size()]=0;T=T->lchild;}T=Stack.top();}printf("%c",T->data);Stack.pop();}}void main(){BiTree T;printf("请按先序输入创建二叉树：\n");CreateBiTree(T);printf("创建成功！\n");printf("先序非递归：");PreOrderTraverse(T);printf("\n");printf("中序非递归：");InOrderTraverse(T);printf("\n");printf("后序非递归：");PostOrderTraverse(T);printf("\n");}运行结果：注释：运行此程序创建二叉树必须按照先序输入才能成功创建二叉树的。

一、选择题（每小题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．1065．在线性表的下列运算中，不改变数据元素之间结构关系的运算是（D）。

A．插入 B．删除 C．排序 D．查找6．线性表采用链式存储时，其地址(D )。

A．必须是连续的 B．一定是不连续的C．部分地址必须连续 D．连续与否均可以7．线性表是(A )。

A．一个有限序列，可以为空 B．一个有限序列，不可以为空C．一个无限序列，可以为空 D．一个无限序列，不可以为空8．若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则可能出现的出栈序列为（B）。

A．3，2，6，1，4，5 B．3，4，2，1，6，5C．1，2，5，3，4，6 D．5，6，4，2，3，19. 若一个栈的输人序列是1，2，3，…，n，输出序列的第一个元素是n，则第k个输出元素是（C ）。

A．k B．n-k-1 C．n-k+1 D．不确定10.对于队列操作数据的原则是（ A ）。

A. 先进先出B. 后进先出C. 先进后出D. 不分顺序11. 栈和队列的共同点是（ C ）。

A. 都是先进先出B. 都是先进后出C. 只允许在端点处插入和删除元素D. 没有共同点12．在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ A ）。

A．front=front->next B．rear=rear->nextC．rear->next=front D．front->next＝rear13. 空串与空格串（ B ）。

《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。

数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。

2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。

3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。

在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。

顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。

在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。

4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。

给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。

5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

在p所指结点后插入s所指结点：4、1。

在p所指结点前插入s所指结点：7、11、8、4、1。

在表首插入s所指结点：5、12。

在表尾插入s所指结点：11、9、1、6。

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;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。

西华大学课程考试参考答案 （A卷）考试科目：数据结构 考试时间：110分钟 试卷总分100分一、选择题（在每个小题四个备选答案中选出一个正确答案）（本大题共20小题，每小题1.5分，总计30分）1 C2 B3 C4 D5 B6 D7 B8 C9 A 10 C 11 C 12 D 13 C 14 A 15 A 16 D 17 C 18 A 19 D 20 A二、填空题（本大题共10题，每空1分，总计10分）（1） ++a*b3*4-cd （2） HIDJKEBLFGCA （3） 69 （4） 5 （5） 深度优先 （6） 广度优先 （7）数字分析 （8）平方取中 （9） 5 （10） 13 三、算法（本大题共5小题，共60分）1 （10分）2 （15分）保证新生成的结点成为头结点的直接后继就行 static createlist2(&L){ L=(Linklist)malloc(sizeof(Lnode)) //生成一个新结点，且指针s 指向它L.next=NULL ； //由L 返回链的头结点，标识链sanf(“input data x “,&x); if (x!=0) {t=(Linklist)malloc(sizeof(Lnode)); // 建立新结点 t.data=x ; t.next=NULL; } //建立第一个数据结点 sanf(“input data x “,&x); //下面开始循环建立其它结点 while (x!=0) /此处假设读入数据为0时结束建立链表 { t=(Linklist)malloc(sizeof(Lnode)); // 建立新结点 t.data=x ; .t.next=L.next L.next=tsanf(“input data x “,&x); } } 3、（10分）011000 101000 100001 010010 000101 001010 4、 （10分）5、（1）MST树（5分）void DFS(Graph G,int V){Visited[V]=TRUE;VisitFunc(V);For(w=FirstAdjV ex(G,V);w>=0;w=NextAd jV ex(G,v,w))if(!Visited[w]) DFS(G,w);}遍历结果：0 1 2 3 5 4。

《数据结构》试卷答案及评分细则一、单项选择题（本题共10小题，每小题2分，共20分。

）1. C2. B3. C4. B5. B6. A7. A &D 9. C 10. A评分细则：每题正确得2分，错误不得分。

二、填空题（本题共10小题，每小题1分，共10分。

）1.集合线性结构树形结构图状结构（或网状结构）2.时间复杂度空间复杂度3.顺序4.物理上相邻指针5.23 100C6.两个串的值相等（或两个串的长度相等，且各个对应位置的字符都相等）7. 5&根结点左子树右子树9.广度优先遍历10.比较交换（移动）评分细则：每题正确得1分，错误不得分。

三、应用题（本题共4小题，每小题10分，共40分。

）1.解：设树T的总结点数为n,树T的分支数为B,度数为0, 1, 2, 3, 4 的结点个数分别为n0,nl,n2,n3,n4 ......................................... （1分）贝lj n=n0+nl+n2+n3+n4 （1）.............................. （2 分）B=0*n0+I*nl+2*n2+3*n3+4*n4 （2）.............................. （2 分）且n=B+l （3）.............................. （4 分）将（1）（2）（3）式联立，求得n0=8o .................................... （1分）评分细则：部分正确酌情给分。

评分细则：树的形状正确5分，后续遍历正确5分；树的形状正确，后序遍历后序遍历序列：FDBGHECA部分部分正确酌情给分。

0 1 2 3 4 5 6 7VI—V2V3 —AV4—►V5 —►V6 —►V7—►V8 —►2A357 A7 A6 A5A4A4A6A(1) 广度优先搜索序列:V1V2V3V4V5V6V7V8(2 ) 深度优先搜索序列:V1V2V4V8V5V3V6V7评分细则：邻接表中结点顺序可不与参考答案一致，搜索序列可不与参考答案一致，部分正确酌情给分。

数据结构期中试卷及答案解析考试说明考试说明：考察前五章小题，难度接近真题。

满分100分，共20道选择题，每题5分。

请在60分钟内完成。

C T(n)=n3+5000nD T(n)=2nlogn-1000n参考答案：C本题考察时间复杂度，多个项相加时，只保留最高阶项由于巴啦啦能量——“常<对<幂<指<阶”，因此T(n)=logn+5000n=O(n)T(n)=n2-8000n=O(n2)T(n)=n3+5000n=O(n3)T(n)=2nlogn-1000n=O(nlogn)所以O(n3)复杂度最大，选C。

3.下列叙述中正确的是（）①线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比②线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关③线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比A. 仅①B. 仅②C. 仅③D. ①②③参考答案：A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比。

线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关4.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。

A. 单链表B. 双向链表C. 单循环链表D. 顺序表参考答案：D注意到，题目要求存取第i个元素及其前驱和后继，ABC三个选项找到第i个元素的时间复杂度均为O(n)，而D选项对于这3个位置的存取的时间复杂度均为O(1)，故选D。

5.静态链表中next域表示的是（）A 下一个元素的地址B 下一个元素的值C 当前元素的值D 下一个元素在数组中的位置参考答案：D静态链表一般保存在数组中，它和链表最大的区别是静态链表占用一段固定的区间，所以next域只需要表示下一个元素在数组中的下标即可而不是表示下一个元素的地址，选D。

6.对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为A top->next=x;top=x;B top=x;top-next=x;C top=x;x->next=top;D x->next=top;top=x;参考答案：D本题考察链栈的操作x入栈之后x下一个元素为原来的top，所以先把x->next=top，然后更新top，栈顶元素指向x。

第一章概论一、选择题1、研究数据结构就是研究（ D ）。

A. 数据的逻辑结构B. 数据的存储结构C. 数据的逻辑结构和存储结构D. 数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A. 空间复杂度和时间复杂度B. 正确性和简单性C. 可读性和文档性D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A. 图B. 树C. 广义表D. 栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、（ B ）等5个特性。

A. 可执行性、可移植性和可扩充性B. 可执行性、有穷性和确定性C. 确定性、有穷性和稳定性D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C ）。

for(i=0;i<m;i++)for(j=0;j<n;j++)a[i][j]=i*j;A. O(m2)B. O(n2)C. O(m*n)D.O(m+n)6、算法是（ D ）。

A. 计算机程序B. 解决问题的计算方法C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8）,其时间复杂度表示（ C ）。

A. O(n)B. O(nlog2n)C. O(n2)D. O(log2n)8、下面程序段的时间复杂度为（ C ）。

i=1;while(i<=n)i=i*3;A. O(n)B. O(3n)C. O(log3n)D. O(n3)9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B. 关系C. 运算D. 算法10、下面程序段的时间复杂度是（A ）。

i=s=0;while(s<n){i++;s+=i;}A. O(n)B. O(n2)C. O(log2n)D. O(n3)11、抽象数据类型的三个组成部分分别为（ A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（）。

四川大学“精品课程”计算机科学与技术专业（本科）《数据结构与算法分析》课程考试说明与模拟试卷第一部分考试说明数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。

由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++开发工具（如：Visual C++或C++ Builder或Borland C++）。

下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。

第一章绪论重点掌握的内容：1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。

2. 集合结构、线性结构、树结构和图结构的特点。

3. 抽象数据类型的定义和表示方法。

4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。

5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。

6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。

7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。

8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。

对于本章的其余内容均作一般掌握。

第二章线性表重点掌握的内容：1. 线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。

2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。

3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。

4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。

数据结构试题及答案试题1.请说明数据结构的定义和作用。

2.请列举数据结构的分类，并简要描述每种分类的特点。

3.请解释什么是线性数据结构，并举例说明。

4.请解释什么是非线性数据结构，并举例说明。

5.请简述栈和队列的特点，并提供实际应用场景。

6.请说明二叉树的定义，并解释二叉树的遍历方式。

7.请解释什么是图数据结构，并提供图的应用场景。

8.请解释什么是散列表，并解释散列表的应用场景。

9.请说明堆数据结构的定义和特点。

10.请解释什么是哈希表，并提供哈希表的应用场景。

答案1.数据结构的定义和作用数据结构是一种组织和存储数据的方式，它定义了数据之间的关系和操作。

数据结构的作用是为了有效地管理和处理大量数据，并提高程序的执行效率和内存利用率。

2.数据结构的分类及特点–线性数据结构：线性数据结构是数据元素之间存在一对一的关系，数据元素之间只能以线性的方式连接。

例如：数组、链表、栈、队列等。

线性数据结构的特点是：数据元素之间具有顺序关系，可以实现快速的查找和插入，但插入和删除操作可能导致大量元素的移动。

–非线性数据结构：非线性数据结构是数据元素之间存在一对多或多对多的关系，数据元素之间可以以任意非线性连接方式组织。

例如：树、图等。

非线性数据结构的特点是：数据元素之间不存在固定的顺序关系，可以更灵活地表示数据之间的关系，但查找和插入的效率可能较低。

3.线性数据结构的例子线性数据结构的一个例子是数组。

数组是一种连续存储数据的结构，每个元素占据相同的大小。

数组的元素通过索引访问，索引从0开始。

例如，一个整型数组可以表示一组整数，可以通过索引快速访问和修改数组中的元素。

4.非线性数据结构的例子非线性数据结构的一个例子是树。

树是一种分层存储数据的结构，包含一个根节点和若干个子节点。

每个节点可以有多个子节点，但只能有一个父节点。

例如，二叉树是一种特殊的树，每个节点最多有两个子节点。

5.栈和队列的特点及应用场景–栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。

一、单选题（每题 2 分，共20分）1. 1.对一个算法的评价，不包括如下（B ）方面的内容。

A．健壮性和可读性B．并行性C．正确性D．时空复杂度2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行(A ).A. p—〉next=HL->next；HL->next=p；B. p—〉next=HL;HL=p；C。

p->next=HL；p=HL；D。

HL=p；p—>next=HL；3. 3.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D。

表中元素的个数不变4.4。

一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ C )A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5.AOV网是一种（D ）。

A．有向图B．无向图C．无向无环图D．有向无环图6.6。

采用开放定址法处理散列表的冲突时，其平均查找长度（B）。

A．低于链接法处理冲突B。

高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7。

若需要利用形参直接访问实参时，应将形参变量说明为（D )参数.A．值B．函数C．指针D．引用8.8。

在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的( A ）。

A．行号B．列号C．元素值D．非零元素个数9.9。

快速排序在最坏情况下的时间复杂度为（D ）。

A．O(log2n) B．O(nlog2n) C．0（n) D．0(n2）10.10。

从二叉搜索树中查找一个元素时，其时间复杂度大致为（C )。

A。

O（n） B. O(1） C. O（log2n) D. O（n2）二、运算题(每题 6 分，共24分)1. 1.数据结构是指数据及其相互之间的______________.当结点之间存在M对N（M：N)的联系时，称这种结构为_____________________。

数据结构参考答案数据结构是计算机科学中的一个重要概念，它用于组织和存储数据，以便于快速访问和操作。

在计算机科学的发展过程中，数据结构一直扮演着重要的角色，它不仅为算法的设计和优化提供了基础，还为各种应用程序的开发提供了支持。

一、数据结构的分类数据结构可以分为线性结构和非线性结构。

线性结构是指数据元素之间存在一对一的关系，如数组和链表；非线性结构是指数据元素之间存在一对多或多对多的关系，如树和图。

线性结构适合于顺序访问和搜索，而非线性结构适合于递归和分治等操作。

二、常见的数据结构1. 数组：数组是一种最简单的数据结构，它将相同类型的数据元素按照一定的顺序存储在连续的内存空间中。

数组的优点是可以通过下标快速访问元素，但是插入和删除操作比较慢。

2. 链表：链表是一种动态数据结构，它通过指针将数据元素按照一定的顺序连接起来。

链表的优点是插入和删除操作比较快，但是访问元素需要遍历链表。

3. 栈：栈是一种后进先出（LIFO）的数据结构，它只允许在栈顶进行插入和删除操作。

栈的应用场景包括函数调用、表达式求值和括号匹配等。

4. 队列：队列是一种先进先出（FIFO）的数据结构，它只允许在队尾插入元素，在队头删除元素。

队列的应用场景包括任务调度、消息传递和缓冲区管理等。

5. 树：树是一种非线性的数据结构，它由节点和边组成，每个节点可以有多个子节点。

树的应用场景包括文件系统、数据库索引和网络路由等。

6. 图：图是一种包含节点和边的数据结构，节点表示实体，边表示实体之间的关系。

图的应用场景包括社交网络、地图导航和网络拓扑等。

三、数据结构的应用数据结构在计算机科学中有着广泛的应用。

例如，在搜索引擎中，数据结构被用于构建倒排索引，以实现快速的关键词搜索。

在数据库系统中，数据结构被用于索引和排序，以提高查询和排序的效率。

在人工智能领域，数据结构被用于构建决策树和神经网络，以实现机器学习和深度学习。

此外，数据结构还被广泛应用于算法设计和优化。