数据的相关试题

1、1 / 14一、单选题 (每小题 2 分，共 12 分)1.在一个单链表 HL 中，若要向表头插入一个由指针p 指向的结点，则执行 ( ) 。A HL = ps p 一next = HLB p 一next = HL; HL= p3C . p 一next = Hl; p= HL;D . p 一next = HL 一next;HL 一next = p；2. n 个顶点的强连通图中至少含有()。A.n l 条有向边 B.n 条有向边C.n(n1)2 条有向边D.n(n 一 1)条有向边3. 从一棵二叉搜索树中查找一个元素时，其时刻复杂度大致 为 ( ) 。A.O(1) B.O(n)C.O(1Ogzn

2、) D.O(n2)4 由权值分不为 3，8，6，2，5 的叶子结点生成一棵哈夫 曼树，2 / 14它的带权路径长度为 ( ) 。A 24 B 48C 72 D 535当一个作为实际传递的对象占用的存储空间较大并可能需 要修改时， 应最好把它讲明为 ( ) 参数， 以节约参数值的传输 时刻和存储参数的空间。A. 整形 B. 引用型C.指针型 D.常值引用型6向一个长度为 n 的顺序表中插人一个新元素的平均时刻复 杂度为 ( ) 。A O(n) B O(1)C O(n2) D O(10g2n)二、填空题 (每空 1 分，共 28 分)1数据的存储结构被分为、 、和四种。2在广义表的存储结构中，单元

3、素结点与表元素结点有一3 / 14个域对应不同，各自分不为域和域。3中缀表达式 3 十 x*（2.4 56） 所对应的后缀 表达式为。4在一棵高度为 h 的 3 叉树中，最多含有结点。5假定一棵二叉树的结点数为 18，则它的最小深度为，最大深度为6在一棵二叉搜索树中，每个分支结点的左子树上所有结 点的值一定该结点的值， 右子树上所有结点的值一定 该结点的值。7当向一个小根堆插入一个具有最小值的元素时，该元素 需要逐层调整，直到被调整到位置为止。8表示图的三种存储结构为、和。9.对用邻接矩阵表示的具有n 个顶点和 e 条边的图进行任一种遍历时，其时刻复杂度为一一，对用邻接表表示的图进行任一种遍历

4、时，其时刻复杂度为一一。4 / 1410.从有序表（12，18，30，43，56，78，82，95）中依次二分查找 43 和 56 元素时，其查找长度分不为一一和-11.假定对长度 n= 144 的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为一一，时刻复杂度为-12 .一棵 B树中的所有叶子结点均处在一一上。13 .每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做排序； 每次从无 序表中选择出一个最小或最大元素，把它交换到有序表 的一端，此种排序方法叫做排序。14 .快速排序在乎均情况下的时刻复杂度为一一，最坏情况下的时刻复

5、杂度为 三、运算题 （每小题 6 分，共 24 分）1 假定一棵二叉树广义表表示为 a（b（c ，d），c（ ，8） ，分不写出对它进行先序、中序、后序和后序遍历的结果。先序：中序；5 / 14后序：2.已知一个带权图的顶点集 V 和边集 G 分不为：V = 0 , 1, 2, 3, 4, 5；E=（0， 1）8， （0， 2）5， （0， 3）2， （1， 5）6， （2，3）25， （2，4）13, （3, 5）9, （4, 5）10 ,则求出该图的最小生成树的权。最小生成树的权；3假定一组记录的排序码为 （46 , 79, 56, 38, 40, 84, 50, 42） ,则利用堆排序方

6、法建立的初始堆为。4有 7 个带权结点，其权值分不为 3，7，8，2，6， 10，14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带 权路径长度、高度、双分支结点数。带权路径长度： 高度： 双分支结点数：四、阅读算法，回答问题 (每小题 8 分，共 16 分)6 / 141 VOldAC(List&L)InitList(L) ；InsertRear(L;25) ；InsertFront(L ，50) ；IntaL4 = 5, 8, 12, 15, 36;for(i nti = 0; i5; i+)if (ai%2= 0)1 nsertFront(L , ai);elselnsert

7、Rear(L ，ai) ；该算法被调用执行后，得到的线性表 L 为：2 void AG(Queue&Q)InitQueue(Q) ；7 / 14inta5= 6 , 12, 5, 15, 8;for(int i=0;i5; i+)QInsert(Q, ai);QInsert(Q，QDelete(Q) ；QInsert(Q, 20)；QInsert(Q, QDelete(Q) 十 16) ；while(!QueueEmpty(Q)coutQDelete(Q) ”；该算法被调用后得到的输出结果为：五、算法填空, 在画有横线的地点填写合适的内容 (每小题 6 分,共 12 分 )1 从一维数组 An) 中二分查找关键字为 K 的元素的递归算法，若查找成功则返回对应元素的下标，否则返回一1。IntBinsch(ElemTypeA，Intlow ，int high ， KeyTypeK)if(low= hig