数据结构C语言版期末考试题(有答案).pdfVIP

数据结构C语言版期末考试题(有答案)--第1页 . 数据结构期末考试试题 一、单选题每小题2 分,共12 分 1 ．在一个单链表 HL 中,若要向表头插入一个由指针 p 指向的结点,则执行 B。 A ． HL ＝ps p 一next ＝HL B ． p 一next ＝HL ；HL ＝p C ． p 一next ＝Hl ；p ＝HL ； D ． p 一next ＝HL 一next;HL 一next ＝p ； 2 ．n 个顶点的强连通图中至少含有B。 A.n—l 条有向边 B.n 条有向边 C.nn—1 ／2 条有向边 D.nn一1条有向边 3.从一棵二叉有哪些信誉好的足球投注网站树中查找一个元素时,其时间复杂度大致为 C 。 A.O1 B.On C.O1Ogzn D.On2 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 ．On B ．O1 C ．On2 D ．O10g2n 二、填空题每空1 分,共28 分 1 ．数据的存储结构被分为顺序结构 链接结构 索引结构 散列结构四种。 2 ．在广义表的存储结构中,单元素结点与表元素结点有一个域对应不同,各自分 别为值域和子表指针域。 1 / 37 数据结构C语言版期末考试题(有答案)--第1页 数据结构C语言版期末考试题(有答案)--第2页 . 3 ．——中缀表达式 3十x*2.4／5—6所对应的后缀表达式为————。 4 ．在一棵高度为h的3叉树中,最多含有—3h一1／2—结点。 5 ．假定一棵二叉树的结点数为18,则它的最小深度为—5—,最大深度为—18—· 6 ．在一棵二叉有哪些信誉好的足球投注网站树中,每个分支结点的左子树上所有结点的值一定—小于— 该结点的值,右子树上所有结点的值一定—大于—该结点的值。 7 ．当向一个小根堆插入一个具有最小值的元素时,该元素需要逐层—向上—调 整,直到被调整到—堆顶—位置为止。 8 ．表示图的三种存储结构为邻接矩阵 邻接表 边集数组。 9 ．对用邻接矩阵表示的具有 个顶点和e条边的图进行任一种遍历时,其时间 复杂度为—O 2—,对用邻接表表示的图进行任一种遍历时,其时间复杂度为 —Oe—。 10 ．从有序表12,18,30,43,56,78,82,95中依次二分查找43和 56元素时,其查 找长度分别为—1—和—3—· 11 ．假定对长度 ＝144的线性表进行索引顺序查找,并假定每个子表的长度均 为12,则进行索引顺序查找的平均查找长度为—13—,时间复杂度为—12—· 13 ．每次从无序表中顺序取出一个元素,把这插入到有序表中的适当位置,此种 排序方法叫做—插入—排序 ；每次从无序表中挑选出一个最小或最大元 素,把它交换到有序表的一端,此种排序方法叫做—选择—排序。 14 ．快速排序在乎均情况下的时间复杂度为 —Onlog n—,最坏情况下的时间 2 复杂度为—O —。