单项选择题分题一共这里不按原题顺序写想起来一个初试.pdfVIP

一、单项选择题：（2分/题，一共80分。这里不是按原题顺序写的，起来一个写一个

的）

1.栈的操作模拟，连续push3个元素后，pop一个，再getTop，问最后得到的这个是哪个

元素。

2.设有一个n*n的对称矩阵A，将其下三角部分按行在一维数组B中，A[0][0]存在B[0]

中，那么第i行的对角元素A[i][i]存放于B中（）处。

A.(i+3)i/2B.(2n-i+1)i/2C.XXXD.xxx记不清了。

3.稀疏矩阵的常用方式有哪两个？（数组、十字链表、还有个啥我忘了）。

4.给一堆字符串，应该都是姓氏的汉语（什么fang、bai、an、tang之类的），然后问

你按升序一趟二路归并排序的序列是啥。

5.串的最常用的两种方式是？（数组、链表、堆）。

6.下列序列，用快排按升序排列，哪个的元素移动次数最多？

A.{10,30,50,70,90}BCD都是这五个数换换顺序，具体是啥记不清了。

7.一个无向图，给出几个结点，和它们之间有哪些边。让你选出哪个是正确的先深遍历序列。

8.下列有关机群的说法正确的是（）

A.机群比多处理器具有更好的扩展性；

B.机群各个节点都有独立的主存；

C.一个进程的多个线程可以同时在集群的各个节点上运行；

D.忘了

9.两个补码表示的负数，相加，让你结果是哪个。

10.流控滑动窗口协议中，可以直接发送而不必确认的数据是（）

A.滑动窗口左边的数据B.滑动窗口右边的数据C.滑动窗口内的数据D.滑动窗口

收缩的数据

11.TCP连接中，用wireshark捕获了一个数据包，内容是seq：0，ack：1，ACKset1，SYN

set1。问正常情况下，下一个数据包是（）

A.seq：1，ack：1B.seq：1，ack：2C.seq:2,ack:1D.seq:0,ack:1

12.OSI参考模型中，负责端到端可靠传输的是哪层？

13.下列不属于文件系统的是（）

A.超级块B.空闲块表C.D.分区表

14.服务器发送数据给客户端，数据封装形式依次是（）

A.{数据，数据段，数据包，数据帧，比特}BCD都是这几个东西换换顺序

二、大题（70分）

41.（10分）

起来了）。其中借书和还书记录都需要包括：书名、书号、借出时间、归还时间。

（1）设计一种合理的结构来存上述信息，并画出图示；

（2）设计一种高效算法来完成借书（当前在借书数大于等于n时不允许再借书）和还书过

程，给出算法思想并用C/C++/java描述；

（3）上述算法的时间、空间复杂度。

42.（10分）

设计算法，对于链表的二叉树，给出其中两个结点x和y后，输出其全部公共祖先。

给出算法思想、C/C++/java描述。

43.（7分）

设计算法，使用单链表实现FIFO的队列的入队和出队操作，要求使用mutex来互斥这俩操

作。给出C/C++/java描述。

44.（8分好像是）

（1）从操作系统的角度，简单描述：运行在用户态的进程，从一个打开的文件中读出一个

字节的全部过程；

（2）上述过程中，数据最多发生几次拷贝？

45.（8分，每问2分）

给了个指令结构示意图（4位OP，2位寻址方式，1位间址标志，1位变址标志，8位地址

A），说该机器的器容量为64K*16位，按字节寻址。采用16位定长指令结构。

跳转指令中地址用补码表示