数据结构AB.doc

院系:_ 班级:_ 姓名:_ 学号:_.密封线学院 2009 2010 学年度第二学期数据结构期末试卷A卷课程归属部门： 计算机与信息工程学院 试卷适用范围：09计算机各专业题号一二三四五总分得分得分评卷人一、判断题（每题1分，共10分）1.程序和算法在原则上没有区别，所以在在讨论数据结构时可以通用。 （ ）2.在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。（ ）3.顺序表结构适宜进行顺序存取，而链表适宜进行随机存取。 （ ）4.空栈就是所有元素都为0的栈。 （ ）5.队列是限制在两端进行操作的线性表。 （ ）6串是n个字母的有限序列。 （ ）7.树结构中每个结点只有一个直接前驱。 （ ）8.在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。 （ ）9.二叉树的遍历是指按某种顺序访问二叉树中的所有结点。 （ ）10. 带权路径长度最小的二叉树称为哈夫曼树。（ ）得分评卷人二、填空题（每空2分，共20分）1数据有逻辑结构和 两种结构。2在栈结构中，允许插入、删除的一端称为 。 3设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_；r=s; r-next=null;。4在队列中存取数据应遵循的原则是 。5在一个链队列中，若队首指针为front，队尾指针rear，则判断该队列只有一个结点的条件为 。6在空串和空格串中，长度不为0的是 。 7在一个具有n个单元的顺序栈中，假定以地址高端（即下标为n的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top_。8设一棵二叉树结点的先序遍历序列为：ABDECFGH，中序遍历序列为：DEBAFCHG，则二叉树中叶结点是 。9 数据的逻辑结构除了集合以外，还包括线性结构、树形结构和 。ABCEFGH10给定如右图二叉树，其前序遍历序列为： 。得分评卷人三、选择题（每题2分，共40分）1算法分析的两个主要方面是（ ）。A空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性 D.数据复杂性和程序复杂性2算法能正确的实现预定功能的特性称为算法的（ ）A健壮性 B易读性 C正确性 D高效性3在具有n个结点的单向链表中，实现（ ）的操作，其算法的时间复杂度是O（n）。 A遍历链表或求链表的第i个结点 B.在地址为P的结点之后插入一个结点 C. 删除开始结点 D.删除地址为P的结点的后继结点4在单链表中，增加头结点的目的是（ ）。A使单链表至少有一个结点 B标志表中首结点的位置C方便运算的实现 D说明该单链表是线性表的链式存储结构5带头结点的链栈LS的示意图如下，栈顶元素是（ ）HABCLSAH B A CB DC6引起循环队列队头位置发生变化的操作是（ ）。 A. 出队 B.入队 C.取队头元素 D.取队尾元素 7队列Q，经过下列运算后，再执行Qempty(Q)的值是（ ）。 InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)； ReadQueue(Q,x)；AaBb C0D1 8串的模式匹配是指（ ）。A判断两个串是否相等 B. 找某字符在主串中第一次出现的位置C. 对两个串比较大小 D.找某子串在主串中第一次出现在的第一个位置 9设串S1=ABCDEFG,S2=PQRST,则ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1,LenStr(S2),2)。A. BCDEF B. BCDEFEF C. BCPQRST D. BCDEFG10树最适合用来表示（ ）。A有序数据元素 B无序数据元素C元素之间无联系的数据 D元素之间有分支的层次关系11把一棵树转换为二叉树后，这棵二叉树的形态是（ ）。A唯一的 B有多种，但根结点都没有左孩子C有多种D有多种，但根结点都没有右孩子12下列陈述正确的是（ ）。A二叉树是度为2的有序树 B二叉树中结点只有一个孩子时无左右之分C二叉树中必有度为2的结点 D二叉树中最多只有两棵子树，且有左右子树之分13二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法（ ）。A正确 B错误 C 不确定 D都有可能 14将一颗有100各结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（ ）。A 46 B47 C.90 D91 15某二叉树的后序遍历序列为：DABEC,中序遍历序列为：DEBAC,则前序遍历序列为（ ）。 A.ACBED B.DECAB C.DEABC D.CEDBA16. 下列算法的时间复杂度是（ ）.for(i=0;in;i+) for(j=0;jdata=_2_;p=head-next;while(p!=NULL&p-data!=a)_3_;if(p=NULL)printf(不存在%d,x);else_4_; _5_;2层次遍历二叉树，其中Queue *Q，则出队函数为OutQueue(Q),队空函数为EmptyQueue(Q)，入队函数EnQueue(Q,data);typedef struct BTint data;struct BT *lchild,*rchild;BT;void LevelOrder(BT *T)Queue *Q,*P;initQueue(Q);if(_1_)printf(此二叉树为空！);return;EnQueue(Q,T);while(_2_)P=_3_;printf(%c ,p-data); if(_4_)EnQueue(Q,P-lchild);if(P-rchild)_5_;3. 假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。typedef struct queuenode / 定义队列的存储结构int data;struct queuenode *next;qu;InQueue(qu *rear, int x) / 向队列插入元素为x的函数 qu *head,*s; s= 1 ; s-data= 2 ; if (rear=NULL) / 循环队列为空，则建立一个结点的循环队列 rear=s; rear-next; else head= 3 ; / 循环队列非空，则将s插到后面rear-next= 4 ;rear=s; 5 =head;4根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。F=（D，R），其中： D=50，25，64，57，82，36，75，55，R=,得分评卷人五、问答题（共10分）1 将图a中的二叉树转换成森林（2分），2 将图b中的森林转换成二叉树并写出中序序列。（4分） （图a） （图b）3假设用于通信的电文仅由A、B、C、D、E、F、G、H8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10。试为这8个字母设计哈夫曼编码。（本小题4分）（注：编码时左分枝标记0，右分枝标记1）院系:_ 班级:_ 姓名:_ 学号:_.密封线学院 2009 2010 学年度第二学期数据结构期末试卷B卷课程归属部门： 计算机与信息工程学院 试卷适用范围：09计算机各专业题号一二三四五总分得分得分评卷人一、判断题（每题1分，共10分）1.数据的逻辑结构和数据的存储结构是相同的。 （ ）2.线性表采用顺序存储，必须占用一片连续的存储单元。（ ）3.将十进制数转换为二进制数是栈的典型应用之一。 （ ）4.一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。（ ）5.链队列在一定范围内不会出现队满的情况。 （ ）6 如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。（ ）7.完全二叉树一定是满二叉树。 （ ）8.具有n个叶子结点的哈夫曼树共为2n-1个结点。 （ ）9.二叉树的遍历是指按某种顺序访问二叉树中的所有结点。 （ ）10. 顺序存储方式的优点是存储密度大，插入、删除效率高。( )得分评卷人二、填空题（每空2分，共20分）1数据结构按逻辑结构可分为线性结构和 。2若内存空间充足， 栈可以不定义栈满运算。 3解决顺序队列“假溢出”的方法是采用 。4 是被限定为只能在表的一端进行插入运算，在另一端进行删除运算的线性表。5在子串的定位运算中，被匹配的主串称为目标串，子串称为 。6对于二叉树来说，第i层上至多有 个结点。 7度为0的结点称为 结点。8设某二叉树的中序遍历为：DEBAC，后序遍历序列为EBCAD，则前序遍历序列为： 。9设r指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点，需执行的三条语句是_；r=s; r-next=null;。10. 在一个具有n个单元的顺序栈中，假定以地址高端（即下标为n的单元）作为栈底，以top作为栈顶指针，则当向栈中压入一个元素时，top的变化是top_。得分评卷人三、选择题（每题2分，共30分）1算法的计算量大小称为算法的（ ）。A现实性B.难度 C. 时间复杂度 D.效率2非线性结构中的每个结点（ ）A无直接前驱结点 B 只有一个前驱结点和一个直接后继结点C无直接后继结点 D可能有多个直接前驱结点和多个直接后继结点高效性3已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。 AB+(i-1)*m B. B+i*m C. B-i*m D. B+(i+1)*m4下面关于线性表的叙述中，错误的是（ ）。A顺序表必须占用一片地址连续的存储单元 B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元 D链表可以随机存取任一元素5带头结点的链栈LS的示意图如下，栈顶元素是（ ）HABCLSAH B A CB DC64个元素按A，B，C，D顺序进S栈，执行两次Pop(S,x)运算后，栈顶元素的值是（ ）。 A. A B. B C. C D. D 7队列Q，经过下列运算后，再执行Qempty(Q)的值是（ ）。 InitQueue(Q)(初始化队列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)； ReadQueue(Q,x)；AaBb C0D1 84个元素按A，B，C，D顺序连续进队Q，则队尾元素是（ ）。A. A B. B C. C D. D 9串是一种特殊的线性表，其特殊性体现在（）。A. 可以顺序存储 B.数据元素是一个字符 C. 可以链接存储 D.数据元素可以是多个字符10在一棵具有五层的满二叉树中，结点的总数为（ ）。A16 B31 C32 D3311任何一棵二叉树的叶结点在前序、中序、后序遍历中的相对次序（ ）。A不发生改变 B发生改变 C不能确定D以上都不对12二叉树的叶结点个数比度为2的结点的个数（ ）。A无关 B相等 C多一个 D少一个13二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法（ ）。A正确 B错误 C 不确定 D都有可能 14将一颗有100各结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（ ）。A 46 B47 C.90 D91 15某二叉树的后序遍历序列为：DABEC,中序遍历序列为：DEBAC,则前序遍历序列为（ ）。 A.ACBED B.DECAB C.DEABC D.CEDBA16. 下列算法的时间复杂度是（ ）.for(i=0;in;i+) for(j=0;jdatanext=_4_; _5_; p=q-next; 2使用递归函数思想实现二叉树的深度， 试完成下列的程序填空。typedef struct BTint data;struct BT *lchild,*rchild;BT;int TreeDepth (BT *T)int ldep,rdep;if(_1_) return 0;else ldep=_2_; rdep=_3_; if(_4_)return ldep+1;else _5_;3假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。typedef struct queuenode / 定义队列的存储结构int data;struct queuenode *next;qu;InQueue(qu *rear, int x) / 向队列插入元素为x的函数 qu *head,*s; s= 1 ; s-data= 2 ; if (rear=NULL) / 循环队列为空，则建立一个结点的循环队列 rear=s; rear-next; else head= 3 ; / 循环队列非空，则将s插到后面rear-next= 4 ;rear=s; 5 =head;4根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。C=（D