下载文档原格式
本次作业总分值：100.0 得分:0.0 正确的题数：0 题目总数: 10 正确率:0.0%得分：0.0 本次作业总分值：100.0 正确率:0.0%正确的题数：0 题目总数：10本次作业总分值：100.0 得分:0.0 正确的题数：0 题目总数: 10 正确率:0.0%不会超过（）。
某二叉树的前序遍历序列为abdgcefh，中序遍历序列为单选题10.0 4 X dgbaechf，则其后序遍历序列为（）。
若一个具有n个结点、k条边的非连通无向图是一个森林单选题10.0 3 X（n>k），本次作业总分值：100.0 得分：0.0 正确的题数：0 题目总数：10正确率:0.0%在线作业自动判卷分正确答案你的答案批改题目类型值从1000个兀素中选出其中五个最大值兀素（）排序单选题10.0 3 X最适合。
以下排序方法中，稳定的排序方法是（）。
单选题10.0 2 X在有序表（3,8,13,15,16,17,21,24,45 ）中，用二分查找法查单选题10.0 1 X 找关键字21,所需进行关键字比较的次数为（）。
下列排序方法中效率最高的排序方法是（）。
单选题10.0 3 X 快速排序属于那种排序类型（）。
单选题10.0 3 X 顺序查找适合于存储结构为（）的查找表。
单选题10.0 4 X 对线性表进行二分查找时，要求线性表必须（）。
单选题10.0 3 X下述几种排序方法中，平均查找长度最小的是（）。
单选题10.0 3 X 对哈希（HASH）函数H（k）= k MOD m, 一般来说，m应取（）。
单选题10.0 1 X 长度为256的表,采用分块查找，每块最佳长度为（）。
单选题10.0 2 X10 正确率:0.0%本次作业总分值：100.0 得分:0.0 正确的题数：0 题目总数:10 正确率:0.0%本次作业总分值:100.0 得分:0.0 正确的题数：0 题目总数：10 正确率:0.0%在线作业自动判卷正确的题数：0 题目总数:本次作业总分值：100.0 得分:0.010 正确率:0.0%。
2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、下列排序算法中，占用辅助空间最多的是（）。
A.归并排序B.快速排序C.希尔排序D.堆排序3、线性表的顺序存储结构是一种（）。
A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。
A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、下列关于无向连通图特性的叙述中，正确的是（）。
Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。
下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。
Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、Ⅳ B．仅Ⅰ、Ⅱ、Ⅲ C．仅Ⅱ、Ⅲ、Ⅳ D．仅Ⅲ、Ⅳ、Ⅴ8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
北理工《数据结构与算法》在线作业试卷总分：100 测试时间：-- 试卷得分：99.5一、单选题（共40 道试题，共99.5 分。
）得分：99.51. 图的存储结构不包括()A. 数组表示B. 邻接表C. 邻接多重表D. 孩子兄弟表示正确答案：D 满分：2.5 分得分：2.52. 当两个元素比较出现反序时就相互交换位置的排序方法称为()。
A. 归并排序B. 选择排序C. 交换排序D. 插入排序正确答案：C 满分：2.5 分得分：2.53. 快速排序属于那种排序类型()。
A. 选择排序B. 插入排序C. 交换排序D. 基数排序正确答案：C 满分：2.5 分得分：2.54. 中序遍历一棵二叉排序树所得到的结点序列是键值的()序列。
A. 递增或递减B. 递减C. 递增D. 无序正确答案：C 满分：2.5 分得分：2.55. 关键路径是指AOE(Activity On Edge)网中()。
A. 最长的回路B. 最短的回路C. 从源点到汇点(结束顶点)的最长路径D. 从源点到汇点(结束顶点)的最短路径正确答案：C 满分：2.5 分得分：2.56. 设有一个二维数A[m][n]，以行序为主序存储。
假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，则A[4][5]在()位置，(10)表明用10进数表示。
A. 692(10)B. 626(10)C. 709(10)D. 724(10)正确答案：C 满分：2.5 分得分：2.57. 当待排序列基本有序时，下列排序方法中()最好。
A. 直接插入排序B. 快速排序C. 堆排序。
《数据结构与算法设计》实验报告——实验二学院：自动化学院班级：06111001学号：**********姓名：宝竞宇一、实验目的掌握栈的建立，输入，删除，出栈等基本操作。
应用栈解决实际问题。
二、实验内容实现简单计算器的功能,请按照四则运算加、减、乘、除、幂（^）和括号的优先关系和惯例，编写计算器程序。
要求支持运算符：+、-、*、/、%、（）和=：①从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志；②输入表达式中的数值均为大于等于零的整数，如果中间计算过程中出现小数也只取整进行计算。
例如，输入：4+2*5= 输出：14输入：(4+2)*(2-10)= 输出：-48三、程序设计1、概要设计抽象数据类型定义：两个栈结构，分别用来储存数据和计算符号宏定义：函数“成功”，“失败的返回值”在主程序程序中先依次输入各表达式，存入相应各栈，然后，调用“判断函数”来判断计算符的优先次序，然后再利用计算函数来计算，表达式值。
其中还有，取栈顶元素函数，存入栈函数。
2、详细设计数据类型实现：struct t{ char dat[200];int top;}prt;入栈函数：存入数组，栈顶指针上移void pushd(long int a){ prd.dat[prd.top++]=a;}出栈：取出对应值，栈顶指针下移long int popd( ){ return prd.dat[--prd.top];}比较优先级：建立数组，比较返回大于小于号。
计算函数：以字符型输入，运算符号，用switch来分支计算判断，返回计算数值long int operation ( long int x, long int y, char a){ s witch(a){ case '+': return x+y;case '-': return x-y;case '*': return x*y;case '/': if ( y )return x/y;else{ printf("Divide 0.\n");return 0;}case '%': return (long int) fmod(x,y);case '^': if (y>=0 ) return (long int) pow(x,y);else return (0);default: printf("Error No. 3\n");return 0;}}主程序：在主程序内，以字符串的形式输入表达式，然后分别调用函数存入各相应栈，然后用数组判断，比较运算符的优先顺序。
《数据结构与算法设计》实验报告——实验四学院：班级：学号：姓名：一、实验目的1.通过实验实践、巩固线性表的相关操作； 2.熟悉VC 环境，加强编程、调试的练习； 3.用C 语言实现线性表的抽象数据类型，实现线性表构造、插入、取数据等基本操作； 4. 理论知识与实际问题相结合，利用上述基本操作实现三种排序并输出。
二、实验内容从键盘输入10个数，编程实现分别用插入排序、交换排序、选择排序算法进行排序，输出排序后的序列。
三、程序设计1、概要设计为了实现排序的功能，需要将输入的数字放入线性表中，进行进一步的排序操作。
(1)抽象数据类型：ADT SqList{数据对象：D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥数据关系：R1=11{,|,,1,2,,}i ii i a a a a D i n --<>∈= 基本操作：InPut(SqList &L)操作结果：构造一个线性表L 。
OutPut(SqList L)初始条件：线性表L 已存在。
操作结果：按顺序在屏幕上输出L 的数据元素。
InsertSort(SqList &L)初始条件：线性表L 已存在。
操作结果：对L 的数据元素进行插入排序。
QuickSort(SqList &L)初始条件：线性表L 已存在。
操作结果：对L 的数据元素进行快速排序。
SelectSort(SqList &L)初始条件：线性表L 已存在。
操作结果：对L 的数据元素进行选择排序。
}ADT SqList⑵主程序流程由主程序首先调用InPut(L)函数创建顺序表，调用InsertSort(L)函数进行插入排序，调用OutPut(L)函数显示排序结果。
调用QuickSort(L)函数进行交换排序，调用OutPut(L)函数显示排序结果。
调用SelectSort(L)函数进行选择排序，调用OutPut(L)函数显示排序结果。
一、单项选择题（共40道试题, 共100分。
）V1.3个结点旳无向完全连通图至少有()条边。
A.3B.4C.5D.62.设有一种二维数A[m][n], 以行序为主序存储。
假设A[0][0]寄存位置在644(10), A[2][2]寄存位置在676(10), 每个元素占一种空间, 则A[4][5]在()位置, (10)表明用10进数表达。
A.692(10)B.626(10)C.709(10)D.724(10)3.具有n个顶点旳有向完全图有()条弧。
A.nB.n*(n-1)C.n*(n+1)D.n*n4.队列旳操作特点是()。
A.先进先出B.后进先出D.只能从队尾出队5.一种栈旳入栈序列是abcde, 则栈旳不也许旳输出序列是()。
A.edcbaB.decbaC.dceabD.abcde6.某二叉树旳前序和后序序列恰好相似, 则该二叉树一定是()旳二叉树。
A.空或只有一种结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子7.学习数据构造重要目旳是()。
A.处理数值计算问题B.研究程序设计技巧C.选用合适数据构造, 写出更有效旳算法D.是计算机硬件课程旳基础8.任何一种无向连通图旳最小生成树()。
A.只有一棵B.有一棵或多棵D.也许不存在9.栈是一种()旳数据构造。
A.存取受限旳线性构造B.存取不受限旳线性构造C.存取受限旳非线性构造D.存取不受限旳非线性构造10.线性表采用链式存储时, 结点旳存储地址()A.必须是不持续旳B.持续与否均可C.必须是持续旳D.和头结点旳存储地址相持续11.一棵高度（假定树根结点为第0层）为4旳完全二叉树中旳结点数至少为()。
A.15B.16C.17D.3112.次序查找适合于存储构造为()旳查找表。
A.压缩存储B.散列存储D.次序存储或链式存储13.设连通图G中旳边集E={(a, b), (a, e), (a, c), (b, e), (e, d), (d, f), (f, c)}, 则从顶点a出发可以得到一种深度优先遍历旳顶点序列为()A.abedfcB.acfebdC.aebdfcD.aedfcb14.评价排序算法好坏旳原则重要是()。
