发布时间 : 星期三 文章数据结构期末考试试题A卷更新完毕开始阅读d25e8babd1f34693daef3eb4
… _ 学院 专业 级 班 姓名 学号
湛江师范学院2008年－2009学年度第1学期
… 期末考试试题A卷
(考试时间:120分钟)
考试科目： 数据结构
总评复查分人 人 得 分 …○…题 号 分 值 一 二 三 四 五 40 20 30 10 总 分 100 ……请将所有答案填写在答题卡上，交卷时请将所有试卷上交
线
一、单选题(每小题2分，共40分)
1．下列算法的时间复杂度是（ B ）。 for ( i=0; i A O(1) B O(n) C O(log2n) D O(n2) 2．每一个存储结点不仅含有一个数据元素，还包含一个指针，该存 储方式是（ B ）存储方式。 A 顺序 B 链式 C 索引 D 散列 3．指针p指向以L为头指针的循环链表的首元素的条件是（ A ）。 A p==L B p->next==L C L->next==p D p->next==NULL 4．4个元素进S栈的顺序是A、B、C、D，进行两次Pop(S,x)操作后， 栈顶元素的值是（ B ）。 A A B B C C D D 5．经过下列栈的运算后GetTop(S)的值是（ A ）。 InitStack(s); Push(s,a); Push(s,b); Pop(s); A a B b C 1 D 2 命题教师签名： 系主任签名： 主管院长签名： 任课教师签名： 第 1 页，共 11 页 …○……内…装…○订. 6．栈的特点是（ B ）。 A 先进先出 B 后进先出 C 后进 后出 D 不进不出 7．经过下列运算后GetHead(Q)的值是（ A ） InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); A a B b C 1 D 2 8．一维数组的元素起始地址loc[0]=1000，元素长度为4， 则loc[2]为（ C ）。 A 1000 B 1010 C 1008 D 1020 9．二叉树第i层上最多有（ C ）个结点。 A 2i B 2i-1 C 2i-1 D i2 10．满二叉树（ A ）二叉树。 A 一定是完全 B 不一定是完全 C 不是 D 不是完全 11．二叉树按二叉链表存储，每个结点包含三个域（lchild、data、rchild），若p指针指向二叉树的根结点，经过运算 while ( p->rchild!=null ) p=p->rchild，则（ A ）。 A p指向二叉树的最右下方的结点 B p指向二叉树的最左下方的结点 C p仍指向根结点 D p为null 12．在具有n个结点的完全二叉树中，结点i(2i 第 2 页，共 11 页 ………○…………线…………○…………订…………○…………装…………○…………内…………○…………○…… 19．排序是根据（ C ）的大小重新安排各元素的顺序。 A 数组 B 关键字 C 元素 D 结点 20．不稳定的排序方法是指在排序中，关键字值相等的不同记录间的前后相对位置（ C ）。 A 保持不变 B 保持相反 C 不定 D 无关 二、填空题(每空2分，共20分) 1．已知带表头结点的单链表L，指针P指向L链表中的一个结点（非首结点、非尾结点），则删除P结点的直接后继结点的语句序列是 P->next=P->next->next ；删除尾结点的语句序列是 while(p->next->next) p=p->next; p->next=NULL; 。 2．栈S经过运算InitStack(s); Push(s,a); Pop(s,x)后，x的值是 a 。 3．队列Q经过运算InitQueue(q); EnQueue(q,a); OutQueue(Q,x)后，EmptyQueue(q)的值是 TRUE 。 4．根结点的层数为 1 。 5．在树与二叉树之间的转换方法中，树的根变为二叉树的 根 。 6．将下列按关键字的值从小到大的直接选择排序算法补充完整。 Select ( list r, int n ) { for ( i=1; 语句1 i<=n ; i++) { k=i; for ( j=i+1; 语句2 j<=n ; j++) if ( r[k].key > r[j].key) 语句3 k=j; ; if ( i != k ) swap ( r[k] , r[i] ); } } 7．两个不同的元素存入同一个散列表，当这两个元素的散列函数相 同时，称为 冲突 。 第 3 页，共 11 页 三、应用题(每题6分，共30分) 1．二叉树的基本形态有几种，请画出所有形态。 的前序、中序 和后 2．写出图1所示二叉树序遍历序列。 答：前序：ABDECF 中序：DBEACF 后序：DEBFCA 3．根据图2所示邻接表，写出该图从C点出发的深度和广度优先搜 索序列。 答： 深度：CDBAFE 广度：CDABFE 4．A、B、C三个元素进S栈的顺序是A、B、C，出栈的序列是C、 B、A，请写出相应的操作序列。 答：A入栈（Push(S,A)），B入栈（Push(S,B)），C入栈（Push(S,C)）， C出栈（Pop(S)），B出栈（Pop(S)），A出栈（Pop(S)）。 第 4 页，共 11 页