数据结构考试习题试卷c.doc

飒爽小君子南通大学2006—2007学年第二学期 数据结构(闭卷) 试卷（C）第1页 共3页试题 一 二 三 四 五 总分 得分 得分 评卷人 一、单项选择题（每小题1分，共20分） 下列各小题的候选答案中只有一个答案是正确的，请把正确答案的字母代号填写在题后括号内。 使用班级 计51,052,053,054,计师051,软051,052 出卷日期 2007年6月21日 南通大学2006—2007学年第二学期 数据结构（闭卷） 试卷（C）第2页 共3页 得分 评卷人 二、判断题（每小题1分，共10分） 请判断下各命题，如正确的，请在后面括号内填上√，否则填上×。 得分 评卷人 三、填空题(每小题1分，共10分) 请将下列各题的正确答案填写在空白处。 得分 评卷人 四、应用题（每小题10分，共40分） 请运用所学的数据结构知识解答下列各题。 南通大学2006—2007学年第二学期 数据结构（闭卷） 试卷（C）第 3页 共3页 得分 评卷人 五、算法设计题（每小题10分，共20分） 请运用所学的数据结构知识解答下列各题。 ————————— 密 ———————————— 封 —————————— 线 ———————— ·····················装·····················订·························线························ 学院： 专业： 班级： 姓名： 学号： ···················装·····················订·························线··················· 密 封 线 内 答 题 无 效 学院： 专业： 班级： 学号： 本人承诺：在本次考试中，自觉遵守考场规则，诚信考试，绝不作弊。 学生姓名（签名）： 9. 串的长度是指（ ）。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 10. 森林T由5棵树组成，树的结点个数依次为n1,n2,n3,n4,n5,将T转换为二叉树后，其根结点的右子树上有（ ）个结点。 A．n1 B．n3+n4+n5 C．n2+n3+n4+n5 D．n1+n2+n3+n4+n5 现有一棵二叉树，它含有5个度为2的结点，2个度为1的结点，由此可知该二叉树的结点总数为（ ） A．14 B．13 C．7 D．11设有向图有n个顶点和e条边，进行拓扑排序时，总的时间复杂度为（ ） A．O(nlog2e) B． O(en) C． O(n+e) D．O(ne)在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做（　 　）次关键码比较。2 B．3 C．4 D．5 17. 表长为20的哈希表，用去除留余法，即按式H(Key)=Key mod P,建立哈希函数，P应取（ ）。 A. 16 B. 17 C. 18 D. 19 18. 下面的序列中，（ ）是堆。 A．B．D． 1. 执行下面程序段时，执行S语句的次数为 ( ) 。 for ( int i=1; i=n; i++) for ( int j=1; j=i; j++) S; A． n2 B． n2/2 C． n(n+1) D． n(n+1)/2 2. 以下数据结构中，（ ）是非线性数据结构。 A．树 B．字符串 C．队 D．栈 3. 线性表采用链式存储结构时，要求内存中可用存储单元的地址( )。 A． 必须是连续的 B． 部分地址必须是连续的 C． 一定是不连续的 D． 连续或不连续都可以 4. 非空的循环单链表head的尾结点（由指针p所指）满足（ ）A．p-next=NULL B．p=NULL C．p-next=head