数据结构期末考试题期末考试卷测试卷AB卷带答案模拟试题试卷21年XX学校X专业.doc

《数据结构期末考试题期末考试卷测试卷AB卷带答案模拟试题试卷21年XX学校X专业.doc》由会员分享，可在线阅读，更多相关《数据结构期末考试题期末考试卷测试卷AB卷带答案模拟试题试卷21年XX学校X专业.doc（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程名称：数据结构 B卷题号一二三四合计满分30103030100实得分班级- 学号- 姓名-一、填空题（每空1.5分，共30分） 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的 。 数据结构是一门研究 的程序设计问题中计算机的操作对象以及它们之间的 等等的学科。 带头结点的单向链表L为空的判定条件是 ；非空的循环单链表head的尾结点p满足条件 。 栈和队列是两种特殊的线性表，栈的特点是 ，栈的典型应用有 和 。 在具有n个单元的循环队列中，队列满时共有 个元素。 若串的长度不能确定，可采用动态存储结构，为串值分配一个存储空间，同时建立一个串的描述子以指示串值的长度

2、和串在存储空间中的位置，称该结构为 。 稀疏矩阵一般的压缩存储方法有两种，即 和十字链表。 二维数组A1020采用列序为主方式存储，每个元素占10个存储单元，且A00的存储地址是2000，则A612的地址是 。 一棵高度为h的满二叉树共有 个终端结点。 已知一棵完全二叉树的第5层有3个结点，其叶子结点数是 。 具有8个顶点的有向完全图有 条弧。 在无向图G的邻接矩阵A中，若Aij等于1，则Aji等于 。 对线性表进行二分查找时，要求线性表必须以 方式存储，且结点按关键字 排列。 在分块查找方法中，首先查找索引，然后再查找相应的 。 与快速排序和堆排序相比，归并排序的最大特点是，它是一种 的排序

3、方法。二、判断题（每小题1分，共10分）若正确，填入“T”，否则填入“F”。（ ）线性表的逻辑顺序与存储顺序总是一致的。（ ）一个栈的入栈序列是12345，则栈的输出序列12345是不可能的。（ ）将递归算法转换成对应的非递归算法时，通常需要使用栈。（ ）设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。（ ）二维数组是其数据元素为线性表的线性表。（ ）线索二叉树是一种逻辑结构。（ ）深度为K的完全二叉树至少有2K-1个结点。（ ）采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。（ ）若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。（ ）在待排序的元素

4、序列基本有序的前提下，效率最高的是插入排序。三、解答下列各题（每小题5分，共30分） 已知一棵二叉树的中序、后序序列分别如下：中序：D C E F B H G A K J L I M 后序：D F E C H G B K L J M I A 要求： 画出该二叉树； 写出该二叉树的先序序列。 在一段文字中，7个常用汉字及出现频度如下：的 地 于 个 和 是 有 20 19 18 17 15 10 1要求： 画出对应的Huffman树； 求出每个汉字的Huffman编码。 求出下图的一棵最小代价生成树。 16 8 1 9 20 6 10 80 15 18 12 20 50 输入一个正整数序列100

5、，50，302，450，66，200，30，260，建立一棵二叉排序树，要求： 画出该二叉排序树； 画出删除结点302后的二叉排序树。 设有一组关键字：19，01，23，14，55，20，84，27，68，采用哈希函数：H（key）=key mod 7，采用开放地址法的线性探测再散列方法解决冲突。要求：在011的散列地址空间中对该关键字序列构造哈希表。0 1 2 3 4 5 6 7 8 9 10 11 一组序列的关键码为：28、19、27、49、56、12、10、25要求： 利用快速排序的方法，写出以第一个记录为基准得到的一次划分结果； 利用堆排序的方法，写出建立的初始大堆。四、算法设计题（共

6、30分）使用类C写出实现算法的函数，并加以适当的注解。 假设有两个按元素值非递增有序排列的线性表LA和LB，请编写算法将LA表和LB表合并成一个按元素值非递增有序排列的线性表LC。假设线性表的存储结构描述如下：#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量以一数据元素存储长度为单位SqList;试设计算法在按元素值非递增有序排列的带头结点单向链表head中，删除值相同的多余元素。假设

7、该链表的存储结构描述如下：typedef struct LNODE ElemType data;struct LNODE *next;*LinkList; 试设计算法计算一棵给定二叉树上所有结点数目。假设二叉树的存储结构描述如下： typedef struct BiTNodeTElemType data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/BiTNode,*BiTree；课程名称：数据结构 B卷参考答案一、填空题： 存储结构 非数值计算 关系和操作 L-next=NULL p-next=head 先进后出 表达式求值 实现递归过程 n-1 堆/

8、堆结构 三元组表 3260 2h-1 9 56 1 顺序 有序 块 插入排序/直接插入排序 稳定 二、判断题：F F T F T F T F T T三、解答下列各题 ：A B I C G J M D E H K L F 先序:A B C D E F G H I J K L M 1 9 20 6 10 15 12 10039 61 19地 20的 26 3511 15和 17个 18于 1有 10是 01 的 00 地 111 于 110 个 101 和 1001 是 1000 有 100 50 30230 66 200 450 260100 50 26030 66 200 450 0 1 2

9、3 4 5 6 7 8 9 10 11 1401238419552027685649 27 28 19 12 10 25 25 19 27 10 12 28 56 49 该序列不是一个堆。建成的初始大根堆如下： 56 49 27 28 19 12 10 25 或：四、算法设计：（以下答案不唯一） void MergeList_Sq(SqList La,SqList Lb,SqList &Lc) pa=La.elem; pb=Lb.elem;pc=Lc.elem=(ElemType )malloc(La.length+Lb.length)*sizeof(ElemType);if (!Lc.ele

10、m) exit(OVERFLOW);pa_last=La.elem+La.length-1;pa_last=Lb.elem+Lb.length-1;Lc.length=0;while (pa=pa_last & pb *pb) *pc+ = *pa+; Lc.length+; else *pc+ = *pb+; Lc.length+; while (pa=pa_last) *pc+ = *pa+; Lc.length+; while (pbnext)p=La-next;while (p-next)if (p-data =p-next-data) q=p-next; p-next=q-next;

11、 free(q); else p=p-next; int CountNode(BinTree bt) if (bt=Null) return(0);else num1=CountNode(root-lchild);num2=CountNode(root-rchild); return(num1+num2+1); 课程名称：数据结构（C语言） A B卷题 号1234合计满 分15103045100实得分班级- 学号- 姓名-（本试卷答卷时间为120分钟；卷面100分，占总分60%，实验及平时占40%）一、填空题（每空1分，共15分） 对于给定的n个数据元素，可能构造出 、 、 和 四种逻辑结构。

12、任何一个算法的设计取决于选定的 ，而算法的实现依赖于采用的 。在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 。稀疏矩阵一般的压缩存储方法有两种，即 和 。具有n个顶点的有向图最多有 条边。在无向图G的邻接矩阵中，求第i个结点的度的方法是 。由树转换为二叉树，其根节点的右子树总是 。在分块查找方法中，首先查找 ，然后再查找相应的块。含12个结点的平衡二叉树的最大深度是 （设根结点的深度为1）。树形选择排序通常采用 存储结构。二、判断题（每小题1分，共10分）若正确，填入“”，否则填入“”。 ( )不带头结点的单向循环链表head为空表的条件是head=NIL。 ( )若

13、采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置。 ( )具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。 ( )若一个广义表的表头为空表，则此广义表亦为空表。 ( )用一维数组存储二叉树时，总是以前序遍历存储节点。 ( )前序和中序遍历用线索树方式存储的二叉树，不必使用栈。 ( )哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。 ( )若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。 ( )折半搜索适用于有序表，包括有序的顺序表和有序的链表。 ( )快速排序的速度在所有的排序方法中为最快，而且所需附加空

14、间也最少。三、解答下列各题（每小题6分，共30分） 证明：具有n个结点的完全二叉树的深度为log2n1。 一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格处的内容，并画出该二叉树。 先序：_ B _ F _ I C E H _ G 中序：D _ K F I A _ E J C _ 后序：_ K _ F B H J _ G _ A 用深度优先搜索遍历下图所示的无向图，试给出以1为起点的顶点访问序列（同一个顶点的多个邻接点，按数字顺序访问），并给出一棵最小生成树。 有关键字集合：53、17、19、61、98、75、79、63、46、49，哈希函数：H（key）=key

15、mod 13，采用开放定址法中的二次探测再散列方法解决冲突。要求： 将上述关键字填入下表； 求等概率下查找成功时的平均查找长度； 求装填因子。0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 已知序列503、87、512、61、908、170、897、275、653、462，写出用下列算法从小到大排序第一趟结束时的序列。 希尔排序（第一趟排序时的增量为3）； 快速排序（选第一个记录为枢轴）； 堆排序（只写出初始堆）。四、算法设计题（，每小题10分，小题15分，共45分）使用类C语言写出实现算法的函数，并加以适当的注解，不必写出整个程序。 设一个环上有若干个整数，现采用单向循

16、环链表L存储该环，设计算法判断环上任意两个相邻元素值之差的绝对值是否不超过2。假设单向循环链表的存储结构描述如下：struct LNODE float coef;int expn;struct LNODE *next;typedef struct LNODE * LinkList; 计算二叉树上单分支结点数目。假设二叉树的存储结构描述如下： typedef struct BiTNodeTElemType data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/ BiTNode,*BiTree； 设计算法实现按层次遍历（遍历操作定义为打印结点的data域）

17、二叉树。二叉树的存储结构描述同上题，在算法中可能要使用一个队列Q，其相关操作:Iniqueue(Q) 置队列空操作Empty(Q) 判空函数Enqueue(Q,x) 入队列操作Dlqueue(Q) 出队列操作 设计算法在国际象棋棋盘上放置八个皇后，以使其中任意两个不能互相吃掉对方。 参考答案课程名称：数据结构（C语言） A B卷一、填空题：(15*1分) 集合 线性结构 树形结构 网状（图形）结构 逻辑结构 存储结构 O（n） 三元组（表） 十字链表 n（n-1） 求邻接矩阵第i行非零元素之和 为空 索引（表） 5 顺序二、判断题：(10*1分) 三、解答下列各题 ：(5*6分) 证明：假设此

18、二叉树的深度为k，根据二叉树性质2及完全二叉树的定义得到： 2k11 n 2k-1即： 2k1 n 2k对不等式取对数，有 k1log2n kA B C D F E G K I H J由于k是整数，所以有：k log2n+1证毕。 先序：A B D F K I C E H J G 中序：D B K F I A H E J C G 后序：D K I F B H J E G C A 16 11 5 6 18 顶点访问序列：1 2 3 6 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 1453791719984661756349 ASL = 15/12 = 1.25 = 1

19、0/15 = 0.67 61 87 170 462 275 512 503 908 653 897 462 87 275 61 170 503 897 908 653 512 908 653 897 503 462 170 512 275 61 87 四、算法设计：（以下答案不唯一）(4*1) Func judge(l:link):boolean; p:=l; repeat if abs(P.data-P.next.data)=2 then P:=P.next; else return(false)until P=L; return(true)endF; FUNC nodes1(t:bitre

20、):integer; if t=nil then nodes1:=0 else if (t.lchild=nil) and (t.rchild=nil) then nodes1:=0else if (t.lchild=nil) or (t.rchild=nil)then nodes1:=1+nodes1(t.lchild)+nodes1(t.rchild) else nodes1:=nodes1(t.lchild)+nodes1(t.rchild) ENDF; PROC Level_traver(T:bitre); Iniqueue(Q); if T nil then【 Enqueue(Q,x

21、); while not Empty(Q) do 【 p:= Dlqueue(Q); write(T.data); if p.lchild nil then Enqueue(Q,p.lchild); if p.rchild nil then Enqueue(Q,p.rchild); 】 】 ENDP; 当前起始坐标（x,y）；正在试探位置的序号i； 将放置情况用二维数组h1.8，1.8表示每个元素存放序号或0； 各位置的度用二维数组p1.8，1.8存储。PROC try(x,y,i:integer); var min,j1,j,u,v,u1,v1:integer; if i=65 then write(h) else【min:=8for j:=1 to 8 do【u:=x+dirj.x ;v:=y+dirj.y;if (u=1) and (u=1) and (v=8) and (hu,v=0)then【pu,v:=pu,v-1;if pu,v minthen【 min:=pu,v;u1:=u;v1:=v】 hu1,v1:=i;try(u1,v1,i+1) 】ENDP; - 12 -