华南师范大学《数据结构与算法设计》试卷(A卷)..docVIP

华南师范大学 ______学院、信息工程与技术系2010/2011学年（1）学期期末考试试卷 《数据结构与算法设计》试卷（A卷） 专业___________ 年级_____ 班级______ 姓名___________ 学号__________ 单项选择题（每小题2分，共22分） 在数据结构中，从逻辑上可以把数据结构分成________________。 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C． 线性结构和非线性结构 D. 内部结构和外部结构 在单链表中p所指结点后插入s所指结点，则下列语句正确的_________________。 A. p->next = s; s->next = p; B. s->next = p->next; p->next = s; C. s->next = p; p->next = s; D. p->next = s->next; s->next = p; 设一个栈的输入序列为1、2、3、4，则借助一个栈所得到的输出序列不可能是___________。 A． 1、2、3、4 B. 4、3、2、1 C. 1、3、4、2 D. 4、1、2、3 下面程序段的时间复杂度为__________________。 for( int i=1; i<m; i++) for( int j=1; j<n; j++) a[i][j] = i*j; A. O(m) B. O(n) C. O(m*n) D. O(m+n) 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是________。 A. 9 B. 11 C. 15 D. 不确定 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为____________。 A. 前序遍历 B. 后序遍历 C. 中序遍历 D. 层次遍历 按照二叉树的定义，具有3个结点的不同形状的二叉树有________种。 A. 3 B. 4 C. 5 D. 6 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较________个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 栈和队列的共同点是 A. 都是先进后出 B, 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点 设有两个串p和q, 求q在p中首次出现的位置的运算称作________。（不考“串”） A. 连接 B. 模式匹配 C. 求子串 D. 求串长 一个有n个顶点的无向图最多有________条边。 A. n B. n (n-1) C. n (n-1)/2 D. 2n 判断题（判断下列各题是否正确， 若正确在（）内打“√ ”，否则“?”。 每小题1分，共10分） （√）1. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （?）2. 顺序表结构适宜于进行顺序存取， 而链表适宜于进行随机存取。 （?）3. 二叉树中任何一个结点的度都是2。 (? ) 4. 有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵。 （?）5. 线性表的特点是每个元素都有一个前驱和一个后继。 （√）6. 按中序遍历二叉排序树所得到中序序列是一个递增有序序列。 （?）7. 串的长度是指串中所含不同字母的个数。 （√）8. n (n>1)个顶点的无向连通图最少有 n-1 条边。 （ ）9. 四种插入排序中，shell 排序记录移动的次数最少。 （√）10. 非空二叉排序树其根结点的值大于其非空左孩子的值。 简答题（共4*8分） 1、（1）写出图1的中根周游序列; （2）写出图2的后根周游序列。 （1）d f e b a g c （2）g d b e h f c a 2.以数据体{4, 5, 6,