(精品课件)数据结构课程试卷20卷.doc

(精品课件)数据结构课程试卷20卷.doc

  1. 1、本文档共4页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
(精品课件)数据结构课程试卷20卷

苏州大学 数据结构 课程试卷20卷(共 4 页) 考试形式:闭卷 年 月 院系 ______________ 年级 ______________ 专业 ______________ 学号 ______________ 姓名 ______________ 成绩 ______________ 填空(2分×15) 1、当一个算法的时间复杂度与问题的规模n大小无关时,时间复杂度表示为________;当一个算法的时间复杂度与问题的规模n成正比时,时间复杂度表示为________。 2、在双向链表中,每个结点含有两个指针域,一个指向__________结点,另一个指向_______结点。 3、二维数组A[5][6]按行存储,每个元素5个字节,若A[0][0]的起始地址是1000,则A[4][5]的起始地址为__________。 4、对于长度为n的线性表,若进行顺序查找,则时间复杂度为________,若进行折半查找,则时间复杂度为__________。 5、已知一组关键字为(19,14,23,1,68,20,84,27,55,11,10,79),哈希函数H(key)=key %13,采用线性探测再散列解决冲突,将这些元素放入 哈希表Hashtable[16]中,则84放入的位置是____________,在等查找概率情况下,查找成功时的平均查找长度为______________。 6、在一个图G的邻接表表示中,每个顶点的邻接表中所含的结点数,对于有向图而言等于该顶点的_______;而对于无向图而言等于该顶点的_________。 7、有3个结点的无序树的形态有_______种;有3个结点A、B、C的有序树有_______棵。 8、向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行的操作为_____________和______________。 二、应用题 1、已知一棵没有度为1(度为1表示只有一个孩子结点)结点的二叉树的先序和后序序列分别为ABCDFGHIE和BFHIGDECA,画出该二叉树。假定该二叉树是由一个森林转换而来的,画出此森林。(10分) 2、以递归树形式画出汉诺塔递归函数move(3,2,3,1)的执行过程。 (10分) 3、将1至9的9个整数填入下图所示二叉查找树的结点中,求出其在等概率情况下查找成功的平均查找长度,并画出删除数据值为4的结点后的二叉查找树。 (10分) 4、已知序列{70,83,100,65,10,32,7,9},请给出采用直接插入排序法以对该序列作升序排序时的每一趟的结果,并对直接插入排序的时间复杂度、所需辅助空间以及稳定性进行分析。(10分) 三、算法设计题 1、编写C++函数,对顺序表完成full 和retrieve操作: (10分) (1) full template class List_entry void ListList_entry :: full( ) (2) retrieve template class List_entry Error_code ListList_entry :: retrieve(int position, List_entry x) const 2、假设二叉查找树定义如下: typedef struct BiTNode{ TElemtype data; struct BiTNode *lchild; struct BiTNode *rchild; } BiTNode,*BiTree; 试设计一个递归算法,求出指定结点在给定的二叉查找树中的层次。(10分) int Tree_level (BiTree T,TElemtype x ); 3、(1)编写一个递归函数 int gcd (int x , int y) ,求两个正整数x和y的最大公约数。请使用Euclid算法:若y=0,则x和y的最大公约数等于y和x % y的最大公约数。(2)编写一个非递归函数 int gcd (int , int y)。(10分) 2 4

文档评论(0)

yan698698 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档