下载文档原格式
【奥鹏】大工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。
数据结构作业答案(大连理工大学)数据结构作业答案入栈和出栈操作是栈这种数据结构最基本的操作，也是我们在日常生活中常常会用到的操作。
本文将为您介绍如何使用Python实现栈的数据结构，以及解答大连理工大学数据结构作业中与栈相关的问题。
一、栈的概念和基本操作栈是一种具有特殊限制的线性表，它只允许在表的一端进行插入和删除操作。
栈遵循先进后出（Last In First Out，LIFO）的原则。
通常，栈顶为允许插入和删除的一端，而另一端则称为栈底。
1.1 栈的初始化在Python中，我们可以使用列表(list)来实现栈的数据结构。
下面的代码演示了如何初始化一个栈：```pythonstack = []```1.2 入栈操作入栈操作是将一个元素添加到栈顶的操作。
在Python中，我们可以使用列表的append()方法来实现入栈操作。
下面的代码演示了如何进行入栈操作：```pythonstack.append(element)```1.3 出栈操作出栈操作是将栈顶元素删除并返回的操作。
在Python中，我们可以使用列表的pop()方法来实现出栈操作。
下面的代码演示了如何进行出栈操作：```pythonelement = stack.pop()```二、栈的应用举例2.1 判断括号匹配一个常见的栈的应用是判断括号是否匹配。
在这个问题中，我们需要使用栈来跟踪括号的开闭情况。
具体的算法如下：①初始化一个空栈。
②遍历字符串中的每个字符。
③如果遇到开括号（例如：'('、'{'、'['），则将其入栈。
④如果遇到闭括号（例如：')'、'}'、']'），则判断栈顶元素是否为相应的开括号，如果不匹配，则返回False。
⑤字符串遍历完成后，如果栈为空，则说明所有括号都匹配，返回True；否则，返回False。
下面是一个基于栈的括号匹配问题的示例代码：```pythondef is_valid_parentheses(s: str) -> bool:stack = []parentheses_map = {')': '(', '}': '{', ']': '['}for char in s:if char in parentheses_map.values():stack.append(char)elif char in parentheses_map.keys():if not stack or parentheses_map[char] != stack.pop():return Falsereturn not stack```2.2 栈的逆序输出另一个栈的常见应用是逆序输出。
大工19秋《数据结构》在线作业1试卷总分:100 得分:100一、单选题(共10 道试题,共50 分)1.线性表采用顺序存储结构时,其地址( )。
A.部分地址必须是连续的B.连续与否均可以C.必须是连续的D.一定是不连续的答案:C2.队列操作的原则是( )。
A.后进先出B.只能插入C.只能删除D.先进先出答案:D3.下述哪一条是顺序存储结构的优点( )。
A.插入运算方便B.存储密度大C.可方便地用于各种逻辑结构的存储表示D.删除运算方便答案:B4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用( )存储方式最节省时间。
A.顺序表B.带头结点的双循环链表C.双链表D.单循环链表答案:A5.链表不具有的特点是( )。
A.插入、删除不需要移动元素B.所需空间与线性长度成正比C.可随机访问任一元素D.不必事先估计存储空间答案:C6.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是( )。
A.不确定B.n-i+1C.n-iD.i答案:B7.设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的出栈排列是( )。
A.ZYXB.ZXYC.YZXD.XYZ答案:B8.一个递归算法必须包括( )。
A.递归部分B.迭代部分C.终止条件和递归部分D.终止条件和迭代部分答案:C9.设计一个判别表达式中左右括号是否配对出现的算法,采用( )数据结构最佳。
A.队列B.线性表的顺序存储结构C.线性表的链式存储结构D.栈答案:D10.对稀疏矩阵进行压缩存储目的是( )。
A.降低运算的时间复杂度B.节省存储空间C.便于进行矩阵运算D.便于输入和输出答案:B二、判断题(共10 道试题,共50 分)11.数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
答案:正确12.算法的有穷性是指一个算法必须总是(对任何合法的输入)在执行有穷步之后结束,且每一步都可在有穷时间内完成。
大连理工大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
()A.正确B.错误参考答案：A2.以下()方法在数据基本有序时效率最好。
A.快速排序B.冒泡排序C.堆排序D.希尔排序参考答案：B3.堆是满二叉树。
()A.正确B.错误参考答案：A4.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是()排序。
A.冒泡B.希尔C.快速D.堆参考答案：C在二叉查找树中，新结点总是作为叶结点插入。
()A.正确B.错误参考答案：A6.链表不具有的特点是()。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比参考答案：B7.在中序线索二叉树中，每个非根结点的非空线索都指向该结点的某个祖先结点。
()A.正确B.错误参考答案：A8.链式存储方法，它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点的逻辑关系由存储单元的邻接关系来体现。
()A.正确B.错误参考答案：B9.串的长度是指()。
A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数10.具有10个叶结点的二叉树中有()个度为2的结点。
A.8B.9C.10D.11参考答案：B11.顺序表的主要缺点是实现线性表的插入或删除可能移动很多元素。
()A.正确B.错误参考答案：A12.在后序线索二叉树中，后序下的第一个结点一定是最左下的结点。
()A.正确B.错误参考答案：B13.同一个算法，实现语言级别越高，算法执行的效率越低。
()A.正确B.错误参考答案：A14.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是()。
A.9B.11C.15参考答案：B15.顺序存储方法，它不要求逻辑上相邻的结点在物理位置上亦相邻，结点之间的逻辑关系是由附加的指针字段表示的。
《数据结构》作业参考答案一、选择题 1． a b 2． c 3． b 4． a,d 5． b 6． d 7． b 8．D 9．D 10．B 11．C 12．C 13． c 14．d 15．a 16．b 17．c18．d 19．c 20．b 21．b 22．c 23．c 24．d 25．d 26．c二、填空题 1．j i i ++2)1( 2．3 43． 2k-1, 2k -1, 2k-2+14． v 1, v 3, v 2, v 4, v 5 5． 46．数据项 7．结点的直接前驱结点， 结点的直接后继结点 8．ST.top= =-19．参加比较的两个字符串长度相同 10．12-h11．120三、算法应用题1．解答：WPL=4*4+5*4+6*3+7*3+10*3+12*2+18*2 =9*4+23*3+30*2 =36+69+60 =1652．解答：和已知序列对应的二叉树是：3．《数据结构》作业参考答案第3页 共12页4．解答：各关键字的哈希函数值见下表：key19 01 23 14 55 20 84 27 68 11 10 77 H(key) =key%136110 13761311 10 12采用开放地址法的线性探测再散列方法解决冲突，已知其装填因子32=α，对上表中的关键字序列构造所得哈希表如下：地址 01 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 key 01 14 55 27 68 19 20 84 23 11 10 77 比较次数121431131132在等概率情况下，其查找成功时的平均查找长度是：122312231131134121=+++++++++++=succ ASL5．和已知序列对应的森林如下图示：6．解答：设这8个字母的权重为7，19，2，6，32，3，21，10由上图的哈夫曼树知这8个字母的哈夫曼编码分别为0010，10，00000，0001，01，00001，11，00117．解答：①如图所示的无向带权图的邻接矩阵如下图示：按Prim 算法求得的最小生成树如下图(f)所示（树中结点用粗黑实线表示）：假设初始时，树中只有一个顶点，不含有任何一条边，下图（a ）～(f)为用Prim 算法求其最小生成树的过程。
大连理工大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.链式栈的栈顶在链表的()位置。
A.链头B.链尾C.链中D.任意参考答案：A2.以下()方法在数据基本有序时效率最好。
A.快速排序B.冒泡排序C.堆排序D.希尔排序参考答案：B3.快速排序每趟都让一个元素放在它最终应在的位置。
()A.正确B.错误参考答案：A4.在任何情况下，起泡排序比快速排序的速度慢。
()A.正确B.错误参考答案：B完全二叉树中，若一个结点没有左孩子，则它必是树叶。
()A.正确B.错误参考答案：A6.以下选项属于非线性结构的是()。
A.广义表B.队列C.优先队列D.栈参考答案：A7.在下面的排序方法中，辅助空间为O(n)的是()。
A.希尔排序B.堆排序C.选择排序D.归并排序参考答案：D8.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的()方法是散列文件的关键。
A.散列函数B.除余法中的质数C.冲突处理D.散列函数和冲突处理参考答案：D9.设计一个判别表达式中左右括号是否配对出现的算法，采用()数据结构最佳。
A.线性表的顺序存储结构D.栈参考答案：D10.线性表的每个数据元素的数据类型都相同。
()A.正确B.错误参考答案：A11.串的长度是指()。
A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数参考答案：B12.在二叉查找树中，新插入的关键码总是处于最底层。
()A.正确B.错误参考答案：B13.归并排序是原地排序。
()A.正确B.错误参考答案：B14.B.通常不会出现栈满的情况C.不会出现栈空的情况D.删除操作更加方便参考答案：B15.栈和队列具有相同的()。
A.逻辑结构B.存储结构C.存取点D.运算参考答案：A16.若一棵二叉树的先序遍历序列为efhigjk，中序遍历序列为hfiejkg，则该二叉树根结点的右孩子为()。
大工秋数据结构在线作业标准化管理部编码-[99968T-6889628-J68568-1689N]大工17秋《数据结构》在线作业1总分：100分95分一、单选题共10题，50分15分下面关于串的概念的叙述中错误的是()。
学生答案：C 得分:5分25分一个有n个结点的有序单链表中,删除一个结点并仍然使链表有序的时间复杂度是()。
学生答案：B 得分:5分35分序列{a,b,c,d}顺序进栈,其出栈的顺序不可能为()。
学生答案：B 得分:5分45分以下四种数据结构中()不是线性结构。
学生答案：D 得分:5分55分最适合用做链式队列的链表是()。
学生答案：B 得分:5分65分栈的插入与删除操作均在()进行。
学生答案：A 得分:0分75分线性表在()情况下最适合采用链表表示。
学生答案：B 得分:5分85分以下算法的时间复杂度为（）：for(i=0;i<n;i++){for(j=1,sum=a[0];j<=i;j++){sum+=a[j];}cout<<"sumforsubarray0through"学生答案：C 得分:5分95分线性表采用链式存储结构时,其地址()。
学生答案：C 得分:5分105分栈是一种具有()特性的线性表。
学生答案：A 得分:5分二、判断题共10题，50分15分若顺序表中第一个元素的存储地址是100,每个元素长度为2,则第5个元素的地址是110。
学生答案：B 得分:5分25分取线性表第k个元素的时间代价同k的大小无关。
学生答案：A 得分:5分35分栈结构是一种限定只能在一端进行插入,在另一端进行删除的线性表。
学生答案：B 得分:5分45分线性表的每个元素都必须有一个前驱和一个后继。
学生答案：B 得分:5分55分串的长度是指串中所含字符的个数学生答案：A 得分:5分65分顺序存储的线性表不可以进行随机存取操作。
学生答案：B 得分:5分75分在队列的任意位置均可以实现插入元素操作。
大连理工大学22春“计算机科学与技术”《数据结构》期末考试高频考点版（带答案）一.综合考核(共50题)1.一个算法是可行的，即算法中描述的操作都是可以通过已实现的基本运算执行有限次来实现的。
()A.正确B.错误参考答案：A2.串的长度是指()。
A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数参考答案：B3.一个栈的输入序列为123...n，若输出序列的第一个元素是n，输出第i(1=i=n)个元素是()。
A.不确定B.n-i+1C.iD.n-i参考答案：B4.具有10个叶结点的二叉树中有()个度为2的结点。
A.8B.9C.10D.11参考答案：B5.若一棵二叉树的先序遍历序列为efhigjk，中序遍历序列为hfiejkg，则该二叉树根结点的右孩子为()。
A.eB.fC.gD.h参考答案：C6.某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是()。
A.空B.完全二叉树C.二叉排序树D.高度等于其结点数参考答案：D7.同一个算法，实现语言级别越高，算法执行的效率越低。
()A.正确B.错误参考答案：A8.一棵线索二叉树中含有的线索数比分支数多()个。
A.2B.1C.0D.不确定参考答案：A9.队列是只允许在表的一端进行插入，而在另一端删除元素的线性表。
()A.正确B.错误参考答案：A10.栈和队列具有相同的()。
A.逻辑结构B.存储结构C.存取点D.运算参考答案：A11.排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。
()A.正确B.错误参考答案：B12.一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。
()A.正确B.错误参考答案：A13.树的后根遍历序列等同于该树对应的二叉树的()。
A.先序序列B.中序序列C.后序序列D.以上都不对参考答案：B14.从19个记录中查找其中的某个记录，最多进行4次关键字的比较，则采用的查找方法只可能是()。
作业1. 线性表编程作业：1．将顺序表逆置，要求用最少的附加空间。
参考答案#include <>#include <>#include <>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ ElemType *elem;int length;int listsize;}SqList;立单链表");printf("2.取元素值");printf("3.查找\n");printf("4.插入");printf("5.删除");printf("6.显示\n");printf("7.删除大于mink且小于maxk的元素值");printf("8.就地升序排序\n");printf("9.就地逆置");printf("a.有序表插入");printf("q.退出\n");printf("\n请选择操作：");fflush(stdin);scanf("%c",&choice);switch(choice){case '1': printf("请输入单链表中结点个数：");scanf("%d",&n);Create_L2(L,n);break;case '2': printf("请输入元素位序：");scanf("%d",&i);GetElem_L(L,i,e);printf("元素值为：%d\n",e);break;case '3': printf("请输入要查找的元素：");scanf("%d",&e);if(dlbcz(L,e))printf("查找成功！");elseprintf("查找失败。
");break;case '4': printf("请输入插入位置：");scanf("%d",&i);printf("请输入要插入的元素：");scanf("%d",&e);if(ListInsert_L(L,i,e))printf("插入成功！单链表为：");elseprintf("插入失败。
");break;case '5': printf("请输入删除位置：");scanf("%d",&i);if(ListDelete_L(L,i,e))printf("删除成功！");elseprintf("删除失败。
\n");break;case '6': printf("\n单链表为：");xsList(L);break;case '7': printf("请输入mink和maxk:");scanf("%d,%d",&mink,&maxk);DelList(L,mink,maxk);break;case '8': sh_sort(L);break;case '9': nizhi(L);break;case 'a': printf("请输入在有序表中插入的元素值:");scanf("%d",&e);yxcharu(L,e);break;}}}作业2. 栈、队列、数组非编程作业：1．若进栈序列为ABCD，请写出全部可能的出栈序列和不可能的出栈序列。
参考答案：可能的出栈序列：(14种)dcba cdba bacd cbda adcb cbad bdca acdb bcda acbd bcad abdc badc abcd不可能的出栈序列：(10种)d bca dbac dabc dacb dcab cabd cdab bdac cadb adbc2．简要说明循环队列如何判断队满和队空参考答案：当牺牲一个存储结点，约定以“队列头指针在队列尾指针的下一位置（指环状的下一个位置）上” 作为队列“满”状态的标志时，循环队列判断队满的条件为：(rear+1) % MaxQsize==front；判断队空的条件为：front == rear。
3．设A为n阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0]开始存放），请分别给出存放上三角阵时任一矩阵元素a ij（1≤i,j≤n）的地址计算公式和存放下三角阵时任一矩阵元素a ij（1≤i,j≤n）的地址计算公式。
参考答案：存放上三角阵时，任一矩阵元素a ij（1≤i,j≤n）的地址计算公式为：()()ij11-1Loc(a)=Loc(a)+1*2i ij l⨯⎡⎤+-⎢⎥⎣⎦存放下三角阵时，任一矩阵元素a ij（1≤i,j≤n）的地址计算公式为：()()ij11-1Loc(a)=Loc(a)+1*2j ji l⨯⎡⎤+-⎢⎥⎣⎦4．写出下面稀疏矩阵的三元组顺序表和十字链表表示。
参考答案：400000503008000000000700200000A⎡⎤⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎣⎦编程作业栈采用顺序栈存储，试设计算法实现将表达式转换成后缀表达式输出。
例如，输入表达式：a+b/c-(d*e+f)*g输出其后缀表达式：abc/+de*f+g*-参考答案：#include <>#include <>#include <>#define OVERFLOW -2#define OK 1#define ERROR 0#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status;typedef char SElemType;typedef char string[80];typedef struct{ SElemType *base;SElemType *top;int stacksize;}SqStack;Status InitStack(SqStack &S){ =(SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));if(! exit(OVERFLOW);=;=STACK_INIT_SIZE;return(OK);}Status ClearStack(SqStack &S){ =(SElemType*)realloc,STACK_INIT_SIZE *sizeof(SElemType));if(! exit(OVERFLOW);=;=STACK_INIT_SIZE;return(OK);}void DestroyStack(SqStack &S){ =0;if free;==NULL;}Status StackEmpty(SqStack S){ if==return true;elsereturn false;}SElemType GetTop(SqStack S){ SElemType e;if>e=*;return e;}Status Push(SqStack &S, SElemType e){if 树非编程作业：1．请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
参考答案：具有3个结点的树：具有3个结点的二叉树：2． 已知二叉树的先序遍历序列是EABDCFHGIKJ ，中序遍历序列是ABCDEFGHIJK ，请构造二叉树，并写出其层次遍历序列和后序遍历序列。
参考答案：层次：E A F B H D G I C K J 后序---C D B A G J K I H F E3． 将下图所示的森林转换成一棵二叉树。
EACB D I JH FGKA B C D G H I J KE FL参考答案：转换成的二叉树为：4． 将下图所示的二叉树还原成树或森林。
BA CDFGE HI JKLABCDGHIJKEFLMN参考答案：转换为森林：5． 假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G}，字母在电文中出现的频率分别为、、、、、、。
试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL 。
参考答案：哈夫曼树为：AC HBFDM EGNJI K L 1AEG BWPL=4*++3*+++2*+=A:101 B:001 C:100 D:0001 E:11 F:0000 G:01编程作业：二叉树采用二叉链表存储，试设计算法实现：1．CreateBT (BiTree &T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；如输入：AB#D##CE#F### 则建立如下图所示二叉树的二叉链表2．ExchangeBT(BiTree T ): 设计递归算法实现二叉树中所有结点的左右孩子交换；3．CountLeaf(BiTree T, TElemType x, int &count ): 统计以值为x 的结点为根的子树中叶子结点的数目；4．DispBiTree(BiTree T, int level ) : 按树状打印二叉树。
打印得到：#C###F ##E A ##D #BBCFAED提示：对于根为T ，层次为level 的子树：① 打印其下一层(level+1层)右子树； ② 打印根结点；③ 打印其下一层(level+1层)左子树； *结点左边的’#’个数为其层次数*参考答案：#include <> #include <>typedef struct BiTNode{ char data;struct BiTNode *lchild,*rchild; }BiTNode, *BiTree; 图非编程作业:1．已知带权有向图如图所示，画出该图的邻接矩阵存储结构。
