数据结构习题课

《数据结构习题课》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一、选择题从物理结构上可以把数据结构分为A.动态结构、静态结构1.B.（）两大类。顺序存储结构、链式存储结构棊木结构、构造结构2.3.C.线性结构、非线性结构D.下述哪一条是顺序存储结构的优点？（）A.物理上相邻的元素在逻辑上也相邻B.插入运算方便C.删除运算方便D.可方便地用于各种逻辑结构的存储表示下而关于线性表的叙述中，错误的是哪一个？（）线性表采用顺序存储，线性表采用顺序存储，线性表采用链式存储，线性表采用链式存储，A.B.C.D.必须占用一段连续的存储单元。便于进行插入和删除操作。不必占用一片连续的存储单元。便于进行插入和删除操作。4・若某线性表最常用的操作是存取任一指定序号

2、的元素和在最后进行插入和删除运算，则利用（）存储方式最节省吋间。A.顺序表B.双链表5.6个元素按照6,5,4,3,2,C.带头结点的双循环链表D•单循环链表的顺序进栈，下列哪一个不是合法的出栈序列？（）B.4,5,3,1,2,6C•394,695,2,16.一个递归算法必须包括（A.递归部分)oB.C.循环部分D.7.执行完下列语句段后，intf（int终止条件利递归部分终止条件和循环部分i值为：（）return((x>0)?x*f(x-1):2);i=f(f(D)；B・4C.8D.无限递归A.28.若用front和rear分别表示循坏队列的队头元素和队尾元素在数组中的下标，则队列

3、为空吋有()oA•rear=front-1B•rear=front+1C•rear=front9.栈和队都是（）A.顺序存储的线性结构C•限制存取点的线性结构D•不能确定B.链式存储的非线性结构D.限制存取点的非线性结构10.一般來说，最快的排序算法是（A、归并排序B、快速排序11.一■组元素为（46,79,56,38,的一次划分结果为（)oC、插入排序D、Shell排序40,84）,则利用快速排序的方法，以第一个元素为基准得到)oA.(38,40,46,56,79,84)B.(40,38,46,79,56,84)D・(40,38,46,84,56,79)C.（40,38,46,56

4、,79,84）12.从未排序序列中依次取出一个元素与己排序序列中的元素依次进行比较，然后将其放在己排序序列的合适位置，该排序方法称为（）排序法。A.插入B.选择C.希尔D.二路归并14.20,9,A.3B.10C.15D.25对序列｛15,9,7,8,7｝则该次采用的增量是A.120,一1,4}用希尔排序方法排序，经一趟后序列变为｛15,-1,4,8,B.C.3D.215.设要将序歹!

5、（qzh,c,y,p,a,m,szrrd,f,x）按字母升序重新排序,（）是初始增彊为4的shell排序一趟扫描的结果；（）是以第一个元素为基准的一趟快速排序的结果。A.f,h,c,dzp,a,m,q

6、,r,s,y,x,d,fzx,rzhzm,y16.C.a,d,c,r,f,q,m,s,y,p,hzxD.hzc,q,pzaE.hzqzczy,azpzmzszd设无向图的顶点个数为n,则该图最多冇(zm,szrzd,fzxzy17.A・n-1B・n（n-1）/2C・要连通具有n个顶点的有向图，至少需要（）条边。n(n+1)/2)条边。D・0E・n*2A・n-丄B・nC.n+1在一个无向图中，所冇顶点的度数Z和等于所冇边数（入度之和等于所冇顶点出度之和的（）倍。18.D・2n）倍，在一个冇向图屮，所冇顶点的A.1/2B.2C.19.下列哪一种图的邻接矩阵是対称矩阵？A.有向图B.无向图

7、20.下列说法不正确的是（）。A.图的遍历是从给定的源点出发每一个顶点仅被访问一次B.遍历的基本算法有两种：深度遍历和广度遍历（）C.有向网D・C.D・D・无向网图的深度遍历不适用于冇向图图的深度遍历是一个递归过程）。21.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（A.G中有弧B.G中有一条从Vi到Vj的路径C.G中没冇弧D.G中冇一条从Vj到Vi的路径二、判断题1.算法的确定性是指一个算法在任何情况下都有相同的输出。（）2.取得线性农的第i个元素的时间同i的大小有关。（）3.对一棵二叉树进行层序遍历时，应借助于一个栈。（

8、）4.在任意一棵非空EST中，插入某结点后接着又将英删除，则所得BST与原树相同。（）5.在n个结点的无向图中，若边数大T-n-lz则该图必是连通图。（）6・有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（）7.无向图的邻接矩阵-•定是对称矩阵，有向图的邻接矩阵-•定是非对称矩阵。（）8.带权无向图的故小生成树必是唯一的。（）9.拓扑排序算法把一个无向图屮的顶点排成一个冇序序列。（）三、填空题1.己知如下程序段FORi:=nDOWNTO1DOBEG