华科834复习资料.pdf-资料库

2018 年华中科技大学 834 计算机专业基础综合复习八套卷一（版）一．填空题（20 分，每题 2 分） 1. 在一个长度为 n 的顺序表中第 i 个元素（1<=i<=n）之前插入一个元素时，需向后移动个元素。 2. 栈是的线性表，其运算遵循的原则 3. 表达式 23+((12*3-2)/4+34*5/7)+108/9 的后缀表达式是。 4. 己知三对角矩阵 A[1..9,1..9]的每个元素占 2 个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A[7,8]的地址为。 5. 对矩阵压缩是为了。 6. 在哈希函数 H（key）=key%p 中，p 值最好取。 7. IP 地址 21.12.240.17 的网络类别是类，主机号是。 8. 100BASE-T 标准规定的信号是，网络速率是。 9. 信息传输速率的单位是，码元传输速率的单位是。 10. 在 TCP/IP 网络中，TCP 协议工作在，FTP 协议工作在。二．判断题（20 分，每个 2 分） No. 1 Answer 2 3 4 5 6 7 8 9 10 1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（） 2. 数据的物理结构是指数据在计算机内的实际存储形式。（） 3. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（） 4. 数组不适合作为任何二叉树的存储结构。（） 5. B-树中所有结点的平衡因子都为零。（） 6. 对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（） 7. 在 OSI 参考模型中，最上层是物理层。（） 8. 在 TCP 段头中，窗口数的大小由发送方决定。（） 9. 带宽的基本单位是 bps,吞吐量的基本单位是 Mbps。（） 10. 一个 IPv4 地址表示 193.168.125.0/30，其中，30 表示主机的位数。（）

三．选择题（30 分，每个 3 分） 2 3 4 5 6 7 8 9 10 No. Answer 1 1. int frog｛ if(n==0) return 1; else return （n+frog（n-1）/2）; ｝上述算法时间复杂度是多少（） A. logn B.n C. nlogn D. (n)`2 2. 连续存储设计时，存储单元的地址（）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 3. 一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A[1..n] 中，则二叉树中第 i 个结点（i 从 1 开始用上述方法编号）的右孩子在数组 A 中的位置是（） A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 4. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为 1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 5. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（）。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ.{5,9,17,21,23,25,30} 6. 下列哪一种图的邻接矩阵是对称矩阵？（） A．有向图 B．无向图 C．AOV 网 D．AOE 网 7. 通信子网中的最高层是（）。 A．数据链路层 B．传输层 C．网络层 D．应用层 8. 计算机网络中的 0SI 参考模型的三个主要概念是（）。 A．服务、接口、协议 B．子网、层次、端口 C．结构、模型、交换 D．广域网、城域网、局域网 9. 下列哪一种传输方式被用于计算机内部的数据传输？（）。

A．串行传输 B．并行传输 C．同步传输 D．异步传输 10. 为了使数字信号传输得更远，可以采用的设备是（）。 A．中继器 B．放大器 C．网桥 D．路由器四．简答题（60 分） 1. 已知一棵二叉树的后序遍历序列为 EICBGAHDF，同时知道该二叉树的中序遍历序列为 CEIFGBADH，试画出该二叉树。 2.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： 1）.归并排序每归并一次书写一个次序。 2）.快速排序每划分一次书写一个次序。 3. 已知无向图如下所示：（1）．给出从 V1 开始的广度优先搜索序列；（2）．画出它的邻接表；（3）．画出从 V1 开始深度优先搜索生成树。

4. 一个 CSMA／CD 基带总线网长度为 1000 米，信号传播速度为 200 米／微秒，假如位于总线两端的节点，在发送数据帧时发生了冲突，试问：（1）两节点问的信号传播延迟是多少？（2）最多经过多长时间才能检测到冲突？ 5. 公用机房有三个计算机室共有 180 台计算机，网络地址号为 192.168.10.0，按 60 台计算机一个计算机室划分子网，请计算出各计算机室的子网掩码和 IP 地址段。五．算法设计（20 分）（请使用类 C 语言进行编程，如果编码困难可以写伪代码，会适当扣分）设计一个算法将二叉树中所有结点的左，右子树相互交换。 typedef struct BiTree { int data； struct BiTree *rchild； struct BiTree *lchild； } * BiTree；

2018 年华中科技大学 834 计算机专业基础综合复习八套卷一（版）参考答案一．填空题（20 分，每题 2 分） 11. 在一个长度为 n 的顺序表中第 i 个元素（1<=i<=n）之前插入一个元素时，需向后移动 n-i +1 个元素。 12. 栈是操作受限（或限定仅在表尾进行插入和删除操作）的线性表，其运算遵循后进先出的原则。 13. 表达式 23+((12*3-2)/4+34*5/7)+108/9 的后缀表达式是 23.12.3*2- 4/34.5*7/++108.9/+。 14. 己知三对角矩阵 A[1..9,1..9]的每个元素占 2 个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A[7,8]的地址为 1038。三对角矩阵按行存储：k=2(i-1)+j (1<=i,j<=n) 15. 对矩阵压缩是为了节省存储空间。 16. 在哈希函数 H（key）=key%p 中，p 值最好取小于等于表长的最大素数或不包含小于 20 的质因子的合数。 17. IP 地址 21.12.240.17 的网络类别是 A 类，主机号是 12.240.17 。 18. 100BASE-T 标准规定的信号是基带，网络速率是 100Mb/s 。 19. 信息传输速率的单位是比特/秒，码元传输速率的单位是波特。 20. 在 TCP/IP 网络中，TCP 协议工作在传输层，FTP 协议工作在应用层。二．判断题（20 分，每个 2 分） No. 1 2 3 4 5 6 7 8 9 10 Answer × √ √ × √ √ × × × × 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ × ） 12. 数据的物理结构是指数据在计算机内的实际存储形式。（ √ ） 13. 栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ √ ） 14. 数组不适合作为任何二叉树的存储结构。（ × ） 15. B-树中所有结点的平衡因子都为零。（ √ ）

16. 对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（ √ ） 17. 在 OSI 参考模型中，最上层是物理层。（ × ） 18. 在 TCP 段头中，窗口数的大小由发送方决定。（ × ） 19. 带宽的基本单位是 bps,吞吐量的基本单位是 Mbps。（ × ） 20. 一个 IPv4 地址表示 193.168.125.0/30，其中，30 表示主机的位数。（ × ）三．选择题（30 分，每个 3 分） 2 3 4 5 6 7 8 9 10 A D C A B C A B A No. Answer 1 B 2. int frog｛ if(n==0) return 1; else return （n+frog（n-1）/2）; ｝上述算法时间复杂度是多少（ B ） A. logn B.n C. nlogn D. (n)`2 2. 连续存储设计时，存储单元的地址（ A ）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 3. 一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A[1..n] 中，则二叉树中第 i 个结点（i 从 1 开始用上述方法编号）的右孩子在数组 A 中的位置是（ D ） A．A[2i](2i<=n) B．A[2i+1](2i+1<=n) C．A[i-2] D．条件不充分，无法确定 4. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为 1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 5. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ A ）。 A． {21,25,5,17,9,23,30} B．{25,23,30,17,21,5,9} C． {21,9,17,30,25,23,5} Ｄ.{5,9,17,21,23,25,30} 6. 下列哪一种图的邻接矩阵是对称矩阵？（ B ） A．有向图 B．无向图 C．AOV 网 D．AOE 网 7. 通信子网中的最高层是（ C ）。 A．数据链路层 B．传输层

C．网络层 D．应用层【解析】所谓通信子网，就是计算机网络中负责数据通信的部分；通信子网包括物理层数据链路层和网络层，网络层是通信子网中的最高层。 8. 计算机网络中的 0SI 参考模型的三个主要概念是（ A ）。 A．服务、接口、协议 B．子网、层次、端口 C．结构、模型、交换 D．广域网、城域网、局域网【解析】OSI 模型，即开放式通信系统互联参考模型，是国际标准化组织（ISO）提出的一个试图使各种计算机在世界范围内互连为网络的标准框架，简称 OSI。0SI／RM 协议是由 IS0 制定的，它有三个基本的功能：提供给开发者一个必须的、通用的概念以便开发完善、可以用来解释连接不同系统的框架。OSI 模型采用分层的设计实现上述要求，每层采用不同的协议，下层为上层提供服务，上层通过下层提供的接口使用下层的服务。 9. 下列哪一种传输方式被用于计算机内部的数据传输？（ B ）。 A．串行传输 B．并行传输 C．同步传输 D．异步传输【解析】并行传输的特点：距离短、速度快。串行传输的特点：距离长、速度慢。在计算机内部传输应该选择并行。而同步、异步传输是通信方式，不是传输方式。 10. 为了使数字信号传输得更远，可以采用的设备是（ A ）。 A．中继器 B．放大器 C．网桥 D．路由器【解析】A 项，中继器是把一根线缆中的电或者光信号传递给另一根线缆，不进行路由选择，也不进行分组过滤的物理层联网设备，中继器的作用是延长以太网通信介质的长度，扩大以太网覆盖范围。中继器一般用在模拟信号中，放大器用在数字信号传输中。C 项，网桥是一种用来连接两个物理网段的设备，可以扩展物理网络的覆盖范围。D 项路由器也是一种网络互联设备，在网络层实现了不同网络的互联。四．简答题（60 分） 1. 已知一棵二叉树的后序遍历序列为 EICBGAHDF，同时知道该二叉树的中序遍历序列为 CEIFGBADH，试画出该二叉树。

2.给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： 1）.归并排序每归并一次书写一个次序。 2）.快速排序每划分一次书写一个次序。 (1)2 路归并第一趟:18,29,25,47,12,58,10,51；第二趟:18,25,29,47,10,12,51,58；第三趟:10,12,18,25,29,47,51,58 (2)快速排序第一趟:10,18,25,12,29,58,51,47；第二趟:10,18,25,12,29,47,51,88；第三趟:10,12,18,25,29,47,51,88 3. 已知无向图如下所示：（1）．给出从 V1 开始的广度优先搜索序列；（2）．画出它的邻接表；（3）．画出从 V1 开始深度优先搜索生成树。设邻接表（略）中顶点的邻接点按顶点编号升序排列（V1 编号为 1）（2）广度优先搜索序列：V1V2V3V4V5V6V7V8 （3）深度优先搜索序列：V1V2V4V8V5V3V6V7 4. 一个 CSMA／CD 基带总线网长度为 1000 米，信号传播速度为 200 米／微秒，假如位于总线两端的节点，在发送数据帧时发生了冲突，试问：（1）两节点问的信号传播延迟是多少？（2）最多经过多长时间才能检测到冲突？答：1）1000/200=5 微秒 2）5x2=10 微秒（往返的时间） 5. 公用机房有三个计算机室共有 180 台计算机，网络地址号为 192.168.10.0，按 60 台计算机一个计算机室划分子网，请计算出各计算机室的子网掩码和 IP 地址段。要把 180 台计算机化成三个子网，每个子网 60 台计算机，所以需要将 IP 地址分成三个子网，三个子网需要有三位作为网络号，所以这三个子网的子网掩码应该是 11111111.11111111.11111111.11100000=255.2555.255.224 每个子网的地址分别应该是： 192.168.10.1---192.168.10.63 （默认网关：192.168.10.1） 192.168.10.64---192.168.10.127 （默认网关：192.168.10.65）

资料库

华科834复习资料.pdf

相关推荐

课程资源

热门标签

最新资料