2017华科计算机专业课分享

P灰灰 · 发表于 2017-8-24 13:38

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 2 3 4 5 6 7 8 9 10
Answer
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分）
No. 1 2 3 4 5 6 7 8 9 10
Answer
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；