还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
数据结构试卷
(一)
一、选择题(分)(数据)项数据(类型)数(据)元素数(据)变量.设数据结构,()其中,1,,,,,1,则数据结构是()0,1,,饯性)结构树(型)结构图(型)结构
1.组成数据的基本单位是()(线性)表栈(B)队列(C)树(D).数组的逻辑结构不同于下列()的逻转结构A ii«0D i
1.二叉树中第i(i2D层上的结点数最多有()个•设指针变量指向单链表结点,则删除结点的后继结点)o需要的操作为A C.设栈和队列的初始状态为空,元素
1、、、和挨次通过栈,一个元素出栈后即进入队列,若个元素出列的顺序为、、、、和,1则栈的容量至少应该是()o(A)(B)(
0.将1阶对称矩阵压缩存储到一维数组中,则数组的长度至少为()o(A)1(B)(
0.设结点有个兄弟结点且结点为结点的双亲结点,则结点的度数数为()(A)(B)(
0.根据二叉树的定义可知二叉树共有()种不同的形态=r[j];i=r[i];j=设有两个集合A和集合B,要求设计生成集合C=AAB的算法,其中集合A、B和C用链式存储结构表示=ha,he=0;p!=0;p==hb;q!=0;q=设有以下四种排序方法,则()的空间复杂度最大冒泡排序快速排序堆排序希尔排序
二、填空题分设顺序循环队列的队头指针和队尾指针分别为和,其中队头指针指向当前队头元素的前一个位置,队尾指针指向当前队尾元素所在的位置,则出队列的语句为设线性表中有个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为,在链式存储结构上实现顺序查找的平均时间复杂度为设一棵二叉树中有个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有个指针域,个空指针域设指针变量指向单链表中结点,指针变量指向被插入的结点,则在结点的后面插入结点的操作序列为设无向图中有个顶点和条边,则其对应的邻接表中有个表头结点和个表结点设无向图中有个顶点条边,所有顶点的度数之和为,则和有关系设一棵二叉树的前序遍历序列和中序遍历序列均为,则该二叉树的后序遍历序列为设一棵彻底二叉树中有个结点,如果按照从上到下、从左到右的顺序从开始顺序编号,则编号为的双亲结点的编号是,编号为的左孩子结点的编号是下列程序段的功能实现子串在主串中位置的算法,要求在下划线处填上正确语句设一个连通图中有个顶点条边,则其最小生成树上有条边
三、应用题(分).设彻底二叉树的顺序存储结构中存储数据,要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列•设给定一个权值集合,,,,,要求根据给定的权值集合构造一棵哈夫曼树并计算哈夫曼树的带权路径长度.设一组初始记录关键字序列为,,,,,,要求给出以为基准的一趟快速排序结果以及第趟直接选择排序后的结果•设无向图(所右图所示),要求给出该图的深度优先和广度优先遍历的序列并给出该图的最小生成树
四、算法设计题分设计判断单链表中结点是否关于中心对称算法设计在链式存储结构上建立一棵二叉树的算法设计判断一棵二叉树是否是二叉排序树的算法数据结构试卷
(一)参考答案
一、选择题
二、填空题
三、应用题链式存储结构略,前序,中序,后序哈夫曼树略,线性探测链地址法深度,广度,最小生成树的边集为
四、算法设计题设计判断单链表中结点是否关于中心对称算法设计在链式存储结构上建立一棵二叉树的算法设计判断一棵二叉树是否是二叉排序树的算法数据结构试卷
(二)
一、选择题分.下面关于线性表的叙述错误的是()0线性表采用顺序存储必须占用一片连续的存储空间线性表采用链式存储不必占用一片连续的存储空间线性表采用链式存储便于插入和删除操作的实现线性表采用顺序存储便于插入和删除操作的实现.设哈夫曼树中的叶子结点总数为,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域.设顺序循环队列的头指针和尾指针分别为和,头指针总是指向队头元素的前一位置,尾指针总是指向队尾元素的当前位置,则该循环队列中的元素个数为()%%.设某棵二叉树的中序遍历序列为,前序遍历序列为,则后序遍历该二又树得到序列为().设某彻底无向图中有个顶点,则该彻底无向图中有()条边.设某棵二叉树中有个结点,则该二叉树的最小高度为().设某有向图中有个顶点,则该有向图对应的邻接表中有()个表头结点.设一组初始记录关键字序列,,,,,以第一个记录关键字为基准进行一趟快速排序的结果为()D,
二、填空题(分)1为了能有效地应用查找技术,必须解决的两个问题是和卜.面程序段的功能实现数据进栈,要求在下划线处填上正确的语句typedef tructint100];int top;tack;voi push(sqst tack,int)if(st to力)printf(^overflow);else;中序遍历二叉排序树所得到的序列是序列(填有序或者无序)快速排序的最坏时间复杂度为,平均时间复杂度为设某棵二叉树中度数为的结点数为,度数为1的结点数为「则该二叉树中度数为的结点数为;若采用二叉链表作为该二叉树而存储结构,则该二叉树中共有个空指针域设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为,则e o设一组初始i瞭关键字序列为(,,,,,,,1,)则利用筛选法建立的初始堆为设某无向图的邻接表为,则从顶点开始的深度优先遍历序列为;广度优先遍历序列为O
三、应用题(分)
1.设一组初始记录关键字序列为(,,,,,,)则分别给出第趟简单选择排序和第趟直接插入排序后的结果•设指针变量指向双向链表中结点A,指针变量指向被插入结点B,要求给出在结点A的后面插入结点B的操作序列(设双向链表中结点的两个指针域分别为和).设一组有序的记录关键字序列为,,,,,,,,,查找方法用二分查找,要求计算出查找关键字时的比较次数并计算出查找成功时的平均查找长度.设一棵树中边的集合为,AB,A,C,A,,B,,C,,C,,要求用孩子兄弟表示法(二叉链表)表示出该树的存储结构并将该树转化成对应的二叉树.设有无向图(如右图所示),要求给出用普里姆算法构造最小生成树所走过的边的集合.设有一组初始记录关键字为,,,,,,要求构造一棵二又排序树并给出构造过程
四、算法设计题分.设有一组初始记录关键字序列(,,,,,),要求设计一个算法能够在的时间复杂度内将线性表划分成两部份,其中左半部份的每一个关键字均小于,右半部份的每一个关键字均大于等于.设有两个集合A和集合B,要求设计生成集合OAAB的算法,其中集合A、B和C用链式存储结构表示数据结构试卷
(二)参考答案
一、选择题B CA AC
二、填空题构造一个好的A函数,确定解决冲突的方法有序
三、应用题树的链式存储结构略,二叉树略
四、算法设计题设有一组初始记录关键字序列(,,,,,),要求设计一个算法能够在的时间复杂度内将线性表划分成两部份,其中左半部份的每一个关键字均小于,右半部份的每一个关键字均大于等于。