下载文档原格式
试卷代号:1252中央广播电视大学2013-2014学年度第一学期“开放学科”期末考试数据结构（本）试题2014年1月一、单项选择题（每小题2分，共30分）1. 在数据结构和算法中，与所使用的计算机有关的是（B）。
A．数据元数间的抽象关系 B．数据的存储结构C．算法的时间复杂度 D．数据的逻辑结构2.对顺序表,以下叙述中正确的是 ( A )。
A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C．数据元素不能随机访问D．插入操作不需要移动元素3．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始),需移动元素的个数为（C）。
A．9 B．10 C．15 D．164. 设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为( A)。
A.p->next=p->next->next;B.p=p->next;C.p=p->next->next;D.p->next=p ;5．元素1，3，5，7按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的可能输出序列是（A）。
（进栈出栈可以交替进行）。
A．7，5，3，1 B．7，3，1,5C．7，5，1，3 D．5,1，3，76．对一个栈顶指针为top的链栈进行进栈操作，设P为待进栈的结点，则执行（C）。
A．p=top->next; top=top next; B．p->next=top;C．p->next=top;top=p; D．top=p;7．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第33号元素对应于矩阵中的元素是（D）。
(矩阵中的第1个元素是a1,1）A．a7,6 B．a10,8C．a9,2 D．a8,58．设有一个17阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,6在一维数组B中的下标是（C）。
实验题目一一、单链表基本运算【问题描述】设计并实现线性表的单链表存储和运算。
【基本要求】实现单链表的插入、删除和遍历运算，每种操作用一个函数实现。
插入操作：将一个新元素插入表中指定序号的位置。
删除操作：将指定序号的元素从表中删除。
遍历操作：从表头按次序输入所有元素的值，若是空表，则输出信息“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。
此题所用的循环链表中不需要“头结点”，请注意空表和非空表的界限。
【选作内容】用顺序存储结构实现该题目。
三、一元多项式相加、减运算器【问题描述】设计一个一元稀疏多项式简单计算器。
大题共4小题，每小题5分。
共20分)
请在答题卡上作答。
26．设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空，回答下列问题。
请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。
29．给定有向无环图G如题29图所示，写出G的5种不同的拓扑排序序列。
的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq 序。
函数f3l完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加值调整结r旨位置。
请将空白处(1)～(3)补充完整。
在答题卡上作答。
回答下列问题。
五、算法设计题(本大题共l小题，共“l0分) 请在答题卡上作答。
34．已知带头结点的单链表类型定义如下：
- 10 -。
课程设计任务书题目：迷宫设计学号：姓名：专业：网络技术课程：数据结构指导教师：职称：讲师完成时间：2013年12 月----2014 年1 月年月日课程设计任务书及成绩评定目录一．迷宫求解································（1）问题描述···········································（2）需求分析及设计思路·································（3）数据结构定义········································（4）系统功能模块介绍····································（5）源代码··············································（6）运行结果及调试分析································（7）课程设计总结·····························一．迷宫求解（1）问题描述输入一个任意大小的迷宫数据，用递归和非递归两种方法求出一条走出迷宫的路径，并将路径输出。
高等教育自学考试数据结构导论真题2014年4月(总分100, 做题时间150分钟)课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。
错涂、多涂或未涂均无分。
1.下列几种算法时间复杂度中，最小的是SSS_SINGLE_SELA O(log2n)B O(n)C O(n2)D O(1)该题您未回答:х该问题分值: 2答案:A2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有SSS_SINGLE_SELA 索引存储方式和树形存储方式B 线性存储方式和散列存储方式C 线性存储方式和索引存储方式D 索引存储方式和散列存储方式该题您未回答:х该问题分值: 2答案:D3.表长为n的顺序表中做删除运算的平均时间复杂度为SSS_SINGLE_SELA O(1)B O(log2n)C O(n)D O(n2)该题您未回答:х该问题分值: 2答案:C4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为SSS_SINGLE_SELA O(1)B O(log2n)C O(n)D O(n2)该题您未回答:х该问题分值: 2答案:C5.元素的进栈次序为A，B，C，D，E，出栈的第一个元素为E，则第四个出栈的元素为SSS_SINGLE_SELA DB CC BD A该题您未回答:х该问题分值: 2答案:C6.带头结点的链队列中，队列头和队列尾指针分别为front和rear，则判断队列空的条件为SSS_SINGLE_SELA front==rearB front!=NULLC rear!==NULLD front==NULL该题您未回答:х该问题分值: 2答案:A7.深度为5的二叉树，结点个数最多为SSS_SINGLE_SELA 31个B 32个C 63个D 64个该题您未回答:х该问题分值: 2答案:A8.如果结点A有2个兄弟结点，结点B为A的双亲，则B的度为SSS_SINGLE_SELA 1B 3C 4D 5该题您未回答:х该问题分值: 2答案:B9.将题9图所示的一棵树转换为二叉树，结点C是SSS_SINGLE_SELA A的左孩子B A的右孩子C B的右孩子D E的右孩子该题您未回答:х该问题分值: 2答案:D10.n为图的顶点个数，e为图中弧的数目，则图的拓扑排序算法的时间复杂度为SSS_SINGLE_SELA O(n)B O(e)C O(n-e)D O(n+e)该题您未回答:х该问题分值: 2答案:D11.无向图的邻接矩阵是SSS_SINGLE_SELA 对角矩阵B 稀疏矩阵C 上三角矩阵D 对称矩阵该题您未回答:х该问题分值: 2答案:D12.在具有101个元素的顺序表中查找值为x的元素结点时，平均比较元素的次数为SSS_SINGLE_SELA 50B 51C 100D 101该题您未回答:х该问题分值: 2答案:A13.构造散列函数的方法很多，常用的构造方法有SSS_SINGLE_SELA 数字分析法、除留余数法、平方取中法B 线性探测法、二次探测法、除留余数法C 线性探测法、除留余数法、链地址法D 线性探测法、二次探测法、链地址法该题您未回答:х该问题分值: 2答案:D14.就平均时间性能而言，快速排序方法最佳，其时间复杂度为SSS_SINGLE_SELA O(n)B O(nlog2n)C O(n2)D O(1og2n)该题您未回答:х该问题分值: 2答案:B15.下述算法中，不稳定的排序算法是SSS_SINGLE_SELA 直接插入排序B 冒泡排序C 堆排序D 归并排序该题您未回答:х该问题分值: 2答案:C二、填空题(本大题共13小题，每小题2分，共26分)16.数据的基本单位是_______。
洛阳理工学院课程设计说明书课程名称_________数据结构_______________ 设计课题________哈夫曼编/译码器_________ 专业______计算机科学与技术_________ 班级________B12xxxx _____________ 学号_______B12xxxxxxx________________ 姓名____ xxx ______________完成日期2014年6月14日课程设计任务书设计题目：_____________哈夫曼编/译码器___________________ _________________________________________________________设计内容与要求：设计内容：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。
要求：以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。
指导教师：xxxx2014 年6 月5日课程设计评语成绩：指导教师：年月日【问题描述】打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，设计一个哈夫曼编/译码系统。
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。
这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。
对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。
试为这样的信息收发站编写一个哈夫曼码的编/译码系统。
【基本要求】以每个字符出现的次数为权值，建立哈夫曼树，求出哈夫曼编码，对文件yuanwen中的正文进行编码，将结果存到文件yiwen中，再对文件yiwen中的代码进行译码，结果存到textfile中。
数据结构单链表实验报告记录————————————————————————————————作者：————————————————————————————————日期：一、设计人员相关信息1.设计者姓名、学号和班号：12地信李晓婧120122429832.设计日期：2014.3.上机环境：VC++6.0二、程序设计相关信息1.实验题目：编写一个程序，实现单链表的各种基本运算（假设单链表的元素类型为char），并在此基础上设计一个程序，完成如下功能：（1）初始化单链表；（2）采用尾插法依次插入元素a,b,c,d,e;（3）输出单链表（4）输出单链表长度（5）判断单链表是否为空（6）输出单链表第3个元素（7）输出元素a的位置（8）在第4个元素位置上插入元素f（9）输出单链表（10）删除第三个元素（11）输出单链表（12）释放单链表2.实验项目组成：（1）插入和删除节点操作（2）建立单链表尾插法建表（3）线性表基本运算在单链表中的实现初始化线性表销毁线性表判断线性表是否为空表求线性表的长度3.实验项目的程序结构（程序中的函数调用关系图）：MainLinkListInitListCreateListRDispListListLengthListEmptyGetElemLocateElemListInsertListDeleteDestroyList4.实验项目包含的各个文件中的函数的功能描述：●尾插法建表CreateListR：将新节点插到当前链表的表尾上，为此必须增加一个尾指针r，使其始终指向当前链表的尾节点。
●初始化线性表InitList：该运算建立一个空的单链表，即创建一个头节点；●销毁线性表DestroyList：释放单链表占用的内存空间，即逐一释放全部节点的空间；●判断线性表是否为空表ListEmpty：若单链表没有数据节点，则返回真，否则返回假；●求线性表的长度ListLength：返回单链表中数据节点的个数；●输出线性表DispList：逐一扫描单链表的每个数据节点，并显示各节点的data域值；●求线性表中某个数据元素值GetElem：在单链表中从头开始找到第i个节点，若存在第i个数据节点，则将其data域值赋给变量e；●按元素值查找LocateElem：在单链表中从头开始找第一个值域与e相等的节点，若存在这样的节点，则返回逻辑序号，否则返回0；●插入数据元素ListInsert：先在单链表中找到第i-1个节点*p，若存在这样的节点，将值为e的节点*s插入到*p节点的后面；●删除数据元素ListDelete：先在单链表中找到第i-1个节点*p，若存在这样的节点，且也存在后继节点*q；删除*q节点，返回TRUE；否则返回FALSE表示参数i错误。
山东大学软件工程学院数据结构课程实验报告学号：姓名：班级：软件工程2014级2班实验题目：矩阵和散列表实验学时：实验日期： 2015.11.11实验目的：掌握特殊矩阵和稀疏矩阵。
掌握散列表及其应用。
硬件环境：实验室软件环境：Vistual Studio 2013实验步骤与内容：实验内容：1、创建三对角矩阵类，采用按列映射方式，提供store和retrieve 方法。
2、创建下三角矩阵类，采用按列映射方式，提供store和retrieve 方法。
3、创建稀疏矩阵类，采用行主顺序把稀疏矩阵映射到一维数组中，实现稀疏矩阵的转置和两个稀疏矩阵的加法操作。
4、使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。
分别使用线性开型寻址和链表散列解决溢出。
代码体：ChainHashTableNode.h#pragma once#include"ChainHashTableNode.h"using namespace std;class ChainHashTable{public:ChainHashTable(int divisor);~ChainHashTable();bool Insert(int k);bool Search(int k);void print();private:int d;ChainHashTableNode *ht;};ChainHashTableNode.cpp#include"ChainHashTable.h"#include<iostream>using namespace std;ChainHashTable::ChainHashTable(int divisor) {d = divisor;ht = new ChainHashTableNode[d];}bool ChainHashTable::Insert(int k){int j = k%d;if (ht[j].Insert(k)){return true;}else{return false;}}void ChainHashTable::print(){for (int i = 0; i < d; i++){ht[i].print();}}ChainHashTableNode.h#pragma once#include"Node.h"class ChainHashTableNode{public:ChainHashTableNode();bool Insert(int k);bool Search(int k);void print();private:Node *first;};ChainHashTableNode.cpp#include"ChainHashTableNode.h"#include<iostream>using namespace std; ChainHashTableNode::ChainHashTableNode() {first = 0;}bool ChainHashTableNode::Search(int k) {if (first == 0) return false;Node *current = first;while (current){if (current->value == k){return true;}current = current->link;if (current){if (current->value == k){return true;}}}return false;}bool ChainHashTableNode::Insert(int k) {if (Search(k)){cout << "已经存在此元素" << endl;return false;}else {Node *p = new Node();p->value = k;if (first == 0){first = p;return true;}else{p->link = first;first = p;return true;}}}void ChainHashTableNode::print(){Node *current = first;if (first){while (first){cout << first->value << " ";first = first->link;}cout << endl;first = current;}else {cout << -1 << endl;}}HashTable.h#pragma onceclass HashTable{public:HashTable(int divisor);~HashTable();int Search(int k);//搜索算法bool Insert(int e);void print();private:int hSearch(int k);int d;//除数int *ht;//桶，大小取决于d就是除数是多少bool *empty;//一维数组，用来存储第I个桶是否存入了元素};HashTable.cpp#include"HashTable.h"#include<iostream>using namespace std;HashTable::HashTable(int divisor){d = divisor;ht = new int[d];empty = new bool[d];for (int i = 0; i < d; i++){empty[i] = true;ht[i] = 0;}}HashTable::~HashTable(){delete[]ht;delete[]empty;}int HashTable::hSearch(int k)//搜索值为K的元素{int i = k%d;int j = i;do{if (ht[j] == k || empty[j]) return j;j = (j + 1) % d;} while (j != i);return j;}int HashTable::Search(int k)//搜索值为K的元素{int b = hSearch(k);if (ht[b] == k) return b;return -1;}bool HashTable::Insert(int e){int b = hSearch(e);if (empty[b]){ht[b] = e;empty[b] = false;return true;}else if (ht[b] == e){cout << "已经存在此元素" << endl;return false;}else{cout << "表已经满了" << endl;return false;}}void HashTable::print(){for (int i = 0; i < 961; i++){cout << ht[i] << " ";}cout << endl;return;}LowerTriangularMatrix.h#pragma onceclass LowerTriangularMatrix{public:LowerTriangularMatrix(int size);void Store(int x, int i, int j);//向矩阵里存储一个元素int Retrieve(int i, int j);//返回矩阵中的一个元素void print();private:int n;//矩阵维数int sum;//矩阵非零元素个数int *t;//用数组来存储矩阵};LowerTriangularMatrix.cpp#include"LowerTriangularMatrix.h"#include<iostream>using namespace std;LowerTriangularMatrix::LowerTriangularMatrix(int size){n = size;sum = n*(n + 1) / 2;t = new int[sum];}void LowerTriangularMatrix::Store(int x, int i, int j){if (i<0 || j<0 || i >= n || j >= n){cout << "下三角矩阵行列输入错误" << i << " " << j << endl;return;}else if (x == 0){cout << "下三角所添加的元素必须非零" << endl;return;}else if (i<j){cout << "下三角添加元素位置错误" << endl;return;}t[sum - ((n - j)*(n - j + 1) / 2) + (i - j)] = x;return;}int LowerTriangularMatrix::Retrieve(int i, int j){if (i<0 || j<0 || i >= (n - 1) || j >= (n - 1)){cout << "三对角矩阵行列输入错误" << endl;return -1;}else if (i >= j){return t[sum - ((n - j)*(n - j + 1) / 2) + (i - j)];}else{return 0;}}void LowerTriangularMatrix::print(){for (int i = 0; i < sum; i++){cout << t[i] << " ";}cout << endl;return;}Node.h#pragma onceclass Node{friend class ChainHashTableNode;private:int value;Node *link;};Node.cpp#include"Node.h"using namespace std;SparseMatrix.h#pragma once#include"Term.h"class SparseMatrix{public:SparseMatrix(int row, int col);void transpose();void Store(int x, int i, int j);//向矩阵里存储一个元素void Add(SparseMatrix &b);//两个稀疏矩阵相加void print();private:int row, col;//数组维数int sum;//元素个数int maxsum;//最多的元素个数Term *t;//存储的数组};SparseMatrix.cpp#include"SparseMatrix.h"#include<iostream>using namespace std;SparseMatrix::SparseMatrix(int r, int c){row = r;col = c;sum = 0;maxsum = r*c;t = new Term[maxsum];}void SparseMatrix::transpose(){Term *cur = new Term[maxsum];int *ColSize = new int[col];int *RowNext = new int[row];for (int i = 0; i < col; i++) ColSize[i] = 0;for (int i = 0; i < row; i++) RowNext[i] = 0;for (int i = 0; i < sum; i++) ColSize[t[i].col]++;//表示每一列的非零元素个数RowNext[0] = 0;for (int i = 1; i < col; i++) RowNext[i] = RowNext[i - 1] + ColSize[i - 1];//表示新矩阵中每一行的矩阵的前面的矩阵的个数//进入转置操作for (int i = 0; i < sum; i++){int j = RowNext[t[i].col]++;cur[j].value = t[i].value;cur[j].col = t[i].row;cur[j].row = t[i].col;}delete t;t = cur;}void SparseMatrix::Store(int x, int i, int j){t[sum].value = x;t[sum].row = i;t[sum].col = j;sum++;return;}void SparseMatrix::print(){for (int i = 0; i < sum; i++){cout << t[i].value << " ";}cout << endl;return;}void SparseMatrix::Add(SparseMatrix &b)//两个稀疏矩阵相加{if (col != b.col || row != b.row){cout << "两个矩阵行列不同无法相加" << endl;return;}int sa = 0;int sb = 0;Term *cur = new Term[maxsum];int k = 0;while (sa < sum || sb < b.sum){if (t[sa].col == b.t[sb].col&&t[sa].row == b.t[sb].row){cur[k].col = t[sa].col;cur[k].row = t[sa].row;cur[k].value = t[sa].value + b.t[sb].value;k++;sa++;sb++;}else if (t[sa].row < b.t[sb].row){cur[k].value = t[sa].value;cur[k].row = t[sa].row;cur[k].col = t[sa].col;k++;sa++;}else if (t[sa].row > b.t[sb].row){cur[k].value = b.t[sb].value;cur[k].row = b.t[sb].row;cur[k].col = b.t[sb].col;k++;sb++;}else if (t[sa].col < t[sb].col){cur[k].col = t[sa].col;cur[k].row = t[sa].row;cur[k].value = t[sa].value;k++;sa++;}else{cur[k].value = b.t[sb].value;cur[k].row = b.t[sb].row;cur[k].col = b.t[sb].col;k++;sb++;}}sum = k;delete t;t = cur;return;}Term.h#pragma onceclass Term{friend class SparseMatrix;private:int col, row;int value;};Term.cpp#include"Term.h"TridiagonalMatrix.h#pragma onceclass TridiagonalMatrix{public:TridiagonalMatrix(int size);void Store(int x, int i, int j);//向矩阵里存储一个元素int Retrieve(int i, int j);//返回矩阵中的一个元素void print();private:int n;//矩阵非0元素个数int *t;//用数组来存储矩阵};TridiagonalMatrix.cpp#include"TridiagonalMatrix.h"#include<iostream>using namespace std;TridiagonalMatrix::TridiagonalMatrix(int size){n = size;t = new int[3 * n - 2];}void TridiagonalMatrix::Store(int x, int i, int j){if (i<0 || j<0 || i >= n || j >= n){cout << "三对角矩阵行列输入错误" << i << " " << j << endl;return;}else if (x == 0){cout << "三对角矩阵所添加的元素必须非零" << endl;return;}else if (abs(i - j)>1){cout << "三对角矩阵添加元素位置错误" << endl;return;}switch (i - j){case -1:t[3 * j - 1] = x;break;case 0:t[3 * j] = x;break;case 1:t[3 * j + 1] = x;break;}return;int TridiagonalMatrix::Retrieve(int i, int j){if (i<0 || j<0 || i >= (n - 1) || j >= (n - 1)) {cout << "三对角矩阵行列输入错误" << endl;return -1;}else if (abs(i - j) <= 1){return t[3 * j + (i - j)];}else{return 0;}}void TridiagonalMatrix::print(){for (int i = 0; i < 3 * n - 2; i++){cout << t[i] << " ";}cout << endl;return;}Test.cpp#include<iostream>#include<cstring>#include<cstdlib>#include"TridiagonalMatrix.h"#include"LowerTriangularMatrix.h"#include"SparseMatrix.h"#include"HashTable.h"#include"ChainHashTable.h"using namespace std;int wei, num[100][100];void c(){for (int i = 0; i < wei; i++)for (int j = 0; j < wei; j++)cin >> num[i][j];}int main(){int k = 0, l = 0;/*三对角矩阵实验开始测试数据4~10~3n-241 2 0 03 4 5 00 7 8 90 0 8 7*/cout << "请输入三对焦矩阵维数及内容：" << endl;cin >> wei;c();TridiagonalMatrix *TM = new TridiagonalMatrix(wei);for (int i = 0; i < wei; i++)for (int j = 0; j < wei; j++)if (num[j][i] != 0)TM->Store(num[j][i], j, i);TM->print();cout << "请输入要查询的元素的位置" << endl;cin >> k >> l;l = TM->Retrieve(k, l);cout << "查询结果：" << l << endl;cout << "***********************************************" << endl;/*下三角矩阵实验开始测试数据4~10~n*(n+1)/241 0 0 02 3 0 04 5 6 07 8 9 -1*/cout << "请输入下三角矩阵维数及内容：" << endl;k = 0, l = 0;cin >> wei;c();LowerTriangularMatrix *LTM = new LowerTriangularMatrix(wei);for (int i = 0; i < wei; i++)for (int j = 0; j < wei; j++)if (num[j][i] != 0)LTM->Store(num[j][i], j, i);cout << "请输入要查询的元素的位置" << endl;cin >> k >> l;l = LTM->Retrieve(k, l);cout << "查询结果：" << l << endl;cout << "***********************************************" << endl;/*稀疏角矩阵实验开始测试数据4 54 51 0 0 0 20 3 0 0 04 0 05 00 6 7 0 84 58 0 7 6 00 5 0 0 40 0 0 3 02 0 0 0 19 0 7 6 20 8 0 0 44 0 0 8 02 6 7 0 9*/cout << "请输入稀疏矩阵的维数及内容：" << endl;cin >> k >> l;SparseMatrix *SM = new SparseMatrix(k, l);for (int i = 0; i < k; i++)for (int j = 0; j < l; j++){cin >> num[i][j];if (num[i][j])SM->Store(num[i][j], i, j);}cout << "稀疏矩阵为： ";SM->print();SM->transpose();cout << "转置后稀疏矩阵为： ";SM->print();SM->transpose();cout << "重新转置后稀疏矩阵为： ";cout << "矩阵相加开始，请输入要使用的矩阵维数及内容:" << endl;cin >> k >> l;SparseMatrix *SM2 = new SparseMatrix(k, l);for (int i = 0; i < k; i++)for (int j = 0; j < l; j++){cin >> num[i][j];if (num[i][j])SM2->Store(num[i][j], i, j);}cout << "新矩阵为： ";SM2->print();SM->Add(*SM2);cout << "矩阵相加后为： ";SM->print();cout << "***********************************************" << endl;cin.get();system("pause");/*使用散列表设计实现一个字典，假设关键字为整数且D为961，在字典中插入随机产生的500个不同的整数，实现字典的建立和搜索操作。
数据结构实验题⽬实验⼀线性表1 实验⽬的通过选择下⾯四个题⽬之⼀进⾏实现，掌握如下内容：熟悉C++语⾔的基本编程⽅法，掌握集成编译环境的调试⽅法学习指针、模板类、异常处理的使⽤掌握线性表的操作的实现⽅法学习使⽤线性表解决实际问题的能⼒2 实验内容2.1题⽬1根据线性表的抽象数据类型的定义，选择下⾯任⼀种链式结构实现线性表，并完成线性表的基本功能。
线性表存储结构（五选⼀）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使⽤头插法、尾插法两种⽅法2、插⼊：要求建⽴的链表按照关键字从⼩到⼤有序3、删除4、查找5、获取链表长度6、销毁7、其他：可⾃⾏定义编写测试main()函数测试线性表的正确性。
2.2题⽬2利⽤线性表实现⼀个通讯录管理，通信录的数据格式如下：struct DataType{int ID; //编号char name[10]; //姓名char ch; //性别char phone[13]; //电话char addr[31]; //地址};要求：实现通讯录的建⽴、增加、删除、修改、查询等功能能够实现简单的菜单交互，即可以根据⽤户输⼊的命令，选择不同的操作。
能够保存每次更新的数据（选作）能够进⾏通讯录分类，⽐如班级类、好友类、⿊名单等等（选作）编写测试main()函数测试线性表的正确性2.3题⽬3利⽤线性表实现⼀个⼀元多项式Polynomialf(x) = a+ a1x + a2x2 + a3x3+ … + a n x n提⽰：Polynomial的结点结构如下：struct term{float coef; //系数int expn; //指数};可以使⽤链表实现，也可以使⽤顺序表实现。
要求：能够实现⼀元多项式的输⼊和输出能够进⾏⼀元多项式相加能够进⾏⼀元多项式相减能够计算⼀元多项式在x处的值能够计算⼀元多项式的导数（选作）能够进⾏⼀元多项式相乘（选作）编写测试main()函数测试线性表的正确性2.4题⽬4利⽤循环链表实现约瑟夫问题的求解。
2014年《数据结构》课程设计题目表1 设计程序按从大到小的次序依次输出函数f(a,b)=2×a2+b2的最小的100个函数值及相应的两个参数的值，其中a和b均为自然数。
要求：（1）作为函数值的存储结构应尽可能节省空间。
（2）所设计算法及整个程序的时间复杂度应尽可能小。
2 设计程序以实现任意两个高次多项式的乘法运算。
要求：（1）所设计的数据结构应尽可能节省存储空间。
（2）程序的运行时间应尽可能小。
3 设计一个模拟计算器的程序，要求对包括加、减、乘、除、括号运算符及SQR和ABS函数的任意整型表达式进行求解。
4 采用十字链表表示稀疏矩阵，并实现矩阵的加法运算。
要求：要检查有关运算的条件，并对错误的条件产生报警。
5采用十字链表表示稀疏矩阵，并实现矩阵的乘法运算。
要求：要检查有关运算的条件，并对错误的条件产生报警。
6（2人）选择合适的存储结构表示广义表，并实现下列运算要求：（1）用大写字母表示广义表，用小写字母表示原子，并提供设置广义表的值的功能。
（2）取广义表L的表头和表尾的函数head(L)和tail(L)。
（3）能用这两个函数的复合形式求出广义表中的指定元素。
（4）由广义表的字符串形式到广义表的转换函数Str-To-List(S):Lists,例如Str-To-Lists(‘(a,(a,b),c)’)的值为一个广义表。
（5）由广义表到广义表的字符串形式转换函数Lists-To-Str(L):String。
（6）最好能设置多个广义表。
7 设计程序实现哈夫曼算法，要求如下：（1）可以利用实验工具的有关功能。
（2）要能演示构造过程。
8 采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。
要求：（1）压缩原文件的规模应不小于5K。
（2）提供恢复文件与原文件的相同性对比功能。
9设计程序完成如下功能：对给定的图结构和起点，产生所有的深度优先搜索遍历序列，并给出求解过程的动态演示。
[大型实验基本要求]
1.原则上可以1－３位同学组成实验小组，进行分工合作，但必需保证每位组员都充分参
与实验过程，每位组员应对实验程序的结构、算法、主要技术完全掌握，方可参加实验验收。
但一个小组内最终只能一个人得到优秀成绩。
2.每组可参考下面大型实验题目和要求，选择一道实验题目，共同设计开发。
3.大型实验时间从第8周开始至16周，要求在考试之前全部验收结束。
原则上，申请大
型实验验收后，若实验没有达到规定的要求，不可再次申请验收，故请大家务必确认程序正确（程序代码和运行结果）后，再申请验收。
[报告规范]
实习报告的开头应该给出题目、班级、姓名、学号、和完成日期，如果是多人完成的，必须写明所有同组人员的班级、姓名和学号，并标明谁是主要负责人，其它为参与者。
实验报告要求有以下五个内容：
1．实验内容分析：明确实验题目目的，设计实验的基本数据结构、类、以及程序的基本流程，程序流程要求以程序流程图明确表示，类及类间关系需明确图示，并给出各函数之间的调用关系。
可以适当粘贴关键代码进行说明；
2．实验验证分析：
（1）输入的形式和输入值的范围；
（2）输出的形式；
（3）程序所能达到的功能；
（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。
３．调试分析
（1）讨论分析调试过程中的主要技术问题以及具体的解决方法（至少３个）；
（2）技术难点分析（至少３个）；
（3）印象最深刻的３个调试错误，及修正方法；
４．测试结果：
（1）展示程序的运行结果，包括输入和输出，分析数据的正确性；
（2）应用边界数据、或极端数据测试系统，分析结果的正确性。
５．附录：附上源代码，并标明源代码的所属文件，并且源代码必须有注释。
[提交内容]
1.电子压缩包：包括实验报告电子稿和所有源代码文件(包括.h文件和.cpp文件)。
2.压缩文件名为：“学号+姓名”；如果是多人合作的，则压缩文件名为：“负责人学号+
负责人姓名+参与者1学号+参与者1姓名+参与者2学号+参与者2姓名”。
[考核方式]
1．以小组方式进行面试，教师提问，结合工作分工和系统完成情况评分。
2．小组内只能一人得优。
[题目]
一、 用户登录系统的模拟
【问题描述】在登录服务器系统时，都需要验证用户名和密码，如telnet远程登录服务器。
用户输入用户名和密码后，服务器程序会首先验证用户信息的合法性。
由于用户信息的验证频率很高，系统有必要有效地组织这些用户信息，从而快速查找和验证用户。
另外，系统也会经常会添加新用户、删除老用户和更新用户密码等操作，因此，系统必须采用动态结构，在添加、删除或更新后，依然能保证验证过程的快速。
请采用相应的数据结构模拟用户登录系统，其功能要求包括用户登录、用户密码更新、用户添加和用户删除等。
【基本要求】
1.要求自己编程实现二叉树结构及其相关功能，以存储用户信息，不允许使用标准模板类
的二叉树结构和函数。
同时要求根据二叉树的变化情况，进行相应的平衡操作，即A VL 平衡树操作，四种平衡操作都必须考虑。
测试时，各种情况都需要测试，并附上测试截图；
2.要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。
主函数中只
能出现类的成员函数的调用，不允许出现对其它函数的调用。
3.要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存
储在另外一个单独的cpp文件中。
如果采用类模板，则类的声明和实现都放在.h文件中。
4.要求源程序中有相应注释；
5.不强制要求采用类模板，也不要求采用可视化窗口；
6.要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表
明各个功能的执行正确；
7.要求采用Visual C++ 6.0及以上版本进行调试；
【实现提示】
1.用户信息(即用户名和密码)可以存储在文件中，当程序启动时，从文件中读取所有的用
户信息，并建立合适的查找二叉树；
2.验证过程时，需要根据登录的用户名，检索整个二叉树，找到匹配的用户名，进行验证；
更新用户密码时，也需要检索二叉树，找到匹配项后进行更新，同时更新文件中存储的用户密码。
3.添加用户时，不仅需要在文件中添加，也需要在二叉树中添加相应的节点；删除用户时，
也是如此；
【运行结果要求】要求能够实现用户登录验证、添加用户、删除用户和更新用户密码功能，实验报告要求有详细的功能测试截图。
【考核要求】要求程序能正常运行，全面完成题目要求。
【题目难度】难，成绩等级高
二、 优先级作业调度系统的模拟
【问题描述】Windows、Linux等操作系统都支持同时运行多个作业，但作业的执行顺序却因调度算法的不同而不同。
通常，操作系统都采用优先级作业调度，即操作系统根据作业的长短来设置优先级大小，优先级高的作业先执行，优先级低的作业后执行。
作业调度的详细情况如下描述：
一个作业J i的长度为t i =（s i，e i），s i为作业运行的开始时间（进入时间），e i为作业运行的结束时间（离开时间），t i则为完成作业J i所需要的执行时间（单位：秒）。
作业调度的基本任务是从作业队列中选取一个来执行，如果没有作业则执行空操作操作。
而优先级作业调度，是指每次选取优先级最高的作业来调度，优先级可以用优先数（每个作业一个优先数p i）来表示，优先数越小，优先级越高。
作业J i进入系统时，即s i时刻，系统给该作业指定其初始优先数p i = t i，从而使越短的作业优先级越高。
该优先数在作业等待调度执行的过程中会不断减小，调整公式为：p i = p i - w i，其中w i为作业J i的等待时间：w i = 当前时间-s i。
一旦作业被调度，该作业就一直执行，不能被抢占，只有当前执行的作业完成时，才产生下一轮调度。
所以需要在每次调度前动态调整各作业的优先数。
在每次调度的时候，如果出现相同优先级的作业，则按照先进先出(FIFO: First In First Out)的原则进行调度。
【基本要求】
1.要求自己编程实现堆结构及其相关功能，从而实现优先级队列，不允许使用标准模板类
的堆函数和优先级队列；测试时，各种情况都需要测试，并附上测试截图；
2.要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。
主函数中只
能出现类的成员函数的调用，不允许出现对其它函数的调用。
3.要求采用多文件方式：.h文件存储类的声明，.cpp文件存储类的实现，主函数main存
储在另外一个单独的cpp文件中。
如果采用类模板，则类的声明和实现都放在.h文件中。
4.要求源程序中有相应注释；
5.不强制要求采用类模板，也不要求采用可视化窗口；
6.要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表
明各个功能的执行正确，包括何时作业进入，何时调度哪个作业，何时离开，每个作业等待多长时间，优先数的动态变化情况等；
7.要求采用Visual C++ 6.0及以上版本进行调试；
【实现提示】
1.优先级队列可以采用最小堆来实现；
2.作业长度，即完成时间，可以用随机的方式产生，并由此设定各个作业的初始优先级；
3.可以在一轮调度的间隙随机地插入一定数量的作业，保证队列不会长时间空闲，也不会
太长。
4.优先级队列要求完成主要的功能，包括作业的插入、最小优先级作业的提取和删除、各
个作业优先级的修改等；
5.作业的执行过程，可以调用sleep函数来模拟；
【考核要求】要求程序能正常运行，全面完成题目要求，实现各项主要功能。
实验报告要求有详细的功能测试截图。
【题目难度】次难，成绩等级次高。
