电信20150924笔试题

一、单选题(4)

1、HTTP应答中的500错误是：（）

A．服务器内部出错

B．文件未找到

C．客户端网络不通

D．没有访问权限

解析：常见HTTP状态码及其含义如下：

200：正常；请求已完成。

400：错误请求 — 请求中有语法问题，或不能满足请求。

404：找不到 — 服务器找不到给定的资源；文档不存在。

500：内部错误 — 因为意外情况，服务器不能完成请求。

2、在CPU和内存之间增加cache的作用是（）

A．提高内存稳定性

B．解决内存速度低于CPU的性能瓶颈

C．增加内存容量

D．增加内存容量且加快存取速度

解析：CPU处理数据，硬盘储存数据，内存负责连接CPU和硬盘，存储临时使用的数据。内存只用于暂时存放程序和数据，一旦关闭电源或发生断电，其中的程序和数据就会丢失。

cache名为高速缓冲存储器，cache是存在于主存（内存）与CPU之间的一级存储器，其作用是缓和中央处理器和主存储器之间速度不匹配的矛盾。

3、关于锁和事务描述正确的是（）

A．事务T1获得了数据项D1上的排它锁后就可以对D1做读写操作了

B．按照不同的力度，锁可以分为：表级锁，页级锁，行级锁，列级锁

C．表级锁比行级锁更容易发生死锁

D．SELECT语句不会产生锁

解析：常见的锁有表锁、行锁、页锁、外键锁等

锁有一定的消耗，主要有：获得锁，检查锁是否已经解除，释放锁等，这些操作都会增加系统的开销。表锁开销比较小，但是并发性能也较差，行锁并发性能高，但是需要更多锁，数据库系统一般都支持锁的自动升级，例如一个事务中的锁过多的时候，可能会将行锁升级到表锁。 mysql的各个存储引擎根据不同的应用场景采用不同的锁机制，MyISAM存储引擎采用表锁，InnoDB使用行锁。如果执行alert table之类的操作，服务器也会采用表锁，而忽略存储引擎的锁机制。

页锁，某些数据库支持页锁，页锁粒度介于行锁和表锁之间，用于锁定存放数据的页，1页通常含有n个数据行。

1）表级锁：开销小，加锁快；不会出现死锁；锁定粒度大，发生锁冲突的概率最高，并发度最低。2）行级锁：开销大，加锁慢；会出现死锁；锁定粒度最小，发生锁冲突的概率最低，并发度也最高。3）页面锁：开销和加锁时间界于表锁和行锁之间；会出现死锁；锁定粒度界于表锁和行锁之间，并发度一般。

SELECT会产生共享锁。

4、甲乙两个人答对一道题的概率分别为90%和80%，对于一道判断题，他们都选的“正确”，问这道题正确的概率为（）

A．9/10

B．18/25

C．36/37

D．35/36

解析：

5、有足够量的2分、5分、1分硬币，如果想凑齐一元钱，可以有（）中方法

A．541

B．270

C．1024

D．128

解析：

package basic;

public class cal1 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int count=0;
        for(int i=0;i<=20;i++){
            for(int j=0;j<=50;j++){
                for(int k=0;k<=100;k++){
                    if(5*i+2*j+k==100){
                        count++;
                    }
                }
            }
        }
        System.out.println(count);//print "541"
    }
}

6、65,8,50,15,37,24,()，括号中的数字是（）

A．25

B．26

C．22

D．27

7、有关下述Java代码描述正确的是（）

public class TestClass{

private static void testMethod(){

System.out.println(“testMethod”);

}

public static void main(String[] args){

((TestClass)null).testMethod();

}

A．编译通过，运行异常，报NullPointerException

B．编译通过，运行异常，报IllegalArgumentException

C．编译通过，运行异常，报NoSuchMethodException

D．运行正常，输出testMethod

package basic;
public class TestClass{
    private static void testMethod(){
        System.out.println("testMethod");
    }
    public static void main(String[] args){
        ((TestClass)null).testMethod();//print "testMethod"
    }
}

8、设有一个用数组Q(1..m)表示的环形队列，约定f为当前队头元素在数组中的下标号，r为队尾元素的后一位置(按顺时针方向)，若队列非空，则计算队列中元素个数的公式是（）

A．(m+r-f)mod m

B．r-f

C．(m-r-f)mod m

D．(m-r+f) mod m

9、设有向图G=(V,E)，顶点集V={V0,V1,V2,V3}，边集E={<v0,v1>,<v0,v2>,<v0,v3>,<v1,v3>}，若从顶点V0开始对图进行深度优先遍历，则可能得到的不同遍历序列个数为

A．2

B．3

C．4

D．5

10、下列选项中，不能构成折半查找中关键字比较序列的是（）

A．500，200，450，180

B．500，450，200，180

C．180，500，200，450

D．180，200，500，450

二、多选题

1、使用ping命令ping另外一台主机，收到正确的应答，能说明（）

A．目的主机可达

B．源主机的ICMP软件和IP软件运行正常

C．目的主机的ICMP软件和IP软件运行正常

D．ping报文经过的路由选择正常

2、关于进程和线程，下列选项中说法正确的是（）

A．线程可以与同进程中的其他线程共享数据，但拥有自己的栈空间，拥有独立的执行序列

B．线程是并发程序在执行过程中分配和管理资源的基本单位

C．一个进程是PCB结构与程序的数据的组合

D．线程的改变不仅代表了CPU执行过程的改变，也发生了进程所拥有资源变化

3、事务具有多个特性，其中包括（）

A．一致性

B．持续性

C．原子性

D．隔离性

解析：对数据库事务拥有的四个特性解释如下：

原子性（Atomicity）：事务作为一个整体被执行，包含在其中的对数据库的操作要么全部被执行，要么都不执行。

一致性（Consistency）：事务应确保数据库的状态从一个一致状态转变为另一个一致状态。一致状态的含义是数据库中的数据应满足完整性约束。

隔离性（Isolation）：多个事务并发执行时，一个事务的执行不应影响其他事务的执行。

持久性（Durability）：已被提交的事务对数据库的修改应该永久保存在数据库中。

4、下面选项正确的是（）

A．二维数组和多维数组均不是特殊的线性结构

B．向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度

C．如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零

D．不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)

解析：多位数组是一种最简单的非线性结构，它采用顺序存储结构。线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。关于广义表，是一种非线性的数据结构。常见的非线性结构有：二维数组，多维数组，广义表，树(二叉树等)，图。

5、已知一段文本有1382个字符，使用了1382个字节进行存储，这段文本全部是由a、b、c、d、e这5个字符组成，a出现了354次，b出现了483次，c出现了227次，d出现了96次，e出现了232次，对这5个字符使用哈夫曼（Huffman）算法进行编码，则以下哪些说法正确（）

A．使用哈夫曼算法编码后，用编码值来存储这段文本将花费最少的存储空间

B．使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值是唯一的

C．使用哈夫曼算法进行编码，a、b、c、d、e这5个字符对应的编码值可以有多个，每个字符编码的位（bit）数是确定的

D．b这个字符的哈夫曼编码值位数应该最短，d这个字符的哈夫曼编码值位数应该最长

解析：哈夫曼编码是一种可变长的编码，它依据字符出现的概率来决定字符编码的长度，使得出现概率大的字符编码长度短，出现概率小的字符的编码长度长，于是可以减少整体的编码的长度。

三、编程题

1、编写一个函数实现：判断一个字符串是否重复字符，字符集为ASCII。

要求：不允许使用额外的数据结构

package basic;

public class RepeatOrNot {
    public static boolean judge(String str){
        char[] chars=str.toCharArray();
        for(int i=0;i<chars.length;i++){
            char c=chars[i];
            String cStr=String.valueOf(c);
            str=str.replaceFirst(cStr, " ");
            if(str.indexOf(cStr)!=-1){
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(RepeatOrNot.judge("abca"));//print "false"
        System.out.println(RepeatOrNot.judge("abcd"));//print "true" 
    }

}

2、对于一个字符串，请设计一个高效算法，找到第一次重复出现的字符。

测试样例：

“qywyer23tdd”,11

返回：y

package basic;

import java.util.HashMap;
import java.util.Map;

public class FindTheFirstRepeatChar {
    private static String getFirstRepeatChar(String str){
        char[] chars=str.toCharArray();
        Map<String,Integer> maps=new HashMap<String,Integer>();
        char c;
        String cStr;
        for(int i=0;i<chars.length;i++){
            c=chars[i];
            cStr=String.valueOf(c);
            if(maps.containsKey(cStr)){
                return cStr;
            }else{
                maps.put(cStr, 1);
            }
        }
        return "";
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println(FindTheFirstRepeatChar.getFirstRepeatChar("qywyer23tdd"));
        System.out.println(FindTheFirstRepeatChar.getFirstRepeatChar("qywaqer23tdd"));
    }

}

3、输入一个字符串，内有数字和非数字字符，如：ak123x456 17960?302gx14563，将其中连续的数字作为一个整体，依次存放到一个数组a中，例如123放入a[0],456放入a[1],……，编程统计其共有多少个整数，并输出这些数。

package basic;

import java.util.ArrayList;
import java.util.List;

public class GetNumbers {
    private static void getNumbers(String str) {
        char[] chars = str.toCharArray();
        int k, flag = 0;
        List a = new ArrayList();
        for (int i = 0; i < chars.length; i++) {
            k = Integer.valueOf(chars[i]);
            if (k >= 48 && k <= 57) {
                flag = flag * 10 + (k-48);
            } else if (flag != 0) {
                a.add(flag);
                flag = 0;
            }
        }
        if (flag != 0) {
            a.add(flag);
        }
        for (Object o : a) {
            System.out.println(o);
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        GetNumbers.getNumbers("abc09ddd124fff456 7898");//print "9 124 456 7898"
    }

}

参考博客及书籍：

数据库锁机制：http://www.cnblogs.com/zhouqianhua/archive/2011/04/15/2017049.html

进程与线程的区别：http://www.cnblogs.com/way_testlife/archive/2011/04/16/2018312.html

哈夫曼算法详解：http://noalgo.info/411.html

关于进程与线程的习题：http://blog.csdn.net/livelylittlefish/

http://blog.csdn.net/livelylittlefish/

http://c.biancheng.net/cpp/html/2643.html

数据结构c语言版陈明