谁有华北水利水电学院的数据结构、计算机组成原理历年期末试题？_百度知道
谁有华北水利水电学院的数据结构、计算机组成原理历年期末试题？
提问者采纳
其他类似问题
为您推荐：
您可能关注的推广回答者：
华北水利水电学院的相关知识
其他1条回答
我有组成原理的
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁您还未登陆，请登录后操作！
谁有济南大学计算机专业（最好是科学方向的）数据结构期末考试题？
呵呵，仔细把以前笔记好好看看吧
以往试题一般找不到。。。
您的举报已经提交成功，我们将尽快处理，谢谢！
大家还关注一、单选题(每小题 2 分，共 12 分) 1．在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的 结点，则执行( B )。 A． HL＝ps p 一&next＝HL B． p 一&next＝HL；HL＝p3 C． p 一&next＝Hl；p＝HL； D． p 一&next＝HL 一&HL 一&next＝p； 2．n 个顶点
的强连通图中至少含有( B )。 A.n―l 条有向边 B.n 条有向边 C.n(n―1)／2 条有向边 D.n(n 一 1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 ( C )。A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为 3，8，6，2，5 的叶子结点生成一棵哈夫曼树， 它的带权路径长度为( D )。A．24 B．48 C． 72 D． 53 5． 当一个作为实际传递的对象占用的存储空间较大并可能需要修 改时，应最好把它说明为( B )参数，以节省参数值的传输时间和 存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型? 6． 向一个长度为 n 的顺序表中插人一个新元素的平均时间复杂度 为( A )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空 1 分，共 28 分) 索引结 1．数据的存储结构被分为顺序结构、 链接结构 构和散列结构四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域 对应不同，各自分别为值(或 data)域和子表指针(或 sublist)域。 3．3 x 2 中缀表达式 3 十 x*(2.4／5―6)所对应的后缀表达 式为 4 5／6 一*十。 4．在一棵高度为 h 的 3 叉树中，最多含有(3h 一 1)／2 结点。 5． 假定一棵二叉树的结点数为 18， 则它的最小深度为 5 ， 最大深度为 18? 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的 值一定小于该结点的值， 右子树上所有结点的值一定大于该结点 的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要 逐层向上堆顶调整，直到被调整到堆顶位置为止。 8．表示图的三种存储结构为邻接矩阵、邻接表和边集数组。9．对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种 遍历时，其时间复杂度为 O(n2)，对用邻接表表示的图进行任一 种遍历时，其时间复杂度为 O(e)。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查 找 43 和 56 元素时，其查找长度分别为 1 和 3? 11．假定对长度 n＝144 的线性表进行索引顺序查找，并假定每 个子表的长度均为 ，则进行索引顺序查找的平均查找长度为 13，时间复杂度为 O( )? 12．一棵 B―树中的所有叶子结点均处在同一层上。 13．每次从无序表中顺序取出一个元素，把这插入到有序表中的 适当位置，此种排序方法叫做插人排序；每次从无序表中挑 选出一个最小或最大元素，把它交换到有序表的一端，此种 排序方法叫做选择排序。 14．快速排序在乎均情况下的时间复杂度为 O(nlog2n)，最坏情 况下的时间复杂度为 O(n2)。 三、运算题(每小题 6 分，共 24 分) 1．假定一棵二叉树广义表表示为 a(b(c，d)，c(((，8)))，分别写 出对它进行先序、中序、后序和后序遍历的结果。 先序：a，b，c，d，e，f，e 中序；c，b，d，a，f，8，e 后序：c，d，b，e，f，e，a 2．已知一个带权图的顶点集 V 和边集 G 分别为： V＝{0，1，2，3，4，5}； E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13， (3，5)9，(4，5)10}， 则求出该图的最小生成树的权。 最小生成树的权：31 、 3．假定一组记录的排序码为(46，79，56，38，40，84，50，42)， 则利用堆排序方法建立的初始堆为(84，79，56，42，40，46， 50，38) 。 4．有 7 个带权结点，其权值分别为 3，7，8，2，6，10，14， 试以它们为叶子结点生成一棵哈夫曼树， 求出该树的带权路径长 度、高度、双分支结点数。 带权路径长度：131 高度：5 双分支结点数：6。 四、阅读算法，回答问题(每小题 8 分，共 16 分) 1．VOldAC(List&L) {InitList(L)； InsertRear(L;25)； InsertFront(L，50)； IntaL4]＝{5，8，12，15，36}; for(inti＝0; i&5; i++) if (a[i]％2＝＝0)InsertFront(L，a[i])； elselnsertRear(L，a[i])； } 该算法被调用执行后，得到的线性表 L 为：(36，12，8，50，25， 5，15) 2．void AG(Queue&Q) { InitQueue(Q)； inta[5]＝{6，12，5，15，8}； for(int i＝0;i&5; i++)QInsert(Q，a[i])； QInsert(Q，QDelete(Q))； QInsert(Q，20)； QInsert(Q，QDelete(Q)十 16)； while(!QueueEmpty(Q))cout&&QDelete(Q)&&” ； } 该算法被调用后得到的输出结果为：5 15 8 6 20 28 五、算法填空，在画有横线的地方填写合适的内容(每小题 6 分，共 12 分) 1．从一维数组 A[n)中二分查找关键字为 K 的元素的递归算法， 若查找成功则返回对应元素的下标，否则返回一 1。 IntBinsch(ElemTypeA[]，Intlow，int high，KeyTypeK) { if(low&＝high) { int mid＝(low+high)／2； if(K＝＝A[mid].key)feturn mid ； else if (K&A[mid].key)returnBinsch(A，low，mid 一 1，K)； returnBmsch(A，mid+1，high，K)； else ； } else return―l； } 2．已知二叉树中的结点类型 BinTreeNode 定义为：structBinTreeNode{ElemType data；BinTreeNode*left，*right}； 其中 data 为结点值域， 和 right 分别为指向左、 left 右子女结点的 指针域。下面函数的功能是返回二叉树 BT 中值为 x 的结点所在 的层号，请在划有横线的地方填写合适内容。 Int NodeLevel(BinTreeNode * BT，ElemType X) { if(BT：＝NULL)return 0； ／／空树的层号为 0 else if(BT 一&data＝＝X)return 1; ／／根结点的层号为 1 ／／向子树中查找 x 结点 else{ int cl＝NodeLevel(BT 一&left，X)； if(cl&＝1)return cl+1; int c2＝ ； ifNodeLevel(BT 一&right，X)；(c2&=1)returnc2 十 1 ／／若树中不存在 X 结点则返回 o else return 0； } } 六、编写算法(8 分) 按所给函数声明编写一个算法，从表头指针为 HL 的单链表中查 找出具有最大值的结点，该最大值由函数返回，若单链表为空则 中止运行。 EIemType MaxValue(LNOde*HL); { if (HL＝=NUlL){ ／／2 分 cerr&&&Linked llst is empty!”&&endl； exit(1)； } ElemTypemax：HL 一&data； ／／3 分 LNOde*p=HI 一&next； ／／4 分 while(P!：NULL){ ／／7 分 if(max&p 一&data)max＝p 一&data； p＝p 一&next； } returnmax； ／／8 分 }
数据结构期末考试试题(有答案)―汇集和整理大量word文档,专业文献,应用文书,考试资料,教学教材,办公文档,教程攻略,文档搜索下载下载,拥有海量中文文档库,关注高价值的实用信息,我们一直在努力,争取提供更多下载资源。数据结构C语言版期末考试试题(有答案)49-第3页
上亿文档资料，等你来发现
数据结构C语言版期末考试试题(有答案)49-3
22.队列是被限定为只能在表的一端进行插入运算；在表的另一端进行删除运算的线性表；23.不包含任何字符（长度为0）的串称为空串；由；24.子串的定位运算称为串的模式匹配；被匹配的主；子串称为模式；25.假设有二维数组A6×8；每个元素用相邻的6个字节存储；存储器按字节编址；已知A的起始存储位置（基地址）为1000；则数组A的体积（存储量）为288B；末尾元素
是被限定为只能在表的一端进行插入运算在表的另一端进行删除运算的线性表 23.
不包含任何字符（长度为0）的串
称为空串；
由一个或多个空格（仅由空格符）组成的串
称为空白串 24. 子串的定位运算称为串的模式匹配； 被匹配的主串
称为目标串子串
称为模式 25. 假设有二维数组A6×8每个元素用相邻的6个字节存储存储器按字节编址已知A的起始存储位置（基地址）为1000则数组A的体积（存储量）为
；末尾元素A57的第一个字节地址为
若按行存储时元素A14的第一个字节地址为
；若按列存储时元素A47的第一个字节地址为
(6×7＋4)×6＋1000）＝1276 26． 由３个结点所构成的二叉树有
种形态 27.
一棵深度为6的满二叉树有 n1+n2=0+ n2= n0-1=31
个分支结点和 26-1 =32
子 注：满二叉树没有度为1的结点所以分支结点数就是二度结点数 28． 一棵具有２５７个结点的完全二叉树它的深度为
9 （ 注：用? log2(n) ?+1= ? 8.xx ?+1=929．设一棵完全二叉树有700个结点则共有
个叶子结点 答：最快方法：用叶子数＝[n/2]＝35030． 设一棵完全二叉树具有1000个结点则此完全二叉树有 500
个叶子结点有
个度为2的结点有
个结点只有非空左子树有
个结点只有非空右子树 答：最快方法：用叶子数＝[n/2]＝500n2=n0-1=499另外 ；个叶最后一结点为2i属于左叶子右叶子是空的所以有1个非空左子树完全二叉树的特点决定不可能有左空右不空的情况所以非空右子树数＝0.31．在数据的存放无规律而言的线性表中进行检索的最佳方法是
顺序查找（线性查找）32. 线性有序表（a1a2a3...a256)是从小到大排列的对一个给定的值k用二分法检索表中与k相等的元素在查找不成功的情况下最多需要检索
次设有100个结点用二分法查找时最大比较次数是
7 33. 假设在有序线性表a[20]上进行折半查找则比较一次查找成功的结点数为1；比较两次查找成功的结点数为
；比较四次查找成功的结点数为
；平均查找长度为
3.7 解：显然平均查找长度＝O（log2n）&5次（25）但具体是多少次则不应当按照公式来计算（即（21×log221）/20＝4.6次并不正确！）因为这是在假设n＝2m-1的情况下推导出来的公式应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7
！！！34．折半查找有序表（4612202838507088100）若查找表中元素20它将依次与表中元素
比较大小 35. 在各种查找方法中平均查找长度与结点个数n无关的查找方法是
散列查找 36. 散列法存储的基本思想是由
关键字的值
决定数据的存储地址二、判断正误（在正确的说法后面打勾反之打叉）（ ×
）1. 链表的每个结点中都恰好包含一个指针 答：错误链表中的结点可含多个指针域分别存放多个指针例如双向链表中的结点可以含有两个指针域分别存放指向其直接前趋和直接后继结点的指针 （ ×
）2. 链表的物理存储结构具有同链表一样的顺序错链表的存储结构特点是无序而链表的示意图有序 （ ×
）3. 链表的删除算法很简单因为当删除链中某个结点后计算机会自动地将后续的各个单元向前移动错链表的结点不会移动只是指针内容改变 （ ×
）4. 线性表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型 错混淆了逻辑结构与物理结构链表也是线性表！且即使是顺序表也能存放记录型数据 （ ×
）5. 顺序表结构适宜于进行顺序存取而链表适宜于进行随机存取 正好说反了顺序表才适合随机存取链表恰恰适于&顺藤摸瓜&（ ×
）6. 顺序存储方式的优点是存储密度大且插入、删除运算效率高 错前一半正确但后一半说法错误那是链式存储的优点顺序存储方式插入、删除运算效率较低在表长为n的顺序表中插入和删除一个数据元素平均需移动表长一半个数的数据元素 （ ×
）7. 线性表在物理存储空间中也一定是连续的 错线性表有两种存储方式顺序存储和链式存储后者不要求连续存放 （ ×
）8. 线性表在顺序存储时逻辑上相邻的元素未必在存储的物理位置次序上相邻 错误线性表有两种存储方式在顺序存储时逻辑上相邻的元素在存储的物理位置次序上也相邻 （ ×
）9. 顺序存储方式只能用于存储线性结构 错误顺序存储方式不仅能用于存储线性结构还可以用来存放非线性结构例如完全二叉树是属于非线性结构但其最佳存储方式是顺序存储方式（后一节介绍）（ ×
）10. 线性表的逻辑顺序与存储顺序总是一致的 错理由同7链式存储就无需一致（ ×
）11. 线性表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型 错线性表是逻辑结构概念可以顺序存储或链式存储与元素数据类型无关 （ ×
）12. 在表结构中最常用的是线性表栈和队列不太常用 错不一定吧？调用子程序或函数常用CPU中也用队列 （ √
）13. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表 是一种后进先出型结构 （ √
）14. 对于不同的使用者一个表结构既可以是栈也可以是队列也可以是线性表 正确都是线性逻辑结构栈和队列其实是特殊的线性表对运算的定义略有不同而已 （ ×
）15. 栈和链表是两种不同的数据结构 错栈是逻辑结构的概念是特殊殊线性表而链表是存储结构概念二者不是同类项 （ ×
）16. 栈和队列是一种非线性数据结构 错他们都是线性逻辑结构栈和队列其实是特殊的线性表对运算的定义略有不同而已 包含各类专业文献、幼儿教育、小学教育、中学教育、各类资格考试、生活休闲娱乐、数据结构C语言版期末考试试题(有答案)49等内容。　
　数据结构C语言版期末考试试题(有答案)_理学_高等教育_教育专区。心有多大,舞台就有多大!有努力就会有回报! &数据结构&期末考试试题 一、单选题(每小题 2 分共... 　数据结构C语言版期末考试试题(有答案)_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报文档 数据结构C语言版期末考试试题(有答案)_理学_高等教育_教育... 　数据结构C语言版期末考试试题(附带复习资料)_文学_高等教育_教育专区。“数据结构...EIemType MaxValue(LNOde*HL); “数据结构”期末考试试题答案 一、单选题(每... 　数据结构c语言版期末考试复习试题1_理学_高等教育_教育专区。《数据结构与算法》...数据结构复习试题(附答案... 10页 免费 数据结构期末考试复习试... 11页 免费... 　数据结构c语言版期末考试复习试题_理学_高等教育_教育专区。《数据结构与算法》复习题 一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态... 　数据结构c语言版试题大全(含答案)_IT认证_资格考试/认证_教育专区。很不错的数据结构c语言版试题大全(含答案)1 绪论 沈阳理工大学应用技术学院 信息与控制学院 计... 　数据结构c语言版期末考试试题_理学_高等教育_教育专区。《数据结构与算法》复习题...历算法类似于二叉树的按层遍历 87.具有 n 个结点的连通图至少有 n-1 条边... 　数据结构C语言版期末试卷_工学_高等教育_教育专区。...数据结构试卷参考答案一、选择题 1.D 2.B 3.C ...设有两个集合 A 和集合 B,要求设计生成集合 C=A... 　数据结构C语言版期末考试复习试题_理学_高等教育_教育专区。《数据结构与算法》复习题一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结...大学数据结构期末考试试题(有答案)答案,大学,数据结构,大学试题
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
大学数据结构期末考试试题(有答案)
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口}