2013吉林省数据结构考资料

10级软件工程专业《数据结构》试题B卷答案及评分细则一、选择题（每小题3分，共30分，选错不给分，选对给3分）1,C 2,A 3,D 4,C 5,B 6,C 7,B 8,B 9,A 10,A二、填空题（每空2分，共20分，填对给2分，填错不给分）1,2 4；2，SXSSXXSX3,-+A*BC/DE4,128 75,存储位置指针6，任意若干连续字符序列7，相同类型数据元素三、应用题1 解：其步骤为i1=index(S,S1,1)………………………………………………(2分)i2=index(S,S2,1)+3………………………………………………(2分)sub1=substr(S,i1,length(S)-i1+1) …………………………………(2分)sub2=substr(S,i2,length(S)-i2+1…………………………………………(2分) S3=concat(sub1, sub2) ………………………………………………(2分)2 解本题即为构造最小生成树，按照最小生成树的构造方法，构造如下：303解：其拓扑排序序列为152634；156234；152364；512634；516234；512364；5612344 解：按照题目要求构造的二叉树如下四、算法设计题由于队列是先进先出，而栈是先进后出，所以只有经过两个栈，即先在第一个栈里先进后出，再经过第二个栈后进先出来实现队列的先进先出。

因此用两个栈模拟一个队列运算就是用一个栈作为输入，而另一个栈作为输出。

当进队列时，总是将数据进入到作为输入的栈中。

在输出时，如果作为输出的栈已空，则从输入栈将已输入到输入栈的所有数据压入输出栈中，然后由输出栈输出数据；如果作为输出的栈不空，则就从输出栈输出数据。

显然，只有在输入、输出栈均为空时队列才为空。

…………………………（写出思想给5分）一个栈s1用来插入元素，另一个栈S2用来删除元素，删除元素时应将前一栈s1中的所有元素读出，然后进入到第二个栈s2中，算法描述如下：Void Enqueue(s1,x)……………………………………………(2分)stack s1;int x;{if(s1->top==0)Printf(“队列上溢“)；ElsePush(s1,x);}Void Dequeue(s1,s2,x) ……………………………………………(2分)Stack s1,s2;Int x;{ S->top=0; /将s2清空While (!empty(s1) /将s1的所有元素退栈后压入s2,此时栈s1为空 Push(s2,pop(s1));Pop(s2,x); /弹出栈s2的栈顶元素（对首元素）并赋给xWhile (!empty(s2) /将剩于元素重新压入栈s1恢复为原s1中的顺序 Push(s1,pop(s2));}Int Queue_empty(s1)……………………………………………(1分) Stack s1;{if empty(s1)Return(1);ElseReturn(0);}。

吉林省考研计算机科学与技术复习资料数据结构常考题解析数据结构是计算机科学与技术专业中的重要课程，也是吉林省考研计算机科学与技术专业考试中的常考内容。

良好的数据结构基础对于考生取得好成绩至关重要。

本文将针对吉林省考研计算机科学与技术专业考试的数据结构常考题进行解析，帮助考生更好地复习备考。

一、线性表线性表是最常用、最基本的一种数据结构，它包括线性表的定义、线性表的顺序存储结构、线性表的链式存储结构等内容。

经常考察的题目类型有：1. 线性表的顺序存储结构实现线性表的顺序存储结构通常使用数组来实现，通过数组元素之间的逻辑关系来表示线性关系。

考生需要了解线性表的顺序存储结构特点，并能够实现其基本操作，如插入、删除、查找等。

2. 线性表的链式存储结构实现线性表的链式存储结构通常使用链表来实现，通过指针来表示元素之间的逻辑关系。

考生需要理解链表的基本概念，并能够实现链表的插入、删除、查找等操作。

二、栈和队列栈和队列是线性表的特例，可以通过线性表的顺序存储结构或链式存储结构来实现。

常考题目有：1. 基本操作实现栈和队列的基本操作包括入栈、出栈、入队、出队等。

考生需要熟练掌握这些基本操作的实现方法，并能够分析其时间复杂度。

2. 栈的应用栈具有"先进后出"的特点，在实际应用中有很多场景，如函数调用、表达式求值等。

考生需要了解栈的应用场景，并能够解决相关的问题。

三、树和二叉树树是一种非线性的数据结构，它具有分层次、递归定义的特点。

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

考生需要掌握树和二叉树的基本概念及其存储结构，常考题目有：1. 二叉树的遍历二叉树的遍历方式包括前序遍历、中序遍历和后序遍历，考生需要掌握这三种遍历方式的递归和非递归实现方法，并能够分析其时间复杂度。

2. 二叉树的建立与转换常见问题有根据前序遍历和中序遍历构建二叉树、根据有序链表构造平衡二叉树等。

考生需要熟悉这些问题的解决方法，并能够应用到实际问题中。

吉林省考研计算机科学复习资料数据结构复习指南数据结构是计算机科学与技术专业的一门重要课程，也是吉林省考研计算机科学专业的必考科目之一。

在备考过程中，掌握好数据结构的知识点和考点是提高分数的关键。

本复习指南将为各位考生提供一份完整的数据结构复习资料，帮助大家系统地复习并应对考试。

一、线性表1. 顺序表顺序表是一种用一段地址连续的存储单元依次存储线性表中的各个元素的存储结构。

其插入、删除操作相对简单，但其长度固定，容易造成空间浪费。

2. 链表链表是一种通过指针将存储单元逻辑上链接在一起的存储结构。

链表插入、删除操作灵活，但查找元素需要遍历链表，时间复杂度较高。

3. 栈和队列栈是一种后进先出（LIFO）的数据结构，常用于实现函数调用的运行环境。

队列是一种先进先出（FIFO）的数据结构，常用于任务调度、缓冲区等场景。

二、树与二叉树1. 二叉树的性质二叉树是一种特殊的树结构，每个节点最多有两个子节点。

二叉树的性质包括深度、高度、满二叉树、完全二叉树等。

2. 二叉树的遍历二叉树的遍历分为前序遍历、中序遍历和后序遍历三种方式，通过递归或栈的方式进行遍历操作。

3. 二叉搜索树二叉搜索树是一种特殊的二叉树，节点的左子树小于等于节点，右子树大于等于节点。

二叉搜索树具有快速查找、插入和删除的特点。

三、图1. 图的基本概念图是由顶点和边组成的一种数据结构，用于表示各种复杂关系，如社交网络、路由器等。

图的表示方法包括邻接矩阵和邻接表。

2. 图的搜索算法图的搜索算法主要包括深度优先搜索（DFS）和广度优先搜索（BFS），用于寻找图中的路径、环和连通分量等。

3. 最短路径算法最短路径算法用于求解图中两个节点之间的最短路径，常用的算法包括迪杰斯特拉算法和弗洛伊德算法。

四、排序算法1. 冒泡排序冒泡排序是一种简单直观的排序算法，通过比较相邻元素并交换位置来实现排序。

2. 快速排序快速排序是一种高效的排序算法，采用分治的思想，在平均情况下具有较快的排序速度。

1、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。

算法应对异常情况（入栈满等）给出相应的信息。

设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，Wn。

问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。

设布尔函数Knap(S，n)表示背包问题的解，Wi(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。

请在下列算法的下划线处填空，使其正确求解背包问题。

Knap(S，n)若S=0则Knap←true否则若（S<0）或(S>0且n<1)则Knap←false否则若Knap(1) , _=true则print(W[n])；Knap ←true否则 Knap←Knap(2) _ , _设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。

假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。

例如：设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。

将n(n>1)个整数存放到一维数组R中。

设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0, x1, x2,…, xn-1），变换为(xp， xp＋1, … , xn-1 ,x0 , x1,…, xp-1)。

2、在有向图G中，如果r到G中的每个结点都有路径可达，则称结点r为G的根结点。

编写一个算法完成下列功能：（1）．建立有向图G的邻接表存储结构；（2）．判断有向图G是否有根，若有，则打印出所有根结点的值。

1、使用浏览器访问网站时，一般将该网站的URL直接输入到____。

A、状态栏中B、菜单栏中C、地址栏中D、常用工具栏中2、主机机箱上RESET按钮的作用是____A、关闭计算机的电源B、使计算机重新启动C、设置计算机的参数D、相当于鼠标的左键3、OSI（开放系统互联)参考模型的最低层是____。

A、传输层B、网络层C、物理层D、应用层4、我们说某计算机的内存是16MB，就是指它的容量为____字节。

A、16*1024*1024B、16*1000*1000C、16*1024D、16*10005、浏览网页过程中，当鼠标移动到已设置了超链接的区域时，鼠标指针形状一般变为____。

A、小手形状B、双向箭头C、禁止图案D、下拉箭头6、欲将一个可执行文件通过邮件发送给远方的朋友，可以将该文件放在邮件的____。

A、主题中B、正文中C、附件中D、收件人中7、计算机系统由哪几部分组成____。

A、主机和外部设备B、软件系统和硬件系统C、主机和软件系统D、操作系统和硬件系统8、com、cn，其中用户名是____。

A、JndhsgB、Fm365C、Fm9、利用计算机将文字、声音、图形、图像和视频等多种媒体有机结合起来进行处理的技术称为____。

A、数字技术B、多媒体技术C、网络技术D、通信技术10、因特网中某主机的二级域名为gov，表示该主机属于____A、赢利性的商业机构B、军事机构C、网络机构D、非军事性政府组织机构11、下列属于计算机输入设备的是____A、鼠标B、音箱C、显示器D、打印机12、san@qq、com D、lisi_1982@sohu、com13、计算机网络的一个突出优点是____。

A、资源共享B、运算速度快C、费用低廉D、数据传输速度快14、常用于收发电子邮件的客户端程序为____。

A、E-mailB、Outlook ExpressC、BBSD、Word15、人们常提到的IT指的是____。

A、计算机技术B、信息技术C、通信技术D、电子技术16、在利用FrontpPage编辑网页时，要想观看网页在浏览器中的情形，应使用FrontpPage2000 网页视图窗口中的____标签。

1、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。

（注：图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。

利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。

下面用0，1，2表示这三种状态。

前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。

对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。

{for(i=1;i<=n;i++)if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。

{printf(“%d”,v);if(i==start) printf(“\n”); else Print(i,start);break;}//if}//Printvoid dfs(int v){visited[v]=1;for(j=1;j<=n;j++ )if (g[v][j]!=0) //存在边(v,j)if (visited[j]!=1) {if (!visited[j]) dfs(j); }//ifelse {cycle=1; Print(j,j);}visited[v]=2;}//dfsvoid find_cycle() //判断是否有回路，有则输出邻接矩阵。

visited数组为全局变量。

{for (i=1;i<=n;i++) visited[i]=0;for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);}//find_cycle2、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。

绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

吉林省考研计算机复习资料数据结构常考算法总结数据结构是计算机考研中的重要部分，算法作为数据结构的核心内容，常常成为考试的重点。

在吉林省考研中，数据结构常考算法有很多，下面将对其中一些常考的算法进行总结。

一、排序算法1. 冒泡排序冒泡排序是一种简单的排序算法，通过不断比较相邻的元素并交换位置，将最大（或最小）的元素逐渐“冒泡”到最后（或最前）的位置。

代码示例：```void bubbleSort(int arr[], int n){for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}}```2. 快速排序快速排序是基于分治策略的排序算法，通过选择一个基准元素，将小于基准元素的放在左边，大于基准元素的放在右边，然后对左右两边的子数组进行递归排序。

代码示例：```int partition(int arr[], int low, int high){int pivot = arr[high];int i = (low - 1);for (int j = low; j <= high - 1; j++)if (arr[j] < pivot){i++;swap(&arr[i], &arr[j]);}}swap(&arr[i + 1], &arr[high]);return (i + 1);}void quickSort(int arr[], int low, int high) {if (low < high){int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}}二、查找算法1. 二分查找二分查找是一种高效的查找算法，它要求待查找的序列必须是有序的。

1、矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m+n），因此不能采用常规的二层循环的查找。

可以先从右上角（i=a,j=d）元素与x比较，只有三种情况：一是A[i,j]>x，这情况下向j 小的方向继续查找；二是A[i,j]<x，下步应向i大的方向查找；三是A[i,j]=x，查找成功。

否则，若下标已超出范围，则查找失败。

void search(datatype A[ ][ ], int a,b,c,d, datatype x)//n*m矩阵A,行下标从a到b,列下标从c到d,本算法查找x是否在矩阵A中.{i=a; j=d; flag=0; //flag是成功查到x的标志while(i<=b && j>=c)if(A[i][j]==x) {flag=1;break;}else if (A[i][j]>x) j--; else i++;if(flag) printf(“A[%d][%d]=%d”,i,j,x); //假定x为整型.else printf(“矩阵A中无%d 元素”，x)；}算法search结束。

[算法讨论]算法中查找x的路线从右上角开始，向下（当x>A[i,j]）或向左（当x<A[i,j]）。

向下最多是m，向左最多是n。

最佳情况是在右上角比较一次成功，最差是在左下角（A[b,c]），比较m+n次，故算法最差时间复杂度是O(m+n）。

2、给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。

20分void Hospital(AdjMatrix w,int n)//在以邻接带权矩阵表示的n个村庄中，求医院建在何处，使离医院最远的村庄到医院的路径最短。

2013年1月高等教育自学考试全国统一命题考试数据结构试题课程代码：02331考生答题注意事项：1.本卷所有试卷必须在答题卡上作答。

答在试卷和草稿纸上的无效。

2.第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。

3.第二部分为非选择题。

必须注明大、小题号，使用0.5毫米黑色字迹笔作答。

4.合理安排答题空间，超出答题区域无效。

选择题部分一、单项选择题（本大题共15小题，每小题2分，共30分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．数据的逻辑结构可以分为A．动态结构和静态结构 B.顺序结构和链式结构C．线性结构和非线性结构 D.简单结构和构造结构2．线性表是一个有限序列，组成线性表的基本单位是A．数据项 B.数据元素C．数据域 D.字符3．栈中有a、b和c三个元素，a是栈底元素，c是栈顶元素，元素d等待进栈，则不可．．能．的出栈序列是A．dcba B.cbdaC．cadb D.cdba4．稀疏矩阵的三元组表是A．顺序存储结构 B.链式存储结构C．索引存储结构 D.散列表存储结构5．已知广义表G，head(G)与tail(G)的深度均为6，则G的深度是A．5 B.6C．7 D.86．下列编码集合中，属于前缀编码的一组是A.{11,10,001,101,0001}B.{00,010,0110,1000}C.{11,01,001,0101,0001}D.{0,10,110,1011}7.如题7图所示二叉树的中序序列为A．ACDBB．DCBAC．CDBAD．ABCD题7图8．有向图中所有顶点入度之和与所有顶点出度之和的比是A．1/2 B.1C．2 D.49．含有n个顶点和e条边的有向图的邻接矩阵中，零元素的个数是A.eB.2eC.n2-2eD.n2-e10.n个顶点的无向连通图，其生成树的边数为A.n-lB.nC.n+lD.nlogn11．用自底向上的冒泡排序方法对序列(8,13,26,55,29,44)从大到小排序，第一趟排序需进行交换的次数为A．2 B.3C．4 D.512．对序列(8,13,26,55,29,44)从小到大进行基数排序，第一趟排序的结果是A.(13,44,55,26,8,29)B.(13,26,55,44,8,29)C.(8,13,26,29,44,55)D.(29,26,8,44,55,13)13．采用分块查找时，要求数据A．块内有序 B.分块有序C．分块无序 D.每块中数据个数必须相同14.下列关于散列函数的说法正确的是A．散列函数越复杂越好B.散列函数越简单越好C．用除余法构造的散列函数是最好的D.在冲突尽可能少的情况下，散列函数越简单越好15.下列关于m阶B树的叙述中，错误．．的是A．每个结点至多有m棵子树B.每个结点至多有m-1个关键字 C ．所有的叶结点均在同一层上 D.根结点至少有/2m ⎡⎤⎢⎥棵子树非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

1、计算机主机硬件结构主要包括三个组成部分，它们分别是____A、CPU、存储器、I/O设备B、CPU、运算器、控制器C、存储器、I/O设备、系统总线D、CPU、控制器、I/O设备2、Hacker是指那些私闯非公开的机构网络进行破坏的人，它的中文俗称是_____。

A、朋克B、海客C、网虫D、黑客3、无论目前浏览的网页在何处，只要按一下下列哪一个按钮即可回到主页____。

A、后退B、前进C、停止D、主页4、____都是计算机的外部设备。

A、打印机，鼠标和辅助存储器B、键盘，光盘和RAMC、ROM，硬盘和显示器D、主存储器，硬盘和显示器5、因特网采用的核心技术是____。

A、TCP/IP协议B、局域网技术C、远程通信技术D、光纤技术6、在Word的编辑状态，对当前文档中的文字进行“字数统计”操作，应当使用的菜单是____。

A、“编辑”菜单B、“文件”菜单C、“视图”菜单D、“工具”菜单7、当一个Word文档窗口被关闭，该文档将____。

A、保存在外存中B、保存在内存中C、保存在剪贴板中D、既保存在外存中，也保存在内存中8、要移动WINDOWS的窗口的位置，必须用鼠标拖动它的____A、边框B、状态栏C、标题栏D、对话框9、在使用Word编辑软件时，插入点位置是很重要的，因为文字的增删都将在此处进行。

请问插入点的形状是____。

A、手形B、箭头形C、闪烁的竖条形D、沙漏形10、假如你的用户名为a_jy，电子邮件服务商的主机名为11、下面的文件格式哪个不是图形图像的存储格式____。

A、.pdfB、.jpgC、.gifD、.bmp12、Modem实现了基于_____的计算机与基于模拟信号的电话系统之间的连接A、模拟信号B、电信号C、数字信号D、光信号13、在描述信息传输中bps表示的是____。

A、每秒传输的字节数B、每秒传输的指令数C、每秒传输的字数D、每秒传输的位数14、代表教育部门的网络名是____。

1、设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。

2、假设以I和O分别表示入栈和出栈操作。

栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（15分）（1）A和D是合法序列，B和C 是非法序列。

（2）设被判定的操作序列已存入一维数组A中。

int Judge(char A[])//判断字符数组A中的输入输出序列是否是合法序列。

如是，返回true，否则返回false。

{i=0; //i为下标。

j=k=0; //j和k分别为I和字母O的的个数。

while(A[i]!=‘\0’) //当未到字符数组尾就作。

{switch(A[i]){case‘I’: j++; break; //入栈次数增1。

case‘O’: k++; if(k>j){printf(“序列非法\n”)；exit(0);}}i++; //不论A[i]是‘I’或‘O’，指针i均后移。

}if(j!=k) {printf(“序列非法\n”)；return(false);}else {printf(“序列合法\n”)；return(true);}}//算法结束。

3、假设以I和O分别表示入栈和出栈操作。

栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。

若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

4、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。

二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。

吉林省专升本考试数据结构分章习题及参考答案———选择题（第一章）1、计算机算法必须具备（）这三个特性。

A、可执行性、可移植性、可扩充性B、可执行性、确定性、有穷性C、确定性、有穷性、稳定性D、易读性、稳定性、安全性2、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A、结构B、关系C、运算D、算法3、具有线性结构的数据结构是（）。

A、图B、树C、广义表D、栈4、设数据结构A=(D, R)，其中D={1, 2, 3, 4}，R={r}, r={<I, 2>, <2, 3>,<3,4>, <4,1>}，则数据结构A是( )。

A、线性结构B、树结构C、图D、集合5、数据结构是指()。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义6、给定有n个元素的向量，建立一个有序单链表的时间复杂度是( )。

A、O(1)）B、O(n)C、O(n2)D、O(n*log2n)7、下列程序段的时间复杂度为（）。

x=n;y=0;while(x>=(y+1)*(y+1))y=y+1;A、O(n)B、O(根号n)C、O(1)D、O(n2)8、计算机算法指的是（）.A、计算方法B、排序方法C、解决问题的步骤序列D、调度方法9、（）是具有相同特性数据元素的集合，是数据的子集。

A、数据符号B、数据对象C、数据D、数据结构10、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构11、算法分析的两个主要方面是：A、空间复杂性和时间复杂性B、正确性和简明性C、可读性和文档性D、数据复杂性和程序复杂性12、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A、存储结构B、逻辑结构C、顺序存储结构D、链式存储结构13、数据结构是一门研究非数值计算的程序设计问题中,数据元素的逻辑结构，数据信息在计算机中的()以及一组相关的运算等的课程。

2013统考408数据结构应用题一、问题描述1.1题目背景在2013年的统一考试408试卷中，数据结构应用题是其中一个考察学生对数据结构理解和运用能力的试题。

本文将详细介绍该应用题的背景、要求和解题思路。

1.2题目要求考题要求学生使用数据结构中的某一种具体表达方式，解决给定的问题。

具体的问题场景和输入要求将在后续的部分中进行阐述。

二、题目内容本题是关于某个名为“学生成绩管理”的系统的设计和实现。

该系统主要用于记录和管理学生的考试成绩信息，包括学生的基本信息、科目成绩和总成绩等。

2.1系统功能要求该系统的主要功能要求如下：1.输入学生的基本信息：包括学生姓名、学号、性别和年级等。

2.输入学生各科目的成绩：包括语文、数学、英语等科目。

3.计算学生的总成绩：根据各科目的权重计算出每个学生的总成绩。

4.查询学生的成绩：可以按照学号、姓名等条件查询学生的成绩信息。

5.统计分析学生成绩：根据学科成绩进行排名、计算平均分等统计分析操作。

2.2输入输出要求输入要求：1.学生基本信息的输入格式为：学号,姓名,性别,年级。

2.各科目成绩的输入格式为：学号,科目,成绩。

输出要求：1.查询学生的成绩信息，按照指定格式输出。

2.统计分析结果的输出格式为：排名,学号,姓名,总成绩。

2.3数据结构设计为了实现该系统的功能，我们需要设计和使用以下数据结构：1.学生信息表：使用一个表格来记录学生的基本信息，包括学号、姓名、性别和年级等。

2.学科成绩表：使用一个表格来记录学生各科目的成绩，包括学号、科目和成绩等。

3.成绩统计表：使用一个表格来记录学生的总成绩和排名等统计信息。

三、解题思路3.1输入数据的处理首先，我们需要按照指定的输入格式，读取学生基本信息和各科目成绩。

可以使用链表等数据结构来保存这些信息，方便后续的查询和统计操作。

3.2计算学生的总成绩和排名根据各科目成绩和权重，计算每个学生的总成绩，并按照总成绩进行排名。

可以使用排序算法，如冒泡排序或快速排序，来实现排名的计算。

E__Temp2_2013数据结构试题2013数据结构试卷一、选择题(每空题2分共30分)1．下列关于算法的说法，正确的是（）。

A．程序一定是算法。

B．算法的可行性是指指令不能有二义性。

C．算法可以没有输入但必须有1个以上的输出。

D．算法必须是用计算机语言描述的。

2．从一个具有n个结点的单链表中查找值为x结点，在查找成功情况下，需平均比较（）个结点。

A． n B． n/2 C． (n-1)/2 D． (n+1)/23．带头结点的单链表head为空的判定条件是( )。

A． head= =NULL B． head->next==NULLC． head->next= =head D． head!=NULL4. 循环队列存储在数组A[0..m]中，则入队时的操作为（）。

A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1)mod mD. rear=(rear+1)mod(m+1)5. 广义表L=((a,b,c))的长度和深度分别是（）。

A.1和1B.1和3C.1和2D.2和36．广义表运算式Tail(((a,b),(c,d)))的操作结果是（）。

A．（c,d） B．c,d C．((c,d)) D．（）7．表达式a*(b+c)-d的后缀表达式是（）。

A．abcd*+- B．abc+*d- C．abc*+d- D．-+*abcd8．设n阶方阵A是一对称矩阵，为节省存储空间，将其下三角（包括对角线）以行序为主序存储在一维数组B(1: n(n+1)/2)中，则对任一上三角元素aij(i<j,1≤i≤n,1≤j≤n)，其在一维数组b中的下标位置k是（）。

< p="">A．i(i-1)/2+j B．j(j-1)/2+i C．i(j-1)/2+1 D．j(i-1)/2+19．广义表((a))的表头是（）。

A．a B．(a) C．() D．((a))10.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。