当前位置：文档之家 › 数据结构副本 - 半期测试

数据结构副本 - 半期测试

  • 格式：doc
  • 大小：295.00 KB
  • 文档页数：51

有序顺序表的合并操作的实现941 #include #include using namespace std; typedef struct { int data[100]; int length; }sqlist; void crearelist(sqlist *&L,int a[],int n) { int i; L=(sqlist *)malloc(sizeof(sqlist)); for(i=0;iL->data[i]=a[i]; L->length=n; } void initlist(sqlist *&L) { L=(sqlist *)malloc(sizeof(sqlist)); L->length=0; } void displist(sqlist *L) { int i; for(i=0;ilength-1;i++) coutdata[i]>L->data[i+1]) {k=L->data[i];L->data[i]=L->data[i+1];L->data[i+1]=k;} } }

int main() { sqlist *L1,*L2,*L3; initlist(L1); initlist(L2); initlist(L3); int i,m,t,b[50],c[50],d[100]; cin>>m; for(i=0;icin>>b[i]; crearelist(L1,b,m); cin>>t; for(i=0;icin>>c[i]; crearelist(L2,c,t); for(i=0;id[i]=b[i]; for(i=0;id[m+i]=c[i]; crearelist(L3,d,m+t); paixu(L3); displist(L3); return 0; } 逆置顺序表942 #include #include using namespace std; typedef struct { char data[100]; int length; }sqlist; void crearelist(sqlist *&L,char a[],int n) { int i; L=(sqlist *)malloc(sizeof(sqlist)); for(i=0;iL->data[i]=a[i]; L->length=n; } void initlist(sqlist *&L) { L=(sqlist *)malloc(sizeof(sqlist)); L->length=0; } void displist(sqlist *L) { int i; for(i=L->length-1;i>0;i--) cout

int main() { sqlist *L1; initlist(L1); int i,m; char b[50]; cin>>m; for(i=0;icin>>b[i]; crearelist(L1,b,m); displist(L1); return 0; }

顺序表插入操作的实现943 #include #include using namespace std; typedef struct { int data[100]; int length; }sqlist; void crearelist(sqlist *&L,int a[],int n) { int i; L=(sqlist *)malloc(sizeof(sqlist)); for(i=0;iL->data[i]=a[i]; L->length=n; } void initlist(sqlist *&L) { L=(sqlist *)malloc(sizeof(sqlist)); L->length=0; } void displist(sqlist *L,int n,int k) { int i,flag=0; for(i=0;ilength;i++) { if(L->data[i]==n) { flag=flag+1; cout<} if(ilength-1) cout>m; for(i=0;icin>>b[i]; crearelist(L1,b,m); cin>>t; cin>>c; displist(L1,t,c); return 0; }

单链表的插入操作的实现952 #include using namespace std; #include typedef struct Node { int data; struct Node *next; } Node; void Create(Node *&L,int a[],int n) { Node *s,*r; int i; L=(Node *)malloc(sizeof(Node)); r=L; for(i=0;i{ s=(Node *)malloc(sizeof(Node)); s->data=a[i]; r->next=s; r=s; } r->next=NULL; } void print(Node *L) { Node *s; s=L->next; coutnext; while(s!=NULL) { cout<<" "next; } } void charu(Node *&L,int i,int e) { int j=0; Node *p,*s; p=L; while(jnext!=NULL) { j++; p=p->next; } s=(Node *)malloc(sizeof(Node)); s->data=e; s->next=p->next; p->next=s; } int main() { int i,e,n,m; int a[1000]; Node *head; cin>>n; for(i=0;i{ cin>>a[i]; } Create(head,a,n); cin>>m>>e; if(m>n||m<1) { cout<<"error!"; return 0; } charu(head,m,e); print(head); return 0; }

单链表的删除操作的实现953 #include #include #include using namespace std; typedef struct node { int data; node *next; }Node; void init(Node *&L) { L=(Node *)malloc(sizeof(Node)); L->next=NULL; } void create(Node *&L,int a[],int n) { int i; Node *p,*q; init(L); q=L; for(i=0;i{ p=(Node *)malloc(sizeof(Node)); p->data=a[i]; p->next=NULL; q->next=p; q=p;

合集下载

国开电大2023年春季期末考试《数据结构》试题(试卷代号1252)

国开电大2023年春季期末考试《数据结构》试题(试卷代号1252)

国家开放大学2023年春季学期期末统一考试数据结构(本)试题一、单项选择题(把合适的选项编号填写在括号内。

每小题3分,共45分)1.线性结构、树形结构、图形结构都是按数据的( )来分类的。

A.存储结构B.物理和存储结构C.物理结构D.逻辑结构2.在数据结构中,从逻辑上可以把数据结构分为( ).A.动态结构和静态结构B.紧凑结构和非紧凑结构C.内部结构和外部结构D.线性结构和非线性结构3.设有一个长度为n的顺序表,要删除第i个元素,则需移动元素的个数为( )。

A. iB. n-i-1C. n-iD. n-i+14.设有一个长度为10的顺序表,要在第3个元素之后插入一个元素,则需移动元素的个数为( ).A.3B.6C. 7D.85.一个队列的人队序列是10,20 ,30,40。

则队列的输出序列是( ).A.40,30,20,10B.10,20,30,40C.10.40,30,20D.30 ,20,40,106.在一棵二叉树中(其根结点编号为1),若编号为8的结点存在右孩子,则该右孩子的顺序编号为( )。

A.18B.16C.15D.177.队列的出队操作在( )进行。

A.队头B.队尾C.任意位置D.指定位置8.串函数index(a ,b)的功能是进行( )。

A.求子串B.串连接C.模式匹配D.求串长9.一个非空广义表的表头元素( )。

A.不可能是原子B.只能是子表C.只能是原子D.可以是子表或原子10.链表所具备的特点之一是( )。

A.可以随机访问任一结点B.需要占用连续的存储空间.C.插人元素的操作不需要移动元索D.删除元素的操作需要移动元素11.树中所有结点数等于所有结点的度加( )。

A.1B.0C. 2D. -112.在一个无向图G中,所有边数之和等于的所有顶点的度数之和( )倍。

A.1/2B. 1C.2D.413.对于一个具有4个顶点和5条边的无向图,若采用邻接表表示,则所有顶点邻接表中的结点总数为( )。

《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。

2. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

数据结构期中考试试题及答案

数据结构期中考试试题及答案

2014-2015学年第二学期《数据结构与算法》期中考试学号：姓名：一、写语句1.设单链表结点指针域为next，试写出删除链表中指针p所指结点的直接后继的C语言语句。

2.设单链表中某指针p所指结点（即p结点）的数据域为data，链指针域为next，请写出在p结点之前插入s结点的操作3. 设双向循环链表中结点的数据域、前驱和后继指针域分别为data,pre和next,试写出在指针p 所指结点之前插入s结点的C语言描述语句。

4. 一线性表存储在带头结点的双向循环链表中，L为头指针。

如下算法：（1）说明该算法的功能。

（2）在空缺处填写相应的语句。

void unknown (BNODETP *L){ …p=L->next; q=p->next; r=q->next；while (q!=L){ while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；(1) ______；q->next=p->next；q->prior=p；(2) ______；(3) ______；q=r；p=q->prior；(4) ______；} }二、写算法1．设有一个正整数序列组成的有序单链表（按递增次序有序，且允许有相等的整数存在），试编写能实现下列功能的算法：（要求用最少的时间和最小的空间）(1)确定在序列中比正整数x大的数有几个（相同的数只计算一次，如序列{20,20,17,16,15,15,11,10,8,7,7,5,4}中比10大的数有5个）；(2) 在单链表将比正整数x小的数按递减次序排列；(3) 将正整数（比）x大的偶数从单链表中删除。

2. 设键盘输入n个英语单词，输入格式为n, w1, w2, …,wn,其中n表示随后输入英语单词个数，试编一程序，建立一个单向链表，实现：（1）如果单词重复出现，则只在链表上保留一个。

数据结构期中试卷A参考答案

数据结构期中试卷A参考答案

北京航空航天大学北海学院课程考试试卷答案要点及评分细则课程名称：《数据结构》考试班级：软件与信息工程学院卷别：_A 命题教师签名： 年 月 日1、 单项选择题（本题共15小题，每小题2分，共30分）123456789101112131415C AD B C B D D C A D C A C B2、 判断正误题(本题共10小题，每小题1分，共10分)1.X,2.X,3.√,4.√,5.X,6.X,7.X,8.√,9.X, 10.√3、 填空题(本题共6小题10个空，每空2分，共20分)(1) O(n)(2) O(n)(3) O(1)(4) 求模式串在主串中首次出现的位置的运算，即求主串中左起第一个与模 式串相等的子串的首字符在主串中的位置。

(5) (Q.rear-Q.front+Max)% Max(6) 4(7) n2log n，n3, 2n(8) n→∞时n3/(n2log n)→∞， 2n/(n3)→∞(9) 为空(10) 出队四、简答题：(本题共4小题，1，2小题各4分，3，4小题各6分，共20分)1.1) 确定性指描述无二义性，相同条件下执行的路线和结果都是唯一的。

2) 输入可以有0至多个从算法外部接受的输入。

2. 该缓冲区应该采用队列结构。

其主要特点是先进先出。

3. 顺序表：O(n)，单循环链表：O(n)，顺序栈：O(1)，循环队列：O(1)，链栈：O(1)，链队列：O(1)。

4. 优点：①随机访问，简捷；②只存数据，局部空间利用率高；缺点：①逻辑关系靠地址表达，插入删除造成大量元素移动；②要求连续存储空间，固定长度，不便扩充；③须预先按最大可能分配，但闲置多,按整体看空间利用率低。

五、设计题(本题共3小题，第1小题2分，第2小题8分，第3小题10分，共20 分)1. typedef struct node{datatype data;struct node *next;}node;2.(1). s->next = head->next; head->next = s;(2). s->next = head; head = s;3. 答案1：采用尾指针表示、带头结点的单循环链表。