下载文档原格式
2022年湖南科技大学软件工程专业《计算机网络》科目期末试卷A（有答案）一、选择题1、世界上第一个计算机网络是（）。
A.ARPANETB.因特网C.NSFnetD.CERNET2、以下说法错误的是（）。
I..广播式网络一般只包含3层，即物理层、数据链路层和网络层II.Intermet的核心协议是TCP/IPIII.在lnternet中，网络层的服务访问点是端口号A. I、II、IIIB. IIIC. I、ⅢD. I、II3、如果一台主机的IP地址为160.80.40.20/16，那么当它被移动到了另一个不属于160.80/16子网的网络中时，它将（）。
A.可以直接接收和直接发送分组，没有任何影响B.既不可以直接接收分组，也不可以直接发送分组C.不可以直接发送分组，但是可以直接接收分组D.可以直接发送分组，但是不可以直接接收分组4、RIP规定，（）跳为一条不可达路径A.1024B.512C.16D.85、假设物理信道的传输成功率是95%，而平均一个网络层的分组需要10个数据链路层的帧来发送。
如果数据链路层采用了无确认的无连接服务，那么发送网络层分组的成功率是（）。
A.40%B.60%C.80%D.95%6、下列关于交换机的叙述中，正确的是（）A.以太网交换机本质上是一种多端口网桥B.通过交换机互连的一组工作站构成一个冲突域C.交换机每个端口所连网络构成一个独立的广播域D.以太网交换机可实现采用不同网络层协议的网络互连7、一个TCP连接的数据传输阶段，如果发送端的发送窗口值由2000变为3000，意味着发送端可以（）。
A.在收到一个确认之前可以发送3000个TCP报文段B.在收到一个确认之前可以发送1000BC.在收到一个确认之前可以发送3000BD.在收到一个确认之前可以发送2000个TCP报文段8、A和B之间建立了TCP连接，A向B发送了一个报文段，其中序号字段seq=300，确认号字段ACK=101，数据部分包含7个字节，那么在B对该报文的确认报文段中（）。
数据结构(一)一、选择题1.组成数据的基本单位是(C )。
(A)数据项(B)数据类型(C)数据元素(D)数据变最2.设数据结构A=(D, R),其中D={1, 2, 3, 4}, R={r}, r={<l, 2>, <2, 3>, <3, 4>, <4, 1>},则数据结构人是(C )o(A)线性结构(B)树型结构(C)图型结构(D)集合3、数组的逻辑结构不同于下列(D )的逻辑结构。
(A)线性表(B)栈(C)队列(D)树4、二叉树中第i (i$l)层上的结点数最多有(C )个。
(A) 2i (B) 21(C) 2i_1(D) 2i-l5、设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为(A )。
(A) p->next=p-〉next-〉next (B) p=p->next(C) p二p->next->next (D) p->next=p6、设栈S和队列Q的初始状态为空，元素El、E2、E3、E4、E5和E6依次通过栈S, —个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是(C )。
(A) 6 (B) 4 (C) 3 (D) 27、将10阶对称矩阵压缩存储到一维数组A屮，则数组A的长度最少为(C )0(A) 100 (B) 40 (C) 55 (D) 808、设结点A冇3个兄弟结点H.结点B为结点A的双亲结点，则结点B的度数数为(B )。
(A) 3 (B) 4 (0 5 (D) 19、根据二义树的定义可知二义树共有(B )种不同的形态。
(A) 4 (B) 5 (0 6 (D) 710、设有以下四种排序方法，则(B )的空间复杂度最人。
(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序11、以下说法正确的是(A )A.连通图的牛成树，是该连通图的一个极小连通子图。
2022年湖南科技大学软件工程专业《计算机系统结构》科目期末试卷B（有答案）一、选择题1、流水机器对全局性相关的处理不包括( )A.猜测法B.提前形成条件码C.加快短循环程序的执行D.设置相关专用通路2、非线性流水线是指( )A.一次运算中使用流水线中的多个功能段B.一次运算中要多次使用流水线中的某些功能段C.流水线中某些功能段在各次运算中的作用不同D.流水线的各个功能段在各种运算中有不同的组合3、不同系列的机器之间，实现软件移植的途径不包括( )A.用统一的高级语言B.用统一的汇编语言C.模拟D.仿真4、"一次重叠"中消除"指令相关"最好的方法是( )。
A.不准修改指令B.设相关专用通路C.推后分析下条指令D.推后执行下条指令5、系列机软件应做到( )。
A.向前兼容，并向上兼容B.向后兼容，力争向上兼容C.向前兼容，并向下兼容D.向后兼容，力争向下兼容6、对机器语言程序员透明的是( )。
A.中断字B.主存地址寄存器C.通用寄存器D.条件码7、计算机中优化使用的操作码编码方法是( )。
（书上为扩展编码法）A哈夫曼编码B ASCII码C BCD码D扩展操作码8、在计算机系统的层次结构中，机器被定义为（）的集合体A.能存储和执行相应语言程序的算法和数据结构B.硬件和微程序（固件）C.软件和固件D.软件和硬件9、多处理机的各自独立型操作系统（）。
A.要求管理程序不必是可再入的B.适合于紧耦合多处理机C.工作负荷较平衡D.有较高的可靠性10、若输入流水线的指令既无局部性相关，也不存在全局性相关，则（）。
A.可获得高的吞吐率和效率B.流水线的效率和吞吐率恶化C.出现瓶颈D.可靠性提高二、填空题11、输入输出设备的异步性、实时性、与________三个特点是现代计算机系统必须具备的共同特性。
12、计算任何一个程序的执行时间的公式可表示为P=I•CPI•T，其中I是________ CPU是________T是一个周期的时间长度。
408 数据结构应用题汇总
以下是一些常见的数据结构应用题目汇总：
1. 矩阵旋转：给定一个二维矩阵，将其顺时针旋转90度。
2. 字符串反转：给定一个字符串，将其反转。
3. 队列实现栈：使用队列数据结构实现栈的功能。
4. 平衡括号：给定一个包含括号的字符串，判断括号是否平衡。
5. LRU缓存：实现一个LRU（Least Recently Used）缓存，删
除最久未使用的元素。
6. 二叉树遍历：实现二叉树的前序、中序和后序遍历。
7. 最小堆：实现一个最小堆数据结构。
8. 拓扑排序：给定一个有向图，对其进行拓扑排序。
9. 二叉查找树：实现一个二叉查找树数据结构。
10. 图的最短路径：给定一个有向加权图和两个节点，计算它
们之间的最短路径。
11. 栈实现队列：使用栈数据结构实现队列的功能。
12. 二叉树的最大深度：计算给定二叉树的最大深度。
13. 跳表：实现一个跳表数据结构。
14. 二叉查找：给定一个有序数组，查找一个元素是否存在。
15. 图的遍历：实现图的深度优先搜索和广度优先搜索。
这些题目涵盖了常见的数据结构应用场景，可以帮助提升对数据结构的理解和应用能力。
在解答这些题目时，可以考虑选择合适的数据结构，并且理解各种操作的时间复杂度和空间复杂度，以找到高效的解决方案。
数据结构与算法题库（含参考答案）一、单选题（共100题，每题1分，共100分）1、在一次校园活动中拍摄了很多数码照片，现需将这些照片整理到一个PowerPoint 演示文稿中，快速制作的最优操作方法是：A、创建一个 PowerPoint 相册文件。
B、创建一个 PowerPoint 演示文稿，然后批量插入图片。
C、创建一个 PowerPoint 演示文稿，然后在每页幻灯片中插入图片。
D、在文件夹中选中所有照片，然后单击鼠标右键直接发送到PowerPoint 演示文稿中。
正确答案：A2、下面对“对象”概念描述错误的是A、对象不具有封装性B、对象是属性和方法的封装体C、对象间的通信是靠消息传递D、一个对象是其对应类的实例正确答案：A3、设栈与队列初始状态为空。
首先A,B,C,D,E依次入栈，再F,G,H,I,J 依次入队；然后依次出队至队空，再依次出栈至栈空。
则输出序列为A、F,G,H,I,J,E,D,C,B,AB、E,D,C,B,A,J,I,H,G,FC、F,G,H,I,J,A,B,C,D,E,D、E,D,C,B,A,F,G,H,I,J正确答案：A4、设表的长度为 20。
则在最坏情况下，冒泡排序的比较次数为A、20B、19C、90D、190正确答案：D5、设二叉树的前序序列为 ABDEGHCFIJ，中序序列为 DBGEHACIFJ。
则后序序列为A、DGHEBIJFCAB、JIHGFEDCBAC、GHIJDEFBCAD、ABCDEFGHIJ正确答案：A6、Excel工作表B列保存了11位手机号码信息，为了保护个人隐私，需将手机号码的后 4 位均用“*”表示，以 B2 单元格为例，最优的操作方法是：A、=REPLACE(B2,7,4,"****")B、=REPLACE(B2,8,4,"****")C、=MID(B2,7,4,"****")D、=MID(B2,8,4,"****")第 10 组正确答案：B7、小金从网站上查到了最近一次全国人口普查的数据表格，他准备将这份表格中的数据引用到 Excel 中以便进一步分析，最优的操作方法是：A、通过 Excel 中的“自网站获取外部数据”功能，直接将网页上的表格导入到 Excel 工作表中。
2022年湖南科技大学潇湘学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（）排序法。
A.插入B.选择C.希尔D.二路归并2、下述文件中适合于磁带存储的是（）。
A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、下列关于AOE网的叙述中，不正确的是（）。
A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。
A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改6、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。
A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、设X是树T中的一个非根结点，B是T所对应的二叉树。
在B中，X是其双亲的右孩子，下列结论正确的是（）。
1．简述栈的基本操作2．给定权值组W={1，3，78，14，20，28}，建立哈夫曼树。
3．试求下面的网络的最小生成树4.对一组关键字49，7，50，5，94，16，90，29，71，使用希尔排序，写出对31=d 时的一趟排序的结果。
1-4题答案：1、栈的基本操作有：栈的建立，判栈满，判栈空，压栈，退栈和取栈顶元素等。
2、3、 4、5．写出队列的基本操作。
6．对下面的二叉树（１） 其中序遍历序列为（２）其后序遍历序列为7．给定一组关键字序列12，7，51，32，23，试构造一棵查找树。
8．对一组关键字49，7，50，5，94，16，90，29，71，使用快速排序，试给出第一次划分过程。
5-8题答案：5．队列的基本操作有：6B →D →A →E →C →15610569138101 a b d h c 5 eg 1447866283820141841313245656986495750941690297157164929509094716．（１）中序遍历序列：d g b a e c h f（２）后序遍历序列：g d b e h f c a7．12７5132238．49 7 50 5 94 16 90 29 71 ↑head ↑tail49 7 50 5 94 16 90 29 71↑head ↑tail29 7 50 5 94 16 90 49 71↑head ↑tail29 7 49 5 94 16 90 50 71↑head ↑tail29 7 16 5 94 49 90 50 71↑head ↑tail29 7 16 5 49 94 90 50 71head↑↑tail9．// 设元素的类型为T， aList是存储顺序表的数组， maxSize是其最大长度；// p为新元素value的插入位置，插入成功则返回true，否则返回falsetemplate <class T> bool arrList<T> :: insert (const int p, const T value) { int i;if (curLen >= maxSize) { // 检查顺序表是否溢出cout << "The list is overflow"<<endl; return false;}if (p < 0 || p > curLen) { // 检查插入位置是否合法cout << "Insertion point is illegal"<<endl; return false;}for (i = curLen; i > p; i--)aList[i] = aList[i-1]; // 从表尾curLen -1起往右移动直到p aList[p] = value; // 位置p处插入新元素curLen++; // 表的实际长度增1return true;}10．图如下，请画出11．一份电文中共使用的字符有A ，B ，C ，D ，E ，它们出现的频率依次为4，7，5，2，9。
试画出其对应的Huffman 树12．用拉链法建立Hash 表，Hash 函数为H(key)=key mod 11,Hash 表长度为10，现有一组关键字（61，18，30，72，13，24，12，11），请画出相应的Hash 表。
139-13题答案：10、11、12、61 mod 11=6 18 mod 11=7 30 mod 11=7 72 mod 11=6 13 mod 11=2 24 mod 11=1 12 mod 11=1 11 mod 11=013、树转化为二叉树的方法如下：①将树中的各兄弟之间加一条连线。
14、画出具有三个结点的二叉树的所有形态。
15、图如右，请画出prim 算法构造最小生成树的过程。
16、对于如下无向图，请画出其深度优先搜索和广度优先搜索生成的树（画出一棵即可）。
17、用线性探测法建立Hash 表，Hash 函数为H(key)=key mod 11,Hash 表长度为10，现有一组关键字（61，18，30，72，13，24），请画出相应的Hash 表。
18、// 设元素的类型为T ；aList 是存储顺序表的数组； p 为即将删除元素的位置 // 删除成功则返回true ，否则返回falsetemplate <class T> // 顺序表的元素类型为T bool arrList<T> :: delete(const int p) { int i; if (curLen <= 0 ) { // 检查顺序表是否为空 3 6 4 1 2 5 3 6 4 125if (p < 0 || p > curLen-1) { // 检查删除位置是否合法cout << "deletion is illegal\n"<<endl;return false ;}for (i = p; i < curLen-1; i++)aList[i] = aList[i+1]; // 从位置p开始每个元素左移直到curLen curLen--; // 表的实际长度减1return true;}14-18题答案：14、15、16设从结点1出发开始深度优先搜索，得到如下一棵深度优先生成树：设从结点1出发开始广度优先搜索，得到如下一棵广度优先生成树：17、18 mod 11=7 30 mod 11=872 mod 11=6→7→8→9 13 mod 11=2 24 mod 11=2→319．设一棵二叉树的先序遍历序列为： A B D F C E G H中序遍历序列为： B F D A G E H C （1）画出这棵二叉树。
（5分）（2）画出这棵二叉树的后序线索树。
（5分）（3）画出由这棵二叉树转换成的树（或森林）。
（5分）20．设有正文AADBAACACCDACACAAD,字符集为A,B,C,D,设计一套二进制编码，使得上述正文的编码最短。
（要求画出Huffman 树并写出编码）（15分）21．已知一个无向图如下图所示，用Kruskal 算法生成最小树（假设以①为起点，要求画出构造过程）。
（10分）22．对于以下的图，写出它的四个不同的拓扑有序序列。
（10分）23．采用哈希函数H（k）=3*k mod 13并用线性探测开放地址法处理冲突，在数列地址空间［0..12］中对关键字序列22,41,53,46,30,13,1,67,51。
（1）构造哈希表（画示意图）；（5分）（2）求装填因子；（1分）（3）等概率下成功的和不成功的平均查找长度。
（4分）24．数据结构与数据类型有什么区别？24.“数据结构”这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。
作为科学概念，目前尚无公认定义，一般认为，讨论数据结构要包括三个方面，一是数据的逻辑结构，二是数据的存储结构，三是对数据进行的操作（运算）。
而数据类型是值的集合和操作的集合，可以看作是已实现了的数据结构，后者是前者的一种简化情况。
25．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。
25.该算术表达式转化的二叉树如右图所示。
26．将下列由三棵树组成的森林转换为二叉树。
（只要求给出转换结果）HGDACJIBFEKO27. 设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。
（2）画出这棵二叉树的后序线索树。
（3）将这棵二叉树转换成对应的树（或森林）。
27.28. 已知下列字符A 、B 、C 、D 、E 、F 、G 的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT 的存储结构的初态和终态。
29. 对有五个结点{ A,B, C, D, E}的图的邻接矩阵，⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞∞∞∞∞∞∞∞05001020060010301000 （1）．画出逻辑图 ； （2）．画出图的十字链表存储； （3）．基于邻接矩阵写出图的深度、广度优先遍历序列；. 30.一带权无向图的邻接矩阵如下图 ，试画出它的一棵最小生成树。
A BM F D (3) CEM HG设顶点集合为{1，2，3，4，5，6}， 由右边的逻辑图可以看出，在{1，2，3}和{4，5，6}回路中， 各任选两条边，加上（2，4），则可构成9棵不同的最小生成树。
31. 试写出用克鲁斯卡尔（Kruskal ）算法构造下图的一棵最小支撑（或生成）树的过程。
V （G ）={1，2，3，4，5，6，7}E （G ）={（1，6，4），（1，7，6），（2，3，5），（2，4，8），（2，5，12），（1，2，18）}32. 设哈希(Hash)表的地址范围为0～17，哈希函数为：H (K)=K MOD 16, K 为关键字，用线性探测再散列法处理冲突，输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49)造出哈希表，试回答下列问题： (1) 画出哈希表示意图； (2) 若查找关键字63，需要依次与哪些关键字比较?(3) 若查找关键字60，需要依次与哪些关键字比较?(4) 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。
（1（2（3）查找关键字60，H （k ）=60 MOD 16=12，散列地址12内为空，查找失败。
（4）ASL succ =23/11ASL succ =15/1034. 设散列函数H(k)=K mod 7,散列表的地址空间为0-6，对关键字序列{32,13,49,18,22,38,21}按链地址法处理冲突的办法构造哈希表，并指出查找各关键字要进行几次比较。
查找时，对关键字49,22,38,32,13各比较一次，对21,18各比较两次35. 设有5个互不相同的元素a、b、c、d、e，能否通过7次比较就将其排好序？如果能，请列出其比较过程；如果不能，则说明原因。
可以做到。
取a与b进行比较，c与d进行比较。
设a>b,c>d(a<b和c<d情况类似)，此时需2次比较，取b和d 比较，若b>d，则有序a>b>d；若b<d时则有序c>d>b，此时已进行了3次比较。
再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。
36. 请阅读下列算法，回答问题PROCEDURE sort（r，n）BEGINFOR i:=2 TO n DOBEGINx:=r(i)；r(O):=x；j:=i-1；WHILE x.key<r(j).key DOBEGINr(j+1):=r(j); j:=j-1END;r(j+1):=xENDEND;问题一：这是什么类型的排序算法，该排序算法稳定吗？问题二：设置r(O)的作用是什么？若将WHILE—DO 语句中判断条件改为x.key<=r(j).KEY,该算法将会有什么变化，是否还能正确工作？(1)此为直接插入排序算法，该算法稳定。
