广东外语外贸大学计算机科学与技术系和软件工程系2004级.doc

广东外语外贸大学计算机科学与技术系和软件工程系2004级数据结构课程期中试卷班级：_学号：_姓名：_成绩：_一、判断题 请在题后括号内打上（正确）或（错误） (共20分 每空2分)1在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）2. 在对带头结点的链队列作出队操作时，头指针的值不会改变。（ ）3用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1,2,3,4, 为了得到1,3,4,2出栈顺序相应的S和X操作串为SXSSXSXX。（ ）4. 在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。（ ）5. 顺序存储的线性表可以按序号随机存取。( )6. 带头结点的单链表队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点（ ） 7. 二叉树中不存在度大于2的结点，当某个结点只有一棵子树时无所谓左、右子树之分。（ ）8. 当k1时，高度为k的二叉树至多有2k-1个结点。 ( )9. 完全二叉树的某结点若无左孩子，则它必是叶结点。( )10假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为31个。（ ）二、单选题 (共20分 每空2分)1. 数据结构是一门研究非数值计算的程序设计问题中计算机的（ A ）以及它们之间的关系和运算等的学科。A.数据元素 B.计算方法C.逻辑存储D.数据映象2. 设单链表中指针p指向结点m ，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）。A.p-next=p-next-next; B.p=p-next;C.p=p-next-next; D.p-next=p;3. 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A. 单链表 B. 仅有头指针的单循环链表 C. 双链表 D. 仅有尾指针的单循环链表4下面程序段的时间复杂度是( B )。for (i=1;i=n;i+)for (j=i;jnext = = NULL;C. head-next = = head; D. head! = NULL;6. 在循环双链表的p所指结点之后插入s所指结点的操作是 ( D )。A. p-right=s; s-left=p; p-right-left=s; s=-right=p-right;B. p-right=s; p-right-left=s; s-left=p; s-right=p-right;C. s-left=p; s-right= p-right; p-right=s; p-right-left=s;D. s-left=p; s-right=p-right; p-right-left=s; p-right=s;7假设顺序栈的定义为：typedef struct selemtype *base; /* 栈底指针*/selemtype *top; /* 栈顶指针*/int stacksize; /* 当前已分配的存储空间,以元素为单位*/sqstack;变量st为sqstack型，则栈st为满的判断条件为（ C ）。A st.base = NULL B st.top = st.stacksizeC st.top-st.base= st.stacksize D st.top = st.base8判断一个循环队列QU ( m0为最大队列长度(以元素为单位)，front和rear分别为队列的队头指针和队尾指针 ) 为空队列的条件是( A )。AQU-front = QU-rear BQU-front != QU-rearCQU-front = (QU-rear+1) % m0 DQU-front != (QU-rear+1) % m09用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组R1.n中，结点Ri若有左子女，则左子女是结点( B )。AR2i+1 B. R2i C. Ri/2 D. R2i-110设a、b为一棵二叉树上的两个结点。在中序遍历时，a在b前面的条件是( B )。Aa在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙三、简答题 (共20分)1已知一棵二叉树用顺序存储表示的结果为ABCKDIEHFJG (表示不存在此结点),要求画出该二叉树。（8分）GEABCKDIHFJ2分别写出下图所示二叉树的的先序、中序、后序、按层遍历的序列。（12）ABCDEFGHIJ先序：ABDEHICFJG中序：DBHEIAFJCG后序：DHIEBJFGCA层序：ABCDEFGHIJ四、算法设计题 (共40分)1. (共15分 )已知Q是一个非空队列，S是一个空栈。仅用队列和栈的基本操作函数和少量工作变量，编写一个算法，将队列Q中的所有元素逆置。 栈的基本操作函数有： clearstack(&s); 置空栈 push(&s,e); 新元素e进栈 pop(s,&e):出栈，返回栈顶值给e stackEmpty(s): 判栈空否 队列的基本操作函数有 enqueue(&q,e); 元素e进队 dequeue(&q,&e):出队列，返回队头值给e queueempty(q): 判队列空否ABC(&q) clearstack(s);while(!queueempty(q) dequeue(q,e);push(s,e);while(!stackEmpty(s) pop(s,e);enqueue(q,e); 2(共25分 ) 设有一个带头结点，由正整数组成的无序单链表，头指针为L，Typedef struct Lnodeint data;struct Lnode *next;Lnode,*Linklist;Linklist L;给出完成下列功能的算法： 找出最小值结点，且打印该数值； 若该数值是奇数，则将其与直接后继结点的数值交换； 若该数值是偶数，则将其直接后继结点删除；bbc(Linklist &L) pmin=L-next;if(!pmin) return ERROR;p=pmin-next;while(p) if(p-datadata) pmin=p;p=p-next;p