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

积少成多，争取每天进步一点。 数据结构期末考试试题 一、单选题(每小题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．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时 应最好把它说明为( )参数 以节省参数值的传输时间和存储参数的空间 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．每次从无序表中顺序取出一个元素 把这插入到有序表中的适当位置 此种排序方法叫做--排序；每次从无序表中挑选出一个最小或最大元素 把它交换到有序表的一端 此种排序方法叫做--排序 14．快速排序在乎均情况下的时间复杂度为-- 最坏情况下的时间复杂度为-- 三、运算题(每小题6分 共24分) 1．假定一棵二叉树广义表表示为a(b(c d) c((( 8))) 分别写出对它进行先序、中序、后序和后序遍历的结果 先序： 中序； 后序： 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) 则利用堆排序方法建立的初始堆为-- 4．有7个带权结点 其权值分别为3 7 8 2 6 10 14 试以它们为叶子结点生成一棵哈夫曼树 求出该树的带权路径长度、高度、双分支结点数 带权路径长度：-- 高度：-- 双分支结点数：-- 四、阅读算法 回答问题(每小题8分 共16分) 1．VOldAC(ListL) { InitList(L)； InsertRear(L;25)； InsertFront(L 50)； IntaL4]＝{5 8 12 15 36}; for(inti＝0; i5; i++) if (a[i]％2＝＝0)InsertF