湖工数据结构

《湖工数据结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、卷号：A总分核分人姓名一、密封线内不准答题。二、姓名、学号、班级不许涂改，否则试卷无效。三、考生在答题前应先将姓名、学号和班级填写在在指定的方框内。四、试卷印刷不清楚，可举手向监考教师询问。学号所在年级、班级密封注意意：二O一一—二O一二学年第二学期期末考试数据结构试题(多个专业用)(闭卷)题号一二三四五六七八九十题分4060得分注意：学号、姓名和所在年级班级不写、不写全或写在密封线外者，试卷作废。一、简答题：本题共6小题，共40分。1.（4分）简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。2.（4分）简述下列每对术语的区别：空串和空白串

2、；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串。3.（6分）在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删除？若可以，分别求出其时间复杂度。4.（6分）简述循环队列的优点，并写出判断循环队列的空和满的方法。5.（10分）指出下述程序段的功能。(Ⅰ)SeqStackS1,S2,tmp;DataTypex;...//假设栈tmp和S2已做过初始化while(!StackEmpty(&S1)){x=Pop(&S1);Push(&tmp,x);}while(!StackEmpty(&tmp)){x=Pop(&tmp);

3、Push(&S1,x);Push(&S2,x);}(Ⅱ)voidDemo2(SeqStack*S,intm){//设DataType为int型SeqStackT;inti;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}

4、。（Ⅰ）为这8个字母设计哈夫曼编码；（Ⅱ）若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少?一、算法设计题：本题共4小题，共60分。7.（15分）假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。8.（10分）回文是指正读反读均相同的字符序列，如"abba"和"abdba"均是回文，但"good"不是回文。运用栈试写一个算法判定给定的字符向量是否为回文。9.（20分）假设循环队列中只设rear和quelen分别指示队尾元素的位置和队中元素的

5、个数。（Ⅰ）试给出判定此循环队列的队满条件；（Ⅱ）写出相应的入队和出队算法，要求出队是需返回队头元素。10.（15分）利用C的库函数strlen，strcpy和strcat写一算法voidStrInsert(char*S，char*T，inti)以实现将串T插到串S的第i个位置上的功能，要求当i大于S的长度时，则不执行该算法。卷号：A总分核分人姓名一、密封线内不准答题。二、姓名、学号、班级不许涂改，否则试卷无效。三、考生在答题前应先将姓名、学号和班级填写在在指定的方框内。四、试卷印刷不清楚，可举手向监考教师询问。学号所在年级、班级密封注意意：二O一一—二O一二学年第二学期期末考试数据

6、结构答题纸(多个专业用)(闭卷)题号一二三四五六七八九十题分4060得分注意：学号、姓名和所在年级班级不写、不写全或写在密封线外者，试卷作废。一、简答题：本题共6小题，共40分。1.2.3.4.5.6.一、算法设计题：本题共4小题，共60分。7.8.9.10.