当前位置：文档之家 › 大连理工大学数据结构(一)上机作业答案——张老师

大连理工大学数据结构(一)上机作业答案——张老师

  • 格式：doc
  • 大小：68.50 KB
  • 文档页数：12

下载文档原格式

  / 12

合集下载

大连理工19秋《数据结构》在线作业1答案

大连理工19秋《数据结构》在线作业1答案

【奥鹏】大工19秋《数据结构》在线作业1
试卷总分:100 得分:100
一、单选题 (共 10 道试题,共 50 分)
第1题，线性表采用顺序存储结构时,其地址 ( )。

[A.]部分地址必须是连续的
[B.]连续与否均可以
[C.]必须是连续的
[D.]一定是不连续的
正确的答案是:C
第2题，队列操作的原则是( )。

[A.]后进先出
[B.]只能插入
[C.]只能删除
[D.]先进先出
正确的答案是:D
第3题，下述哪一条是顺序存储结构的优点( )。

[A.]插入运算方便
[B.]存储密度大
[C.]可方便地用于各种逻辑结构的存储表示
[D.]删除运算方便
正确的答案是:B
第4题，若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。

[A.]顺序表
[B.]带头结点的双循环链表
[C.]双链表
[D.]单循环链表
正确的答案是:A
第5题，链表不具有的特点是( )。

[A.]插入、删除不需要移动元素
[B.]所需空间与线性长度成正比
[C.]可随机访问任一元素
[D.]不必事先估计存储空间
正确的答案是:C
第6题，一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是( )。

[A.]不确定
[B.]n-i+1。

最新大连理工大学数据结构(一)上机作业答案——张老师

最新大连理工大学数据结构(一)上机作业答案——张老师
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n){
s->data=m;
s->next=NULL;
p->next=s;
}
}
void ReverseList(LinkList &L){
LNode *p,*q;
if(L->next&&L->next->next){
p=L->next;
q=p->next;
p->next=NULL;
while(q){
p=q;
typedef int Status;
#define LIST_INIT_SIZE 100
#define LISTTINCREMENT 10
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//创建空顺序表
Status InitList_Sq(SqList &L){
1．将顺序表逆置，要求用最少的附加空间。
参考答案
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0

数据结构完整题目及答案1

数据结构完整题目及答案1

数据结构与算法实验报告目录实验一学生成绩分析程序 (4)1.1 上机实验的问题和要求（需求分析）： (4)1.2 程序设计的基本思想，原理和算法描述： (4)1.3 调试和运行程序过程中产生的问题及采取的措施： (4)1.4 运行输出结果： (4)1.5 源程序及注释： (5)实验二线性表的基本操作 (8)2.1 上机实验的问题和要求（需求分析）： (8)2.2 程序设计的基本思想，原理和算法描述： (8)2.3 调试和运行程序过程中产生的问题及采取的措施： (8)2.4 运行输出结果： (8)2.5 源程序及注释： (8)实验三链表的基本操作 (11)3.1 上机实验的问题和要求（需求分析）： (11)3.2 程序设计的基本思想，原理和算法描述： (11)3.3 调试和运行程序过程中产生的问题及采取的措施： (11)3.4 运行输出结果： (11)3.5 源程序及注释： (11)实验四单链表综合实验 (14)4.1 上机实验的问题和要求（需求分析）： (14)4.2 程序设计的基本思想，原理和算法描述： (14)4.3 调试和运行程序过程中产生的问题及采取的措施： (14)4.4 运行输出结果： (14)4.5 源程序及注释： (14)实验五串 (19)5.1 上机实验的问题和要求（需求分析）： (19)5.2 程序设计的基本思想，原理和算法描述： (19)5.3 调试和运行程序过程中产生的问题及采取的措施： (19)5.4 运行输出结果： (19)5.5 源程序及注释： (21)实验六循环队列的实现与运算 (22)6.1 上机实验的问题和要求（需求分析）： (22)6.2 程序设计的基本思想，原理和算法描述： (22)6.3 调试和运行程序过程中产生的问题及采取的措施： (22)6.4 运行输出结果： (22)6.5 源程序及注释： (23)实验七栈子系统 (26)7.1 上机实验的问题和要求（需求分析）： (26)7.2 程序设计的基本思想，原理和算法描述： (26)7.3 调试和运行程序过程中产生的问题及采取的措施： (26)7.4 运行输出结果： (26)7.5 源程序及注释： (28)实验八树 (36)8.1 上机实验的问题和要求（需求分析）： (36)8.2 程序设计的基本思想，原理和算法描述： (39)8.3 调试和运行程序过程中产生的问题及采取的措施： (39)8.4 运行输出结果： (39)8.5 源程序及注释： (41)实验九建立哈夫曼树与哈夫曼树与码 (50)9.1 上机实验的问题和要求（需求分析）： (50)9.2 程序设计的基本思想，原理和算法描述： (50)9.3 调试和运行程序过程中产生的问题及采取的措施： (50)9.4 运行输出结果： (50)9.5 源程序及注释： (50)实验十图 (53)10.1 上机实验的问题和要求（需求分析）： (53)10.2 程序设计的基本思想，原理和算法描述： (53)10.3 调试和运行程序过程中产生的问题及采取的措施： (53)10.4 运行输出结果： (53)10.5 源程序及注释： (53)实验一学生成绩分析程序一、上机实验的问题和要求（需求分析）：【题目】设一个班有10个学生，每个学生有学号，以及数学、物理、英语、语文、体育 5 门课的成绩信息。

数据结构 张铭 习题

数据结构 张铭 习题

第一章概论练习答案上一章下一章本章练习题答案分页： [1] [2]1、解答：【题意解析】本题指定了字符的顺序，所以不能按照ASCII字符顺序来排序。

【典型错误】1.不按照题目给出的字符顺序进行排序，而按照ASCII字符顺序。

2.没有给出排序结果3.认为顺序存储法比较节约空间，事实上由于字符空隙，顺序法并不节约空间；4. 没有比较各种方法的优劣。

【数据结构】本题可以采用的存储结构有顺序（数组）和链表。

1. 用二维数组array[NUMOFSTRING][MAX_LENGTH]，此题可定义const int优点:为紧凑存储结构，没有用于存储其他附加的信息，表示方法比较直观简单，代码实现十分容易。

缺点:为每个但此都开辟了同样长度的空间,造成空间的浪费。

2. 用链表的结构存储，结点为结构struct strings{char string[MAX_LENGTH];strings *pNext;}优点:如果有后续工作如反复增删结点,效率很高.并且可以使用不连续的空间。

缺点:操作过程相对复杂,容易出错.而且排序过程需要从表头开始沿链索一个结点一个结点的比较搜索,相当费时。

3. 索引存储是顺序存储的一种推广.使用一个字符串char data[500],其中将大小长度不等的数据结点(单词)顺序存储其中.令使用一个字符指针数组 char* index[n],存储一系列指针,每个指针指向存储区域的一个数据结点.排序时,直接对index中的地址值进行调换修改即可,而不用修改data中的任何内容。

索引存储的优点是:由于单词长度不同,在存储时充分考虑了这个因素,可以节省空间,此外由于交换的不是单词本身而是单词的地址,可以节省时间,从时空两方面得到了优化。

【排序结果】B899，B9，CRSI，CXY，PAB，PABC，5C，72、解答：【题意解析】本题没有指明这100个实数是否存在相等的情况，在这里，我们考虑存在多个最大值的情形（即100个实数可能有相等的），为了保存其位置，利用int pos[100]（因为有可能这100个实数都是相同的）来保存最大值的所有位置。

大连理工大学数据结构试题及答案

大连理工大学数据结构试题及答案

数据结构期末试卷一、选择题1．组成数据的基本单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（）的逻辑结构。

(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（）个。

(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

大连理工大学《数据结构》作业 参考答案

大连理工大学《数据结构》作业 参考答案
u=q->link; q->link=L->link; L->link=q; q=u; } }
数据结构作业参考答案
//有序表插入 void yxcharu(LinkList &L, ElemType e) {
LinkList pre,p,s; pre=L; p=L->link; while(p&&p->data<e) {
pre=p; p=p->link; } s=(LinkList)malloc(sizeof(Lnode)); s->data=e; s->link=p; pre->link=s; }
main()
{
LinkList L;
int n,i,mink,maxk;
ElemType e;
char choice='0';
数据结构作业参考答案
if(InitList_Sq(L)) {
printf("建立空顺序表成功！\n"); do{
printf("当前线性表长度为：%d\n",L.length); printf("请输入要插入元素的位置："); scanf("%d",&i); printf("请输入要插入的元素值："); scanf("%d",&k); if(sxbcr(L,i,k)) {
s=(LinkList)malloc(sizeof(Lnode));
scanf("%d",&s->data); s->link=NULL;
p->link=s;
p=s;

[大连理工大学]20春《数据结构》在线作业2-复习资料答案

[大连理工大学]20春《数据结构》在线作业2-复习资料答案

[大连理工大学]20春《数据结构》在线作业2-复习资料答案
科目名称：大工20春《数据结构》在线作业2
学校名称：奥鹏-大连理工大学
一、单选题 (共 10 道试题,共 50 分)
1.树最适合用来表示( )。

A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
提示：本题为必答题，请认真阅读题目后再作答
--本题参考答案：C
2.假定一棵度为3的树中结点总数为50,则其最小高度为( )。

A.3
B.4
C.5
D.6
提示：本题为必答题，请认真阅读题目后再作答
--本题参考答案：C
3.一棵二叉树中有35个结点,其中所有结点的度之和是( )。

A.16
B.33
C.34
D.35
提示：本题为必答题，请认真阅读题目后再作答
--本题参考答案：C
4.一棵高度为8的完全二叉树至少有( )叶子结点。

A.63
B.64
C.127
D.128
提示：本题为必答题，请认真阅读题目后再作答
--本题参考答案：B
5.某二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树一定是( )。

A.空
B.完全二叉树
C.二叉排序树
D.高度等于其结点数
提示：本题为必答题，请认真阅读题目后再作答
--本题参考答案：D。

数据结构上机考试(含答案)

数据结构上机考试(含答案)

《数据结构》上机练习题1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。

2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。

3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。

4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。

5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。

10、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。

11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。

12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。

13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。

14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。

15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。

16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。

17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。

18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。

19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。

大连理工大学数据结构(一)上机作业答案——张老师

大连理工大学数据结构(一)上机作业答案——张老师
#define OVERFLOW -2
typedef int ElemType;
typedef int Status;
#define LIST_INIT_SIZE 100
#define LISTTINCREMENT 10
typedef struct{
ElemType *elem;
int length;
for(i=0;i<n;i++)
{
printf("input elem:");
scanf("%d",&L.elem[i]);
}
}
//输出顺序表中的元素
void ListOutput_Sq(SqList L){
int i,n;
n=L.length;
for(i=0;i<n;i++)
printf("%2d",L.elem[i]);
else
return -2;
}//优先级比较
void transform(char suffix[], char exp[])
{
char *p, ch, c;
p = exp;
ch = *p;
SqStack S;
InitStack (S);
Push (S, '#');
while(!StackEmpty(S))
}
}
}
void DeleteList(LinkList &L,ElemType mink,ElemType maxk){
LNode *p=L,*q;
while(p->next&&p->next->data<=mink)

大连理工大学22春“计算机科学与技术”《数据结构》作业考核题库高频考点版(参考答案)试题号1

大连理工大学22春“计算机科学与技术”《数据结构》作业考核题库高频考点版(参考答案)试题号1

大连理工大学22春“计算机科学与技术”《数据结构》作业考核题库高频考点版（参考答案）一.综合考核(共50题)1.已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为()。

A.CBEFDAB.FEDCBAC.CBEDFAD.不定参考答案：A2.顺序存储方法，它不要求逻辑上相邻的结点在物理位置上亦相邻，结点之间的逻辑关系是由附加的指针字段表示的。

()A.正确B.错误参考答案：B3.队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。

()A.正确B.错误参考答案：A4.在二叉查找树中，新插入的关键码总是处于最底层。

()A.正确B.错误参考答案：BA.冒泡B.希尔C.快速D.堆参考答案：C6.栈和队列具有相同的()。

A.逻辑结构B.存储结构C.存取点D.运算参考答案：A7.有向图的邻接矩阵是对称的。

()A.正确B.错误参考答案：A8.在二叉树的先序遍历序列中，任一结点均处在其子树结点前面。

()A.正确B.错误参考答案：A9.以下()方法在数据基本有序时效率最好。

A.快速排序B.冒泡排序C.堆排序D.希尔排序10.一棵满二叉树共有64个叶子结点，则其深度为()。

A.4B.6C.7D.8参考答案：C11.在链式存储中所有结点之间的存储地址可连续也可不连续。

()A.正确B.错误参考答案：A12.完全二叉树中，若一个结点没有左孩子，则它必是树叶。

()A.正确B.错误参考答案：A13.算法的有穷性是指一个算法必须总是(对任何合法的输入)在执行有穷步之后结束，且每一步都可在有穷时间内完成。

()A.正确B.错误参考答案：A14.一棵二叉树中有35个结点，其中所有结点的度之和是()。

A.16B.33参考答案：C15.设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。

A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈参考答案：D16.堆是满二叉树。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
int i,n;
n=L.length;
for(i=0;i<n;i++)
printf("%2d",L.elem[i]);
}
//顺序表逆置
void ReverseList_Sq(SqList &L){
int i,n;
ElemType p;
n=L.length;
for(i=0;i<n/2;i++)
{
p=L.elem[i];
p++;
*p = '\0';
} //将字符串结尾附成\0
int Precede(char c)
{
if (c == '*' || c == '/')
return 2;
if (c == '+' || c == '-')
return 1;
if (c == '(' || c == ')')
return -1;
L.elem[i]=L.elem[n-i-1];
L.elem[n-i-1]=p;
}
}
void main(){
SqList L;
InitList_Sq(L);
ListInput_Sq(L);
ListOutput_Sq(L);
ReverseList_Sq(L);
printf("\n");
printf("输出结果为：");
printf("建立单链表请按1.\n");
printf("显示单链表请按2.\n");
printf("有序插入新元素请按3.\n");
printf("单链表就地逆置请按4.\n");
printf("删除大于mink且小于maxk的所有元素请按5.\n");
printf("退出请按0.\n");
printf("*********************************\n");
ListOutput_Sq(L);
printf("\n");
}
2．从键盘读入n个整数（升序），请编写算法实现：
（1）CreateList()：建立带表头结点的单链表；
（2）PrintList()：显示单链表，（形如：H->10->20->30->40）;
（3）InsertList()：在有序单链表中插入元素x；
int n,i;
printf("input the length of Sqlist:");
scanf("%d",&n);
L.length=n;
for(i=0;i<n;i++)
{
printf("input elem:");
scanf("%d",&L.elem[i]);
}
}
//输出顺序表中的元素
void ListOutput_Sq(SqList L){
scanf("%d",&e);
InsertList(L,e);
PrintList(L);
break;
case 4:
printf("要执行本操作请先建立单链表，请输入单链表中的节点个数：");
scanf("%d",&n);
CreateList(L,n);
printf("单链表逆置：");
ReverseList(L);
PrintList(L);
break;
}
}while(number!=0);}
第二次作业
栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。
例如，输入表达式：a+b/c-(d*e+f)*g
输出其后缀表达式：abc/+de*f+g*-
参考答案：
#include<stdio.h>
#include<stdlib.h>
#define ERROR 0
typedef int ElemType;
typedef int Status;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n){
typedef int Status;
#define LIST_INIT_SIZE 100
#define LISTTINCREMENT 10
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//创建空顺序表
Status InitList_Sq(SqList &L){
q=p;
while(q&&q->data<maxk)
q=q->next;
p->next=q;
}
void main(){
LinkList L;
int n,number;
ElemType e,mink,maxk;
do{
printf("*********************************\n");
PrintList(L);
break;
case 5:
printf("要执行本操作请先建立单链表，请输入单链表中的节点个数：");
scanf("%d",&n);
CreateList(L,n);
printf("请输入mink和maxk：");
scanf("%d%d",&mink,&maxk);
DeleteList(L,mink,maxk);
void add(char exp[])
{
char *p;
p = exp;
while (*p != '\0')
++p;
*p = '#';
*(p + 1) = '\0';
}//在表达式结尾加结束符
void del(char suffix[])
{
char *p;
p = suffix;
while (*p != '#')
typedef char SElemType;
typedef char ElemType;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;//定义结构
int InitStack(SqStack&S){
S.base=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L.elem)exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
//创建顺序表，插入元素
void ListInput_Sq(SqList &L){
int i;
LNode *p,*q;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
q=L;
printf("请输入所要建立的单链表所包含的元素：");
for(i=0;i<n;i++){
p=(LinkList)malloc(sizeof(LNode));
scanf("%d",&p->data);
q=q->next;
p->next=L->next;
L->next=p;
}
}
}
void DeleteList(LinkList &L,ElemType mink,ElemType maxk){
LNode *p=L,*q;
while(p->next&&p->next->data<=mink)
p=p->next;
1．将顺序表逆置，要求用最少的附加空间。
参考答案
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int ElemType;
LNode *p,*q,*s;
p=L;
q=L->next;
while(q&&q->data<m){
p=q;
q=q->next;
}
if(q){