09计科《数据结构》期末考B答案(本科).docVIP

武夷学院期末考试试卷 （ 09级 计算机科学与技术 专业2010 ～2011学年度 第 1 学期） 课程名称 数据结构 B 卷 考试形式 闭卷 考核类型 考试 本试卷共 五大题，卷面满分100分，答题时间120分钟。 参考答案及评分标准 题号 一 二 三 四 五 六 七 八 总分 复核人 得分 得分 评卷人 一、选择题：（本大题共10小题，每小题2分，共20分） 　　1-5． D　D　A　C　B　　6-10． B　B　C　A　 二、填空题（每空2分，共20分） 　　1．(n-1)/2　　2．操作受限后进先出的线性表 　　3．3 　　4．38　　5．稀疏 　　6．20/7　　7．顺序 　　8．同义词 　　9．中根 　　10．(s.top-s.base)=L三、应用题（共50分） 　　1．（5分）答： 　　顺序存储：用地址连续的地址表示逻辑上的相邻关系。可以实现随机存取，但进行插入删除操作时需要移动大量元素。适合于查询操作比较多时。 　　链式存储：用随机的不连续的存储地址存储线性表，通过指针来表示逻辑上的相邻关系。不能随机存储，要找到链表里面某一元素时必须从头指针开始，依次访问链表。插入删除操作时只需修改指针，不用移动元素。适合插入、删除操作比较多时。 　　评分细则：两者定义2分，优点2分，缺点2分。 2．答：　　　(1)先：abdghcef　　　中：dhgbaefc　　　后：hgdbfeca（3分） 　　　(2) 　　　　　　　　　　　　　　　　　　　　　　　 （3分） 　　　　 ????(3) （4分）　　　　 3．（5分）答：　　　　　 　4．（8分）答： 　　　(1)　C D B A F E　　　(2)　C D A B F E　　评分细则：（1）4分；（2）4分。 　　5．（7分）答： 　　　(1)　15 18 10 26 62 37 29 85 　　　(2)　10 15 18 26 29 37 62 85　　　(3)　10 15 18 26 29 37 62 85　　评分细则：（1）2分；（2）2分；（3）3分。 　　6．（7分）答 ： 　　　(1) head(tail(head(L1)))　　　(2) head(head(head(tail(L2))))　　评分细则：（1）3分；（2）4分。 7．（8分）答： 　　　　 　　　　　　(1) 　　　　　(2)　　　　　(3)　　　　　　　　　(4)　　　　　　　　　　(5) 　　　　 　　　　　　(1)　　　　　　　　(2)　　　　　　　(3)　　　　　　　　(4)　　　　　　(5) 　　　　评分细则：Prim（普里姆）和Kruskal（克鲁斯卡尔）最小树各4分。 四、算法设计（每题5分，共10分） 　　1．（5分）　　void InsertLlist(LinkList L，ElemType x)　　　{ LinkList P,S,q;　　　　P=L-next;q=L;　　　　for(;PP-datax;q=P;P=P-next);　　　　S=(LinkList)malloc(sizeof(LinkNode));　　　　S-data=x;　　　　S-next=NULL;　　　　S-next=P;　　　　q-next=S;　　} 2．（5分）　　void　Function(Stack S,int a[n])　　{　 int i,e,length;　　　　for(i=0;in;i++)　　　{ if(a[i]==-1)　　　{ if((S.top-S.base)=StackLength(S))　　　　{　S.base=(ElemTyp*)realloc(S.base,(S.stacksize+StackIncrement)* sizeof(ElemType));　　　　　 S.top=S.base+S.stacksize;　　　　　 S.stacksize= S.stacksize+StackIncrement;}　　　　　 Push(S,s[i]);　　　else 　　　　if(!StackEmpty) {Pop(S,e);Printf(e); }　　}　} 5 系别 专业（班级） 姓名 学号 ………………………密……………………封…………………………装…………………订……………………