湖工数据结构.doc

卷号：A总分核分人姓 名一、密封线内不准答题。二、姓名、学号、班级不许涂改，否则试卷无效。三、考生在答题前应先将姓名、学号和班级填写在在指定的方框内。四、试卷印刷不清楚，可举手向监考教师询问。学 号所在年级、班级密封注意 意：二O一一 二O一二学年第二学期期末考试 数据结构 试题( 多个 专业用) (闭卷)题号一二三四五六七八九十题分4060得分注意：学号、姓名和所在年级班级不写、不写全或写在密封线外者，试卷作废。一、 简答题：本题共6小题，共40分。1.（4分）简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。2.（4分）简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串。3.（6分）在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，分别求出其时间复杂度。4.（6分）简述循环队列的优点，并写出判断循环队列的空和满的方法。5.（10分）指出下述程序段的功能。() SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp); Push( &S1,x);Push( &S2, x);() void Demo2( SeqStack *S, int m) / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i);6.（10分）假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成，这8个字母在电文中出现的概率分别为0.06,0.18,0.02,0.06,0.32,0.03,0.22,0.11。（）为这8个字母设计哈夫曼编码； （）若用这三位二进制数(07)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几? 它使电文总长平均压缩多少?二、 算法设计题：本题共4小题，共60分。7.（15分）假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。8.（10分）回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。运用栈试写一个算法判定给定的字符向量是否为回文。9.（20分）假设循环队列中只设rear和quelen分别指示队尾元素的位置和队中元素的个数。（）试给出判定此循环队列的队满条件； （）写出相应的入队和出队算法，要求出队是需返回队头元素。10.（15分）利用C的库函数strlen，strcpy和strcat写一算法void StrInsert(char *S，char *T，int i)以实现将串T插到串S的第i个位置上的功能，要求当i大于S的长度时，则不执行该算法。卷号：A总分核分人姓 名一、密封线内不准答题。二、姓名、学号、班级不许涂改，否则试卷无效。三、考生在答题前应先将姓名、学号和班级填写在在指定的方框内。四、试卷印刷不清楚，可举手向监考教师询问。学 号所在年级、班级密封注意 意：二O一一 二O一二学年第二学期期末考试 数据结构 答题纸( 多个 专业用) (闭卷)题号一二三四五六七八九十题分4060得分注意：学号、姓名和所在年级班