# 前 75 题 ## 题目 1 下列数据结构不是多型数据类型的是（） * 堆 * 栈 * 字符串 * 有向图 ### 正确答案 答案：C 多型就是数据元素的类型不确定，字符串的每个元素始终都是字符(char)，而不会是别的类型 ## 题目 2 稀疏矩阵压缩存储后,必会失去随机存取功能() ### 正确答案及解析 答案：对的 稀疏矩阵在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。 ## 题目 3 某二叉树的前序遍历序列为`-+a*b-cd/ef`，后序遍历序列为`abcd-*+ef/-`，问其中序遍历序列是()。 ### 正确答案及解析 答案：`a+b*c-d-e/f` 可以根据后缀表达式求出中缀表达式，中缀表达式是直观的表达式。 这里要注意理解，不能理解为树只给前序遍历和后序遍历就无法确定树的结构。 ## 题目 4 一棵3阶B-树中含有2047个关键字,包含叶结点层,该树的最大深度为() ### 正确答案及解析 答案：12 M阶B-树中含有N个关键字，最大深度为 ![最大深度公式](http://uploadfiles.nowcoder.com/images/20150805/851149_1438779900299_FR2RB72F3D3O8X7.png) ## 题目 5 设某种二叉树有如下特点：每个结点要么是叶子结点，要么有2棵子树。假如一棵这样的二叉树中有m（m>0）个叶子结点，那么该二叉树上的结点总数为（ ）。 * 2m+1 * 2m-1 * 2(m-1) * 2m ### 正确答案及解析 答案：B 出度为0的结点为m 出度为2的结点 = 出度为0的结点 - 1 = m - 1 题目中说：每个结点要么是叶子结点，要么有2棵子树 所以没有出度为1的结点 总结点数为：2m - 1 ## 题目 6 若用数组S\[0. .n-1]做为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（ ）。 * S1的栈底位置为0，S2的栈底位置为n-1 * S1的栈底位置为0，S2的栈底位置为n/2 * S1的栈底位置为1，S2的栈底位置为n/2 ### 正确答案及解析 答案：A ## 题目 7 下面关于二分查找的叙述中正确的是： * 表必须有序,表可以顺序方式存储,也可以链表方式存储 * 表必须有序且表中数据必须是整型,实型或字符型 * 表必须有序,而且只能从小到大排列 * 表必须有序,且表只能以顺序方式存储 ### 正确答案及解析 答案：D 折半查找方法适用于不经常变动而查找频繁的有序列表。 它的算法要求是必须是顺序存储结构，必须有序排列 ## 题目 8 假设某段通信电文仅由 6 个字母 ABCDEF 组成，字母在电文中出现的频率分别为2，3，7，15，4，6。根据这些频率作为权值构造哈夫曼编码，最终构造出的哈夫曼树带权路径长度与字母 B 的哈夫曼编码分别为`______`。(这里假定左节点的值小于右节点的值) ### 正确答案及解析 答案：86、1011 长度计算为 `（2+3）*4+（4+6+7）*3+15*1=86` ![哈夫曼树](http://uploadfiles.nowcoder.com/images/20150309/408620_1425895148659_1.jpg) ## 题目 9 一个长度为99的循环链表，指针A和指针B都指向了链表中的同一个节点，A以步长为1向前移动，B以步长为3向前移动，一共需要同时移动多少步A和B才能再次指向同一个节点`____`。 ### 正确答案及解析 答案：99 设需要走x步A、B才能重新相遇，那么`x%99 = (3x)%99`; 令`x%99 = r`,则可得`x = 99k1 + r`, `3x = 99k2 + r`，整理两个式子可得 `x = 99 * (k2 - k1)/2`，因为均为正整数，所以x最小为99 ## 题目 10 有一个数组（53,83,18,59,38,35），依次将其存储在hash表中，其中哈希函数为`h(k)=k%7`,如采用线性探测（每次向后查找1位）的方式解决冲突，则该hash表上查找38,35,53访问hash表的表项次数分别为 ?, ?, ?。 ### 正确答案及解析 5, 2, 1 表的顺序: | 索引值 | 表项 | | --- | -- | | 0 | 38 | | 1 | 35 | | 2 | | | 3 | 59 | | 4 | 53 | | 5 | 18 | | 6 | 83 | 附带求模结果： `53 % 7 = 4, 83 % 7 = 6, 18 % 7 = 4` `59 % 7 = 3, 38 % 7 = 3, 35 % 7 = 0` ## 题目 11 对于某个函数调用，可以不给出被调用函数的原形的情况是（）。 * 被调用函数式无参函数 * 被调用函数式无返回值的函数 * 函数的定义在调用处之前 * 函数的定义在别的程序文件中 ### 正确答案及解析 如果被调用函数的定义出现在主调函数之前，可以不必加以声明。因为编译系统已经事先知道了已定义的函数类型，会根据函数首部提供的信息对函数的调用作正确性检查。 ## 题目 12 To speed up data access , we build cache system. In one system , The L1 cache access time is 5 ns , the L2 cache access time is 50 ns and the memory access time is 400 ns. The L1 cache miss rate is 50% , the L2 cache miss rate is 10%. The average data access time of this system is: ### 正确答案及解析 `0.5*5+0.5*0.9*（50+5）+0.5*0.1*（400+50+5）=50` ## 题目 13 某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括()棵树 ### 正确答案及解析 答案：3 ![二叉树](http://uploadfiles.nowcoder.com/images/20150107/909995_1420569532126_2.png) 构建后的二叉树的右下节点都是由对应的森林里不同的树相连而成的，可以想象二叉往树右侧的先序遍历依次经过A-C-F到达树的底端，这三个结点在对应的森林中都必定分属不同的树。所以一共有三棵树。 ## 题目 14 某表达式的前缀形式为`"+-*^ABCD/E/F+GH"`,它的中缀形式为() * A^B\*C-D+E/F/G+H * A^B\*(C-D)+(E/F)/G+H * A^B\*C-D+E/(F/(G+H)) * A^B\*(C-D)+E/(F/(G+H)) ### 正确答案及解析 答案：C 前缀表达式的计算机求值特点： 从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 op 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果。 ``` 根据从右至左扫描计算过程如下: 题目中的前缀形式为：+-*^ABCD/E/F+GH 1) 首先扫描 H,是数字 入栈 ，栈中为: H 2) 扫描 G 为数字 入栈 ,栈中为:G,H 3)扫描+ 为运算符 ,依次弹出G ,H ,得到 G+H 的结果 入栈，栈中为： G+H(在这里方便讲解 标记为 G+H) 4)扫描 F 为数字 ,入栈 ，栈中为 F, G+H 5)扫描 / 为运算符, 依次弹出 F,G+H ，计算F/(G+H) 的结果入栈 ，栈中为 F/(G+H) 6)扫描 E 为数字,入栈，栈中为 E, F/(G+H) 7) 扫描 / 为运算符, 依次弹出E, F/(G+H) ，计算 E/(F/(G+H)) 8)扫描 D 为数字,入栈 栈中为:D, E/(F/(G+H)) 9) 扫描 C 为数字,入栈 栈中为:C,D, E/(F/(G+H)) 10) 扫描 B 为数字,入栈 栈中为:B,C,D, E/(F/(G+H)) 11) 扫描 A 为数字,入栈 栈中为:A,B,C,D, E/(F/(G+H)) 12) 扫描^ 为数字,依次弹出 A,B 计算 A^B的结果入栈, 栈中为：A^B ,C,D, E/(F/(G+H)) 13) 扫描*为数字,依次弹出 A^B,C 计算 A^B*C的结果入栈, 栈中为：A^B* C,D, E/(F/(G+H)) 14) 扫描-为数字,依次弹出 A^B*C,D 计算 A^B*C-D的结果入栈, 栈中为：A^B* C-D, E/(F/(G+H)) 15) 扫描+为数字,依次弹出 A^B*C-D, E/(F/(G+H)) 计算 A^B*C-D+ E/(F/(G+H)) 的到结果 最后得到的表达式为： A^B* C-D+ E/(F/(G+H)) ``` ## 题目 15 下面有关 ibatis 中的#与$的区别，描述错误的是？ * `#`将传入的数据都当成一个字符串，会对自动传入的数据加一个双引号 * $ 方式能够很大程度防止 sql 注入。 * $ 方式一般用于传入数据库对象，例如传入表名 * $ 将传入的数据直接显示生成在 sql 中 ### 正确答案及解析 答案：B ``` 1. # 是把传入的数据当作字符串，如#user_id_list#传入的是1,2,则sql语句生成是这样，in ('1,2') , 2. $ 传入的数据直接生成在sql里，如$user_id_list$传入的是1,2,则sql语句生成是这样，in(1,2)． 3. # 方式能够很大程度防止sql注入． 4. $ 方式无法方式sql注入． 5. $ 方式一般用于传入数据库对象．例如传入表名. 6. 一般能用#的就别用$. 举例： #str# 出来的效果是 'str' $str$ 出来的效果是 str ``` ## 题目 16 下面关于B和B+树的描述中，不正确的是() * B树和B+树都是平衡的多叉树 * B树和B+树都可用于文件的索引结构 * B树和B+树都能有效的支持顺序检索 * B树和B+树都能有效的支持随机检索 ### 正确答案及解析 答案：C B树只适用于随机检索，不适用于顺序检索；而B+树把所有关键码都存在叶结点上，这就为顺序检索也提供了方便。 * B 树和 B+ 树用于组织文件的动态索引结构。 * B 树和 B+ 树都是平衡的多分支树。 * B 树只适用于随机检索, 不适用于顺序检索, 而 B+ 树适用于顺序检索和随机检索 ## 题目 17 求解最短路径的Floyd算法的时间复杂度为() * `O(n)` * `O(n+c)` * `O(n*n)` * `O(n*n*n)` ### 正确答案及解析 答案：D ```cpp int n;//n为节点个数 for(int i=0; i 右, 即 a3 对应的是 ``, `B -> D` 这个方向 * 该 AOE 网络的源点为 A, 汇点为 F * 事件 D 的最早发生时间：从源点 A 开始到达 D 的所有路径加和的最大值 `max{,} = 6` * 事件 D 的最迟发生时间 ： ``` 首先求出汇点 F 的最早发生时间: max{,,,} = 8 汇点 F 的最早发生时间 - max{汇点逆向到事件 D 的路径累加之和} = 8 - max{} = 5 ``` * 活动 `a3 ` * 最早发生时间: 以 a3 该活动为出发点的事件 `B ---a3---> D`, 即 B 事件的最早发生时间； * 最迟发生时间： 以 a3 该活动对应的箭头所指向的事件的最迟发生时间 - a3 活动持续时间 `B---a3--->D`, 即, D 事件的最迟发生时间 - a3 活动的持续时间 \= 5 - 2 = 3 ``` 综上所述， 最早发生时间，事件=活动，是从前往后计算 最迟发生时间，都是从后往前计算， 事件最迟发生时间与汇点和路径累加有关， 事件的时间计算要先于活动的时间计算 活动最迟发生时间与活动持续时间有关 ``` ## 题目 32 若某线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？ * 顺序表 * 双链表 * 带头结点的双循环链表 * 单循环链表 ### 正确答案及解析 答案：A 线性表最常用得操作是存取任一指定序号的元素和在最后进行插入和删除运算； 进行任意位置存取，这个最省时省力的就是数组了，也就是顺序表。 而且元素是在最后的位置进行插入和删除运算，也就不涉及其他元素进行位移的额外操作，最多涉及的就是去扩展空间了。 所以答案选择 A 顺序表 ## 题目 33 已知一棵二叉树，如果先序遍历的节点顺序是：ADCEFGHB，中序遍历是：CDFEGHAB，则后序遍历结果为：（） ### 正确答案及解析 CFHGEDBA ## 题目 34 设有数组A\[i,j],数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A\[5,8]的存储首地址为()。 ### 正确答案及解析 答案：`BA + 180` 注意是列为主, `((7 * 8 + 5) - 1) * 3 = 180` ## 题目 35 对进程和线程的描述，一下哪个是正确的？ * 父进程的所有线程共享相同的地址空间，父进程的所有子进程共享相同的地址空间 * 改变进程里面主线程的状态会影响其他线程的行为，改变父进程的状态不会影响其他子进程 * 多线程会引发死锁，而多进程不会 * 以上都不对 ### 正确答案及解析 答案：D * A 错, 进程拥有独立的地址空间 * B 错, 主线程和子线程是并行关系的时候, 并没有依赖关系. 父进程和子进程中, 子进程是父进程的一个副本, 创建子进程后, 子进程会有自己的空间, 然后把父进程的数据拷贝到子进程的空间里. 运行时, 谁先运行是不确定的, 这由系统决定 * C 错, 多线程和多进程都会引起死锁, 一般说的死锁指的是进程间的死锁 进程和线程的主要差别在于它们是不同的操作系统资源管理方式。进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。 ## 题目 36 下述有关hash冲突时候的解决方法的说法，错误的有？ * 通常有两类方法处理冲突：开放定址(Open Addressing)法和拉链(Chaining)法。 * 开放定址更适合于造表前无法确定表长的情况 * 在用拉链法构造的散列表中，删除结点的操作易于实现 * 拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间 ### 正确答案及解析 答案：B 由于拉链法中各链表上的结点空间是动态申请的,故它更适合于造表前无法确定表长的情况 ## 题目 37 如果关系模式R=(A,B,C,D,E)中的函数依赖集F={A→B,B→C,CE→D},这是第几范式？ ### 正确答案及解析 答案：第一范式 F={A→B,B→C,CE→D}，主键为(A,E)，非主属性B,C却并不是完全依赖于码(A,E)，只依赖于主键的部分属性 A，因此不符合2NF, 只1NF。 ``` * 第一范式（ 1NF ）：属性不可分； * 第二范式（2NF）：符合 1NF，并且，非主属性完全依赖于主键，而不是依赖于部分主键属性； * 第三范式（3NF）：符合 2NF，并且，消除传递依赖； * BC 范式（BCNF）：符合 3NF，并且，主属性不依赖于主属性（若一个关系达到了第三范式，并且它只有一个候选码，或者它的每个候选码都是单属性，则该关系自然达到 BC 范式）； * 第四范式：要求把同一表内的多对多关系删除； * 第五范式：从最终结构重新建立原始结构。 ``` ## 题目 38 完全二叉树共有700结点，该二叉树有多少个叶子结点？ ### 正确答案及解析 答案：350 因为 12/2 等于 6, 等于父节点值, 所以是最后一个带子节点的, 拿总数减去 6, 即为叶子节点数, 同理, 所以 700 作为最后一个节点, 他的父节点是 350, 所以序号 350 是最后一个非叶子节点, 以下的都没有子节点, `700 -350 = 350` 所以答案选 B ## 题目 39 下面 Transact-SQL 语句中可以用于创建主键的是（） * alter table table1 with notcheck add constraint \[PK\_table1] primary key nonclustered (column1) on primary; * alter table table1 column1 primary key; * alter table table1 column1; * create table table1 (column1 char(13) not null primary,column2 int not) on primary; ### 正确答案及解析 答案：A ``` 表中删除主键为： alter table table_test drop primary key; 表中增加主键为： alter table table_test add primary key(id); ``` ## 题目 40 字符串 `www.qq.com` 所有非空子串（两个子串如果内容相同则只算一个）个数是（） ### 正确答案及解析 答案：50 要求的是子串, 从左到右一次截取, 10 个字符的子串, 1 个; 9 个字符的子串, 2个; 8, 3个; 7, 4 个; ......... 1, 10 个 共有: `1 + 2 + 3 + ... + 10 = 10 * (10 + 1) / 2 = 55` 减去重复的: 1 个字符时有 3 个 w, 2 个 q, 2 个 ., 2 个字符时有 2 个 ww, 故应减去:`(2+1+1+1)=5` 答案: `55-5=50` ## 题目 41 从浏览器打开 `http://www.nowcoder.com`, `TCP/IP` 协议族中不会被使用到的协议是() * SMTP * HTTP * TCP * IP ### 正确答案及解析 答案：A ## 题目 42 一进程刚获得3个主存块的使用权，若该进程访问页面的次序是{1,2,3,4,1,2,5,1,2,3,4,5}。当采用先进先出调度算法时，发生缺页次数是()次 ### 正确答案及解析 答案：9 ``` 1被访问，第1次缺页，队列为1 2被访问，第2次缺页，队列为1,2 3被访问，第3次缺页，队列为1,2,3 4被访问，第4次缺页，队列为2,3,4。1出队列，4入队列。 1被访问，第5次缺页，队列为3,4,1。2出队列，1入队列。 2被访问，第6次缺页，队列为4,1,2。3出队列，2入队列。 5被访问，第7次缺页，队列为1,2,5。4出队列，5入队列。 1被访问，此时不缺页，队列不变，即队列为1,2,5。 2被访问，此时不缺页，队列不变，即队列为1,2,5。 3 被访问，第8次缺页，队列为 2,5,3。1出队列，3入队列。 4 被访问，第9次缺页，队列为 5,3,4。2出队列，4入队列。 5被访问，此时不缺页，队列不变，即队列为5,3,4。 所以共9次缺页。 ``` ## 题目 42 以下对 CSMA/CD 描述正确的是？ * 在数据发送前对网络是否空闲进行检测 * 在数据发送时对网络是否空闲进行检测 * 在数据发送时对发送数据进行冲突检测 * 发生碰撞后 MAC 地址小的主机拥有发送优先权 ### 正确答案及解析 答案：AC CSMA/CD 协议即带冲突检测的载波监听多路访问协议。 ``` A，发送前空闲检测，只有信道空闲才发送数据 B，发送时当前信号占据信道，信道必定不为空闲，检测空闲没意义 C，发送过程中冲突检测，如果发生冲突，立即停止发送，随机避让。 D，冲突发送后，两个发送端都随机避让一段时间，避让的时间是随机的，优先级相等，没有哪个优先权高的说法。 ``` ## 题目 43 内存管理中的 LRU 方法是用来管理什么的？ * 虚拟内存的分配 * 虚拟内存的释放 * 物理内存的分配 * 物理内存的释放 ### 正确答案及解析 答案：AD 1. 页面调入：是给页面调入内存中，给它分配物理内存。 2. 页面置换，就是将内存中的页面置换出来，放到虚拟内存中，让物理内存空闲出来，让给需要使用的页面。 3. LRU：全称是：Least Recently Used（最近最久未使用）置换算法，所以这个算法涉及到了虚拟内存的分配和物理内存的释放。所以答案是 AD。 ## 题目 44 http, telnet, ftp的端口是 ?, ?, ?(FTP写最常用的那一个端口就好) ### 正确答案及解析 80, 23, 21 FTP 端口号有两个 20 和 21, 一个为控制端口, 一个为数据端口 ## 题目 45 VLAN的主要作用有？ * 保证网络安全 * 抑制广播风暴 * 简化网络管理 * 提高网络设计灵活性 ### 正确答案及解析 答案：B VLAN（virtual local area network）虚拟局域网，把大的局域网划分为几个单独的互不相通的虚拟局域网，隔离广播风暴。 ## 题目 46 在公有派生情况下，有关派生类对象和基类对象的关系，下列叙述不正确的是( ) * 派生类的对象可以赋给基类的对象 * 派生类的对象可以初始化基类的引用 * 派生类的对象可以直接访问基类中的成员 * 派生类的对象的地址可以赋给指向基类的指针 ### 正确答案及解析 答案：C A，B 和 D 说法是相同的，都是说可以用派生类对象初试化基类对象或者指针，是正确的 C，派生类对象只有在基类成员未被派生类覆盖的情况下才能访问基类中的成员 ## 题目 47 国标规定交换机中具备CID功能的用户电路的配置比例暂定为 * 5％～10％ * 10％～20％ * 10％～30％ * 10％～40％ ### 正确答案及解析 答案：C ## 题目 48 一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足() * 其中任意一个结点均无左孩子 * 其中任意一个结点均无右孩子 * 其中只有一个叶结点 * 其中度为2的结点最多为一个 ### 正确答案及解析 答案：C 一棵非空的二叉树的前序序列和后序序列正好相反,则该二叉树一定满足只有左子树或只有右子树。 A,B 明显不对，举最简单的例子，1为根节点，2分别为1的左右孩子，都满足前序序列和后序序列正好相反。 D 不可能出现一个度为2的节点。 ## 题目 49 判断一个单向链表中是否存在环的最佳方法是（） * 两重遍历 * 快慢指针 * 路径记录 * 哈希表辅助 ### 正确答案及解析 答案：B 让快慢指针都从链表表头开始，快指针一次向前移动连个位置，慢指针每次向前移动一个位置。如果快指针到达了NULL，说明不存在环，但如果快指针追上了慢指针，说明存在环。 ## 题目 50 把逻辑地址转变为内存的物理地址的过程称作（）。 * 编译 * 连接 * 运行 * 重定位或地址映射 ### 正确答案及解析 答案：D 重定位对应的也是虚拟内存的地址，不是真正的物理地址 ## 题目 51 对于IP地址130.63.160.2，MASK为255.255.255.0，子网号为（） * 160.2 * 160 * 63.160 * 130.63.160 ### 正确答案及解析 答案：B 130.63.160.2是B类IP地址 B类IP地址前16位（两个字节）为网络号，后16位是主机号 划分子网就是将主机号中的一部分拿出来当做子网号 这里子网掩码为255.255.255.0也就是把前三个字节当成了网络号 与B类IP默认的前两个字节作为网络号相比，第三个字节就是子网号，就是160 所以这个ip的网络号是130.63 子网号是 160 主机号是2 ## 题目 52 关于进程的正确说法是()。 * 进程就是程序，或者说进程是程序的另一叫法 * 一个被创建了的进程，在它被消灭之前，处于进程的三种基本状态之一 * 多个不同的进程不可以包含相同的程序 * 一个处于等待队列中的进程，即使进入其他状态，仍然放在等待队列中 ### 正确答案及解析 答案：B 进程的三种基本状态包括有就绪状态，执行状态，阻塞状态。 多个不同的进程可以包含相同的程序段， ## 题目 53 下列关于网络编程错误的是`______`。 * UDP 是不可靠服务 * 主动关闭的一端会出现 TIME\_WAIT 状态 * 服务端编程会调用 listen(),客户端也可以调用 bind() * TCP 建立和关闭连接都只需要三次握手 * Linux 通过提供提供 socket 接口来进行网络编程 * 长连接相对短连接可以节省建立连接的时间 ### 正确答案及解析 答案：D TCP建立连接3次握手,断开链接需要4次 ![TCP 断开连接](http://uploadfiles.nowcoder.com/images/20150329/623288_1427558474242_11.png) ## 题目 54 单链表的每个结点中包括一个指针link，它指向该结点的后继结点。现要将指针q指向的新结点插入到指针p指向的单链表结点之后，下面的操作系列中哪一个是正确的？ * q=p->link;p->link=q->link * p=p->link=q->link;p->link * q->link=p->link;p->link=q; * p->link=1;q->link=p->link ### 正确答案及解析 答案：C 首先应该让新结点q的link指向p的link也就是q->link = p->link; 然后再让p的link指向q即可.也就是p->link = p; ## 题目 55 有n(n>0)个分支结点的满二叉树的深度是() ### 正确答案及解析 答案：`log2(n+1)+1` 假设树有K层，所有的分枝节点都在 `1 - (k - 1)` 层，每层都是满的，对有 `1 - (k - 1)` 层，有 `2^(k-1)-1=n` 变形后得：`k=log(n+1)+1`。 ## 题目 56 有订单表orders，包含字段用户信息userid，字段产品信息productid，以下语句能够返回至少被订购过两会的productid？ * select productid from orders where count（productid）>1 * select productid from orders where max（productid）>1 * select productid from orders where having count（productid）>1 group by productid * select productid from orders group by productid having count（productid）>1 ### 正确答案及解析 答案：D 顺序为：select, from, where, group by, having, order by, limit ## 题目 57 银行家算法中的数据结构包括有可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need，下列选项中表述正确的是（）。 * `Allocation[i,j]=Max[i,j] +Need[i,j]` * `Need[i,j]= Max[i,j]- Allocation[i,j]` * `Max[i,j]= Allocation[i,j]*Need[i,j]` * `Need[i,j]= Max[i,j]+Allocation[i,j]` ### 正确答案及解析 答案：B ## 题目 58 进行数据库提交操作时使用事务（Transaction）是为了? * 提高效率 * 保证数据一致性 * 网络安全 * 归档数据文件 ### 正确答案及解析 答案：B 数据库事务(Database Transaction) ，是指作为单个逻辑工作单元执行的一系列操作。 事务处理可以确保除非事务性单元内的所有操作都成功完成，否则不会永久更新面向数据的资源。通过将一组相关操作组合为一个要么全部成功要么全部失败的单元，可以简化错误恢复并使应用程序更加可靠。一个逻辑工作单元要成为事务，必须满足所谓的ACID(原子性、一致性、隔离性和持久性)属性。 ## 题目 59 以下代码的输出结果是? ```cpp #define a 10 void foo(); main(){ printf("%d..",a); foo(); printf("%d",a); } void foo(){ #undef a #define a 50 } ``` ### 正确答案及解析 答案：10..10 宏定义是在编译器预处理阶段中就进行替换了，替换成什么只与define和undefine的位置有关系，与它们在哪个函数中无关。 以本题为例：#define a 10 到 #undef a之间的代码在预处理阶段就将a全部换为10，#define a 50后面的代码会将a替换为50。 如果没有#define a 50后面再使用a，编译器就会报错了。 ## 题目 60 采用可重定位分区分配方式，（）。 * 使用户程序占用若干不连续的内存空间 * 解决了碎片问题 * 为用户编写程序提供方便 * 扩充了内存容量，提供了虚拟存储器 ### 正确答案及解析 答案：B 可重定位分区分配方式也是属于连续分配方式的，只是它在内存碎片很多而导致的程序不能放入内存时，进行“紧凑”（可能会移动原来的数据的，所以此时就需要重定位啦\~紧凑完了，就能放进去啦\~\~），所以A是不对的哦 ## 题目 61 mysql数据库有选课表 `learn(student_id int,course_id int)`,字段分别表示学号和课程编号，现在想获取每个学生所选课程的个数信息，请问如下的sql语句正确的是 * `select student_id,sum(course_id)from learn` * `select student_id,count(course_id)from learn group by student_id` * `select student_id,count(course_id)from learn` * `select student_id,sum(course_id)from learn group by student_id` ### 正确答案及解析 答案：B `group by student_id` 是按学生号分组，每个编号的学生可能有多门课程，但不可能课程编号会重复，所以直接使用 `count(course_id)`，否则就要使用 `count(disctinct(course_id))` ## 题目 62 若度为m的哈夫曼树中,其叶结点个数为n,则非叶结点的个数为() ### 正确答案及解析 答案：`[(n-1)/(m-1)]` 首先说明一点,我们平时一般所说的哈夫曼树是指最优二叉树,也叫做严格二叉树（注意不是完全二叉树）,但是哈夫曼树完全不局限于二叉树,也存在于多叉树中,即度为m的哈夫曼树,也叫最优m叉树,严格m叉树（注意不是完全m叉树） 这题表示哈夫曼树的节点 的度要么是0要么是m 设度不为0（即非叶结点 ）的个数为X 则总的结点数为：X+n 除根结点外，其余的每一个结点都有一个分支连向一个结点，对于度为m的每个结点都有m个分支，而度为0的结点是没有分支的，所以从分支的情况来看 总的结点数位：X\*m + 1（这里的1为根结点） 两者相等，所以答案是 （n-1) / （m-1） ## 题目 63 计算斐波那契数列第n项的函数定义如下： * 117 * 137 * 157 * 177 ### 正确答案及解析 答案：D ``` 若C(n) 表示计算次数，则 C(0) = 1; C(1) = 1; C(n) = C(n-1) + C(n-2) + 1; n>=2; 故： C(0) = 1; C(1) = 1; C(2) = 1 + 1 + 1 = 3; C(3) = 3 + 1 + 1 = 5; C(4) = 5 + 3 + 1 = 9; C(5) = 9 + 5 + 1 = 15; …… ``` ## 题目 64 给定下列程序，那么执行 `printf("%d\n", foo(20, 13));` 的输出结果是 `________`。 ```cpp int foo(int x, int y){ if (x <= 0 || y <= 0) return 1; return 3 * foo( x-6, y/2 ); } ``` ### 正确答案及解析 答案：81 分析： `3*6 < 20 < 4*6`,递归 4层。 `log13 < log16 = 4;` 所以结果为 `3^4 = 81`. ## 题目 65 设图 G 的相邻矩阵如下图:则 G 的顶点数和边数分别为() ``` 01111 10100 11011 10101 10110 ``` ### 正确答案及解析 答案：5, 8 总共有5行，所以有5个顶点。 在无向图里，矩阵里任意两个1为两个顶点的连线，总共有8对。所以边数为8。 ## 题目 66 （）操作不是P操作可完成的。 * 为进程分配处理机 * 使信号量的值变小 * 可用于进程的同步 \*使进程进入阻塞状态 ### 正确答案及解析 答案：A P操作分配的是我们申请的资源，并不是处理机 ## 题目 67 关于下列操作哪个复杂度为O(1)? * `vector<>` 中插入元素(动态数组) * `set` 中查找元素 * `hasp_map` 中查找元素 * `deque`尾部删除元素 ### 正确答案及解析 答案：CD 双端队列，尾部插入一个应该是O(1)吧 ## 题目 68 同一进程下的线程可以共享以下？ * stack * data section * register set * file fd ### 正确答案及解析 答案：BD 线程共享的内容包括： 1. 进程代码段 2. 进程的公有数据(利用这些共享的数据，线程很容易的实现相互之间的通讯) 3. 进程打开的文件描述符 4. 信号的处理器 5. 进程的当前目录 6. 进程用户ID与进程组ID 线程独有的内容包括： 1. 线程ID 2. 寄存器组的值 3. 线程的堆栈 4. 错误返回码 5. 线程的信号屏蔽码 ## 题目 69 下面描述中正确的为： * 线性表的逻辑顺序与物理顺序总是一致的。 * 线性表的顺序存储表示优于链式存储表示。 * 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。 * 二维数组是其数组元素为线性表的线性表。 ### 正确答案及解析 答案：CD ## 题目 70 在下列说法中，哪个是错误的（ ） * 若进程A和进程B在临界段上互斥，那么当进程A处于该临界段时，它不能被进程B中断 * 虚拟存储管理中采用对换(swapping)策略后，用户进程可使用的存储空间似乎增加了 * 虚拟存储管理中的抖动(thrashing)现象是指页面置换(page replacement)时用于换页的时间远多于执行程序的时间 * 进程可以由程序、数据和进程控制块(PCB)描述 ### 正确答案及解析 答案：AC 注意A选项，A进程是可以被B进程中断的，只是B不能进入临界区。 c选项中：是请求分页虚拟存储管理。 当需要执行否条的指令或使用某个数据而发现他们不再内存中时候，会产生缺页异常。 系统从磁盘中把此指令或数据所在的页面装入。缺页异常是由硬件所产生的一种特殊终端信号，其中当中断率较高时，整个系统的页面调度非常频繁造成大部分时间都花费在来回调度上，而不是执行任务，这种现象叫做“抖动”。——《操作系统》 ## 题目 71 数组不适合作为任何二叉树的存储结构() ### 正确答案及解析 答案：错的 二叉树的顺序存储就是利用数组实现的。也就是用一组连续的存储单元存放二叉树中的结点。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。 ## 题目 72 程序出错在什么阶段（）? ```cpp int main(void) { http://www.taobao.com cout << "welcome to taobao" << endl; return 0; } ``` * 预处理阶段出错 * 编译阶段出错 * 汇编阶段出错 * 链接阶段出错 * 运行阶段出错 * 程序运行正常 ### 正确答案及解析 答案：Ｆ "http:"是goto语句的标记，＂//＂是注释，注释内容为"[www.taobao.com](http://www.taobao.com)" ## 题目 73 下列哪一个不属于关系数据库的特点？ * 数据冗余度小 * 数据独立性高 * 数据共享性好 * 多用户访问 ### 正确答案及解析 答案：D 关系数据库的特点： * 数据库存在的一个目的就是统一管理数据，减少数据冗余度，A正确； * 数据独立性，指数据和其管理软件独立，以及数据及其结构的独立，B正确； * 数据库就是为了方便用户之间共享数据，C正确； * 数据库中存在锁机制，如果多用户访问可能导致数据不一致等，D不正确。 ## 题目 74 通道能够完成（）之间数据的传输。 * CPU与外设 * 内存与外设 * CPU与主存 * 外设与外设 ### 正确答案及解析 答案：B CPU正在工作，突然想到要与外设通信，于是发命令给通道，然后接着做自己的工作。 通道接到命令后，接通外设与内存，并在他们之间传递数据，等数据传递完成后，通知CPU进行处理。 ## 题目 75 某IP地址192.168.48.10，掩码为255.255.255.128，其所在的子网为()，广播地址为()，有效的主机IP地址范围从()到(). ### 正确答案及解析 答案：192.168.48.0/192.168.48.127/192.168.48.1 到 192.168.48.126 255转换为2进制是 11111111 128转换为2进制是 10000000 对地址 192.168.48.10和掩码255.255.255.128 进行 and操作 得到 子网 192.168.48.0 ip地址和掩码做and操作后， 得到这个子网地址的都属于这个ip段， 192.168.48.0 ... 192.168.48.127和 255.255.255.128进行and操作后都是 192.168.48.0 其中， 192.168.48.127为广播地址， 192.168.48.0 ... 192.168.48.126为有效地址 ## 题目 76 ### 正确答案及解析 答案： ## 题目 77 ### 正确答案及解析 答案： ## 题目 78 ### 正确答案及解析 答案： ## 题目 79 ### 正确答案及解析 答案： ## 题目 80 ### 正确答案及解析 答案： ## 题目 81 ### 正确答案及解析 答案： ## 题目 82 ### 正确答案及解析 答案： ## 题目 83 ### 正确答案及解析 答案： ## 题目 84 ### 正确答案及解析 答案： ## 题目 85 ### 正确答案及解析 答案： ## 题目 86 ### 正确答案及解析 答案： ## 题目 87 ### 正确答案及解析 答案： ## 题目 88 ### 正确答案及解析 答案： ## 题目 89 ### 正确答案及解析 答案： ## 题目 90 ### 正确答案及解析 答案： ## 题目 91 ### 正确答案及解析 答案： ## 题目 92 ### 正确答案及解析 答案： ## 题目 93 ### 正确答案及解析 答案： ## 题目 94 ### 正确答案及解析 答案： ## 题目 95 ### 正确答案及解析 答案： ## 题目 96 ### 正确答案及解析 答案： ## 题目 97 ### 正确答案及解析 答案： ## 题目 98 ### 正确答案及解析 答案： ## 题目 99 ### 正确答案及解析 答案： --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://l1nwatch.gitbook.io/interview_exercise/ji-suan-ji-zhi-shi/readme1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.