还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
判断题
11.数据的逻辑结构与数据元素本身的内容和形式无关
2.线性表的逻辑顺序与物理顺序总是一致的
3.若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点,则它一定是该子树的中序遍历结果序列的最后一个结点
4.对于同一组待输入的关键码集合,虽然各关键码的输入次序不同,但得到的二叉搜索树都是相同的
5.最优二叉搜索树的任何子树都是最优二叉搜索树
6.在二叉搜索树上插入新结点时,不必挪移其它结点,仅需改动某个结点的指针,使它由空变为非空即可
7.有n nl个顶点的有向强连通图至少有n条边
8.连通分量是无向图中的极小连通子图
9.二叉树中任何一个结点的度都是
210.单链表从任何一个结点出发,都能访问到所有结点1L线性表的长度是线性表占用的存储空间的大小
12.队列只能采用链式存储方式
13.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关
14.由二叉树的先序序列和中序序列能惟一确定一棵二叉树
15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数
16.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同
17.数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运算三个方面
18.线性表中的每一个结点最多惟独一个前驱和一个后继
19.二叉排序树查找总比顺序查找速度快
20.对具有n个顶点的连通图进行深度优先遍历,所得顶点序列是惟一的
21.线性表中各个数据元素的类型必须是相同的
22.R树是一种特殊的二叉树
23.栈可视为一种特殊的线性表
24.快速排序总是比其它排序方法快
25.使用双向链表存储数据,可以提高查找定位运算的速度
26.最小生成树是边数至少的生成树A[1…n]中查找值为k的元素,若找到则输出其位置i l〈二i〈二n,否则输出0作为标志;2找出数组A[1…n]中元素的最大值和次最大值本小题以数组元素的比较为标准操作20写出下面二叉树的中序遍历结果21若栈为S,且已知popS=A,试说明下列等式是否成立Pop pushS,A=push S,popS;22对于下图,从顶点1出发,分别按深度优先搜索和广度优先搜索方法遍历,写出相应的顶点序列
23.已知下图所示双向循环链表L=a,b,c,d o请写出将该表转换为L=b,a,c,d的简
24.对于给定字符串,1234+-X/15678,试写出删除串中的+-X/的算法25算法与程序有何不同?,为何要引出算法概念?,如何评价算法的时间、空间复杂性及好坏?26已知线性表a,a,a中的元素值按递增有序罗列,选用向量结构存放试编写算12n法删除线性表中值介于C与d c=d之间的元素
27.说明栈和队列与线性表的异同点
28、给定一组元素值
17、
28、
54、
30、
27、
94、
15、
21、
83、40,用这一组元素值构造一棵哈夫曼树29如果队列中不设表头结点,如图所示,并令front=rear=null表示队列空,试写出实现队列的三个基本操作(入队、出队、判空)front
30、设一个有叙文件的关键字为2,5,8,11,13,17,25,36,47,55,60,63,65,67,76,84,当用折半查找算法查找关键字55时,试决定关键字的比较次数
31、抽象数据类型(ADT)与面向对象方法有何关系?使用ADT的优点有哪些?
32、给出一组关键字{12,2,16,30,8,4,10,20,6,18}写出按下上升排序时,用汽泡排序方法排序的每一趟排序结束状态
33、试写出一个将已知字符串所有字符倒过来重新罗列的算法例如ABCDEF改为FEDCBA
34、试描述数据结构的概念与程序设计语言中数据类型概念的区别
35、试设计算法,求循环链表中结点的个数,并删除表中的第一个结点a
二、单选题1向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要挪移()个元素A.8B.
63.5C.63D.72设有一个二维数组假设A
[0]
[0]存放位置在644,A
[2]
[2]存放位置在676,每个元素占一个空间,则A⑶⑶在()位置,°)表明常10进数表示
(10)A.692B.626C.709D.724
(10)
(10)
(10)
(10)3N个顶点的连通图至少有()条边A.N-l B.N C.N+1D.04下面程序的时间复杂度为forint i=0;im;i++A.0m2B.0n2C.0m*n D.0m+nforint j=0;j〈n;j++a[i]5设单链表中结点的结构为(data,link)已知指针q所指结点是指针p所指结点的直接前驱,o若在*q与*pN间插入结点*s,则应执行下列哪一个操作()A.s-link=p-link;p-link=s;B.q-link=s;s-link=p;C.p-link=s-link;s-link=q;D.p-link=s;s-link=q;6栈的插入和删除操作在()进行A.栈顶B.栈底C.任意位置D.指定位置A.3,2,12,1,3C.3,1,2D.1,3,2BO.C.空表D.a7若让元素1,2,3挨次进栈,则出栈次序不可能浮现哪种情况()9采用邻接表存储的图的深度优先遍历算法类似于二叉树的()OA.中序遍历B.前序遍历C.后序遍历10每次从D.按层次遍历无序表中挑选出一个最小或者最大元素,把它交换到有序表的一端,此种排序方法叫做()序A.插入B.选择C.交换D.外排序
11.一个顺序表有255个对象,采用顺序搜索查找,平均数据比较次数为()A.128B.127C.126D.
25512.含5个结点(元素值均不相同)的二叉树搜索树有()种A.54B.42C.36I).
6513.数据结构中,与所使用的计算机无关的是数据的结构(A)存储;(B)物理;(C)逻辑;(D)物理和存储;
14.在链表中进行操作比在顺序表中进行操作效率高(A)顺序查找;(B)折半查找;(C)分块查找;(D)插入;
15.树结构最适合于用来表示(A)元素间具有分支和层次关系的数据;(B)无序数据;(C)有序数据;(D)元素间没有关联的数据;
16.借助于栈,输入A、B、C、D四个元素,则不可能浮现的输出序列为oA ABCD;B CABD;C DCBA;D BACD;
17.从理论上讲,将数据以___________结构存放,则查找一个数据所用时间不依赖于数据个数N二叉查找树;B链表;C二叉树;D散列表;A
18.头指针为L的单循环链表,指针p所指结点为尾结点的条件为A pfnext=NULL;B pfnext=L;C p=L;D p=NULL;19直接选择排序的时间复杂度为n为元素的个数0n;B Ologn;C0n logn;D0n2Ao2220散列存储中,碰撞或者称冲突指的是________________oA两个元素具有相同序号;B不同的关键字对应于相同的存储地址;C两个记录的关键字相同;D数据元素过多;
三、填空题
1.算法是一个有穷的指令集,它为解决某一特定任务规定了一个运算序列它应具有输入、输出、、有穷性和可执行性等特性
2.当问题的规模n趋向无穷大时,算法执行时间Tn的数量级被称为算法的
3.在一棵度为3的树中,度为2的结点个数是1,度为0的结点个数是6,则度为3的结点个数是
4.当用长度为n的数组顺序存储一个栈时,若用top=n表示栈空,则表示栈满的条件为
5.对序列49,38,65,97,76,27,13,50采用快速排序法进行排序,以序列的第一个元素为基准元素得到的划分结果是o
6.对于一棵具有n个结点的树,该树中所有结点的度数之和为o
7.请指出在顺序表{
5、
11、
23、
35、
51、
64、
72、
85、
88、
90、98}中,用折半查找关键码30需做次关键码比较
8.若线性表采用顺序存储结构,每一个元素占用4个存储单元,第一个元素的存储地址为100,则第12个元素的存储地址是o
9.在一个长度为n的顺序表中,向第i个元素1W iWn+1之前插入一个新元素时,需要向后挪移个元素
10.设有两个串p和q,求q在p中首次浮现的位置的运算称作
11.判定一个循环队列QU最多元素为m为满队列的条件是o
12.在一个无向图的邻接表中,若表结点的个数是明则图中边的条数是条
13.对于一个具有n个顶点的图,若采用邻接矩阵表示,则矩阵大小为
14.有N个顶点的无向连通图至少有条边
15.在下图所示的链表中,若在指针p所指的结点之后插入数据域值相继为a和b的两个结点,则可用下列两个语句实现该操作,它们挨次是和HD~41H~11K I-I~I1AlP“b
16.设根结点的层数为0,定义树的高度为树中层数最大的结点的层数则高度为k的二叉树具有的结点数目,至少为,最多为o
17.单链表中指针p所指结点惟独一个后继结点的条件是o
18.深度为k的满二叉树有_______________个结点
19.设s=I AMA STUDENT,t=GOOD WORKER,CONCATSubstrs,6,2,t
20.文件在外存储器组织结构的三种形式分别为、___________________和o
21.对广义表LS=a,b,c,,d,e进行HEAD和TAIL运算的结果分别是________、O22二维数组A[L.20,L.10]按行优先顺序存储,每一个元素占4个单元,月5[1,1]的地址是1000,则A[18,9]的存储地址是o.深度为k的彻底二叉树至少有__________个结点,至多有___________仝结点23ISAM文件由、柱面索引、磁道索引和主文件组成2425在单链表中,将指针p所指结点插到指针s所指结点后面的两步主要操作语句为,O
26.设二维数组A[L.20,
1..10]按行优先存储,每一个元素占4个单元,A[l,1]的地址是100,则A[5,5]的地址是.
27.散列既是一种___________方式,又是一种查找方法28抽象数据类型定叉甬部份组成
四、程序阅读填空
1.在顺序表中第i个位置插入新元素Xtemplate classType intSeqListType::Insert Typex,int i{if i0||ilast+l||last==MaxSize-l return0;〃插入不成功else{last++;for;ji;j___________________________»data[i]=x;return1;〃插入成功}
2.直接选择排序的算法template classType void SelectSortdatalistTypelist{forint i=0;ilist.CurrentSize-1;i++;}template classType viodSelectExchangedatalistTypelist,const inti{int k=i;forint j=i+l;j list.CurrentSize;j++iflist.Vector[j].getKeylist.Vector[k].getKey__________________________________;〃当前具有最小关键码的对象if k!=i Swaplist.Vector[i],list.Vector[k];〃交换
3、删去链表中除表头结点外的所有其他结点template classType voidListType::MakeEmpty{ListNodeType*q;while firstflink!二NULL{//将表头结点后第一个结点从链中摘下delete q;//释放它last二first;〃修改表尾指针
4、基于有序顺序表的折半搜索递归算法Element为有序顺序表template classType intorderedListType::BinarySearchconst Typex,const intlow,const inthighconst intmid=-1;iflow=high{ifElement[mid].getKeyx mid=BinarySearch;else ifElement[mid].getKeyx mid=BinarySearchx,low,mid-1;return mid;}
5、在顺序表中第i个位置插入新元素x oint insertsqlist*L,datatype x,inti{intj;表满,不能插入!上溢;}if L-n==maxsize{coutw”n;return-1非法插入位置!if{coutw”n”;return0;}forj=L-n;j=i;j-〃节点后移L-data[j]=L-data[j-1];________________________________;//插入x〃修改表长L-n++;〃插入成功Return1;
6、直接选择排序的算法voidSelectSortlist R,intn{intij,k;趟排序for i=1;i=n-1;i++{//n-1;//在当前无序区中找键值最小的记录forj=i+1jv=n,j++R[k]ifR[j].keyR[k].key;ifk!=i{R
[0]=R[i];R[i]=R[k];R[k]=R
[0];}
五、简答题
1.线性表可用顺序表或者是链表存储,此两种存储表示各有哪些优缺点?
2.设有一个输入数据的序列是{46,25,78,62,12,37,70,29,试画出从空树起,逐个输入各个数据而生成的二叉搜索树
3.用广义表的带表头结点的存储表示法表示下列集合A=B=6,2C=5,3,XD=B,C,AE=B,D1----------
54.上图所示为一有向图,请给出该图的下述要求1给出每一个顶点的入度和出度;2以结点3为起始结点,分别画出该图的一个深度优先生成树和一个宽度优先生成树;3给出该图的邻接矩阵;4给出该图的邻接表;
5.对于如上图所示的有向图,试写出:1从顶点
①出发进行深度优先搜索所得到的深度优先生成树;2从顶点
②出发进行广度优先搜索所得到的广度优先生成树;
6.已知二叉树的先序、中序和后序序列分别如下,但其中有一些已含糊不清,试构造出该二叉树先序序列_BC_EF_中序序列BDE_AG_H后序序列_DC_GH_A.分析下列两个程序段的运行时间时间复杂度7void mysteryintn{inti J,k;for i=1;in;i++for j=i+1;j v=n;j++for k=1;k=j;k++;void oddintn{intij,x=0,y=0;for i=1;i=n;i++if oddi{forj=i;j=n;j++x++;forj=1;j=i;j++y++;}
9.有一组数据25,50,70,21,4,18,100,43,7,12现采用汽泡排序算法进行排序,写出每趟排序的结果,并标明第一趟数据的挪移情况
10.数据结构与软件的关系是什么?解决实际问题时,选取或者设计数据结构的原则是什么?
11.说明下列概念是否正确
①线性表在物理存储空间中也一定是连续的;
②链表的物理存储结构具有同链表一样的顺序;
③链表的删除算法很简单,因为当删去链表中某个结点后,计算机会自动地将后继的各个单元向前挪移使用双向链表存储数据,可以提高查找定位的速度
12.写一个算法,借助栈将一个单链表倒置提示可以使用栈的基本运算也即,将下面的单链表:13描述以下概念的区别头指针、头结点、首元结点头指针变量和头结点的作用?并比较顺序存储结构和链式存储结构的优缺点14哪些链表可以仅由一个尾指针来惟一确定即从尾指针出发能访问到链表上任何一个结点15设n为正整数,试确定下列三段程序中带下划线语句的频度a inti=1,k=0;while i=n-1{k=k+10*i:i=i+1;}b inti=1,j=0;while i+j=n ifii i++:else i++;c inti=1,k=0;while-i=n-1{k=k+10*i:i++;16已知s=xyz+*,t=x+z*y,试利用联接、求子串和置换等串的基本运算,将s转化为t17有如下12个整数23,37,7,79,29,43,73,19,31,61,23,47,按气泡排序方法将这组整数排序,分别写出每遍处理后的数列18逻辑结构与存储结构是什么关系?,有何区别?19设计求解下列问题的C++语言算法,并分析其最坏情况时间复杂度及其数量级1在数组。