2012-2013数据结构试卷(final).doc

第1页 共6页 聊城大学计算机学院2012—2013学年第1学期期末考试2011级《数据结构》试题（闭卷B卷） 题号 一 二 三 四 五 总分 复核人 得分 一、单项选择题（共15题，每题2分，共30分） 得分 阅卷人 （答案必须写在下面表格内） 题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 研究数据结构就是研究（ ）。 数据的逻辑结构 B．数据的存储结构 C．数据的逻辑结构和存储结构 D．数据的逻辑结构、存储结构及其基本操作 在数据结构中，从逻辑上可以把数据结构分为（ ）。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 算法分析的两个主要方面是A．空间复杂度和时间复杂度 B．正确性和简单性 C．可读性和文档性 D．数据复杂性和程序复杂性 下面程序段的时间复杂度是（ ）。 for(i=0；im；i++) for(j=0；jn；j++) a[i][j]=i*j；A．O(m2) B．O(n2) C．O(m*n) D．O(m+n) 栈和队列的共同特点是A．只允许在端点处插入和删除元素 B．都是先进后出 C．都是先进先出 D．没有共同点 ( )。 B．decba C．dceab D．abcde 带头结点的单链表head为空的判定条件是（ ）。 A．head == NULL B head-next ==NULL C．head-next ==head D head!=NULL 8. 设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ） A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 9. 在循环双链表的p所指的结点之前插入s所指结点的操作是（ ）。 A．p-prior = s；s-next = p；p-prior-next = s；s-prior = p-prior B．p-prior = s；p-prior-next = s；s-next = p；s-prior = p-prior C．s-next = p；s-prior = p-prior；p-prior = s；p-prior-next = s D．s-next = p；s-prior = p-prior；p-prior-next = s；p-prior = s 10. 深度为5的二叉树结点个数最16 B．32 C．31 D．10 11. 具有10个叶子结点的二叉树中度为2的结点个数是（ ）。 A．8 B．9 C．10 D．11 12. （ ）。 次13. 广义表（（a））的表尾是（ ）。 A．a B．（） C．（a） D．（（a）） 14. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是（ ）。 A．选择排序 B．希尔排序 C．归并排序 D．快速排序 15. 采用折半查找法查找长度为n的线性表时，每个元素的平均查找长度为（ ）。 A O(n2) B O(nlog2n) C O(n) D O(log2n) 二、填空题（共6题，每空1分，共10分） 得分 阅卷人 ①____________ ②____________ ③____________ ④____________ ⑤____________ ⑥____________ ⑦____________ ⑧__