《数据结构》考试样卷

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

1、一、选择题1.从物理结构上可以把数据结构分为()两大类。A.动态结构、静态结构B.顺序存储结构、链式存储结构C.线性结构、非线性结构D.初等结构、构造型结构2.下而关丁线性表的叙述中，错误的是哪一个?()A.线性表采用顺序存储，必须占用•段连续的存储单元。B.线性表采用顺序存储，便于进行插入和删除操作。C.线性表采用链式存储，不必占用一片连续的存储单元。D.线性表采用链式存储，使于进行插入和删除操作。3.6个元素按照6,5,4,3,2,1的顺序进栈，下列哪一个不是合法的出栈序列?()A.5,4,3,6,1,2

2、B.4,5,3,1,2,6C.3,4,6,5,2,1D・2,3,4,1,5,64.设有循环队列A[0若用front和rear分別表示队头元素和队尾元素在数组屮的下标，则当前队列中的兀素数是()。A.(rear-front+m)%mB.rear-front+1C・rear-frontD・rear-front5.若串S1='ABCDEFG‘，S2='9898z/S3='ABC,,贝lj执行substr(SI,length(S2),length(S3))Jo»其结果为()。A.DEFB.EFGC・ABCDD・CDE

3、F1.若对n阶对称矩阵A以行序为主序方式将其位于I—.ft的元索(含主对角线上所有元素)依次存放于维数组BEl..(n*(n+l))/2]中，则元素a(i,j)(ivj)在数纽.B中的下标为(儿(注意：设数组下标从0开始)A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+l)/2+i7.卜面几个字符串编码集合中,不是前缀编码的是(B.{11,101,1010,0111}C・{00,010,0110,1000}D.{1,01,001,0000}8.卜•列哪一种图的邻接矩

4、阵是对称矩阵？()A.有向图B.无向图C.A0V网D・A0E网9.在对有向图G进行拓扑排序所得到的拓扑序列中，若顶点Vi的位置在顶点Vj之前，则卜•列情形不可能出现的是()。A・G屮有弧vVi,Vj>B・G屮有一条从Vi到Vj的路径c.G中没有D.G中有一条从Vj到Vi的路径10.下而关丁•折半査找(或—分査找)的叙述正确的是()。A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序，而且只能从小到大排列C.表必须有序冃表屮数据元素的类型必须是整型，实型或字符型D.表必须有斥，且表只能以顺斥方

5、式存储二、判断题1.算法的确定性是指•个算法在任何情况卜•都有相同的输出。()1.取得线性表的第i个元素的时间同i的大小有关。（）2.一个稀疏矩炸A采用三元组顺序表表示，若把三元组屮所有行的行下标与列下标的值耳换，并把A的行数和列数的值互换，则完成了A的转迓运算。（）3.对丁任何一个非空广义表，GetTail（即''取表尾〃）运算，其结果可以是表，也可以是原子。（）4.对•棵一叉树进行层次遍历吋，应借助于个栈。（）5.采川邻接矩阵表示无向图，则图中的边数等于邻接矩阵中非零元素之和的一半。（）6./I-：AOE

6、网屮，若缩短一条关键路径上某个活动的时间，则整个丁程的时间也就必定缩短。（）7.若S表示当前已求得最短路径的终点的集合，则求得的卜一条最短路径（设其源点为V,终点为x）或者是弧,或者是从Vlll发经过S中所有顶点而到达x的那条路径。（）8.在任意•棵非空一叉排序树中，插入某结点后接着又将其删除，则所得二叉排序树与原树相同。（）9.简单选择排序算法中，关键字比较的次数与待排序序列的初始状态无关。（）三、填空题1•在一个氏度为n的顺序表屮第i个元素（l<=iv=n）之前插入一个元素，需向后移动个元素,然

7、后再删除（前血的插入操作完成后）第i个（l<=i<=n+l）兀素，需向前移动个兀素。2・设循环队列的最人队列员度为MAX,队头指针和队尾指针分别为front和rear,则队列为空的条件是，队列为满的条件是。3.栈的运算遵循的原则，栈中允许插入和删除元素的一端称为。4•包含n个结点的完全一叉树的深度是,深度为k的一•叉树全多有个结点。5・平衡二叉树中结点的平衡因子是指,树中所有叶子结点的平衡因子是。四、问答题1.什么是头结点，在线性衣的链式存储结构中，附设头结点有何用处？2.若一棵一义树中度为0、K2的结点数分

8、别为no、nl和n2,试证明：nO=n2+：L（要写出推导过程）。3・一叉树如下图所示，分別对It•进行先序、屮序、后序、层次遍历，写出每种遍历所得到的序列。图4一34•设一个哈希表含13个记录（即表长hashsize为13）,其下标从0到12,采川线性探测再散列解决冲突。请按以下要求，将关键字{10,100,32,45,58,126,3,29,200,400,0}散列到表中。要求：哈希函数采用除留