2009秋-数据结构B-经0806-试卷B卷答案--武守秋、邸书灵.pdf

石家庄铁道学院 2009-2010 学年第 1 学期 2008 本科班期末考试试卷（B ）答案 课程名称： 数据结构B 任课教师：武守秋、邸书灵 考试时间： 120 分钟 学号： 姓名： 班级： 考试性质（学生填写）：正常考试（ ）缓考（ ）补考（ ）重修（ ）提前修读（ ） 题 号 一 二 三 四 五 六 七 总分 满 分 20 20 45 15 100 得 分 阅卷人 一、单项选择题（每小题2 分，共20 分） 1. 执行下面程序段时，执行S 语句的次数为___A_____ 。 for ( int i = 1; i = n; i++ ) for ( int j = 1; j = n; j ++ ) S; 2 2 (A)n (B)n /2 (C)n(n+ 1) (D)n(n+ 1)/2 2. 用链表表示线性表的优点是__C_____ 。 (A)便于随机存取 (B)花费的存储空间比顺序表少 (C)便于插入与删除 (D)数据元素的物理顺序与逻辑顺序相同 3. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为____C____ 。 (A) 顺序表 (B) 用头指针表示的循环单链表 (C) 用尾指针表示的循环单链表 (D) 单链表 4. 一个栈的输入序列为12345，则下列序列中是栈的输出序列的是____A______。 (A)23415 (B)54132 (C)31245 (D)14253 5. 队列的插入操作在____B____进行。 (A) 队头 (B) 队尾 (C)任意位置 (D)指定位置 6. 设循环队列中数组的下标范围是1~n，其头尾指针分别为f 和r ，则其元素个数为 ____D_____ 。 (A)r-f (B)r-f+ 1 (C) (r-f) mod n + 1 (D) (r-f+n) mod n 7. 数组A[1..5,1..6] 的每个元素占5 个单元，将其按行优先顺序存储在起始地址为 1000 的连续的内存单元中，则元素A[5,5]的地址为_____A_____ 。 (A) 1140 (B) 1145 (C) 1120 (D) 1125 8. 设森林F 中有4 棵树， 1、2、3、4 棵树的结点个数分别为n 、n 、n 、n ，当把 1 2 3 4 森林F 转换成一棵二叉树后，其根结点的左子树中有___A_____个结点。 (A)n - 1 (B)n (C)n (D)n 1 2 3 4 1 页 共6 页 9. 有n 个顶点的强连通有向图G 至少有__C__条弧。 (A)n+ 1 (B)2n (C)n (D)n-1 10. 路径长度A 的路径是关键路径。 (A)最长 （B ）最短 二、填空题（每空2 分，共20 分） 1. 算法具有输入、输出、确定性、（有 性）和可执行性等特性。 2. 在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数 插入或删除的位置有关。插入时平均次数n/2 ，删除时平均次数（ (n- 1)/2 ）。 3.