数据结构试题数据结构试题

1、数据结构试题3一、选择题（每小题2分，共8分）1. 若需要利用形参直接访问实参，则应把形参变量说明为（）参数。A.指针B.引用C.值2. 在一个单链表HL中，若要在指针q所至结点的后面插入一个由指针p所指向的结点，则执行（）。A. q-next=p-next; p_next=q;B. p-next=q-next; q=p;C. q-next=p-next; p-next=q;D. p-next=q-next; q-next=p;3. 在一个顺序队列中，队首指针指向对首元素的（）位置。A.后一个B.前一个C.当前4 向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。A. O（long2n）

2、B. 0（n）C. 0（1） D. O（nlong2n）二. 、填空题（每空1分，共同社2分）1. 数据的存储结构被分为 , 和四种。2. 对于一个顺序存储的线性表，在表头插入元素的时间复杂度为 ,在表尾插入元素的时间复杂度为 。3. 在稀疏矩阵所对应的三远组线性表中，每个三元组元素按 为主序，为辅序的次序排列。4. 在广义表的存储结构中，单元表结点与表元素结点有一个域对应不同，各自分别为 域和 域。5. 中级表达式3+x*（2.4/5-6）所对应的后缀表达式为 。6. 在一棵高度为h的3叉树中，最多含有 结点。7. 假定一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。8. 在一课

3、二叉树搜索中，每个分支结点的左子树上所有的结点的值一定 该结点的值，右子树上所有的结点的值一定该结点的值。9. 当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层 调整，知道被调整到 位置为止。10. 表示图的三种存储结构为 ， 和 。11. 对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为 ，对用邻接表表示的图进行任一种遍历时，其时间复杂度为 。12. 从有序表（12，18, 30,43,56，78，82, 95）中依次二分查找43和56元素时，其查找长度分别为 和。13. 假定对长度n=144的线性表进行索引查找，并假定每个子表的长度均为，则进行索引查找的平

4、均查找长度为，时间复杂度为 。14. 一棵B_树中的所有叶子结点均处在 上。15. 每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做排序；每次从无序表中挑选出一个最小或最大兀素，把它交换到有序表的一端，此种排序方法叫做排序。16. 快速排序在平均情况下的时间复杂度为 ，在最环情况下的时间复杂度为三. 、运算题（每小题6分，共24 分）先根: 后根：按层：2 .已知一个带全图的定点集V和边集G分别为：V=0，1，2，3，4，5，6，7；E=（0, 1）8，（0, 2）5，（ 0，3）2，（ 1，5）6，（ 2，3）25，（ 2，4）13（ 3，5）9；则求出该图的最

5、小生成树的权。最小生成树的泉：3 .对于线性表（18，25，63，50，41，32，90，66）进行三列存储时，若选用H（K）=K%11作为散列函数，则散列地址为0的元素有个，散列地址为3的元素有 个，散列地址为8的元素有个。4 .假定一组纪录的排序码为（46，79，56，38，40，80，25，34 ），在对其进行快速排序的过程中，进 行第一次划分后得到的排序码序列为。四、阅读算法，回答问题（每小题8分，共16分）1 . Void AD（LNode*&HL）Insert（HL，30）;Insert（HL，50）;Delete（HL，26）;Delete（HL，55）;假定调用该算法时以 HL

6、为表头指针的单链表中的内容为（15，26，48，55），则调用返回后该单链表中的 内容变为：2 . Void AI(adjmatrixGA ， int I， int n)coutvvlvv;visitedl=true;for(int j=0;jdata=item;BST=p;else if(itemdata);else;六. 编写算法(10分)编写向类型为List的线性表L中第I个元素为值插入一个元素的算法，假定不需要对I的值进行有效性检查,同时不需要检查存储空间是否用完。Void Insert(List&L ，int I， ElemType x)答案：1、B . 2、D . 3、B .4、A

7、二、填空1、顺序结构、链接结构、索引结构、散列结构(次序无先后)2、O (n )、0(1)3、行号、列号4、值(或data )、子表指针(或 sublist )5、3x2.45/6-*+6、(3h-1)/27、5 188、小于大于9、向上堆顶10、 邻接矩阵邻接表 边集数组(次序无先后)11、O (n2 )0(e)12、1 313、13 0 ()14、同一层15、插入选择16、0 (nlog2n)0(n2)三、运算题1、先根：a,b,e,c,f,h,l,g,d;后根：e,b,h,I,f,g,c,d,a;按层：a,b,c,d,e,f,g,h,I;2、最小生成树的权：343、1 1 2每个数据占2分4、( 40 ，34 ，25 ,38，46, 80，56，79)四、阅读算法，回答问题。1、( 15，30，48，50)GA所表示的图2、从初始点Vi出发深度优先搜索遍历由邻接矩阵五、算法填空，在画有横线的地方填写合适的内容。p-left=p-right=nullinsert(bst-left,item)insert(bst-rig