数据结构试题试题及答案.doc

《数据结构试题试题及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、　　　　　 单选题（每小题2分，共8分）1.在一个长度为n的线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为　 C　 。A.n 　　　　　　　　B.n/2　　　 　　　 C.(n+1)/2　　　　 D.(n-1)/22 。以下数据结构中哪一个是非线性结构？(D)A.队列　　B.栈C.线性表　　D.二叉树3.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为(D)A.1

2、，2，3B.9，5，2，3C.9，5，3D.9，4，2，34.设有6个结点的无向图，该图至少应有(A)条边才能确保是一个连通图。A.5B.6C.7D.85．在下列排序方法中，（c）方法平均时间复杂度为0(nlogn)，最坏情况下时间复杂度为0(n2)；（d）方法所有情况下时间复杂度均为0(nlogn)。a.插入排序  b.希尔排序  c.快速排序  d.堆排序 6．具有m个结点的二叉排序树，其最大深度为（f），最小深度为（b）。a.log2m       b.└log2m┘+1    c.m/2d.┌m/2┐-1

3、    e.┌m/2┐         f.m  7．下列排序方法中，属于不稳定的排序方法是(A)A.直接插入排序法B.冒泡排序法C.基数排序法D.归并排序法8在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(  C)A.快速排序       B.堆排序C.归并排序       D.基数排序9设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表

4、示。A．688B．678C．692D．69610由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D5311，某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（B）的二叉树。A、空或只有一个结点B、高度等于其结点数D、任意结点无右孩子C、任意结点无左孩子12将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为___A___。A.98B.99C.50D.4813.设有100个元素，用折半查找

5、法进行查找时，最大比较次数是____D_。A.25B.50C.10D.714.在含有n个项点有e条边的无向图的邻接矩阵中，零元素的个数为___D_____。A.eB.2eC.n2-eD.n2-2e15.图的深度优先遍历类似于二叉树的___A____。A.先序遍历B.中序遍历C.后序遍历D.层次遍历16.设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为_____C__。A.O(1)B.O(log2n)C.O(n)D.O(n2)17.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序

6、的时间复杂度是____B____A．O（1）B.O（n）C.O(nlogn)D.O(n2)18．队和栈的主要区别是____D____A.逻辑结构不同B.存储结构不同C.所包含的运算个数不同D.限定插入和删除的位置不同19．链栈与顺序栈相比，比较明显的优点是___D_____A.插入操作更加方便B.删除操作更加方便C.不会出现下溢的情况D.不会出现上溢的情况20．在目标串T[0…n-1]=”xwxxyxy”中，对模式串p[0…m-1]=”xy”进行子串定位操作的结果___C____A.0B.2C.3D.521．已知

7、广义表的表头为A，表尾为(B,C)，则此广义表为____B____A.（A,(B,C)）B.（A,B,C）C.(A,B,C)D.((A,B,C))22．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为420，A[3][3]的存储地址为446，则A[5][5]的存储地址为___C____A.470B.471C.472D.47323.向堆中插入一个元素的时间复杂度为____A____。A、O(log2n)B、O(n)C、O(1)D、O(nlog2n)24.用某种排序方法对关键字序列（2

8、5，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况是如下____D____：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是________A.选择排序B.希尔排序C.归并排序D.快速排序25.线性表若采用链表存储结构