数据结构与算法（C语言） |
您所在的位置：网站首页 › c语言的题目与解析 › 数据结构与算法（C语言） |
数据结构与算法（C语言）
|
还在为代码无法正常运行而烦恼，关注罡罡同学不迷路，解决你的烦恼。如果你觉得，本文章对你有那么一丢丢的帮助，记得点赞关注转发，罡罡同学非常感谢哈！ 后续文章是关于数据结构一些基础实验，本人都已经成功运行，如果有问题，欢迎在评论区留言。您的支持是罡罡同学前进的最大动力！**我是罡罡同学，一位初入网安的小白。 ☜(ˆ▽ˆ) **（疯狂暗示 点赞 ！关注！转发 ！！！ 点赞 ！关注！转发 ！！！） 《数据结构》期末考试模拟试题答卷 专业:XXX 班级：XXX 学号：XXX 姓名：XXX 考试时间：120分钟 第1题 第2题 第3题 第4题 第5题 第6题 总分 评阅人 （题量有些多，干就完了。） 为方便大家刷题,题目后紧跟答案 码字辛苦！求点赞+关注！！一、名词解释1.算法：算法是对特定问题求解的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 2.模式匹配算法：给定主串S=“S1S2S3…Sn”和模式串T=“t1t2t3…tn”,在S中寻找T的过程称为模式匹配。如果匹配成功，返回T在S中的位置，如果匹配失败，返回0。 3.AOV网：在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网。 4.AOE网：在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，边上的权值表示活动的持续时间，称这样的有向图叫做边表示活动的网，简称AOE网。 5.内部排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中。 6.外部排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录在外存上。整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。 7.无向完全图：在无向图中，如果任意两个顶点之间都存在边，称该图为无向完全图。 8.有向完全图：有向图有n个顶点，则最多有n(n-1)条边，将具有n(n-1)条边的有向图称为有向完全图。 9.孩子兄弟表示法：将树转换为二叉树的存储结构，一个数据域，两个指针域，左指针指向第一个孩子节点，右指针指向下一个兄弟节点。10.抽象数据类型（ADT）：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。 11.数据结构：相互之间存在一种或多种特定关系的数据元素的集合。 12.堆：堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。 13.哈希表：根据设定的哈希函数H（Key）和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字地址作为记录在表中的存储位置，这一存储结构称为构造哈希表（散列表）。 14.数据的逻辑结构：对数据之间关系的描述，它与数据的存储结构无关，同一种逻辑结构可以有多种存储结构。 15.数据的物理结构：又称存储结构，是数据的逻辑结构在计算机中的表示。它包括数据元素的表示和关系的表示。 二、判断题1.不管一颗哈夫曼树有偶数或是奇数个叶子结点，其树中总结点的个数必为奇数。 T2.由二叉树的前序和后序遍历序列可以唯一的确定一颗二叉树逻辑结构。 F3.表达式a*(b+c)-d的后缀表达式是abc+*d-。T4.线性表的逻辑顺序与存储顺序总是一致的。F5.算法可以用不同的语言描述，如C、C++、Python等，因此算法实际上就是程序了。F6.算法的确定性是指算法只能有唯一的一条执行路径，即只要输入是相同的就只能得到相同的输出结果。T7.数据元素是数据的最小单位。F8. 三、简答题1、设有一个栈，元素入栈的次序为A，B，C，D，E，能否得到“E，C，A，B，D”的出栈序列，若能，写出操作序列；若不能，说明原因。不能。栈的特点是先进后出。按ABCDE入栈，E出栈后，下一个应为D，而不可能是C。 2、在长度为11的哈希表中填写关键字17，49，29，38，哈希函数为H（key）=key MOD 11，采用二次探测再散列。 3、数组A中，每个元素的长度为2个字节，行下标i的范围从1到8，列下标j的范围从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要多少个单元？存放一行一列数据需要多少单元？（字节可以简单理解为单元）存放该数组至少需要：8X10X2=160个单元（8+10-1）x2=34个单元 4.写出下图两种不同的广度优先遍历序列，从V1顶点出发。 5.已知一颗完全二叉树的结点总数为19，最后一层的结点数为多少，解释原因。在完全二叉树中，易知i层完全二叉树至多2i-1个结点。设该完全二叉树共h层，易知前h-1层中每一层结点都是满的，且24-1next=HS->next;HS->next=SC.S->next=HS;HS=SD.S->next=HS;HS=->next选C 12.循环队列的初始化、判空、判满条件是什么？如何求循环队列的实际长度？初始化：front=rear=0;判空：front=rear;判满：(rear+1)%maxsize=front;实际长度：(rear-front+maxsize)%maxsize;13.若一个栈的输入序列是1，2，3…n,输出序列的第一个元素是n，能否确定第k个输出元素是什么？若不能说明原因。可以确定。因为第一个输出序列为n，那么前n-1个元素都是依次进栈，那么第K个元素为n-k+1。14.用一条语句实现单链表中删除P所指结点的后继结点。P->next=p->next->next;15.for(i=0;inext=m->next; //头插法 m->next=p;//头插法 } } 2.折半查找算法 int search(table *ST)//折半查找 在动态数组上查找 { int low=0,high=ST->length-1,key,mid;//高、低位指针初始化 scanf("%d",&key);//待查找关键字 while(lowhigh时循环结束 { mid=(low+high)/2; if(key==ST->data[mid]) return mid+1;//输出的是该关键字是 else if(keydata[mid]) high=mid-1;//转换区域 else low=mid+1;//转换区域 } }3.设计算法判断双向循环链表L是否对称。 int duichen(node *head) { node *p;node *q; p=head->next; q=head->rior;//rior为前指针域 while(p!=q&&p->next!=q) { if(p->data==q->data) { p=p->next; q=q->next; } else return 0; } return 1; }4.采用顺序存储的字符串，设计算法实现从i位置开始删除连续的j个字符。 int sqstring_delete(sqstring* str1,sqstring* str2) { int i,j,k; str2->length=0; str2->data=(char*)malloc((str1->length-j+1)*sizeof(char)); if(istr1->length||i+j-1>str1->length||jdata[k]; for(k=i+j-1;klength;k++) str2->data[k-j]=str1->data[k]; str2->length=str1->length-j; return 1; }5.单链表的就地逆置 void nizhi(node* head) { node* p;node* q; p=head->next; head->next=NULL; while(p!=NULL) { q=p->next; p->next=head->next; head->next=p; p=q; } }6.简单选择排序 void SelectSort(sqlist *L) { int i,j,k,temp; for(i=1;ilength;i++) { k=i; for(j=1+i;jlength;i++) if(L->data[k]>L->data[j]) k=j; if(k!=j) { temp=L->data[i]; L->data[i]=L->data[k]; L->data[k]=temp; } } }7.在循环队列中插入一个元素x。 int forqueue_charu(forqueue* qu,int x) { if((qu->rear==qu->front&&qu->flag==1)||(qu->rear==qu->maxsize-1&&qu->front==-1)) return 0;//队列已满 qu->rear=(qu->rear+1)%qu->maxsize; qu->data[qu->rear]=x; qu->flag=1; return 1; }8.删除单链表中的一个元素并返回它。 int list_shanchu(node *head,int i,int *e) { int j; node *p=head; for(j=0;jnext; } node *q=p->next; *e=q->data; p->next=q->next; fre(q); return e; }
|
V1V2V3V4V6V5V7V1V3V2V4V6V5V7（本题答案不唯一）【本文地址】