湖南工业大学数据结构试卷-重点.docx

一、单择题 栈和队列的共同特点是()。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 二叉树的第k层的结点数最多为()。 A.2k-1 B.2K+1 C.2K-1 D. 2k-1 数据结构中，从逻辑上可以把数据结构分成( )。 A.动态结构和静态结构 B.进凑结构和非进凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.设二叉树的先序遍历序列和后序遍历序列正好相反，则该二树满足的条件是( )。 A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 5.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。 A. n-i B. n+l -i C.n-1-i D. i 6.判定一个栈ST（最多元素为m0）为空的条件是( )。 A.ST→TOP!=0 B.ST→TOP==0 C.ST→TOP!=m0 D.ST→TOP==m0 7. 非空的循环单链表head的尾结点（由P所指向）满足( )。 A.p-next=NULL B.p=NULL C.p-next=head D.p=head 8.在线性结构中，所有结点都有( )个直接后继。 A.0 B.0或1 C.1 D.不确定 9. 设数组A[m]作为循环队列sq的存储空间，front为队头指针，rear为队尾指针，则执行入队操作时修改指针的语句是 。 A、sq.front=(sq.front+1)%m B、sq.front=(sq.front+1)%(m+1) C、sq.rear=(sq.rear+1)%m D、sq.rear=(sq.rear+1)%(m+1) 二、填空题 1.已知一棵二叉树的中序序列和后序序列分别为：DBGEACHF和DGEBHFCA，则该二叉树的前序序列是( )。 2.在( )链表中，从任何一结点出发都能访问到表中的所有结点。 3.以下函数的时间复杂度为( )。 fact(int n) { if (n=1) return 1; else return(n*fact(n-1)); } 4.在线索化二叉树中，t所指结点没有左子树的充要条件是t-Ltag==( )。 5.现有按中序遍历二叉树的结果为abc，问有( )种不同形态的二叉树可以得到这一遍历结果。 6.如图所示，删除元素b的语句为( )。 三、应用题 1.给出下面森林对应的二叉树及二叉树的后序序列。 2.已知二叉树的先序、中序和后序序列如下: 前序序列：*BC***G* 中序序列：CB*EAGH* 后序序列：*EDB**FA ，其中有一些看不清的字母用*表示。 请先补充*处的字母. 再构造一棵符合条件的二叉树 (3)最后画出带头结点的中序线索链表。 3.有一个含头结点的单链表，头指针为A, 另有一个不含头结点的单链表，头指针为B。 (1)分别写出判断A为空和B为空的条件。 (2)假设S指向一个新结点，分别写出在A的表头插入S，和在B的表头插入S的语句。 设A～H 8个字符出现的概率为:W={0.10, 0.16, 0.01, 0.02, 0.29, 0.10, 0.07, 0.25}。设计最优二进制编码（用0,1编码） 画出最优二叉树 计算平均码长(二叉树的带权路径长度)。 5.线性表有两种存储结构一是顺序表，二是链表。试问 （1）如果有 n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？ 为什么？ （2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？ 6. 循环队列的优点是什么？如何判别它的空和满？ 四、编程题 1、已知顺序表结构体定义如下： #define MAXLEN 100 typedef struct{ int data[MAXLEN]; int last; }SeqList; 在顺序表L的第i个位置上插入值为x的元素的函数定义如下： int InsList(SeqList *L,int i,int x){ …… //（1）函数代码空缺部分 } 要求：将“（1）函数代码空缺部分”的内容，在下面空白处填写完整，其中顺序表满，返回-1；插入位置错误，返回0；正常完成数据插入返回1。 2、已知链队列元素的结构体定义如下： typedef struct Node{ int dat