数据结构期末复习 10 计科2 16 号 朱志彬 1 武 夷 学 院 期 末考试 试 卷 （ 09级计算机科学与技术专业2010 ～2011 学年度第 1 学期） 课程名称 数据结构 A 卷 考试形式 闭卷 考核类型 考试 本试卷共 五 大题，卷面满分100分，答题时间120分钟。 一、选择题：（本大题共10小题，每小题2分，共20分） 1． 某内排序方法的稳定性是指( )。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为0（n log n）的排序方法 D．以上都不对 2．下面程序段的时间复杂度为( )。 for(i=2;i<=n;++I) for(j=2;j<=i-1;++j) {++x;a[i，j]=x;} A.O(1) B.O(lo g2n ) C.O(n ) D.O(n 2) 3．非空的循环单链表head 的尾结点p 满足( )。 A.p->next=head； B. p->next=NULL； C.p =NULL； D. p->next->next =head； 4．设栈s 和队列Q 的初始状态为空， 元素b 1 ，b 2， ，b 3 ， b 4 ， b 5 和b 6 依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是b 2 ，b 4 ，b 3 ，b 6 ，b 5 ，b 1 ， ，则栈S 的容量至少应该是( )。 A. 3 B. 4 C. 5 D.其它 题号 一 二 三 四 五 六 七 八 总分 复核人 得分 得分 评卷人 ………………………密……………………封…………………………装…………………订………………………线……………………… 系别 专业（班级） 姓名 学号 数据结构期末复习 10 计科2 16 号 朱志彬 2 5．表头和表尾均为空表的广义表是( )。 A.() B.(()) C.((())) D.(()，()) 6.下列二叉排序树中，满足平衡二叉树定义的是( )。 A． B. C. D. 7．二维数组 A 的成员是4 个字符（每个字符占一个存储单元）组成的串，行下标 i 的范围从 1到 8，列下标 j 的范围从 1 到 10，若 A 按行优先方式存储，起始地址为SA，那么元素 A[8][5]的起始地址为 ( )。 A．SA+292 B．SA+296 C．SA+300 D．SA+304 8．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( )。 A． 必定快 B．不一定 C． 在大部分情况下要快 D． 取决于表递增还是递减 9．下列关键字序列中，构成小根堆的是( )。 A．{ 84，46，62，41，28，58，15，37} B．{ 84，62，58，46，41，37，28，15} C．{ 15，28，46，37...
