2008数据结构考试试卷.doc

一、判断题（每小题2分，共20分） 要求：判断下列各题的说法是否正确，将结果填写下列表中，正确的划√，错误的划×。 1． 2． 3． 4． 5． 6． 7． 8． 9． 10． 1．对链表进行插入和删除操作时，不必移动结点。 2．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先有哪些信誉好的足球投注网站就能访问每个顶点，则该图一定是完全图。 3．二路归并时，被归并的两个子序列中的关键字个数一定要相等。 5．当一棵具有n个叶子结点的二叉树的带权路径长度（WPL）为最小时，称其树为哈夫曼（Huffman）树且二叉树的形状必是唯一的。 6．对一棵二叉树进行层次遍历时，应借助于一个栈。 7．哈希表（Hash）的平均查找长度与处理冲突的方法无关。 8．在顺序表中取出第i个元素所花费的时间与i成正比。　 9．哈夫曼树中不存在度为1的结点。 10．对任何数据结构链式存储结构一定优于顺序存储结构。 1．( ) A. 树 B. 串 C. 队列 D. 堆栈 2. 在一个单链表HL中，若要在指针q所指的结点的后面插入一个由指针p所指的结点，则执行的语句序列是( ) 。 A.q-next = p-next ; p-next = q； B. p-next = q-next; q = p; C. q-next = p-next；p-next = q D. p-next = q-next ; q-next = p; 3．若让元素…i,…,Pj,…,Pk,…依次进栈，则出栈次序不可能出现( )种情况。 A. …k,,…,Pj,…,Pi, … B. …,Pj,…,Pi,…,Pk, … C. …,Pk,…,Pi,…,Pj ,… D. …,Pi,,…,Pk,…,Pj,… 4. 设树中有一结点x，在先根遍历序列中的序号为P(x)，后根遍历序列中的序号为S(x)。若树中结点x是结点y的祖先，则有( )。 A. P(x) P(y)和S(x)S(y) B. P(x)P(y)和S(x)S(y) C. P(x)P(y)和S(x)S(y) D. P(x)P(y)和S(x)S(y) 5. 对22个记录的有序表作折半查找，当查找失败时，至少需要比较( )次关键字。 A. 3 B. 4 C. 5 D. 6 6. 对于一个具有n个顶点，e条边的图，若采用邻接矩阵表示，则矩阵大小为( )。 A. n行n列 B. n行e列 C. e行n列 D. e行e列 7．由权值分别为7,5,2,4的四个叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A. 36 B. 46 C. 35 D. 18 8. 若要求一个稀疏图G的最小生成树，最好用( )算法来求解。 A. Prim B. Dijkstra C. Kruskal D. Floyd 9. 对于n个记录的集合进行归并排序，所需要的附加空间是( )。 A． O(lbn) B. O(n) C. O(nlbn) D. O(1) 10．堆是一种( )排序。 A. 插入排序. 选择排序 排序排序对称矩阵A[n][n]中，按行优先次序存放在一维数组 [m]中，在中只存放A的下三角元素A[i][j]＝B[k］。请m至少定义为多少？②写出用i , j 表示k的下标变换公式 2. ①对于一棵有n个结点的二叉树采用链式存储结构，有多少个空指针域？②对于对于有n个结点的k叉树采用链式存储结构，有多少个空指针域? 3. 算法复杂度的定义是什么？算法复杂度O(1)含义是什么？ 4．平均查找长度是如何定义的？什么是动态查找表？ 四、算法理解（每题8分，共24分） 1．设一维数组中的关键字按升序排列，采用二分查找方法查找关键字为K的元素的递归算法，若查找成功则返回对应元素的下标，否则返回-1。请在横线上将语句补充完整。 int Binsch( DataType *A , int low , int high , KeyType K ) { if ( ① ) { int mid = (low+