2010级数据结构实验题目分享

1、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定2、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的3、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ D ）存储方式最节省时间。

A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表4、以下属于顺序存储结构优点的是（ A ）。

A) 存储密度大B) 插入运算方便C）删除运算方便D）可方便地用于各种逻辑结构的存储表示5、（ C ）在进行插入操作时，常产生假溢出现象。

A）顺序栈 B）循环队列C）顺序队列 D）链队列6、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。

A) 单链表 B) 仅有头指针的单循环链表C) 双链表 D) 仅有尾指针的单循环链表7、设一数列的顺序为1，2，3，4，5，6，通过栈结构不可能排成的顺序数列为（ B ）。

A）3，2，5，6，4，1 B）1，5，4，6，2，3C）2，4，3，5，1，6 D）4，5，3，6，2，18、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;9、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的10、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。

通过上机实验加深对课程内容的理解，增加感性认识，提高算法设计、程序编写及调试的能力。

要求所编的程序能正确运行（最好用C++调试），并提交实验报告。

实验题目先由理论课程的教师给学生，实验前学生必须做好准备，实验报告理论教师可以相当于作业登记。

上实验课程的教师督促、监控学生是否自己调试程序，相关情况作为成绩评定的依据。

实习报告规范：实习报告开头有题目，班级，姓名，学号和完成日期，并包括以下七个内容：1. 需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？明确规定：输入的形式和输入值的范围；输出的形式；程序所能达到的功能；测试数据；2. 概要设计：说明本程序中用到的所有抽象数据类型的定义，主程序的流程以及各程序模块之间的层次关系。

3. 详细设计：对每个操作写出伪码算法；对主程序和其他模块也需要写出伪码算法；画出函数的调用关系图。

提交带注释的源程序或者用伪代码写出每个操作所涉及的算法。

4. 调试分析：调试过程中遇到的问题；算法的时空分析和改进思想；经验和体会。

5. 用户使用说明：说明如何使用你编写的程序，详细列出每一步的操作步骤。

6. 测试结果：列出你的测试的结果，包括输入和输出。

7. 附录：带注释的源程序。

《数据结构》实验题目实验一栈的实现及应用一、实验目的及要求：1、熟悉栈的定义和栈的基本操作。

2、掌握顺序存储栈和链式存储栈的基本操作的具体实现。

3、加深对栈结构的理解，并逐步培养解决实际问题的编程能力二、实验内容说明：以下题目选择其一编程实现，在报告中说明栈实现的方式1．数制转换将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题，用"除B取余法"来解决。

【例】将十进制数13转化为二进制数。

解答：按除2取余法，得到的余数依次是1、0、1、1，则十进制数转化为二进制数为1101。

2．表达式求值（后缀表达式）当用户输入一个合法的后缀表达式后，能够返回正确的结果。

《数据结构》程序设计实习题目1.分别以顺序表和单链表作为存储结构，实现将线性表就地逆置的操作。

（所谓“就地逆置”是指辅助空间为O（1），即利用原表中的结点空间）。

2.写一程序将单链表中值重复的结点删除，使得表中各结点值均不相同。

3.已知一单链表中含有两类字符的数据元素（如：字母、数字），试编写程序将该单链表分成两个单链表，使得每个链表中只含有同一类的字符。

4.假设有两个按元素值递增有序的单链表A和B，试编写程序将A和B归并成一个按元素值递减有序的单链表。

5.利用线性结构（顺序表或链表）实现两个20位大整数的加法运算。

6.已知两个以顺序结构存储的线性表A和B，试编写程序实现从A表中删除包含在B表中的元素。

7.已知两个单链表A和B，试编写程序实现从A表中删除包含在B表中的元素。

8.已知两个以顺序结构存储的线性表A和B，试编写程序实现：将在B表中但不在A表中的元素插入到A表。

9.已知两个单链表A和B，试编写程序实现：将在B表中但不在A表中的元素插入到A表。

10.试编写程序，对任意输入的一个算术表达式，将式中的数字和运算符分成两类（一类是数字，一类是运算符），并按逆序输出。

（提示：利用栈来实现）11.利用栈结构，编写一个程序，对以逆波兰式表示的表达式求值。

12.编写程序，求得所有包含在串S中而不包含在串T中的字符（S中重复的字符只选一个）构成的新串R。

13.编写程序，求任意输入的串S中所含不同字符的总数和每种字符的个数。

14.一个文本串可用事先给定的字母映射表进行加密。

例如：设字母映射表为：a b c d e f g h i j k l m n o p q r s t u v w x y zn g z q t c o b m u h e l k p d a w x f y i v r s j则字符串“encrypt”被加密为“tkzwsdf”。

试写一程序将输入的文本串进行加密后输出。

15.假设两个10×10的稀疏矩阵A和B以三元组表的方式存储，试编写程序实现矩阵的相加运算，其结果存放在三元组表C中。

第 1 题：报数问题(时间限制为：5000毫秒)5输入：标准输入输出：标准输出描述：n个人围成一个圈，每个人分别标注为1、2、...、n，要求从1号从1开始报数，报到k的人出圈，接着下一个人又从1开始报数，如此循环，直到只剩最后一个人时，该人即为胜利者。

例如当n=10,k=4时，依次出列的人分别为4、8、2、7、3、10，9、1、6、5，则5号位置的人为胜利者。

给定n个人，请你编程计算出最后胜利者标号数。

输入：输入包含若干个用例，每个用例为接受键盘输入的两个数n(1<=n<=1000000), k(1<=k<=50)，分别表示总人数及报到出圈数。

输入为“0 0“表示输入用例结束。

输出：每个用例用一行输出最后胜利者的标号数。

输入样例1：1 110 40 0输出样例1：15第2题：成绩统计(顺序线性表)(时间限制为：1000毫秒)描述：根据输入统计学生的平均分及各科平均分。

输入：第一行为学生的个数n及课程数m，第二行至m+1行为课程名，接下来为各学生的姓名及成绩，每个学生的信息占两行，第一行为学生的姓名，第二行为m个实数，表示学生各科成绩。

输出：输出包含2n+2m行，前2n行为学生的平均分，其中第一行为学生姓名，第二行为该生的平均分，后2m行为各课程的平均分，其中第一行为课程名，第二行为对应的平均分。

(保留两位小数)样例输入：3 2englishcomputerzhangshan87.5 98lisi80 78wangwu60 59样例输出：zhangshan92.75lisi79.00wangwu59.50english75.83computer78.33第3题：合并线性表(时间限制为：500毫秒)描述：已知两非递减的顺序线性表，要求合并成一个新的非递减顺序线性表。

输入：输入包含四行，第一行为自然数n，表示第一个非递减顺序线性表的长度，第二行为n个自然数构成的非递减顺序线性表，第三行为自然数m，表示第二个非递减顺序线性表的长度，第四行为m个自然数构成的非递减顺序线性表。

当涉及数据结构的上机实验题时，通常会涉及编程和算法的实践。

以下是一些可能的
上机实验题目：
1. 实现一个栈（Stack）数据结构，并编写基本的操作（入栈、出栈、获取栈顶元素等）。

2. 实现一个队列（Queue）数据结构，并编写基本的操作（入队、出队等）。

3. 实现一个链表（Linked List）数据结构，并编写插入、删除、查找等操作。

4. 实现一个二叉树（Binary Tree）数据结构，并编写遍历算法（前序、中序、后序遍历）。

5. 实现一个图（Graph）数据结构，并编写基本的图算法（深度优先搜索、广度优先搜索）。

6. 实现一个哈希表（Hash Table）数据结构，并编写插入、删除、查找等操作。

这些实验题目可以帮助学生加深对数据结构的理解，并通过编程实践来掌握数据结构
的基本操作和算法。

同时，这些实验也有助于提高学生的编程能力和解决问题的能力。

10级数据结构实验题目一、实验题目1、设有两个无头结点的单链表，头指针分别为ha，hb，链中有数据域data，链域next，两链表的数据都按递增序存放，现要求将hb表归到ha表中，且归并后ha仍递增序，归并中ha表中已有的数据若hb中也有，则hb中的数据不归并到ha中，hb的链表在算法中不允许破坏。

2、结合书上第41页的例子（一元多项式相加），采用链式存储结构，将两个线性链表表示的一元多项式相加，并输出。

3、二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。

其中指针lchild和rchild的类型为bitre。

静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。

所不同的是，lchild和rdhild 为integer型，分别用于存储左右孩子的下标，如果没有左右孩子，则相应的值为0。

例如，二叉树的静态二叉链表如上图所示。

编写算法由二叉树的动态二叉链表构造出相应的静态二叉链表a[1..n]，并写出其调用形式和有关的类型描述。

其中n为一个确定的整数。

4、设无向图G有n个点e条边，编写算法建立G的邻接表，并按照深度优先搜索输出顶点，要求该算法时间复杂性为O（n+e），且除邻接多表本身所占空间之外只用O（1）辅助空间。

5、二叉排序树采用二叉链表存储。

写一个算法，删除结点值是X的结点。

要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。

4 #include "stdafx.h"#include<stdio.h>#include<stdlib.h>#define MAX_VERTEX_NUM 10typedef int ARC_INFO_TYPE; //弧相关信息类型typedef char VERTEX_TYPE; //结点信息类型typedef enum{UDG, DG}GRAPH_TYPE; //图的类型:无向，有向图 //弧结点（表结点）typedef struct ArcNode{int num; //结点编号ARC_INFO_TYPE* info;//弧的其他相关信息，如权值等等struct ArcNode* nextArcNode;//指向下一个表结点的指针}ArcNode;//顶点（头节点）typedef struct VNode{VERTEX_TYPE data;//顶点的数据ArcNode* firstArcNode;//指向第一个弧结点的指针}VNode, AdjList[MAX_VERTEX_NUM];//邻接表//整个图的信息typedef struct ALGraph{int vertexNum;//结点个数int arcNum;//边或者弧个数GRAPH_TYPE kind;}ALGraph;//定义全局变量，便于操作ALGraph Graph;AdjList adjList;//辅助数组，记录每个顶点是否被访问过int visited[MAX_VERTEX_NUM];//创建一个图int CreateALGraph(void){int i;int v1,v2;//暂时存放两个相关联点的编号ArcNode* p=NULL;printf("输入结点个数，边数，图类型：\n");scanf("%d,%d,%d",&Graph.vertexNum,&Graph.arcNum,&Graph.kind); fflush(stdin); //注意:清除缓冲区的残余输入流，这里清除回车后留下的'\r' and'\n'之一，否则下面的输入出错printf("输入顶点的数据：\n");for(i = 0; i < Graph.vertexNum; ++i){ //初始化各个顶点（头节点）scanf("%c",&adjList[i].data);adjList[i].firstArcNode = NULL;}printf("输入相关联的边：\n");for(i = 0 ; i < Graph.arcNum; ++i){ //输入所有边（关联的点）编号scanf("%d,%d",&v1,&v2);p = (ArcNode*)malloc(sizeof(ArcNode));p->num = v2; （按照有向图处理，所以不是v1）p->nextArcNode = adjList[v1].firstArcNode;adjList[v1].firstArcNode = p;if(!Graph.kind){ //若为无向图（无向图在有向图的基础上多添加e个结点得到）p = (ArcNode*)malloc(sizeof(ArcNode));p->num = v1;p->nextArcNode = adjList[v2].firstArcNode;adjList[v2].firstArcNode = p;}}return 1;}//查找顶点v的第一个邻接点int FirstAdjVex(int v){if(adjList[v].firstArcNode)return adjList[v].firstArcNode->num;elsereturn -1;//对于有向图中出度为0的顶点建立邻接表时不存在邻接点 }//查找顶点v的下一个未被访问的邻接点int NextAdjVex(int v, int lastV){ArcNode* p;p = adjList[v].firstArcNode;while(p){if(!visited[p->num] && p->num!=lastV)return p->num;elsep = p->nextArcNode;}if(!p)return -1; //没有找到一个未被访问的邻接点}//对某一个节点作为始点的深度遍历算法int DFS(int v){int w;visited[v] = 1; //已经被访问过printf("%c",adjList[v].data);//输出顶点值for(w = FirstAdjVer(v); w >= 0; w = NextAdjVer(v,w)) //for循环为了递归返回的时候访问那些没有被访问的邻接点if(!visited[w])DFS(w);return 1;}//对整个图的深度遍历算法DFSint DFSGraph(void){int i;//初始化辅助数组for(i = 0; i < Graph.vertexNum; ++i)visited[i] = 0;//对每一个没有被访问的邻接点深度遍历for(i = 0; i < Graph.vertexNum; ++i)if(!visited[i])DFS(i);return 1;}//主函数测试int main(void){printf("创建以邻接表为存储结构的无向图........\n");CreateALGraph();printf("深度优先搜索遍历图：\n");DFSGraph();system("pause");return 0;}//测试数据：【解答5】typedef struct BSTNode{keytype key;struct BSTNode *lchild;struct BSTNode *rchild;}BSTNode,*BSTree;bool DeleteBSTNode(BSTree& root,keytype x){//在BST树中查找关键字为x的结点，找到后删除之BSTNode *T=root;while(T!=NULL){if(T->key>x) //转左子树T=T->lchild;else if(T->key<x) //转右子树T=T->rchild;else { Delete(T); return true; }//找到关键字为x的结点，删除之}return false; //BST树中没有此结点，报错}void Delete(BSTree& p){//从BST树中删除结点p，将结点p的中序直接前驱pre 放置到p的位置if(!p->rchlid){ //右子树空则只需重接它的左子树q=p; p=p->lchild; free(q);}esle if (!p->lchild){ //左子树空则只需重接它的右子树q=p; p=p->rchlid; free(q);}else{ //左右子树均不空，找p的中序直接前驱pre，用pre代替pq=p; pre=p->lchild; //q为pre的父结点while(pre->rchild){ //p的中序直接前驱pre是p的左孩子结点的最右端结点q=pre; pre=pre->rchild;}p->data=pre->data;//删除pre，这里只需重接pre的父结点的左右子树即可if(q!=p) q->rchild=pre->lchild; //重接q的右子树else q->lchild=pre->lchild; //重接q的左子树}//end else}//end Delete二、实验报告填写要求1、实验报告开头写明实验日期和实验题目2、中间部分写上算法3、最后写上实验结果。

一、实习背景与目的随着信息技术的飞速发展，数据结构作为计算机科学的核心基础之一，在软件开发和数据处理中扮演着至关重要的角色。

为了提高自身对数据结构应用的理解和掌握，本次实习旨在通过设计和实现一个基于链表与树结构的多功能数据管理系统，提升对数据结构理论知识的实践运用能力，并增强系统分析与设计的能力。

二、需求分析1. 程序所实现的功能：（1）实现链表的基本操作，如插入、删除、查找等；（2）实现二叉树的基本操作，如插入、删除、查找等；（3）实现数据管理系统，包括数据的存储、查询、修改、删除等；（4）实现用户界面，方便用户进行操作。

2. 程序的输入：（1）输入数据格式：链表数据以空格分隔，二叉树数据以括号表示，节点间用逗号分隔；（2）输入说明：用户需按照要求输入数据，系统将自动处理。

3. 程序的输出：（1）输出格式：链表、二叉树以文本形式输出；（2）输出说明：系统将按照用户操作要求，实时显示操作结果。

4. 测试数据：（1）链表测试数据：1 2 3 4 5；（2）二叉树测试数据：(1,2,(3,4,5),6)。

5. 合作人及其分工：（1）负责人：负责整体设计和开发；（2）成员1：负责链表和二叉树的基本操作实现；（3）成员2：负责数据管理系统的设计和实现；（4）成员3：负责用户界面设计和实现。

三、设计说明1. 主要的数据结构设计说明：（1）链表：采用单向链表实现，节点包含数据域和指针域；（2）二叉树：采用二叉搜索树实现，节点包含数据域和左右指针域。

2. 程序的主要流程图：（1）用户输入数据；（2）系统解析数据并创建链表和二叉树；（3）用户选择操作，系统根据操作进行相应处理；（4）系统输出操作结果。

3. 程序的主要模块：（1）链表模块：负责链表的基本操作；（2）二叉树模块：负责二叉树的基本操作；（3）数据管理系统模块：负责数据的存储、查询、修改、删除等；（4）用户界面模块：负责用户与系统的交互。

4. 程序的主要函数及其伪代码说明：（1）链表插入：function insertNode(head, data)（2）链表删除：function deleteNode(head, data)（3）二叉树插入：function insertNode(root, data)（4）二叉树删除：function deleteNode(root, data)5. 合作人设计分工：（1）负责人：负责整体设计和开发；（2）成员1：负责链表和二叉树的基本操作实现；（3）成员2：负责数据管理系统的设计和实现；（4）成员3：负责用户界面设计和实现。

杭州电子科技大学2010《数据结构》真题及解析一、是非题(每小题2分，共20分)1.线性表的顺序存储结构优于链式存储结构。

2.栈和队列也是线性表。

如果需要，可对它们中的任一元素进行操作。

3.非空广义表的表头和表尾都有可能是原子或广义表。

4.在二叉树的先序遍历序列中，任意-个结点均处在其孩子结点的前面。

5.通常，在二叉树的第i层上有2^i-1个结点。

6.二叉树按某种次序线索化后，任一结点均有指向其前驱和后继的线索指针。

6.赫夫曼树中的结点个数一定是奇数。

8.用邻接矩阵(数组表示法)存储一个图时，所需的存储空间大小与图的边数无关。

9.对于一棵m阶的B-树而言.树中每个结点至多有m个关键字，除根之外的所有非终端结点至少有┌m/2┐个关键字。

10.对于任何待排序序列来说，快速排序均快于冒泡排序。

二、选择题(每小题2分，共20分)1.递归过程可借助于_____转化为非递归过程。

A:线性表 B:队列 C:栈 D:数组2.循环队列用数组A[0..m-1]存放其元素值，设头尾游标分别为front(队头元素的位置)和rear(队尾元素的位置)，则当前队列中的元素个数是_______。

A: rear-front B: rear-front+1C: (rear-front+m)%m D: (rear-front+1+m)%m3.对广义表A=（（a, （6）），(c，（））,d）执行操作gettail(gethead(gettail （A）））的结果是:________。

A:（） B:(()) C:d D:(d)4.对二叉排序树______可得到有序序列。

A:按层遍历 B:前序遍历C:中序遍历 D：后序遍历5.在有n个结点的二叉树的二叉链表表示中，空指针数为________。

A:不定 B: n+1 C:n D：n-16.图示的三棵二叉树中_____为最优二叉树。

A: B: C:7.设无向图G=(V,E)和G=(V′,E′)，若G′是G的生成树，则下面不正确的说法是_________。

实验题目一一、单链表基本运算【问题描述】设计并实现线性表的单链表存储和运算。

【基本要求】实现单链表的插入、删除和遍历运算，每种操作用一个函数实现。

插入操作：将一个新元素插入表中指定序号的位置。

删除操作：将指定序号的元素从表中删除。

遍历操作：从表头按次序输入所有元素的值，若是空表，则输出信息“empty list!”。

【实现提示】程序运行时，首先在main函数中创建空的、带头结点的单链表。

然后多次调用实现插入操作的函数（每次都将元素在序号1位置上插入），将元素依次插入表中，最后调用实现遍历操作的函数输出所有元素。

之后再多次调用实现删除操作的函数将表还原为空表（每次都删除第1个元素，每删除一个元素后，将表中剩余元素都输出一次）。

【测试数据】输入数据：1 2 3 4 5 0（为0时结束，0不存入链表）第一次输出：5 4 3 2 1第二次输出：4 3 2 1第三次输出：3 2 1第四次输出：2 1第五次输出：1第六次输出：empty list!二、约瑟夫环问题【问题描述】编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。

现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。

报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出列为止。

【基本要求】利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。

【测试数据】M的初始值为20；n等于7，7个人的密码依次为：3，1，7，2，4，8，4。

输出为：6，1，4，7，2，3，5【实现提示】程序运行时，首先要求用户指定初始报数上限值，然后读取各人的密码。

可设n≤30。

此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。

【选作内容】用顺序存储结构实现该题目。

三、一元多项式相加、减运算器【问题描述】设计一个一元稀疏多项式简单计算器。

数据结构课程设计要求1.学生必须仔细阅读《数据结构》课程设计题目，认真主动完成课设的要求。

有问题及时主动与老师联系沟通。

2.学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况。

3.课程设计完成要求运行界面友好（有菜单）、操作方便、输出结果正确、可读性强，每种操作有验证性输出。

4.按规定时间提交课程设计报告，过期计为0分。

课程设计实习报告封面的书写格式课程设计课程：数据结构题目：专业班级：姓名：学号：设计时间：指导教师：课程设计报告的内容一、设计题目二、运行环境（软、硬件环境）三、算法设计的思想四、算法的流程图五、算法设计分析六、源代码七、运行结果分析八、收获及体会《数据结构》课程设计参考题课程设计题一：排序算法比较一、设计目的1．掌握各种排序的基本思想。

2．掌握各种排序方法的算法实现。

3．掌握各种排序方法的优劣分析及花费的时间的计算。

4．掌握各种排序方法所适应的不同场合。

二、设计内容和要求利用随机函数产生3000个随机整数，利用插入排序、起泡排序、选择排序、快速排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。

--------------------------------------课程设计题二：图的深度周游一、设计目的1．掌握图的邻接表存贮结构。

2．掌握堆栈的基本运算实现。

3．掌握图的邻接表的算法实现。

4．掌握图的深度优先搜索周游算法实现。

二、设计内容和要求对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用堆栈的五种基本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现图的深度优先搜索周游。

-------------------------------------- 课程设计题三：图的广度周游一、设计目的1．掌握图的邻接表存贮结构。

2．掌握队列的基本运算实现。

3．掌握图的邻接表的算法实现。

4．掌握图的广度优先搜索周游算法实现。

2010年数据结构考试复习资料-杀虫剂数据结构试卷（一）一、单选题（每题 2 分，共20分）1.栈和队列的共同特点是( )。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表 D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。

A．688 B．678 C．692 D．6965.二叉树的第k层的结点数最多为( ).A．2k-1 B.2K+1 C.2K-1D. 2k-16.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，37.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：_________、_________、_________和_________。

2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。

3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_-_________个，树的深度为___________，树的度为_________。

4.后缀算式9 2 3 +- 10 2 / -的值为__________。

中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。

《数据结构实验》的实验题目及实验报告模板实验一客房管理（链表实验）●实现功能：采用结构化程序设计思想，编程实现客房管理程序的各个功能函数，从而熟练掌握单链表的创建、输出、查找、修改、插入、删除、排序和复杂综合应用等操作的算法实现。

以带表头结点的单链表为存储结构，实现如下客房管理的设计要求。

●实验机时：8●设计要求：#include<stdio.h>#include<stdlib.h>#include<string.h>//定义客房链表结点结构typedef struct HNode{char roomN[7]; //客房名称float Price; //标准价格float PriceL; //入住价格(默认值=标准价格*80%)int Beds; //床位数Bedschar State[5]; //入住状态(值域："空闲"、"入住"、"预订"，默认值为"空闲")struct HNode *next; //指针域}Hotel, *HLink;(1)实现创建客房信息链表函数void Build(HLink &H)，输入（客房名称、标准价格、床位数），同时修改入住价格、入住状态为默认值，即入住价格=标准价格*80%，入住状态为”空闲”（提示：用strcpy()字符串拷贝函数）。

为了提高程序调试效率，要求：用文件操作来输入客房信息（客房名称、标准价格、床位数）；(2)实现输出客房信息函数void Exp(HLink H)，输出所有客房的客房名称、标准价格、入住价格、床位数、入住状态；(3)函数int Find(HLink &H, char *roomN)，查找房间名称为roomN的客房。

如果找到，则返回该客房在链表中的位置序号（>=1），否则返回0。

提示：用strcmp()字符串比较函数；(4)实现函数void updateH(HLink &H, int beds, char *state)，将床位数为beds的客房入住状态改为state。

1、在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为（ B ）。

A) rear=rear->next; B) front=front->next;C) rear=front->next; D) front=rear->next ;2、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A3、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的4、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的5、n个顶点的强连通图至少有（ A ）条边。

A）n B）n+1 C）n-1 D）n(n-1)6、串的逻辑结构与（ D ）的逻辑结构不相同。

A）线性表 B）栈C）队列 D）集合7、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法8、栈进行插入和删除操作的特点是（ A ）。

A）LIFO B）FIFOC）FCFS D）HPF9、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一C）不含回路 D）有n条边10、数据结构研究的内容是（ D ）。

A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面11、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为（ C ）。

A）4 B）5C）6 D）712、数据结构研究的内容是（ D ）。

A）数据的逻辑结构 B）数据的存储结构C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面13、链式存储的存储结构所占存储空间（ A ）。

《数据结构》实验报告二学校：班级：09软工A1学号：09XXXXX 姓名：XXX日期：2010 .04.08 程序名：L2311.CPP一、上机实验的问题和要求：单链表的查找、插入与删除。

设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。

具体实现要求：1.从键盘输入20个整数，产生带表头的单链表，并输入结点值。

2.从键盘输入1个整数，在单链表中查找该结点。

若找到，则显示“找到了”；否则，则显示“找不到”。

3.从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。

4.从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。

5.将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。

6.删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。

7.把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。

8.（★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。

二、程序设计的基本思想，原理和算法描述：（包括程序的结构，数据结构，输入/输出设计，符号名说明等）三、源程序及注释：#include <iostream.h>//单链表的定义：typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char typedef struct node //结点类型定义{ DataType data; //结点的数据域struct node *next; //结点的指针域}ListNode,*LinkList;//typedef ListNode *LinkList;void main(){int i;DataType key,x;LinkList head;//ListNode *p;LinkList p;LinkList CreateList(void);void PrintList(LinkList head);LinkList LocateNode(LinkList head,DataType key);LinkList GetNode(LinkList head,int i);void InsertList(LinkList head,DataType x,int i);void DeleteList(LinkList head,int i);void DeleteManyList(LinkList head);void DeleteEvenList(LinkList head);void ChangeCircList(LinkList head);void PrintCircList(LinkList head);head=CreateList(); //建立单链表PrintList(head); //打印单链表cout<<"输入要查找的值:";cin>>key;p=LocateNode(head,key); //单链表查找cout<<"输入要查找的位置:";cin>>i;p=GetNode(head, i);cout<<"请输入欲插入元素的位置:";cin>>i;cout<<"请输入欲插入的元素(整数):";cin>>x;InsertList(head,x,i); //单链表插入PrintList(head); //打印单链表cout<<"请输入欲删除结点的位置:";cin>>i;DeleteList(head,i); //单链表删除PrintList(head); //打印单链表DeleteManyList(head); //删除重复值PrintList(head); //打印单链表DeleteEvenList(head); //删除偶数值PrintList(head); //打印单链表ChangeCircList(head); //修改为循环单链表PrintCircList(head); //打印循环单链表/*void DivideList(LinkList head,LinkList *A,LinkList *B);//分割成两个单链表DivideList(head, &A, &B);PrintList(A);PrintList(B);*/}//单链表的建立：LinkList CreateList(void){LinkList head,p,q;head=new ListNode;head->next=NULL;q=head;cout<<"输入20个整数(以空格分隔):";for(int i=0;i<20;i++){p=new ListNode;cin>>p->data;q->next=p;q=q->next;}q->next=NULL;return head;//在此插入必要的语句}//单链表的打印：void PrintList(LinkList head){LinkList L=head;cout<<"单链表打印:";while(L->next!=NULL){cout<<L->next->data<<" ";L=L->next;}cout<<endl;//在此插入必要的语句}//单链表的查找1：LinkList LocateNode(LinkList head,DataType key) {LinkList L=head;while(L->next!=NULL){{cout<<"找到了!\n";return L;}L=L->next;}cout<<"没找到!\n";return L;//在此插入必要的语句}//*单链表的查找2：LinkList GetNode(LinkList head,int i){LinkList L=head;for(int j=1;j<=i;j++){L=L->next;if(L->next==NULL){cout<<"<警告!您输入的节点位置不存在!>\n查找失败!\n";return L;}}if(i<=0){cout<<"<警告!您输入的节点位置不存在!>\n查找失败!\n";return L;}cout<<L->data;cout<<"找到了!\n";return L;}//单链表的插入：void InsertList(LinkList head,DataType x,int i){LinkList L=head,p;for(int j=1;j<i;j++){//if(L->next->next==NULL){cout<<"<警告!您输入的元素位置不存在,程序自动将数插到链表尾部!>\n";break;}L=L->next;}if(i<=0){cout<<"<警告!您输入的元素位置不存在,程序自动将数插到链表的头结的后面!>\n";}//L=L->next;p=new ListNode;p->data=x;p->next=L->next;L->next=p;//在此插入必要的语句}//单链表的删除：void DeleteList(LinkList head,int i){LinkList L=head;for(int j=1;j<i;j++){L=L->next;if(L->next==NULL){cout<<"<警告!您输入的节点位置不存在!>\n删除失败!\n";return;}}if(i<=0){cout<<"<警告!您输入的节点位置不存在!>\n删除失败!\n";return;}L->next=L->next->next;cout<<"删除成功!\n";//在此插入必要的语句}//删除单链表中重复值：void DeleteManyList(LinkList head){LinkList L=head,p;cout<<"删除链表中重复的元素\n";while(L->next!=NULL){p=L->next;while(p->next!=NULL){if(L->next->data==p->next->data)L->next=L->next->next;p=p->next;}L=L->next;}//在此插入必要的语句}//删除单链表中偶数值：void DeleteEvenList(LinkList head){LinkList L=head;cout<<"删除链表中的偶数值\n";do{if(L->next->data%2==0){if(L->next->next!=NULL)L->next=L->next->next;else{L->next=NULL;break;}}L=L->next;}while(L->next!=NULL);//在此插入必要的语句}//修改为循环单链表：void ChangeCircList(LinkList head){LinkList L=head;cout<<"修改为循环单链表\n";while(L->next!=NULL){L=L->next;}L->next=head;//在此插入必要的语句}//循环单链表的打印：void PrintCircList(LinkList head){LinkList L=head;cout<<"循环单链表打印:";while(L->next!=head){cout<<L->next->data<<" ";L=L->next;}cout<<endl;//在此插入必要的语句}/*//分割成两个单链表void DivideList(LinkList head,LinkList *A,LinkList *B); {//在此插入必要的语句}*/四、运行输出结果：五、调试和运行程序过程中产生的问题及采取的措施：当需要插入和删除的数值超过20时，如果不写：if(L->next==NULL){cout<<"<警告!您输入的节点位置不存在!>\n删除失败!\n";return;}那么就会不产生效果.六、对算法的程序的讨论、分析，改进设想，其它经验教训：七、对实验方式、组织、设备、题目的意见和建议：。

《数据结构》实验指导第一章实验0 C/C++程序设计一、实验基础知识二、实验案例1 学生成绩统计系统[问题描述]一个班同学的学号为1-n，输入n位同学的学号、姓名、语文、数学、英语等3门课程成绩，统计每位同学的总分后按成绩从高到低的次序输出。

[基本要求]实现成绩表的录入、总分统计、总分排序和输出。

[测试数据]对于10个同学的学号、姓名、语文、数学、英语等3门课程成绩设计实例数据[实现提示]1）用结构体设计同学记录，学号、各课程成绩和总分数据域用整型，姓名域采用字符数组；学生成绩表用数组模拟，数组大小根据实际学生数动态申请；学生成绩统计系统通过主菜单形式提供成绩表初始化、学生成绩录入、学生总分统计和排名、成绩表输出等功能。

[提高部分]1）实现成绩表的文件录入和文件保存2）实现成绩键盘录入的有效数据限制2复数计算器[问题描述]设计一个能进行复数运算的演示程序。

[基本要求]实现复数的基本运算：1）由输入的实部和虚部生成一个复数；2）求两个复数的和；3）求两个复数的差；4）求两个复数的乘积；5）求复数的实部；6）求复数的虚部[测试数据]0+0=03.1,0;4.22,8.9;输出7.32+i8.99,8;-9,8;输出i169,-8;-9,-8;输出-i16-9,8;-9,-8;输出-189,-7;-9,8;输出i9,-9;-9,8;输出-i[实现提示]将复数的实部和虚部组成结构体数据类型，利用实数的操作实现复数的操作。

[提高部分]1）实现复数的除法运算；2）求共轭复数3有理数计算器[问题描述]设计一个能进行有理数运算的演示程序。

[基本要求]实现有理数的基本运算：1）由输入的分子和分母生成一个有理数；2）求两个有理数的和；3）求两个有理数的差；4）求两个有理数的乘积；5）求有理数的分子；6）求有理数的分母[实现提示]将有理数的分子和分母组成结构体数据类型，利用整数的操作实现有理数的操作。

[提高部分]1）实现有理数的除法运算；第二章线性表一、实验基础知识二、实验案例4顺序表基本操作演示系统[问题描述]设计一个能进行顺序表基本运算的演示程序。

浙江理工大学二O一O年硕士学位研究生招生入学考试试题考试科目：数据结构与数据库技术代码：938 （*请考生在答题纸上答题，在此试题纸上答题无效）第一部分：数据结构（本部分共90分）一、程序设计题1. 假设以带头节点的循环链表表示队列，并且只设一个队尾指针rear，不设队首指针，试编写相应的入队列和出队列一个结点的算法。

（20分）2．一颗树的根其层次定义为0。

任何其它结点的层次定义为比它的双亲的层次大1。

树的深度是层次最大的结点的层次。

一颗树的内部路径长度是该树中边的总数。

已知二叉树的根结点为t，其二叉链表结构定义如下：typedef struct node {char data;struct node *lch,*rch;int level;} tnode ;这里，data为结点的名称，lch为其左孩子，rch为其右孩子，level为结点的层次。

试编写非递归程序算法，输出这颗树的深度和内部路径长度。

（25分）3．已知哈希(Hash)函数H(k)=k%p（k为线性表的关键字），用开放地址法处理冲突，其中：d1=H(k)，d i=( d i-1+m)%p (i=2,3,,…)；试编写程序算法，在H[0~p-1]的散列地址空间中，对关键字序列a[0],a[1],…,a[p-1]构造哈希表（假设每个关键字最终都能找到地址），并计算输出在等概率情况下查找成功的平均查找长度。

（20分）4．已知单链表结构如下所示。

头指针为head，关键字域为key。

试编写程序构造一个单链表，将串s中的每个字符存放到单链表中去（每个结点存放一个字符），同时在已有的单链表基础上，编写程序采用直接插入排序算法将单链表中的各个结点按字符值大小进行升序排序。

（25分）typedef struct node {char key;struct node *next;} lnode;第二部分：数据库技术（本部分共60分）二、解答题（下列各题中任选6小题解答，每小题10分，按得分最多的6小题计算分数，本题得分最多不超过60分）数据库Sales用来存放某企业销售数据，它有4张表，表Products用来存放产品信息（其中合计销售额amount是未知的）；表Customers用来存放客户信息；表Orders用来存放订单总体信息；OrderDetails用来存放订单明细信息。

华北水利水电学院数据结构实验报告2012～2013学年第一学期2010级计算机科学与技术专业班级：2010134 学号：201013418 姓名：杨学成实验三树的应用一、实验题目：树的应用——哈夫曼编码二、实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。

根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。

从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。

要求：1．输出存放哈夫曼树的数组HT的初态和终态；2．输出每个字符的哈夫曼编码；3．输入由上述若干字符组成的字符串，对电文进行编码并输出；4．（选作）输入电文的哈夫曼编码，进行译码并输出。

三、程序源代码：#include <iostream.h>#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct{char date;int weight;int parent,lchild,rchild;}HTNode ,*HuffmanTree;typedef char * *HuffmanCode;void Select(HuffmanTree HT,int i,int &s1,int &s2){int m1,m2,k;m1=m2=10000;s1=s2=0;for (k=1;k<=i;k++){if((HT[k].parent==0)&&(HT[k].weight<m1)){m2=m1;s2=s1;m1=HT[k].weight;s1=k;}else if((HT[k].parent==0)&&(HT[k].weight<m2)){m2=HT[k].weight;s2=k;}}}void main (){char str[81],str2[81];HuffmanTree HT;HuffmanCode HC;int w[81], n,i,s1,s2,m,c,f;printf ("请输入编码字符的个数:");scanf("%d",&n);printf("\n编码字符:");cin>>str;printf("\n请输入字符对应的权重:");for (i=0;i<n;i++){scanf("%d",&w[i]);}if(n<=1) return;m=2*n-1;HT=(HuffmanTree) malloc ((m+1)*sizeof(HTNode));for(i=1;i<=n;++i){HT[i].date=str[i-1];HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for(;i<=m;++i){HT[i].date='-';HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}cout<<" HT的初态"<<endl;cout<<"-------------------------------------------------------------"<<endl;cout<<" date weight parent lchild rchild"<<endl;cout<<"-------------------------------------------------------------"<<endl;for(i=1;i<=m;i++){printf("%4c %4d %4d %4d %4d\n" ,HT[i].date,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);cout<<"-----------------------------------------------------------"<<endl;}for (i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}cout<<" HT的终态"<<endl;cout<<"-------------------------------------------------------------"<<endl;cout<<" date weight parent lchild rchild"<<endl;cout<<"-------------------------------------------------------------"<<endl;for(i=1;i<=m;i++){printf("%4c %4d %4d %4d %4d\n" ,HT[i].date,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);cout<<"-------------------------------------------------------------"<<endl;}HC=(HuffmanCode)malloc((n+1)*sizeof(char *));char *cd=(char *)malloc(n*sizeof(char));cd[n-1]='\0';for (i=1;i<=n;++i)int start=n-1;for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) if(HT[f].lchild==c)cd[--start]='0';else cd[--start]='1';HC[i]=(char *) malloc ((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}free(cd);cout<<"字符的编码"<<endl;for (i=1;i<=n;i++){printf("%c : %s\n",HT[i].date,HC[i]);}printf("请输入上述字符组成的任何字符串：");cin>>str2;for (i=0;str2[i]!='\0';i++){for (int j=1;j<=n;j++){if (str2[i]==HT[j].date)cout<<HC[j];}}cout<<endl<<"请输入哈夫曼电文的编码:";cin>>str2;char str4[81];int k=0,tr=0;for (i=0;str2[i]!='\0';i++)int a=i, t=0;char str3[81];tr=0;str3[t]=str2[i];t++;str3[t]='\0';for(;strlen(str3)<n;){for (int j=1;j<=n;j++){if( strcmp(str3,HC[j])==0){str4[k]=HT[j].date;k++;tr=1;}}if (tr==1)break;i++;str3[t]=str2[i];t++;str3[t]='\0';}}if (tr==0){cout<<"It is error.";str4[k]='\0';}else{str4[k]='\0';cout<<str4;}cout<<endl;}四、测试结果：五、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）注：内容一律使用宋体五号字，单倍行间距对我来说，数据结构这门课还是有点难度。