《2022年数据结构试卷 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构试卷 .pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、一、单项选择题(在每小题的四个备选答案中选出一个正确答案，并将其号码填在题干的括号内。每小题 1 分，共 14 分)1.算法分析的目的是()A.找出数据结构的合理性B.研究算法中的输入/输出关系C.分析算法的效率以求改进D.分析算法的易读性2.在需要经常查找结点的前驱与后继的场合中，使用()比较合适。A.单链表 B.双链表 C.顺序表 D.循环链表3.下面关于线性表的叙述中，错误的为()A.顺序表使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域4.带头结点的单链表head 为空的判断条件是()A.head=NIL B.
2、head.next=NIL C.head.next=head D.headNIL 5.队列通常采用两种存储结构是()A.顺序存储结构和链表存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构6.按照二叉树的定义，具有3 个结点的二叉树有()种。A.3 B.4 C.5 D.6 7.二叉树的结构如下图所示，其中序遍历的序列为()A.a,b,d,g,c,e,f,h B.d,g,b,a,e,c,h,f C.g,d,b,e,h,f,c,a D.a,b,c,d,e,f,g,h 8.深度为 5 的二叉树至多有()个结点。A.16 B.32 C.31 D.10 9.对于一个具有
3、 n 个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为()A.n B.n+1 C.n1 D.n+边数10.在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要()条边。A.n B.n+1 C.n1 D.n/2 11.静态查找表与动态查找表二者的根本差别在于()A.它们的逻辑结构不一样B.施加在其上的操作不同C.所包含的数据元素的类型不一样D.存储实现不一样12.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。因为散列函数不是一对一的关系，所以选择好的()方法是散列文件的关键。名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 7 页 -A.散列函数 B
4、.除余法中的质数C.冲突处理 D.散列函数和冲突处理13.对于大文件的排序要研究在外设上的排序技术，即()A.快速排序法 B.内排序法C.外排序法 D.交叉排序法14.设有 5000 个无序的元素，希望用最快的速度挑选出其中前50 个最大的元素，最好选用()法。A.冒泡排序 B.快速排序C.堆排序 D.基数排序二、判断题(判断下列各题，正确的在题干后面括号内打“”，错误的打“”。每小题 2 分，共 20 分)1.所谓数据的逻辑结构指的是数据元素之间的逻辑关系。()2.在线性结构中，每个结点都有一个直接前驱和一个直接后继。()3.插入和删除是数组的两种基本操作。()4.在链栈的头部必须要设置头结
5、点。()5.在二叉树中插入结点则该二叉树便不再是二叉树。()6.查找表的逻辑结构是集合。()7.静态查找表的检索与修改被分成两个不交叉的阶段分别进行。()8.在索引顺序文件中插入新的记录时，必须复制整个文件。()9.如果某种排序算法是不稳定的，则该方法没有实际的应用价值。()10.对于 n 个记录的集合进行冒泡排序，在最坏情况下所需要的时间是0(n2)()三、填空题(每小题 2 分，共 30 分)1.程序设计的实质是 _ 和_。2.设由字符串 a=data、b=structure、c=,则 a 与 c 连接然后与 b 连接的结果为：_。3.通常单链表的头结点指的是_；单链表的首结点指的是 _。
6、4.一个队列的入队序列是a、b、c、d，则队列的输出序列为 _。5.栈结构通常采用的两种存储结构是_ 和_。6.具有 N 个结点的完全二叉树的深度为_。7.树的三种主要的遍历方法是：_、_ 和层次遍历。8.在无向图的邻接矩阵A 中，若 A i,j 等于 1，则 A j,i 等于_。9.采用散列技术实现散列表时，需要考虑的两个主要问题是：构造_ 和解决_。10.索引顺序表上的查找分两个阶段：(1)_；(2)_。11.散列文件中的记录通常是成组存放的。若干的记录组成一个存储单位，称作_。12.就文件而言，按用户的观点所确定的基本存储单元称为_。按外设的观点所确定的基本存储单元称为 _。13.文件的
7、检索有三种方式：_ 存取、_ 存取和按关键字存取。14.最简单的交换排序方法是 _ 排序。名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 7 页 -15.外排序的基本方法是 _。四、应用题(每小题 6 分，共 18 分)1.假定在学生的档案中含有：姓名、学号、年龄、性别。如采用线性表作为数据结构来实现档案管理问题，分别给出线性表的在顺序实现下的类型定义和在链接实现下的类型定义。有一份电文中共使用五个字符：a、b、c、d、e,它们的出现频率依次为8、14、10、4、18，请构造相应的哈夫曼树(左子树根结点的权小于等于右子树根结点的权)，求出每个字符的哈夫曼编码。3.有初始的无序序列
8、为 98,65,38,40,12,51,100,77,26,88,给出对其进行归并排序(升序)的每一趟的结果。五、设计题(每小题 6 分，共 18 分)1.假设用一个循环单链表来表示队列(称为循环链队)，该队列中只设一个队尾指针 rear,不设队首指针。请编写向循环链队中插入一个元素X 的过程。2.以邻接表为存储结构，写出连通图的深度优先搜索算法。3.设有一组关键字 19,01,23,14,55,20,84,27,68,11,10,77,采用散列函数：H(key)=key MOD 13,采用线性探测法解决冲突，试在018 的散列地址空间中对该关键字序列构造散列表。浙江省 2001 年 10 月
9、高等教育自学考试数据结构导论试题参考答案课程代码：02142 一、单项选择题(每小题 1 分，共 14 分)1.C 2.B 3.D 4.B 5.A 6.C 7.B 8.C 9.A 10.C 11.B 12.D 13.C 14.C 二、判断题(每小题 2 分，共 20 分)1.2.3.4.5.6.7.8.9.10.三、填空题(每小题 2 分，共 30 分)1.(1)数据表示(2)数据处理。2.datastructure。3.(1)在单链表第一个结点之前增设的一个类型相同的结点(2)表结点中的第一个结点。4.a、b、c、d。5.(1)顺序存储结构(2)链表存储结构。6.log2N+1。名师资料总结
10、-精品资料欢迎下载-名师精心整理-第 3 页，共 7 页 -7.(1)先根遍历(2)后根遍历。8.1。9.(1)散列函数(2)冲突。10.(1)确定待查元素所在的块(2)在块内查找待查的元素。11.桶。12.(1)逻辑结构(2)物理结构。13.(1)顺序(2)直接。14.冒泡排序。15.归并。四、应用题(每小题 6 分，共 18 分)1.顺序实现：const maxsize=100.顺序表的容量typedatatype=record 档案数据类型name string 10.姓名number integer.学号boolean.性别ageinteger.年龄end.typeslist=reco
11、rd dataarray 1.maxsize of datatype.last integer.end.链接实现：typepointer=node.node=record name string 10.姓名number interger；学号sex boolean.性别ageinteger.年龄next pointer.结点的后继指针end.list=pointer.542212104800 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 7 页 -2.哈夫曼树为：3214181 0 101 1 cb e da 相应的哈夫曼编码为：a:001 b:10 c:01 d:000 e:
12、11 画出正确的哈夫曼树给4 分，写出相应哈夫曼编码给2 分3.初始无序序列：98 65 38 40 12 51 100 77 26 88 986538401251100772688第一次归并：65 98 38 40 12 51 77 100 26 88 第二次归并：38 40 65 98 12 51 77 100 26 88第三次归并：12 38 40 51 65 77 98 100 26 88第四次归并：12 26 38 40 51 65 77 88 98 100五、设计题(每小题 6 分，共 18 分)1.PROCEDUREinsert(VAR rearpointer.xinteger)
13、.VARhead,tmppointer;BEGIN new(tmp).tmp.data=x.if(rear=NIL)then 循环队列为空，新结点是队列的首结点BEGIN comrear=tmp.rear.next=tmp.END else 队列不空，将新结点插入在队列尾BEGIN head=rear.next.rear.next=tmp.名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 7 页 -rear=tmp.rear.next=head.END END.2.proceduredfs(g:adjlist.v1integer).从 v1 出发，深度优先遍历图gbegin wri
14、te(v1).visited(v1)=true.标志 v1 已访问p=g v1.link.找 v1 的第一个邻接点while pnil do if not(visited p.vertex)then dfs(g,p.vertex).p=p.next 找 v1 的下一个邻接点end.以邻接表为存储结构，连通图的深度优先搜索就是顺序查找链表。3.构造过程如下：H(19)=19 MOD 13=6 H(01)=01 MOD 13=1 H(23)=23 MOD 13=10 H(14)=14 MOD 13=1(冲突)H(14)=(1+1)MOD 19=2 H(55)=55 MOD 13=3 H(20)=2
15、0 MOD 13=7 H(84)=84 MOD 13=6(冲突)H(84)=(6+1)MOD 19=7(仍冲突)H(84)=(6+2)MOD 19=8 H(27)=27 MOD 13=1(冲突)H(27)=(1+1)MOD 19=2(冲突)H(27)=(1+2)MOD 19=3(仍冲突)H(27)=(1+3)MOD 19=4 H(68)=68 MOD 13=3(冲突)H(68)=(3+1)MOD 19=4(仍冲突)H(68)=(3+2)MOD 19=5 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 7 页 -H(11)=11 MOD 13=11 H(10)=10 MOD 13=
16、10(冲突)H(10)=(10+1)MOD 19=11(仍冲突)H(10)=(10+2)MOD 19=12 H(77)=77 MOD 13=12(冲突)H(77)=(12+1)MOD 19=13 因此，各关键字相应的地址分配如下：address(01)=address(14)=address(55)=address(27)=address(68)=address(19)=address(20)=address(84)=address(23)=10 address(11)=11 address(10)=12 address(77)=13 其余的地址中为空。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 7 页 -