数据结构期末考试试卷.docVIP

“数据结构”（刘大有）期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(B)。 A． HL＝ps p一next＝HL B． p一next＝HL；HL＝p3 C． p一next＝Hl；p＝HL； D． p一next＝HL一next;HL一next＝p； 2．n个顶点的强连通图中至少含有(B )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉有哪些信誉好的足球投注网站树中查找一个元素时，其时间复杂度大致为(C )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为(D )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( B )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为(A )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。(顺序结构，链式结构，索引结构，散列结构) 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。（值(或data) 子表指针(或sublist)） 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。（3 x 2．4 5／6一*十） 4．在一棵高度为h的3叉树中，最多含有——结点。（(3h 一1)／2） 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——·（5 18） 6．在一棵二叉有哪些信誉好的足球投注网站树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结 点的值。（小于 大于（或大于等于）） 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。（向上 堆顶） 8．表示图的三种存储结构为——、——和———。（邻接矩阵 邻接表 边集数组(次序无先后)） 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一 种遍历时，其时间复杂度为——。（O（n^2） O(e)） 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——·(1 3) 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长 度为——，时间复杂度为——·(13 O()) 12．一棵B—树中的所有叶子结点均处在——上。(同一层) 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做——排序；每次从无序表中挑 选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做——排序。（插入 选择） 14．快速排序在乎均情况下的时间复杂度为——，最坏情况下的时间复杂度为——。（O(nlog2n) O(n^2)） 三、运算题(每小题6分，共24分) 1．假定一棵二叉树广义表表示为a(b(c，d)，c(((，8)))，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序：a，b，c，d，e，f，e 中序；c，b，d，a，f，8，e 后序：c，d，b，e，f，e，a 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}， 则求出该图的最小生成树的权。 最小生成树的权；最小生成树的权：31 3．假定一组记录的排序码为(46，79，56，38，40，84，50，42)，则利用堆排序方法建立的初始堆为——。(84，79，56，4