西安电子科技大学《数据结构》2009试题.pdfVIP

西 安 电 子 科 技 大 学 考试时间 分钟 试 题 题号 一 二 三 四 五 六 七 八 九 十 总分 分数 1.考试形式：闭卷；2。考试日期：20 年 月 日3.本试卷共 四 大题，满分 100 分。 班级 学号 姓名 任课教师 一. 选择题（15小题，共 30分）  1. 逻辑上通常可以将数据结构分为（ ）  A.动态结构和静态结构  B.顺序结构和链式结构  C.线性结构和非线性结构  D.初等结构和组合结构  2. 在下列对顺序表进行的操作中，算法时间复杂度为 O(1)的是（ ）  A.访问第 i 个元素的前驱（1 i£ n ）  B.在第 i 个元素之后插入一个新元素( 1£ i £ n )  C.删除第 i 个元素( 1£ i £ n )  D.对顺序表中元素进行排序 3. 一个栈的输入序列为 123…n，若输出序列的第一个元素是 n，输出第 i （1=in） 个元素是（ ）。 A. 不确定 B. n-i+1 C. i D. n-i  4.  如果将矩阵  A × 的每一列看成一个子表，整个矩阵看成是一个广义表  L，即  n n  L=((a ,a ,…,a ),(  a ,a ,…,a ),…，（a ,a ,…,a ）),并且可以通过求表头 head 和求表 11 21 n1 12 22 n2 1n 2n nn 尾 tail 的运算求取矩阵中的每一个元素，则求得 a 的运算是（ ）  21  A. head (tail (head (L)))  B. head (head(head(L)))  C. tail (head (tail (L)))  D. head (head (tail (L)))  5. 设森林 F中有三棵树，第一、第二、第三棵树的结点个数分别为 M1，M2 和 M3，则与森林 F 对 应的二叉树根结点的右子树上的结点个数是（ ）。  A．M1          B．M1+M2       C．M3           D．M2+M3  6. 对下列关键字序列进行快速排序时，所需进行比较次数最少的是（ ）  A. （1，2，3，4，5，6，7，8）  B. （8，7，6，5，4，3，2，1）  C. （4，3，8，6，1，7，5，2）  D. （2，1，5，4，3，6，7，8） 第 1页 共 页 第 2页 共 页  7.  以下程序的时间复杂度为（ ）  for （i=0；im；i++）  for （j=0；jt；j++）  c ［i］［j］=0；  for （i=0；im；i++）  for （j=0；jt；j++）  for （k=0；kn；k++）  c ［i］［j］=c ［i］［j］+a ［i］［k］*b ［k］［j］；  A.O （m+n×t）