06-07数据结构试题a答案.doc

系主任 审批并签名 教研室主任 审批并签名 刘顺海 A卷 拟题人 刘顺海 广州大学松田学院 2006 ~ 2007 学年考试卷（答案） 课程: 数据结构 考试形式（闭卷） 专业： 计算机科学与技术 准考证号： 姓名： 题次 一 二 三 四 五 六 七 总分 分数 16 10 14 30 30 100 评卷人 填空题（每空1 分，共计 16 分） 数据（Data）_ O( n*m)__。For(i=0;in;i++) For(j=0;jm;j++) A[i][j]=0; 在一个循环顺序队列Q中，判断队空的条件为 front==rear ，判断队满的条件为 (rear+1)%QueueMaxSize==front 。 若已知一棵二叉树的深度为k(k≥1)，则这棵树至多有 2k-1??????? 个结点，这棵树的第i (1≤i≤k)层上至多有??? 2i-1?? 个结点，若这是一棵具有n结点的完全二叉树，则k与n的关系为 k=└log2n┘+1??????????? 。 中缀算术表达式3+4/(25-(6+15))*8 所对应的波兰算术表达式 为_____3 4 25 6 15 +-/8*+_____。 一个有向图中有1000个顶点，1000条边，则形成的邻接矩阵有 1000 个非零元素，因此是 稀疏矩阵 。 每次从待排序的区间中选择出具有最小排序码的元素，把该元素与该区间的第一个元素交换位置，此种排序方法叫做__直接选择______排序；使两个有序表合并成一个有序表的排序方法叫做_二路归并_______排序。 对于下图1，请_________0,1,2,3,4,5,6,7,8,9______________。 图1 向线性表中满足条件的位插入一个元素是void Insert(ListL,const Elimtypeitem) 。在下面的程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，则程序段执行后所得到的线性表La为： 26、34、48、57、62、79 。 InitList(La); int a[]={48,26,57,34,62,79}; for(i=0; i6; i++) Insert(La,a[i]); TraverseList(La); 假定一组记录的排码为（46,79,56,38,40,84））a[i]的另一种等价表示方式为 （ A ）A *(a+i) B a+i C *a+i D a+I 链栈与顺序栈相比，有一个较明显的优点是 （ A ）C 插入操作更加方便 D 删除操作更加方便 若查找表中的记录按关键字的大小顺序存放在一个一维数组中，用二分法（折半法）查找的平均有哪些信誉好的足球投注网站长度为 （ B ）0(n) B 0(log2n) C 0(nlog2n) D 0((log2n)2) 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（B）A. HL = p; p-next = HL; B. p-next = HL; HL = p;C. p-next = HL; p = HL;D. p-next = HL-next; HL-next = p; 下列广义表中是线性表的只有 （ C ）A. E(a,(b,c)) B. E(a, E) C. E(a,b) D. E(a, L()) 设线性链表中结点的结构为(data,link)。已知指针p所指结点不是尾结点，若在p指针指向的结点之后插入s指针指向的结点，则应执行以下哪个操作 （ C ） s-link:=p; p-link:=s B s-link:=p-link; p:=s;C s-link:=p-link; p-link:=s; D p-link:=s; s-link:=p; 设图中有n 个顶点和e 条边，进行深度优先有哪些信誉好的足球投注网站遍历的时间复杂度至多为 （ A ）。A. O(n + e ) B. O(n*e) C. O(nlog2 n) D. (elog2 e) 采用折半查找方法进行查找，数据文件应为且限于（?A ）。A. 有序表 顺序存储结构 ????????????? B.? 有序表? 链式存储