“数据结构”期末考试试题一、单选题(每小题 2 分，共 12 分) 1．在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行( )。 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 个顶点的强连通图中至少含有( )。 A.n—l 条有向边 B.n 条有向边 C.n(n—1)／2 条有向边 D.n(n 一 1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n)C.O(1Ogzn) D.O(n2)4．由权值分别为 3，8，6，2，5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 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 十 x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为 h 的 3 叉树中，最多含有——结点。5．假定一棵二叉树的结点数为 18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找 43 和 56 元素时，其查找长度分别为——和——· 11．假定对长度 n＝144 的线性表进行索引顺序查找，并假定每个子表的长度均为，则进行索引顺序查找的平均查找长度为——，时间复杂度为——· 12．一棵 B—树中的所有叶子结点均处在——上。 13．每次从无序表中顺序取出一...
