《湖南工业大学数据结构试卷重点》由会员分享，可在线阅读，更多相关《湖南工业大学数据结构试卷重点（7页珍藏版）》请在金锄头文库上搜索。
1、一、单择题1. 栈和队列的共同特点是()。A. 只允许在端点处插入和删除元素B. 都是先进后出C. 都是先进先出D. 没有共同点2. 二叉树的第k层的结点数最多为()。A.2k-1B.2K+1C.2K-1 D. 2k-13. 数据结构中，从逻辑上可以把数据结构分成( )。A.动态结构和静态结构B.进凑结构和非进凑结构C.线性结构和非线性结构D.内部结构和外部结构4. 设二叉树的先序遍历序列和后序遍历序列正好相反，则该二树 满足的条件是( )。A.空或只有一个结点B.高度等于其结点数C.任一结点无左孩子D.任一结点无右孩子5. 设顺序线性表中有n个数据元素，则删除表中第i个元素需要 移动( )个
2、元素。A. n-i B. n+l -i C.n-1-i D. i6. 判定一个栈ST （最多元素为mO）为空的条件是（）。A.STTOP !=0B.STTOP=OC.STTOP !=m0D.STTOP二二mO7. 非空的循环单链表head的尾结点（由P所指向）满足（）。A.p-next=NULL B.p=NULL C.p-next=head D.p=head2. 按昭二叉树的定义，具有3个结点的二叉树有（）种。久 34 C. 5 D. 63. 个栈的入栈序列是已b, 5 d, e,则栈的不可能的输出序列是（ 儿A, edcba B. decba C* dceab D. abode4. 假设以数
3、组Am存放循环队列的元索，其头尾指针分别为front 和rear,则当前队列中的元素个数为（ 儿A. （rear-front+m）B. rearfront+1G （frontrear+m） %mD. （rear-front） %rn5”从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（）个结点A.n B.n/2 C. （n-1）/2 D. （n+1）/26.在一个带头结点的单链表HL中，若要在第一个元素之前插入一 个由指针P指向的结点，则执行( 几Ar HL = p; p-next = HL;B. p-next = HL;HL = p;G. p-next =
4、HI ;p = HL;D* p-next = HL-next; HL-next = p;7在一棵三叉树中度为3的结点数为2个，度为2的结点数为1 个度为1的结点数为2个，则度为0的结点数是( 儿A.4 B. 5 C. 6 D. 78. 在线性结构中，所有结点都有()个直接后继。A.0B.0或1C.1 D.不确定9-设数组Am作为循环队列sq的存储空间，front为队头指针，rear为队尾 指针，则执行入队操作时修改指针的语句是。A、sq.front=(sq.front+1)%mB、sq.front=(sq.front+1)%(m+1)C、sq.rear=(sq.rear+1)%mD、sq.re
5、ar=(sq.rear+1)%(m+1)二、填空题1. 已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA，则该二叉树的前序序列是()。2. 在()链表中，从任何一结点出发都能访问到表中的所有结点。3. 以下函数的时间复杂度为()。fact(int n)if (n=l)return 1;elsereturn(n*fact(n-l);4. 在线索化二叉树中，t所指结点没有左子树的充要条件是t-Ltag=（）。5. 现有按中序遍历二叉树的结果为abc,问有（）种不同形态的 二叉树可以得到这一遍历结果。6. 如图所示，删除元素b的语句为（）。三、应用题1. 给出下面森林对应
6、的二叉树及二叉树的后序序列。2. 已知二叉树的先序、中序和后序序列如下:刖序序列：*BC*G*中序序列：CB*EAGH* 后序序列：*EDB*FA，其中有一些看不清的字母用*表示。(1) 请先补充*处的字母.(2) 再构造一棵符合条件的二叉树(3) 最后画出带头结点的中序线索链表。3. 有一个含头结点的单链表，头指针为A,另有一个不含头结点 的单链表，头指针为B。分别写出判断A为空和B为空的条件。假设S指向一个新结点，分别写出在A的表头插入S,和在B的 表头插入S的语句。4. 设AH 8个字符出现的概率为:W=0.10, 0.16, 0.01, 0.02,0.29,0.10,0.07, 0.2
7、5。设计最优二进制编码(用0,1编码)(1) 画出最优二叉树(2) 计算平均码长(二叉树的带权路径长度)。5. 线性表有两种存储结构一是顺序表，二是链表。试问(1)如果有n个线性表同时并存，并且在处理过程中各表的长 度会动态变化，线性表的总数也会自动地改变。在此情况下，应 选用哪种存储结构？ 为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要 求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？ 为什么？6. 循环队列的优点是什么？如何判别它的空和满？四、编程题1、已知顺序表结构体定义如下：#define MAXLEN 100typedef structint dataMA
8、XLEN;int last;SeqList;在顺序表L的第i个位置上插入值为x的元素的函数定义如下：int InsList（SeqList *L,int i,int x） /（1）函数代码空缺部分 要求：将“（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中顺序 表满，返回-1；插入位置错误，返回0；正常完成数据插入返回1。2、已知链队列元素的结构体定义如下：typedef struct Nodeint data;struct Node *next;QNode;链队列头结点定义为：typedef structQNode *front,*rear;LQueue;在队列中，完成入队操作的函
9、数定义如下：void In_LQueue（LQueue *q,int x） /（2）函数代码空缺部分 依据题目条件，将“（2）函数代码空缺部分”的内容，在下面空白处填写完整。3、已知线性单链表结构体定义如下：typedef struct Nodeint data;struct Node *next;LNode,*LinkList;在单链表L的第i个位置上插入值为x的元素的函数定义如下：int Insert_LinkList（LinkList L,int i,int x） /（1）函数代码空缺部分假设LNode *Get_LinkList（LinkList L,int i）函数已经定义完成，该函
10、数 的功能为“在单链表L中查找第i个元素结点，找到后返回其指针；否则返回空 指针”。要求：将“（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中插入 位置错误，返回值为0；正常完成数据插入返回值为1。4、已知栈的结构体定义如下：#define MAXLEN 100typedef structchar dataMAXLEN;int top;SeqStack;在栈中，完成“出栈”操作的函数定义如下：int Pop_SeqStack（SeqStack *s,char *x） /（2）函数代码空缺部分要求：将“（2）函数代码空缺部分”的内容，在下面填写完整，因空栈导致无法 正常出栈，返回值为0；正常出栈返回值为1。
