下载文档原格式
第1章单元测试1、算法的时间复杂度取决于___。
答案：A和B2、数据在计算机内存中的表示是指（）答案：数据的存储结构3、算法指的是（）答案：求解特定问题的指令有限序列4、在数据结构中，与所使用的计算机无关的数据结构是（）答案：逻辑7、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。
答案：1448、算法能正确地实现预定功能的特性称为算法的（）。
答案：正确性第2章单元测试1、链表不具备的特点是（）。
答案：可随机访问任意一个结点3、线性表的顺序存储表示优于链式存储表示。
答案：错4、顺序存储结构的缺点是不便于修改,插入和删除需要移动很多结点。
答案：对5、在设头、尾指针的单链表中,与长度n有关的操作是( )。
答案：删除最后一个结点6、设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为( )。
答案：q->next=s; s->next=p;7、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。
答案：用尾指针表示的循环单链表8、在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行( )。
答案：s->link=p->link;p->link=s;9、在双向链表存储结构中，删除p所指的结点时须修改指针____。
答案：p->next->prior=p->prior; p->prior->next=p->next;10、若事先不知道线性表的长度,则处理线性表时较好的存储结构是( )。
答案：单链表11、向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动( )个元素。
答案：63.512、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。
c语⾔实现--带头结点单链表操作可能是顺序表研究的细致了⼀点，单链表操作⼀下⼦就实现了。
这⾥先实现带头结点的单链表操作。
⼤概有以下知识点.1;结点：结点就是单链表中研究的数据元素，结点中存储数据的部分称为数据域，存储直接后继地址的部分称为指针域。
2;结点⽰意图：3;头指针：头指针始终指向链表第⼀个元素，当有头结点时头结点就是链表第⼀个元素。
头指针具有标识左右，故头指针命名为链表的名字，这⾥为linklist。
头指针是⼀定存在的。
4;头结点：引⼊头结点的⽬的是，将链表⾸元结点的插⼊和删除操作与其他结点的插⼊和删除操作统⼀起来。
（即头指针地址不在发⽣变化）5;单链表结点结构体表⽰：1struct LNode2 {3int data; //姑且认为其数据为整型4struct LNode * next;5 };67 typedef struct LNode * linklist6;单链表的操作集合，头⽂件 defs.h1 #ifndef _DEFS_H_2#define _DEFS_H_34 #include<stdio.h>5 #include<stdlib.h>6 #include<malloc.h>78struct LNode //单链表结点的定义9 {10int data;11struct LNode * next;12 }13 typedef struct LNode * linklist1415//操作集合16void InitList(linklist *L); //申请头结点，头指针地址改变17void DestroyList(linklist *L); //须释放头结点，头指针地址改变18void ClearList(linklist L); //保留头结点，头指针地址不变19void ListEmpty(linklist L);20int ListLength(linklist L);21int GetElem(linklist L, int i, int *e);22int LocateElem(linklist L, int e);23int PriorElem(linklist L, int cur_e, int *pri_e);24int NextElem(linklist L, int cur_e, int *nex_e);25int ListInsert(linklist L, int i, int e); //插⼊不改变头指针的值26int ListDelete(linklist L, int i, int *e); //删除操作也不改变头指针的值27void TravelList(linklist L);28#endif7;InitList操作实现1 #include"defs.h"23void InitList(linklist *L) //接受头指针的地址值4 {5 *L = (linklist)malloc(sizeof(struct LNode)); //*L表⽰头指针67if (*L == NULL)8 {9 printf("分配结点失败。
数据结构相关题库及答案第三章栈和队列一、判断题：1、栈和队列都是限制存取点的线性结构(易)2、栈和队列是两种重要的线性结构。
(易)3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易)4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。
(易)答案：1-4 √√××二、选择题：1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。
A、 edcba B、 decbaC、 dceabD、 abcde2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为_C___。
A、 iB、 n=iC、 n-i+1D、不确定3、栈结构通常采用的两种存储结构是_A___。
A、顺序存储结构和链式存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存储结构和非线性存储结构4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。
A、top !=0B、top= =0C、top !=m0D、top= =m0-15、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。
A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-16、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。
(不带空的头结点) (易)A、HS—＞next=s;9B、s—＞next= HS—＞next; HS—＞next=s;C、s—＞next= HS; HS=s;D、s—＞next= HS; HS= HS—＞next8、从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行__ _B_。
(不带空的头结点) (中)A、x=HS; HS= HS—＞next;B、x=HS—＞data;C、HS= HS—＞next; x=HS—＞data;D、x=HS—＞data; HS= HS—＞next;9、一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是___C_ 。
数据结构复习题1一、选择题1. 以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是 ( ) A 、集合中任何两个结点之间都有逻辑关系但组织形式松散 B 、线性结构中结点按逻辑关系依次排列形成一条"锁链"C 、树形结构具有分支、层次特性，其形态有点像自然界中的树D 、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接2. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A 、顺序存储结构 B 、链式存储结构 C 、索引存储结构 D 、散列存储结构3. 在长度为n 的顺序表的第i (1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( ) A 、n-i+1 B 、n-i C 、i D 、i-14. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A 、顺序表B 、用头指针表示的单循环链表C 、用尾指针表示的单循环链表D 、单链表5. 一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是（ ）A 、e d c b aB 、d e c b aC 、d c e a bD 、a b c d e6. 已知图1如右所示，若从顶点A 出发按深度优先搜索进行遍历，则可能得到的顶点序列为（ ） A 、 A ，B ，E ，C ，D ，F B 、 A ，C ，F ，E ，B ，DC 、 A ，E ，B ，C ，F ，DD 、 A ，E ，D ，F ，C ，B7. n 个顶点的有向图中含有向边的数目最多为 ( )A 、n-1B 、nC 、n(n-1)/2D 、n(n-1) 8. 若一个栈的输入顺序是1，2，…，n ，输出序列的第一个元素是n ，则第i （1≤i ≤n ）个输出元素是（ ）A 、n-iB 、n-i-1C 、i+1D 、n -i+1 9. 已给图2，（ ）是该图的正确的拓扑排序序列A 、1，2，3，4，5B 、1，3，2，4，5C 、1，2，4，3，5D 、1，2，3，5，4 10. 为查找某一特定单词在文本中出现的位置，可应用的串运算是( )A 、插入B 、删除C 、串联接D 、子串定位二、填空题A BC D E F 图1 1 2 34 5 图21.存储结构是逻辑结构的__________实现。
《数据结构》课程教学大纲课程类别：专业基础课适用专业：计算机应用技术适用层次：高起专适用教育形式：成人教育考核形式：考试所属学院：计算机科学与技术学院先修课程：C语言程序设计一、课程简介《数据结构》课程是计算机专业的核心基础课程，是一门理论与实践相结合的课程，整个计算机专业教学体系中处于举足轻重的地位。
数据结构是程序设计（特别是非数值计算的程序设计）的基础，也是设计和实现编译程序、操作系统、数据库系统及其它系统程序和大型应用程序的重要基础。
基于该门课程的重要性，现在该课程已经是计算机相关专业研究生考试必考专业课之一，是反映学生数据抽象能力、编程能力的重要体现。
二、课程学习目标通过本课程的学习，使学生具备下列能力：1、能够理解常用数据结构和算法的基本思路、思考方法、使用场合以及算法设计中考虑的各种因素，能运用于非数值型计算问题的建模和算法设计；深入体会经典算法的思路和分析解决问题的方法，能运用于解决其他领域的相关问题。
2、能够针对基本数据结构和算法方面的特定问题进行分析或推导，分析相应的逻辑结构、选择合适的物理结构或给出问题的解；能对简单算法进行复杂度分析。
3、能针对特定问题需求和给定的数据结构进行算法设计。
三、与其他课程的关系数据结构是计算机及其相关专业的专业基础课，是《操作系统》、《数据库原理》等课程的先导课。
四、课程主要内容和基本要求第1单元数据结构及算法性能分析『知识点』本章作为本课程的绪论部分，主要介绍数据结构课程的研究内容，以及数据结构课程中用到的与课程内容相关的概念和基本术语。
另外，在本章还重点介绍了算法的概念、算法的特性以及算法设计的基本要求，分析算法的方法。
本章重点讲解数据结构的相关概念以及算法及其算法分析。
『基本要求』1、识记：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、数据类型、抽象数据类型等基本概念。
2、领会：顺序存储结构和链式存储结构。
3、简单应用：能够实现顺序存储结构和链式存储结构，并在简单问题中应用。
使用单链表的总结单链表是一种基本的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的引用。
以下是使用单链表的一些关键总结：1. 基本结构：-单链表的节点包含两个部分：数据域和指针域。
-数据域存储节点的值。
-指针域存储指向下一个节点的引用。
2. 头节点：-单链表的头节点是链表的入口，用于引导整个链表。
-头节点通常不包含有效数据，只是用于指向第一个包含数据的节点。
3. 插入操作：-在链表头部插入节点是一种常见的操作，称为头插法。
-在链表尾部插入节点也是一种常见的操作，称为尾插法。
-在链表中间插入节点需要调整前后节点的引用。
4. 删除操作：-删除链表中的节点需要调整前后节点的引用，确保链表的连续性。
-删除头节点和中间节点的操作方式不同。
5. 遍历操作：-遍历链表是查看链表中所有元素的常见方式。
-可以使用循环或递归进行链表的遍历操作。
6. 链表的优势：-相比于数组，链表的插入和删除操作更为高效，不需要移动大量元素。
-链表的大小可以动态变化，不需要预先分配空间。
7. 链表的劣势：-链表访问元素的时间复杂度为O(n)，而数组是O(1)。
-链表需要额外的内存空间存储指针。
8. 循环链表：-在单链表的基础上，尾节点的指针指向头节点，形成一个循环结构。
9. 双向链表：-每个节点包含两个指针，分别指向前一个节点和后一个节点，提供了双向遍历的能力。
10. 应用场景：-单链表常用于需要频繁插入和删除操作的场景，如LRU缓存算法、图的邻接表表示等。
总体而言，单链表是一种简单而灵活的数据结构，能够有效地应用于特定的问题领域，特别是在涉及频繁插入和删除操作时。
了解链表的基本特性和操作是编写高效代码的重要一环。
计算机专业基础综合数据结构（栈和队列）历年真题试卷汇编7(总分：74.00，做题时间：90分钟)一、单项选择题(总题数：19，分数：38.00)1.若循环队列使用C数组A[m]存放其数据元素，已知头指针front指向队首元素，尾指针rear指向队尾元素后的空单元，则当前队列中的元素个数为( )。
【华中科技大学2007一、3(2分)】A.(rear—front+m)％m √B.rear-front+1C.rear-frontD.rear-front-12.设顺序队列的容量为MaxSize，其头指针为front，尾指针为rear，空队列的条件为( )。
【电子科技大学2008一、4(2分)】A.front=rear √B.front=-MaxSizeC.front+1=rearD.rear=03.循环队列存储在数组A[0．m]中，则入队时的操作为( )。
【中山大学1999一、6(1分)】A.rear=rear+1B.rear=(rear-H)mod(m一1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1) √4.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少?( )【浙江大学1999四、1(4分)】A.1和5B.2和4 √C.4和2D.5和15.已知输入序列为abcd，经过输出受限的双向队列后能得到的输出序列有( )。
【西安交通大学1996三、3(3分)】A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对√双端队列的输出序列求解见四、36。
6.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是( )。
【西安电子科技大学1996一、5(2分)】【烟台大学2007一、5(2分)】A.1234B.4132C.4231 √D.42137.最大容量为n的循环队列，队尾指针是rear，队头是frunt，则队空的条件是( )。
数据结构链表的基本操作一、引言链表是计算机科学中的一种数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
链表可以用于实现栈、队列和其他数据结构。
本文将详细介绍链表的基本操作。
二、链表的基本概念1. 节点：链表中的每个元素称为节点，它包含两部分：数据和指向下一个节点的指针。
2. 头结点：链表中第一个节点称为头结点，它不包含实际数据，只有指向第一个真正节点的指针。
3. 尾节点：链表中最后一个节点称为尾节点，它的指针为空。
4. 空链表：不包含任何元素的链表称为空链表。
三、链表的基本操作1. 创建链表创建一个空链表很简单，只需要让头结点指针为空即可。
如果需要创建带有多个元素的非空链表，则需要依次创建每个节点，并将前一个节点的指针指向当前节点。
2. 插入元素在插入元素时，需要先找到要插入位置前面的那个节点。
然后新建一个要插入的节点，并将其指针指向原来位置上后面那个节点。
最后将前面那个节点的指针改为新建立的节点。
3. 删除元素在删除元素时，需要先找到要删除的那个节点。
然后将前一个节点的指针指向后一个节点，从而跳过要删除的那个节点。
最后释放要删除的节点。
4. 遍历链表遍历链表是指依次访问链表中每个元素。
可以使用循环结构来实现遍历操作。
从头结点开始，依次访问每个节点，并将其数据输出即可。
5. 查找元素查找元素时，需要从头结点开始依次遍历每个节点，直到找到目标元素或者遍历完整个链表为止。
6. 反转链表反转链表是指将原来的链表顺序倒置。
可以使用三个指针分别表示当前节点、前一个节点和后一个节点，依次修改它们之间的指针即可实现反转操作。
四、链表的应用举例1. 栈和队列：栈和队列都可以用链表来实现。
栈是一种先进后出（FILO）的数据结构，而队列是一种先进先出（FIFO）的数据结构。
2. 链式存储文件系统：文件系统中通常采用基于树或者基于哈希表的存储方式。
但是在某些情况下，也可以采用基于链式存储方式来实现文件系统。
.h#ifndef LIST_H_INCLUDED#define LIST_H_INCLUDED/*****本头文件均为带头结点的单链表，功能函数包括对单链表的单个结点的修改，删除等操作，包含对整个单链表整个操作单链表来实现栈，队列等数据结构*****/typedef int ElemType;typedef int Status;typedef struct LNode{ElemType data;struct LNode * next;}LNode, *LinkList;typedef struct LStack{LinkList top;}LStack, *PLStack;//单链表实现栈typedef struct LQueue{LinkList Front;LinkList rear;}LQueue, *PLQueue;//单链表实现队列//单链表操作Status InitList_L(LinkList &L);//构造一个空的单链表Status DestroyList_L(LinkList &L);//销毁单链表LStatus ClearList_L(LinkList &L);//将单链表置为空表int ListLength_L(LinkList L);//求单链表的长度LNode * Search_L(LinkList L, ElemType e);//查找链表L第一个数据域为e的元素，若不存在则返回NULLLNode * NextElem_L(LinkList p);//返回p结点的直接后结点的指针，若P结点是尾元素结点，则返回NULLLNode * MakeNode_L(ElemType e);//构造e结点，返回指向该结点的指针Status InsertAfter_L(LNode *p, LNode *q);//在p结点之后插入q结点Status DeleteAfter_L(LNode *p, ElemType &e);//删除结点P直接结点的后继结点，用e返回结点值，若p为空或指向尾结点则操作失败void ListTraverse_L(LinkList L);//遍历单链表//基于单链表的算法void Find_SortList_L(LinkList L);//链表中的元素排序，查找排序void maopao_SortList_L(LinkList L);//链表中的元素冒泡排序void Fast_SortList_L(LinkList L);//用快速排序对链表元素排序void InverseList(LinkList L);//单链表的重置。
void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc);//将升序的单链表La与Lb归并为新的单链表Lc//链栈Status InitList_Stack(LStack &S);//初始化一个链栈Status DestroyList_Stack(LStack &S);//销毁一个链栈Status StackEmpty_List(LStack &S);//链栈是否为空void ClearStack_List(LStack &S);//清空链栈Status PushStack_List(LStack &S, ElemType e);//往一个链栈中压入元素eStatus PopStack_List(LStack &S, ElemType &e);//链栈顶元素出栈到eStatus getTop_StackList(LStack &S, ElemType &e);//去链栈顶元素到e//队列Status InitList_Queue(LQueue &Q);//初始化一个循环链队void DestroyList_Queue(LQueue &Q);//销毁链队void ClearList_Queue(LQueue &Q);//清空链队Status QueueEmpty_List(LQueue &Q);//对链队判空int QueueLength_List(LQueue Q);//求链队的长度Status PushQueue_List(LQueue &Q, ElemType e);//将元素e入队Status PopQueue_List(LQueue &Q, ElemType &e);//队头元素出队#endif // LIST_H_INCLUDED.cpp#include"List.h"#include<iostream>#include<malloc.h>#define error 0#define ok 1using namespace std;Status InitList_L(LinkList &L)//初始化一个带头结点的链表{L=(LinkList)malloc(sizeof(LNode));if(NULL==L){cout<<"初始化失败！"<<endl;return error;}L->next=NULL;cout<<"初始化成功！"<<endl;return ok;}Status DestroyList_L(LinkList &L)//销毁链表{LinkList p=L, q;while(p){q=p;p=p->next;free(q);}cout<<"销毁链表！"<<endl;return ok;}Status ClearList_L(LinkList &L)//清空链表{LinkList p=L, q;while(p->next){q=p->next;p=p->next;free(q);}cout<<"清空链表！"<<endl;return ok;}int ListLength_L(LinkList L)//求表长度{LinkList p=L;int num=0;while(p->next){p=p->next;++num;}return num;}LNode *Search_L(LinkList L, ElemType e)//在表中查询是否存在元素e，并返回该元素结点{LinkList p=L->next;while(NULL!=p){if(p->data==e){cout<<"查询成功！"<<endl;return p;}elsep=p->next;}cout<<"不存在该元素！"<<endl;return NULL;}LNode *MakeNode_L(ElemType e)//构造值为e的结点，返回结点指针{LinkList p;p=(LinkList)malloc(sizeof(LNode));if(NULL==p){cout<<"创建结点失败！"<<endl;return NULL;}elsep->data=e;return p;}Status InsertAfter_L(LNode *p, LNode *q)//在p结点之后插入q结点{if(NULL==p||NULL==q)return error;q->next=p->next;p->next=q;cout<<"插入成功！"<<endl;return ok;}Status DeleteAfter_L(LNode *p, ElemType &e)//删除结点P直接结点的后继结点，用e返回结点值，若p为空或指向尾结点则操作失败{if(NULL==p){cout<<"删除结点失败！"<<endl;return error;}LinkList q;q=p->next;p->next=q->next;free(q);cout<<"删除成功！"<<endl;return ok;}void ListTraverse_L(LinkList L)//遍历单链表{LinkList p=L->next;while(p){cout<<p->data<<" ";p=p->next;}cout<<endl;}Status InitList_Stack(LStack &S)//初始化一个链栈{S.top=(LinkList)malloc(sizeof(LNode));if(NULL==S.top)return error;cout<<"Inite success!"<<endl;S.top->next=NULL;return ok;}Status DestroyList_Stack(LStack &S)//销毁一个链栈{LinkList p=S.top, q;while(p){q=p;p=q->next;free(q);}return ok;}Status StackEmpty_List(LStack &S)//链栈是否为空{if(NULL==S.top->next){cout<<"空栈！"<<endl;return ok;}elsereturn error;}void ClearStack_List(LStack &S)//清空链栈{LinkList p=S.top->next, q;while(p){q=p;p=p->next;free(q);}}Status PushStack_List(LStack &S, ElemType e)//往一个链栈中压入元素e {LinkList q;q=(LinkList)malloc(sizeof(LNode));q->data=e;q->next=S.top->next;S.top->next=q;cout<<"Push success!"<<endl;return ok;}Status PopStack_List(LStack &S, ElemType &e)//链栈顶元素出栈到e {LinkList q=S.top->next;if(NULL==q)return error;e=q->data;S.top->next=q->next;free(q);return ok;}Status getTop_StackList(LStack &S, ElemType &e)//去链栈顶元素到e {if(NULL==S.top->next)return error;e=S.top->next->data;return ok;}Status InitList_Queue(LQueue &Q)//初始化一个循环链队{Q.Front=(LinkList)malloc(sizeof(LNode));if(NULL==Q.Front)return error;Q.Front->next=NULL;Q.rear=Q.Front->next;cout<<"InitList Queue success!"<<endl;return ok;}void DestroyList_Queue(LQueue &Q)//销毁链队{LinkList p=Q.Front, q;while(p){q=p;p=p->next;free(q);}cout<<"DestroyList Queue success!"<<endl;}void ClearList_Queue(LQueue &Q)//清空链队{LinkList p=Q.Front->next, q;while(p){q=p;p=p->next;free(q);}cout<<"clear ListQueue success!"<<endl;}Status QueueEmpty_List(LQueue &Q)//对链队判空{if(Q.Front->next==Q.rear)return ok;elsereturn error;}int QueueLength_List(LQueue Q)//求链队的长度{int num=0;num=ListLength_L(Q.Front);return num;}Status PushQueue_List(LQueue &Q, ElemType e)//将元素e入队{LinkList q;q=(LinkList)malloc(sizeof(LNode));if(NULL==q)return error;q->data=e;q->next=NULL;if(Q.rear==NULL)Q.rear=Q.Front;Q.rear->next=q;Q.rear=q;return ok;}Status PopQueue_List(LQueue &Q, ElemType &e)//队头元素出队{if(QueueEmpty_List(Q))return error;LinkList q=Q.Front->next;e=q->data;Q.Front->next=q->next;free(q);return ok;}void maopao_SortList_L(LinkList L)//链表中的元素排序，冒泡排序{ElemType e;LinkList p=L->next, temp;while(p){temp=p->next;while(temp){if(p->data>temp->data)e=p->data, p->data=temp->data, temp->data=e;temp=temp->next;}}}void Find_SortList_L(LinkList L)//链表中的元素排序，查找排序{LinkList p=L->next, temp, q;ElemType e;while(p){temp=p;q=p->next;while(q){if(temp->data>q->data)temp=q;q=q->next;}if(temp!=p){e=p->data;p->data=temp->data;temp->data=e;}p=p->next;}}void InverseList(LinkList L)//单链表的重置。
